Multithreaded Hybrid Genetic TSP Solver Files

Author: Pete Terlep

This is a multi-threaded, hybrid, genetic solver for the asymmetric
traveling salesman problem.

Here's a high-level overview of the theory of operation:
(The following assumes that the reader has a cursory understanding of the
traveling salesman problem)

GENES
Given n unique cities, there are n! possible ordered sets that each
represent a trip (formally a Hamiltonian Cycle). Each of these sets
can be represented genetically as an n-tuple of
(E.g. {A, D, C, B, E}  or {D, C, A, B, E}).
 
POPULATIONS
This solver is hard-coded to 4 multi-threaded populations. One population
performs one-point PMXs (partially-mapped crossover). Two populations
perform two-point PMXs. One population performs simulated annealing.
The size of each population can be manipulated in the Properties.java
file. The default is 500 as this tended to work well on my Core 2 Duo
machine with 4 GB RAM.

POPULATION MERGING
One can think of isolated populations as Galapagoses and merged
populations as a sort of Pangea. The way population merging works:
1)Populations go into isolation, run their respective crossover (or sim. annel.) 
and mutation operations. Populations attempt to find local optima.
2)Populations merge into Pangea. Pangea is the set of all n-tuple genes.
Pangea is shuffled and redivided into isolated populations. As an added
heuristic, each isolated population is "seeded" with the Pangea population
current best.

CROSSOVER
Genetic algorithms require two essential properties to be effective:
crossover and mutation. Since a single trip is an ordered set, simple
crossover operations cannot be employed since this would create duplicate cities 
in the child of any two parents. Rather, there are special crossover operations
that preserve partial ordering and rule out the possibility of duplicate or
absent cities in children. These types of crossovers are called partially-mapped
crossovers and are outside of the scope of this overview. One can work through
the code and/or read the literature on partially-mapped crossovers.

SIMULATED ANNEALING
The one population that performs simulated annealing continually swaps cities
in each gene until the gene improves or there is a timeout. The function
of combining simulated annealing provides a type of "intelligent mutation"
that only commits a mutation to a gene if there's improvement. This population's
main function is to add some diversity to state coverage within Pangea--this
theoretically encourages the genetic populations to diverge exploration
from local optima.

MUTATION
After a population performs crossover operations on its members, there is a small
chance of mutation. The mutation for this solver simply swaps two cities in a
gene if the gene has been selected for mutation. The mutation bias can be
tweaked in Properties.java. The default is .05

EVALUATION
The evaluation function is simple in that for each gene of cities, the total cost
of the trip is computed and associated with that gene.

FITNESS
Fitness levels are based upon gene evaluations on a logarithmic scale. I'll admit,
there's a few magic numbers in here for this purpose.

INPUT
At runtime, the program will ask for a TSP file which is basically a
whitespace-delimited asymmetric distance matrix. Here's an example of such a file:

5
0 3 1 4 2
4 0 6 1 4
1 2 0 6 5
6 3 1 0 8
4 1 9 3 0

Where the first line is the number of cities. Each entry indicates the distance
(or cost) from the ith city row to the jth city column. Each distance entry must
be an integer. The source code includes a few convenient examples for
5, 15, 30, and 100 cities. I generated the 100-city file from RANDOM.org. Each entry
is in the range {0, 20000} since the earth's diameter is 40000km. So, this
solver will theoretically work well on real-world city distances.

RUNNING THE SOLVER
Run the .jar file as:
java -jar TSP.jar
During runtime the program will ask for the path to your distance matrix file.

NOTES
There's a few bits of kludge mixed in here but I hope the reader will find this project
fairly navigable and fun to use. I was still learning the basics of multithreading when
I wrote this so please excuse any granularity missteps. Also, I did this for a school 
project and the utmost documentation and code guidelines were relaxed. 
This was supposed to be a much simpler project but I enjoyed working on it so much 
that it sort of evolved into a personal side project. I really enjoyed learning the 
intricacies of partially-mapped crossovers which is why the project evolved beyond a
simple school assignment. After that I thought it'd be fun
to tool with the Java multithreading libraries and add in some optimizing heuristics.
There are a few UML diagrams included that I created in UMLet that explain the operation 
of this solver pretty well. There's a compiled version of this software
in the dist folder but feel free to modify and tweak this as you please.