遗传算法解决多头动臂式贴片机的路径优化

王宝仁， 胡晓琳

（山东科技大学，山东 青岛 266590）

0 引言

随着电子制造业的迅猛发展，目前由晶体管、电子管等电子元器件组成的电子设备日益小型化、微型化，生产技术也向着批量化、自动化发展。表面贴装技术（Surface Mounted Technology，SMT）应运而生，这一技术的产生加速了电子产品的更新换代，是印制板制造和研究的主流方向［1］。

表面贴装技术（SMT）是一门涉及电子元器件、组装装备、焊接方法等多学科的综合性技术［2］。贴片机是SMT组装生产线上最核心、最关键的设备［3］。随着贴片机技术的发展，贴片机的结构变得越来越复杂 ，多头贴片机己成为市场的潮流，结构的复杂化和贴片头的增加对解决算法提出了新的要求。

文中针对多头动臂式贴片机，探讨在供料器位置确定后，分析元件贴装顺序的优化问题，采用遗传算法来解决该问题。

1 贴装工艺简介及建模

贴片机是由计算机控制，通过吸取、移动、对中、放置等步骤将元件准确放置在PCB已定位置［4］。贴片工艺过程如下：首先PCB通过输送带被输送到相应位置并固定，然后装有贴片头的动臂移到供料器的相应位置依次吸取元件，之后移到 PCB上的相应位置，依次贴装这些元件。如此循环取贴，直到所有元件取贴完毕后卸掉PCB。

多头动臂式贴片机贴装路径包括元件拾取和元件贴装两部分，一次取贴循环可以实现多个元件的贴装，将一次循环中取贴的元件称为一组，那么元件的拾取问题包括两个部分：组内元件的拾取和组间元件的拾取。组内元件拾取时动臂移动距离必须最短，并且要求元件的拾取次数尽可能等于吸嘴个数以减少组间往返次数。元件组间的拾取则需要根据元件的贴装顺序来进行求解，以减少循环过程中动臂拾取元件组的移动距离。

拾取元件时，动臂的移动距离为

式中：K表示取贴循环的次数；L表示同一组拾取元件的个数（本文中采用 4 头贴片机，L=4）；dl，（l－1）表示同一元件组内拾取元件时动臂的移动距离。

元件的贴装顺序包括组内元件的贴装顺序和组间元件的贴装顺序。组内元件的贴装顺序是指完成一组（L个元件）的贴装顺序。对于吸嘴上的L个元件，确定各个元件在PCB板上的贴装位置后根据遗传算法优化元件的贴装顺序，从而获得最短的贴装距离。元件组间的贴装顺序是元组之间拾取和贴装的顺序，这需要根据组内元件顺序和供料槽上元件的分布位置来决定。

元件贴装时，动臂的移动距离可以表示为

其中：更换吸嘴时，

不需要更换吸嘴时，

式中：H为动臂上吸嘴的个数；h为第k个元件组内贴装的顺序编号；di，（i+1）为组内2个相邻贴装元件间动臂的移动距离；d（k-1），k为第 k-1 次取贴循环和第 k 次取贴循环之间动臂移动的距离；PHk-1为第k-1组元件中最后一个贴装元件的贴装位置；P1k为第 k组元件中第一个贴装元件的贴装位置；S1k为第 k组元件中第一个拾取元件所在供料槽位置；SHk为第k组元件中最后一个拾取元件所在供料槽位置；PANC为吸嘴更换处的位置；更换吸嘴时动臂先由上一次循环的最后贴装点移动到吸嘴更换处（ANC）更换吸嘴，后由ANC移动到供料槽下一次循环需要吸取的第一个元件的供料槽位置，顺次吸取H个元件后，由最后的元件供料槽位置返回PCB板进行本次循环的元件贴装。不需要更换吸嘴时，动臂只需往返于PCB与供料槽之间，因此贴装过程要尽量少地更换吸嘴，以达到最佳的贴装路径。

2 遗传算法

遗传算法是由美国密歇根大学John Holland教授受自然界生物进化过程的启发所提出的一种全局随机搜索优化算法［6］。该算法把问题的解表达成“染色体”，在执行算法之前，先给出一群“染色体”即假设解。然后把这群“染色体”放置在问题的环境中，按照适者生存的原则，较适应的“染色体”存活下来进行复制，再经过交叉、变异的过程产生更适应环境的下一代"染色体"群。这样一代一代地进化，最后收敛到最适应环境的一个染色体，这就是问题的最优解［7］。

