The goal is to find the shortest cycle in a complete graph of N nodes. The nodes
represent cities that are visited by a salesman.
Evolution Strategy Theory
Travelling Salesman Problem - Problem Info
The salesman has to visit n cities and every city shall only be visited once. The postions of
the n cities are given and fixed. The salesman is looking for the shortest path on his tour
through all cities.
The cities are numbered from 1 through n. A vector containig a permutation of the numbers
from 1 through n is created and interpreted as the sequence the cities are visited. To close
the salesmans path, the last city (i.e. the number at vector position n) is connected with
the first on (number at vector postion 1). The salesman will have to find the permutation of
numbers from 1 through n, that the length of the path associated with this permutation becomes
minimal.
chromosome (genotype repesentation)
The object-parameters contain the permutation of numbers from 1 through n.
As the search-space (permutations) is discrete, a specific mutation operator is defined.
It creates a new permutation by swapping two numbers of the permutation. The numbers may
only be swapped if they cities associated with the numbers lie within a distance d to each
other. The strategy-parameters contain these distances. The distance found with the first
object-parameter chosen, will be used and adopted after being swapped: by random decision
it will be either increased by 10% or decreased by 10%. The distance of the 'swap-partner'
will not be changed.
The cities positions are randomly generated when the applet is initialized (within [150,150])
and the distances (from all to all cities) are precalculted.
//9 cities (initial settings)
double object_parameters[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
double strategy_parameters[] = { 100,100,100,100,100,100,100,100,100 };
drawing the chromsome (phenotype representation)
Simply draw the cities and draw the path given by the permutation.
applet parameters