Evolutionary Optimization Algorithms:
Biologically-Inspired and Population-Based Approaches
to Computer Intelligence
Dan Simon, Professor
Cleveland State
Department of Electrical and Computer Engineering
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. My
email address is available on my home page at http://academic.csuohio.edu/simond,
and I enthusiastically welcome feedback, comments, suggestions for
improvements, and corrections. The book also contains algorithmic, high-level pseudocode 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.
1. Introduction
2. Optimization
3. Genetic Algorithms
4. Mathematical Models of
Genetic Algorithms
5. Evolutionary Programming
6. Evolution Strategies
7. Genetic Programming
8. Variations on Evolutionary Algorithms
9. Simulated Annealing
10. Ant Colony Optimization
11. Particle Swarm
Optimization
12. Differential Evolution
13. Estimation of
Distribution Algorithms
14. Biogeography-Based
Optimization
15. Cultural Algorithms
16. Opposition-Based Learning
17. Other Evolutionary Algorithms
18. Combinatorial Optimization
19. Constrained Optimization
20. Multi-Objective
Optimization
21. Expensive, Noisy, and Dynamic Fitness Functions
A. Some Practical Advice
B. The No Free Lunch Theorem
and Performance Testing
C. Benchmark Optimization Functions
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 psuedo-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.
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.
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
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
Benchmarks u01.m through u10.m are from the CEC 2009 competition
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
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
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
There is no software for this chapter
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
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)
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)
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)
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
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
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)
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)
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)
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)
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)
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)
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
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)
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)
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.
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)
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)
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)
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
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)
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)
Department of Electrical and
Computer Engineering
Last Update March 24, 2015