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.


Constructor Summary
GASalesman()
           
 
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()
           
 

Constructor Detail

GASalesman

public GASalesman()
           throws com.softtechdesign.ga.examples.GAException
Method Detail

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)