0

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?

Improve this question
2
  • "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"? Commented Apr 24, 2013 at 23:02
  • 1
    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. Commented Apr 24, 2013 at 23:10

2 Answers 2

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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.

Improve this answer

6 Comments

No. Every solution at any point should be fully legal, otherwise you're algorithm may carry through these solutions that look awesome, but aren't legal and can't be modified to be legal without a massive hit to quality. And worse than that, it will use cross-over and mutation to generate more illegal solutions. Thus you'll potentially end up with a bunch of illegal solutions in your final population, and, once made legal, leads to a solution very far from optimal. Whether this can happen / how likely this is depends on the problem.
@Dukeling: So do you suggest that every time while doing a cross-over and mutation an illegal string is generated it should be replaced with a legal string?
@vjain27 Well, a better idea would be never to generate an illegal string in the first place, if possible (they had a similar problem at the company I work, and managed to change the representation such that illegal solutions aren't generated in the first place). But yes, if this is not possible, I would advise illegal strings be replaced with legal strings as soon as they appear. However, my advise is to be taken with a pinch of salt, I'm no expert.
It's problem-specific - sometimes allowing illegal intermediate values will let you move out of a local maxima and into a global maxima, but it might also result in instability where you start producing infinities and NANs all over the place.
Evolutionary computation isn't an algorithm or a method, but a general category which includes genetic algorithms.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.