遗传算法求解旅行商问题

本文提出一种新的遗传算法，用以求解著名的组合优化难题－旅行商问题。引用原始的文献数据，对城市数为10、30、50的试例均求得公布的最优解，对城市数为75的试例，每次结果均好于公布的最优解。用此算法求解中国旅行商问题，以20％的概率得到已知最优解1540km。或次最优解15409km，而所得最差与最好结果的相对距离为0．69％（即所得最长路径为15510km)。在COMPAQ／DX／25MH微机上每得到一个优化解平均历时150s左右。本算法与传统求解TSP问题的方法相比，具有简单、强壮、高效、高速的特点，它原则上对任何规模的对称欧几里德平面TSP具有通用性。

A Genetic Algorithm for Travelling Salesman Problems

Based on the theory of natural evolution,a new optimization method Genetic Algorithm is developed for the famous combinatorial optimization problem Travelling Salesman Problems in this paper.For 10 town,30 town and 50 town problems,the same optimum solutions as published before are obtained.For 75 town problem,every result is better than the result published before.As a further test,China TSP is calculated fifty times,getting the shortest tour (15 404 km) or the quasi shortest tour (15 409 km) ten times.The relative difference between the lengths of the best and the worst tour found is only 0.69%,and final results can be obtained every 150 seconds in COMPAQ386/DX/25MH.Compared to traditional search methods,the method of genetic algorithm is simple,robust and efficient,and is suitable for all Euclidean TSP in principle without considering the computer ebvironment.