应用于贴片机贴装顺序优化的遗传算法的比较和改进

罗爱玲　龙绪明

摘 要： 元件贴装顺序优化是决定贴片机生产效率的关键问题，传统的解决贴装顺序优化问题的方法有遗传算法，蚁群算法，SS（伞布搜索法）等。使用较多的还是遗传算法。遗传算法中包含选择算子、交叉算子、变异算子，且编程思想简单，但容易出现局部最优，过早收敛等情况。在此，通过对遗传算法在贴装顺序优化应用的结果比较找到一种更适合的遗传算法，使之拥有较快的收敛速度和全局优化性。

关键词： 元件贴装顺序优化； 贴片机； 遗传算法； 交叉算子

中图分类号： TN919?34； TP202.7 文献标识码： A 文章编号： 1004?373X（2014）06?0129?03

0 引 言

随着电子产品装配技术日新月异的发展，表面组装技术（SMT），这一集电子元器件、组装装备和焊接技术为一体的综合性技术得到了越来越广泛的应用[1]。表面组装生产线的使用，加快了电子产品的生产效益，增强了产品的可靠性，与此同时大大降低了生产成本，使得电子产品装配较之手工装配发生了质的飞跃。为进一步地提高贴片机的性能，其关键因素之一就是提高贴片机的效率：即贴片机送料器的位置分配优化和元器件的贴装优化。

这里假设送料器位置固定，来解决元器件的贴装优化问题。对于单台贴片机而言，这个问题都属于NP?Hard 问题，一般被规划为旅行商问题（ Traveling Salesman Problem，TSP）[2]， 已有一些学者成功地用传统的遗传算法（GA）解决。但是，由于贴片机的发展， 它的结构已经变得更为复杂，其头数已多达12头， 甚至更多，解决贴装顺序优化问题的方法近年来主要有：遗传算法、蚁群算法、伞布搜索法以及差分算法。遗传算法是进化算法，主要通过选择变异和交叉算子完成；蚁群算法是基于图论的算法，通过信息素选择交换信息；伞布搜索法属于比较新的应用于贴装顺序优化的算法，目前国内的研究报道少之又少，国外尚未有关此算法在贴装优化方面的研究应用；差分算法是在遗传算法的基础上增加了迁徙进化过程，使算法拥有更好的全局性，但较之遗传算法编程思想比较麻烦。所以本文只讨论遗传算法的应用，并对其进行改进，使贴装优化不仅编程简便且拥有较好的全局性和收敛性。

1 遗传算法的基本原理

20世纪50—60年代，一些科学家独立开展了旨在可以成为工程问题优化工具的进化系统的研究。80年代以后，经过相关领域专家学者的交流和共同努力，遗传算法、ES、EP走向融合，构成了进化计算的思想和主要算法形式[3]。由于其不受搜索空间的限制性假设的约束，不必要求诸如连续性、倒数存在和单峰等假设，以及其固有的并行性，遗传算法在最优化、机器学习和并行处理领域得到了越来越广泛的应用。遗传算法GA把问题的解表示成 “染色体”，在执行遗传算法之前，给出一群“染色体”，即假设解。然后把这些假设解放置于问题的“环境”中，按照适者生存的原则，较适应环境的“染色体”被挑选出来进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

2 贴片机的工作过程及数学模型

无论是全自动贴片机还是手动贴片机，无论是高速贴片机还是中低速贴片机，它的总体结构均有类似之处。图1是一种通用贴片机的内部结构示意图，所示为12个吸嘴，其工作过程：PCB由传送带入口送入，传送带将PCB送到工作位置停板，定位针进行夹紧，通过相机识别MARK点对PCB板完成定位后，PCB板固定，贴装头吸取元件通过x/y轴及R轴和Z轴的移动以一定的压力把元件贴装在有粘性的已经印刷焊锡的焊盘上，即吸取?位移?定位?放置功能[4]，贴装头不断地重复这样的贴装循环，直到所有元件贴装完毕即完成贴装。贴片机贴装路径优化问题描述如下：已知印制板上各个元器件的装配位置，寻求一个贴片机头遍历这些装配位置的路径，寻求开销最小。

