TSP

From JCLEC wiki
Jump to: navigation, search

The travelling salesman problem (TSP) is a combinatorial optimization problem studied in operations research and computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

Graph.jpg

Example

Download and run the travelling salesman problem

java -jar jclec4-tutorial.jar TSP.cfg

Output

Generation 1000 Report

Best individual: OrderArrayIndividual {genotype = (36 0 21 30 17 44 31 48 43 15 28 1 6 41 29 22 19 33 34 35 38 39 37 23 47 45 25 46 12
                 13 51 9 8 40 2 16 20 49 5 3 24 11 27 26 10 50 32 42 7 18 14 4), fitness = net.sf.jclec.fitness.SimpleValueFitness@f35f44e[value=9482.023516170919]}
Worst individual: OrderArrayIndividual {genotype = (36 0 21 30 17 44 31 48 43 15 28 1 6 41 29 22 19 33 34 35 38 39 37 23 47 45 25 46 12
                 13 51 9 10 40 2 16 20 49 5 3 24 11 27 26 8 50 32 42 7 18 14 4), fitness = net.sf.jclec.fitness.SimpleValueFitness@2658dd2d[value=12737.531381147648]}
Median individual: OrderArrayIndividual {genotype = (36 0 21 30 17 44 31 48 43 15 28 1 6 41 29 22 19 33 34 35 38 39 37 23 47 45 25 46 12
                 13 51 9 8 40 2 16 20 49 5 3 24 11 27 26 10 50 32 42 7 18 14 4), fitness = net.sf.jclec.fitness.SimpleValueFitness@302a0a5[value=9482.023516170919]}

Average fitness = 9763.69763
Fitness variance = 457183.97999

The ouput shows the best, worst and median individual from the population at generation 1000. The genotype shows the path followed from the starting city to the others.

For further information see the TSP Wiki