基于ＨＧＡ的较小旅行时间多旅行商问题研究

2012年02月14日12:49:16 本网站我要评论(2)字号：T | T | T

摘　　　要：为了解决较小化旅行时间的多旅行商一类问题，提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点，采用一种递阶编码方案，此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子，操作简单，并且解码方法适于求解距离矩阵对称和距离矩阵非对称的多旅行商问题。计算结果表明，递阶遗传算法是有效的，能适用于优化较小化完成时间的多旅行商问题。

关　键　词：递阶遗传算法；多旅行商问题；较小完成时间；解码方法

引　言：旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，ＴＳＰ）是一个典型的组合优化难题，它在许多领域都有着广泛的应用，已被证明属于ＮＰ问题［１］。有关ＴＳＰ问题的研究在现实问题中有很大的使用价值。诸如：交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等，都可抽象成ＴＳＰ或ＭＴＳＰ问题［２５］。为了有效地解决较小旅行时间、距离矩阵对称或者非对称的多旅行商问题，本文提出了一种递阶遗传算法（ＨｉｅｒａｒｃｈｉｃａｌＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＨＧＡ）和矩阵解码方法，以便确定每个城市由哪个旅行商经过以及各个旅行商的行走路线，即找到一个较优旅行商分配及行走路线，在各旅行商行走完后，使耗用时间较大的那个旅行商的时间较小。仿真结果证明，本文提出的算法鲁棒性好、运行效率高，具有实际应用的价值。

登录网站后可下载文件

基于ＨＧＡ的较小旅行时间多旅行商问题研究

相关阅读: