Evolutionary Optimization Algorithms:
Biologically-Inspired and Population-Based Approaches to Computer Intelligence
Dan Simon, Professor
Cleveland State
Department of Electrical and Computer Engineering
本教科書針對大學部高年級、碩士生以及工程師，實用而縝密地介紹如何應用evolutionary algorithms (EAs) 做最佳化法。
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.
本書包括：
103 worked examples和262 end-of-chapter problems.
解答(出版社提供給授課講師)A solution manual will be available to course instructors from from the publisher.
可下載本書範例的Matlab程式碼(詳下)。
超過700篇涵蓋歷史經典經典到新發表的參考文獻
Overview
一本perspective適合教學且教材資源豐富的書。 In particular, I hope that this book will offer the following.
· 直觀， bottom-up approach，協助讀者對 EAs建立清晰而具縝密理論基礎的認識。本書藉由呈現easy-to-implement algorithms和探討rigorous theory 間取得平衡，兼顧理論和實務。
· 簡單範例提供讀者對EA的數理、公式和理論直覺式的瞭解，並讓學生直接了解理論如何應用於實務。
· 本書可下載範例的MATLAB程式碼。(Note that the examples and the MATLAB code are not intended as efficient 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.)
· 最新發表/發展的EAs 理論，包括 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等。提供讀者對EAs更完整的認識及具良好的定位，以便能進行新的研究。
· 有些EAs的書也具以上特色，但據我所知唯有本書包含以上所有。
Summary Table of Contents
Part I: An Introduction to Evolutionary Optimization
1. Introduction
2. Optimization
Part II: Classic Evolutionary Algorithms
3. Genetic Algorithms
4. Mathematical Models of Genetic Algorithms
5. Evolutionary Programming
6. Evolution Strategies
7. Genetic Programming
8. Variations on Evolutionary Algorithms
Part III: More Recent 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
Part IV: Special Types of Optimization Problems
18. Combinatorial Optimization
19. Constrained Optimization
20. Multi-Objective Optimization
21. Expensive, Noisy, and Dynamic Fitness Functions
Matlab Code
All of the routines are described below and are available in hyperlinked ZIP files.
Common Matlab Routines
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
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
Chapter-by-Chapter Matlab Code
Chapter 1: Introduction
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)
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 nfor 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)
[From]http://academic.csuohio.edu/simond/EvolutionaryOptimization/
