基于免疫算法的拱架式贴片机贴装过程优化

许继影　陈仕军

摘 要： 提出一种免疫算法来优化带多头的拱架式贴片机贴装过程。通过设计合理的问题编码、免疫算子以及参数，对贴装过程进行优化求解，并与遗传算法进行比较。以4贴片头的贴片机为例，对13个案例进行计算，得到免疫算法解的质量均要比遗传算法提高5%～10%，且每个实例的平均计算时间减少10%～25%。结果表明免疫算法比遗传算法更加有效。

关键词： 贴片机； 贴装过程； 免疫算法； 遗传算法

中图分类号： TN081?34； TP301.6 文献标识码： A 文章编号： 1004?373X（2017）07?0100?05

Immune algorithm based component placement process optimization of

arch placement machine

XU Jiying， CHEN Shijun

（Hubei University of Arts and Science， Xiangyang 430012， China）

Abstract： An immune algorithm （IA） is proposed to optimize the component placement process of the arch placement machine. The reasonable coding， immune operator and parameter are designed to solve the component placement process optimally. The IA is compared with the genetic algorithm（GA）. The 13 instances were calculated by taking the four?head placement machine as an example. The solution quality of IA is increased by 5%～10% than that of GA， and each instance′s average computational time of IA is decreased by 10%～25% than that of GA. The results show that the IA is effective than GA.

Keywords： surface mounting machine； placement process； immune algorithm； genetic algorithm

0 引 言

贴片机是一种采用表面贴装技术（SMT）将所需电子元件贴装到印刷电路板（PCB）上的自动装配机[1]。目前，对带有微型和密集型元器件的PCB的需求不断增大，使得生产企业面临提高PCB生产效率的要求。单个贴片机的贴装路径优化是提高整个PCB生产线生产效率的关键环节，研究该问题具有重要现实意义。

贴片机的贴装过程优化可以看做两个相互关联的子问题：喂料器的分配问题；元件的贴装顺序问题[2]。这两个问题均为NP难问题，故同时解决相当困难。部分学者采用将两个子问题分开各自优化，即在假定一个问题已解决的情况下解决另外一个问题[2?4]。例如，文献[2]在已知喂料槽分配的情况下，将元件取贴序的优化归结为三维非对称旅行商问题；假定元件贴装顺序已定时，将喂料槽分配看成二次指派问题。文献[3]在喂料器确定的条件下，采用遗传算法对贴装顺序进行优化。文献[4]在假设元件贴装顺序确定的情况下，将喂料槽分配建模成二次整数规划问题，应用启发式算法求解。由于两个子问题是相互耦合的，各自分开求解难以保证全局最优解。近年来不少学者将其同时考虑，采用启发式或元启发式方法，如多邻域搜索[5]、粒子群优化[6]、蚁群优化[7]、遗传算法[8?14]等来求解。文献[5]针对带多贴片头的贴装优化问题，提出一种变邻域蒙特卡洛的启发式优化方法，主要是基于定义的三种邻域结构进行局部搜索，实例测试表明该方法能找到满意解。文献[6]提出自适应的粒子群优化方法，同时优化具有多贴片头的喂料槽放置和贴片顺序，结果证实该方法不差于遗传算法。文献[7]提出一种改进的蚁群优化算法，并用实例计算说明所提方法优于传统的蚁群优化算法。文献[8]设计遗传算法对拱架型贴片机的贴装过程进行优化，并设计了新的交叉算子。文献[9]提出一种分段二元实数编码方法，采用将遗传算法和元件分配启发式方法相结合实现贴装优化。文献[10]将双拱架式贴片机贴片过程建模成0?1整数规划模型，并利用遗传算法求解简化后的数学模型。文献[11]将遗传算法用于求解贴片机贴装过程，并对遗传算法的可能改进方法进行多种实验和分析。文献[12?13]均提出了基于遗传算法的混合启发式方法优化贴片机的贴装过程，其主要区别在于遗传算子和混合优化的设计方法不同。文献[14]提出了带单贴片头的拱架式贴片机贴装过程集成优化的精确数学模型，但该模型的精确解方法只适用于小规模问题，因此采用遗传算法求大规模的贴装优化问题。上述既有研究均已证实，遗传算法能在有效时间内得到满意解。

