The Steady State Genetic Algorithm and The Evolution Strategy Comparison

Hello, Friends!!


I read something about Generation Gap, Overlapping Populations and Steady State Genetic Algorithm (SSGA), so, I decided to implement those stuffs and try some comparison between them and the Evolution Strategy.

Here we have the configurations of the SSGA and the Evolution Strategy (ES):


Steady State Genetic Algorithm (SSGA):

String Length: 25 bits
Parents Population: 100
Generation Gap: 70
Crossover Probability: 0.7
Mutation Probability: 0.03
Elitism: Highly Elitist
Number of Generations: 3000

NOTE: The Generation Gap above means that only 70 parents can reproduce, that is, they generate 70 offspring and, after the reproduction, both parents population and offspring population compete for survival, i.e., we have a post-selection in wich from the temporary population parents+offspring we select the best 100 individuals to compose the next generation.


Evolution Strategy (ES):

Type of ES: (mu + lambda)-ES
Number of Parents(mu): 15
Number of Offspring(lamdba): 35
Mutation: O.k
Crossover: O.k
Number of Generations: 30; 45; 1000



1-First Function: Schwefel Function

F1 = sum(-x(i)·sin(sqrt(abs(x(i))))), i=1:2
x(1) = [-500:500]
x(2) = [-500:500]
Global Minimum: 837.9658; x(i)=420.9687, i=1:2

Here we can see an image of Schwefel's Function:




This function is deceptive and the search for the global minimum can drive the search to a wrong direction.


Below there is a contour map of the Schwefel Function.





SSGA

Best Initial Values
x1 = 404.66612293321259
x2 = -274.55141468499346
F(x1,x2) = -594.4647574012356

Best Final Values (after 3000 Generations)
x1 = 420.96873882319744
x2 = 420.96903684643019
F(x1,x2) = -837.96577453421264
Simulation Time = 83.61 s

Evolution Strategy

Best Initial Values
x1 = -339.01782978280346
x2 = 405.52768712189408
F(x1,x2) = -532.95484456153542

Best Final Values (after 30 Generations)
x1 = 420.96873130520726
x2 = 420.96870632616128
F(x1,x2) = -837.96577454463647
Simulation Time = 0.04 s

Here we have a performance comparison of the best fitness versus generation (the Blue Line is the Evolution Strategy and the Red Line is the Steagy State Genetic Algorithm):


As we can see, both SSGA and the ES could achieve the global minimum and, althoug the SSGA seems, at a first glance, have spent much more time than the ES, in the graph above we note that the SSGA got a solution very close to that achivied by the ES, and for this the SSGA did not spent so much generations.

2-Second Function: Schaffer Function

Number of Variables: 2
Number of optima: 1
Variables' Range: x1 = x2 = [-100:100]
Optima Variables: x1 = x2 = 0
Optimum Function Value: f(x1,x2) = 0


SSGA

Best Initial Values
x1 = -3.1670779933654662
x2 = -6.9732697896143732
F(x1,x2) = 2.9646431665317086

Best Final Values (after 3000 Generations)
x1 = -2.9802323275873732e-006
x2 = 2.9802323275873732e-006
F(x1,x2) = 0.0036238913066679486
Simulation Time = 61.629 s


Evolution Strategy

Best Initial Values
x1 = 8.4105629978750667
x2 = 7.3227216058050848
F(x1,x2) = 4.6930491714630076

Best Final Values (after 1000 Generations)
x1 = 1.3362218153590791e-162
x2 = -2.8625317383361051e-163
F(x1,x2) = 0
Simulation Time = 1.232 s

Here a comparison.




3 - Third Function: Easom Function

Number of Variables: 2
Number of optima: 1
Variables' Range: x1 = x2 = [-100:100]
Optima Variables: x1 = x2 = pi
Optimum Function Value: f(x1,x2) = -1


SSGA

Best Initial Values
x1 = -11.977538823412026
x2 = 1.2930781034552485
F(x1,x2) =-3.975239915042439e-102

