Genetic Algorithms

Question

I am trying to implement a genetic algorithm that will calculate the minimum of Rastrigin functon , and I am having some problems. <w> I need to represent the chromosome as a binary string, and since the Rastrigin function takes a list of numbers as a parameter, how can I decode a chromosome into a list of numbers?
Rastrigin also wants the elements in the list to be -5.12 <= x (i) <= 5.12, what happens if, during the generation of the chromosome, he produces a number not in this interval?

Answer 1

You want to implement a genetic algorithm. Your implementation should be such that it works for any common minimization (or maximization) problem, not just the Rastrigin function. You may decide to implement binary encoded GA or real encoded GA. Both have their own applications and niche applications. But for you, I would suggest implementing Real-encoded GA. According to your question regarding what to do if the generated variable values ​​are outside of [-5.12: 5.12], the real encoded GA and binary encoded GA will handle them differently.

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

Pyevolve is a Python library for genetic algorithms and genetic programming.

Now that we talked about implementation materials, is your understanding of GA clear? If not, refer to this tutorial , which introduces GA from an optimization point of view. Please note that the explanation of crossover and mutation for binary-coded GA is not automatically transferred to the real coded GA. Real coded GA has its own subtleties that you will need to read some documents and understand them. Take your time, but with full load you should be able to easily get there.

Answer 2

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

As for limiting values, when you generate initial members of the population, make sure that random numbers are within the range you need. Limit your mutation operator to avoid creating values ​​outside this range (you can either simply trim values ​​that are outside this range, or you could wrap them).

If you really need to use a binary string, look at the Gray Code , which is a way of encoding numeric values ​​in binary format making them more mutable.

Answer 3

Encoding solutions to real-world problems as a bit string is actually not the case. When you get numbers as bit strings, you use fixed-point numbers to represent numbers. Once your algorithm is close to optimal, accurate to your fixed-point encoding, it will not make further progress. You can use more bits, but then you will have a slower convergence. In practice, for serious problems, this approach is several orders of magnitude smaller than a competent algorithm that works on floating point values.

Using floating point numbers will allow you to get closer to the optimal, say, 1e-10, using typical 64-bit numbers. Moreover, the modern evolutionary algorithm uses an adaptive scheme to adjust the mutation step during optimization. Such a mechanism makes it possible to increase the convergence rate in comparison with a fixed mutation step. Check this out to see what typical evolutionary optimizers achieve in the Rastrigin function: http://coco.gforge.inria.fr/doku.php?id=bbob-2010

Answer 4

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

char* chrom_as_bytes=(...) 

you can get the i-th value by going to int *

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

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

See also the article on Wikipedia .

Answer 5

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