Test data generation with a Kalman filter-based adaptive genetic algorithm

Highlights

• We introduce a new approach for generating test data, based on adaptive optimisation.

• The adaptive optimisation framework uses feedback from the optimisation process to adjust parameter values of a genetic algorithm during the search.

• Our approach is compared to a state of the art test data optimisation algorithm that does not adapt parameter values online, and a conspicuous adaptive optimisation algorithm, outperforming both methods in a wide range of problems.

Abstract

Software testing is a crucial part of software development. It enables quality assurance, such as correctness, completeness and high reliability of the software systems. Current state-of-the-art software testing techniques employ search-based optimisation methods, such as genetic algorithms to handle the difficult and laborious task of test data generation. Despite their general applicability, genetic algorithms have to be parameterised in order to produce results of high quality. Different parameter values may be optimal for different problems and even different problem instances. In this work, we introduce a new approach for generating test data, based on adaptive optimisation. The adaptive optimisation framework uses feedback from the optimisation process to adjust parameter values of a genetic algorithm during the search. Our approach is compared to a state of the art test data optimisation algorithm that does not adapt parameter values online, and a representative adaptive optimisation algorithm, outperforming both methods in a wide range of problems.

Introduction

Search-based optimisation methods, such as genetic algorithms, ant colony optimisation and simulated annealing have successfully been applied in solving a wide range of software testing problems (Ahmed, Hermadi, 2008, Ferrer, Chicano, Alba, 2012, Harman, Lakhotia, McMinn, 2007, Harman, McMinn, 2010, Mairhofer, Feldt, Torkar, 2011, McMinn, 2004). The commonality of these approaches is that they aim at optimising the quality of a given test data set. Quality could be measured with respect to certain coverage criteria, e.g. branch, statement, and method coverage for source code, or metrics such as transition coverage for model-based testing. Beside these function-oriented approaches, a variety of methods focus on non-functional aspects of test data optimisation, such as searching for input situations that break memory or storage requirements, automatic detection of memory leaks, stress testing and security testing. A systematic literature review of search-based testing for non-functional system properties by Afzal et al. (2009) presents a comprehensive overview of these methods.

Genetic algorithms (GAs) are among the most frequently applied search-based optimisation method in test data generation (Aleti et al., 2013). GAs provide approximate results where exact approaches cannot be devised and optimal solutions are hard to find. They can be used by practitioners as a ‘black box’, without mastering advanced theory, whereas more sophisticated exact approaches are tailored to the specific mathematical structure of the problem at hand, and can become completely inapplicable if small aspects of the problem change. Another advantage of GAs compared to traditional methods, such as gradient descent-based algorithms is the stochastic element which helps them get out of local optima.

In recent years, it has been acknowledged that the performance of GAs depend on the numerous parameters, such as crossover rate, mutation rate and population size (Aleti, 2012, Eiben, Hinterding, Michalewicz, 2007, Eiben, Smit, 2011). Algorithm parameters determine how the search space is explored. They are responsible for the flexibility and efficiency of the search procedure, and when configured appropriately, produce high-quality results regardless of the search space difficulty. Because of the influence of parameter values on algorithm performance, poor algorithm parameterisation hinders the discovery of solutions with high quality (Eiben, Hinterding, Michalewicz, 2007, Eiben, Smit, 2011, Lobo, 2011). It has been acknowledged that parameters required for optimal algorithm performance are not only domain-specific, but also have to be chosen based on the problem instance at hand (Eiben and Schut, 2008).