Best Final Values (after 3000 Generations)
x1 = 3.141591046499939
x2 = 3.1415970069645942
F(x1,x2) = -0.99999999996769862
Simulation Time = 58.173 s


Evolution Strategy

Best Initial Values
x1 = 21.300842203805615
x2 = 14.823566430631823
F(x1,x2) = -1.6190289343389992e-203

Best Final Values (after 45 Generations)
x1 = 3.1415926565055088
x2 = 3.1415926519644986
F(x1,x2) = -1
Simulation Time = 0.061 s


The Graph:



One more time the ES got a very good solution and the SSGA did not find the result, althoug the SSGA is very close to it. The ES was faster and the most important: the ES got the solution using only 45 generations.

4 - Fourth Function: Michalewicz Function

Number of Variables: 2
Number of optima: 1
Variables' Range: x1 = x2 = [0:pi]
Optima Variables: x1 = x2 = pi/2
Optimum Function Value: f(x1,x2) = -2

SSGA

Best Initial Values
x1 = 1.5210479820083809
x2 = 1.4612604610821343
F(x1,x2) = -1.5408508750355414

Best Final Values (after 3000 Generations)
x1 = 1.5707963736082748
x2 = 1.5707963736082748
F(x1,x2) = -1.9999999999999993
Simulation Time = 55.8 s


Evolution Strategy

Best Initial Values
x1 = 1.7029091414282871
x2 = 1.6858213688002974
F(x1,x2) = -1.0194035697340043

Best Final Values (after 35 Generations)
x1 = 1.5707963223628052
x2 = 1.5707963300574828
F(x1,x2) = -2
Simulation Time = 0.03 s


The Graph:




5 - Fifth Function: Ackley's Function

F5 = -a·exp(-b·sqrt(1/n·sum(x(i)^2)))-exp(1/n·sum(cos(c·x(i))))+a+exp(1)
a=20; b=0.2; c=2·pi; i=1:2
x1 = [-32.768:32.768]
x2 = [-32.768:32.768]
Global Minimum: f = 0; x1 = x2 = 0;


Below we can see the graph of Ackley's Function:




This function is very multimodal, there are a lot of local optima, and this can trap the search in those places.


A closer view:




A plot map:





SSGA

Best Initial Values
x1 = -1.0377881168659961
x2 = -2.285001044660838
F(x1,x2) = 7.2358656827208128

Best Final Values (after 3000 Generations)
x1 = -9.7656252910291452e-007
x2 = 9.7656252910291452e-007
F(x1,x2) = 3.9063009055542979e-006
Simulation Time = 70.251 s


Evolution Strategy

Best Initial Values
x1 = 2.7559732831437018
x2 = 2.3995094157902104
F(x1,x2) = 10.108951936627786

Best Final Values (after 1000 Generations)
x1 = 1.0133584085863174e-016
x2 = 2.3441664160783457e-017
F(x1,x2) = 1.4463256980956629e-016
Simulation Time = 1.272 s


A comparison:





Well, I think that both were not so good in the search, the global minimum was not achivied with a good precision.

We saw, again, that the ES had a better performance than the SSGA, I do not know if this is due the kind of problem that each one was designed to deal or, simply, because the ES is better in those kind of problems.

Até Mais!!!

Marcelo

Evolution Strategies and Binary Genetic Algorithm Comparison (New Version)

Hello, my friends!!

Here I am again to show you some Evolutionary Computation Simulations. :D

Today we will see a little comparison between an Evolution Strategy (ES) and a Binary Genetic Algorithm. I applied the algorithms to optimize three function: Easom Function, Michalewicz Function and Schaffer Function. All these are minimization problems.

Let me tell you about the configuration of each algorithm:

