Appendix A: TSP solver using genetic algorithm provides about The outline of the GA for TSP, Mutation by 2-opt, Crossover operator, Greedy Subtour Crossover, Survivor Selection, Other parameters and somethings else. | APPENDIX A: TSP SOLVER USING GENETIC ALGORITHM The outline of the GA for TSP The algorithm consists of the following steps: Initialization: Generation of M individuals randomly. Natural Selection: Eliminate p1% individuals. The population decreases by . Multiplication: Choose 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. Representation We 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. Mutation by 2-opt The 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. Crossover operator Greedy Subtour Crossover (GSX). It acquires the longest possible sequence of parents’ subtours. Using GSX, the solution can pop up from local minima effectively. Greedy Subtour Crossover Inputs: 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) procedure 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 else fa false } if fb = true then { if bx g then g else fb false } } while fa = true or fb = true if |g| APPENDIX A: TSP SOLVER USING GENETIC ALGORITHM The outline of the GA for TSP The algorithm consists of the following steps: Initialization: Generation of M individuals randomly. Natural Selection: Eliminate p1% individuals. The population decreases by . Multiplication: Choose 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. Representation We 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. Mutation by 2-opt The 2-opt is one of the most well-known local search operator (move .
