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)
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:
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)
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)
Return to the Beginning