org.jgap.impl.salesman
Class Salesman

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

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

TravellingSalesman

public abstract class Salesman
extends java.lang.Object
implements java.io.Serializable

The class solves the travelling salesman problem. The traveling salesman problem, or TSP for short, is this: 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.)

Since:

2.0

See Also:

• 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.
• Sushil J. Louis & Gong Li (explanatory material)
• TPS web site

, Serialized Form

Constructor Summary

Salesman()

Method Summary

Configuration	createConfiguration(java.lang.Object a_initial_data) Create a configuration.
FitnessFunction	createFitnessFunction(java.lang.Object a_initial_data) Return the fitness function to use.
abstract IChromosome	createSampleChromosome(java.lang.Object a_initial_data) Override this method to create a single sample chromosome, representing a list of "cities".
abstract double	distance(Gene a_from, Gene a_to) Override this method to compute the distance between "cities", indicated by these two given genes.
IChromosome	findOptimalPath(java.lang.Object a_initial_data) Executes the genetic algorithm to determine the optimal path between the cities.
Configuration	getConfiguration()
int	getMaxEvolution()
int	getPopulationSize()
int	getStartOffset() Gets a number of genes at the start of chromosome, that are excluded from the swapping.
void	setMaxEvolution(int a_maxEvolution) Set the maximal number of iterations for population to evolve (default 512).
void	setPopulationSize(int a_populationSize) Set an population size for this solution (default 512)
void	setStartOffset(int a_offset) Sets a number of genes at the start of chromosome, that are excluded from the swapping.

Methods inherited from class java.lang.Object

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

Constructor Detail

Salesman

public Salesman()

Method Detail

distance

public abstract double distance(Gene a_from,
                                Gene a_to)

Override this method to compute the distance between "cities", indicated by these two given genes. The algorithm is not dependent on the used type of genes.

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

createSampleChromosome

public abstract IChromosome createSampleChromosome(java.lang.Object a_initial_data)

Override this method to create a single sample chromosome, representing a list of "cities". Each gene corresponds a single "city" and can appear only once. By default, the first gene corresponds a "city" where the salesman starts the journey. It never changes its position. This can be changed by setting other start offset with setStartOffset( ). Other genes will be shuffled to create the initial random population.

Parameters:

a_initial_data - the same object as was passed to findOptimalPath. It can be used to specify the task more precisely if the class is used for solving multiple tasks

Returns:

a sample chromosome

Since:

2.0

createFitnessFunction

public FitnessFunction createFitnessFunction(java.lang.Object a_initial_data)

Return the fitness function to use.

Parameters:

a_initial_data - the same object as was passed to findOptimalPath. It can be used to specify the task more precisely if the class is used for solving multiple tasks

Returns:

an applicable fitness function

Since:

2.0

createConfiguration

public Configuration createConfiguration(java.lang.Object a_initial_data)
                                  throws InvalidConfigurationException

Create a configuration. The configuration should not contain operators for odrinary crossover and mutations, as they make chromosoms invalid in this task. The special operators SwappingMutationOperator and GreedyCrossober should be used instead.

Parameters:

a_initial_data - the same object as was passed to findOptimalPath. It can be used to specify the task more precisely if the class is used for solving multiple tasks

Returns:

created configuration

Throws:

InvalidConfigurationException

Since:

2.0

getMaxEvolution

public int getMaxEvolution()

Returns:

maximal number of iterations for population to evolve

Since:

2.0

setMaxEvolution

public void setMaxEvolution(int a_maxEvolution)

Set the maximal number of iterations for population to evolve (default 512).

Parameters:

a_maxEvolution - sic

Since:

2.0

getPopulationSize

public int getPopulationSize()

Returns:

population size for this solution

Since:

2.0

setPopulationSize

public void setPopulationSize(int a_populationSize)

Set an population size for this solution (default 512)

Parameters:

a_populationSize - sic

Since:

2.0

findOptimalPath

public IChromosome findOptimalPath(java.lang.Object a_initial_data)
                            throws java.lang.Exception

Executes the genetic algorithm to determine the optimal path between the cities.

Parameters:

a_initial_data - can be a record with fields, specifying the task more precisely if the class is used to solve multiple tasks. It is passed to createFitnessFunction, createSampleChromosome and createConfiguration

Returns:

chromosome representing the optimal path between cities

Throws:

java.lang.Exception

Since:

2.0

setStartOffset

public void setStartOffset(int a_offset)

Sets a number of genes at the start of chromosome, that are excluded from the swapping. In the Salesman task, the first city in the list should (where the salesman leaves from) probably should not change as it is part of the list. The default value is 1.

Parameters:

a_offset - start offset for chromosome

Since:

2.0

getStartOffset

public int getStartOffset()

Gets a number of genes at the start of chromosome, that are excluded from the swapping. In the Salesman task, the first city in the list should (where the salesman leaves from) probably should not change as it is part of the list. The default value is 1.

Returns:

start offset for chromosome

Since:

2.0

getConfiguration

public Configuration getConfiguration()