该问题与经典的TSP问题有相似之处，即都是遍历整个集合，求最小值问题。不同的是，贴片机贴装要分批进行，如一个4吸嘴的贴片头一个贴装循环内只能贴装4个元器件，一次循环结束后贴片头要返回工料站进行取料再开始下一个循环。所以整体来说，贴片机的贴装优化并不属于TSP问题。贴片机贴装时间需包括：取料时间、贴装时间、循环间吸取原料的时间及弃料抛料时间等。整个贴片机的贴装过程是一个比较复杂的过程，为使模型的建立稍微简单些，必须牺牲掉一些不必要的环节，故参照文献[5]做以下假设：

（1） 假设供料器位置为原点；

（2） 将整个贴装过程中只做一次的动作例如PCB MARK点的定位省略；

（3） 假设每次贴片式贴装头在x，y方向运动的时间均大于其贴装头的旋转对中时间；

（4） 假设吸嘴吸片时间固定，为90 ms；贴片时间固定，为90 ms；

故类似文献[6]，一个完整的贴装时间可以表示为：

式中：[T1i]表示第i个循环内总共的贴片头移动时间；[T2i]表示贴片头从第i个循环的最后一个元件贴装完毕移动到下一个循环的第一个元件的贴装位置所需要的时间；[ti]表示第i个元件的贴片时间，如上文所假设，一般每个元件的贴片时间一定；s表示总循环次数；n表示总元件个数。按距离远近x，y方向的运动有加速?减速（短距离）、加速?恒速?减速（长距离）两种形式。按给定运动距离S、加速度a、恒速度v可得到对应的运动时间t的计算公式：

短距离：[t=4Sa]；长距离：[t=Sv+va]

式中v，a都是设定值。故求上式的最小值可简化为[i=1sd1i+i=1s-1d2i]的最小值，d1表示贴装循环内贴片头要移动的距离，d2表示循环间贴片头要移动的距离。

3 算法

3.1 遗传算法

遗传算法在群体进化过程中发生繁殖、杂交和突变现象，不断发现重要基因[7]。寻找较好模式的过程中，高适应度的个体被选择的概率大于低适应度的个体，则好的基因得以遗传下来，不好的基因被剔除，随着迭代次数的增加逐渐创造出更好的个体，同时也渐渐趋近于全局最优解。

主要包括3部分：多样性初始解集的产生；解集的改良更新，其中的算子包括复制算子、交叉算子和变异算子；最优解的出现。

3.2 初始解集的产生

初始解集的特性对计算结果和计算效率有重要的影响，要实现全局最优，初始解集在解空间上应尽量分散，若按照随机方法产生一组原始解集，可能会导致初始解集在解空间的分布不均进而影响算法的性能。在遗传算法中初始种群的各个个体间应保持一定的距离，这样的分布能使解在解空间上含有较丰富的模式，进而增加搜索收敛全局最优的可能性[8]。

3.3 复制算子

遗传算法中通过个体的适应值反映群体中个体的好坏程度，复制算子把当前群体中的个体按照与适应值成比例的概率复制到新的群体中。一般选用赌盘选择的方法完成复制。

3.4 交叉算子

交叉算子是对整个染色体操作的，所以在遗传算法中起核心作用，遗传算法的收敛性主要取决于交叉算子的收敛性[9]。经典的交叉算子包括： 单点交叉、两点交叉、多点交叉、融合交叉、均匀交叉等。

3.5 变异算子

按概率对染色体的某一基因位（自变量的某一维）进行一个微扰动或是取反。

4 算法的比较和改进

以一个PCB板子上的20个元器件为例，其各个元件坐标如下表所示，假设贴片头上有4个吸嘴。这里初始染色体中有10个体，迭代次数为200，交叉概率为定值0.8，变异概率为定值0.2，采用多种遗传算法的贴装距离分别如表1所示。

如图2所示，其中（a）结果收敛性和全局优化性都差；（b）虽然收敛速度快，但全局性不好；（c）虽然获得了好的全局性，但收敛速度慢；相比之下（d）的收敛速度和全局性都比较优秀。

图2（d）是在前3种遗传算法上的改进，算法步骤为：

（1） 初始化染色体，这里取染色体的个体为10；

（2） 按照赌盘选择和适应值的大小进行复制。即将染色体中前5个适应值高的个体直接复制给新的群体，剩下的5个解则按照赌盘选择的方法进行选择，这样不仅提高了群体的平均适应值，也加快了算法的整体收敛速度；