遗传算法具有早熟收敛的缺陷，但具有很大的改进空间。类似于遗传算法，免疫算法[15]作为模仿自然免疫系统机理的新型进化算法，具有很强的全局和局部搜索能力，在解决多目标优化[16]、旅行商问题[17]以及背包问题[18]等NP难问题都有理想的效果，但目前还没有被用于对贴片机贴装过程进行优化的研究。本文尝试用免疫算法解决带多头拱架式贴片机的贴装优化问题。以带4贴片头的贴片机为例，通过设计合理的编码、免疫算子及参数，对13个案例进行优化计算，并与遗传算法在计算结果和运算时间上进行比较分析，证实了免疫算法能有效解决该问题。

1 多头拱架式贴片机贴装优化模型

1.1 贴片机贴装元件流程

拱架式贴片机主要由固定的喂料槽、固定PCB的平台、可沿[X]或[Y]方向移动的贴片头和吸嘴组成。喂料槽用于放置提供各种装配元件的喂料器，每个喂料器对应一种类型的元件。多头贴片机与单头贴片机的区别在于，多头贴片机的机器臂带有多个贴装头，可一次性抓取多个元件，而单头贴片机只有一个贴装头。多头拱架式贴片机，见图1。

单头拱架式贴片机贴装元件的过程大致如下：带有贴装头的机器臂从初始位置移动到第一个待贴元件所在的喂料槽上方，吸取该元件后，移动到PCB上方贴装元件到相应预先确定的位置；贴装完后（若需要更换吸嘴，则先更换吸嘴），机器臂再移动到喂料槽上吸取第二个元件，再贴装到PCB上相应位置；依此类推，直到将所有元件贴装完毕，机器臂返回到初始位置准备继续贴装下一块PCB板。而带多头的贴片机，在吸取元件时，可同时吸取多个元件，再移动到PCB板上依次贴装。每次吸取的多个元件构成一组元件，对该组元件的吸取和贴装过程称为一个取贴循环。一个取贴循环的过程是，机器臂按照该组元件的吸取顺序移动到各元件对应的喂料槽上依次吸取完毕后，再移动到PCB板上按该组元件的贴装顺序依次贴装。整个元件贴装过程由一系列的取贴循环组成，整个贴装时间由所有取贴时间之和构成。显然，不同的元件喂料槽分配和元件取贴顺序得到的整个贴装时间也不同。

1.2 贴片机贴装优化模型

如何安排元件在喂料槽上的分配，以及如何确定所有元件的吸取与贴装顺序，使总的取贴循环时间最短，是对贴片机整个贴装过程优化的目标。

考虑带有4贴片头的拱架式贴片机贴装优化问题。设[n]个元件[{c1，c2，…，cn}]需要装贴到PCB上，贴片头每次拾取和装贴4个元件（若[mod（n，4）≠0]，则最后一次取贴循环的元件数量为[mod（n，4）]）。因此，若给定所有元件的贴装顺序，则每次取出4个元件构成一组，对应的吸取和贴装过程构成一个取贴循环。需注意的是，在某个取贴循环内，对该组元件的吸取顺序应按其在喂料槽上从左至右（或从右至左）的顺序以得到最优的吸取路径。另外，不妨假定元件的类型数与喂料槽数量相同。

为了方便描述，做以下符号假设：

[c]：总的取贴循环数， 则[c=n4] （[n4]为大于[n4]的最小整数）。

[t1i]：第[i]次取贴循环中，贴片头在喂料槽上吸取该组所有元件共花费的时间。

[t2i]：第[i]次取贴循环中，贴片头在PCB上贴装完该组元件共花费的时间（包括贴片头从最后一个拾取元件的位置到PCB上第一个贴装元件位置的时间）。

