Genetic algorithms

https://stackoverflow.com/questions/2179823

24-09-2019
|

문제

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?

해결책

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.

다른 팁

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.

Coding solutions of a real-valued problems as a bit-string is not really the way to go. When you got numbers as bit strings, you are using fixed-point numbers to represent the numbers. Once your algorithm will be close to the optimum, up to the precision of your fixed point encoding, it will do no further progress. You can use either more bits, but then you will have slower convergence. In practice, on serious problems, such an approach is several orders magnitude slower than a competent algorithm working on floating point values.

Use floating point numbers would allow you to go much closer to the optimum, say 1e-10, while using your typical 64 bits numbers. Moreover, modern evolutionary algorithm use adaptive scheme to adjust the mutation step during the optimization. Such mechanism allow for greater convergence speed, compared to a fixed mutation step. Checkout this to see what typical evolutionary optimizers achieve on the Rastrigin function : http://coco.gforge.inria.fr/doku.php?id=bbob-2010

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.