Natural Search
Natural SearchNaturalSearch is a generalization of EvolutionByNaturalSelection and GeneticAlgorithms. The term was coined by RobHarwood.
Sketch algorithm:
NaturalSearch(population) begin generation replicate individuals with mutation perform NaturalSelection exit loop if previous generation is genetically identical to next generation next generation result is populationBug: Why does it terminate if two successive generations are identical? This could happen by chance during a period of rapid violent change. If mutation is random, then a new spurt of interesting development could begin at any time, even after a lengthy phase of stability. --DanielEarwicker
Good call. I suppose a true natural search would never terminate (until population dies or ceases reproducing). Choosing a termination condition will always be a tradeoff between quality and processing time. Genetic stasis is a pretty common criterion for GAs, although a fixed time or number of generations is often more practical. I think I'd revise the algorithm and definition, but right now I'm content to let it stagnate a bit until my interest piques again. -- RH
The problem with this algorithm as listed is that it can converge to a fitness maximum that is not a global maximum. Evolution in real-world biological terms appears to follow a "punctate equilibrium" pattern where it is possible for a species to escape from a local fitness maximum to a higher (but possibly still only locally maximal) fitness state. The effect is long periods of very slow evolution interspersed with short periods of very rapid change.
Even punc-eq (PunctuatedEquilibrium) folks don't think that it provides a better solution - just a more rapid approach to a local maximum. -- PeteHardie
JohnHolland's landmark work in the field of GeneticAlgorithms is about this very thing. He proved that the classical form of GeneticAlgorithm is guaranteed to find the global maximum, though it might take forever. The secret lies in the exponential nature of reproduction. Other research regarding the more modern form of GeneticAlgorithm (which NaturalSearch is based upon) show similar findings of robustness. I don't have any specific papers to cite since I'm just recalling this off the top of my head, but I'm sure there's a lot of info to be found on ftp://alife.santafe.edu/pub/USER-AREA/EC/Welcome.html.
The proof is interesting from the theoretical point of view, however, none of the systems to which NaturalSearch is being performed have infinite time, nor do they have the unbounded space and resources necessary to sustain an exponential population expansion.
The same can be said of any robust, general-purpose search algorithm. SimulatedAnnealing, and TabuSearch are examples. As long as NP != P, this is a weak criticism. Also see the NoFreeLunchTheorem.
This is too optimistic for many real-world interesting problems. Current computational power is unable to even predict the three-dimensional structure of a polypeptide chain of any reasonably biologically relevant length.
I would suggest reading JohnKoza?'s books on GeneticProgramming, especially ISBN 1558605436 and ISBN 0262111896 . All the various forms of EvolutionaryComputation? are already being used on real-world NpComplete problems such as scheduling, etc. Koza lists several inventions that were invented by GeneticProgramming and related methods. Also see comp.ai.genetic for the current usenet issues, and http://www.aic.nrl.navy.mil/galist/ for a moderated academic view. I won't further defend the applicability of NaturalSearch here. Go to these sources if you're skeptical.
The robustness of the algorithm, combined with its simplicity, is one of the main reasons I think it's so cool.
Old definition:
Something is exhibiting NaturalSearch iff, within an arbitrary range of time, it replicates such that the replicant is also capable of replicating, and the replicant is different from the original, and those differences are both inheritable and also affect the replicant's ability to reproduce when compared to the original.
The conditions of NaturalSearch can be condensed to:
Something is exhibiting NaturalSearch iff it is under the domain of NaturalSelection.
The term NaturalSearch is related to the term NaturalSelection by the following simplified extension of the GeneticAlgorithm:
A NaturalSearch performs repeated selection on a population of genomes, while the genomes replicate under the conditions of NaturalSearch. Essentially, the conditions and the selection mechanism are those of NaturalSelection (as opposed to divine selection, or random selection, for example). The NaturalSearch itself, then is the process by which NaturalSelection operates.
To make the analogy to GeneticAlgorithms, NaturalSelection is the loop body, and NaturalSearch is the loop itself. If we were to refactor the code, NaturalSearch would be a method which repeatedly called the NaturalSelection method. According to the theory of EvolutionByNaturalSelection, the end result of such a process is evolution.
Again, drawing on the abstraction of the GeneticAlgorithm, which is a generalized SearchAlgorithm?, NaturalSearch is a GeneticAlgorithm which uses NaturalSelection as its selection criteria.
It's really just another way of restating EvolutionByNaturalSelection without all the extra traditional baggage that forces EvolutionByNaturalSelection to restrict its study to natural cellular life, and without the specialization of GeneticAlgorithms which restricts its study from natural cellular life.
The two processes are the same, and the nice clean name to describe them as one is NaturalSearch.
See NaturalSearchIsaDefinitionOfLife
Please note, the above was written between 2-3am and is the first time I've written it out. It's a rough draft. Comments are welcome. -- RobHarwood
Elsewhere (DefinitionOfLife) it has been noted that a failing of the above conditions is that they do not consider point-mutations, only copying errors. This is an omission on my part. The intent was to draw the minimal conditions from NaturalSelection. When I have some time to think about it, I'll attempt a revision of the above conditions to reflect this. -- RobHarwood
What exactly is the difference between a point-mutation and a copying error in a single bit/base pair?
Functionally, there is no difference. Imagine if there were no copying errors, but point mutations did occur. A cell divides into two daughter cells; one of those cells mutates; the two cells divide into four, some of which also mutate during their lifetimes. Over the generations, genetic variation would still be generated even though the actual copying process is perfect. -- RobHarwood
In that case, it's hardly a problem that they fail to consider one or the other. I'm not so convinced there's even a theoretical difference between the two.
The term 'mutation' in its most general sense covers both, and also includes crossover in sexual species. The definition should probably be changed to use this more general term. -- RH
Why is replication a requirement? Suppose we have an "individual" which can actively adapt it's structure such that it operates more efficiently within its given environment. As a thought experiment, posit the existence of an individual who is both sterile and of infinite longevity yet able to modify his genetic structure at will as he determines would be best. Is this individual a) alive? and/or b) undergoing NaturalSearch? Most AI would fall into this category.
Such an entity may or may not be alive, and is definitely not undergoing NaturalSearch. What you're referring to is an entirely different effect.
Agreed. There are many robust search algorithms, and NaturalSearch is only one of them. The reason I think NaturalSearch is so interesting is that it has come about spontaneously in the form of natural life, and I think life is pretty darn neat. Since most other search algorithms were invented by humans, we might say that NaturalSearch was the first robust search algorithm. Of course, annealing is a counter-example, but it's fun to pretend anyway. :-) -- RobHarwood
By adapting itself to operate more efficiently in its environment, it is searching for a particular entity similar to itself which will retain its identity and improve its fitness. This is an abstraction of a genetic algorithm which removes the notion that genetics are essential to evolution. The body of the entity is analogous to a population; its cells will remain a population, though individual cells might not remain in the population. The creature's immortality demonstrates it has at least a net equilibrium with its environment, and so, for any sufficiently large timescale, the creature's NaturalSearch is successful.
Dare I add that it seems pretty pointless to be able to modify your genetic structure at will if you're sterile ?
I should think that its ability to alter its body to any situation would render sterility highly improbable.
The above ("old") definition uses the phrase "it replicates". This seems a bit narrow, because it can be interpreted to exclude the case where a 3rd party does the replication, with no intentionality from the thing that is replicated.
Intentionality is intentionally unspecified (irony intended...). It doesn't matter how the replication occurs since the same emergent properties arise (i.e. evolution of complexity, robustness, etc.). However, I am going to amend the above definition soon to remove the focus on the 'it' and place it on the 'process'. -- RH
Things that fit the description:
Here is an attempt to draw a UML diagram of NaturalSearch and its relationship to traditional EvolutionByNaturalSelection and GeneticAlgorithms as SearchAlgorithms?:
(Darn, this is harder to get right than I thought. ConvertSpacesToTabs screws it up, and backslashes seem to get deleted by Wiki)
+---------------+ exhibits +-----------+ | NaturalSearch |------------| Evolution | +---------------+ +-----------+ /| /_| || |+--------------------------------+ | | +-----------------------------+ +-------------------+ | EvolutionByNaturalSelection | | GeneticAlgorithms | +-----------------------------+ +-------------------+
Personally I have long used EvolutionByNaturalSelection to refer to what you call NaturalSearch. It doesn't have carbon-based baggage for me, or for anyone I recall discussing it with. In fact creationists claim that evolution is not what happened in our biological history.
I think the new term is a bit dubious. "Search" suggests to me more teleology, more purpose, than evolution has. "Natural" seems to rule out various artificial setups such as cellular automata. In fact, in my experience, to design a system with interesting evolution takes great care. Some ways of representing genes, and mutation regimes, are more fruitful than others. It makes sense for "natural" to qualify the selection process but not the whole thing. -- DaveHarris
I like "search" in the sense of "a process that converges on a solution". No teleological connotation need enter the term. Similarly, Maynard Smith's concept of an Evolutionarily Stable Strategy, which according to Dawkins yields much of value in modern evolutionary biology, uses "strategy" without a connotation of "intent".
I wouldn't call what evolution does "converging", either, in general; if anything it seems strongly divergent.
The "Search" in NaturalSearch is intended to have the same degree of 'purpose' in it as "Selection" has in NaturalSelection -- i.e. none.
Also, the idea of 'converging on a solution' is difficult to translate into dynamic environments where the 'solution' keeps changing. It is true that evolution is highly divergent in nature, but the interpretation taken from EvolutionaryProgramming would be that this divergence represents an exploration into the search space, kind of like BreadthFirstSearch?. I like to think of the 'search' part of natural search as searching for niches rather than true solutions. -- RobHarwood
'I wouldn't call what evolution does "converging", either, in general; if anything it seems strongly divergent.'
Biological evolution is what converging looks like when you have multiple moving targets...
EditText of this page
(last edited February 21, 2005)
or FindPage with title or text search