It can be downloaded here: GA.tar.gz

What follows is taken directly from the included readme.txt.

This program attempts to solve the Travelling Salesman problem using

a Genetic Algorithm approach.

The basic sequence of events is as follows (omitting special cases and

display code of any kind);

iteration = 0;

while( iteration < maxGenerations ){

//Breed

Perform ERO on quads from top half of ‘generation’.

//Mutate

Randomly select ‘n’ children{

For each child{

Randomly swap city positions in its genome ‘X’ times.

}

}

//Sort the generation by path length (shortest first)

generation.sort();

if( generation.best not changed in X generations )

exit(done)

iteration++;

}

If the ‘–attempt_autocorrection’ (or -ac) flag is set upon starting the

program, the following sequence is executed immediately following the

mutate stage;

Randomly select ‘n’ children{

For each child{

Randomly swap city positions in its genome ‘X’ times.

}

}

In this implementation, genes are stored as array offsets, allowing very

fast manipulation of data without extensive memory access.

Additionally, this allows modifications to the agents to be made without

details on the search space, allowing very generic representations of

agents.

Edge Recombination is used to breed new agent sequences from a

pair of parents. This has the advantage of only creating offspring

which are very similar to their parents, keeping ‘good’ sequences in the

gene pool and allowing them to spread to other agents genome in the next

breeding cycle.

The Edge Recombination Operator (ERO) is defined thus;

Generate adjacency matrix for their genome.

}

Combine the matrices to one, removing any duplicated entries.

Start from a parent‘s first point.

Remove all instances of the current point from the matrix

While( Matrix not empty ){

if( Points exist on this row )

Select next point from matrix.

else

Choose a random point on the matrix.

Remove all instances of the current point from the matrix

}

Return new child( from points );

Selection is simple, the entire generation is ordered by how close to

zero they are, and the bottom half are removed. The top half then breed

with their ‘rightmost’ neighbours, stepping twice for each breed

( 1&2&3&4, 3&4&5&6, 4&5&6&7, etc. ) and populate the generation with

pairs of children.

Once they have bred, the breeders then move into the next generation

themselves, such that they can persist unless better candidates are

found.

The algorithm will exit if the best solution has not changed in a set

number of generations, as determined by the –stagnate (or -st)

parameter.

While this is not a brilliant metric for completion, it works most of

the time as the GA tends to plateu after a while as the probability of

it finding a better solution reduces the closer it gets to the perfect

route.

BUILDING:

With javac and javadoc on your PATH, simply calling;

make

which will generate both the binaries and the java documentation in

./bin and ./docs respectively.

To perform a clean build;

make clean && make

Logs of example runs can be found in ./logs, and are stored such

that the short parameter names follow their values; ie.

150 agents, 25 cities = 150a25c.txt

300 agents, 100 cities = 300a25c.txt

Logs are in CSV with the column order of:

Generation

Best Length

Worst Length

Average Length

SteveScore Best

SteveScore Worst

SteveScore Average

[–width=X | -w=X]

[–height=X | -h=X]

[–agents=X | -a=X]

[–cities=X | -c=X]

[–mutate=X | -m=X]

[–mutate_factor=X | -f=X]

[–simple | -s]

[–stagnate=X | -st=X]

[–noreturn | -nr]

[–stevescore | -ss]

[–show_worst | -b]

[–seed=X | -se=X]

[–manual | -e]

[–log=FILE | -l=FILE]

[–attempt_autocorrection | -ac]

[–help]

–width=X | -w=X

Sets the width of the search space to X.

–height=X | -h=X

Sets the height of the search space to X.

–agents=X | -a=X

Sets the number of agents in each generation to X.

–cities=X | -c=X

Sets the number of cities to pathfind through.

–mutate=X | -m=X

Sets the number of agents to run mutations on.

–mutate_factor=X | -f=X

Sets the number of mutations to occur in a mutated agent.

–stagnate=X | -st=X

Will halt the GA after no better route is found after X generations.

–noreturn | -nr

Performs calculations without a return path – gives open-ended routes.

–stevescore | -ss

Displays the scores in ‘steve’ format, for benchmarking purposes.

–simple | -s

Uses simple random mutation rather than edge recombination breeding.

–show_worst | -b

Displays the worst path in red on the search space window.

–seed | -se=X

Sets the random seed for city position generation.

–manual | -e

Allows you to tweak the best route produced for each generation.

‘swap [a] [b]’ swaps two points in the tour array, and

‘skip [generations]’ skips edits until ‘n’ generations have passed.

–attempt_autocorrection | -ac

Attempts to reduce the number of small, crossed over routes by

an additional form of mutation. This takes the form of selectively swapping

the points in edges with very short lengths.

This uses the mutate factor to determine where to start reassembling

edges in the generation (distance from best).

–log | -l

Sets the log file and starts logging to that file

–help

Prints this help.