[t0，1]：贴片头从初始位置移动到第1个待吸取元件所在的喂料槽花费的时间。

[t3i，i+1]：第[i]次取贴循环到第[i+1]次取贴循环，贴片头移动的时间。

[tc，0]：贴片头从最后一个贴装元件的位置移动到初始位置的时间。

贴片机贴装过程优化的目标是使总的取贴循环时间最小，即：

[min T=t0，1+i=1c-1（t1i+t2i+t3i，i+1）+tc，0] （1）

2 免疫算法與模型求解

2.1 免疫算法简介及其框架

免疫算法是通过模拟自然生物机体的体液免疫应答过程，根据免疫系统的部分免疫机理提出的一种新型智能算法[15]。而这种免疫系统的机理以细胞克隆选择学说和独特性免疫网络原理为主。细胞克隆选择学说认为，当某种抗原侵入机体后，机体内会有识别该抗原的特异性免疫细胞，被激活、分化和增值，产生大量特异性的抗体，从而清除抗原。根据独特性免疫网络原理，在免疫系统中，抗体不仅识别抗原，同时也识别其他抗体和被其他抗体所识别。即在独特型免疫网络中，各抗体分子间是相互协调、相互促进和抑制的关系。

将进化过程中的抗原看作问题，抗体看成优化问题的候选解，则抗体通过学习清除抗原的过程可看成寻求问题最优解的过程。若将求最优化问题解的过程模拟成体液免疫应答过程，则得到免疫算法，见图2。

图2 免疫算法框图

在图2中，克隆选择与抗体克隆将亲和度较高的抗体进行一定数量的克隆，使其参与进化；亲和突变将克隆的抗体进行免疫基因操作，使这些优良抗体做一个局部搜索，从而搜索更有利于改善目标值的解空间；募集新成员则加强了种群抗体的多样性。

2.2 抗体编码及解码

采用自然数编码，将喂料槽分配与元件贴片顺序统一编码成1条染色体，对应1个抗体。该染色体由两部分组成：第一部分是喂料槽分配情况，基因位上的基因值表示喂料槽编号；第二部分是元件贴片顺序的编码，基因位上的基因值代表元件号，两部分基因段通过元件类型相互联系。例如在图3中，该抗体编码由竖线隔开，分为两部分。第一部分喂料槽编号依次是3，2，4，1；第二部分依次是元件5，7，1，2，4，6，3。

抗体解码方法是：第一部分的第[i]个基因位上的基因值表示第[i]种类型元件分配的喂料槽编号；第二部分的第[j]个基因位上的基因值表示第[j]次贴装的元件编号。在图3中，该抗体表示元件类型1，2，3，4分别位于喂料槽3，2，4，1；元件的贴装顺序分别为元件5，7，1，2，4，6，3。

2.3 免疫算法相关概念设计

免疫算法中主要涉及的概念有抗体?抗原亲和度、抗体间距、抗体?抗体亲和力、抗体克隆规模、亲和突变算子以及免疫选择等。这些概念和算子设计的好坏直接影响免疫算法性能的高低。各种定义如下：

（1） 抗体?抗原亲和度

抗体?抗原亲和度对应优化问题解空间的解个体与目标函数的匹配程度。文中贴片机贴装完所有元件的贴装时间越短，抗体与抗原亲和度越大。因此，定义抗体抗原亲和度：

[Fitness=ZT] （2）

式中：[Z]是待设参数；[T]是优化模型（1）的目标值。

（2） 抗体间距

设抗体[A=（a1，a2，…，an），]其中[a1，a2，…，an]是[1，2，…，n]的一个排列；类似，记抗体[B=（b1，b2，…，bn）]，定义抗体[A]与[B]之间的距离：

[dA，B=i=1nai-bi] （3）

（3） 抗体?抗体亲和力

抗体?抗体亲和力反映了该抗体在抗体群中的浓度，亲和力越小，则其浓度越大，即与其相似抗体的个数越多。设抗体群[G={A1，A2，…，Ag}，]其中[Ai=（ai1，ai2，…，ain），]则抗体[Ai]相对于抗体群[G]的亲和力定义为：