1-Binary Genetic Algorithm:
a) String Lenght: 25 bits
b) Probability of Crossover: 0.7
c) Probability of Mutation: 0.03
d) Elitism: Ok
e) Population Size: 100 chromossomes
f) Number of generations: 1000 Schaffer Function F7; 3000 Easom Function; 3000 Michalewicz Function
g) Selection Method: Stochastic Tournament (2 chromossomes)

2-Evolution Strategy(ES):
a) Type of Evolution Strategy: (mu+lambda)-ES
b) Number of Parents (mu) : 15
c) Number of offspring (lamda): 35
d) Mutation: Ok.
e) Crossover: Ok.
f) Number of Generations: 1000 Schaffer Function F7; 45 Easom Function; 45 Michalewivz Function


In the Graphs the Red Line is the Binary Genetic Algorithm and the Blue Line is the Evolution Strategy.

First Function: Easom Function
Number of Variables: 2
Number of optima: 1
Variables' Range: x1 = x2 = [-100:100]
Optima Variables: x1 = x2 = pi
Optimum Function Value: f(x1,x2) = -1

Best Initial Values of GA:
x1 = -11.977538823412026
x2 = 1.2930781034552485
f(x1,x2) = -3.975239915042439e-102

Best Final Values of GA(after 3000 generations):
x1 = 3.1249971128999325
x2 = 3.1249971128999325
f(x1,x2) = 0.99917409269409185
Simulation Time: 28.381 s

Best Initial Values of ES:
x1 = 21.300842203805615
x2 = 14.823566430631823
f(x1,x2) = -1.6190289343389992e-203

Best Final Values of ES(after 45 generations):
x1 = 3.1415926474802367
x2 = 3.1415926550537772
f(x1,x2) = -1
Simulation Time: 0.07 s

Below there is an image of the best fitness versus generations



A closer image:





Second Function: Michalewicz' Function
Number of Variables: 2
Number of optima: 1
Variables' Range: x1 = x2 = [0:pi]
Optima Variables: x1 = x2 = pi/2
Optimum Function Value: f(x1,x2) = -2


Best Initial Values of GA:
x1 = 1.5210479820083809
x2 = 1.4612604610821343
f(x1,x2) = -1.5408508750355414

Best Final Values of GA(after 3000 generations):
x1 = 1.5707962799815152
x2 = 1.5707962799815152
f(x1,x2) = -1.9999999999999978
Simulation Time: 42.411 s


Best Initial Values of ES:
x1 = 1.7029091414282871
x2 = 1.6858213688002974
f(x1,x2) = -1.019403305540362

Best Final Values of ES(after 45 generations):
x1 = 1.5707963401440286
x2 = 1.5707963200922377
f(x1,x2) = -2
Simulation Time: 0.101 s

Below there is a graph/chart showing us the comparison for that function:





Below we can see a closer view:



Algthough the GA have began closer to the global optimum(its variables are very near from pi/2), the GA did a good search but did not find the global optimum. However, the ES got the answers and is interesting to note that the ES began the search less close to optima variables than the GA did.


Third Function: Schaffer Function
Number of Variables: 2
Number of optima: 1
Variables' Range: x1 = x2 = [-100:100]
Optima Variables: x1 = x2 = 0
Optimum Function Value: f(x1,x2) = 0


Best Initial Values of GA:
x1 = -3.1670779933654662
x2 = -6.9732697896143732
f(x1,x2) = 2.9646431665317086

Best Final Values of GA(after 1000 generations):
x1 = -2.9802323275873732e-006
x2 = -2.9802323275873732e-006
f(x1,x2) = 0.0036238913066679486
Simulation Time: 9.42 s


Best Initial Values of ES:
x1 = 8.4105629978750667
x2 = 7.3227216058050848
f(x1,x2) = 4.6930482262207818

Best Final Values of ES(after 1000 generations):
x1 = 1.3362218153590791e-162
x2 = -2.8625317383361051e-163
f(x1,x2) = 0
Simulation Time: 3.21 s

Below we can see the graph:



Até Mais!!

[]´s

Marcelo