SECTION 17.3 TRAVELING SALESMAN PROBLEM
Given n cities, and a matrix c(i,j) containing the costs of travelling from city i to city j, find a closed path that visits every city exactly once and minimizes total cost.
An approximate solution to this problem is obtained using a genetic algorithm. See R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms, John Wiley & Sons, 1998.
Genetic algorithms start by generating a set of random feasible solutions. The best of these solutions are permitted to "mate" and produce offspring and mutations are occasionally introduced. The worst solutions in every generation are discarded and the process continues until either an iteration limit is reached or convergence takes place.
The MAIN program should include
COMMON/BPRINT/IPT,NFILE,NDIG,NPUNCH,JPT,MFILE
CALL DFLT
The call to TRAVSAL is as follows:
CALL TRAVSAL(NP,NIPOP,NPOP,NGOOD,CC,PP,C,CPP,MATES,X,Y,POP,
* FVAL,ITERC,IER,IVAL)
where
NP = the number of cities
NIPOP = the size of the initial population (a power of 2; 64
is often useful)
NPOP = the size of the continuing population, after the worst
of the NIPOP solutions are discarded (a power of 2; 32
is often useful)
NGOOD = the number of parents who are allowed to mate (a power
of 2; 16 is often useful); each pair of parents
generates two offspring and thus the population
temporarily increases to NPOP+NGOOD; but the NGOOD worst
are discarded
CC, PP, CPP = DOUBLE PRECISION work arrays that should be
dimensioned CC(NGOOD), PP(NGOOD), CPP(NGOOD)
C = DOUBLE PRECISION array dimensioned C(NP,NP), should
contain the costs of going from city i to city j. Set
the diagonal elements C(I,I) = 0. It is required that
C(I,J) = C(J,I).
MATES = a work array dimensioned MATES(2,NGOOD/2)
X,Y = DOUBLE PRECISION work arrays dimensioned X(NP),Y(NP)
POP = INTEGER array dimensioned POP(NIPOP,NP); it contains the
city identifiers of the tours in the subsequent
generations. After convergence, POP(1,1),...,POP(1,NP)
contains the solution; i.e., the optimal tour starts in
the city with identifier contained in POP(1,1),
continues to the city the identifier of which is
contained in POP(1,2), etc.; after the city contained
in POP(1,NP) is reached, the tour returns to POP(1,1).
FVAL = DOUBLE PRECISION array dimensioned FVAL(NIPOP); it will
contain the costs of the tours (after convergence,
FVAL(1) is the optimal cost)
ITERC = upon returning from TRAVSAL, it contains the number of
generations
IER = error return; -1 iteration limit exceeded, -3 input
error
IVAL = upon returning from TRAVSAL, it contains the number of
function evaluations
Other parameters can also be set, but will be initialized by CALL DFLT (See Section 1.1). The following COMMON blocks are relevant:
COMMON/BENALG5/JNITGEN,JPAIR,JTERL,JTEST
where
JNITGEN = 2 members of the initial population are generated
at random (default=2)
= 4 The user read in the members of the initial
population into the array POP (NIPOP sets of values)
JPAIR = 1 parents are selected for pairing as follows: the
lowest-cost parent mates with the second-lowest
cost parent, the third-lowest with the
fourth-lowest, and so on
= 2 pairing by rank-weighting (See Haupt and Haupt,
p. 39)
= 3 pairing by cost weighting (See Haupt and Haupt,
pp. 39-40) (default=3)
= 4 random pairing
JTERL = iteration limit (default=99)
JTEST = 1 if testing for convergence should be based on the
optimal value achieved in a population (default=1)
= 2 if testing should be based on the mean value of the
population (this latter is likely to give a better
optimum, but may take a great deal more computation)
COMMON/BENALG6/YMUTE,BCCwhere
YMUTE = DOUBLE PRECISION constant defining the mutation rate;
the number of mutations in a population will be
(NPOP+NGOOD)*NP*YMUTE. The required number of
individuals in the population will be chosen at random
(except the best element in the population will not
be subject to mutation) and then two randomly
chosen city pairs will be exchanged (default=0.06)
BCC = DOUBLE PRECISION required relative accuracy (default=
0.001)