| java.lang.Object
 org.jgap.impl.salesman.Salesman
examples.salesman.TravellingSalesman
| TravellingSalesman | | public class TravellingSalesman extends Salesman (Code) | | 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 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.
author:
Audrius Meskauskas
since:
2.0 |
| Field Summary | |
| final public static int | CITIES
|
| Method Summary | |
| public IChromosome | createSampleChromosome(Object a_initial_data)
Create an array of the given number of integer genes. | | 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. | | public static void | main(String[] args)
Solve a sample task with the number of cities, defined in a CITIES
constant. |
| CITIES | | final public static int CITIES(Code) | | The number of cities to visit
|
| createSampleChromosome | | public IChromosome createSampleChromosome(Object a_initial_data)(Code) | | 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.
Parameters:
a_initial_data - ignored Chromosome
author:
Audrius Meskauskas
since:
2.0 |
| distance | | public double distance(Gene a_from, Gene a_to)(Code) | | 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.
Parameters:
a_from - first gene, representing a city
Parameters:
a_to - second gene, representing a city the distance between two cities represented as genes
author:
Audrius Meskauskas
since:
2.0 |
| main | | public static void main(String[] args)(Code) | | 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
author:
Audrius Meskauskas
since:
2.0 |
|
|