基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第31页
湖北工业大学硕士学位论文 入法、最近邻算法、ｒ—ｏｐｔ算法、混合算法、概率算法等。智能演化算法禁忌搜索 方法、遗传算法、模拟退火算法，蚁群算法，粒子群算法，郭涛算法。 传统方法： ｌ精确算法 （１）线性规划方法 这是求解ＴＳＰ的最早的一种算法，主要是采用整数规划中的割平面法，即先 求解模型中由前二个约束构成的松驰ＬＰ问题，然后通过增加不等式约束产生割平 面，逐渐收敛到最优解。Ｄｚｎｔｚｉｇ等人早在１９５４年就求解过Ⅳ一４２的ＴＳＰ最优解…
湖北工业大学硕士学位论文
Ｓａｌｅｓｍａｎ
Ｐｒｏｂｌｅｍ，简称ＴＳＰ）。
ＴＳＰ问题是经典的组合优化问题：给定Ｎ个城市，有一个旅行商从某一城市出
发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回
路径【７１。也可用图论描述设ｃ＝｛ｏ，１，・・研一Ｕ是ｎ个城市的集合，￡＝职『Ｉｑ，ｃ『∈ｃ】．任
是集合中元素城市两连接的集合，
ｄ；ｆＯ，．ｊ『＝１，２，…甩）是２：ｆ『距离，即
略＝√＠一工Ｊ）２＋（ｙ；一ｙ∥，Ｇ一（ｃ，￡）是一个有向图，从有向图Ｇ中找出长度最短
的Ｈｉｍｉｌｔｏｎ圈。
ＴＳＰ问题的搜索空间随着城市数Ｎ的增大而迅猛增大，所有的路线组合数为
仍一１）！／２，这就产生了所谓的“组合爆炸’’问题。如果万一５０，则共有３．０４１４×１０６２
条路线。若采用穷举搜索法在如此庞大的搜索空间中寻求最优解，即使是使用每
秒计算一亿次的巨行计算机，所需时间也要为５×１０４８年，这显然是不现实的。
作为图论的经典问题，ＴＳＰ问题一直是一个在工程规划、地理信息系统、军事
等领域应用十分广泛的问题，对该问题的研究有着重要的理论和应用价值。
３．４．１
ＴＳＰ问题的意义
ＴＳＰ问题是最有代表性的优化组合问题之一，它的应用已逐步渗透到各个技术
领域和我们的日常生活中，至今还有不少学者在从事这方面的研究工作，一些项
目还得到美国军方的资助。ＴＳＰ问题无论是在理论上还是实际应用上都有非常重要
的意义。
ＴＳＰ问题在图论的意义下就是所谓的最小Ｈｉｍｉｌｔｏｎｎ踟圈问题，在许多领域有
着广泛的应用，常作为比较算法性能的标志。而且ＴＳＰ问题是已知的几百个ＮＰ完
全问题中的一个。研究它的重要性在于所有的ＮＰ完全问题在数学上都等价于ＴＳＰ。
许多实际问题也都可抽象为ＴＳＰ问题，比如说交通管理，网络路由以及大规模的
生产过程。
ＴＳＰ问题还可延伸到其他行业，如运输业、后勤服务业。然而，由于ＴＳＰ问题
随着问题规模的增大会产生组合爆炸的问题，因而寻找其实际而高效的算法就显
得非常重要了。
３．４．２
ＴＳＰ问题的求解方法
在求解ＴＳＰ的算法的过程中，人们一直在寻找切实有效的方法，按其出现的
时间大致可分为传统算法和智能演化算法。传统方法有精确算法和近似优化算法，
精确算法又有线性规划方法、动态规划方法、分支定界方法等，而近似算法有插
湖北工业大学硕士学位论文
入法、最近邻算法、ｒ—ｏｐｔ算法、混合算法、概率算法等。智能演化算法禁忌搜索
方法、遗传算法、模拟退火算法，蚁群算法，粒子群算法，郭涛算法。
传统方法：
ｌ精确算法
（１）线性规划方法
这是求解ＴＳＰ的最早的一种算法，主要是采用整数规划中的割平面法，即先
求解模型中由前二个约束构成的松驰ＬＰ问题，然后通过增加不等式约束产生割平
面，逐渐收敛到最优解。Ｄｚｎｔｚｉｇ等人早在１９５４年就求解过Ⅳ一４２的ＴＳＰ最优解
７０年代中期对于ＴＳＰ多面体理论的研究ｎ钊，产生了一些比较有效的不等式约束，
如子回路消去不等式、梳子不等、团树不等式等等。但是，由于该方法在寻找割
平面时常常要凭借经验，因此，后来很少作为一般方法使用。
（２）动态规划算法
记ｓ为集合｛２，３，…挖｝的子集，七∈ｓ，ｃ岱，七）为从１出发遍历ｓ中的点并终止
在ｋ的最优行程。由于动态规划算法的空间复杂度为疗・２“故一般除了很小规模的
问题外，几乎不予采用。
（３）分支定界算法
分支定界法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制
搜索进程，使之能向着状态空间树上有最优解的分支推进，以便尽快找出一个最
优解。该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的分支
定界法。以分派问题为界通过求解相应的分派问题，得到ＴＳＰ的一个下界，以此
进行分支定界搜索。这是一种使用较多的分支定界算法。以匹配问题为界通过求
解相应的匹配问题，得到ＴＳＰ的一个下界，以此进行分支定界搜索。一该方法适
用于对称型ＴＳＰ。以最小树问题为界通过求解相应的最小树问题，得到ＴＳＰ的一个
下界。虽说分支定界法对于较大规模的ＴＳＰ问题并不十分有效，可有时却被用来
求解近似解。而且，将分支定界法与一些启发式算法相结合，常常能获得一些意
外的成功。
２近似算法
（１）插入算法
插入型算法可按插入规则的不同而分为若干类，其一般思想为：
步骤１：通过某种插入方式选择插入边（ｉ，ｊ）和插入点ｋ，将ｋ插入ｉ和ｊ之
间，形成（…ｉ，ｋ，ｊ…）。
步骤２：依次进行直至形成回路解。
（２）最近邻算法
２７
湖北工业大学硕士学位论文
步骤１：任取一出发点
步骤２：依次取最近的点加入当前解中直至形成回路解。
（３）ｒ—ｏｐｔ算法
该方法是一种局部改进搜索算法，其思想是对给定的初始回路，通过每次交
换ｒ条边来改进当前解ｎ
５１。对不同的ｒ，根据大量计算发现，３一ｏｐｔ法比２一ｏｐｔ法
好，而４一ｏｐｔ，５一ｏｐｔ等并不比３一ｏｐｔ好，况且ｒ越大，运算时间越长。所以一般
采用３一ｏｐｔ法。
（４）混合算法
用某个近似算法求得初始解，然后借助一个或者若干个ｒ—ｏｐｔ算法对解加以
改进。这种混合型算法往往能获得较好的解，但也很耗时。
智能方法：
２０世纪年６０代以来，一些新颖的优化算法，如模拟退火、遗传算法、禁忌搜
索、人工神经网络、蚁群算法、粒子群算法、郭涛算法等，通过模拟或揭示某些
自现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智
能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段由于这
些算法构造的直观性和自然机理，通常称作智能演化算法，或称为现代启发式算
法。引入智能演化算法的原因在于避免陷人局部最优解，希望得到更好的解上界。
１模拟退火算法（Ｓｉｍｕｌａｔｅｄ
Ａｎｎｅａｌｉｎｇ，简称ＳＡ）
ＳＡ应用于ＴＳＰ取得了非常好的解，其缺点在于搜索速度慢，因此就出现了一
些ＳＡ的改进算法ｎ
６１。也经常与其他的局部搜索方法关于问题的演化算法研究相结
合，如ＬＫ算法等，取长补短，以取得更好的搜索速度和解质量。
２遗传算法（Ｇｅｎｅｔｉｃ
Ａｌｇｏｒｉｔｈｍ，简称ＧＡ）
在求解ＴＳＰ的过程中，ＧＡ存在的问题是收敛到局部最优解，而非全局最优解，
以及收敛速度慢ｎ掣。同样，它也经常被用来与其他方法相结合，以得到更好的算
法。
３禁忌搜索算法（Ｔａｂｏｏ
Ｓｅａｒｃｈ，简称ＴＳ）
禁忌搜索应用于ＴＳＰ，其目的在于更细致地搜索局优解近邻，困难之处在于禁
忌表的设计以及有效管理。遗撼的是，ＴＳ在搜索速度和解的精度都无法与３一ｏｐｔ
相比，因此，现在的一些研究人员将目标转向并行计算，到目前为止，还没有好
的结论。
４人工神经网络（Ａｒｔｉｆｉｃｉａｌ
Ｎｅｕｒａｌ
Ｎｅｔｗｏｒｋ，简称ＡＮＮ）
ＡＮＮ在求解ＴＳＰ中获得了一定的成功，但无论从精度还是从计算时间上，ＡＮＮ
算法无法与经典算法相抗衡。因此，现在有很多工作是对神经网络的改造。．