基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第40页
湖北工业大学硕士学位论文 通常设置０＜ＪＤ＜１；△％表示本次循环中路径（ｉ，ｊ）上的信息素增量，△ｔ，‘表示 第Ｋ只蚂蚁在本次循环中留在路径（ｉ，ｊ）上的信息量。 根据信息素更新策略不同，Ｍ．Ｄｏｒｉｇｏ提出三种不同的基本蚁群算法模型啪１， 分别是Ａｎｔ—Ｃｙｃｌｅ模型，Ａｎｔ—Ｑｕａｎｔｉｔｙ模型及Ａｎｔ—Ｄｅｎｓｉｔｙ模型，其差别在于△％‘ 的求法不同口１ｌ。 在Ａｎｔ—Ｃｙｃｌｅ模型中 ｆ Ｑ 若第ｋ只蚂蚁在本次循环中经过（ｉ，ｊ…
湖北工业大学硕士学位论文
整个算法的运行效率和快速反应的能力。
４．３基本蚁群算法数学模型
以求解平面上ｎ个城市的ＴＳＰ问题用（０，ｌ，…ｎ一１）表示城市序号来说明基本
蚁群算法啪１。
首先引入如下记号：ｍ为蚁群中的蚂蚁数；ｄ。Ｏ，ｊ『一１’２，…，１）为城市ｉ和城市ｊ
之间的距离；％Ｏ）为ｔ时刻路径（ｉ，ｊ）上的信息量；ｎ为城市的数量。初始时刻，
各条路径上的信息素相等，设％（０）＝Ｃ为常数，蚂蚁忌似。Ｌ２，・・朋）在运动过程中根
据各条路径上的信息素量决定转移方向。基本蚁群算法所使用的状态转移规则被
称为随机比例规则，它给出了位于城市ｉ蚂蚁ｋ转移到城市的ｊ概率。ｐ：Ｏ）为在
ｔ时刻蚂蚁由城市转移到城市的状态转移概率
露（ｆ）一
若．『∈口Ｚ如俐ｔ
（４．１）
否则
式中口踟ｗ耐。＝｛０，１…，ｎ一１）表示蚂蚁当前能选择的城市集合：砌加。为禁忌
表，它记录蚂蚁ｋ己走过的城市：口为信息启发式因子，表示轨迹的相对重要性。。
为时刻的能见度，反映由城市转移到城市的期望程
∥为期望启发因子，表示能见度的相对重要性啪１
为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步
或者完成对所有个城市的遍历后，要对残留信息进行更新啪１。经过ｎ个时刻，所
有蚂蚁完成一次循环，各路径上的信息素按式（４．２）和（４．３）更新
％Ｏ＋刀）；（１一ｐｈｆ（ｆ）＋△％
（４．２）
△％。荟△％‘
（４．３）
式中，ｐ表示信息素挥发系数，则１一ＪＤ信息素残留因子，为防止信息的无限积累，
一小
１ｊ一
纠一％
晰一纠
绁ｈ
—Ｖ一
“
鱼
咄
｜一Ｖ觎
一
廊
。
湖北工业大学硕士学位论文
通常设置０＜ＪＤ＜１；△％表示本次循环中路径（ｉ，ｊ）上的信息素增量，△ｔ，‘表示
第Ｋ只蚂蚁在本次循环中留在路径（ｉ，ｊ）上的信息量。
根据信息素更新策略不同，Ｍ．Ｄｏｒｉｇｏ提出三种不同的基本蚁群算法模型啪１，
分别是Ａｎｔ—Ｃｙｃｌｅ模型，Ａｎｔ—Ｑｕａｎｔｉｔｙ模型及Ａｎｔ—Ｄｅｎｓｉｔｙ模型，其差别在于△％‘
的求法不同口１ｌ。
在Ａｎｔ—Ｃｙｃｌｅ模型中
ｆ
Ｑ
若第ｋ只蚂蚁在本次循环中经过（ｉ，ｊ）
△％‘一Ｊ
ｔ
（４．４）
Ｌ
Ｏ
否则
式中，Ｑ表示信息素强度，它在一定程度上影响算法的收敛速；ｋ表示第只蚂
蚁在本次循环中所走路径的总长度。
在Ａｎｔ—Ｑｕａｎｔｉｔｙ模型中
△％‘２｛，三二ｋ只蚂蚁在ｔ和ｔ＋１经过（ｉ，ｊ）
（４．５）
△巧。：ｒ
Ｑ
若第ｋ只蚂蚁在ｔ和”１经过（ｉ’ｊ）
。４ｑ
１…。’
式（４．５）和式（４．６）利用的是局部信息，即蚂蚁完成一步后更新路径上的信息
素；而式（４．４）利用的是全局信息，即蚂蚁完成一个循环后更新所有路径上的信息
４．４基本蚁群算法的实现
湖北工业大学硕士学位论文
图４．２蚁群算法的程序结构流程图
蚁群算法根据上述公式，当循环的次数达到实现定义好的ＮＣｍａｘ时或者所有
的蚂蚁都选择了同一种路径方式时，整个程序终止。其程序的基本步骤如下：
１初始化
参数初始化令ｔ＝０和循环次数ＮＣ＝０，设置最大循环次数ＮＣ眦ｘ，将ｍ只蚂蚁
随机地放到ｎ个城市，将每条边（ｉ，ｊ）上的信息素设为一个常数，且△％；０，将
出发点城市设置到禁忌表中
２迭代过程
Ｗｈｉｌｅ
ｎｏｔ结束条件ｄｏ
３７