The traveling salesman problem

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 double distance(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.

abstract Chromosome createSampleChromosome(Object an_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

Chromosome findOptimalPath(Object an_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).

Literature

Copyright © 2004 - 2012 Audrius Meskauskas and Klaus Meffert, GNU free documentation license