基于TSP的蚁群算法参数选择问题分析.docVIP

基于TSP的蚁群算法参数选择问题分析 　　摘要：根据目前针对社会性动物群体活动的实验调查，发现其自组织行为广泛存在，例如群体活动较为频繁的蚂蚁，在群体觅食过程中能够找到蚁穴到食物的最短路径，即蚁群算法。文章围绕蚁群算法在TSP中的应用，就算法的参数选择进行了深入的研究。最后通过对全文的研究工作进行了总结，并展望了其应用价值及后期还需继续研究的问题。 　　关键词：蚁群算法 TSP 最短路径 参数选择 　　中图分类号：TP183 文献标识码：A 文章编号：1007-9416（2016）12-0131-02 　　蚁群算法是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo提出，它主要的依据就是蚂蚁在觅食过程中能够找到蚁穴到食物的最短路径。蚂蚁的视觉系统非常薄弱，几乎可以说是瞎子，但是它们却能发现食物与蚁穴之间最短的距离。生态学家的研究表明，蚂蚁是借助信息素来实现这一点的。蚁群算法也越来越多被应用到实际的问题中，并且取得了较好的效果，例如调度问题、着色问题、求解旅行商问题（TSP），并在大规模集成电路设计，通信路由控制等诸多领域表现出较好的性能。本文在介绍蚁群算法的基本原理的基础上，主要分析了蚁群算法参数的选择策略问题。 　　1 蚁群算法的基本原理 　　1.1 蚁群算法的原理 　　蚁群算法是从自然界启发中得到的一种新型的模拟进化算法，应用该算法求解TSP问题取得了较好的结果。科学家发现虽然单个蚂蚁无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线。经过大量研究发现：蚂蚁在运动过程中，能够留下一种称之为信息素的物质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此，由大量蚂蚁组成的蚁群的集体行?楸惚硐殖鲆恢中畔⒄?反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径的概率就越大。蚁群算法具有实现简单、正反馈、分布式的优点。 　　人工蚁群和自然界蚁群的相似之处在于，两者优先选择的都是含“信息素”浓度较大的路径。这在两种情况下，较短的路径上都能聚集比较多的信息素，受到上述情况的启发，科研人员在此基础上提出了蚁群算法，它不仅具有蚁群觅食行为中的信息传递功能，还具有自然界蚁群所没有的记忆能力，即能够保存已经去过的地方和已经走过的路径，从而能够更加智能的选择下一地点和路径，并且按照一定的规律总结出特有的算法进行最短路径的选择。 　　1.2 基于TSP问题的蚁群算法数学模型 　　TSP问题又称为旅行商问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访M个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最终要回到原来出发的城市。路径的选择目标是要求旅行商人怎样才能得到最短的路径，取得最佳的利益。 　　根据信息素更新的策略不同，Dorigo M曾给出了不同的蚁群算法模型，分别称为ant-cycle模型，ant-quantity模型和ant-density模型。它们的差别在于循环中路径的信息素的增量的求法不同。 　　在ant-quantity模型中： 　　其中，是信息素强度，它影响算法的收敛速度是指两座城市之间的欧氏距离，是指第只蚂蚁所走的路径长度。ant-quantity和ant-density是利用局部信息完成求解运算，ant-cycle是利用整体信息完成求解运算。通过实验得到ant-cycle的模型比其他两种模型效果好。 　　2 参数优化策略 　　通过对蚁群算法基本原理及其数学模型的学习理解，可以使用MATLAB进行蚁群算法求解TSP最短路径问题的仿真试验工作，其主要任务是：根据城市的坐标，使用蚁群算法求解TSP最优化问题，并绘制最佳结果的路径图，生成平均距离和最短距离统计图。 　　算法中的主要参数有：城市的个数，城市的坐标（城市个数*2的矩阵），最大循环次数（即迭代的次数），蚂蚁个数，表征信息素重要程度的参数，表征启发因子（期望）重要程度的参数，信息素挥发系数，信息素强度的系数（一般是一个常量），最佳路线的长度。 　　实现步骤为：第一步：变量初始化；第二步：循环开始，判断变量是否达到最大迭代次数，如果没有达到，继续下一步运行，否则，循环结束；第三步：将所有蚂蚁随机放到所有城市上；第四步：所有蚂蚁按概率函数选择下一座城市，完成各自的周游；第五步：记录本次迭代最佳路线；第六步：更新信息素；禁忌表清零，回到第二步，达到停止条件时跳到第七步；第七步：输出结果。 　　仿真中采用最短路径作为参考项，进行多目标测试得出结果，并由结果分析出蚁群算法中的参数如何选择优化。 　　2.1 缺省值的选择 　　在实验过程中，本文在进行参数选择时，取城市个数为20，迭代次数为100，蚂蚁个数为15，信息素重要程度