您所在的位置: 中国管理论文网 >> 经济管理论文 >> 求解TSP 问题的一种改进蚁群算法
求解TSP 问题的一种改进蚁群算法
来源:
摘 要：TSP 问题是典型的NP-hard 组合优化问题，用蚁群算法求解此问题存在搜索时间长，容易陷入局部最优解的不足。本文提出了一种改进的蚁群算法。该算法在蚁群算法中植入遗传算法，利用遗传算法生成信息素的分布，克服了蚁群算法中搜索时间长的缺陷。此外，在蚁群算法寻优中，采用交叉和变异的策略，改善了TSP 解的质量。仿真结果显示，改进的蚁群算法是有效的。
关键词：蚁群算法；遗传算法；TSP 问题
1 引 言
旅行商问题（Traveling Salesman Problem,TSP）是一个易于描述却难以处理的问题。它可描述为：假设有一个旅行商人从自己所在的城市出发去拜访n 个城市，要求每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求一条最短的周游路径。由于TSP 问题在智能机器人路径规划、城市管道铺设优化、交通运输、电路板设计以及物流配送等领域内有着广泛的应用，因此，能快速、有效地求解TSP 问题有着重要的意义。
近年来，人们从仿生学的机理中收到启发，提出了许多用于求解TSP 问题的新方法，如模拟退火算法[1]、遗传算法[2]、神经网络[3]等。其中，由意大利学者Colorni A、和Maniezzo V 于1992 年首先提出来的蚁群算法是基于蚂蚁觅食行为的一种仿生优化算法。
该算法与自然界蚁群的觅食行为以及旅行商问题有相似之处，是一种求解NP-HARD 问题较有潜力的随机优化算法。然而用蚁群算法求解TSP 存在搜索时间长、容易陷入局部最优解等缺点，并且随着城市数目的增多，TSP 问题求解的空间和时间复杂度呈指数级增长。
为了克服蚁群算法的缺陷，本文将遗传算法融入到蚁群算法中。首先利用遗传算法的随机搜索、快速性、全局收敛性产生寻找最优路径的初始信息素分布，然后充分利用蚁群算法的并行性、正反馈机制以及求解效率高等特性求解出TSP 的最优解。改进的算法汲取了两种算法的优点，克服各自的缺陷。在时间效率上优于蚁群算法，在求解效率上优于遗传算法，加快了收敛速度，较好地求解了TSP 问题。
2 改进蚁群算法的主要操作
改进的蚁群算法的基本思路是首先由遗传算法产生较优解，较优的路径上留下信息素，其他不改变；然后让蚂蚁按照蚁群算法，完成一次遍历后，再让蚂蚁作遗传算法的交叉操作和变异操作，从而得到较优的解。
2.1 算法设计
（1）改进算法中遗传算法的设计本文以城市的遍历次序作为遗传算法的编码，适应度函数取为哈密顿圈的长度的倒数。
利用rand 函数随机生成一定数量的十进制实数编码种群，通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群，然后对这个种群进行下一轮进化。在改进算法中，遗传算法种群中每一个染色体看作是蚁群算法中的一只蚂蚁。在经过一轮选择、交叉、变异操作后，算法产生的可行解，可以看作是这些蚂蚁找到的新解。其中，变异操作策略主要是：在第1~ n 个访问的城市中随机地选取第j1次和第j 2 次访问的城市，在路径C0 中交换第j1次和第j 2 访问的城市，其余不变，此时的路径为C1。比如，j1=2（第2 次访问的城市是城市3），j 2 =7（第7 次访问的城市是城市9），则C1= 2 9 4 1 5 7 3 8 6。
另外，利用种群中优秀个体反馈信息指导算法的交叉操作，从而解决了初始城市的选择问题，保证较长优秀基因片段的获取，大大提高算法的效率。其主要操作是在第二个串中随机选择一个交叉
