genetic algorithm handling illegal strings

0
votes

I am trying to implement genetic algorithm for maximizing a function of n variables such that each variable is in the range [-n, n].

In order to make crossover less complex, while generating initial population, I am only generating numbers from 0 to 2n and then while evaluating fitness I subtract n from each of them. Since n may be small, I have decided to use bit strings instead of integer arrays for representing chromosomes.

Now the problem is with generation of illegal values (greater than 2n) during crossover and mutation. One way would be to replace the illegal value with a legal value during both crossover and mutation. But this will be a little complicated and might also affect performance.

So I am wondering if I can leave the checking and replacing at the time of crossover and mutation and instead do it at after both are done.So I after I have the new generation, I will iterate through the chromosomes of each individual and replace illegal strings and calculate fitness. Also, is it possible to get away without replacing the illegal bit-strings?

2
algorithmgenetic-algorithm
"generation of illegal values (greater than 2n) during crossover and mutation.". How is that possible, since you say you're "only generating numbers from 0 to 2n"? - Franck Dernoncourt
2n might not be exact power of 2. So while crossover and mutation, numbers greater than 2n can be generated. for e.g. if 2n = 8, then i will be using 4-bit genes. But during mutation, by turning a bit from 0 to 1 can cause it to become 12. - vjain27

2 Answers

1
votes

There are two options, I can think of:

  1. As you indicated, if a generated value is outside of the range then try again. Of course, the algorithm may stack in a loop, in which case even after millions of generation the population may not evolve.

  2. Since you are maximizing, you should add a negative penalty for illegal values of n in the objective function. This way, you will be biasing your algorithm to stay away from the illegal numbers. I need to see your implementation to make a concrete comment. But hope this helps.

1
votes

You don't need to replace the illegal bit-strings for intermediate populations - you only need to do this for the final population. One solution is to save the last few (2 or 3) legal values for a bit-string so that you can randomly iterate over these values when replacing illegal bit-strings in your final population (rather than having to entirely make up legal values).

Incidentally, I've always preferred evolutionary computation to genetic algorithms, since more often than not I found that crossover would just lead me up a blind alley.