参数设置的研究

《参数设置的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、蚁群算法中参数，，设置的研究*——以TSP问题为例叶志伟郑肇葆（武汉大学遥感信息工程学院湖北武汉430079）【摘要】本文以TSP问题为例，对蚁群算法中参数，，的影响和作用做了理论上的分析和研究。以30个城市为实例的计算表明，理论分析是正确的，同时对最优的参数配置问题做了分析和研究。在保证获得解的前提下，为了提高计算速度，我们对基本蚁群算法中的选择路线策略进行了调整，通过实例的计算表明：这种调整是切实可行的，有较好的实用价值。【关键词】：蚁群算法，TravelingSalesmanProblem（TSP），参数配置１引言自从1991年意大利学者DorigoM，Ma

2、niezzoV和ColorniA等首先提出蚁群算法以来，吸引了很多研究人员对该算法进行研究，并被成功地运用于解决许多组合优化问题。如：TSP（TravelingSalesmanProblem）,QAP(QuadraticAssignmentProblem),JSP(Job-shopSchedulingProblem),图像处理分析等。TSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果，但是也存在一些不足：（1），如果参数,,设置不当，

3、导致求解速度很慢且所得解的质量特别差。（2），基本蚁群算法计算量大，求解所需时间较长。（3），基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环数的条件下很难达到这种情况。另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。以上这些问题的存在，限制了蚁群算法在实际应用中的进一步推广。因此，本文首先对参数,,的设置作理论上的定性分析，并对其在TSP问题中的作用作整体说明。然后通过以ol

4、iver30城市问题（该问题目前已知最优解为423.73）为例进行计算，提出一组较优的参数配置。实验表明，按照这组参数配置运行能保证得到TSP问题质量很高的解。而后，我们针对基本蚁群算法计算量大的问题进行了进一步的研究。通过对基本蚁群算法的深入理论分析，我们认识到：蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合，但是原有的基本蚁群算法中蚂蚁却利用随机选择策略来选择线路。“正反馈”原理旨在强化性能较好的解，而随机选择策略却使进化速度缓慢，并容易出现停滞现象，甚至丢失较好的解——这就是造成蚁群算法耗时长的根本原因。因此我们从选择路线策略上着手进行修改，提

5、出了一种新的策略和参数配置的方法。试验证明，这种方法是切实可行的，有较好的实用效果。2蚁群算法2.1蚁群行为仿真的基本思想蚁群算法是一种受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。其基本原理如下图：图1蚁群路线fig1thepathofantcolony上图表示蚂蚁觅食的线路，A为蚁穴,Ｂ为食源，从Ａ到Ｂ有两条线路可走，ＡＣＢ是长路径，ＡＤＢ是短路径。蚂蚁走过一条路线以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这种气味的强度选择移动的方向。图1(ａ)表示起始情况，假定蚁穴中有4只蚂蚁，分别用1,2,3,4表示，Ｂ为食源

6、。开始时蚁穴中蚂蚁1,2向食源移动，由于路线ＡＣＢ和ＡＤＢ上均没有蚂蚁通过，在这两条路线上都没有信息素气味，因此蚂蚁1,2选择这两条线路的机会均等。令蚁1选择ＡＣＢ线路，蚁2选择ＡＤＢ线路，假定蚂蚁移动的速度相同，当蚁2到达食源Ｂ时，蚁1还在途中，如图1(ｂ)。蚁2到达食源以后就返回，这时从Ｂ返回也有两条线路选择，哪一条线路上信息素的气味重就选择哪一条。因为蚁1还在途中，没有到达终点，这时在ＢＣＡ线路上靠近Ｂ端处，蚁1还没有留下信息素气味，所以蚁2返回蚁穴的线路只有一个选择，就是由原路返回。当蚁2返回Ａ时，蚁3开始出发，蚁3的线路选择必定是ＡＤＢ，因为这时ＡＤＢ上

7、气味浓度比ＡＣＢ上重(ＡＤＢ上已有蚂蚁两次通过)，如图1(ｃ)所示。当蚁1到达食源Ｂ时,蚁1返回线路必然选择ＢＤＡ，如图1(ｄ)所示。如此继续下去，沿ＡＤＢ线路上移动的蚂蚁越来越多，这就是巢穴到食源的最短路线，蚂蚁根据线路上留下信息素浓度的大小，确定在路线上移动的方向，蚁群向信息素浓度重的线路集聚的现象称为正反馈。蚂蚁算法正是基于正反馈原理的启发式算法。2.2蚁群算法的模型及在TSP问题中的实现基本蚁群算法在TSP问题中实现的过程如下：假设将m只蚂蚁放入到n个随机选择的城市中,每只蚂蚁每步的移动，是根据一定的概率，选择下一个它还没有访问过的城市。蚂蚁选择下一个目标

8、城市的主要