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

Friday, March 25, 2005

A Little Genetic Algorithm Simulation

Hello, my friends!!!

Today I'm going to show you a very simple GA Simulation that I made here in my house using my PC - a Pentium III 700 MHz with Windows 98 and 256 MB RAM, my PC is like the girl that no guy wants do dance in a party, but anyway...

I simulated the function: f(x1, x2) = 21.5 + x1*sin(4*x1*pi) + x2*sin(20*x2*pi)
x1 = [-3, 12.1]
x2 = [4.1, 5.8]

I used two codifications to my GA, i.e, Binary and Real Numbers. And some different types of genetic operators( crossover, mutation and selection, later I'll explain how each one works).

If you are a GA enthusiast, try by yourself to optimize the function above.

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

Free Image Hosting at www.ImageShack.us

Here is a Map Graph that shows you the values that the function f(x1, x2) has inside the two intervals of it variables.

Free Image Hosting at www.ImageShack.us

See You!!

Monday, March 21, 2005

Artificial Intelligence And The Squared-Mind Persons


Today I had my first class about Performance Analysis of Systems (this class should be made last week, but the teacher was traveling) and the teacher was going on with the subject, showing us what We would face, talked about Stochastic Processes, Markhov Chains and all the set of techniques used inside his class subject. He said, too, that Artificial Intelligence aproaches (Genetic Algorithms, Fuzzy Systems, Neural Nets and others) are all Fag Things (that's right, gay things) and He likes much more the classical stochastic models. Well, I'm a Computer Engineering student and I deal with some of those AI stuff since 2002, I know I'm a newbie :D, but talk in the same way the teacher did, this, yes, is a BIG limitation. But I should make him an allowance. Why? Simple: He is a Computer Scientist and here in my country (Brazil) the CS courses don't have a good base in Mathematics and other stuffs. :D

See You!!

Sunday, March 20, 2005

Genetic Argonaut

Hello, everybody!!

I decided to begin a blog about Evolutionary Computation(EC) and other things that I study at University, but my first aim is to provide you with information about my evolution through EC, mainly in Genetic Algorithm (GA) and Evolution Strategies (ES). I'll talk about too other things, like Evolution itself and etc. See You!!
Charles Darwin Has A Posse Check Google Page Rank