基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第39页
湖北工业大学硕士学位论文 整个算法的运行效率和快速反应的能力。 ４．３基本蚁群算法数学模型 以求解平面上ｎ个城市的ＴＳＰ问题用（０，ｌ，…ｎ一１）表示城市序号来说明基本 蚁群算法啪１。 首先引入如下记号：ｍ为蚁群中的蚂蚁数；ｄ。Ｏ，ｊ『一１’２，…，１）为城市ｉ和城市ｊ 之间的距离；％Ｏ）为ｔ时刻路径（ｉ，ｊ）上的信息量；ｎ为城市的数量。初始时刻， 各条路径上的信息素相等，设％（０）＝Ｃ为常数，蚂蚁忌似。Ｌ２，・・朋）在运动过程中根 据…
湖北工业大学硕士学位论文
４．２．２蚁群优化的特点
从蚁群算法的原理可以看出，蚁群的觅食行为实际上是一种分布式的协同
优化机制，单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径，但找到最短路径
的可能性极小，只有当多只蚂蚁组成蚁群时，其集体行为才突现出蚂蚁的智能一发
现最短路径的能力，在寻找最短路径的过程中，蚁群使用一种间接通信方式，即
通过向所经过的路径上释放一定量的信息素，其他蚂蚁通过感知这种物质的强弱
来选择下一步要走的路，这种个体间通过改变环境、感知环境的变化来彼此间接
通讯的方式机制被称为协同机制，该通信机制可以非常容易地扩展到人工多主体
模型，即首先用状态变量来表示问题的状态，然后让人工主体只访问局部状态变
量信息，因此，人工蚂蚁可以通过更新问题的状态变量来模拟真实蚂蚁更新信息
素的行为。
在蚁群的觅食行为中，另一种重要的方面是自催化机制和解的隐式评估，自
催化机制实际上是一种正反馈机制，解的隐式评估指蚁群将先走完较短的路径，
自催化机制和解的隐式评估相结合，极大地提高了问题的求解效率，即对于越短
的路径蚂蚁将越早走完，从而使更多的蚂蚁将会选择该路径，自催化机制对基于
群体的算法非常有效，如在遗传算法中，通过选择和复制机制来实现，因为他奖
励好的个体，可以指导搜索方向，在使用自催化机制时，要努力避免早熟现象。
在蚁群算法中，使用信息素蒸发和随机状态转移来弥补自催化机制的缺陷。
蚁群算法的主要特点概括如下嘶３
（１）采用分布式控制，不存在中心控制。
（２）每个个体只能感知局部的信息，不直接使用全局信息。
（３）个体可改变环境，并通过环境来进行间接通讯。
（４）具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的
智能。
（５）是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会
求得全局最优解。
（６）其优化过程不依赖于优化问题本身的严格数学性质，如连续性，可导性
及目标函数和约束函数的精确数学描述。
（７）是一类基于多主体的智能算法，各主体之间通过相互协作来更好地适应
环境。
（８）具有潜在的并行性，其搜索过程不是从一点出发，而是从多个点同时进
行，这种分布式多智能体的协作是异步并发进行的，分布并行的模式将大大提高
湖北工业大学硕士学位论文
整个算法的运行效率和快速反应的能力。
４．３基本蚁群算法数学模型
以求解平面上ｎ个城市的ＴＳＰ问题用（０，ｌ，…ｎ一１）表示城市序号来说明基本
蚁群算法啪１。
首先引入如下记号：ｍ为蚁群中的蚂蚁数；ｄ。Ｏ，ｊ『一１’２，…，１）为城市ｉ和城市ｊ
之间的距离；％Ｏ）为ｔ时刻路径（ｉ，ｊ）上的信息量；ｎ为城市的数量。初始时刻，
各条路径上的信息素相等，设％（０）＝Ｃ为常数，蚂蚁忌似。Ｌ２，・・朋）在运动过程中根
据各条路径上的信息素量决定转移方向。基本蚁群算法所使用的状态转移规则被
称为随机比例规则，它给出了位于城市ｉ蚂蚁ｋ转移到城市的ｊ概率。ｐ：Ｏ）为在
ｔ时刻蚂蚁由城市转移到城市的状态转移概率
露（ｆ）一
若．『∈口Ｚ如俐ｔ
（４．１）
否则
式中口踟ｗ耐。＝｛０，１…，ｎ一１）表示蚂蚁当前能选择的城市集合：砌加。为禁忌
表，它记录蚂蚁ｋ己走过的城市：口为信息启发式因子，表示轨迹的相对重要性。。
为时刻的能见度，反映由城市转移到城市的期望程
∥为期望启发因子，表示能见度的相对重要性啪１
为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步
或者完成对所有个城市的遍历后，要对残留信息进行更新啪１。经过ｎ个时刻，所
有蚂蚁完成一次循环，各路径上的信息素按式（４．２）和（４．３）更新
％Ｏ＋刀）；（１一ｐｈｆ（ｆ）＋△％
（４．２）
△％。荟△％‘
（４．３）
式中，ｐ表示信息素挥发系数，则１一ＪＤ信息素残留因子，为防止信息的无限积累，
一小
１ｊ一
纠一％
晰一纠
绁ｈ
—Ｖ一
“
鱼
咄
｜一Ｖ觎
一
廊
。
湖北工业大学硕士学位论文
通常设置０＜ＪＤ＜１；△％表示本次循环中路径（ｉ，ｊ）上的信息素增量，△ｔ，‘表示
第Ｋ只蚂蚁在本次循环中留在路径（ｉ，ｊ）上的信息量。
根据信息素更新策略不同，Ｍ．Ｄｏｒｉｇｏ提出三种不同的基本蚁群算法模型啪１，
分别是Ａｎｔ—Ｃｙｃｌｅ模型，Ａｎｔ—Ｑｕａｎｔｉｔｙ模型及Ａｎｔ—Ｄｅｎｓｉｔｙ模型，其差别在于△％‘
的求法不同口１ｌ。
在Ａｎｔ—Ｃｙｃｌｅ模型中
ｆ
Ｑ
若第ｋ只蚂蚁在本次循环中经过（ｉ，ｊ）
△％‘一Ｊ
ｔ
（４．４）
Ｌ
Ｏ
否则
式中，Ｑ表示信息素强度，它在一定程度上影响算法的收敛速；ｋ表示第只蚂
蚁在本次循环中所走路径的总长度。
在Ａｎｔ—Ｑｕａｎｔｉｔｙ模型中
△％‘２｛，三二ｋ只蚂蚁在ｔ和ｔ＋１经过（ｉ，ｊ）
（４．５）
△巧。：ｒ
Ｑ
若第ｋ只蚂蚁在ｔ和”１经过（ｉ’ｊ）
。４ｑ
１…。’
式（４．５）和式（４．６）利用的是局部信息，即蚂蚁完成一步后更新路径上的信息
素；而式（４．４）利用的是全局信息，即蚂蚁完成一个循环后更新所有路径上的信息
４．４基本蚁群算法的实现