com.softtechdesign.ga.examples
Class GASalesman
com.softtechdesign.ga.examples.GASalesman
- public class GASalesman
Traveling salesman problem. A salesman has to travel to N different cities. In what
sequence should he visit each city to minimize the total distance traveled. Each city
is represented in the chromosome string as a letter (e.g. 'A' or 'B').
To simplify the mathematics of the fitness function, this example reduces the coordinate
space to one dimension. Each city (or node) has a position given by one coordinate.
This model can be extrapolated to 2 or 3 dimensions by giving each city (or node) a 2
dimensional (X,Y) or 3 dimensional (X,Y,Z) coordinate and then modifying the distance
calculating function accordingly.
If a chromosome = 'ABCDEFGHIJKLMNOPQRST', then the fitness is evaluated as
fitness = Dist(A, B) + Dist(B, C) + Dist(C, D)....+ Dist(S, T)
Higher fitness values mean a higher probability that this chromosome will reproduce.
The possible combinations (sequences of cities) is N factorial. For 20 cities, the possible
combinations = 20! or 2.432902008177e+18.
This is an enormous number. If you tried every combination of sequences and could test
10,000 of those sequences per second (looking for the minium), it would take your
computer 8 million years to randomly come up with the minimum (ideal) sequence.
|
Method Summary |
protected double |
getFitness(int iChromIndex)
Fitness function for GASalesman now access genes directly through genes[] array
Old benchmark: 29 sec. |
static void |
main(java.lang.String[] args)
|
(package private) void |
setInitialSequence()
|
GASalesman
public GASalesman()
throws com.softtechdesign.ga.examples.GAException
setInitialSequence
void setInitialSequence()
getFitness
protected double getFitness(int iChromIndex)
- Fitness function for GASalesman now access genes directly through genes[] array
Old benchmark: 29 sec. New benchmark 16 sec.
main
public static void main(java.lang.String[] args)