基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第32页
湖北工业大学硕士学位论文 步骤１：任取一出发点 步骤２：依次取最近的点加入当前解中直至形成回路解。 （３）ｒ—ｏｐｔ算法 该方法是一种局部改进搜索算法，其思想是对给定的初始回路，通过每次交 换ｒ条边来改进当前解ｎ ５１。对不同的ｒ，根据大量计算发现，３一ｏｐｔ法比２一ｏｐｔ法 好，而４一ｏｐｔ，５一ｏｐｔ等并不比３一ｏｐｔ好，况且ｒ越大，运算时间越长。所以一般 采用３一ｏｐｔ法。 （４）混合算法 用某个近似算法求得初始解，然后借助一个或…
湖北工业大学硕士学位论文
入法、最近邻算法、ｒ—ｏｐｔ算法、混合算法、概率算法等。智能演化算法禁忌搜索
方法、遗传算法、模拟退火算法，蚁群算法，粒子群算法，郭涛算法。
传统方法：
ｌ精确算法
（１）线性规划方法
这是求解ＴＳＰ的最早的一种算法，主要是采用整数规划中的割平面法，即先
求解模型中由前二个约束构成的松驰ＬＰ问题，然后通过增加不等式约束产生割平
面，逐渐收敛到最优解。Ｄｚｎｔｚｉｇ等人早在１９５４年就求解过Ⅳ一４２的ＴＳＰ最优解
７０年代中期对于ＴＳＰ多面体理论的研究ｎ钊，产生了一些比较有效的不等式约束，
如子回路消去不等式、梳子不等、团树不等式等等。但是，由于该方法在寻找割
平面时常常要凭借经验，因此，后来很少作为一般方法使用。
（２）动态规划算法
记ｓ为集合｛２，３，…挖｝的子集，七∈ｓ，ｃ岱，七）为从１出发遍历ｓ中的点并终止
在ｋ的最优行程。由于动态规划算法的空间复杂度为疗・２“故一般除了很小规模的
问题外，几乎不予采用。
（３）分支定界算法
分支定界法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制
搜索进程，使之能向着状态空间树上有最优解的分支推进，以便尽快找出一个最
优解。该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的分支
定界法。以分派问题为界通过求解相应的分派问题，得到ＴＳＰ的一个下界，以此
进行分支定界搜索。这是一种使用较多的分支定界算法。以匹配问题为界通过求
解相应的匹配问题，得到ＴＳＰ的一个下界，以此进行分支定界搜索。一该方法适
用于对称型ＴＳＰ。以最小树问题为界通过求解相应的最小树问题，得到ＴＳＰ的一个
下界。虽说分支定界法对于较大规模的ＴＳＰ问题并不十分有效，可有时却被用来
求解近似解。而且，将分支定界法与一些启发式算法相结合，常常能获得一些意
外的成功。
２近似算法
（１）插入算法
插入型算法可按插入规则的不同而分为若干类，其一般思想为：
步骤１：通过某种插入方式选择插入边（ｉ，ｊ）和插入点ｋ，将ｋ插入ｉ和ｊ之
间，形成（…ｉ，ｋ，ｊ…）。
步骤２：依次进行直至形成回路解。
（２）最近邻算法
２７
湖北工业大学硕士学位论文
步骤１：任取一出发点
步骤２：依次取最近的点加入当前解中直至形成回路解。
（３）ｒ—ｏｐｔ算法
该方法是一种局部改进搜索算法，其思想是对给定的初始回路，通过每次交
换ｒ条边来改进当前解ｎ
５１。对不同的ｒ，根据大量计算发现，３一ｏｐｔ法比２一ｏｐｔ法
好，而４一ｏｐｔ，５一ｏｐｔ等并不比３一ｏｐｔ好，况且ｒ越大，运算时间越长。所以一般
采用３一ｏｐｔ法。
（４）混合算法
用某个近似算法求得初始解，然后借助一个或者若干个ｒ—ｏｐｔ算法对解加以
改进。这种混合型算法往往能获得较好的解，但也很耗时。
智能方法：
２０世纪年６０代以来，一些新颖的优化算法，如模拟退火、遗传算法、禁忌搜
索、人工神经网络、蚁群算法、粒子群算法、郭涛算法等，通过模拟或揭示某些
自现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智
能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段由于这
些算法构造的直观性和自然机理，通常称作智能演化算法，或称为现代启发式算
法。引入智能演化算法的原因在于避免陷人局部最优解，希望得到更好的解上界。
１模拟退火算法（Ｓｉｍｕｌａｔｅｄ
Ａｎｎｅａｌｉｎｇ，简称ＳＡ）
ＳＡ应用于ＴＳＰ取得了非常好的解，其缺点在于搜索速度慢，因此就出现了一
些ＳＡ的改进算法ｎ
６１。也经常与其他的局部搜索方法关于问题的演化算法研究相结
合，如ＬＫ算法等，取长补短，以取得更好的搜索速度和解质量。
２遗传算法（Ｇｅｎｅｔｉｃ
Ａｌｇｏｒｉｔｈｍ，简称ＧＡ）
在求解ＴＳＰ的过程中，ＧＡ存在的问题是收敛到局部最优解，而非全局最优解，
以及收敛速度慢ｎ掣。同样，它也经常被用来与其他方法相结合，以得到更好的算
法。
３禁忌搜索算法（Ｔａｂｏｏ
Ｓｅａｒｃｈ，简称ＴＳ）
禁忌搜索应用于ＴＳＰ，其目的在于更细致地搜索局优解近邻，困难之处在于禁
忌表的设计以及有效管理。遗撼的是，ＴＳ在搜索速度和解的精度都无法与３一ｏｐｔ
相比，因此，现在的一些研究人员将目标转向并行计算，到目前为止，还没有好
的结论。
４人工神经网络（Ａｒｔｉｆｉｃｉａｌ
Ｎｅｕｒａｌ
Ｎｅｔｗｏｒｋ，简称ＡＮＮ）
ＡＮＮ在求解ＴＳＰ中获得了一定的成功，但无论从精度还是从计算时间上，ＡＮＮ
算法无法与经典算法相抗衡。因此，现在有很多工作是对神经网络的改造。．
湖北工业大学硕士学位论文
５蚁群算法（Ａｎｔ
Ｃ０１０ｎｙ
Ｏｐｔｉｍｉｚａｔｉｏｎ，简称ＡＣＯ）
ＡＣＯ是一种新型的模拟进化算法。它是一种启发式算法，来源于对蚂蚁群体搜
索行为的研究，它还充分模拟了实际蚁群寻求最短路径的协作优化特性。由于蚂
蚁寻求最短路径的行为类似于问题的解决过程，因而蚁群算法非常适合求解ＴＳＰ
问题。现在ＡＣＯ中主要面临的问题是蚂蚁信息素的积累和挥发机制的选择ｎ
８ｌ。
６粒子群算法（Ｐａｒｔｉｃｌｅ
Ｓｗａｒｍ
０ｐｔｉｍｉｚａｔｉｏｎ，简称ＰＳＯ）
ＰＳＯ是源于鸟群和鱼群群体觅食运动行为研究结果的启发，与ＧＡ比较，ＰＳ０
算法的优势在于简单、易于实现同时又有深刻的智能背景，既适合科学研究，又
特别适合工程应用。因此，ＰＳ０算法一提出，立刻引起了演化计算等领域的学者们
的广泛关注，并在短短的几年时间里出现大量的研究成果，形成了一个研究热点。
ＰＳＯ算法关键在于位置和速度的表示ｎ引，以及这些量的运算规律和粒子的运动方程
如何定义。
７郭涛算法（Ｇｕｏ
Ｔａｏ
ａｌｇｏｒｉｔｈｍ，简称ＧＴ）
ＧＴ可能是目前国际上求解ＴＳＰ问题最快的演化算法，算法中提出了一种求解
对称ＴＳＰ问题的高效算子Ｉｎｖｅｒ—ｏｖｅｒ算子，郭涛算法比起其它只是单纯基于杂交
算子的算法来说，在求解质量和速度上效果要好很多，主要在于它能够充分利用
群体信息。现在的工作在于不断改进算子以提高求解大规模ＴＳＰ问题的质量和速
度。
３．５本章小结
本章分析了贴片机贴装工艺流程，结合实际情况，在合理假设的基础上创建
了贴装工艺数学模型，并将求最优贴装时间转化为求贴片机最优路径问题。阐述
了贴片机最优路径问题即是经典的组合优化问题～ＴＳＰ问题。分析了求解ＴＳＰ问题
的若干种方法。