基因演算法（Genetic Algorithm）是一種模仿自然界生物演化過程的演算法，適合在巨大數量的可行解中，迅速找到最佳解的近似解。基因演算法利用交配與突變的作用，讓一群可行解自行演化出更好的解。此演算法很合適用來解旅行推銷員問題（Traveling Salesman Problem），這篇論文除了利用典型的基因演算法外，並設計了新的限制作用，並得到了更好的結果。

The traveling salesman problem (TSP) is an NP-complete problem. These problems are considered to have no solution in polynomial time. However, there are ways of approximating the solutions to these problems. Genetic algorithm (GA) is a model of machine learning based on biological evolution of population, which uses crossover and mutation operators to solve optimization problems, evaluate individual by fitness function. They have been used successfully in different problems, including the TSP.
In this paper, we design a restriction action to weed out some paths. It is a new idea. Restriction had better be a necessary condition of the optimal solution, but they also work even though they are not. Restriction itself is not an operator. This can be added to other operators to make them more efficient. We also compare with some studies of other researchers. We find that a suitable restriction can increase the efficacy of GAs. We can design other restrictions on GAs for TSP or other problems.

[1] Arkin, F.M. and Chiang, Y.J. al. On the Maximum Scatter TSP (Extended Abstract), Cite Seer, 1997.

[2] Brady, R.M. (1985). Optimization Strategies Gleaned From Biological Evolution, Nature, 317, pp. 804-806.

[3] Bryant, K. Genetic Algorithms and Traveling Salesman Problem. University of Harvey, Cite Seer, 2000.

[4] Chatterjee, S. and Carrera, C. Genetic Algorithms and Traveling Salesman Problems. European Journal of Operational Research 93, 490-510, 1995.

[5] Davis, L. Applying Adaptive Algorithms to Epistatic Domains, Proceedings of the International Joint. Conference on Artificial Intelligence, pp. 162-164, 1985

[6] Fogel, D.B. An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144, 1988.

[7] Fogel, D.B. A Parallel Processing Approach to a ultiple Traveling Salesman Problem Using Evolutionary Programming, Proceedings on the Fourth Annual Parallel Processing Symposium, Fullerton, CA, pp. 318-326, 1990.

[8] Holland, J. Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

[9] Homaifar, A., Guan, S. and Liepins, G.E. Schema Analysis of the Traveling Salesman Problem using Genetic Algorithms. Complex systems, 6(2):183-217, 1992.

[10] Larraňaga, P., Kuijpers, C.M.H. and Murga, R.H. Tackling the Traveling Salesman Problem with Evolutionary Algorithm: Representations and Operators, Cite Seer, 1998.

[11] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B. (Eds.) . A Guided Tour of Combinatorial Optimization, The Travelling Salesman Problem, Wiley, Chichester. 1985.

[12] Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Berlin Heidelberg. 1992.

[13] Recheiiberg, 1. Optimierung Technischer Systeme Nach Prinzipien der Biologischen Information, Frommann Verlag, Stuttgart, 1973.

[14] Reinelt, G. The Traveling Salesman Computational Solutions for TSP Applications. Springer-Verlag. 1994.

[15] Syswerda, G. Schedule Optimization Using Genetic Algorithms, in Davis, L. (Ed.) Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, pp. 332-349, 1991.

[16] Whitley, D., Starkweather, T. and D'Ann Fuquay. Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator, in Schaffer, J. (Ed.) Proceedings on the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, Los Altos, CA, , pp. 133-140, 1989.