Dan Simon, PhD

Evolutionary Optimization Algorithms: Biologically-Inspired and Population-Based Approaches to Computer Intelligence, John Wiley & Sons, 2013

This textbook is intended for the advanced undergraduate student, the beginning graduate student, or the practicing engineer who wants a practical but rigorous introduction to the use of evolutionary algorithms (EAs) for optimization. I’ve been working and publishing in the area of EAs since the early 1990s, originally in industry and also in academia. I’ve also taught graduate-level courses on EAs. I like step-by-step explanations, so that’s how I wrote the book. I tried to make it clear and simple for the beginning EA student, but I also included recent research results, so I think that the book has a nice balance of foundational principles and cutting-edge results. The book includes 103 worked examples and 262 end-of-chapter problems. Matlab code for the examples in the book is available for download from this web site. The book is well-documented with over 700 references, ranging from historical references from hundreds of years ago, to papers published in the 2010s.

Overview

There are already many fine books on EAs, which raises the question: Why yet another textbook on this topic? After teaching an EA course for many years and reading many books on the subject, I thought that I would be able to write a book that better met the needs of my students, and that also might better meet the needs of others. The reason I wrote this book is to offer a pedagogical approach, perspective, and material that is not available in any other single book. In particular, I hope that this book will offer the following.

1. A straightforward, bottom-up approach that assists the reader in obtaining a clear but theoretically rigorous understanding of EAs. Some books discuss a variety of EAs as cookbook algorithms without any theoretical support or detailed explanations. Other books read more like research monographs than textbooks, and are not very accessible to the average engineer. This book tries to strike a balance by presenting easy-to-implement algorithms along with some rigorous theory, and lots of discussion about tuning parameters, implementation issues, and trade-offs.
2. Simple examples that provide the reader with an intuitive understanding of EA math, software, equations, and theory. Some EA books present examples or problems that are not amenable to an intuitive understanding. However, it is possible to present simple examples and problems that require only paper and pencil to solve. These simple examples and problems allow the student to more directly see how the theory works out in practice, and more importantly, why it works.
3. MATLAB source code for all of the examples in the book are available on this web page. A number of other books supply source code, but it is often incomplete or outdated, which is frustrating for the reader. The book also contains algorithmic, high-level pseudo-code listings that are more permanent than any specific software listings. Note that the examples and the Matlab code are not intended to provide efficient, production-quality, or competitive optimization algorithms; they are instead intended to allow the reader to gain a basic understanding of underlying EA concepts. Any serious research or application should rely on the sample code only as a preliminary starting point.
4. Theory and recently-developed EAs that are not available in most other books. These topics include Markov models of EAs, dynamic system models of EAs, artificial bee colony algorithms, biogeography-based optimization, opposition-based learning, artificial fish swarm algorithms, shuffled frog leaping, bacterial foraging optimization, and many others. These topics are recent additions to the state of the art, and their coverage in this book is not matched in any other books. However, this book is not intended to survey the state-of-the-art in any particular area of EA research; that would be impossible, in view of the breadth and depth of current EA research. This book is instead intended to provide a high-level overview of many areas of EA research so that the reader can gain a broad understanding of EAs, and so that the reader can be well-positioned to pursue additional, in-depth  studies in the state-of-the-art.

There are other books on EAs that offer some of the above features, but no other books of which I am aware offer all of these features.

Summary Table of Contents

Errata

A list of typos and errors in the book is available here.

Solution manual

A solution manual is available for course instructors from the publisher at http://www.wiley.com/go/optimization.

Matlab Code

Here are some caveats about the Matlab code.

1. I am aware that the code is not as efficient as it could be. This is due to two reasons. First, I am not a software engineer, and so my coding is less than perfect. Second, I intentionally sacrifice efficiency for the sake of readability. My goal in writing this software is education, not efficiency. (If I were looking for efficiency I would have written the code in C.)
2. I will not be able to explain the code to you in an email. In order for this code to be useful to you, you really need to be proficient in Matlab programming. So please do not email me with requests to help you modify the code for your research problem. The best way to learn how to use and modify the code is to compare it with the pseudo-code in the book, step through the code one line at a time, inspect the variables one at a time, and study the results so that you understand exactly what each line is doing, and why. If you are able to get to that point with this software, then you will be able to easily modify it for your own particular optimization problem and algorithmic variations. Also, I hope that the many comments in the code will be helpful.

