Overview: Evolutionary Algorithms

Schriftenreihe CIplus, Band 2/2015 Herausgeber: T. Bartz-Beielstein, W. Konen, H. Stenzel, B. Naujoks Overview: Evolutionary Algorithms Thomas Bartz-Beielstein, J¨urgen Branke, J¨orn Mehnen, Olaf Mersmann Overview: Evolutionary Algorithms1 Thomas Bartz-Beielstein Cologne University of Applied Sciences J¨ urgen Branke Warwick University J¨ orn Mehnen Cranfield University Olaf Mersmann Cologne University of Applied Sciences Keywords Evolutionary algorithms, Bio-inspired search heuristics, Evolution strategies, Genetic algorithms, Genetic programming Abstract Evolutionary algorithm is an umbrella term used to describe population based stochastic direct search algorithms that in some sense mimic natural evolution. Prominent representatives are genetic algorithms, evolution strategies, evolutionary programming, and genetic programming. Based on the evolutionary cycle, similarities and differences between theses algorithms are described. We briefly discuss how evolutionary algorithms can be adapted to work well in case of multiple objectives, dynamic or noisy optimization problems. We look at the tuning of algorithms and present some recent developments from theory. Finally, typical applications of evolutionary algorithms for real-world problems are shown, with special emphasis on data mining applications. Evolutionary Algorithms in a Nutshell Invention and development of the first evolutionary algorithms is nowadays attributed to a few pioneers who independently suggested four related approaches (Bartz-Beielstein et al., 2010b). •Fogel et al. (1965) introduced evolutionary programming (EP) aiming at evolving finite automata, later at solving numerical optimization problems. 1This is the pre-peer reviewed version of the following article: Bartz-Beielstein, T. and Branke, J. and Mehnen, J. and Mersmann, O.: Evolutionary Algorithms. WIREs Data Mining Knowl Discov 2014, 4:178195. doi:10.1002/widm.1124 1 •Holland (1973) presented genetic algorithms (GA), using binary strings, which were inspired by the genetic code found in natural life, to solve combinatorial problems. •Evolution strategies (ES) as proposed by Rechenberg (1971) and Schwefel (1975) were motivated by engineering problems and thus mostly used a real-valued representation. •Genetic programming (GP), suggested by Koza (1992b) emerged in the early 1990s. GP explicitly performs the optimization of programs. Since about the same time, these four techniques are collectively referred to as evolutionary algorithms (EAs), building the core of the evolutionary computation (EC) field. Evolutionary algorithms are understood as population based stochastic direct search algorithms that in some sense mimic the natural evolution. Points in the search space are considered as individuals (solution candidates), which form a population. Their fitness value is a number, indicating their quality for the problem at hand. Besides initialization and termination as necessary constituents of every algorithm, EAs can consist of three important factors: A set of of search operators (usually implemented as ’recombination’ and ’mutation’), an imposed control flow, and a representation that maps adequate variables to implementable solution candidates (the so-called ’genotype-phenotype mapping’). A widely accepted definition reads as follows: Evolutionary algorithm: collective term for all variants of (probabilistic) optimization and approximation algorithms that are inspired by Darwinian evolution. Optimal states are approximated by successive improvements based on the variation-selection-paradigm. Thereby, the variation operators produce genetic diversity and the selection directs the evolutionary search (Beyer et al., 2002). Although different EAs may put different emphasis on the search operators mutation and recombination, their general effects are not in question. Mutation means neighborhood based movement in the search space that includes the exploration of the ’outer space’ currently not covered by a population, whereas recombination rearranges existing information and so focuses on the ’inner space’. Selection is meant to introduce a bias towards better fitness values. It can be applied at two stages: When parents are selected from the population to generate offspring (mating selection), and after new solutions have been created and need to be inserted into the population, competing for survival (environmental selection or survival selection). GAs primarily focus on mating selection, ESs utilize only environmental selection. A concrete EA may contain specific mutation, recombination, or selection operators, or call them only with a certain probability, but the control flow is usually left unchanged. Each of the consecutive cycles is termed a generation. 2 Concerning the representation, it should be noted that most empiric studies are based on canonical forms such as binary strings or real-valued vectors, whereas many real-world applications require specialized, problem dependent representations. B¨ ack (1996) compares GAs, ES, and EP. For an in-depth coverage on the defining components of an EA and their connection to natural evolution, see Eiben & Schoenauer (2002) and Eiben & Smith (2003). Beyer et al. (2002) provide a very useful glossary, which covers the basic definitions. De Jong (2006) presents an integrated view. The remainder of this article is structured as follows. After introducing prominent representatives of EAs, namely evolutionary programming, genetic algorithms, evolution strategies and genetic programming, the following special topics are discussed: Multi-objective optimization, dynamic and stochastic optimization, tuning, theory, and applications. The article concludes with a short list of EA related software. The Family of Evolutionary Algorithms Starting with its oldest member, namely EP, the family of EAs is described in the following paragraphs. Although EP, GA, ES, and GP have been invented independently and are described separately, it is unquestioned that these algorithms are specific instances of the more general class of EAs (De Jong, 2006) and that it is nowadays difficult to distinguish theses algorithms from each other (Beyer, 2001). Only one differentiation is possible even today: EP algorithms do not use recombination. Today, there is a huge set of very sophisticated and problem-specific EA implementations, and this article can only scotch the surface. Evolutionary Programming Evolutionary programming uses a fixed program structure, while its numerical parameters are allowed to evolve. The essential steps of the EP approach can be described as follows (Yao et al., 1999): (i) generate offspring by mutating the individuals in the current population and (ii) select the next generation from the offspring and parent population. These key ideas are similarly used in ES, GP, and GAs. However, while ES often used deterministic selection, selection is often probabilistic in EP. EP operates on the natural problem representation, thus no genotype-phenotype mapping is used. Contrary to GAs and ES, recombination (crossover) is not used in EP. Only mutation is used as the variation operator. Algorithm 1 provides a pseudocode listing of an EP algorithm. The steps of an EA are implemented as follows: first, individuals, which form the population, are randomly generated (line 1). Random initialization is probably the simplest initialization 3 Algorithm 1: Evolutionary programming algorithm 1population = InitializePopulation(populationSize, problemDimension); 2evaluatePopulation(population); 3bestSolution = getBestSolution(population); 4while testForTermination == false do 5offspring = ∅; 6for parenti∈population do 7offspringi= mutate(parenti); 8offspring = {offspring} ∪ offspringi; 9evaluatePopulation(offspring); 10 bestSolution = getBestSolution(offspring,bestSolution); 11 population = {population}∪{offspring}; 12 population = environmentalSelection(population); 13 Return(bestSolution); method. Other, more problem specific initialization methods are possible. For example, already known good solutions can be used as seeds (starting points) for the initial population. The evaluation function (line 2) assigns a quality measure or fitness value to each individual. If the original problem to be solved is an optimization problem, the term objective function is used. Mutation is a stochastic variation operator, which is applied to one individual (line 7). Before the next round in the evolutionary cycle is started, the environmental (or survivor) selection is performed (line 12) that removes some individuals in order to keep the population size constant. The decision which individuals to include in the next generation is usually based on fitness values. This evolutionary cycle continues until the termination criterion is fulfilled (line 4). Fogel (1999) summarizes experiences from forty years of EP, and Fogel & Chellapilla (1998) revisit and compare EP with other EA approaches. Genetic Algorithms Genetic algorithms are a variant of EA, which, in analogy to the biological DNA alphabet, originally focused on (bit) string representations. However, alternative encodings have been considered for the representation issue, such as real-coded GAs (Goldberg, 1990; Herrera et al., 1998). Binary strings can be decoded in many ways to integer or real values. The string corresponds to the genotype of the individual. The phenotype of the individual is realized by a mapping onto the object parameters, the so-called ’genotype-phenotype mapping’. For example, a binary string that is eight bits long can encode integers between 0 and 255. The genotype ’00000011’ decodes the integer value 3. The fitness of the individual depends on the optimization problem. 4 A typical (mating) selection method in GAs is fitness-proportional selection. The probability that an individual is selected for mating depends on its fitness. For example, if a population consists of an individual with fitness value 1 and a second individual with fitness 3, then there is a probability of 1/(1+3) = 1/4for selecting the first individual and of 3/(1 + 3) = 3/4of selecting the second individual. Many other selection methods have been developed for GAs, such as tournament selection. A tournament is a simple comparison of the fitness values of a small randomly chosen set of individuals. The individual with the best fitness is the winner of the tournament and will be selected for the recombination (crossover) step. Mutation adds new information to the population and guarantees that the search process never stops. A simple mutation method is bit-flipping for binary encoded individuals: at a randomly chosen position, a ’0’ is changed to a ’1’ and vice-versa. For example, the genotype ’00000011’ can be mutated to ’00000010’, if the eighth bit is flipped. Mutation can be performed with a certain probability, which can be decreased during the search. Besides mutation, crossover is an important variation operator for GAs. It has the following two purposes: (i) reduction of the search to more promising regions and (ii) inheritance of good gene properties. One-point crossover is a very simple form of crossover. At a randomly chosen position, segments from two individuals are exchanged. Consider two individuals, say ’10101010’ and ’11110000’. One-point crossover at the third position results in two new individuals. The first is ’10110000’ (with bits one to three from the first parent and bits four to eight from the second parent) and the second is ’11110000’, respectively. Other popular crossover methods are two-point crossover and uniform crossover (Sywerda, 1989). Instead of a fitnessbased environmental selection, often a simple generational replacement procedure is used where the newly generated offspring replaces their parents independent of fitness. Algorithm 2 provides a pseudocode listing of an GA. Note that in addition to the operators used by EP, GAs apply mating selection (line 6) and crossover (or recombination). Crossover combines information from two or more individuals (line 8). The newly generated offspring replaces the parental individuals in the replacement procedure (line 14). Goldberg (1989) and Whitley (1994) are classical introductions to GAs. Evolution Strategies The first ES, the so-called (1+1)-ES or two membered evolution strategy, uses one parent and one offspring only. Two rules have been applied to these candidate solutions: Apply small, random changes to all variables simultaneously. If the offspring solution is better (has a better function value) than the parent, take it as the new parent, otherwise retain the parent. Schwefel (1995) describes this algorithm as ’the minimal concept for an imitation of organic evolution.’ The first (1+1)-ES used binomially distributed mutations (Schwefel, 1965). These have been replaced by continuous variables and Gaussian mutations, which enable the (1+1)-ES to generate larger mutations and thereby possibly escape from local optima. Rechenberg (1971) presented an approximate analysis of the (1+1)-ES. His analysis showed that the optimal mutation 5 Algorithm 2: Genetic algorithm 1pop = InitializePopulation(populationSize, problemDimension); 2evaluatePopulation(population); 3bestSolution = getBestSolution(population); 4while testForTermination == false do 5offspring = ∅; 6parents = matingSelection(population); 7for parent1, parent2∈parents do 8(offspring1,offspring2) = crossover(parent1, parent2); 9offspring1= mutate(offspring1); 10 offspring2= mutate(offspring2); 11 offspring = {offspring} ∪ offspring1∪offspring2; 12 evaluatePopulation(offspring); 13 bestSolution = getBestSolution(offspring); 14 population = replace(population, offspring); 15 Return(bestSolution); rate corresponds to a success probability that is independent of the problem dimension. The optimal success probability is approximately 1/5 for a linear and also for a quadratic objective function. These results inspired the famous one-fifth rule: Increase the mutation rate if the success rate is larger than 1/5, otherwise, decrease the mutation rate. Schwefel’s evolution strategy (ES) is a variant of EA, which generally operates on the natural problem representation and thus uses no genotype-phenotype mapping for object parameters. In addition to the usual set of decision variables, the individual also contains a set of so-called strategy parameters that influence the mutation operator (e.g., the step size). The ES employs mutation and recombination as variation operators. Beyer & Schwefel (2002) present a comprehensive introduction to ES. Algorithm 3 provides a pseudocode listing of an ES. Please not that the strategy parameters are also subject to recombination (line 8) and mutation (line 9). The covariance matrix adaptation evolution strategy (CMA-ES) is a variant of ES, which was developed for difficult non-linear non-convex optimization problems in continuous domains (Hansen & Ostermeier, 1996). To motivate the development of the CMA-ES, consider the following black-box optimization problem minimize x∈Rnf(x)(1) and the related problem minimize x∈Rn ˜ f(x) := f(Rx).(2) Here Ris an n×nrotation matrix2. Clearly we would like an optimization algorithm to show similar performance characteristics when solving problem (1) or (2). But neither 2A rotation matrix is an orthogonal matrix (RT=R−1) with determinant (det R= 1). The set of all n×nrotation matrices forms the special orthogonal group SO(n). 6 Algorithm 3: Evolution strategy. 1population = InitializePopulation(populationSize, problemDimension); 2evaluatePopulation(population); 3bestSolution = getBestSolution(population); 4while testForTermination == false do 5offspring = ∅; 6for i = 0 to offspringSize do 7matingPop = matingSelection(population); 8offspringi= recombination (matingPop); 9offspringi= mutate(offspringi); 10 offspring = {offspring} ∪ offspringi; 11 evaluatePopulation(offspring); 12 population = environmentalSelection(population); 13 bestSolution = getBestSolution(population); 14 Return(bestSolution); the (1 + 1)-ES nor Schwefel’s ES are invariant under rotation and therefore will perform quite differently when solving the two problems. To illustrate this, let us consider a simple example. Let n= 2, f(x) = x2 1+ 10x2 2and R=cos(π/4) −sin(π/4) sin(π/4) cos(π/4) . Here Ris a clockwise rotation of x∈Rnaround the origin by 45 degrees. Both fand ˜ freach their global minimum in x∗=0. Their respective function landscape is shown in Figure 1. The optimal sampling distribution for f(x)should have a covariance structure that (locally) matches the contours of the function landscape. If we restrict ourselves to the multivariate Normal distribution, then the optimal sampling distribution for faround the point xis given by Nx, σ 1 0 0 10. This distribution is clearly covered by both the (1 + 1)-ES and Schwefel’s ES. The optimal sampling distribution for ˜ fon the other hand is not within the scope of either algorithm: Nx, σR1 0 0 10. Here, we need to adapt not just the individual’s variances for each parameter but also the covariance structure which models the interdependence between the parameters so that the contour lines of our function and the contour of the search distribution are (locally) similar. It was this insight that gave rise to the development of the original CMA-ES algorithm (Hansen et al., 1995). Instead of only adapting the individual variances in each 7 f(x) x1 x2 1 4 9 9 16 16 25 25 36 36 −2 −1 0 1 2 −2 −1 0 1 2 f ~(x)=f(Rx) x1 x2 1 4 9 9 16 16 25 25 36 36 49 49 64 64 −2 −1 0 1 2 −2 −1 0 1 2 Figure 1: Contour plot of f(x)and ˜ f(x)illustrating the effect of rotation on the function landscape. iteration, a full covariance matrix update is performed based on an estimate of the covariance structure from the current population. In the canonical CMA-ES, offspring is generated by mutating the (sometimes weighted) center of the µparent individuals, which is usually denoted as (µ/µ, λ)-ES. The strategy parameters include the full covariance matrix instead of just the variance for each dimension of the search space. The update of the strategy parameters is calculated using a maximum-likelihood approach. Here the the mean of the search distribution is updated such that the likelihood of selected offsprings is maximized. The covariance matrix is incrementally adapted such that the likelihood of successful search steps is maximized. Because of its richer class of sampling distributions compared to a regular ES and its invariance to rotations of the search space, it is not surprising that the CMA-ES has been very successful at solving both synthetic as well as real-world black-box optimization problems (Kern et al., 2004). It is well suited for problems that are non-convex, nonseparable, ill-conditioned, multi-modal, or if the objective function is noisy. If the objective function is separable, the CMA-ES may not be ideal because it will attempt to learn a covariance structure where there is none to exploit. In such cases a classic ES may outperform the CMA-ES. Recently the update mechanism of the CMA-ES has been recast as a form of natural gradient descent (Wierstra et al., 2008). This has made it possible to adapt the core ideas to other types of continuous search distributions. The tutorial ’Evolution Strategies and CMA-ES’ (Auger & Hansen, 2013) might serve as an introduction to the recent developments in the field of CMA-ES. 8 Parameter control (on-line) is used to change EA parameter values during a run and offers the greatest flexibility and promises the best performance. However, it poses great challenges to EA designers. Eiben et al. (1999) serves as a good starting point. Theory The theoretical analysis made some progress over the last decades, but still many open problems are remaining. Rudolph (1997) investigated convergence properties of ES. Beyer (2001) presents a framework and the first steps toward the theoretical analysis of ES and a recent article by Auger & Hansen (2011) presents global convergence results for ES. The Genetic Programming Theory and Practice (GPTP) Workshop series discuss the most recent developments in GP theory and practice (Yu et al., 2006). Reeves & Rowe (2002) present theoretical results for GAs. The tutorial slides from Rowe (2012) might serve as a good starting point to GA theory. The existence of a population and the combination of several randomized procedures (mutation, recombination, selection) make EA analysis difficult. Computational complexity theory, which can be seen as the corner stone of computer science, is a popular approach for the theoretical analysis of EAs (Wegener, 2005). In application to randomized search heuristics it takes the form of black-box complexity. Jansen (2013) discusses black-box optimization from a complexity-theoretical perspective. However, complexity theory can give paradoxical results, such as assigning a low complexity to very hard problems. New definitions such as parameterized complexity have been recently proposed (Downey & Fellows, 1999). Parameterized complexity classifies computational problems with respect to their number of input parameters. The complexity of a problem is a function in those parameters. Because the complexity of a problem is only measured by the number of bits in the input in classical complexity theory, problems can be classified on a finer scale. Much of the advances in the theory of evolutionary algorithms has studied simplified algorithms on artificial (toy) problems. The application to real-world problems is much more difficult. An interesting approach is based on landscape analysis, Kauffman & Levin (1987) introduced NK fitness landscapes to capture the intuition that both the overall size of the landscape and the number of its local ’hills and valleys’ influence the complexity of objective functions. Computing these features can be used to guide the EA search process. Exploring new methods for designing EAs is also subject of current research (Wierstra et al., 2011; Rothlauf, 2011). And, last but not least, there are many fundamental questions on their working principles for multi-objective optimization problems, which still remain unsolved (Coello et al., 2006). 15 Applications Analyzing the papers published in the most popular EA conferences (i.e., GECCO, WCCI, PPSN) reveals that the top four fields of EA applications are in engineering (parameter optimization), medicine, scheduling, and image analysis. The following paragraphs describe important considerations that are necessary for applying EAs in practice. Choosing the Right Model Many classical algorithms require simplified problems (e.g., quadratic functions or differentiability) to guarantee exact solutions, whereas EAs generate approximate solutions on the natural problem. EAs are able to work on a model of the real problem, but cannot guarantee convergence to the global optimum (Michalewicz & Fogel, 2004). The design of a fitness function should be concise. Overly detailed functions may use too many parameters which impact negatively on the performance of the search algorithm. As a rule of thumb maybe a dimension of 30 is typically well manageable by an EA while any number above 300 may be called high dimensional in evolutionary terms. Linear programming such as CPLEX can easily deal with several thousand parameters while being limited to linear problems only. Kordon et al. (2005) describe a methodology how to deal with problems in industry. They integrate EAs with statistical methods, neural networks, and support vector machines and describe applications in the areas of inferential sensors, empirical emulators of mechanistic models, accelerated new product development, complex process optimization, and effective industrial design of experiments. Constraints When dealing with real-world problems constraints play a major role as almost all real-world problems have to take some kind of limitations of the parameter space into account. Evolutionary algorithms can deal with constraints though special techniques such as the application of penalty functions, decoders, repair mechanisms, constraint preserving operators, or other techniques need to be used. Sometimes it could be worthwhile reformulating a constraint as an objective and vice versa. This technique can be particularly useful in multi-objective optimization where the algorithms are designed to deal with several objectives at the same time. Constraints can also be imposed gradually so that the algorithm may violate constraints in its early explorative stage while getting constrained to the true feasible solution space as the population matures. Although theoretically evolutionary algorithms can find solutions anywhere in the solution space, in reality constraints can direct the algorithms into a suboptimal area having only a very slim chance to escape. Starting the algorithm near a known good solution might help. Also interactive evolution could be a very powerful technique as the user can interactively resolve some issues if the algorithm gets stuck. 16 Michalewicz & Schoenauer (1996) survey several EA based approaches for constrained parameter optimization problems. Coello (2013a) has compiled a list of more than 1,000 references on constraint-handling techniques used with EAs. Expensive Function Evaluations In industrial applications, superior solutions have been found needing a minimum number of e.g. 150 fitness function evaluations only. Two approaches, which tackle this problem, are considered next: (i) parallelization and (ii) meta-modeling. Parallel evaluation of several individuals can speed up the algorithm or even increase the probability of finding better solutions through utilizing multiple parallel populations that communicate sporadically through migrants. A discussion of these parallelization concepts goes far beyond the scope of this article, the reader is referred to Cant´ u-Paz (2001) for an elementary introduction. Alba & Tomassini (2002) investigate parallelism and EAs. Hu et al. (2010) analyze the effect of variable population size on accelerating evolution in the context of a parallel EA. Cant´ u-Paz (2007) reviews parameter settings in parallel GAs. Meta-modeling can be a very powerful tool in case the evaluation of a fitness function is too expensive. Meta-modeling is a technique that replaces an expensive mathematical model (such as FEM or CFD) or a complex physical experiment by a often crude but very quick to evaluate model. Statistical approaches such as Design of Experiments (DoE) from Taguchi type models to sophisticated Kriging are typical. Emmerich (2005) describes the development of robust algorithms for optimization with time-consuming evaluations. The main working principle of these techniques is to combine spatial interpolation techniques with EAs. Current results from these demanding real-world applications are presented during GECCO’s evolutionary computation in practice trace, see, e.g., http://www.sigevo.org/gecco-2013/ecp.html. Analyzing the Results Because the output of an EA run is stochastic, a solution the algorithm finds in one run may slightly or sometimes quite significantly differ from another run. A thorough analysis of EA results needs statistical analysis. Any critical EA analysis should contain at least box-and-whiskers plots to illustrate the statistical spread of the results as any EA run will result typically in a distribution of solutions around any (local) optimum the algorithm finds. Very helpful in industrial applications could be a look at the parameter settings of a solution. A solution close to a constraint could indicate that the optimization problem might be over-constraint or there is a potential better solution in the real-world when a constraint can be relaxed. Also the pattern of the parameter settings in the parameter space can help understanding the underlying problem structure. A random walk structure for example may indicate local plateau areas. In case solutions can be visualized through CAD it can sometimes be helpful to view the actual evolution of the solution as a video. This can help improving parameter settings (finding the 17 narrow evolutionary window, i.e., the parameter window where the EA converges best towards to better solutions) or determining realistic stopping criteria of the algorithm. It should be highlighted that robustness of the solution is often a very important criterion in industrial practice. The best solution may be contained in a very narrow set intervals that when left the solutions deteriorate quickly. Robust solution in this sense would allow some variation in the parameter settings. Any robustness analysis of a proposed solution (e.g., using ANOVA) gives extra confidence in a result that is supposed to be applied in a critical industrial application. Limitations Some EAs face limitations when it comes to budgeted fitness evaluations. The stochastic nature of EA may also be a limiting factor when it comes to safety critical applications where repeatability is important. Typically in these cases, EA are used to improve the parameter settings of deterministic algorithms. The explanation of a solution can also be difficult as the way how a solution was deduced is based on a complex stochastic search rather than on a deterministic one-step-at-a-time approach. A proof that a solution is optimal will not be provided by any current EA, not even how close a solution might be to an optimal solution. Kordon (2010) gives a lively description how to apply EAs in industry and describes several pitfalls. Filipiˇ c & Tuˇ sar (2013) present two case studies of applying optimization methodology in industry, one involving numerical optimization based on simulation models, and the other combinatorial optimization with specific constraints and objectives. They identify some of the challenges frequently met by solution providers for industrial optimization problems. Data Mining and Knowledge Discovery EAs have been successfully applied in a large variety of real-world problem areas. Given the focus of the journal, it seems sensible to briefly discuss a particular application area for EAs: Data mining and knowledge discovery. In a sense, data mining is about finding good and meaningful models and rules, and thus essentially an optimization task. So it is not surprising that EAs may be helpful also in this area. They have been proposed for a variety of data-mining related tasks, including feature selection and feature construction, instance selection, or rule extraction, Ghosh & Jain (2005) provide a number of examples. Freitas (2002a,b, 2008) presents a comprehensive introduction to data mining and EAs and introduces the term evolutionary data mining to subsume any data mining using EAs. More specific, Tan et al. (2005) present a distributed coevolutionary classifier for extracting comprehensible rules in data mining. Vladislavleva et al. (2013) forecast the energy output of wind farms using GP and report on the correlation of the different variables for the energy output. Note that GP is able to search for symbolic representations 18 that are interpretable (Vladislavleva, 2008). Schmidt & Lipson (2008) use GP techniques for automatically reverse engineering symbolic analytical models of dynamical systems directly from experimental observations. EAs have been used indirectly to tune parameters of data-mining algorithms (Lessmann et al., 2005) or replace machine learning algorithms such as clustering (Handl & Knowles, 2007). Even the automated design of new data mining algorithms has been proposed (Pappa & Freitas, 2010). Last, but not least, Schmidt & Lipson (2009) has to be mentioned. The authors apply sophisticated GP techniques for the ’identification of nontriviality’. Motion-tracking data captured from various physical systems, e.g, harmonic oscillators and chaotic double-pendula, is used to re-discover Hamiltonians, Lagrangians, and other laws of geometric and momentum conservation. Interestingly, no prior knowledge about physics, kinematics, or geometry, is used by the algorithm. Software A variety of software frameworks for GP is available: DataModeler is a software package that is developed within the context of industrial data analysis (Evolved Analytics LLC, 2010). It implements several non-linear modeling techniques such as Pareto-symbolic regression, statistical learning theory, and non-linear variable selection. The GP-based software Discipulus is applied to Data Mining as well as to problems requiring predictive Analytics and Classification (Francone, 2010). Eureqa is a software tool for detecting equations and hidden mathematical relationships in data (Dubˇ c´ akov´ a, 2011; Austrem, 2012). GPTIPS is a free genetic programming (GP) and predictive modeling toolbox for MATLAB (Searson et al., 2010). MATLAB’s Global Optimization Toolbox has genetic algorithms for single and multi objective functions (Mathworks, 2011). Implementations of the CMA-ES and links to libraries that contain such implementations can be found on the author’s web page3(Hansen et al., 1995). The Java Evolutionary Computation Toolkit (ECJ) is a freeware evolutionary computation research system written in Java. It implements several EA techniques, e.g., GAs, GP, and ES (Luke, 2013). The MOEA Framework is an open-source evolutionary computation library for Java that specializes in multi-objective optimization (Hadka, 2012). State-of-the-art software packages for parameter tuning and algorithm configuration such as Bonesa (Smit & Eiben, 2011), irace (L´ opez-Ib´ anez et al., 2011), ParamILS (Hutter et al., 2010), and SPOT (Bartz-Beielstein & Zaefferer, 2011) are freely available from the authors’ web pages. Alcal´ a-Fdez et al. (2009) develop KEEL, an open source Java software tool to assess evolutionary algorithms for data mining problems. Mikut & Reischl (2011) discuss the historical development and present a range of existing state-of-the-art data mining and related tools. They provide a list of data mining tools, which includes EA based 3https://www.lri.fr/˜hansen/cmaes_inmatlab.html 19 approaches, too. Weka and RapidMiner, which provide several machine learning algorithms for solving real-world data mining problems, contain a couple of EA-based search methods (Witten & Frank, 2005; Rapid-I, 2010). Finally, the statistical software R(R Core Team, 2005) should be mentioned. Several EAs, e.g., emoa,GA, or cmaes are available as R packages, see http://cran.r-project.org/web/ packages. Conclusion Evolutionary algorithms are established stochastic direct search algorithms. The evolutionary cycle can be seen as the common ground for EA. They are trying to reach optimal states by successive improvements. Improvements occur by variation (mutation, recombination). Several problem specific selection methods enable to cope with different situations, e.g., noisy and dynamically changing environments. Since they are population-based search algorithms, EAs are well suited to solve multi-objective optimization problems. They are also flexible tools for data-mining problems. By modifying the evolutionary cycle, new members of the EA family are generated. Bio-inspired algorithms such as particle swarm optimization (Eberhart & Kennedy, 1995) or ant colony algorithms (Dorigo, 1992) enrich the EA family with new problem specific optimization techniques. References Adenso-Diaz, B. & Laguna, M. (2006). Fine-tuning of algorithms using fractional experimental design and local search. Operations Research, 54(1), 99– 114. Alba, E. & Tomassini, M. (2002). Parallelism and evolutionary algorithms. Evolutionary Computation, IEEE Transactions on, 6(5), 443–462. Alcal´ a-Fdez, J., S´ anchez, L., Garc´ ıa, S., del Jes´ us, M. J., Ventura, S., Garrell, J., Otero, J., Romero, C., Bacardit, J., Rivas, V. M., et al. (2009). KEEL: a software tool to assess evolutionary algorithms for data mining problems. Soft Computing, 13(3), 307–318. Arnold, D. V. (2002). Noisy optimization with evolution strategies, volume 8. Kluwer Academic Pub. Arnold, D. V. & Beyer, H.-G. (2003). A comparison of evolution strategies with other direct search methods in the presence of noise. Computational Optimization and Applications, 24(1), 135–159. Auger, A. & Hansen, N. (2011). Theory of evolution strategies: a new perspective. In A. Auger & B. Doerr (Eds.), Theory of Randomized Search Heuristics: Foundations and Recent Developments chapter 10, (pp. 289–325). World Scientific Publishing. 20 Auger, A. & Hansen, N. (2013). Evolution strategies and cma-es (covariance matrix adaptation). Austrem, P. G. (2012). A comparative study of the eureqa tool for end-user development. IJISMD, 3(3), 66–87. B¨ ack, T. (1996). Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, volume 996. Oxford university press Oxford. B¨ ack, T., Kok, J. N., & Rozenberg, G. (2012). Handbook of Natural Computing. Springer. Balaprakash, P., Birattari, M., & St¨ utzle, T. (2007). Improvement strategies for the F-race algorithm: Sampling design and iterative refinement. In Hybrid Metaheuristics (pp. 108–122). Bartz-Beielstein, T., Chiarandini, M., Paquete, L., & Preuss, M., Eds. (2010a). Experimental Methods for the Analysis of Optimization Algorithms. Berlin, Heidelberg, New York: Springer. Bartz-Beielstein, T., Lasarczyk, C., & Preuß, M. (2005). Sequential parameter optimization. In B. McKay & others (Eds.), Proceedings 2005 Congress on Evolutionary Computation (CEC’05), Edinburgh, Scotland, volume 1 (pp. 773– 780). Piscataway NJ: IEEE Press. Bartz-Beielstein, T., Parsopoulos, K. E., & Vrahatis, M. N. (2004). Design and analysis of optimization algorithms using computational statistics. Applied Numerical Analysis and Computational Mathematics (ANACM), 1(2), 413–433. Bartz-Beielstein, T., Preuß, M., & Schwefel, H.-P. (2010b). Model optimization with evolutionary algorithms. In K. Lucas & P. Roosen (Eds.), Emergence, Analysis, and Evolution of Structures—Concepts and Strategies Across Disciplines (pp. 47–62). Berlin, Heidelberg, New York: Springer. Bartz-Beielstein, T. & Zaefferer, M. (2011). SPOT Package Vignette. Technical report, Cologne University of Applied Sciences. Beume, N., Naujoks, B., & Emmerich, M. (2007). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669. Beyer, H.-G. (2001). The Theory of Evolution Strategies. Berlin, Heidelberg, New York: Springer. Beyer, H.-G., Brucherseifer, E., Jakob, W., Pohlheim, H., Sendhoff, B., & To, T. B. (2002). Evolutionary algorithms—terms and definitions. http://ls11www.cs.uni-dortmund.de/people/beyer/EA-glossary/def-engl-html.html. Beyer, H.-G. & Schwefel, H.-P. (2002). Evolution strategies: A comprehensive introduction. Natural Computing, 1(1), 3–52. 21 Birattari, M., St¨ utzle, T., Paquete, L., & Varrentrapp, K. (2002). A racing algorithm for configuring metaheuristics. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’02 (pp. 11–18). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. Branke, J. (2008). Consideration of user preferences in evolutionary multiobjective optimization. In J. Branke, K. Deb, K. Miettinen, & R. Slowinski (Eds.), Multiobjective Optimization - Interactive and Evolutionary Approaches, volume 5252 of LNCS (pp. 157–178). Springer. Branke, J., Greco, S., Słowi´ nski, R., & Zielniewicz, P. (2009). Interactive evolutionary multiobjective optimization using robust ordinal regression. In M. Ehrgott & others (Eds.), International Conference on Evolutionary MultiCriterion Optimization, volume 5467 of LNCS (pp. 554–568).: Springer. Branke, J., Kaußler, T., & Schmeck, H. (2001). Guidance in evolutionary multiobjective optimization. Advances in Engineering Software, 32, 499–507. Brownlee, J. (2011). Clever algorithms: nature–inspired programming recipes. Lulu Enterprises. Cant´ u-Paz, E. (2001). Migration policies, selection pressure, and parallel evolutionary algorithms. Journal of Heuristics, 7(4), 311–334. Cant´ u-Paz, E. (2007). Parameter setting in parallel genetic algorithms. In Parameter Setting in Evolutionary Algorithms (pp. 259–276). Springer. Coello, C. A. C. (2013a). List of references on constraint-handling techniques used with evolutionary algorithms. http://www.cs.cinvestav.mx/ constraint/. Coello, C. A. C., Lamont, G. B., & Veldhuizen, D. A. V. (2006). Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation). Secaucus, NJ, USA: Springer-Verlag New York, Inc. Coello, C. C. (2013b). Emoo web page. http://delta.cs.cinvestav. mx/˜ccoello/EMOO/. De Jong, K. A. (2006). Evolutionary computation: a unified approach, volume 262041944. MIT press Cambridge. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA–II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197. Deb, K. & Srinivasan, A. (2006). Innovization: Innovating design principles through optimization. In M. Keijzer & others (Eds.), Proceedings of the 8th annual conference on Genetic and evolutionary computation (pp. 1629–1636).: ACM. Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy. 22 Downey, R. G. & Fellows, M. R. (1999). Parameterized Complexity. SpringerVerlag. Dubˇ c´ akov´ a, R. (2011). Eureqa: software review. Genetic Programming and Evolvable Machines, 12(2), 173–178. Eberhart, R. & Kennedy, J. (1995). A new optimizer using particle swarm theory. In Proceedings Sixth International Symposium on Micro Machine and Human Science (Nagoya, Japan) (pp. 39–43). Piscataway NJ: IEEE Service Center. Eiben, A., Hinterding, R., & Michalewicz, Z. (1999). Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 3(2), 124–141. Eiben, A. & Smit, S. (2011). Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evolutionary Computation, 1(1), 19 – 31. Eiben, A. E. & Schoenauer, M. (2002). Evolutionary computing. Information Processing Letters, 82(1), 1–6. Eiben, A. E. & Smith, J. E. (2003). Introduction to Evolutionary Computing. Berlin, Heidelberg: Springer. Emmerich, M. (2005). Singleand Multi-objective Evolutionary Design Optimization: Assisted by Gaussian Random Field Metamodels. PhD thesis, Universit¨ at Dortmund, Germany. Evolved Analytics LLC (2010). DataModeler Release 8.0. Evolved Analytics LLC. Filipiˇ c, B. & Tuˇ sar, T. (2013). Challenges of applying optimization methodology in industry. In Proceeding of the fifteenth annual conference companion on Genetic and evolutionary computation conference companion, GECCO ’13 Companion (pp. 1103–1104). New York, NY, USA: ACM. Fogel, D. B. & Chellapilla, K. (1998). Revisiting evolutionary programming. In Aerospace/Defense Sensing and Controls (pp. 2–11).: International Society for Optics and Photonics. Fogel, L. J. (1999). Intelligence through simulated evolution: forty years of evolutionary programming. John Wiley & Sons, Inc. Fogel, L. J., Owens, A. J., & Walsh, M. J. (1965). Artificial intelligence through a simulation of evolution. In A. Callahan, M. Maxfield, & L. J. Fogel (Eds.), Biophysics and Cybernetic Systems. Washington DC: Spartan Books. Fonseca, C. M. & Fleming, P. J. (1998). Multiobjective optimization and multiple constraint handling with evolutionary algorithms - part I: A unified fomulation. IEEE Transactions on Systems, Man, and Cybernetics - Part A, 28(1), 26–37. 23 Francone, F. D. (2010). Discipulus—Owner’s Manual. Register Machine Learning Technologies, Inc. Freitas, A. A. (2002a). Data mining and knowledge discovery with evolutionary algorithms. Springer. Freitas, A. A. (2002b). A survey of evolutionary algorithms for data mining and knowledge discovery. In In: A. Ghosh, and S. Tsutsui (Eds.) Advances in Evolutionary Computation: Springer-Verlag. Freitas, A. A. (2008). A review of evolutionary algorithms for data mining. In Soft Computing for Knowledge Discovery and Data Mining (pp. 79–111). Springer. Ghosh, A. & Jain, L. C., Eds. (2005). Evolutionary Computation in Data Mining. Springer. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Reading MA: Addison-Wesley. Goldberg, D. E. (1990). Real-coded genetic algorithms, virtual alphabets, and blocking. Urbana, 51, 61801. Hadka, D. (2012). MOEA Framework—A Free and Open Source Java Framework for Multiobjective Optimization. Handl, J. & Knowles, J. (2007). An evolutionary approach to multiobjective clustering. IEEE Transactions, 11(1), 56–76. Hansen, N. & Ostermeier, A. (1996). Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Evolutionary Computation, 1996., Proceedings of IEEE International Conference on (pp. 312–317).: IEEE. Hansen, N., Ostermeier, A., & Gawelczyk, A. (1995). On the adaptation of arbitrary normal mutation distributions in evolution strategies: The generating set adaptation. In ICGA (pp. 57–64). Herrera, F., Lozano, M., & Verdegay, J. L. (1998). Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artif. Intell. Rev., 12(4), 265–319. Holland, J. H. (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal of Computing, 2(2), 88–105. Hu, T., Harding, S., & Banzhaf, W. (2010). Variable population size and evolution acceleration: a case study with a parallel evolutionary algorithm. Genetic Programming and Evolvable Machines, 11(2), 205–225. Huang, D., Allen, T. T., Notz, W. I., & Zeng, N. (2006). Global optimization of stochastic black-box systems via sequential kriging meta-models. Journal of Global Optimization, 34(3), 441–466. 24