Web Hosting by Netfirms | Free Domain Names by Netfirms

Before starting, it is assumed that you have visited Building a Traveling Salesman Problem Set so that you can create your own problem set called cities.dat. If you want to run the Evolutionary Programming method yourself, you should visit Evolutionary Programming Code for the Traveling Salesman Problem to obtain the necessary software.

Since a general discussion of Evolutionary Programming has already been presented, this web page will focus on applying this method to the Traveling Salesman Problem (TSP). As with all Evolutionary Programming runs, a random number generator is used to build a population of initial solutions. Since we are dealing with a 60-city TSP that starts at city 1, each solution is an ordered list of 60 integers. This list starts with the number 1 and contains the numbers 1 through 60 exactly once. For example, in a 6-city problem, the array

   (1,4,3,5,6,2)

As stated in the general discussion, Evolutionary Programming is a computational methodology, not a particular algorithm. In order to create a particular algorithm, several decisions have to be made. Some of these decisions are

1. What is the population size (NPOP)?
2. How many generations (NGEN) are run?
3. How is a offspring generated?
4. How are solutions chosen from the merged population to become the Current Population for the next generation?

When all of these questions have been answered, you have a particular algorithm, and all you need is the seed for the random number generator to run the simulation.

In the demonstration program, eptsp.exe, many of these decisions are left to the user by setting values in the file eptsp.dat. The values set in eptsp.dat at distribution time and their variable names used by the program are listed below.

cities.dat             DATFIL
300 900 5              NPOP NGEN NTRN
30. 15.                PRM2 PRM3
220421573.             SEED

NPOP is the population size and is set to 300 solutions. The maximum the program allows is 600 solutions. The number of generations to run (NGEN) is 900, and there is no upper limit to this value. NTRN controls the tournament size for selecting the next generations Current Population, and is set to 5. If NTRN is set to 1, a Deterministic Selection is used.

For this program, the mutation operator selects a pair of locations along the path and switches the cities at these locations. PRM2 and PRM3 are the probabilities that the mutation operator is used a second and third time, respectively.

Finally, SEED is the seed to the random number generator which generates uniformly-distributed random numbers between 0.0 and 1.0.

Note that pair-switching is the only mutation operator available in this demonstration program. Region inversion, or any other possible operation, is excluded. In addition, the probabilities of switching a second and third pair of cities is the same for all offspring generation and remains constant throughout the simulation. It is possible for another application of Evolutionary Programming to store these probabilities in the solution vector so that they can be different for each offspring produced, or that they can be increased or decreased as the simulation proceeds. Finally, a Tournament Selection (NTRN > 1) or Deterministic Selection (NTRN = 1) procedure are the only fitness-based selection procedures available in the program. Other selection procedures are available, but testing all mutation operators and selection procedures is outside the scope of the demonstration program.

For the set of values originally stored in eptsp.dat, the flow of the demonstration program is as follows.

1. The random number generator uses SEED to generate 300 random paths through the 60 cities, always starting with City 1. The COST of each route is determined by calculating the total path length starting and ending at City 1. These random paths, and their COSTs, represent the Current Population at the start of the search. A generation counter, IGEN, is set to 0.
2. For each path in the Current Population, a new path is constructed by choosing two locations along the path (e.g. the 12th and 35th cities visited) and switching the cities in these locations.
   • If a random number between 0.0 and 1.0 is less that 0.30, a second pair of cities are switched.
     • If another random number is less than 0.15, a third pair of cities are switched.
   The COST of this route is calculated and is stored with the route in a new population.
3. When all solutions in the Current Population have generated a new solution, the Current Population and new population are merged.
4. NPOP routes (and associated COSTs) are chosen from this merged population to be the new Current Population. The selection procedure for this run is as followed.
   • The merged population is checked, and the route with the lowest COST is removed and placed in the Current Population. This is called the elitist strategy and should be used whenever a probabilistic method selects members for the Current Population.
   • 5 routes are selected at random from the merged population, and the route with the lowest COST is removed and placed in the Current Population. This procedure is repeated until NPOP solutions are moved to the Current Population.
5. The generation counter, IGEN, is increased by 1 and if it is less than 900 (NGEN) the program returns to Step 2. Otherwise, the first route in the Current Population represents the best route found by this search.

Note that if NTRN was set to 1 in eptsp.dat, the third step would have simply placed the NPOP routes with the lowest COST in the Current Population.

The resulting route lengths for various combinations of the input parameters are shown in the following Table. The first set of results all used a population size of 100 and ran the search for 600 generations with the same seed to the random number generator. The best result was found for the smallest values of PRM2 and PRM3 and a deterministic selection procedure. None of these results are very good since all of the routes have a path length that is greater than that found by the Closest City method (8489.48).

The second set of results uses the same values for most of the imput parameters. The only difference is that the population size is doubled (200) and the number of generations is halved (300). Therefore, these sets of runs generate exactly the same number of offspring as the previous set. Comparing these sets clearly shows that the second set generates results that are consistently worse than the first. This means that the search space is way too complex to be adequately sampled by 200 solutions and that the quality of the solution is more dependent upon the number of generations.

The third set of results keeps the population size at 200 and raises the number of generations back to 600. On average, these results are slightly better then for the first set, but none of the solutions are as good as the one found by the Closest City method.

The fourth and fifth sets of results increase both the population size and the number of generations. There is very little difference in the quality of the results between these sets, but they are better than the first three sets of runs.

In the sixth set of results, the population size is increased to 500 and the number of generations to 1500. When a Deterministic Selection procedure is used with the smalles values of PRM2 and PRM3, a route is obtained that is only about 130 longer than that found by the Closest City method.

When the population size and number of generations are increased to 600 and 2000, respectively, the seventh set of results are obtained. Here, one of the runs produces a route that has a smaller length than that found using the Closest City metods. These results suggest that better routes are found if a Deterministic Selection procedure is used and PRM2 and PRM3 are relatively small.

To explore this further, an eighth set of results is displayed. Here a Deterministic Selection is used throughout and only PRM2 and PRM3 are varied. Though 5 of the 9 searches found a route that has a shorter length than that found by the Closest City method, none are as good as the route found when PRM2=30 and PRM3=15. The last three runs only varied the seed to the random number generator. These results show that the simulations have not converged and that the number of generations should probably be increased further.

For the results presented here, the Evolutionary Programming route with the shortest length (7886.0) is

   1  11  10   8  38  16  34   9  15  48  19  43  35  36  17  26  32  52  54  42
  30   2  37   7  31  13  56  24  39  27  29  58   3  44   5  14  12  45   6  22
  59  46  50  21  53  33  23  51  47  20  28  49  57  60  40  55  18  25  41   4

The net result of these simulations is, as implimented here, Evolutionary Programming does a reasonable job in solving the TSP. The simplistic Closest City Approach produced a route whose total distance (8489.48) is only reduced by the largest Evolutionary Programming runs examined here. These results suggest that this method may produce even better results if the number of generations is increased beyond 2000 and different seeds to the random number generator are tested.

Again, these results only show how well the sepcific algorithm solves this problem, but make no definitive statements about the methodology.