Two problematic issues with genetic algorithms mutations

Hi all,

I have been using genetic algorithms (and several other evolutionary
methods) for the past few years, and I am very happy with the results
achieved (I managed to solve several "open" problems in our project
using GAs).

However, I have noticed the following two problematic issues with the
way standard binary-string GAs are mutated:

1) LSB and MSB have the same mutation probability

Assume we have 5 bits representing a certain parameter (its value can
be between 0 to 31). When performing standard mutation, we are
basically flipping every bit with a low probability (say 0.001). In
this case the probability that the least significant bit is flipped is
the same as the probability that the most significant bit is flipped.
For example, if currently our 5 bits contain 10011, the probability
that after mutation it becomes 10010 is the same as the probability
that it becomes 00011. Intuitively, one would expect that more
significant mutations (e.g., mutating MSB) occur less than minor
mutations. And I believe this is also what's happening in natural
evolution.

2) Unequal increase/decrease probabilities

Assume 5 bits representing a certain value are 01111 at the moment
(representing the value 15). Now, what is the probability that after
the mutation, the value increases or decreases by one:

a) decrease: 15 becomes 14 (01111 becomes 01110)

Only one bit needs to be mutated.

Assuming a mutation rate of 0.01:

probability = 0.99 * 0.99 * 0.99 * 0.99 * 0.01 = 0.0096059601


a) increase: 15 becomes 16 (01111 becomes 10000)

All the five bits need to be mutated.

Assuming the same mutation rate of 0.01:

probability = 0.01 * 0.01 * 0.01 * 0.01 * 0.01 = 0.0000000001

In other words, in the above example the probability that our number
is decreased by one is about 100 million times (!!) more than the
probability that it is increased by one.


For both these issues I used devil's advocate kind of examples to
illustrate the point. However, in practice I have noticed these
problems taking place frequently. For example, when a certain
parameter reaches the value 111111111 (that is, 511), practically all
chances that after a mutation it increases are gone.

I didn't find any reference to these problems (especially the second
problem) in the published literature. I will be happy to hear your
insights.

As far as I can see, Evolution Strategies (ES) deals with both these
issues better. For the first problem, ES can add Gaussian noise to a
parameter so that the probability of minor mutations is greater than
that of major mutations. And for second problem, since ES does not use
bit flipping for mutations, it is impervious to this problem.

Thanks,

David.
.

Relevant Pages

  • Re: the numbers (or "why is the debate eternal")
    ... known, selection criteria is roughly known, probability of mutation is ... happens that creationist tries to attack evolution and the ... The point is that we need to know certain things like selection ...
    (talk.origins)
  • Re: Hardy-weinberg Equilibrium
    ... while panmixis means equal probability of any ... But suppose we assumed a normal distribution? ... Are you claiming that statistical randomness requires a uniform ... For example, mutation ...
    (talk.origins)
  • Re: Re: microreversibilty of a mutation
    ... If a mutation from A to B has a probability pthen the ... One direct consequence of this hypothesis is that if evolution is ... Such a probability breaks down the micro reversibility and inverting ...
    (talk.origins)
  • Re: microreversibilty of a mutation
    ... If a mutation from A to B has a probability pthen the ... something about genotypes based on phenotype frequencies. ... math and physics are bound for a long run ...
    (talk.origins)
  • Re: microreversibilty of a mutation
    ... If a mutation from A to B has a probability pthen the ... math and physics are bound for a long run ... There are plenty of biologists who know about non equilibrium ...
    (talk.origins)