（3） 对染色体按适应度大小进行排列，适应度大的排在前面，小的排在后面；

（4） 从第一个染色体开始选取概率为Pc个染色体，每两个进行组合形成一对父代双亲，随机产生一个交叉点k，并随机产生一个小于从交叉点到最后节点个数的随机数r，进行交叉。

如假设P1=[1，4，3，7，2，5，6]，P2=[2，4，7，3，6，5，1]；

若随机产生k=2，r=3；则P1′=[7，3，6，1，4，3，7，2，5，6]，P2′=[3，7，2， 2，4，7，3，6，5，1]；依次删去重复的数得到新的子代个体：p1=[7，3，6，1，4，2，5]，p2=[3，7，2，4，6，5，1]；

（5） 分别比较2个父代和子代的适应值，选择适应值最大的遗传下来，作为最终的子代个体。这样保证了每次都遗传最好的基因，加快了最优解出现的速度。

5 结 论

本文提出的遗传算法，是在传统遗传算法基础上的完善，通过改善复制算子和交叉算子并加入最后选择算子，使新的交叉算子有更大的全局优化性和更快的收敛性。相比于文献[2]，文献[2]是改进过交叉算子的应用，但迭代结果仍然上下波动，收敛效果不好；相比于文献[10]虽然效果相似，但却比其有着更简便的编程思想。该方法得到最优解更具有全局性，且速度也比较快。

参考文献

[1] SRIHARI K， RAGHAVAN Sundarraman. A process planning system for PCB assembly using TAB and SMT [J]. Advanced Manufacturing Technology， 1994， 9： 311?318.

[2] 曾又姣，金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统，2004，10（2）：205?208.

[3] 韩瑞锋.遗传算法原理与应用实例[M].北京：兵器工业出版社，2009.

[4] 王燕.水平旋转式贴片机贴装过程优化研究[D].西安：西安电子科技大学，2010.

[5] 袁鹏，刘海明，胡跃明.高速高精度多功能贴片机及产业化关键技术研究[D].广州：华南理工大学，2005.

[6] 朱光宇，罗哲，陈志锦.基于差分算法的贴装顺序优化问题求解[J].中国工程机械学报，2012，10（4）：391?397.

[7] 俞国燕，郑时雄，刘桂雄，等.复杂工程问题全局优化算法研究[J].华南理工大学学报，2000，28（8）：104?110.

[8] 袁鹏，刘海明，胡跃明.基于伞布搜索法的贴片机贴装顺序优化算法[J].电子工艺技术，2007，28（6）：316?320.

[9] 翟梅梅.基于交叉算子改进的遗传算法求解TSP问题[J].淮南师范学院学报，2009，11（5）：114?119.

[10] 杜轩，李宗斌，高新勤，等.基于遗传算法的转塔式贴片机贴装过程优化[J].西安交通大学学报，2008，42（3）：295?299.

主要包括3部分：多样性初始解集的产生；解集的改良更新，其中的算子包括复制算子、交叉算子和变异算子；最优解的出现。

3.2 初始解集的产生

初始解集的特性对计算结果和计算效率有重要的影响，要实现全局最优，初始解集在解空间上应尽量分散，若按照随机方法产生一组原始解集，可能会导致初始解集在解空间的分布不均进而影响算法的性能。在遗传算法中初始种群的各个个体间应保持一定的距离，这样的分布能使解在解空间上含有较丰富的模式，进而增加搜索收敛全局最优的可能性[8]。

3.3 复制算子

遗传算法中通过个体的适应值反映群体中个体的好坏程度，复制算子把当前群体中的个体按照与适应值成比例的概率复制到新的群体中。一般选用赌盘选择的方法完成复制。

3.4 交叉算子

交叉算子是对整个染色体操作的，所以在遗传算法中起核心作用，遗传算法的收敛性主要取决于交叉算子的收敛性[9]。经典的交叉算子包括： 单点交叉、两点交叉、多点交叉、融合交叉、均匀交叉等。

3.5 变异算子

按概率对染色体的某一基因位（自变量的某一维）进行一个微扰动或是取反。

4 算法的比较和改进

以一个PCB板子上的20个元器件为例，其各个元件坐标如下表所示，假设贴片头上有4个吸嘴。这里初始染色体中有10个体，迭代次数为200，交叉概率为定值0.8，变异概率为定值0.2，采用多种遗传算法的贴装距离分别如表1所示。