I will be glad to hear from you if you find a bug in the code. Just like a paper always has one more typo, a computer program always has one more bug. So I will appreciate it if you tell me about any bugs that you find.

The examples in the book can be reproduced by running the code that is available here. Here is what you need to do.

1. The first thing to do is to download the benchmarks and other generic routines under the “Common Matlab Routines” heading below. These routines include common code that is called by many different optimization algorithms. This common code is re-used by many algorithms and so it is available in separate routines for the sake of efficiency. On my computer, I put all of this common code in separate directories on my computer and add those directories to my Matlab path.
2. After you download the benchmarks and the common code, you can download and run the code for whatever chapter you want, which is available under the “Chapter-by-Chapter Matlab Code” heading below.

All of the Matlab routines are described below and are available in hyperlinked ZIP files.

Common Matlab Routines

Benchmark Functions

Given an independent vector variable, these routines return the cost function value.

• Ackley.m – Ackley benchmark function
• AckleyDisc.m – Discretized Ackley benchmark function
• Fletcher.m – Fletcher benchmark function
• FourPeaks.m – Four peaks benchmark function
• Griewank.m – Griewank benchmark function
• Pairs.m – Pairs benchmark function
• Penalty1.m – Penalty #1 benchmark function
• Penalty2.m – Penalty #2 benchmark function
• Quartic.m – Quartic benchmark function
• Rastrigin.m – Rastrigin benchmark function
• Rosenbrock.m – Rosenbrock benchmark function
• Schwefel12.m – Schwefel 1.2 benchmark function
• Schwefel221.m – Schwefel 2.21 benchmark function
• Schwefel222.m – Schwefel 2.22 benchmark function
• Schwefel226.m – Schwefel 2.26 benchmark function
• Sphere.m – Sphere benchmark function
• Step.m – Step benchmark function

Constrained Benchmark Functions

• Benchmarks g01.m through g24.m are from the CEC 2006 competition
• Benchmarks c01.m through c18.m are from the CEC 2010 competition
• Readme.txt provides the references for the benchmarks

Multi-objective Benchmark Functions

• Benchmarks u01.m through u10.m are from the CEC 2009 competition

Other Common Functions

• ClearDups.m – Replaces duplicate individuals in the population with randomly-generated individuals
• ComputeCostAndConstrViol.m – Computes the cost and the constraint violation level of each indivdiual
• ComputeRandomShift.m – Computes a random shift for a benchmark function (see Appendix C.7.1)
• Conclude.m – Displays data about the population and plots results
• createRotMatrix.m – Creates a random rotation matrix for a benchmark function (see Appendix C.7.2)
• Init.m – Initializes the population and common EA tuning parameters
• PopSort.m – Sorts the population from best to worst
• ResetPlotOptions.m – Resets Matlab plot options to default values
• SetPlotOptions.m – Sets Matlab plot options to values that give nice-looking plots

Traveling Salesman Benchmarks

These files, along with many others, are available at the TSPLIB web site.

• *.tsp and *.opt.tour – Note that * is the name of the problem:
• ulysses16 (a 16-city problem)
• ulysses22 (a 22-city problem)
• pr76 (a 76-city problem)
• berlin52 (a 52-city problem)
• *.tsp file is a text file that defines the problem
• *.opt.tour is a text file that specifies the globally optimal solution

Common Functions for TSPs

• CalcDistance.m – Calculate the distance of a TSP tour
• ConcludeTSP.m – Display data about a TSP population and plot results
• CreateDistanceArray.m – Calculate the array of distances between each pair of cities in a TSP
• GetCoordinates.m – Retrieve latitude and longitude from a .TSP file
• GetLongLat.m – Convert .TSP-format data to latitude and longitude
• MutateTSP.m – Mutate a closed TSP tour using one of several possible mutation methods
• PlotBestTour.m – Plot the best TSP tour from a *.opt.tour file
• PlotTour.m – Plot a TSP tour
• PopSortTSP.m – Sort TSP individuals from best to worst
• ReplaceDupsTSP.m – Replace duplicate individuals in a TSP population

