Evolutionary Optimization Algorithms:

Biologically-Inspired and Population-Based Approaches
to Computer Intelligence

Dan Simon, Professor

Cleveland State

Department of Electrical and Computer Engineering

*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 now in academia. I've also taught graduate-level
courses on EAs. I like step-by-step explanations, so that is 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 established principles and cutting-edge results. The book includes
103 worked examples and 262 end-of-chapter problems. A solution manual is
available to course instructors from http://www.wiley.com/go/optimization
. 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 within the last few months.

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