一种改进的遗传算法及其在TSP求解中的应用

摘要：

在使用传统遗传算法求解问题的过程中，收敛速度与问题解的质量是影响算法寻优能力的一对主要矛盾。针对上述矛盾，本文通过引入一种新的变异算子——转位算子以及增加一些控制策略，提出了一种高效的改进型遗传算法，并且使用基于 DCOM 的分布式环境来实现其并行性。使用改进型遗传算法对国际通用的 TSP 测试库 TSPLIB 中不同城市规模的数据进行测试表明，实例 att48 和实例 st70得到的最短路径长度均优于 TSPLIB 中提供的最优路径计算结果，实例 kroA100 得到的最短路径长度与 TSPLIB 中提供的最优路径计算结果相同。实验表明，该算法不仅容易收敛到问题的最优解，而且求解速度也有所提高。

关键词： 遗传算法 孤岛模型 转位算子

作者: 于兴涛 刘宏 朱大铭

作者单位: 山东大学计算机科学与技术学院， 济南250061

会议类型: 国内会议

会议名称: 2005中国计算机大会

会议地点: 武汉

会议语种:中文

在线出版日期: 2005-10-13（万方平台首次上网日期，不代表论文的发表时间）