Chapter-by-Chapter Matlab Code

Chapter 1: Introduction

There is no software for this chapter

Chapter 2: Optimization

• AdaptiveHillClimbing.m – Adaptive hill climbing
• NextHillClimbing.m – Next ascent hill climbing
• RandomHillClimbing.m – Random mutation hill climbing
• SteepestHillClimbing.m – Steepest ascent hill climbing
• MonteHill.m – Monte Carlo simulation software to obtain the results in Example 2.7

Chapter 3: Genetic Algorithms

• GA.m – Genetic algorithm for discrete or continuous optimization (Example 3.3)
• PlotContour.m – Plots individuals on top of the Ackley contour plot (called from GA.m)
• AckleyContour.m – Create a contour plot of the two-dimensional Ackley function (called from PlotContour.m)
• GAContVsDisc.m – Compare a continuous GA with a discrete GA (Example 3.4)

Chapter 4: Mathematical Models of Genetic Algorithms

• GAMarkovTheory.m – Uses a Markov model to calculate probabilities of GA population distributions (Example 4.9 and 4.10)
• GAMarkovSim.m – Simulates a simple GA and plots the proportion of various population distributions (Example 4.9 and 4.10)
• EnumPops.m – Recursively generate a list of all possible EA populations (called by GAMarkovSim.m and GAMarkovTheory.m)
• GADyn1.m – Uses a dynamic system model to calculate the proportion of each individual in a selection-only GA (Example 4.11)
• GADyn2.m – Uses a dynamic system model and a simulation to calculate the proportion of each individual in a GA with only selection and mutation (no crossover) (Example 4.12)
• GADynEx3.m – Uses a dynamic system model to calculate the percentage of GA population distributions (Example 4.14)

Chapter 5: Evolutionary Programming

• EP.m – Evolutionary programming for continuous optimization
• EPMonte.m – Comparision of EP with and without adaptation of mutation variance (Example 5.1)
• FSMPrediction.m – EP to optimize a finite state machine to output a desired bit pattern (Example 5.2)
• PrimePrediction.m – EP to optimize a finite state machine to predict prime numbers (Example 5.3)
• PrimePredictionMonte.m – Monte Carlo simulation of PrimePrediction.m (Example 5.3)
• Prisoner.m – EP to optimize a finite state machine for the prisoner’s dilemma problem (Example 5.4)
• SanteFe32.m – EP to optimize a finite state machine for the 32 x 32 Sante Fe trail (Section 5.5)
• SanteFe32Monte.m – Monte Carlo simulation of SanteFe32.m (Section 5.5)

Chapter 6: Evolution Strategies

• ES.m – Evolution strategy for continuous optimization (Example 6.1 and 6.3)
• MonteES1plus1.m – Compare an ES with standard deviation adaptation and an ES without it (Example 6.1)
• MonteESmulambda.m – Compare a (mu+lambda)-ES with a (mu,lambda)-ES (Example 6.2)
• MonteESmulambdaAdapt.m – Compare an ES with mutation rate adaptation and an ES without it (Example 6.3 and 6.4)
• MonteESmulambdaAdaptAll.m – Save Matlab figure files from MonteESmulambdaAdapt.m for all benchmarks

Chapter 7: Genetic Programming

• test1.lisp – A simple Lisp program to see how Lisp works
• test1Instructions.txt – Instructions for running test1.lisp
• test2.lisp – Another simple Lisp program to see how Lisp works
• test2Instructions.txt – Instructions for running test2.lisp
• GPCartControl.lisp – Genetic programming routine for the minimum-time control problem (Section 7.3)
• *.lisp – Various auxiliary Lisp routines that are called by GPCartControl.lisp
• PhasePlane.lisp – Creates a file of controls as a function of position and velocity for a given switching strategy
• EvalCartControl.lisp – Evaluate the cost of a given switching strategy
• PhasePlane.m – Generate the theoretically optimal switching curve and sample trajectory (Figures 7.10 and 7.11)
• PlotPhasePlane.m – Plot the phase plane based on input files that were created with PhasePlane.lisp
• AddNodes.m – An implementation of recursive syntax tree generation (Figures 7.6 and 7.7)
• Readme.txt – Instruction file

