Evolution and Evolutionary Computing.

Jean Baptiste Lamark was the true discoverer of Evolution, unfortunately there was not much evidence around in 1800 to back up his leap of faith. Darwin, on the other hand, collected examples to prove his work and so became the father of evolution. Darwin's and Lamark's ideas of natural selection, much like Newton's theories, have gone through some major changes and much has been added to their work through time. Darwin and other biologists used natures results for their examples of their theories. Darwin's most famous example is the finches he found on a collection of islands. These finches have differing beaks according to the environment they had found themselves in. Other examples include moths that evolved to cope with the colours created by pollution.

Evolution has had more than it's far share of opponents, mostly from religious quarters. For a dramatic representation of this see the film, 'Inherit the wind', a black and white movie where the teaching of evolution comes to trial. Even recently other theories Have been put forward such as resonant theory, that attempt to rewrite the rules of evolution. Again often this is due to religious opposition.

DNA is at the center of evolution and shows how information about form and shape is conserved from one generation to another. The information that describes the object is called the Genotype. Without these means there would be no sure fire way of reproducing even identical off spring - the rules of entropy put paid to this. DNA is the instructions the body's cells follow to create and run all its functions, like a look up table or hand book for each cell. A asexual creature that reproduces effectively recreated a clone of its self. This is fine up to a point and is a useful tool for creatures with a limited life span but can cause problems for more complex life forms.

The problem is no room for adaptation is allowed from generation to generation. Variations are important in the survival of a species. A species has to survive in an environment and few environments are ever stable, the main reason being that of hunting and being hunted. If any one creature can increase its chances of survival then it is far more likely to reproduce, after all a dead fertile creature has no chance of reproduction! In fact for a species to survive it has to take part in an evolutionary arms race. The Red Queen principle, taken from Alice in Wonderland, says that species has to change in order to survive. In essence to stay still a species has to keep on moving forward, and moving forward is done by way of adaptation. Adaptation can only come about through alteration. This can be done in more than one way.

Mutation in asexual system can lead to adaptation but also leads to a high chance of useless mutation. Natural selection can iron out the bugs in the system providing there is not to much mutation. See the section on Complexity for details of why this is important. At best this system works but can be too random to be of real use and good results can only happen over many generations.

The best current solution is recombination of genes and the process for this is sex. By recombining similar set of genes the resulting DNA is a combination of working parts and therefore more likely to result in an error free set of instructions. This also has the advantage of allowing for selection when mating, a device used by all creatures and results in some of the stranger behaviour in the animal kingdom (e.g. disco dancing).

As this is true for nature so it is true for aLife. Evolution has turned out to be a powerful computing tool and has produced some useful and surprising results. Evolution is now used in computer programming in the field known as genetic algorithms. These are programs that are not so much programmed as grown.

Alife has not only been instrumental in using evolution but has also proved evolution's credentials. Before it needed a considerable amount of time to do any evolution experiment, now it is possible to model evolution and watch it in the accelerated environment possible inside a computer.

One good example of this is the Biomorph program written by Richard Dawkins as part of his exploration of evolution. Dawkins is one of the preachers of what has been called the of doctrine DNA. In his book, The Blind Watchmaker, he describes the way he put together the program and the amazement he felt upon getting the unusual shapes he ended up with.

The Biomorph program is a simple program that uses mutation and manual selection to breed creatures known as Biomorphs. These creatures are made out of lines and each possesses a simple set of instructions, much like DNA, to describe their shape. Starting from a seed, you are faced with several similar creatures; each slightly mutated from the starting seed. As this is a simple program there is no virtual environment for these creatures to battle in, see Karl Sim's work in the creatures section for details about this. Instead selection is the work of the user. It is simply a matter of picking the creature you like the look of.

For example say you want a creature that looked like a lunar lander. The starting creature may look nothing like a lunar lander and may look more like a squashed fly. By picking the squashed fly that is more like a lunar lander than the others then in time the result will be something like the result you want. So in this case the environment is aesthetic and fitness is summed up in terms of looking like a lunar lander.

Other time dawkins managed to breed all types of creatures using the power of evolution, or at least a simulation of it. In this case it is possible to say that this kind of evolution is man made and cannot be seen as truly independent. It could be seen much like the selective breeding used on dog to alter their appearance. There are models that are not reliant on human selection.

Environmental Selection.

For a better example a system that, given the ability, uses evolution is better. The best known system that does this is Tom Ray's Tierra. This program, devised by a practicing biologist, sets up an environment where creatures compete for machine resources. These creatures are strings of instructions with markers that denote how long they are. As time goes by creatures are gathered by what Tom Ray called the reaper. These collected dead creatures, those who could not carry out instructions, and the unfit. Fitness was decided by the ability to carry out instructions. There was also a time limit, so creatures had to be quick at what they did.

