- Too see this applet, you must have a JAVA enabled browser -

Click toggles the cell state. Ctrl+Click changes the target. Shift+Click adds a bomb.

Chat Explain

Genetic Algorithms

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)

About - Maze Solver

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 generation¹ . 
Mutate 
'Optimize'² 
Evaluate 
Sort according to weight (only to help the survivor selection) 
Show best fit genes (only to see how the GA evaluates) 
Resolve Crowding³ 
Mutate Maze⁴ if option is chosen

^{1 Best fit genes are over-represented in the mother population.

² A number of optimizations are applied

³ Crowding occurs in the vicinity of the best-fit gene's end-point.

⁴ Maze mutation is activated manually, but the mutation parameters are fixed.
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.
The Maze
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.

3rd best gene - in yellow

2nd best gene - in red

BEST FIT gene - in black

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 a Maze applet, by Paul Falstad, that lets you try to solve a Maze at ground level.

Configuration

Stop the Maze Solver if it is running.
Configure Maze

- Clicking on a cell toggles the cell state.

- Clicking on a cell while holding down the Control key changes the target point

- Clicking on a cell while holding down the Shift key adds a bomb (cannot be removed)

(Cells can be configured while the Maze Solver is running !)
Configure Parameters

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.

Parameters
Keep ratios in the range (0.0 <= r <= 1.0).

Other parameters must be positive integers, except lockCount which can also equal 0.

Optimize - If checked, optimization is applied
Auto Mutate Maze - If checked, Maze will Auto mutate
Columns - Number of columns in Maze. Range [1,N]. (Resizing the Maze)
Rows - Number of rows in Maze. Range [1,N]. (Resizing the Maze)
Block Ratio - Ratio of cells blocked when maze is randomized.
Cross Scheme - Determines how 2 genes are crossed.

Random: Select randomly one of the other cross schemes.
Cut: Cut 2 genes at a random index. Combine the parts.
Insert Section: Insert a random section from one gene into another.
Truncate Section: Remove a random section from one gene, append steps from the other.
Merge: Combine the parent genes stepwise.

Generation Steps - Max number of generations to iterate the algorithm. Range [1,N].
Population Size - Number of strings in gene pool. Range [1,N].
Gene Size - Number of steps in each gene. Range [1,N]. (Resizing the Maze)
Survival Ratio - Ratio of genes surviving each generation steps. Range [0.0 <= ratio <= 1.0].
Population Mutation Ratio - Ratio of genes mutating each generation step. Range [0.0 <= ratio <= 1.0].
Gene Mutation Ratio - Ratio of a mutating gene's values randomized. Range [0.0 <= ratio <= 1.0].
New Gene Ratio - Ratio of new (random) genes added each generation step. Range [0.0 <= ratio <= 1.0].
Lock Count - Number of best fit genes not subject to mutation or other alterations. Range [0,N].

Maze Solver uses some parameters internally that cannot be configured:

Best-fit gene over-representation = on

The best fit genes are over-represented in the 'mother' population, i.e. the group of genes which are crossed to produce the next generation genes.

Best fit gene - 3 extra instances

2nd best gene - 2 extra instances

3rd best gene - 1 extra instance

Note: The extra instances are only used as a base for crossing.
crowding radius = 1.5
The distance from a gene's end point

to the end point of the best fit gene.

A value of 1.5 hits all genes adjacent to the best fit gene.

Genes within this radius are forced to mutate.

(Note: locked genes never mutate).

Included to help gene pool from becoming degenerate.
Maze Mutation settings
Auto mutation of the maze is activated manually, but the mutation rules/parameters are fixed.

If activated, the following parameters apply to the Maze mutation

Maze is mutated at the end of every generation step.
5% of the maze cells are mutated.
30% of mutated cells are blocked (70% are freed)

Dead-end detection delay = 4 generations
If the best fitness does not progress within the number of generations in the delay, the end point of the best-fit gene is marked as a bomb. Bombs kill genes. This helps the algorithm choose new paths.

Optimization
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.
Known Bugs
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.

Bombs will sometimes not kill the chromosome hitting it. This is a bug, but due to the unpredictable nature of GAs, this can result in beneficial results.
Locked genes are sometimes mutated. This may cause the best fit to change. Again, this sometimes helps progressing the GA towards the solution.
The GA sometimes just halts without any reason. Try restarting your browser if this happens.
If the maze size is reduced, the target may be positioned outside the maze area. If this happens, use Ctrl+Click to reposition the target.

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.
More Information
Some indexes

The Genetic Algorithms Archive
Yahoo! - Science:Computer Science:Algorithms:Genetic Algorithms
Nova Genetica
Applets for Neural Networks and Artificial Life covers GAs and other areas.
Zooland. "The Artificial Life Resource"

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: arild@beteco.com

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}