### 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

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