Genetic Algorithms

Elementary examples:

You read the book. You saw the movie. Now try the applet.

Eaters vs. plants: In this simulation the eaters evolve, with the ones who are good at consuming the most plants getting the best chance of reproducing.

Model the biomorph: In some GAs, the goal is to evolve the best solution to solve a specific problem. In this applet, however, the end result is already known. The task for this GA is instead to evolve a solver that will best match the known goal.

Highest point of a landscape: In this applet, "bugs" attempt to find the highest point in a fractal landscape. Recall that a fractal is not suited to evaluation by normal analytical methods of calculus, so genetic algorithms are a practical way of solving this problem. (Hint: a larger population will solve the problem more exactly, but it takes much longer to run. Because this applet does take a long time, it opens in a separate window.) A similar applet--Finding the Maximum of a Function--works almost the same way, but without the "bugs."

Traveling Salesman problem (TSP):

This introductory applet allows the mutation speed, the number of cities and the number of solvers (a.k.a "Pop Size") for the Traveling Salesman problem. Try changing both the mutation % and the population size. Note how the solution changes: visually inspect the result. Does it appear to be optimal?

The traveling salesman problem, or TSP for short, is easy to state: given a number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. The simplicity of the statement of the problem is deceptive--the TSP is one of the most intensely studied problems in computational mathematics and yet no effective solution method is known for the general case. Indeed, the resolution of the TSP would settle the P versus NP problem and fetch a $1,000,000 prize from the Clay Mathematics Institute.

Numerous algorithms have been created to solve the TSP. The most obvious one is the brute-force approach, where all possible combinations of routes are tested. However, this is also the most compute-intensive, so other algorithms have been developed [ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ].

The TSP has numerous applications other than travelling logistics. These pages [ 1 | 2 | 3 ] document many of them.

The Seven Bridges of Konigsberg:

This is an old puzzle that was solved by the famous mathematician Leonhard Euler in 1735. This is a very similar problem to the TSP, and is often assigned to computer science students as homework. The Seven Bridges problem spawned the field of graph theory, which is a subset of topology. It is also very amenable to solution by genetic algorithms.

Miscellaneous GAs:

Manna Mouse: Among interactive artificial life simulations, Manna Mouse is uniquely simple: a creature's genome encodes its location on the display area. This simplicity allows us to see interesting dynamics that are often inaccessible. With your mouse you paint manna--the reward function. By visualizing the fitness landscape, you can quickly build intuitions about evolution.

Evolving Floys are social, territorial, evolving artificial life creatures. They belong to the flocking Alife creatures variety, sharing with them the social tendency to stick together, and the lifelike emergent behavior which is based on a few simple, local rules. They differ from most other flocking Alife animals by having the following properties:

Echo is a simulation tool developed to investigate mechanisms which regulate diversity and information-processing in systems comprised of many interacting adaptive agents, or complex adaptive systems.

Maze Solver: finds a path from the origin point of a grid to a target.

Evolution of a Prism Lens: The goal is to optimise the shape of lens in such a way that parallel rays falling into the lens will focus in one single point.