Tsp solver using genetic algorithm

1APPENDIX A:TSP SOLVER USING GENETIC ALGORITHM2The outline of the GA for TSPThe algorithm consists of the following steps:Initialization: Generation of M individuals randomly.Natural Selection: Eliminate p1% individuals. The population decreases by M.p1/100.Multiplication: Choose M.p1/100 pairs of individuals randomly and produce an offspring from each pair of individuals (by crossover). The population reverts to the initial population M.Mutation by 2-opt: choose p2% of individuals randomly and improve them by the 2-opt method. The elite individual (the individual with the best fitness value in the population) is always chosen. If the individual is already improved, do nothing.3RepresentationWe use the path representation for solution coding.EX: the chromosome g = (D, H, B, A, C, F, G, E) means that the salesperson visits D, H, B, A,E successively, and returns to town D.4Mutation by 2-optThe 2-opt is one of the most well-known local search operator (move operator) among TSP solving algorithms.It improves the tour edge by edge and reverses the order of the subtour.When we apply the 2-opt mutation to a solution, the solution may fall into a local mimimum.56Crossover operatorGreedy Subtour Crossover (GSX). It acquires the longest possible sequence of parents’ subtours.Using GSX, the solution can pop up from local minima effectively.7Greedy Subtour CrossoverInputs: Chromosomes ga = (D, H, B, A, C, F, G, E) and gb = (B, C, D, G, H, F, E, A).Outputs: The offspring g = (H, B, A, C, D, G, F, E)8procedure crossover(ga, gb){ fa  true fb  true choose town t randomly choose x, where ax = t choose y, where by = t g  t do { x  x -1 (mod n), y  y + 1 (mod n). if fa = true then { if ax  g then g  ax.g else fa  false } if fb = true then { if bx  g then g  g.by else fb  false } } while fa = true or fb = true if |g| < ga| then { add the rest of towns to g in the random order } return g}Algorithm: Greedy Subtour CrossoverInputs: Chromosomes ga = (a0, a1, , an-1) and gb = (b0, b1,, bn-1).Outputs: The offspring chromosome g.9Example:Suppose that parent chromosomes ga = (D, H, B, A, C, F, G, E) and gb = (B, C, D, G, H, F, E, A).First, choose one town at random, say, town C is chosen. Then x = 4 and y =1. Now the child is (C).Next, pick up towns from the parents alternately. Begin with a3 (A) and next is b2 (D). The child becomes g = (A, C, D).In the same way, add a2 (B), b3 (G), a1 (H), and the child becomes g = (H,B,A,C,D,G).Now the next town is b4 = H and H has already appeared in the child, so we can’t add any more towns from parent gb.Now, we add towns from parent ga. The next town is a0 = D, but D has already used. Thus, we can’t add towns from parent ga, either.Then we add the rest of the towns, i.e., E and F, to the child in the random order. Finally the child is g = (H,B,A,C,D,G,F,E).10Survivor SelectionEliminate R = M.p1/100. We eliminate similar individuals to maintain the diversity in order to avoid immature convergence.First, sort the individuals in fitness-value order. Compare the fitness value of adjoining individuals. If the difference is less than , eliminate preceding individual while the number of eliminated individuals (r) is less than R. Next, if r < R, eliminate R - r individuals in the order of lowest fitness value.11Other parametersTest data: TSPLIBgr96.data (666 cities)Population size: 200maximum number of generations: 300p1 = 30%p2 = 20%produces the minimum solutionConclusion: The solver brings out good solution very fast since GA here utilizes heuristic search (2-opt) in genetic operators. It is a hybrid algorithm.12ReferenceH. Sengoku, I. Yoshihara, “A Fast TSP Solver Using GA on Java”, 1997.