摘要
本文提出一种新的遗传算法，用以求解著名的组合优化难题－旅行商问题。引用原始文献的数据，对城市数为１０、３０、５０的试例均求得公布的最优解，对城市数为７５的试例，每次结果均好于公布的最优解。用此算法求解中国旅行商问题，以２０％的概率得到已知最优解１５４０４ｋｍ。或次最优解１５４０９ｋｍ，而所得最差与最好结果的相对距离为０．６９％（即所得最长路径为１５５１０ｋｍ）。在ＣＯＭＰＡＱ／ＤＸ／２５ＭＨ微机上每得到一个优化解平均历时１５０ｓ左右。本算法与传统求解ＴＳＰ问题的方法相比，具有简单、强壮、高效、高速的特点，它原则上对任何规模的对称欧几里德平面ＴＳＰ具有通用性。
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.
出处
《西南交通大学学报》
EI
CSCD
北大核心
1996年第5期550-554,共5页
Journal of Southwest Jiaotong University
基金
国家攀登计划
关键词
遗传算法
旅行商问题
组合优化
genetic algorithm
travelling salesman problem(TSP)
combinatorial optimization