2.1 种群初始化

根据遗传算法内容，用n个自然数编码PCB板上n个元器件的贴装位置，这n个自然数的不同排列方式就代表n个元器件贴装的不同次序，也就是贴片机头的不同路径。

2.2 适应度计算

在适应度计算过程中，不仅要考虑组内元件的贴装过程（式（2）～式（4））；还要考虑元件拾取时，动臂的移动距离（式（1））。因此，先计算元件贴装过程的移动距离D2（包括吸嘴更换的路径距离），其中每4个元件之间插入一个拾取元件时动臂移动距离D1，之后计算整个装配过程的路径之和。

2.3 遗传操作

1）选择方法。采用轮盘赌方法来进行选择，先计算各个路径的适应值和适应起止区间，通过轮盘赌方法选择是否保留该个体以获得一个新种群。然后求新种群的适应值，再根据轮盘赌方法来选择是否保留这个个体。

for（i=0;i

{

p=rand（）%1000/1000.0;

if（p

newpopulation［i］=population［0］;

else

{

for（j=0;j

If（p＞=population［j］.cfitness&&p

newpopulation［i］=population［j+1］;

}}

2）交叉。交叉过程首先产生一个随机数，随机数与交叉概率Pc比较，当这个随机数小于Pc时，进行交叉，否则不执行。

for（i=0;i

{

x=rand（）%1000/1000.0;

if（x

{……

if（max

{temp=max;max=min;min=temp;}

flag=max;

for（j=min;j<=（max+min）/2;j++）

{

swap（&population［i］.gene［j］，&population［i］.gene［flag］）;

flag=flag-1;

}}}

3）变异。变异过程也是先产生一个随机数，随机数与变异概率Pm进行比较，当这个随机数小于Pm时，则进行变异，否则不执行。

for（i=0;i

{

x=（int）rand（）%1000/1000.0;

if（x

{……//随机产生 x1，x2

swap（&population［i］.gene［x1］，&population［i］.gene［x2］）;

}}}

3 实例探究

用文中提到的遗传算法对一块需要贴装200个元件的PCB板作为实例进行计算。设定印制板横、纵坐标限于0～100之间单位为mm；依据印制板生成20个元器件的装配位置，共有10种元件类型，供料槽宽度为15mm。

设定遗传算法中种群大小为50，遗传代数为100，交叉概率Pc=0.8，变异概率Pm=0.01，计算结果如下：

……

第1代，个体 47：18 5 10 12 2 19 6 7 17 3 1 0 11 16 8 9 4 15 14 13代价值为：18718

第1代，个体 48：1 3 8 6 7 5 0 2 4 9 代价值为：18859

第1代，个体49：8 6 3 1 9 5 7 4 2 0 代价值为：19455

当前第2代：

第2代，个体0：4 3 0 1 7 5 8 9 6 2代价值为：13771

第2代，个体 1：1 7 3 4 5 8 6 2 9 0 代价值为：15302

第2代，个体 2：6 2 5 7 8 4 9 3 0 1 代价值为：15474

……

第 100代，个体 47：4 3 9 6 1 0 7 8 5 2 代价值为：12055

第 100代，个体 48：4 3 9 6 1 0 7 8 5 2 代价值为：12055

第100代，个体 49：4 3 9 6 1 0 7 8 5 2 代价值为：12055

4 结语

对多头动臂式贴片机的贴装过程进行分析，利用遗传算法解决贴装路径的最优化问题，利用概率转移原则进行计算的，而不是单一从一点出发沿一条线来寻找最优路径，在整个解空间同时搜索这样有效避免陷入局部最优解。将贴装过程分解成拾取元件和元件组内的贴装顺序，并考虑到了吸嘴更换、元件布置策略等实际问题的影响，使优化结果更具与可行性。

［1］ 谢青松，赵立博.SMT表面贴装技术工艺应用与探讨［J］.船电技术，2009，29（10）:36-38.

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

［3］ 贾春艳.贴片机研究与结构设计［D］.哈尔滨:哈尔滨工程大学，2008:1-35.

［4］ 郎为民，稽英华.表面组装技术（SMT）及其应用［M］.北京 :机械工业出版社，2007.

［5］ Rogers P，Warrington R.Production planning for surface mount technology lines ［J］.International Journal of Production Research，2004，42（13）:2693-2718.

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

［7］ 王小平，曹立明.遗传算法-理论、应用与软件实现［M］.西安:西安交通大学出版社，2002.