The configuration of the algorithm is usually the responsibility of the practitioner, who often is not an expert in search-based algorithms. General guidelines for successful parameter values give different recommendations: e.g. De Jong (1995) recommends using 0.6 for crossover rate, Grefenstette (1986) suggests 0.95, whereas Schaffer et al. (1989) recommends any value in the range [0.75, 0.95]. These general guidelines conflict with each other, because each one reports the best parameter configuration of a GA for a particular class of problems. For a newly arising problem, the search space is typically unknown, hence it is hard to formulate any general principles about algorithm parameter configurations for universal applicability (Mitchell, 1996). In these circumstances, algorithm parameterisation presents itself as an optimisation problem in its own right (Eiben and Smit, 2011). To save time, practitioners tend to configure the GA based on a few preliminary runs, where different parameter values are tried in an attempt to fine-tune the algorithm to a particular problem (Eiben and Smit, 2011). Depending on the number of parameters and their possible values, investigative trials for parameter optimisations can themselves be attempts to solve a combinatorially complex problem. Even if parameters are tuned to their optimal values, there is no guarantee that the performance of the algorithm will be optimal throughout the optimisation process. In fact, it has been empirically and theoretically demonstrated that different parameter settings are required for different stages of the optimisation process (Bäck, 1992, Bäck, Eiben, van der Vaart, 2000, Cervantes, Stephens, 2009, Hesser, Manner, 1991, Smith, Fogarty, 1996, Stephens, Olmedo, Vargas, Waelbroeck, 1998, Thierens, 2002). This means that tuning parameter values before the optimisation process does not guarantee optimal GA performance. This problem has been tackled by many researchers in the optimisation community, who propose to set GA parameter values during the run using feedback from the search, known as adaptive parameter control (Corne, Oates, Kell, 2002, Davis, 1989, Eiben, Hinterding, Michalewicz, 2007, Fialho, Costa, Schoenauer, Sebag, 2010, Goldberg, 1989, Hong, Wang, Chen, 2000, Igel, Kreutz, 2003, Julstrom, 1995, Lobo, Goldberg, 1997, Schlierkamp-Voosen, Mühlenbein, 1994, Tuson, Ross, 1998). The intuitive motivation comes from the way the optimisation process unfolds from a more diffused global search, requiring parameter values responsible for the exploration of unseen areas of the search space, to a more focused local optimisation process, requiring parameter values which help with the convergence of the algorithm.

In essence, adaptive parameter control methods monitor the behaviour of a GA run, and use the performance of the algorithm to adapt parameter values, such that successful parameter values are propagated to the next generation. The majority of adaptive parameter control methods found in the literature belong to the class of probability matching techniques (Corne, Oates, Kell, 2002, Davis, 1989, Hong, Wang, Chen, 2000, Igel, Kreutz, 2003, Julstrom, 1995), in which the probability of applying a parameter value is proportional to the quality of that parameter value. The earliest approaches (Hong, Wang, Chen, 2000, Igel, Kreutz, 2003) lacked the exploration of parameter values if the feedback from the algorithm was not in their favour in the initial phases of the process. In later work, a minimum selection probability was introduced (Igel and Kreutz, 2003), to ensure that under-performing parameter values did not disappear during the optimisation, in case they were beneficial in the later stages of the search. One of the more recent and mature examples of probability matching is the work by Igel and Kreutz (2003), where the selection probability for each parameter value incorporates a minimum probability of selection.

These adaptive parameter control methods assume that the improvement in the quality of the solutions is directly related to the use of certain parameter values. However, GAs are stochastic systems that may produce different results for the same parameter values (DeJong, 2007). Ideally, the randomness induced by the stochastic behaviour of GAs should be taken care of by the parameter control strategy. To address this issue, we introduce an adaptive genetic algorithm, which adjusts algorithm parameters during the optimisation process using a Kalman filter. The Kalman filter-based genetic algorithm (KFGA) redefines parameter values repeatedly based on a learning process that receives its feedback from the optimisation algorithm. The Kalman filter is employed to reduce the noise factor from the stochastic behaviour of GAs when identifying the effect of parameter values on the performance of the algorithm. KFGA outperforms a GA with pre-tuned parameter values and the probability matching technique by Igel and Kreutz (2003) when solving the problem of test data generation. The proposed method consistently finds test suites with better branch coverage than the state-of-the-art, as shown by the experiments performed on a set of open-source problem instances.