[AffitAi=minexpdAi，AjDj≠i，j=1，2，…，g， i=1，2，…，g] （4）

式中：[D=maxdAi，Aji≠j；i，j=1，2，…，g]。

（4） 抗体克隆规模

根据独特性免疫网络原理，抗体间是相互促进和抑制的。将其应用于免疫优化算法中，对浓度较大的抗体采取抑制作用，使得搜索群体呈现多样化，有利于算法的全局优化。单个抗体的克隆数量与抗体?抗原亲和度成正比，与该抗体?抗体亲和力成反比。设抗体群[G={A1，A2，…，Ag}，]则抗体[Ai]的适应度相对抗体群[G]适应度的比例为：

[R（Ai）=Fitness（Ai）j=1gFitness（Aj）] （5）

则抗体[Ai]的克隆规模定义为：

[qAi=roundNc?R（Ai）?AffitAi] （6）

其中：[Nc]为克隆规模控制参数；[round{?}]是取整操作。

（5） 亲和突变算子

亲和突变算子类似于遗传算法中的基因突变算子，是抗体空间中的局部搜索算子。由于抗体编码由两部分组成，故变异时采用抗体的两段分别变异。变异算子对编码的喂料槽部分采用随机两点交换，元件编号部分用三点随机交换。

（6） 免疫选择

采用精英保留与轮盘赌选择相结合的选择策略。

2.4 遗传算法算子设计

为了便于免疫算法与遗传算法进行比较，遗传算法的染色体编码与免疫算法中的抗体编码一致；变异算子与免疫算法中亲和突变算子相同；遗传种群选择策略与免疫选择相同。

对于交叉算子，则定义如下：随机生成交叉点，将两个父个体交叉点前段基因分别作为两个子个体前半部分基因；第一个子个体的后半部分基因从第二个父个体后半部分依次填补与子个体前半部分不重复的基因，剩余的基因位仍由第一个父个体补充。具体操作如图4所示。

在图4中，生成的随机数是3，子个体1的前3个基因由父个体的前3个基因组成；子个体1的后半段4个基因中，依次由父个体2后半段中除去4，3剩余的6，2补充；剩余2个基因位仍由父个体1中除去重复部分基因后的基因5，7组成。类似地，子个体1也由此方法生成。

2.5 实例计算及分析

（1） 参数设计

为了比较遗传算法和免疫算法的性能，将两种算法都有的关键参数如种群规模、迭代次数均设置为相同值。具体如下：种群规模[Psize=100；]迭代次数[Iter=500]。其他參数设置通过多次实验取各自的最好参数值，遗传算法中交叉概率[Pc=0.7，]变异概率[Pm=0.2；]免疫算法中，募集新成员数占种群规模的比例[α=10%，]亲和度公式中参数[Z=1 000，]克隆规模控制参数[Nc=40]。

（2） 计算实例与结果

对实际中4头贴片机装置进行仿真模拟，生成13个测试案例，其元件类型和元件数见表1。

从表2中可以看出，对13个实例中的每一个实例，将最小目标值、最大目标值分别进行比较，ImmA都要优于GA；而且对所有实例，ImmA在20次运算中的最大目标值也小于GA得到的最小目标值，说明ImmA相对于GA具有明显优势。

表3的统计结果表明， ImmA计算所得的平均目标值结果和平均计算时间都优于GA。为清晰可见，13个实例用GA和ImmA求得的解的平均目标值和平均计算时间比较结果见图5，图6。

图5和图6直观说明了ImmA不仅在求解质量上占优，且所需的计算时间大大优于GA的结果。通过计算，ImmA的平均解质量要比GA提高5%～10%，且能节约计算时间10%～25%。随着问题规模的增大，ImmA比GA更具优势。

（3） 原因分析

