Evolution and its Relation
to Computer Algorithms.

Copyright 1996 by Keith A. and Eugene L. Oxenrider
Use, reproduction, and modification of the information contained
herein, including Java applets, is hearby authorized as long as
the user acknowledges the authors in this and all subsequent work.

Table of Contents
Introduction To Evolution
Conventional Problem Solving
Problem Solving Using The EA

Introduction to Evolution

Charles Darwin was one of the first to articulate the idea of evolution in his book "The Origin of Species". At that time, the idea that things changed was very controversial. In our modern society, most people see the inevitable shifting and changing of our world and accept the idea of evolution in more than just the change of plants and animals over time.

Evolution is the idea that there is an accumulation of small changes over time that (usually) make a plant or animal better suited for its environment. If one were to look at the environment as an independent, objective testing criteria, then you can talk about organisms that are best fit are those that score highly in the environment. For instance, orchids are tropical plants (for the most part), and if there were to be a shift in the climate and Brazil were to become a colder, dryer place, then orchids, a very successful class of plants in the Amazon rain forest today, would become less fit to live in the changed climate, and may ultimately be replaced by other plants that do very well in that environment.

The amazing thing about using an environment as an evaluation mechanism is that you cannot predict the way the organism will adapt. The way a species adapts is a product of its own genetic makeup and the actual circumstances surrounding it. For instance, Darwin observed on the Galapagos islands (a cluster of islands in the Pacific Ocean that is very far from other land) that there was originally only a very few species of a type of bird called the Finch on the island. By the time Darwin visited the island, he found many types of adaptations of the finch species to the diverse environments. Some finches had developed tougher beaks for breaking seeds, while others develop long thin beaks for harvesting small seeds from difficult to reach places. This adaptive radiation, where one species of plant or animal changes into many by adapting to new circumstances, is accomplished by virtue of genetic variability within the finch population.

In any group of finches, some will have slightly shorter and thicker beaks, while some will have slightly longer and thinner beaks. As long as there is no competitive advantage for having either a long thin or short thick beak, then beak size will stay within certain limits. Because on the Galapagos islands there were no other competing species of birds eating any of these types of seeds, those finches with slightly shorter- thicker beaks were able to take advantage of the seeds available with hard shells at a slightly better rate than those finches with longer- thinner beaks (and vice versa). This now allowed this pool of the 'same' type of finches to be better fit as two types of finches. Those finches best suited for eating thick-shelled seeds got better and better at eating thick-shelled seeds. The finches with shorter- thicker beaks (when compared to their peers) were better able to provide for their offspring, thereby making themselves more representative of the population. Ultimately, what happens is you now have two species that do not interbreed and natural genetic drift will cause them to look and act less and less alike. It is this adaptation to a given environment that is the power of evolution.

This brief outline of the concepts of evolution is meant to serve as an introduction, not as an in depth discussion of the theory of evolution. Any good University library will have many text devoted to creating a detailed understanding of these principles.

Conventional Problem Solving using Computers

Computers are wonderful tools. They never get bored, they can do the very same task over and over again without any mistakes, and they can do things thousands, and often times millions of times faster than a human can. The one big limitation to computers is that they are able to do ONLY what they are told to do. Getting a computer to think for itself is a job that many of the great scientists in this world are working on, but with very limited success.

All programs currently in use are those that have been written by humans. Humans (compared to computers) have very short attention spans, get bored easily, need to take coffee breaks, demand time with their families, must get sleep every night, and make mistakes. Computers that have been programmed by humans have some of the same limitations as humans, just manifested in different ways.

The current programming paradigm is to take a large problem, break it down into smaller and smaller pieces, until eventually you have pieces that individual humans can program. Keep in mind that all these classifications are made for humans by humans, and as such are subject to the frailties and faults of all humans. Conventional programming seeks to minimize variability and to maximize reproducibility. This approach has worked very well in the past, and has enabled humans to attain amazing goals. Computers were directly responsible for our being able to stand on the moon and to visit other celestial objects indirectly. These machines have enabled tremendous increases in productivity of workers in nearly every walk of life and have enabled greater efficiencies to be realized by minimizing waste and downtime.

There are, however, classes of problems that are not solvable by conventional computer programming. Computers by the nature of their programming, are supremely capable of repetitive tasks and as they get faster and faster, the type of tasks they are applied toward increase on a daily basis. But if the problem is so complicated that to test every possible solution to a complicated problem were to take every computer in the world, working together, millions of years, it becomes impractical to use computers to solve these types of problems. Problems with many variables that interact with one another in a non-linear fashion are typically solved by human experts who make judgment calls based on their personal experience and education. There have been efforts to capture this expert information on computer databases, but with mixed success. The best computer expert system is still not able to address a new situation with even a tiny fraction of the capability of a human expert. This approach fails miserably when there are no human experts available.

What is needed is a different programming approach that can find a good solution to problems with out having to search the entire range of possible answers. An approach that builds on the information gleaned from testing of past solutions in such a way that it is able to avoid exploring blind alleys. An approach has been developed called an evolutionary algorithm.

Evolutionary Programming Problem Solving

The concepts of Evolutionary Programming are the opposite to conventional programming in many ways. Evolutionary Algorithms (EAs) attempt to preserve the complexity and feedback interactions of the real world and works to embrace the whole problem in its entirety.

The EA paradigm is at its most powerful when used to address problems that are difficult or impossible to break down into meaningful parts that can be worked on by humans. The concepts of the EA parallel those of Darwinian evolution. The programmer creates an environment that reflects the properties of a problem to be solved that allows for the determination of relative fitness values of a population of possible solutions.

Each possible solution (in Darwinian evolution each possible solution is analogous to an individual finch on the Galapagos islands) is then tested in this environment (the finch is born, grows up and leaves the nest) and those most fit are the most likely to breed (the best suited finch is likely to have the most offspring). This cycle of fitness evaluation by testing against an environment can allow for the simultaneous testing of a great many variables that interact in a non- linear manner.

The EA approach has allowed programmers to achieve high quality solutions to problems that would otherwise be only addressable by human experts. EAs (one member of this fraternity is the Genetic Algorithm) have been applied in many different academic research areas with often impressive success.

The success of EAs in the non- academic setting has been less spectacular. This may be due in part to the type of problem that the EA is best suited for is the same type of problem most people would assume cannot be solved by a computer at all, and must rely on human experts.

This Web site is an effort to disseminate the academic know-how on the use and application of EAs in such a way that a layman can see the benefit of the approach. What we have attempted to do is develop a visual method of representing an EA and display the results of each generation in a visual manner.

The basic Visual EA is a sentence (called a "string" in computer jargon) that you, the user, can input. The order of the characters in the sentence is then randomized, and the EA's task is to evolve an individual that exactly matches the original string (goal) from that randomized initial population. The environment in this case is a world where the sentences that best match the goal are the most fit. These best strings are allowed to breed more often than the less fit (worst matching) strings, and some 'genetic drift' is added by a little mutation.

You can change the number of individuals in each population and the total number of generations for the evolutionary test. You can watch the ongoing evolution, because the best sentence of each generation is displayed for you as it happens.

We hope you enjoy this display (written in a new World Wide Web programming language called Java) and find the information contained within this site interesting and educational. If you have any questions or comments, please contact US.