CODEWITHSUNDEEP
genetic-algorithmmutation
Mohammad Asasi
Mohammad Asasi

Reputation: 27

how to mutate offspring in genetic algorithm?

I have an abstract question about mutation in genetic algorithm. I do not include any code snippet to ask my question independent of coding environment.

I am writing a genetic algorithm code but I do not know how to implement mutation. Suppose an offspring that is going to be mutated is a string like 10110011110101000111 which has a length of 20.

Mutation must be done with a very small probability for example 0.001. We produce a random number between 0 and 1, and by that we decide whether the offspring should be mutated or not. My question is that we have to generate 20 random number and make decision about mutation for every 20 bits of this offspring? or we have to generate only 1 random number for the whole offspring and toggle a bit randomly?

In other words does each bit in the offspring have a chance to be mutated according to generated random number or only one bit has the chance of mutation?

Upvotes: 1

Views: 640

Answers (1)

manlio
manlio

Reputation: 18902

"Traditionally" the mutation rate pmutation ("Genetic Algorithms in Search, Optimization and Machine Learning" by David E Goldberg) is a measure of the likeness that random elements of your chromosome will be flipped into something else (your "option 1").

I.e. if your chromosome is encoded as a binary string of length 1000 and pmutation is 1% (0.01), it means that 10 out of your 1000 bits (on average) will be flipped.

Although it would be possible to avoid much random number generation deciding when the next mutation should occur (rather than calling the RNG each time), the implementation is somewhat more complex. To avoid sophisticated niceties many implementations go with "option 2".

Consider that, if L is the length of the binary chromosome:

  • for unimodal search spaces, 1/L is often suggested as a good mutation rate (e.g. "How genetic algorithms really work: mutation and hillclimbing" by H. Muehlenbein).
  • for multimodal search spaces, mutation rates significantly higher than 1/L are the standard and your "option 2" would have some problems.

"option 1" is a bit more flexible and follows the rule of least surprise so, lacking other details, I'd choose it.

Upvotes: 2

Related Questions