Tuesday, March 29, 2005

The Evolution Strategy

Hello, my friends!!!

Here I'm again to talk with you about Evolutionary Computation, and today I have a great approach to the function in the post below, just to compare, although in a unfair way, the performance of GA's and ES's (Evolution Strategy). This stuff began in Germany on early 1960's when Ingo Rechenberg and Hans-Paul Schwefel met and decided to do bodies' shape optimization inside the wind tunnel of Technical University of Berlin. They tried the optimization through randomic pertubations in the parameters that defined the body's shape. ES was a technique designed to numerical optimization with real numbers (the real numbers idea was later taken to GA field). The classical ES has only mutation (Gaussian Mutation) and no crossover. The ES approach is very interesting in its classical template, let me explain you:

1 - You have "mu" candidate solutions;
2 - Those "mu" candidate generates, each one, "lambda"(in my simulations I always generated "mu" offspring) offspring through Gaussian Mutation;
3 - Now, You have a population with "mu+lambda" candidate solutions;
4 - Select "mu" candidate solutions to build the next generation, but the solution from offspring only passes for the next generation iff(if and only if) it has a Fitness greater than its parent, else the correspondent parent passes to the next generation;
5 - Evaluate the new population;
6 - Repeat from step 2.

I know, there are a lot of new ES's, but is very interesting to show the beginning. Today GA's and ES's are very close each other.

In the image below you see a comparation between GA's and an ES.

GA's Configuration:

Population Size: 1000
Mutation Probability: 0.01
Crossover Probability: 0.25
Number of Generations: 1000

ES Configuration:

Population Size: 1
Mutation Probability: The single candidate solution always is mutated each generation
Crossover Probability: There is no Crossover in the Classical ES
Number of Generations: 1000

Time Performance

Binary Classic GA: 76.68 seconds
Real Coded Classic GA: 26.530 seconds
Real Coded GA With Stochastic Tournament: 6.70 seconds
Elitist Real Coded GA: 29.660 seconds
(mu+mu)-ES: 1.26 seconds

The Graph:

Free Image Hosting at www.ImageShack.us

The horizontal axis is the number of generations and the other is the Fitness' arithmetic mean.

A closer Graph's image:

Free Image Hosting at www.ImageShack.us

Here you can see a closer image.

The ES approach does not oscillate like the GA's, it happens due to the nature of the ES' selection operator wich only selects a candidate solution iff it has a Fitness greater than its parent.

See You!!


Anonymous Amir massoud Farahmand said...

ES with (1+1) strategy is somehow like Simulated Annealing. Actually, if you change its selection criterion to a stochastic selection with an ever decreasing chance of selecting the inferior individual, it is SA.
Have you tested that?

25 April, 2005 00:26  

Post a Comment

Links to this post:

Create a Link

<< Home

Charles Darwin Has A Posse Check Google Page Rank