基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第46页
湖北工业大学硕士学位论文 并且收集了一系列国际知名研究人员对ＴＳＰ问题的研究成果，之后还在不断更新 扩充。该问题库己成为国际上研究ＴＳＰ问题的通用测试集Ｈ刳。 表４．１几种改进蚁群算法测试结果 表４．１为测试结果，数字为选取城市数目。从表４．１可以看出，ＭＭＡＳ算法具 有最好的性能，其次是ＡＣＳ算法，通常情况下４％算法优于ＡＳ算法。 ４．８本章小结 本章全面阐述了蚁群算法的原理，分析了蚁群算法的优缺点，通过实验比较 了几种改进蚁群算法的…
湖北工业大学硕士学位论文
最优解附近提高解的质量和收敛速度，而且能够有效地避免早熟收敛¨引，是到目
前为止解决ＴＳＰ问题最好的蚁群算法。主要作了如下改进
（１）完成一次循环后，只有循环最优解或到全局最优解所属路径上的信息被
更新。
（２）为了避免算法过早收敛于非全局最优解，将各条路径上的信息素限制于
ｈ∽‰】之间，超出这个范围的值被强制设为ｆ晌或者是ｚ嘲，可以有效地避免某
条路径上的信息素远大于其它路径，使得蚂蚁都集中到一条路径上汹１。
（３）为使蚂蚁在算法初期能更多地搜索新的解决方案，初始时刻将各条路径上
的信息素都设为了僦。
（４）当所有蚂蚁完成一次循环后，按式和式对路径上的信息进行全局更新。
％Ｏ＋以）＝（１一ｐ心Ｏ）＋‘芦
（４．１５）
ｌ
１
若（ｉ，ｊ）∈最优路径
△露耐＝Ｊ
邝妇）
（４．１６）
Ｌ
。
否则
式中，ｐ表示信息素挥发系数，则１一ｐ信息素残留因子，为防止信息的无限
积累，通常设置（０＜ＪＤ＜１）；厂Ｏ妇）表示本次循环最优解或到目前为止找出的
全局最优解。
４．７几种改进的蚁群算法比较
与ＡＳ算法相比彳Ｓ加算法、ＡＣＳ算法及ＭＭＡＳ算法的共同之处在于加强了对最
优解的利用Ｈ０１。只有最优解所属路径上的信息素允许加耐３０１。但是，加强对最优
解的利用将会导致搜索中的停滞现象。在ＡＣＳ算法中通过增加局部信息素更新来
减少路径上的信息素量，从而使后面的蚂蚁选择该路径的可能性减少；在ＭＭＡＳ算
法中，通过限制信息量的范围，使路径上的信息量不会小于某一最小值，从而避
免了所有蚂蚁选择同一条路径的可能性，即避免了搜索中的停滞现象。
我们从ＴＳＰＬＩＢ问题库中选取几种有代表性研究得比较多并且己有己知最优解
的对称问题作为测试对象ｍ１，对前述几种算法进行性能评价。
ＴＳＰＬＩＢ是由一系列ＴＳＰ问题以及相关问题所组成的问题库。它于１９９０年Ｒｉｃｅ
大学并行计算研究中心举行的ＴＳＰ问题研讨会上建立：最初包含８４个测试问题，
４１
湖北工业大学硕士学位论文
并且收集了一系列国际知名研究人员对ＴＳＰ问题的研究成果，之后还在不断更新
扩充。该问题库己成为国际上研究ＴＳＰ问题的通用测试集Ｈ刳。
表４．１几种改进蚁群算法测试结果
表４．１为测试结果，数字为选取城市数目。从表４．１可以看出，ＭＭＡＳ算法具
有最好的性能，其次是ＡＣＳ算法，通常情况下４％算法优于ＡＳ算法。
４．８本章小结
本章全面阐述了蚁群算法的原理，分析了蚁群算法的优缺点，通过实验比较
了几种改进蚁群算法的性能，得到的结论是ＭＭＡＳ算法在解决ＴＳＰ问题上性能最好。
为下一章贴片机路径优化的实现提供了理论基础。
４２
湖北工业大学硕士学位论文
第５章贴片机路径优化系统实现
５．１贴片机器路径优化的几个原则
优化原则在很大程度上取决于设备的结构。对于Ｘ／Ｙ构架的设备，通常依照
下述原则命名其达到最小循环时间：
１、尽量大可能使多个贴装头同时拾取元件。
２、尽可能优先拾取同种元件。
３、拾取频率高的喂料器应安放在接近印制的位置，一般将其放在设备的前面，
接近主挡块。
４、在每个拾放循环过程中，都要使所有的贴装头满负荷，这样可以优化效率。
５、在一个拾放循环过程中，只从前面或后面拾取元件，而不是两边都取，这
样可以减少拾取时的移动路程。
６、为了减少拾取时的移动路在一个拾放循环过程中只沿着Ｘ坐标增加或Ｘ坐
标减少的方向拾取元件，而不能朝两个方向都运动。
７、一个循环中，按照ｘ和Ｙ坐标增加或ｘ和Ｙ坐标减少的顺序进行贴装，减
少贴装头的移动路程。
很显然，有几个原则在本质上是有矛盾的，这就意味着设备优化程序必须进
行折衷，这也取决于应用过程的复杂性。对于每一个原则都进行权衡后，设备优
化程序就可以在相对矛盾的情况下，确定一个适当的解决办法嘲。
对于我们的研究，原则２是最具有影响性的，其他原则都可以在我们的研究
中忽略。即在计算最优路径之前，要计算不同喂料器的位置。使得拾取频率高的
喂料器安放在和ＰＣＢ板上同类型的元件距离之和最小的位置。这样会在贴装过程
中大大减少贴片头移动距离。
５．２路径优化系统的实现
５．２．１路径优化系统数据流程图
系统数据从采集进入系统数据库到计算输出，其数据流程如图５．１所示：
４３