Re: Two problematic issues with genetic algorithms mutations

On Mon, 25 Feb 2008 16:25:21 -0800, deepint wrote:

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

[...]

2) Unequal increase/decrease probabilities

[...]

These issues are actually quite well-known. A popular method of
addressing them is to use a different (binary) encoding for numerical
parameters, in particular a Gray code:

http://en.wikipedia.org/wiki/Gray_code

Gray codes suffer less from these problems. In particular a random bit-
flip of a Gray coded parameter will generally (but not invariably) yield
a number close to the original.

And I believe this is also what's happening in natural evolution.

What leads you to believe that natural evolution uses anything like the
"standard" encoding for numerical parameters (quite apart from the fact
that natural genotypes are not binary)? Or, indeed, that natural
evolution has anything corresponding to "numerical parameters", given
the conventional understanding of biological encoding that nucleotide
sequences code for *proteins*, which relate to the phenotype in massively
complex and (with some exceptions) ill-understood fashion.

I believe that one should be wary in general of assuming that GAs (as
deployed in engineering problems) are anything like biological evolution.
They are not, on many levels.

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.

Perhaps you were not looking in the right place ;-)

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.

I tend to agree... if your problem space features real-valued numerical
parameters, then indeed why not encode them directly and use a more
parsimonious mutation mechanism?

Having said which, in my experience Gray coding works rather well in
practice.

Note that you do not need to go the full ES route. You can probably plug
real-valued encoding of numeric parameters, along with some
"natural" (perhaps Gaussian) mutation mechanism, into your pet GA with
minor alteration to the underlying algorithm. Of course, if you use
crossover you will need a crossover mechanism too, but it is not
difficult to come up with "natural" crossover schemes for real-value
encoded parameters. You can even, quite easily, mix real-valued and
binary parameters in the same GA problem.

Regards,

--
Lionel B
.

Relevant Pages

  • Re: The Starting Point Problem - for Howard Hershey
    ... the evolution without DNA, RNA, or ribozymes, happens at all. ... here is how modern cytochrome c might have come into existence. ... "Within one or two residue changes". ... rather than with the mutation. ...
    (talk.origins)
  • Re: Crossing a Vast "Neutral Gap" in One Step
    ... >> increase in selectability with increased binding of one protein to ... >> other than increased binding to a pre-established protein structure. ... >> That is template matching and that sort of evolution can happen very ... before the mutation was not at a selectable level. ...
    (talk.origins)
  • Re: Attn ID proponents: When a theory is in trouble
    ... All I ask for is a single instance where a claimed speciation was ... A number of wild plant species appear to be due to autopolyploidy from ... turns out to be perfectly suited for evolution. ... clearly demonstrated that reversion, just like forward mutation, *when ...
    (talk.origins)
  • Re: IDs semantic manipulations
    ... capable of modeling the observed rates of evolution. ... There is nothing in the measurement of the mutation rate, ... computed by the cellular biochemical network. ... guessing randomly or using some intelligent strategy. ...
    (talk.origins)
  • Re: Irreducible Stupidity (No, Not Nashy this time)
    ... "Do you imagine that god, after the long lunch that he took after ... What all evolutionists should keep in mind is that evolution isn't ... and falsifiable predictions, supporting data from both experimental and ... "mutation x will occur in an average of three individuals out of every ...
    (talk.origins)