A Demonstration of the Genetic Algorithm
To launch the GA applet, click here:
Note: This applet requires Java 1.1.
Brief Instructions: You can control the applet using the menus. (If you are using a Macintosh, they might have been added to the menu bar at the top of the screen.) The red things are Eaters, which eat the plants (the green things). As generation follows generation, the Eaters might evolve to become better eaters. Try putting things into fast forward by setting the Speed to "Fastest". After a while, reduce the speed and see how the Eaters' behavior has changed.
More Information
"GA" is a little applet that demonstrates the genetic algorithm, in which methods analogous to the process of natural evolution are applied to solve problems on a computer. This "artificial evolution" uses reproduction, mutation, and genetic recombination to "evolve" a solution to a problem. The genetic algorithm is described fully by John Holland in his book, "Adaptation in Natural and Artificial Systems." More popular accounts can be found in the books "Complexity" by M. Mitchell Waldrop and "Artificial Life" by Steven Levy.
The genetic algorithm can be applied to many different types of problems, but GA uses it to evolve simulated "organisms" called Eaters in a simulated world that contains simulated plants for the Eaters to eat. I stress the word "simulated", but even that word really goes too far. GA is really just a kind of metaphor for natural evolution in the real world. You can judge for yourself the extent to which that metaphor might be valid.
When you first launch the applet, you will see a world containing 250 plants and 25 Eaters. The plants tend to grow in clumps. The Eaters will display random-looking, undirected behavior, but sometimes an Eater will eat a plant. (It does this merely my moving to the position occupied by the plant.) At the end of each year, a new world is produced, containing a new generation of Eaters. The new Eaters are produced as copies, with modification, of Eaters from the previous generation. The more plants that an Eater has eaten, the better its chances of producing "offspring" in the new generation. Differential reproduction, based on "fitness" defined as the number of plants eaten, would by itself tend to increase the average fitness of the population. The random modifications introduced during reproduction allow new behaviors to be tested and, if they turn out to be advantageous, to spread through the population in later generations. There are two types of modification: "mutation", in which random changes are introduced as an Eater is copied, and "crossover", in which a new Eater is made by combining parts of the genetic makeup of two Eaters from the previous generation.
This is all you really need to know to start playing with the program. The rest of this page contains the details you need in order to understand what is going on.
The Eaters' world is divided into little squares. Each square can hold an Eater or a plant, or it can be blank. A square cannot be occupied by two things at once. An Eater can "see" the single square just in front of it. (The front is the pointy end of the T-shaped Eater.) It can see one of four different things: an Eater, a plant, a blank space, or a wall. In addition to this external information, the Eater has an internal memory that contains a number between 0 and 15. This number is called the "state" of the Eater. At each time step, the Eater can perform one of the actions:
1. Move forward one square 2. Move backwards one square 3. Turn in place 90 degrees to the left 4. Turn in place 90 degrees to the right.It can also change its state, by changing the number in its memory. If it tries to move into a wall or onto a square that already contains another Eater, it will not be allowed to move; however, it can still change its state. If it moves onto a square containing a plant, it "eats" the plant and scores a point. Depending on menu settings, the plant might immediately grow back somewhere else. At the end of a year, the "fitness" of the Eater is the number of plants it has eaten PLUS ONE. (The 1 is added to avoid having a fitness of zero.)
Now, how does an Eater decide what to do on each turn? It bases its decision on two things, its current state and the item that it sees in front of it. Its behavior is completely determined by a set of rules that tell it what to do for each possible combination of current state and item-in-view. All the Eater does is follow its rules. The rules differ from one Eater to another. In fact, the Eater's rules, which completely determine the behavior of the Eater, make up the Eater's genetic endowment, what we will call its "chromosome". The chromosome consists of 64 rules (one for each combination of one of 16 states and one of four items-in-view). Each rule specifies two things: an action and a new state. The chromosome can be considered to be just a list of 128 numbers.
Here is what happens at the end of a year: The average fitness of the current population is computed. A new population is created by making copies of the Eaters (that is, of the chromosomes) in the current population. An Eater's chance of being copied depends on its fitness. Eaters that have fitness much below average are likely not to be reproduced at all (although they always have some chance of reproduction.) Eaters with high fitness are likely to be copied several times. Then a mutation operation is applied: Each of the 128 numbers in each chromosome has a chance of being randomly changed. This chance is 1% by default and is controlled by the Mutation Probability submenu of the World Design menu. Finally, a crossover operation is performed: Pairs of Eaters in the new population are chosen at random and have a certain probability of being "crossed over". This probability is 75% by default and is controlled by the Crossover Probability submenu of the World Design menu. Crossover here means that the chromosomes exchange some genetic material; a random position between 1 and 128 is chosen and all data on the chromosomes after that position are swapped between the two chromosomes.
Note that the default mutation rate, 1%, is already quite high since every chromosome is likely to have at least one of its rules modified. In fact, I have found that setting the mutation rate to 0.25% seems to give longer-term, more stable development.
The new Eaters are placed in a new world with a new set of plants. They are initially in state number zero and are facing in random directions.
The average fitness and the highest individual fitness for the previous year are displayed at the bottom of the "World" window. This information is also--sometimes--added to a "Statistics" window. (Information is displayed in this window every year for the first 100 years, then every tenth year up to the 1000-th year, and every 100-th year after that. Also, if a new high average score is achieved in a given year, data for that year is added to the Summary Statistics window. New high average scores are starred in this window.) After the first 100 years, this window also shows the "average average score" for the previous 100 years.
Various aspects of the world are controlled using the various submenus of the World Design menu. Mutation Probability and Crossover Probability were mentioned above. Most of the other items in this menu are either self-explanatory or best left to discovery through exploration. Whenever you make a change in this menu, it becomes operative at first opportunity. For example, if you change the setting of the "Plants Grow" submenu, it will have an immediate effect on the location where plants grow back after begin eaten. The Approximate population submenu, on the other hand, will come into effect at the end of the current year.
The "Start from Scratch" command in the Control menu will start over with a new, randomly generated population of Eaters. (This does NOT change any of the settings in the World Design menu back to their default values.)
The five speed settings in the Speed menu should be fairly obvious. Note that speed number 1 is designed to make the years go by as quickly as possible. A good technique is to let the program run in speed 1 until it looks from the average scores like something interesting has happened. You can then switch back to speed 2 or 3 and try to see what new behavior the Eaters have "learned".
The GA applet is a straightforward translation of an older program for Macintosh computers, which is still available for download from my home page.
You can see the source code for the GA applet if you want, but it's uncommented and it bears some marks of its Macintosh Pascal origins (such as not using the zero-th position in some arrays).
David Eck
eck@hws.edu
http://math.hws.edu/eck/
February 24, 2001