The traveling salesman problem is the following: given a finite 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. This task has deserved a serious attention from mathematicians, and a lot of literature is available.

The number of the possible routes increases rapidly when increasing the number of cities to visit, and the method of force become inappropriate. Genetic methods cannot find surely the best solution, but they can find the comparatively good solution in an acceptable time. JGAP implements the solution of this task using swap mutations and greedy crossover algorithm, as it is described by (Grefenstette et al, 1985).

To solve this task with JGAP, you must define the specific of your task by deriving class from org.jgap.impl.Salesman.

The most critical information you need to specify is how to
measure the travel cost between the two cities. JGAP
uses subclasses of its *Gene *to represent a city. For
example, if you use the *IntegerGene *to store the
number-city reference then you can query some local structure of
even remote database to get the travel costs or distance between
the cities. To specify the needed algorithm, you must override
the method Salesman.**distance**:

abstract doubledistance(Gene a_from, Gene a_to)

You also need to specify the cities we need to visit, and from
which city the journey should begin. This is done by representing
a "sample solution". This solution must be formally
correct, but need not be even close to the optimal one. The
sample solution must be presented in as a *Chromosome*
that can be easily constructed from the gene array.

abstractChromosomecreateSampleChromosome(Objectan_initial_data)

For more precise control on the solution you may also need to
override several other methods and use the parameter *an_initial_data.
*Read the org.jgap.impl.salesman.Salesman
documentation for details.

After you create a working descendant of the *Salesman*
by overriding the two mentioned methods, the task solution can be
obtained just by calling

ChromosomefindOptimalPath(Objectan_initial_data)

The parameter *an_initial_data *is later passed to **createSampleChromosome.
**This is how you can solve multiple tasks with the same class,
creating the different sample solution from the data, stored in
your object.

The result is also returned in a form of *Chromosome*,
where you can easily access the individual genes.

You can actually do more, but other details are obvious from the code documentation page. If you have some comments, questions or suggestions for this implementation, please submit a bug or rfe (feature request).

See also the complete java source code for a simple example, where the distance between the cities is equal to the absolute difference between they given numbers.

For an overview of genetic operators suitable for TSP-like problems, see Permutational Operators, a kind contribution of Laszlo Illyes (Sapientia University, Romania).

J. Grefenstette, R. Gopal, R. Rosmaita,
and D. Gucht. *Genetic algorithms for the traveling
salesman problem*. In Proceedings of the Second
International Conference on Genetic Algorithms. Lawrence
Eribaum Associates, Mahwah, NJ, 1985.

J. L Sushil, L. Gong (explanatory material on the web)

**Copyright © 2004 - 2015 Audrius Meskauskas
and Dr. Meffert Online Marketing,
GNU free documentation license**