第３８卷 第４期 ２０１０年７月 河南师范大学学报（自然科学版）
Ｊｏｕｒｎａｌ ｏｆ Ｈｅｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ） ｆ．３８ Ｎｏ．４ Ｊｕｌｙ．２０１０
文章编号：１０００～２３６７（２０１０）０４—００４８—０３
蚁群算法迭代次数的一种优化策略 袁培燕 ，刘 萍 ，高宏卿 （河南师范大学ａ．物理与信息工程学院；ｂ．网络中心，河南新乡４５３００７） 摘 要：针对蚁群算法中后期多次迭代无法产生更优解的问题，提出了一种优化策略，当连续多次迭代没有产 生更优解时，减少迭代的总次数，加速算法的收敛性．仿真结果显示，在不影响最优解的情况下，优化后的策略明显 降低了算法的时间复杂度和空间复杂度． 关键词：蚁群算法；随机环境；性能评价；旅行商问题 中图分类号：ＴＰ３９３．０１ 文献标志码：Ａ
近年来，智能算法的研究受到了越来越多的关注．而作为继模拟退火算法、遗传算法、禁忌搜索（Ｔａｂｕ Ｓｅａｒｃｈ）算法、人工神经网络算法后的又一种应用于组合优化问题的启发式搜索算法——蚁群算法（Ａｎｔ Ａ卜 ｇｏｒｉｔｈｍ）［ ，更是研究的热点，并得到了广泛的应用．蚁群算法由意大利Ｍ．Ｄｏｒｉｇｏ等人首先提出，它模拟 蚂蚁觅食时的行为，按照启发式思想，通过信息素的诱导作用，逐步收敛到问题的最优解． 旅行商问题（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ）是ＮＰ（Ｎｏｎ—ｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｐｏｌｙｎｏｍｉａ１）问题中的一个典型例 子．实际上，蚁群算法在首次提出时，就是充分利用了蚂蚁搜索食物的过程与ＴＳＰ（旅行商）问题之问的相似 性来求解ＴＳＰ的．目前，基于蚁群算法求解ＴＳＰ问题的相关文献很多Ⅲ３ ］．其中，文献［３］主要研究了蚁群算 法中蚂蚁位置的初始化问题，通过将蚂蚁边缘化而不是随机设置，来增大解的空间，提高解的质量．文献［４］ 通过将蚁群算法中的参数进行分段继而达到优化的目的．文献［５］分析了蚁群算法中最佳配置参数的问题， 文献［６］则对目前智能算法求解ＴＳＰ问题进行了归纳分类，通过不同的实验发现进化算法与局部搜索组合 求解ＴＳＰ效果最好．结合相关文献及进行的大量实验发现，在迭代中后期，多次迭代无法产生更优解的现象 明显增多，蚁群算法陷入局部最优的可能性增大．基于此，对总的迭代次数进行了优化，当多次迭代无法产生 更优解的次数超过某个界限时，减少总的迭代次数，从而降低算法的时间复杂度和空间复杂度．
１ 蚁群算法及ＴＳＰ问题 蚁群算法由意大利学者Ｍ．Ｄｏｒｉｇｏ等人首先提出，该算法利用蚂蚁搜索食物的过程与ＴＳＰ问题的相似 性，通过模拟自然界中蚂蚁寻找食物的行为，来解决ＴＳＰ等各类复杂优化问题．蚁群算法采用分布式正反馈 并行计算机制，容易与其它算法结合，具有较强的鲁棒性和适应性．由于蚂蚁在寻路时主要依据于路径上的 信息素浓度，所以不同的信息素更新策略对蚁群算法的性能影响很大．Ｄｏｒｉｇｏ Ｍ曾给出３种不同的信息素 更新模型，分别为Ａｎｔ ｃｙｃｌｅ ｓｙｓｔｅｍ（ＡＣＳ），Ａｎｔ ｑｕａｎｔｉｔｙ ｓｙｓｔｅｍ（ＡＱＳ），Ａｎｔ ｄｅｎｓｉｔｙ ｓｙｓｔｅｍ（ＡＤＳ）． 旅行商问题是一个经典的组合优化问题，它是指一个商人欲到”个城市推销产品，希望选择这样的一条 路径：使得商人经过所有城市一次又回到初始城市，并且所走的路径最短．ＴＳＰ问题是一个典型的ＮＰ一难问 题，也是验证求解组合优化问题有效性的一个间接标准．ＴＳＰ问题的数学描述为：设 一｛ｖｌ，ｖ２，…，＂ＵＹｔ｝是 个城市的集合，Ｅ一｛（ｖｉ， ），ｖｉ， ∈Ｖ｝足 中任意两个城市两两连接的边的集合，ｃ（ｉ， ）一ｃ（ｊ， ）是边（ｖｉ， ｖｊ）∈Ｅ所需要的费用．ＴＳＰ问题就是寻找一条闭合的汉密尔顿回路使之能够访问所有的城市一次，并且这
收稿日期：２００９一ｎ—ｌ０ 基金项目：河南省教育厅自然科学基金（２００９Ｂ５２００１６）；河南师范大学青年科学基会（２ＯＯ８ｑｋＯ６） 作者简介：袁培燕（１９７８一），男，河南邓州人，河南师范大学讲师，研究方向：网络协议 ｌ 程． 第４期 袁培燕等：蚁群算法迭代次数的一种优化策略 ４９ 条回路的费用最少Ｅ ］． ２ 蚁群算法的优化及仿真分析 蚁群算法最初就是为解决ＴＳＰ问题而提出的，因此用ＴＳＰ问题评价蚁群算法在不同参数体系下的相 对性能是恰当的．在大量的实验中发现，在算法的中后期，大量的迭代次数产生相同解，即存在多次迭代无法 产生更优解的现象．最坏的一次是在５００次的迭代实验中，从第４次到最后一次的值是一样的．也就是说，在 具体的实验中，大量的迭代次数是不必要的．能不能在不影响解的情况下，减少总的迭代次数，从而达到降低 算法复杂度的目的？基于这样的考虑，设置了一个统计连续多次没有产生更优解的计数器ｃｏｕｎｔｅｒ，每当当 前迭代产生的解与上一次迭代产生的解相同，ｃｏｕｎｔｅｒ的值加１，当ｃｏｕｎｔｅｒ的值大于某一规定值Ｋ时，减少 迭代次数，同时ｃｏｕｎｔｅｒ清零．算法的伪代码如下： ｗｈｅｎ（当前迭代产生的解同上一次一样） ｛总的迭代次数一总的迭代次数一Ｄ ｃｏｕｎｔｅｒ加１ ｃｏｕｎｔｅｒ＝０） ｗｈｅｎ（ｃｏｕｎｔｅｒ大于某个值Ｋ） Ｄ为每次减少的迭代次数，实验中Ｄ的变化为１、２、５、１０．仿真平台采用ＶＣ＋＋，仿真数据是ＴＳＰＬＩＢ 标准库（Ｒｅｉｎｅｌｔ，１９９１）里面的实例ｅｉｌ５１．实验中通过改变ａ，Ｊ３的值来观察蚁群算法的性能．蚂蚁个数为３４ 个，迭代次数为５００次，Ｋ的值等于６，ａ取值范围为０．１到１．０，Ｊ３取值范围为０．１到５．实验一共生成８５种 随机场境，每种场境运行１Ｏ次，最后的结果为１ｏ次的平均值．算法的评价因子有两个，一个是求得最短路径 的距离，另一个是算法的实际迭代次数． ２．１ ａ，Ｉ３对算法的影响
瀣
６００ ５５０ 蛰
５００
变动的 图Ｉ最短路彳争ＶＳ口
变动的Ｂ 图３最短路径ＶＳ ０
隶罨 杠
上＜ 较
◆＿＿Ａｎｔ—Ｄ一１—１卜Ｄ一２ ■ Ｄ一５—● Ｄ ｌ０
Ｏ．１ Ｏ．２ Ｏ．３ Ｏ．４ Ｏ．５ Ｏ．６ ０．７ Ｏ．８ Ｏ．９ １
变动的ｄ 图２实际迭代次数ＶＳ ｏ
Ｏ．１ Ｏ．２ ０．５ １ ２ ３ ４ ５ 变动的１３ 图４实际迭代次数ＶＳ１３
０ ０ ０ ０ ０ Ｏ Ｏ 鲫 ∞ ∞ ∞ 加 ５０ 河南师范大学学报（自然科学版） 图Ｉ至图４显示了当ａ，８变动时，算法求得的最短路径及迭代次数的变化情况．从图１可以看到，当ａ 小于０．６时，优化后的策略影响了最优值，当Ｄ＝＝＝１０，ａ一０．２时，误差最大，偏离最优值达到２．４６ ，而随着ａ 的增大，这种影响逐渐减小．不过从图２也可以看到，优化后的策略明显降低了算法的迭代次数，从而降低了 算法的时间和空间复杂度．从图３和图４可以看到，相对于ａ而言，Ｇ值的波动对最短路径的影响较小，两种 情况下基本一致．而对迭代次数的影响与ａ一样，显著降低了算法的迭代次数．从上面的分析可知，优化后的 策略，在不影响最优解的情况下，显著改善了算法的复杂度． ２．２ Ｄ的改变对算法的影响 从图１到图４可以同时看到，当改变Ｄ时，最短路径及迭代次数的变化情况．当迭代次数每次减少的次 数由１、２、５到１０发生变化时，最短路径的波动较小（图１和图３所示），而迭代次数的变化较为明显，即呈现 递减的趋势．说明随着Ｄ的增大，在对最优解没有产生明显影响的情况下（图１和图３各条均线粘合在一 起），总的迭代次数随之减少．当然，也不可能将Ｄ无限增大来降低问题的求解规模，否则求得的解将会严重 偏离最优解．也就是说，为了求得尽可能的最优解，一定的迭代次数是必要的，但同时也观察到，在实验中后 期，许多次的迭代是不必要的．从图２和图４可以看出，最大的迭代次数仍然没有超过４００，所以在实验初期 设置的迭代次数５００过大，浪费了系统资源．但是，对某个ＴＳＰ问题来说，在实验初期，如何设定迭代次数是 未知的，不可能设置一个恰到好处的值，所以如何合理优化蚁群算法的迭代次数，从而降低算法的时间和空 间复杂度，是一个值得认真考虑的问题．文中通过发现连续多次迭代无法产生更优解这一实验现象，继而降 低总的迭代次数以达到对算法进行优化的目的，仿真结果表明该方案是可行的，有效的．
３ 结 论 结合ＴＳＰ问题，对蚁群算法的性能进行了评价，发现在算法运行的中后期，大量的迭代次数实际上是不 必要的，通过对该阶段的研究提出了文中的优化策略，对减少蚁群算法的迭代次数，降低算法的时空复杂度 进行了有益的尝试．
参 考 文 献 ［１］Ｄｏｒｉｇｏ Ｍ，Ｍａｎｉｃｚａｏ Ｖ，Ｃｏｌｏｍ ｉ Ａ．Ａｎｔ ｓｙｓｔｅｍ：Ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ ａ ｃｏｌｏｎｙ ｏｆ ｃｏｏｐｅｒａｔｉｎｇ ａｇｅｎｔｓ［Ｊ｜］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ Ｍａｎ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ Ｐａｒｔ Ｂ，１９９６，２６（１）：２９—４１． ［２３ Ｄｏｒｉｇｏ Ｍ，Ｇａｍ ｂａｒｄｅｉｌａ Ｌ Ｍ．Ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ：Ａ ｃｏｏｐｅｒａｔｉｖｅ ｌｅａｒｎｉｎｇ ａｐｐ ｒｏａｃｈ ｔｏ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，１９９７，１（１）：５３ ６６． ［３］ 吴春明，陈治，姜明．蚁群算法中系统初始化及系统参数的研究［Ｊ］．电子学报，２００６，３４（８）：１５３０—１ ５３３． ［４］ 卢辉斌，贾兴伟，范庆辉．基本蚂蚁算法中参数的讨论与改进［Ｊ］．计算机工程，２００５，３１（２０）：１７５—１７９． Ｅ５］ 叶志伟，郑肇葆．蚁群算法中参数ａ、Ｂ、Ｐ设置的研究一以ＴＳＰ为例［Ｊ］．武汉大学学报：信息科学版，２００４，２９（７）：５９８—６０１． ［６］ 张煜东，吴乐南，韦耿，智能算法求解ＴＳＰ问题的比较［Ｊ］．计算机工程与应用，２００９，４５（１１）：１１－１ ５． ［７］ 朱颢东，钟勇基．于贝叶斯粗糙集的文本特征选择方法［Ｊ］．河南师范大学学报：自然科学版，２００９，３７（４）：３ｌ ３５ ［８］ 蒋玲艳，张军，钟树鸿．蚁群算法的参数分析啊Ｊ］．计算机工程与应用，２００７，４３（２０）：３１—３６．
Ａｎ Ｏｐｔｉｍｉｚｅｄ Ｓｔｒａｔｅｇｙ ｆｏｒ Ｉｔｅｒａｔｉｏｎ Ｎｕｍｂｅｒｓ ｉｎ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ＹＵＡＮ Ｐｅｉ—ｙａｎ ，ＬＩＵ Ｐｉｎｇ ，ＧＡＯ Ｈｏｎｇ—ｑｉｎｇ （ａ．Ｃｏｌｌｅｇｅ ｏｆ Ｐｈｙｓｉｃｓ ８乙Ｉｎｆ０ｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，ｂ．Ｎｅｔｗｏｒｋ Ｃｅｎｔｅｒ，Ｈｅｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉｎｘｉａｎｇ ４５３００７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｖｉｄｅｓ ａｎ ｏｐｔｉｍｉｚｅｄ ｓｔｒａｔｅｇｙ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｎｏｔ ｃａｌｃｕｌａｔｉｎｇ ｂｅｔｔｅｒ ａｎｓｗｅｒ ｉｎ ｔｈｅ ｌａｔｔｅｒ ｐｈａｓｅ ｏｆ ｓｉｍｕｌａｔｉｏｎ，ｔｈａｔ ｉｓ，ｗｈｅｎ ｍｕｃｈ Ｏｆ ｃｏｎｓｅｃｕｔｉｖｅ ｉｔｅｒａｔｉｏｎ ｃａｎ ｎｏｔ ｗｏｒｋ ｏｕｔ ｂｅｔｔｅｒ ａｎｓｗｅｒ，ｉｔ ｉｓ ｎｅｃｅｓｓａｒｙ ｔｏ ｄｅｃｒｅａｓｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｉｔｅｒａｔｉｏｎ ｉｎ ｏｒｄｅｒ ｔｏ ｓｐｅｅｄ ｕｐ ａｓｔｒｉｎｇｅｎｃｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｏｐｔｉｍｉｚｅｄ ｓｔｒａｔｅｇｙ ｒｅｄｕｃｅｓ ｔｈｅ ｔｉｍｅ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ ｏｂｖｉｏｕｓｌｙ ｗｉｔｈｏｕｔ ｓａｃｒｉｆｉｃｉｎｇ ｔｈｅ ｂｅｓｔ ａｎｓｗｅｒ ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ． Ｋｅｙ ｗｏｒｄｓ：ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ；ｒａｎｄｏｍ ｅｎｖｉｒｏｎｍｅｎｔ；ｐｅｒｆｏｒｍａｎｃｅ ｅｖａｌｕａｔｉｏｎ；ＴＳＰ