- Too see this applet, you must have a JAVA enabled browser -
Clicktoggles the cell state. Ctrl+Click changes the target. Shift+Click adds a bomb.
Genetic Algorithms (GA) are based on an evolution of random tries by 'individuals', not on logic as regular algorithms. It is a computer simulation of Darwins theories. Though the whole prosess is built on randomness, the effect is not. It seeks towards the 'solution'
The 'God' in a GA is the Objective function, which determines fitness of each individual. Only the better fit 'individuals' survive to breed. Children are bred by combining the traits of the 2 parents. Traits are codings the domain knowledge, i.e. the genes. The Maze Solver knows 4 directions (N)orth, (S)outh, (E)ast and (W)est. A series of these combine to make a path. The path is evaluated, based on how close the end-point is to the target.
Each cycle in the process of: evaluation, selecting survivors, breeding, evaluation, etc. is called a generation. The GA continues the iteration of generations until the goal is found or some other end criterea occurs.
Mutation helps prevent a degenerate population, which tends to settle prematurely at a non-optimum solution.
Optimization can improve both the GAs speed and capability to solve problems.
"GAs do not find the best solution, they find the first". (unknown)
Maze solver is a configurable genetic algorithm.
It does not find the optimal path, but usually finds a path to the target.
Each gene consist of a string of directions ('N', 'E', 'S' & 'W').
The solver starts at coordinate (0,0) and tries to step in the first direction.
If the cell is free, the step is successful, and the current standing point is updated.
Then it repeats the same for the rest of the gene's values.
The standing point after all steps is called the end-point.
The genes fitness is the negative of the distance between the end-point and the maze's target point, i.e. the closer the end-point is to the target point, the better the fitness.
A Maze Solvers generation step consists of
- Select survivors, i.e. the genes with the highest fitness
- Add new (random) genes to survival population
- Cross survivor population to create the next generation1 .
- Sort according to weight (only to help the survivor selection)
- Show best fit genes (only to see how the GA evaluates)
- Resolve Crowding3
- Mutate Maze4 if option is chosen
1Best fit genes are over-represented in the mother population.
New in version 2.1.4
A dead-end detection is added. If the best fitness is the same over several runs, the end-point is marked as a dead-end by placing a bomb on the cell.
To start the Maze Solver, press 'Start'. (If nothing happens, the starting position, at the upper left corner, is probably blocked. Free some cells, so it is possible for the genes to 'escape' the starting point).
The Maze Solver attempts to find the path to the target (red dot). The genes are displayed alternate green-blue as they are evaluated. If a gene encounters a bomb (light red dots), it is killed. The target (red dot) can be changed by Ctrl+Click. New bombs (light red dots) can be added by Shift+Click
The maze pattern is generated randomly. You can adjust the number of blocked and free cells by changing the blockRatio. Click toggles the cell state between blocked-free. 'Regular' mazes must be built manually.
After a run is completed, the 3 best fit genes are displayed.
The GA completes when either the target (red dot) is encountered or max number of generation steps is reached.
Solving a maze is easy from above. Here's aMaze applet, by Paul Falstad, that lets you try to solve a Maze at ground level.
Resizing the Maze
You can resize the maze by adjusting the row and column counts. If so, you should also adjust the gene size, which determines the number of steps in the path. A rule of thumb is,
Gene Size = 2 * (Row Count + Column Count)
Note that if you reduce the maze size, the target point may fall outside the maze. If this happens, use Ctrl+Click to reposition the target.
Keep ratios in the range (0.0 <= r <= 1.0).
Other parameters must be positive integers, except lockCount which can also equal 0.
Optimization tunes the GA to a specific problem, i.e. the Maze. The Maze Solver applies a number of optimization techniques, e.g. loop truncation and redundant step elimination. Optimization is not necessarily confined to the step indicated above. Disabling optimization leaves the 'pure' GA.
Maze Solver 2.0 is compiled using JDK 1.1, and tested using Netscape 4.0 for WindowsNT. If you are using an older browser or a browser incompatible with JDK 1.1, this version will not load/run correctly.
Please send an e-mail if you detect other bugs. Remember to include you browser type and version and the platform (Operating System) you are using.
Solving a maze is easy from above. Here's a Maze applet, by Paul Falstad, that lets you try to solve a Maze at ground level.
Genetic Algorithms are derived from Darwins theory of evolution. Check out Web Sites in General Anthropology, Evolution, and Genetics for more information. The works of Charles Darwin are also available on-line.
'Advantages of Using G.A.s for Game Problems' and more, visit Genetic Algorithms and Games Theory.
Traveling Salesman Solver, by Thomas Pederson., is a GA for the Travelling Salesman Problem.
A Fast TSP Solver from Hitachi.
"The Hitch-Hiker's Guide to Evolutionary Computation". FTP to the FAQ for comp.ai.genetic.
Any comments or suggestions are welcomed !
(Here's a review of Maze Solver v 1.1 in the 1st of September 1996 edition of JavaWorld).
Contact me through: firstname.lastname@example.org
This chat client is intended for chat's about the MazeSolver and GAs
You are visitor number since August 15, 1996
Last updated Dec 02, 1999
You are visitor number since August 15, 1996