Re: We believe in design

On 5/28/05, Pim van Meurs <pimvanmeurs@yahoo.com> wrote:

[quote]Evolutionary algorithms apply the process of variation,
> reproduction, and selection to look for an individual capable of solving
> the task at hand. In order to improve the evolvability of a population
> we propose to copy important characteristics of nature's search space.
> Desired characteristics for a genotype-phenotype mapping are described
> and several highly redundant genotype-phenotype mappings are analyzed in
> the context of a population-based search. We show that evolvability,
> defined as the ability of random variations to sometimes produce
> improvement, is influenced by the existence of neutral networks in
> genotype space. Redundant mappings allow the population to spread along
> the network of neutral mutations and the population is quickly able to
> recover after a change has occurred. The extent of the neutral networks
> affects the interconnectivity of the search space and thereby affects
> evolvability.[/quote]
> How neutral networks influence evolvability Marc Ebner, Mark Shackleton,
> Rob Shipman
>
> See also
>
> http://www2.informatik.uni-wuerzburg.de/staff/ebner/research/evolvability2/evolvability.html
> for an example using pictures.
>
>
Pim,

This is REALLY interesting to me, because having seen the pictures on the
link you have given me it made me remember that a few months back I had just
about exactly the same idea (using neutral mutations) for GA's as a means of
improving the efficiency. I really got quite excited about it for a few
hours, then came to the conclusion that it wouldn't work for anything other
than toy problems of low dimension, and since in my job we are optimising
systems with tens of thousands of variables, it wasn't going to be a lot of
use. Maybe I should have pursued it further. I was unfamiliar with the term
"neutral networks", but I think that is how my idea worked.

In essence it was this. Consider a classical GA where the bit string
genotype maps to a phenotype which is a vector of numerical parameters that
are fed into the fitness function. Say you have 100 parameters, and 10 bits
per parameter, giving an integer between 0 and 1023 for each parameter
(suitably scaled). That gives you a genome of 1000 bits in length. Now I
considered modifying the segment for each parameter so you had two copies of
the genome for each parameter (10+10 bits, and we call these P and Q). You
also have an extra bit S for each parameter that is 1 if P is to be used in
the phenotype and 0 if Q is to be used. So that makes 21 bits per parameter.
So for example if you used binary coding, then
S=1,P=1111111111,Q=00000000000000 would code to 1023 and
S=0,P=1111111111,Q=0000000000 would code to zero.

If one uses that redundant coding scheme, then it is clear that at any time
only half the P/Q bits are used for the phenotype, and the non-selected
segment would be subject to neutral mutations, that wouldn't effect the
phenotype until the selector bit flipped. In this manner, the genome could
potentially spread out over the "neutral network" as shown in the diagrams
in the link you provided, and could in principle then hop to a completely
different part of phenotype-space when the selector bit flipped.

For a while I really thought this was worth pursuing, but soon abandoned the
concept. Why? Because this idea, while it looks plausible in 2-D space (as
shown in the diagrams on your link) is highly unlikely to work in high
dimensional space. This is because of a well-known phenomenon called the
"curse of dimensionality", which means that as dimension increases, the
ability to populate search space with a random set of points decreases, or
in other words the number of points (population) needed to spread out evenly
over this space grows exponentially. For example in 2-D to cover a unit
square with 10 points per axis uniformly requires 100 points. But to cover
to the same density in 100-Dimensional space requires 10^100 points.

Therefore my conclusion would be that my idea might work well for a GA that
is optimising a function of a few variables (say less than 5), but would
become increasingly ineffective for high dimensions, particularly if the
space of viable solutions is sparsely populated itself.

So ... to return back to my original point - if the space of viable
phenotypes were densely populated (designed that way as Glenn said in his
article) so there were caverns of viability connected by viable paths, then
evolutionary search can work, and indeed the neutrality idea would improve
the efficiency of that search by spreading out over neutral networks. But if
this were not the case, then as I see it, neutrality doesn't have much
effect - it won't change a space that is sparsely populated with viable
organisms into a viable one - only make a densely populated one more rapidly
searchable.

However, maybe one day I'll give my S-P-Q algorithm a go if I get time.

Thanks for the link which was very stimulating - hope it hasn't bored all
the others!

Iain
Received on Mon May 30 16:54:36 2005