从GA和ImmA的设计过程比较：GA是通过种群中个体交叉，然后进行变异，最后选择得到新一代的种群；而ImmA主要通过变异算子获取下一代种群。在ImmA中，一方面，所有个体均进行变异；另一方面，对亲和度大的抗体进行更多次的局部搜索（主要体现在抗体的克隆规模上）。这两方面保证了ImmA中的种群不仅具有广泛的个体多样性，且算法在迭代过程中更加集中搜索最有前途的解区域，使算法快速收敛到最优解，从而在性能上要优于GA。

3 结 语

贴片机贴装元件过程是制约PCB生产线效率的瓶颈。本文提出一种免疫算法对带多头（以4贴片头为例）的拱架式贴片机的贴装过程进行优化。通过设计合理的免疫算子和参数，并将免疫算法与遗传算法进行比较，结果表明免疫算法能在更短的时间内得到更优的解，证实了免疫算法对解决该类问题的有效性。如何充分挖掘自然免疫系统的免疫机理，设计更合理的免疫算子和算法框架，使其更加有效解决各类贴片机贴装优化问题，还需要进一步探索。

参考文献

[1] 胡以静，胡跃明，吴忻生.高速高精度贴片机的贴装效率优化方法[J].电子工艺技术，2006，27（4）：191?196.

[2] LEIP?L? T， NEVALAINEN O. Optimization of the movements of a component placement machine [J]. European journal of operational research， 1989， 38（2）： 167?177.

[3] ONG N S， TAN W C. Sequence placement planning for high?speed PCB assembly machine [J]. Integrated manufacturing systems， 2002， 13（1）： 35?46.

[4] DUMAN E， OR I. The quadratic assignment problem in the context of the printed circuit board assembly process [J]. Computers & operations research， 2007， 34（1）： 163?179.

[5] AYOB M. A variable neighbourhood search for component pick?and?place sequencing in printed circuit board assembly [J]. International journal of computer science and network security， 2007， 7（7）： 184?193.

[6] CHEN Y M， LIN C T. A particle swarm optimization approach to optimize component placement in printed circuit board assembly [J]. The international journal of advanced manufacturing technology， 2007， 35（5）： 610?620.

[7] 王君，罗家祥，胡跃明.基于改进蚁群算法的贴片机贴装过程优化[J].计算机工程，2011，37（14）：256?258.

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

[9] 杜轩，李宗斌，贾晓晨.基于遗传算法的复合式贴片机贴装过程优化[J].西安交通大学学报，2009，43（5）：80?84.

[10] 倪郁东，董娟娟，何兴康.基于遗传算法的高精度贴片机集成优化[J].合肥工业大学学报（自然科学版），2013，36（12）：1529?1533.

[11] 罗爱玲，龙绪明.应用于贴片机贴装顺序优化的遗传算法的比较和改进[J].现代电子技术，2014，37（6）：129?131.

[12] SUN D S， LEE T E， KIM K H. Component allocation and feeder arrangement for a dual?gantry multi?head surface mounting placement tool [J]. International journal of production economics， 2005， 95 （2）： 245?264.

[13] DU X， LI Z B， WANG S. Integration of PCB assembly process planning and scheduling [J]. Assembly automation， 2011， 31（3）： 232?243.

[14] HO W， JI P. An integrated scheduling problem of PCB components on sequential pick?and?place machines： mathematical models and heuristic solutions [J]. Expert systems with applications， 2009， 36（3）： 7002?7010.

[15] 谢克明，郭红波，谢刚，等.人工免疫算法及其应用[J].计算机工程与应用，2005，41（20）：77?80.

[16] 宋丹，赖旭芝，吴敏.非达尔文效应多目标免疫算法[J].控制理论与应用，2013，30（11）：1360?1368.

[17] 戚玉濤，刘芳，焦李成.求解大规模TSP问题的自适应归约免疫算法[J].软件学报，2008，19（6）：1265?1273.

[18] 钱淑渠，武慧虹.约束动态免疫算法及对背包问题性能测试研究[J].计算机应用与软件，2012，29（5）：155?158.