如图2所示，其中（a）结果收敛性和全局优化性都差；（b）虽然收敛速度快，但全局性不好；（c）虽然获得了好的全局性，但收敛速度慢；相比之下（d）的收敛速度和全局性都比较优秀。

图2（d）是在前3种遗传算法上的改进，算法步骤为：

（1） 初始化染色体，这里取染色体的个体为10；

（2） 按照赌盘选择和适应值的大小进行复制。即将染色体中前5个适应值高的个体直接复制给新的群体，剩下的5个解则按照赌盘选择的方法进行选择，这样不仅提高了群体的平均适应值，也加快了算法的整体收敛速度；

（3） 对染色体按适应度大小进行排列，适应度大的排在前面，小的排在后面；

（4） 从第一个染色体开始选取概率为Pc个染色体，每两个进行组合形成一对父代双亲，随机产生一个交叉点k，并随机产生一个小于从交叉点到最后节点个数的随机数r，进行交叉。

如假设P1=[1，4，3，7，2，5，6]，P2=[2，4，7，3，6，5，1]；

若随机产生k=2，r=3；则P1′=[7，3，6，1，4，3，7，2，5，6]，P2′=[3，7，2， 2，4，7，3，6，5，1]；依次删去重复的数得到新的子代个体：p1=[7，3，6，1，4，2，5]，p2=[3，7，2，4，6，5，1]；

（5） 分别比较2个父代和子代的适应值，选择适应值最大的遗传下来，作为最终的子代个体。这样保证了每次都遗传最好的基因，加快了最优解出现的速度。

5 结 论

本文提出的遗传算法，是在传统遗传算法基础上的完善，通过改善复制算子和交叉算子并加入最后选择算子，使新的交叉算子有更大的全局优化性和更快的收敛性。相比于文献[2]，文献[2]是改进过交叉算子的应用，但迭代结果仍然上下波动，收敛效果不好；相比于文献[10]虽然效果相似，但却比其有着更简便的编程思想。该方法得到最优解更具有全局性，且速度也比较快。

参考文献

[1] SRIHARI K， RAGHAVAN Sundarraman. A process planning system for PCB assembly using TAB and SMT [J]. Advanced Manufacturing Technology， 1994， 9： 311?318.

[2] 曾又姣，金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统，2004，10（2）：205?208.

[3] 韩瑞锋.遗传算法原理与应用实例[M].北京：兵器工业出版社，2009.

[4] 王燕.水平旋转式贴片机贴装过程优化研究[D].西安：西安电子科技大学，2010.

[5] 袁鹏，刘海明，胡跃明.高速高精度多功能贴片机及产业化关键技术研究[D].广州：华南理工大学，2005.

[6] 朱光宇，罗哲，陈志锦.基于差分算法的贴装顺序优化问题求解[J].中国工程机械学报，2012，10（4）：391?397.

[7] 俞国燕，郑时雄，刘桂雄，等.复杂工程问题全局优化算法研究[J].华南理工大学学报，2000，28（8）：104?110.

[8] 袁鹏，刘海明，胡跃明.基于伞布搜索法的贴片机贴装顺序优化算法[J].电子工艺技术，2007，28（6）：316?320.

[9] 翟梅梅.基于交叉算子改进的遗传算法求解TSP问题[J].淮南师范学院学报，2009，11（5）：114?119.

[10] 杜轩，李宗斌，高新勤，等.基于遗传算法的转塔式贴片机贴装过程优化[J].西安交通大学学报，2008，42（3）：295?299.

主要包括3部分：多样性初始解集的产生；解集的改良更新，其中的算子包括复制算子、交叉算子和变异算子；最优解的出现。

3.2 初始解集的产生

初始解集的特性对计算结果和计算效率有重要的影响，要实现全局最优，初始解集在解空间上应尽量分散，若按照随机方法产生一组原始解集，可能会导致初始解集在解空间的分布不均进而影响算法的性能。在遗传算法中初始种群的各个个体间应保持一定的距离，这样的分布能使解在解空间上含有较丰富的模式，进而增加搜索收敛全局最优的可能性[8]。

3.3 复制算子

遗传算法中通过个体的适应值反映群体中个体的好坏程度，复制算子把当前群体中的个体按照与适应值成比例的概率复制到新的群体中。一般选用赌盘选择的方法完成复制。

