基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第42页
湖北工业大学硕士学位论文 ｆｏｒ ｉ＝ｌ ｔｏ ｎ一１ Ｄｏ（遍历所有城市） ｆｏｒ ｋ＝１ ｔｏ Ｍ Ｄｏ（对Ｍ只蚂蚁循环） ｆｏｒ ｊ＝ｌ ｔｏ ｎ Ｄｏ（对ｎ个城市循环） 根据公式（４．２）和（４．３），蚂蚁ｋ选择下一个城市ｊ，将蚂蚁ｋ移 动到城市ｊ，把城市ｊ置入禁忌列表纪６‰； ｅｎｄ ｅｎｄ ｅｎｄ 计算所有蚂蚁求得的回路距离，根据公式（４．２），（４．３）和（４．５）， 更新路径（ｉ，ｊ）上的信息激素； Ｎｃ＝ｎｃ＋１： Ｅ…
湖北工业大学硕士学位论文
图４．２蚁群算法的程序结构流程图
蚁群算法根据上述公式，当循环的次数达到实现定义好的ＮＣｍａｘ时或者所有
的蚂蚁都选择了同一种路径方式时，整个程序终止。其程序的基本步骤如下：
１初始化
参数初始化令ｔ＝０和循环次数ＮＣ＝０，设置最大循环次数ＮＣ眦ｘ，将ｍ只蚂蚁
随机地放到ｎ个城市，将每条边（ｉ，ｊ）上的信息素设为一个常数，且△％；０，将
出发点城市设置到禁忌表中
２迭代过程
Ｗｈｉｌｅ
ｎｏｔ结束条件ｄｏ
３７
湖北工业大学硕士学位论文
ｆｏｒ
ｉ＝ｌ
ｔｏ
ｎ一１
Ｄｏ（遍历所有城市）
ｆｏｒ ｋ＝１
ｔｏ
Ｍ
Ｄｏ（对Ｍ只蚂蚁循环）
ｆｏｒ
ｊ＝ｌ
ｔｏ
ｎ
Ｄｏ（对ｎ个城市循环）
根据公式（４．２）和（４．３），蚂蚁ｋ选择下一个城市ｊ，将蚂蚁ｋ移
动到城市ｊ，把城市ｊ置入禁忌列表纪６‰；
ｅｎｄ
ｅｎｄ
ｅｎｄ
计算所有蚂蚁求得的回路距离，根据公式（４．２），（４．３）和（４．５），
更新路径（ｉ，ｊ）上的信息激素；
Ｎｃ＝ｎｃ＋１：
Ｅｎｄ
ｗｈｉｌｅ
３输出结果，结束算法。
４．５基本蚁群算法的优缺点
基本蚁群算法具有很强的发现解的能力，这是因为该算法不仅利用了正反馈
原理ｂ羽，在一定程度上可以加快进化过程，而且是一种本质上并行的算法，不同
个体之间不断进行信息交流和传递，从而能够相互协作，有利于发现较好解。具
有如下的优点：
（１）分布式本质并行算法，它是一种基于种群的进化算法，本质上具有并行
性，易于并行实现。
（２）具有较强的鲁棒性，对其模型稍加修改，便可以应用于其他问题。
（３）易于与其他方法结合，基本蚁群算法很容易与多种启发式算法结合，以
改善算法的性能。
（４）其优化过程不依赖于优化问题本身的严格数学性质，如连续性，可导性
及目标函数和约束函数的精确数学描述。
（５）是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会
求得全局最优解∞１。
基本蚁群算法是一种有效的随机搜索算法，但也存在一些缺陷Ⅲ１
（１）与其他方法相比，该算法一般需要较长的时间。
（２）该算法易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的
解完全一致，不能对解空间进一步搜索，不利于发现更好的解。
湖北工业大学硕士学位论文
４．６基本蚁群算法的改进思路
基本蚁群算法存在收敛速度慢，易于陷入局部最优解，针对这些不足，人们
提出了几种改进蚁群算法。
４．６．１带精英策略的蚁群系统
带精英策略的蚁群系统（Ａｎｔ
Ｓｙｓｔｅｍ
ｗｉｔｈ
ｅｌｉｔｉｓｔ
ｓｔｒａｔｅｇｙ简称彳＆ｆｆｆ）是最
早的改进的蚁群算法，在某些方面它类似遗传算法中所使用的精英策略口钔。在遗
传算法中精英策略的思想是为了保留住一代中的最适应个体啪３，类似地，在４￡船
中，为了使到目前为止所找到的最优解在下一次循环中对蚂蚁更有吸引力在每次
循环之后给予最优解以额外的信息素增量信息素按式（４．７）和式（４．８）进行更新。
％ｐ＋１）＝（１一ｐ境Ｏ）＋△‘ｆ＋△％。
（４．７）
其中
△影一
△巧＝∑△巧‘
七・１
（４．８）
Ｑ
若第ｋ只蚂蚁在本次循环中经过（ｉ，ｊ）
ｔ
（４．９）
Ｏ
否则
△％ｋ＜＿罟尊？“’Ｄ是当前最＿解的一部分
。４．１∞
蚁群系统（Ａｎｔ
Ｃ０１０ｎｙ
Ｓｙｓｔｔｅｍ简称ＡＣＳ）是由Ｍ．Ｄｏｒｉｇｏ和Ｇａｍｂａｒｄｅｌ
ｌａ在
厂ｌｌ●，弋●Ｌ