遗传算法求解旅行商问题

被引：16

作者：

孙惠文

机构：

[1] 西南交通大学神经网络与信息技术研究所

来源：

西南交通大学学报 | 1996年 / 05期

基金：

国家攀登计划;

关键词：

遗传算法；旅行商问题；组合优化;

D O I：

暂无

中图分类号：

TP15 [自动模拟理论（自动仿真理论）];

学科分类号：

摘要：

本文提出一种新的遗传算法，用以求解著名的组合优化难题－旅行商问题。引用原始文献的数据，对城市数为１０、３０、５０的试例均求得公布的最优解，对城市数为７５的试例，每次结果均好于公布的最优解。用此算法求解中国旅行商问题，以２０％的概率得到已知最优解１５４０４ｋｍ。或次最优解１５４０９ｋｍ，而所得最差与最好结果的相对距离为０．６９％（即所得最长路径为１５５１０ｋｍ）。在ＣＯＭＰＡＱ／ＤＸ／２５ＭＨ微机上每得到一个优化解平均历时１５０ｓ左右。本算法与传统求解ＴＳＰ问题的方法相比，具有简单、强壮、高效、高速的特点，它原则上对任何规模的对称欧几里德平面ＴＳＰ具有通用性。

引用

页码：82 / 86

页数：5