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