Chapter 8: Evolutionary Algorithm Variations

• EPMonteDirectedInit.m – Directed initialization in an evolutionary program (Example 8.1)
• SuddenJump.m – An example of a sudden jump in an EA cost function (Figure 8.2)
• GrayLandscape.m – Show the difference between a binary-code and gray-code landscape (Example 8.2)
• MonteEAVarGA.m – Explore the effect of binary-coding vs. gray-coding in a GA (Examples 8.3 and 8.5). The Matlab command “MonteEAVarGA(@AckleyDisc)” reproduces the results of Example 8.3, and “MonteEAVarGA(@WorstCaseProblem)” reproduces the results of Example 8.5.
• EAVarGA.m – Genetic algorithm for Examples 8.3 and 8.5
• WorstCaseProblem.m – Cost function file for the worst-case problem of Example 8.5
• MonteGAElite.m – Explore the effect of elitism on a GA (Example 8.6)
• MonteStudGA.m, GAStud.m – Explore the effect of stud selection on a GA (Example 8.11)

Chapter 9: Simulated Annealing

• SACooling.m – Generate the cooling schedule plots of Figures 9.3, 9.4, 9.6, and 9.7
• SA.m – Simulated annealing for continuous optimization
• SAMonteBeta.m – Monte Carlo simulation of SA.m (Example 9.1)
• CauchyGaussian.m – Generate the Cauchy and Gaussian PDFs of Figure 9.8
• AckleyScaledPlot.m – Generate the scaled Ackley plot of Figure 9.9
• SADimension.m – Modified version of SA.m to use different cooling schedules for different dimensions
• AckleyScaled.m – Initialization and cost functions the scaled Ackley benchmark function (Example 9.2)
• SAMonteBetaDim.m – Monte Carlo simulation of SADimension.m (Example 9.2)

Chapter 10: Ant Colony Optimization

• ACOInitial.m – Generate the ant simulation plot of Figure 10.5
• AS.m – Ant system code for TSP optimization (Example 10.1)
• ASCont.m – Ant system code for continuous optimization
• ASContMonte.m – Monte Carlo ant system simulation to explore the effect of the number of pheromone bins (Example 10.2)
• ASContNumBestMonte.m – Monte Carlo ant system simulation to explore the effect of the number of pheromone contributors (Example 10.3)
• ASContMonte1.m – Monte Carlo ant system simulation to explore the effect of the local pheromone decay constant (Example 10.4)
• ASContMonte2.m – Monte Carlo ant system simulation to explore the effect of the exploration constant (Example 10.5)

Chapter 11: Particle Swarm Optimization

• DeltaPlot.m – Generate the discriminant plot of Figure 11.3
• ConstrictionLambda.m – Generate the eigenvalue plots of Figures 11.4 and 11.5
• PSO.m – Particle swarm optimization for continuous functions (Example 11.1)
• PSOMonte.m – Monte Carlo simulation of PSO (Example 11.1)
• PSOFully.m – Fully informed particle swarm optimization (Example 11.2)
• PSOFullyMonte.m – Monte Carlo simulation of fuzzy informed PSO (Example 11.2)
• NPSO.m – Negative reinforcment PSO (Example 11.3)
• NPSOMonte.m – Monte Carlo simulation of negative reinforcement PSO (Example 11.3)

Chapter 12: Differential Evolution

• DE.m – Differential evolution
• DEMonteLbin.m – Compare the “/L” and the “/bin” versions of DE (Example 12.1)
• DEMonteBase.m – Compare DE using different base vectors (Example 12.2)
• DEMonteDiff.m – Compare DE using one or two difference vectors (Example 12.2)
• DEMonteF.m – Compare DE using dithered, jittered, or constant F (Example 12.3)

Chapter 13: Estimation of Distribution Algorithms

