基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第34页
湖北工业大学硕士学位论文 第４章蚁群算法原理分析 自然界的蚂蚁在觅食过程中，能在其经过的路径上分泌一种具有气味的化 学物质，称为信息激素乜０。。蚂蚁间通过这种信息激素来进行信息传递，并指导自 己的运动方向。蚂蚁在走过的路径上会留下信息激素，同时信息激素随着时间的 消逝会逐渐挥发，信息激素浓度越高的路径吸引的蚂蚁越多，而某一路径上走过 的蚂蚁越多，此路径上蚂蚁留下的信息激素也就越多，则后来蚂蚁选择该路径的 概率也就越大，从而增加了该路径被…
湖北工业大学硕士学位论文
５蚁群算法（Ａｎｔ
Ｃ０１０ｎｙ
Ｏｐｔｉｍｉｚａｔｉｏｎ，简称ＡＣＯ）
ＡＣＯ是一种新型的模拟进化算法。它是一种启发式算法，来源于对蚂蚁群体搜
索行为的研究，它还充分模拟了实际蚁群寻求最短路径的协作优化特性。由于蚂
蚁寻求最短路径的行为类似于问题的解决过程，因而蚁群算法非常适合求解ＴＳＰ
问题。现在ＡＣＯ中主要面临的问题是蚂蚁信息素的积累和挥发机制的选择ｎ
８ｌ。
６粒子群算法（Ｐａｒｔｉｃｌｅ
Ｓｗａｒｍ
０ｐｔｉｍｉｚａｔｉｏｎ，简称ＰＳＯ）
ＰＳＯ是源于鸟群和鱼群群体觅食运动行为研究结果的启发，与ＧＡ比较，ＰＳ０
算法的优势在于简单、易于实现同时又有深刻的智能背景，既适合科学研究，又
特别适合工程应用。因此，ＰＳ０算法一提出，立刻引起了演化计算等领域的学者们
的广泛关注，并在短短的几年时间里出现大量的研究成果，形成了一个研究热点。
ＰＳＯ算法关键在于位置和速度的表示ｎ引，以及这些量的运算规律和粒子的运动方程
如何定义。
７郭涛算法（Ｇｕｏ
Ｔａｏ
ａｌｇｏｒｉｔｈｍ，简称ＧＴ）
ＧＴ可能是目前国际上求解ＴＳＰ问题最快的演化算法，算法中提出了一种求解
对称ＴＳＰ问题的高效算子Ｉｎｖｅｒ—ｏｖｅｒ算子，郭涛算法比起其它只是单纯基于杂交
算子的算法来说，在求解质量和速度上效果要好很多，主要在于它能够充分利用
群体信息。现在的工作在于不断改进算子以提高求解大规模ＴＳＰ问题的质量和速
度。
３．５本章小结
本章分析了贴片机贴装工艺流程，结合实际情况，在合理假设的基础上创建
了贴装工艺数学模型，并将求最优贴装时间转化为求贴片机最优路径问题。阐述
了贴片机最优路径问题即是经典的组合优化问题～ＴＳＰ问题。分析了求解ＴＳＰ问题
的若干种方法。
湖北工业大学硕士学位论文
第４章蚁群算法原理分析
自然界的蚂蚁在觅食过程中，能在其经过的路径上分泌一种具有气味的化
学物质，称为信息激素乜０。。蚂蚁间通过这种信息激素来进行信息传递，并指导自
己的运动方向。蚂蚁在走过的路径上会留下信息激素，同时信息激素随着时间的
消逝会逐渐挥发，信息激素浓度越高的路径吸引的蚂蚁越多，而某一路径上走过
的蚂蚁越多，此路径上蚂蚁留下的信息激素也就越多，则后来蚂蚁选择该路径的
概率也就越大，从而增加了该路径被选择的可能性。随着时间的推移，蚂蚁就会
集中到信息激素浓度最大的一条路径上，而这条路径就是从蚁巢到食物源的最短
路径。通过仿真模拟实际蚂蚁的觅食行为，建立的蚂蚁算法在许多相当困难的组
合优化问题的求解中体现了极强的寻优能力和较好的性质。
求解ＴＳＰ问题的改进蚂蚁算法个体之间不断进行信息交流和传递，有利于发
现较好解。单个个体容易收敛于局部最优，多个个体通过合作，可以很快收敛于
解空间的某个子集，有利于对解空间的进一步探索，从而发现较好解。并且蚂蚁
算法模型简单，算法参数设置简单，便于实际应用。所以本文选择蚁群算法进行
贴片机路径优化研究。
４．１基本蚁群算法的产生
蚂蚁是大家司空见惯的一种昆虫，而它们的群体合作的精神令人钦佩。它们
的觅食、御敌、筑巢之精巧令人惊叹。２０世９０年代初意大利学者Ｄｏｒｉｇｏ，Ｍａｎｉｅｚｚｏ
首先提出“蚂蚁系统瞳ｕ（Ａｎｔ
Ｃｏｌｏｎｙ
０ｐｔｉｍｉｚａｔｉｏｎ，简称ＡＣＯ）’’。就是依照蚂蚁
觅食原理，设计的一个群体智能的算法。
意大利学者Ｄｏｒｉｇｏ于１９９１年提出了第一个蚂蚁算法的模型蚂蚁系统（Ａｎｔ
Ｓｙｓｔｅｍ，ＡＳ）用于求解如旅行商问题般的组合优化问题。在随后几年的时间里，
Ｄｏｒｉｇｏ等人从两方面对ＡＳ进行了发展，一方面将ＡＳ不断应用到各种具体问题之
中；另一方面又针对ＡＳ中存在的问题进行了改进，提出新的算法模型。１９９６年
Ｇ硼ｂａｒｄｅｌｌａ和Ｄｏｒｉｇｏ在这些研究的基础上，进一步总结给出了求解组合优化问
题的蚂蚁算法元模型一蚂蚂蚁体优化（Ａｎｔ
Ｃｏｌｏｎｙ
Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）同时，
这一研究也逐渐引起了其他科学家的关注。为了克服蚂蚁算法存在的收敛慢、容
易出现停滞现象、算法运行时长等缺点，人们提出了许多改进算法。德国学者
Ｔｈｏｍａｓｔｕｚｌｅ和Ｈｏｌｅｒｈ００ｓ提出的一种改进算法，最大最小蚂蚁系统（Ｍａｘ—Ｍｉｎ
Ａｎｔ
湖北工业大学硕士学位论文
Ｓｙｓｔｅｍ，ＭＭＡＳ），在解决，等问题时结果要优于一般的ＡＣＯ类算法。一些学者还把
蚂蚁算法与其它的算法相结合。意大利学者Ｆａｂｉｏ，Ａｂｂａｔｔｉｓｔａ等人受遗传算法
的启发，提出蚂蚁算法和遗传算法相结合的混合优化算法。近年来，蚂蚁算法逐
渐被国内学者了解，出现了一些介绍性文献。其后国内学者在蚂蚁算法的应用研
究方面如优化，路由调度等开展了一些工作，提出了一些改进算法，其中有代表
性的主要有：吴庆洪等人提出的具有变异特征的蚂蚁算法ＭＳＡ（Ｍｕｔａｔｉｏｎ
Ａｎｔ
Ｓｙｓｔｅｍ）；陈烨提出的带杂交算子的蚂蚁算法ＣＡＣＳ（Ｃｒｏｓｓｅｄ
Ａｎｔ
Ｃ０１０ｎｙ
Ｓｙｓｔｅｍ）；
郝晋等人提出的具有扰动特性的蚂蚁算法ＳＤＡＳ（Ｓｔｏｃｈａｓｔｉｃ
Ｄｉｓｔｕｒｂｅｄ
Ａｎｔ
Ｓｙｓｔｅｍ）；王颖等人提出的自适应蚂蚁算法ＡＡＳ（Ａｄａｐｔｉｖｅ
Ａｎｔ
Ｓｙｓｔｅｍ）。
蚂蚁算法是一种源于大自然中生物世界的新的仿生进化算法，具有很强的通
用性和鲁棒性，从提出到现在只有短短的十几年时间，但其在离散型组合优化问
题中，表现得很突出，引起了广大学者的关注。自从蚂蚁算法在著名的旅行商求
解ＴＳＰ问题的改进蚂蚁算法问题和工件排序问题上取得成效以来，已陆续渗透到
其它问题领域中，如二次分配问题，ｊｏｂ—ｓｈｏｐ问题、图着色问题、大规模集成电
路设计、通讯网络中的负载问题、网络路由选择、车辆调度问题、机器人视线规
划等等，表现出良好的性能，显示出其强大的生命力和美好的发展潜力。
４．２基本蚁群算法的原理
蚁群算法是对真实蚁群行为研究而提出的。仿生学家经过长期研究发现蚂蚁
虽然没有视觉，但运动时会通过在路径上释放出一种特殊的分泌物一信息素来寻
找路径。，使得一定范围内的其它蚂蚁能够感觉到这种物质，且倾向于朝着该物质
强度高的方向移动，因此，蚁群的集体行为表现为一种信息正反馈现象某条路径
经过的蚂蚁数越多，其上留下的信息量也就越多当然，随时间的推移会逐渐蒸发
掉一部分，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上信息素的
强度。这样最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间
的流逝而逐渐减少，最终整个蚁群会找出最优路径。在整个寻径过程中，虽然单
只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群具有非常高的自组织
性，蚂蚁之间交换着路径信息，最终通过蚁群的集体自催化行为找出最优路径瞳刳。
下面通过图４．１来说明蚁群的搜索原理。
３１