Neutral Networks

My very rough idea of Neutral Networks is that they are a special class of problem where you're guaranteed that you can always move "sideways" in at least one-dimension in the fitness space. That is, for any individual, there's always at least one direction to go that doesn't reduce your fitness.

The interesting part is that many systems, such as evolved neural networks, have the hope of being at least a little like ideal neutral networks, and so may be good problems to solve via evolution. Indeed, supposedly, if a problem behaves according to the rigorous definition, a global minima will be found.

All this got started with Motoo Kimura, Eigen and Schuster. Looking at RNA "folding landscapes" (not the proteins generated by the code, but the actual RNA molecule itself, (what's the jargon for it??)) as netural networks.

All this seems to have started with Lionel Barnett's 1997 MSc dissertation "Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality" (word) (ps). I find it wonderfully readable and inspiring. Here's some quotes:

Comparatively recent developments in evolutionary theory and molecular biology have all pointed to the importance of selective neutrality as a significant factor in evolutionary dynamics. This work includes Motoo Kimura's Neutral Theory of molecular evolution, Manfred Eigen's analysis of molecular "quasispecies" and recent developments in the understanding of RNA evolution both in vitro, in simulation and analytically. A picture emerges of populations engaged not in hill-climbing but rather drifting along connected networks of neutral genotypes, with sporadic jumps between networks. These neutral networks are of particular significance if they "percolate" the landscape - i.e. they come arbitrarily close to almost every other neutral network - for this raises the possibility that (given enough time) genotypes of almost any possible fitness value can ultimately be attained by the population. The scenario of a population trapped on a local hilltop vanishes.

and he also makes a point that has bugged me since first reading about GA's:

...we limit our "genetic operators" to mutation alone. Our genotypes are all haploid and reproduction is asexual. This merits some comment. In the GA literature dating back to John Holland there has been a perception of recombination (crossover) as the driving force behind evolutionary search, with mutation taking a back seat as an insurance policy against permanent allelic loss. It is not clear why mutation has been thus relegated, nor that recombination is necessarily effective in search. From the biological point of view there are many organisms for which recombination rarely or never occurs during reproduction. Molecular biology, furthermore, offers many scenarios of non-recombinative reproduction.

Finally, Sussex EASy's Bibliography of Neutral Networks (way out of date), and some high-level, but good lecture notes from a class there. (Use IE. Really, Firefox 1.0.4 didn't work)