• UMDABinary.m – Simulation of the binary univariate marginal distribution algorithm
• MonteUMDABinary.m – Monte Carlo simulation of UMDABinary.m (Example 13.1)
• cGABinary.m – Simulation of the binary compact genetic algorithm
• MonteCGABinaryAlpha.m – Monte Carlo simulation of cGABinary.m with various values of alpha (Example 13.2)
• MonteCGABinaryPopSize.m – Monte Carlo simulation of cGABinary.m with various values for population size (Example 13.3)
• Kullback.m – Calculation and optimization of mutual information (Examples 13.5 and 13.6)
• MIMICBinary.m – Simulation of binary MIMIC and COMIT algorithms
• MonteCOMITBinary.m – Monte Carlo simulation of MIMICBinary.m (Example 13.7)
• MonteCOMIT_MIMICBinary.m – Monte Carlo simulation of MIMICBinary.m (Example 13.7)
• EDAContEx1.m – Generate the PDF plot of Figure 13.18
• PBILCont1.m – Generate the PDF plots of Figure 13.20
• PBIL.m – Simulation of PBIL algorithm
• PBILEta.m – Monte Carlo simulation of PBIL.m with various learning rates (Example 13.10)
• PBILUpdateCount.m – Monte Carlo simulation of PBIL.m with various values of Nbest and Nworst (Example 13.10)
• PBILSigma.m – Monte Carlo simulation of PBIL.m with various values of k0 and kf (Example 13.10)

Chapter 14: Biogeography-Based Optimization

• BioSim.m – Calculate species count probabilities (Example 14.1)
• SinusoidMigration.m – Generate the migration curves of Figure 14.5
• BBO.m – Simulation of the biogeography-based optimization algorithm
• MonteBBOSinusoidVsLinear.m – Monte Carlo simulation of BBO.m with linear and sinusoidal migration (Example 14.3)
• MonteBBOBlendedVsStandard.m – Monte Carlo simulation of BBO.m with and without blended migration (Example 14.4)
• InitialImmigration.m – Generate the immigration curve of Figure 14.10

Chapter 15: Cultural Algorithms

• CAEPMutate1.m – Generate the PDFs of Figure 15.2
• CAEP.m – Simulation of a cultural algorithm with evolutionary programming (Example 15.2)
• CAEPMonte.m – Monte Carlo simulation of CAEP.m with and without a belief space (Example 15.2)
• SampleACMGrid.m – Generate a random sample grid for the adaptive cultural model (Figure 15.5)
• CATSP.m – Simulation of an adaptive cultural model to solve the traveling salesman problem (Example 15.3)
• PlotCATSPNumBest.m – Generate the plot of Figure 15.10 (Example 15.3)

Chapter 16: Opposition-Based Learning

• OBBO.m – Oppositional biogeography-based optimization for optimizing a continuous function
• MonteOBBOJumpRate.m – Monte Carlo simulation of OBBO.m with various jump rates (Examples 16.2 and 16.3)
• OBLTSP.m – Oppositional biogeography-based optimization for optimizing the traveling salesman problem
• MonteOBLTSP.m – Monte Carlo simulation of OBLTSP.m with various jump rates and jumping ratios (Example 16.5)

Chapter 17: Other Evolutionary Algorithms

• GSO.m – Group search optimizer algorithm for optimizing a continuous function (Section 17.3)
• MonteGSO.m – Monte Carlo simulation of GSO.m on various benchmarks
• Results from this software are not in the book. This software was contributed to this web page by Steve Szatmary.

Chapter 18: Combinatorial Optimization

• TSP.m – Simulation of combinatorial evolutionary optimization to solve traveling salesman problems
• TSPMonte.m – Monte Carlo simulation of TSP.m with various crossover, mutation, and initialization methods (Example 18.1)

Chapter 19: Constrained Optimization

• InteriorExample.m – Generate Figure 19.1
• BBO.m – Constrained biogeography-based optimization (same routine as in Chapter 14)
• MonteBBOConstrained.m – Monte Carlo simulation of BBO.m (Section 19.6)

Chapter 20: Multi Objective Optimization

• Pareto1.m – Generate the Pareto set and Pareto front for a multi-objective problem (Example 20.2)
• Pareto2.m – Use the aggregation method to generate the Pareto set and Pareto front for a multi-objective problem (Example 20.5)
• Pareto3.m – Use a brute force search, along with the aggregation method, to generate the Pareto set and Pareto front (Example 20.6)
• MultiBBO.m – Multi-objective biogeography-based optimization
• MonteMOEA.m – Monte Carlo simulation of MultiBBO.m with various multi-objective strategies and for various benchmarks (Section 20.5.5 and Table 20.1)