The program was first run on a Toshiba laptop. It started on the 3 January 1990, and ran over night resulted in enough data to keep Tom Ray busy for a considerable amount of time. As the creatures were made from assembler language they were not a visible as dawkins creatures so it took a long time to find out quite what had happened. By studying this and other runs Tom discovered that the system he had created was using many of the rules nature loves. The creatures, through evolution, had not only evolved into little reproduction machines but had found loopholes in the environment that meant that the creatures could grow in size beyond the limit the program allowed. Creatures would also cheat by acting like parasites and using other creatures' time to do their work. Others formed groups that acted as one, multi-part creature. Tom sometimes found that some creatures could not reproduce and it took some time to find out that this was because they were dependent on other creatures to do this for them.

Evolution had come up with programming tricks only ever used by some expert programmer. The code was self optimized and did things in and immensely small amount of cycles. As Tom was an adequate programmer and no coding expert he had no way of dictating these routines and often it took him a long while to work out what his creatures were doing.

Tierra had become a breeding ground for what has become silicon based life. Many problems were solved through necessity with predators always ready to pounce on those solutions that were not up to speed.

Another system that behaves as an environment for creatures to live is Venus (I-II). Venus grew out of what was called "Corewars", an environment where computer programs created creatures to battle against each other.

Evolutionary Algorithms and Genetic Algorithms

An evolutionary algorithm is the product of a means of solving computer based problems using evolution as the main tool for design and implementation. There are several different types of Evolutionary Algorithm methods. The main ones are genetic algorithms, evolutionary programming and the use of evolution strategy. These methods are linked with aLife in that their main driving forces are akin to natural forces. Evolution and selection are heavily used as is the basic principle of genetics.

Each process is a method of optimization that uses its fitness to the solution as its likelihood or survival. The ideal is an optimum solution is reached by the 'grown' algorithm. They are best used to solve problems that have proven difficult to code. Hand-written specialist code can often be better than an evolved solution although it has been found that Evolutionary Algorithms can often be very rugged pieces of code. These rugged pieces of are less likely to do nasty things providing the creation technique was good.

The different types of algorithms mainly differ in their approach of the subject. Evolutionary Programming and Evolution Strategies are very similar although they were both devised independently. Each of them does not use a simulation of Genetic crossover as in nature but instead mutate the actual creature. Nature does not do this as changing the DNA of a creature that is living can cause all sort of problems; there are to many interdependencies. In a program it is totally safe to do this, after all that is how programs are written and debugged.

Mutations are applied directly to a parent of a creature. Offspring are therefore reproduced asexually with varying mutations. These mutations can be controlled, unlike nature, and be forced to move more rapidly. An optimum solution to the problem is often estimated and the results of the algorithm reaches towards the values of this solution mutation is lessened to allow for greater accuracy. Evolution does something similar as the harsher the environment; the higher the price paid for not being adapted to that environment.

Genetic Algorithms try and mirror nature by using a DNA type structure as the center of their workings. This is the main difference between genetic algorithms and the other members of evolutionary algorithms. The use of a structure that can be used for crossover recombination means that all the aspects of the program must be able to be converted into a string of simple symbols and back again. Evolutionary programming mutates the phenotype in effect instead of this genotype approach. Evolutionary Strategies often involve the manipulation of variables rather than the program directly.

A concept of a fitness landscape is often used. This landscape has peaks and troughs and each algorithm can be represented as a dot on this landscape. The optimum solution is the highest peak on the map. Each creature's driving goal is to get as far up on the landscape as possible. By the used of predators to pick on the weaknesses of those algorithms that are not fully developed it has been shown that solutions can be reached much quicker.

Evolutionary Algorithms main difference from the main body of aLife is that they have a distinctive goal and one reached often cannot be bettered. This is unlike Life where there is no known goal and is a continuing process. For practical purposes solutions are always needed and Evolutionary Algorithms offer the chance to grow solutions when no obvious one can be found. EAs do not always come up with better solutions than hand crafted ones but they are a useful tool and will in the future become and increasingly used programming tool.

Convergent evolution .. or, Hang on, that was my idea!.

This sort of stuff happens all the time, its called convergent evolution. Often a good idea is thought of by several different people at the same time. The question is why did one not have the idea years before. The easy answer is if one did it would not be convergent evolution. The other explanation is no one person can make huge intellectual leaps. Even the most intelligent person has to be fed the right information to get the right answer. News spreads well among like minds and it is no surprise that similar information can act as a spark for several minds. The result is the same idea may be devised by many people at the same time, or at least independently without knowledge of the prior decision.

One advantage of this is that an answer conceived independently by many people, not through the teaching on an idea, is far more likely to be correct as each person has had to prove each step of their thinking. Therefore good theories and correct concepts may arrive independently all the time. All that may change is the finer details or the terminology used. This can be seem when comparing disciplines.

Please send any corrections, comments or additions to: alife(at)stewdean(dot)com