|
|
Before beginning, it is assumed that you have gone to Building a Traveling Salesman Problem Set, and have downloaded the zip-file, extracted its contents and run bldcity so that you have a copy of cities.dat.
The first step is to download the file eptsp.zip and save it to a the same directory that contains cities.dat. (If given the option, make sure that you use a binary download.)
When the entries of this zip-file are extracted, four new files will be stored on your disk. The executable eptsp.exe is used to determine the Evolutionary Programminging solution (eptsp.out). This executables use eptsp.dat to control the execution. The remaining two files (eptspp.dat and (eptspp.exe) are used to create a PostScript plot (eptsp.ps) of the final route.
An inspection of eptsp.dat shows that it contains the lines
cities.dat DATFIL 300 900 5 NPOP NGEN NTRN 30. 15. PRM2 PRM3 220421573. SEEDThe first line contains the name of the disk file that contains the data for the cities to visit. This is done so that you can create multiple TSP problem sets, save them as different names on your disk, and run these executables on each of them. The second line contains the population size, number of generations and tournament size. The third line contains the probabilities of using the mutation operator a second and third time to generate an offspring. The final line is the seed to the random number generator.
When eptsp.exe is run from a DOS-window, it creates a file named eptsp.out. This file contains the route determined by this particular application of the Evolutionary Programming methodology. The beginning and ending lines of this output are as follows.
Evolutionary Programming treatment of the TSP
City data obtained from cities.dat
It contains 60 cities on a 1000.0 by 1000.0 map
The population size is 300
The number of generations is 900
The survival tournament size is 5
The seed to the random number generator is 220421573.0
The second mutation probability is 30.000
The third mutation probability is 15.000
The lowest initial distance is 2.79722E+04
GENERATION DIST(FINAL)
========== ============
1 2.79331E+04
2 2.79331E+04
(lines deleted for brevity)
899 1.09940E+04
900 1.09940E+04
The best route is:
1 8 48 36 15 30 60 57 23 47 20 49 55 40 28 18 51 33 53 32
14 44 58 9 39 24 56 11 10 38 16 34 27 29 42 54 50 22 45 5
12 26 52 21 59 46 6 3 17 35 43 19 2 25 7 41 4 37 31 13
The program generates an initial population of random routes; the best of
which has a route length of 27972.2. This population generates offspring
for a total of 900 generations. At the end of this, the best route has a
path length of 10994.0.
The order of cities visited for this
best route is then displayed.
After this program is run, you can run eptspp.exe to create a PostScript plot of this route. An inspection of eptspp.dat shows that it contains the single line
eptsp.outThis is done so that you can run the program on multiple problem sets, or with different values of the control parameters, saving the output as different names on your disk, and run eptspp.exe on each of them.
When eptspp.exe is run from a DOS-window, it creates a file named eptsp.ps. This file contains the route determined by Evolutionary Programming as a PostScript plot.
Return to Application of Evolutionary Programming to the Traveling Salesman Problem.
