基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第45页
湖北工业大学硕士学位论文 最优解附近提高解的质量和收敛速度，而且能够有效地避免早熟收敛¨引，是到目 前为止解决ＴＳＰ问题最好的蚁群算法。主要作了如下改进 （１）完成一次循环后，只有循环最优解或到全局最优解所属路径上的信息被 更新。 （２）为了避免算法过早收敛于非全局最优解，将各条路径上的信息素限制于 ｈ∽‰】之间，超出这个范围的值被强制设为ｆ晌或者是ｚ嘲，可以有效地避免某 条路径上的信息素远大于其它路径，使得蚂蚁都集中到一条路径上汹１。…
ｒ
ａｒｇ盘瓤吨ｏ）慨刚｝若留ｓ吼
ｓ＝｛
㈤Ⅲ
巧Ｏ＋以）一（１一ｐｈＯ）＋肚％
（４．１３）
△％＝｛，
否则若Ｑ，＂，∈全局最优路径
（４・１４）
湖北工业大学硕士学位论文
最优解附近提高解的质量和收敛速度，而且能够有效地避免早熟收敛¨引，是到目
前为止解决ＴＳＰ问题最好的蚁群算法。主要作了如下改进
（１）完成一次循环后，只有循环最优解或到全局最优解所属路径上的信息被
更新。
（２）为了避免算法过早收敛于非全局最优解，将各条路径上的信息素限制于
ｈ∽‰】之间，超出这个范围的值被强制设为ｆ晌或者是ｚ嘲，可以有效地避免某
条路径上的信息素远大于其它路径，使得蚂蚁都集中到一条路径上汹１。
（３）为使蚂蚁在算法初期能更多地搜索新的解决方案，初始时刻将各条路径上
的信息素都设为了僦。
（４）当所有蚂蚁完成一次循环后，按式和式对路径上的信息进行全局更新。
％Ｏ＋以）＝（１一ｐ心Ｏ）＋‘芦
（４．１５）
ｌ
１
若（ｉ，ｊ）∈最优路径
△露耐＝Ｊ
邝妇）
（４．１６）
Ｌ
。
否则
式中，ｐ表示信息素挥发系数，则１一ｐ信息素残留因子，为防止信息的无限
积累，通常设置（０＜ＪＤ＜１）；厂Ｏ妇）表示本次循环最优解或到目前为止找出的
全局最优解。
４．７几种改进的蚁群算法比较
与ＡＳ算法相比彳Ｓ加算法、ＡＣＳ算法及ＭＭＡＳ算法的共同之处在于加强了对最
优解的利用Ｈ０１。只有最优解所属路径上的信息素允许加耐３０１。但是，加强对最优
解的利用将会导致搜索中的停滞现象。在ＡＣＳ算法中通过增加局部信息素更新来
减少路径上的信息素量，从而使后面的蚂蚁选择该路径的可能性减少；在ＭＭＡＳ算
法中，通过限制信息量的范围，使路径上的信息量不会小于某一最小值，从而避
免了所有蚂蚁选择同一条路径的可能性，即避免了搜索中的停滞现象。
我们从ＴＳＰＬＩＢ问题库中选取几种有代表性研究得比较多并且己有己知最优解
的对称问题作为测试对象ｍ１，对前述几种算法进行性能评价。
ＴＳＰＬＩＢ是由一系列ＴＳＰ问题以及相关问题所组成的问题库。它于１９９０年Ｒｉｃｅ
大学并行计算研究中心举行的ＴＳＰ问题研讨会上建立：最初包含８４个测试问题，
４１
湖北工业大学硕士学位论文
并且收集了一系列国际知名研究人员对ＴＳＰ问题的研究成果，之后还在不断更新
扩充。该问题库己成为国际上研究ＴＳＰ问题的通用测试集Ｈ刳。
表４．１几种改进蚁群算法测试结果
表４．１为测试结果，数字为选取城市数目。从表４．１可以看出，ＭＭＡＳ算法具
有最好的性能，其次是ＡＣＳ算法，通常情况下４％算法优于ＡＳ算法。
４．８本章小结
本章全面阐述了蚁群算法的原理，分析了蚁群算法的优缺点，通过实验比较
了几种改进蚁群算法的性能，得到的结论是ＭＭＡＳ算法在解决ＴＳＰ问题上性能最好。
为下一章贴片机路径优化的实现提供了理论基础。
４２