examples.salesman
Class TravellingSalesman

java.lang.Object
  org.jgap.impl.salesman.Salesman
      examples.salesman.TravellingSalesman

All Implemented Interfaces:

java.io.Serializable

public class TravellingSalesman
extends Salesman

Explains how to use JGAP extensions, needed to solve the task group, known as the Problem of the travelling salesman. The extensions are defined in org.jgap.impl.salesman

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.

Also see

• J. Grefenstette, R. Gopal, R. Rosmaita, and D. Gucht. Genetic algorithms for the traveling salesman problem. In Proceedings of the Second International Conference on Genetice Algorithms. Lawrence Eribaum Associates, Mahwah, NJ, 1985.
• Sushil J. Louis & Gong Li (very clear explanatory material)
• Travelling salesman web site

This simple test and example shows how to use the Salesman class. The distance between the cities is assumed to be equal to the difference of the assigned numbers. So, the optimal solution is obviously 1 2 3 4 ... n or reverse, but the system does not know this. To get the useful application, you need to override at least the distance function. Also, it is recommended to define a new type of gene, corresponding the data about your "city". For example, it can contain the city X and Y co-ordinates, used by the distance function.

Since:

2.0

See Also:

Serialized Form

Field Summary

static int	CITIES The number of cities to visit
static int[][]	CITYARRAY

Constructor Summary

TravellingSalesman()

Method Summary

IChromosome	createSampleChromosome(java.lang.Object a_initial_data) Create an array of the given number of integer genes.
double	distance(Gene a_from, Gene a_to) Distance is equal to the difference between city numbers, except the distance between the last and first cities that is equal to 1.
static void	main(java.lang.String[] args) Solve a sample task with the number of cities, defined in a CITIES constant.

Methods inherited from class org.jgap.impl.salesman.Salesman

createConfiguration, createFitnessFunction, findOptimalPath, getConfiguration, getMaxEvolution, getPopulationSize, getStartOffset, setMaxEvolution, setPopulationSize, setStartOffset

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

CITIES

public static final int CITIES

The number of cities to visit

See Also:

Constant Field Values

CITYARRAY

public static final int[][] CITYARRAY

Constructor Detail

TravellingSalesman

public TravellingSalesman()

Method Detail

createSampleChromosome

public IChromosome createSampleChromosome(java.lang.Object a_initial_data)

Create an array of the given number of integer genes. The first gene is always 0, this is the city where the salesman starts the journey.

Specified by:

createSampleChromosome in class Salesman

Parameters:

a_initial_data - ignored

Returns:

Chromosome

Since:

2.0

distance

public double distance(Gene a_from,
                       Gene a_to)

Distance is equal to the difference between city numbers, except the distance between the last and first cities that is equal to 1. In this way, we ensure that the optimal solution is 0 1 2 3 .. n - easy to check.

Specified by:

distance in class Salesman

Parameters:

a_from - first gene, representing a city

a_to - second gene, representing a city

Returns:

the distance between two cities represented as genes

Since:

2.0

main

public static void main(java.lang.String[] args)

Solve a sample task with the number of cities, defined in a CITIES constant. Print the known optimal way, sample chromosome and found solution.

Parameters:

args - not relevant here

Since:

2.0