Genetic algorithms

Question

I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues.
I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of numbers?
Also the Rastrigin's wants the elements in the list to be -5.12<=x(i)<=5.12 what happens if when i generate the chromosome it will produce number not in that interval? I'm new to this so help and explanation that will aid me in understanding will be highly appreciated.
Thanks.

Answer 1

I assume you're programming in C. Integers (int for the C language) can be packed as an array of 4 bytes/char (32 bits). so if your array is

char* chrom_as_bytes=(...)

your can get the i-th value by casting to int*

int ith=3;
value=((int*)chrom_as_bytes)[ith];

if a value is not in the range -5.12<x<5.12 than, your fiteness function should return a very bad value and this step in the evolution should be discarded at the next generation.

See also the article in Wikipedia.

Answer 2

Why do you need to represent the chromosome as a binary string? You can write evolutionary algorithms that use other types. You could use a list of numbers.

As for restricting the values, when you generate the initial members of the population ensure that the random numbers are within the range that you need. Restrict your mutation operator to avoid producing values outside of this range (you could either just truncate values that are outside this range, or you could have them wrap around).

If you really have to use a binary string, take a look at Gray Code, which is a way of encoding numeric values in binary making them more amenable to mutations.

Answer 3

You are looking to implement a Genetic Algorithm. Your implementation should be such that it works for any generic minimization (or maximization) problem, and not only the Rastrigin function. You may decide to implement a binary coded GA or a Real coded GA. Both has its own uses and niche applications. But for you, i would suggest to implement a Real coded GA. As per your question regarding what to do, if the generated variable values are outside of [-5.12:5.12], a Real coded GA and binary coded GA will handle them differently.

Having a reference code is always good before you start implementing your own version. If you are looking for a C implementation, the source section of lab has a Real Coded GA implementation, which is widely used by us and others for our research work. I would suggest you to play with it and try out some of the simple optimization problems given there.

Pyevolve is a Python library for Genetic Algorithms and Genetic Programming.

Now, that we have talked about the implementation stuff, is your GA understanding clear? If not, please refer to this tutorial, which introduces GA from a optimization point of view. Please note that the explanation of crossover and mutation for a Binary Coded GA do not automagically transfer to a Real Coded GA. Real coded GA has its own intricacies, which you will need time to read some papers and understand them. No hurries, but with full time effort you should be able to get going easily.

Answer 4

If you're interested, I've done an implementation using Pyevolve: http://pyevolve.sourceforge.net/examples.html#example-7-the-rastringin-function Sorry for the typo in the name.