Chapter 21: Expensive, Noisy, and Dynamic Fitness Functions

• DACE.m – Use the design of computer experiments (DACE) algorithm to approximate the two-dimensional Branin or Goldstein-Price function (Examples 21.1 , 21.2, and 21.3)
• Overfitting.m – Generate Figure 21.14
• BBODynamic.m – Biogeography-based optimization for optimizing a time-varying function
• BBODynamicMonte1.m – Monte Carlo simulation of BBODynamic.m (Example 21.4)
• BBODynamicMonte2.m – Monte Carlo simulation of BBODynamic.m with various types of dynamic function changes and various dynamic adaptation strategies (Examples 21.5 and 21.6)
• DynamicAckley.m – Dynamic Ackley benchmark function (Examples 21.4, 21.5, 21.6)
• DynamicSphere.m – Dynamic Sphere benchmark function (not used in any examples)
• GaussianNoise.m – Generate Figure 21.23
• Resample.m – Generate Figure 21.24

Appendix A: Some Practical Advice

• There is no software for this appendix

Appendix B: The No Free Lunch Theorem and Performance Testing

• Irregular.m – Generate a random function (Figure B.1) or a deceptive function (Figure B.2)
• IrregularTest.m – Generate a random function (Example 2.1) or a deceptive function (Example 2.2) and see how long it takes, on average, for hill descending, random search, and hill ascending algorithms to find the minimum
• BoxPlotExample.m – Generate the box plot of Figure B.4 (requires the Statistics Toolbox)
• TTest.m – T test example (Example 2.5)
• FTest.m – F test example (Example 2.6)

Appendix C: Benchmark Optimization Functions

• SpherePlot.m – Plot the two-dimensional sphere function (Figure C.1)
• AckleyPlot.m – Plot the two-dimensional Ackley function (Figure C.2)
• AckleyTestPlot.m – Plot the two-dimensional Ackley Test function (Figure C.3)
• RosenbrockPlot.m – Plot the two-dimensional Rosenbrock function (Figure C.4)
• FletcherPlot.m – Plot the two-dimensional Fletcher function (Figure C.5)
• GriewankPlot.m – Plot the two-dimensional Griewank function (Figure C.6)
• Penalty1Plot.m – Plot the two-dimensional Penalty 1 function (Figure C.7)
• Penalty2Plot.m – Plot the two-dimensional Penalty 2 function (Figure C.8)
• QuarticPlot.m – Plot the two-dimensional Quartic function (Figure C.9)
• TenthPlot.m – Plot the two-dimensional Tenth Power function (Figure C.10)
• RastriginPlot.m – Plot the two-dimensional Rastrigin function (Figure C.11)
• Schwefel12Plot.m – Plot the two-dimensional Schwefel Double Sum function (Figure C.12)
• Schwefel221Plot.m – Plot the two-dimensional Schwefel Max function (Figure C.13)
• Schwefel222Plot.m – Plot the two-dimensional Schwefel Absolute function (Figure C.14)
• Schwefel226Plot.m – Plot the two-dimensional Schwefel Sine function (Figure C.15)
• StepPlot.m – Plot the two-dimensional Step function (Figure C.16)
• AbsPlot.m – Plot the two-dimensional Absolute function (Figure C.17)
• ShekelPlot.m – Plot the two-dimensional Shekel Foxhole function (Figure C.18)
• MichalewiczPlot.m – Plot the two-dimensional Michalewicz function (Figure C.19)
• SineEnvPlot.m – Plot the two-dimensional Sine Envelope function (Figure C.20)
• EggholderPlot.m – Plot the two-dimensional Eggholder function (Figure C.21)
• WeierstrassPlot.m – Plot the two-dimensional Weierstrass function (Figure C.22)
• SphereShiftedPlot.m – Plot the shifted Sphere function (Figure C.26)
• Schwefel221RotatedPlot.m – Plot the rotated Schwefel Max function (Figure C.28)