3.4 交叉算子

交叉算子是对整个染色体操作的，所以在遗传算法中起核心作用，遗传算法的收敛性主要取决于交叉算子的收敛性[9]。经典的交叉算子包括： 单点交叉、两点交叉、多点交叉、融合交叉、均匀交叉等。

3.5 变异算子

按概率对染色体的某一基因位（自变量的某一维）进行一个微扰动或是取反。

4 算法的比较和改进

以一个PCB板子上的20个元器件为例，其各个元件坐标如下表所示，假设贴片头上有4个吸嘴。这里初始染色体中有10个体，迭代次数为200，交叉概率为定值0.8，变异概率为定值0.2，采用多种遗传算法的贴装距离分别如表1所示。

如图2所示，其中（a）结果收敛性和全局优化性都差；（b）虽然收敛速度快，但全局性不好；（c）虽然获得了好的全局性，但收敛速度慢；相比之下（d）的收敛速度和全局性都比较优秀。

图2（d）是在前3种遗传算法上的改进，算法步骤为：

（1） 初始化染色体，这里取染色体的个体为10；

（2） 按照赌盘选择和适应值的大小进行复制。即将染色体中前5个适应值高的个体直接复制给新的群体，剩下的5个解则按照赌盘选择的方法进行选择，这样不仅提高了群体的平均适应值，也加快了算法的整体收敛速度；

（3） 对染色体按适应度大小进行排列，适应度大的排在前面，小的排在后面；

（4） 从第一个染色体开始选取概率为Pc个染色体，每两个进行组合形成一对父代双亲，随机产生一个交叉点k，并随机产生一个小于从交叉点到最后节点个数的随机数r，进行交叉。

如假设P1=[1，4，3，7，2，5，6]，P2=[2，4，7，3，6，5，1]；

若随机产生k=2，r=3；则P1′=[7，3，6，1，4，3，7，2，5，6]，P2′=[3，7，2， 2，4，7，3，6，5，1]；依次删去重复的数得到新的子代个体：p1=[7，3，6，1，4，2，5]，p2=[3，7，2，4，6，5，1]；

（5） 分别比较2个父代和子代的适应值，选择适应值最大的遗传下来，作为最终的子代个体。这样保证了每次都遗传最好的基因，加快了最优解出现的速度。

5 结 论

本文提出的遗传算法，是在传统遗传算法基础上的完善，通过改善复制算子和交叉算子并加入最后选择算子，使新的交叉算子有更大的全局优化性和更快的收敛性。相比于文献[2]，文献[2]是改进过交叉算子的应用，但迭代结果仍然上下波动，收敛效果不好；相比于文献[10]虽然效果相似，但却比其有着更简便的编程思想。该方法得到最优解更具有全局性，且速度也比较快。

参考文献

[1] SRIHARI K， RAGHAVAN Sundarraman. A process planning system for PCB assembly using TAB and SMT [J]. Advanced Manufacturing Technology， 1994， 9： 311?318.

[2] 曾又姣，金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统，2004，10（2）：205?208.

[3] 韩瑞锋.遗传算法原理与应用实例[M].北京：兵器工业出版社，2009.

[4] 王燕.水平旋转式贴片机贴装过程优化研究[D].西安：西安电子科技大学，2010.

[5] 袁鹏，刘海明，胡跃明.高速高精度多功能贴片机及产业化关键技术研究[D].广州：华南理工大学，2005.

[6] 朱光宇，罗哲，陈志锦.基于差分算法的贴装顺序优化问题求解[J].中国工程机械学报，2012，10（4）：391?397.

[7] 俞国燕，郑时雄，刘桂雄，等.复杂工程问题全局优化算法研究[J].华南理工大学学报，2000，28（8）：104?110.

[8] 袁鹏，刘海明，胡跃明.基于伞布搜索法的贴片机贴装顺序优化算法[J].电子工艺技术，2007，28（6）：316?320.

[9] 翟梅梅.基于交叉算子改进的遗传算法求解TSP问题[J].淮南师范学院学报，2009，11（5）：114?119.

[10] 杜轩，李宗斌，高新勤，等.基于遗传算法的转塔式贴片机贴装过程优化[J].西安交通大学学报，2008，42（3）：295?299.