基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第33页
湖北工业大学硕士学位论文 ５蚁群算法（Ａｎｔ Ｃ０１０ｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，简称ＡＣＯ） ＡＣＯ是一种新型的模拟进化算法。它是一种启发式算法，来源于对蚂蚁群体搜 索行为的研究，它还充分模拟了实际蚁群寻求最短路径的协作优化特性。由于蚂 蚁寻求最短路径的行为类似于问题的解决过程，因而蚁群算法非常适合求解ＴＳＰ 问题。现在ＡＣＯ中主要面临的问题是蚂蚁信息素的积累和挥发机制的选择ｎ ８ｌ。 ６粒子群算法（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ …
湖北工业大学硕士学位论文
步骤１：任取一出发点
步骤２：依次取最近的点加入当前解中直至形成回路解。
（３）ｒ—ｏｐｔ算法
该方法是一种局部改进搜索算法，其思想是对给定的初始回路，通过每次交
换ｒ条边来改进当前解ｎ
５１。对不同的ｒ，根据大量计算发现，３一ｏｐｔ法比２一ｏｐｔ法
好，而４一ｏｐｔ，５一ｏｐｔ等并不比３一ｏｐｔ好，况且ｒ越大，运算时间越长。所以一般
采用３一ｏｐｔ法。
（４）混合算法
用某个近似算法求得初始解，然后借助一个或者若干个ｒ—ｏｐｔ算法对解加以
改进。这种混合型算法往往能获得较好的解，但也很耗时。
智能方法：
２０世纪年６０代以来，一些新颖的优化算法，如模拟退火、遗传算法、禁忌搜
索、人工神经网络、蚁群算法、粒子群算法、郭涛算法等，通过模拟或揭示某些
自现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智
能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段由于这
些算法构造的直观性和自然机理，通常称作智能演化算法，或称为现代启发式算
法。引入智能演化算法的原因在于避免陷人局部最优解，希望得到更好的解上界。
１模拟退火算法（Ｓｉｍｕｌａｔｅｄ
Ａｎｎｅａｌｉｎｇ，简称ＳＡ）
ＳＡ应用于ＴＳＰ取得了非常好的解，其缺点在于搜索速度慢，因此就出现了一
些ＳＡ的改进算法ｎ
６１。也经常与其他的局部搜索方法关于问题的演化算法研究相结
合，如ＬＫ算法等，取长补短，以取得更好的搜索速度和解质量。
２遗传算法（Ｇｅｎｅｔｉｃ
Ａｌｇｏｒｉｔｈｍ，简称ＧＡ）
在求解ＴＳＰ的过程中，ＧＡ存在的问题是收敛到局部最优解，而非全局最优解，
以及收敛速度慢ｎ掣。同样，它也经常被用来与其他方法相结合，以得到更好的算
法。
３禁忌搜索算法（Ｔａｂｏｏ
Ｓｅａｒｃｈ，简称ＴＳ）
禁忌搜索应用于ＴＳＰ，其目的在于更细致地搜索局优解近邻，困难之处在于禁
忌表的设计以及有效管理。遗撼的是，ＴＳ在搜索速度和解的精度都无法与３一ｏｐｔ
相比，因此，现在的一些研究人员将目标转向并行计算，到目前为止，还没有好
的结论。
４人工神经网络（Ａｒｔｉｆｉｃｉａｌ
Ｎｅｕｒａｌ
Ｎｅｔｗｏｒｋ，简称ＡＮＮ）
ＡＮＮ在求解ＴＳＰ中获得了一定的成功，但无论从精度还是从计算时间上，ＡＮＮ
算法无法与经典算法相抗衡。因此，现在有很多工作是对神经网络的改造。．
湖北工业大学硕士学位论文
５蚁群算法（Ａｎｔ
Ｃ０１０ｎｙ
Ｏｐｔｉｍｉｚａｔｉｏｎ，简称ＡＣＯ）
ＡＣＯ是一种新型的模拟进化算法。它是一种启发式算法，来源于对蚂蚁群体搜
索行为的研究，它还充分模拟了实际蚁群寻求最短路径的协作优化特性。由于蚂
蚁寻求最短路径的行为类似于问题的解决过程，因而蚁群算法非常适合求解ＴＳＰ
问题。现在ＡＣＯ中主要面临的问题是蚂蚁信息素的积累和挥发机制的选择ｎ
８ｌ。
６粒子群算法（Ｐａｒｔｉｃｌｅ
Ｓｗａｒｍ
０ｐｔｉｍｉｚａｔｉｏｎ，简称ＰＳＯ）
ＰＳＯ是源于鸟群和鱼群群体觅食运动行为研究结果的启发，与ＧＡ比较，ＰＳ０
算法的优势在于简单、易于实现同时又有深刻的智能背景，既适合科学研究，又
特别适合工程应用。因此，ＰＳ０算法一提出，立刻引起了演化计算等领域的学者们
的广泛关注，并在短短的几年时间里出现大量的研究成果，形成了一个研究热点。
ＰＳＯ算法关键在于位置和速度的表示ｎ引，以及这些量的运算规律和粒子的运动方程
如何定义。
７郭涛算法（Ｇｕｏ
Ｔａｏ
ａｌｇｏｒｉｔｈｍ，简称ＧＴ）
ＧＴ可能是目前国际上求解ＴＳＰ问题最快的演化算法，算法中提出了一种求解
对称ＴＳＰ问题的高效算子Ｉｎｖｅｒ—ｏｖｅｒ算子，郭涛算法比起其它只是单纯基于杂交
算子的算法来说，在求解质量和速度上效果要好很多，主要在于它能够充分利用
群体信息。现在的工作在于不断改进算子以提高求解大规模ＴＳＰ问题的质量和速
度。
３．５本章小结
本章分析了贴片机贴装工艺流程，结合实际情况，在合理假设的基础上创建
了贴装工艺数学模型，并将求最优贴装时间转化为求贴片机最优路径问题。阐述
了贴片机最优路径问题即是经典的组合优化问题～ＴＳＰ问题。分析了求解ＴＳＰ问题
的若干种方法。
湖北工业大学硕士学位论文
第４章蚁群算法原理分析
自然界的蚂蚁在觅食过程中，能在其经过的路径上分泌一种具有气味的化
学物质，称为信息激素乜０。。蚂蚁间通过这种信息激素来进行信息传递，并指导自
己的运动方向。蚂蚁在走过的路径上会留下信息激素，同时信息激素随着时间的
消逝会逐渐挥发，信息激素浓度越高的路径吸引的蚂蚁越多，而某一路径上走过
的蚂蚁越多，此路径上蚂蚁留下的信息激素也就越多，则后来蚂蚁选择该路径的
概率也就越大，从而增加了该路径被选择的可能性。随着时间的推移，蚂蚁就会
集中到信息激素浓度最大的一条路径上，而这条路径就是从蚁巢到食物源的最短
路径。通过仿真模拟实际蚂蚁的觅食行为，建立的蚂蚁算法在许多相当困难的组
合优化问题的求解中体现了极强的寻优能力和较好的性质。
求解ＴＳＰ问题的改进蚂蚁算法个体之间不断进行信息交流和传递，有利于发
现较好解。单个个体容易收敛于局部最优，多个个体通过合作，可以很快收敛于
解空间的某个子集，有利于对解空间的进一步探索，从而发现较好解。并且蚂蚁
算法模型简单，算法参数设置简单，便于实际应用。所以本文选择蚁群算法进行
贴片机路径优化研究。
４．１基本蚁群算法的产生
蚂蚁是大家司空见惯的一种昆虫，而它们的群体合作的精神令人钦佩。它们
的觅食、御敌、筑巢之精巧令人惊叹。２０世９０年代初意大利学者Ｄｏｒｉｇｏ，Ｍａｎｉｅｚｚｏ
首先提出“蚂蚁系统瞳ｕ（Ａｎｔ
Ｃｏｌｏｎｙ
０ｐｔｉｍｉｚａｔｉｏｎ，简称ＡＣＯ）’’。就是依照蚂蚁
觅食原理，设计的一个群体智能的算法。
意大利学者Ｄｏｒｉｇｏ于１９９１年提出了第一个蚂蚁算法的模型蚂蚁系统（Ａｎｔ
Ｓｙｓｔｅｍ，ＡＳ）用于求解如旅行商问题般的组合优化问题。在随后几年的时间里，
Ｄｏｒｉｇｏ等人从两方面对ＡＳ进行了发展，一方面将ＡＳ不断应用到各种具体问题之
中；另一方面又针对ＡＳ中存在的问题进行了改进，提出新的算法模型。１９９６年
Ｇ硼ｂａｒｄｅｌｌａ和Ｄｏｒｉｇｏ在这些研究的基础上，进一步总结给出了求解组合优化问
题的蚂蚁算法元模型一蚂蚂蚁体优化（Ａｎｔ
Ｃｏｌｏｎｙ
Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）同时，
这一研究也逐渐引起了其他科学家的关注。为了克服蚂蚁算法存在的收敛慢、容
易出现停滞现象、算法运行时长等缺点，人们提出了许多改进算法。德国学者
Ｔｈｏｍａｓｔｕｚｌｅ和Ｈｏｌｅｒｈ００ｓ提出的一种改进算法，最大最小蚂蚁系统（Ｍａｘ—Ｍｉｎ
Ａｎｔ