Genetic Algorithm for TSP

Our encoding and operators for the genetic algorithm itself are not particularly novel and we describe them below. The objective function for the N cities two dimensional Euclidean TSP is the sum of Euclidean distances between every pair of cities in the tour. That is:

$$\mbox{Obj. function} = \sum_{i=1}^{N} \sqrt{(x_{i}-x_{i-1})^{2}+(y_{i}-y_{i-1})^{2}}$$

Where, x_i, y_i are the coordinates of city i and x_N, y_N equals x₀, y₀. We turn this minimization problem into a maximization problem for the GA by subtracting the objective function value from a large constant.

We use the usual path representation where the cities are listed in the order in which they are visited. Greedy crossover which was invented by Grefenstette  [Grefenstette et al., 1985] ensures that we always get legal tours.

  

Figure: Illustration of the Greedy-Swap Mutation

A tour before applying greedy-swap (Tour1)

A possible tour after greedy-swap (Tour2)

We use a new mutation operator, greedy-swap. The basic idea of greedy-swap is to randomly select two cities from one chromosome and swap them if the new (swapped) tour length is shorter than the old one. Only four edges are different between the two tours. This is shown in Figure 2. Before mutation we have $Tour1 = \underbrace{DA}B\underbrace{CF}ED$, and city B and city E are randomly chosen from the tour as the swap positions. After swapping B and E, we get tour $Tour2 = \underbrace{DA}E\underbrace{CF}BD$. Edges AB, BC, FEand ED in Tour1 are replaced by edges AE, EC, FB and BD in Tour2. We keep the new tour only when

$$\begin{array}{l} \big\Vert AB\big\Vert+\big\Vert BC\big\Vert ... ...Vert +\big\Vert FB\big\Vert + \big\Vert EB\big\Vert \end{array}$$

All the other edges are the same in Tour1 and Tour2, so the total tour length of Tour2 when the above condition holds, is shorter.

We use CHC selection to guarantee that the best individual will always survive in the next generation [Eshelman, 1991]. In CHC selection if the population size is N, we generate N children by roulette wheel selection, then combine the N parents with the N children, sort these 2N individuals according to their fitness value and choose the best N individuals to propagate to the next generation.