許繼影　陳仕軍

摘 要： 提出一種免疫算法來優(yōu)化帶多頭的拱架式貼片機貼裝過程。通過設(shè)計合理的問題編碼、免疫算子以及參數(shù)，對貼裝過程進行優(yōu)化求解，并與遺傳算法進行比較。以4貼片頭的貼片機為例，對13個案例進行計算，得到免疫算法解的質(zhì)量均要比遺傳算法提高5%～10%，且每個實例的平均計算時間減少10%～25%。結(jié)果表明免疫算法比遺傳算法更加有效。

關(guān)鍵詞： 貼片機； 貼裝過程； 免疫算法； 遺傳算法

中圖分類號： 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 引 言

貼片機是一種采用表面貼裝技術(shù)（SMT）將所需電子元件貼裝到印刷電路板（PCB）上的自動裝配機[1]。目前，對帶有微型和密集型元器件的PCB的需求不斷增大，使得生產(chǎn)企業(yè)面臨提高PCB生產(chǎn)效率的要求。單個貼片機的貼裝路徑優(yōu)化是提高整個PCB生產(chǎn)線生產(chǎn)效率的關(guān)鍵環(huán)節(jié)，研究該問題具有重要現(xiàn)實意義。

貼片機的貼裝過程優(yōu)化可以看做兩個相互關(guān)聯(lián)的子問題：喂料器的分配問題；元件的貼裝順序問題[2]。這兩個問題均為NP難問題，故同時解決相當困難。部分學(xué)者采用將兩個子問題分開各自優(yōu)化，即在假定一個問題已解決的情況下解決另外一個問題[2?4]。例如，文獻[2]在已知喂料槽分配的情況下，將元件取貼序的優(yōu)化歸結(jié)為三維非對稱旅行商問題；假定元件貼裝順序已定時，將喂料槽分配看成二次指派問題。文獻[3]在喂料器確定的條件下，采用遺傳算法對貼裝順序進行優(yōu)化。文獻[4]在假設(shè)元件貼裝順序確定的情況下，將喂料槽分配建模成二次整數(shù)規(guī)劃問題，應(yīng)用啟發(fā)式算法求解。由于兩個子問題是相互耦合的，各自分開求解難以保證全局最優(yōu)解。近年來不少學(xué)者將其同時考慮，采用啟發(fā)式或元啟發(fā)式方法，如多鄰域搜索[5]、粒子群優(yōu)化[6]、蟻群優(yōu)化[7]、遺傳算法[8?14]等來求解。文獻[5]針對帶多貼片頭的貼裝優(yōu)化問題，提出一種變鄰域蒙特卡洛的啟發(fā)式優(yōu)化方法，主要是基于定義的三種鄰域結(jié)構(gòu)進行局部搜索，實例測試表明該方法能找到滿意解。文獻[6]提出自適應(yīng)的粒子群優(yōu)化方法，同時優(yōu)化具有多貼片頭的喂料槽放置和貼片順序，結(jié)果證實該方法不差于遺傳算法。文獻[7]提出一種改進的蟻群優(yōu)化算法，并用實例計算說明所提方法優(yōu)于傳統(tǒng)的蟻群優(yōu)化算法。文獻[8]設(shè)計遺傳算法對拱架型貼片機的貼裝過程進行優(yōu)化，并設(shè)計了新的交叉算子。文獻[9]提出一種分段二元實數(shù)編碼方法，采用將遺傳算法和元件分配啟發(fā)式方法相結(jié)合實現(xiàn)貼裝優(yōu)化。文獻[10]將雙拱架式貼片機貼片過程建模成0?1整數(shù)規(guī)劃模型，并利用遺傳算法求解簡化后的數(shù)學(xué)模型。文獻[11]將遺傳算法用于求解貼片機貼裝過程，并對遺傳算法的可能改進方法進行多種實驗和分析。文獻[12?13]均提出了基于遺傳算法的混合啟發(fā)式方法優(yōu)化貼片機的貼裝過程，其主要區(qū)別在于遺傳算子和混合優(yōu)化的設(shè)計方法不同。文獻[14]提出了帶單貼片頭的拱架式貼片機貼裝過程集成優(yōu)化的精確數(shù)學(xué)模型，但該模型的精確解方法只適用于小規(guī)模問題，因此采用遺傳算法求大規(guī)模的貼裝優(yōu)化問題。上述既有研究均已證實，遺傳算法能在有效時間內(nèi)得到滿意解。

遺傳算法具有早熟收斂的缺陷，但具有很大的改進空間。類似于遺傳算法，免疫算法[15]作為模仿自然免疫系統(tǒng)機理的新型進化算法，具有很強的全局和局部搜索能力，在解決多目標優(yōu)化[16]、旅行商問題[17]以及背包問題[18]等NP難問題都有理想的效果，但目前還沒有被用于對貼片機貼裝過程進行優(yōu)化的研究。本文嘗試用免疫算法解決帶多頭拱架式貼片機的貼裝優(yōu)化問題。以帶4貼片頭的貼片機為例，通過設(shè)計合理的編碼、免疫算子及參數(shù)，對13個案例進行優(yōu)化計算，并與遺傳算法在計算結(jié)果和運算時間上進行比較分析，證實了免疫算法能有效解決該問題。

1 多頭拱架式貼片機貼裝優(yōu)化模型

1.1 貼片機貼裝元件流程

拱架式貼片機主要由固定的喂料槽、固定PCB的平臺、可沿[X]或[Y]方向移動的貼片頭和吸嘴組成。喂料槽用于放置提供各種裝配元件的喂料器，每個喂料器對應(yīng)一種類型的元件。多頭貼片機與單頭貼片機的區(qū)別在于，多頭貼片機的機器臂帶有多個貼裝頭，可一次性抓取多個元件，而單頭貼片機只有一個貼裝頭。多頭拱架式貼片機，見圖1。

單頭拱架式貼片機貼裝元件的過程大致如下：帶有貼裝頭的機器臂從初始位置移動到第一個待貼元件所在的喂料槽上方，吸取該元件后，移動到PCB上方貼裝元件到相應(yīng)預(yù)先確定的位置；貼裝完后（若需要更換吸嘴，則先更換吸嘴），機器臂再移動到喂料槽上吸取第二個元件，再貼裝到PCB上相應(yīng)位置；依此類推，直到將所有元件貼裝完畢，機器臂返回到初始位置準備繼續(xù)貼裝下一塊PCB板。而帶多頭的貼片機，在吸取元件時，可同時吸取多個元件，再移動到PCB板上依次貼裝。每次吸取的多個元件構(gòu)成一組元件，對該組元件的吸取和貼裝過程稱為一個取貼循環(huán)。一個取貼循環(huán)的過程是，機器臂按照該組元件的吸取順序移動到各元件對應(yīng)的喂料槽上依次吸取完畢后，再移動到PCB板上按該組元件的貼裝順序依次貼裝。整個元件貼裝過程由一系列的取貼循環(huán)組成，整個貼裝時間由所有取貼時間之和構(gòu)成。顯然，不同的元件喂料槽分配和元件取貼順序得到的整個貼裝時間也不同。

1.2 貼片機貼裝優(yōu)化模型

如何安排元件在喂料槽上的分配，以及如何確定所有元件的吸取與貼裝順序，使總的取貼循環(huán)時間最短，是對貼片機整個貼裝過程優(yōu)化的目標。

考慮帶有4貼片頭的拱架式貼片機貼裝優(yōu)化問題。設(shè)[n]個元件[{c1，c2，…，cn}]需要裝貼到PCB上，貼片頭每次拾取和裝貼4個元件（若[mod（n，4）≠0]，則最后一次取貼循環(huán)的元件數(shù)量為[mod（n，4）]）。因此，若給定所有元件的貼裝順序，則每次取出4個元件構(gòu)成一組，對應(yīng)的吸取和貼裝過程構(gòu)成一個取貼循環(huán)。需注意的是，在某個取貼循環(huán)內(nèi)，對該組元件的吸取順序應(yīng)按其在喂料槽上從左至右（或從右至左）的順序以得到最優(yōu)的吸取路徑。另外，不妨假定元件的類型數(shù)與喂料槽數(shù)量相同。

為了方便描述，做以下符號假設(shè)：

[c]：總的取貼循環(huán)數(shù)， 則[c=n4] （[n4]為大于[n4]的最小整數(shù)）。

[t1i]：第[i]次取貼循環(huán)中，貼片頭在喂料槽上吸取該組所有元件共花費的時間。

[t2i]：第[i]次取貼循環(huán)中，貼片頭在PCB上貼裝完該組元件共花費的時間（包括貼片頭從最后一個拾取元件的位置到PCB上第一個貼裝元件位置的時間）。

[t0，1]：貼片頭從初始位置移動到第1個待吸取元件所在的喂料槽花費的時間。

[t3i，i+1]：第[i]次取貼循環(huán)到第[i+1]次取貼循環(huán)，貼片頭移動的時間。

[tc，0]：貼片頭從最后一個貼裝元件的位置移動到初始位置的時間。

貼片機貼裝過程優(yōu)化的目標是使總的取貼循環(huán)時間最小，即：

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

2 免疫算法與模型求解

2.1 免疫算法簡介及其框架

免疫算法是通過模擬自然生物機體的體液免疫應(yīng)答過程，根據(jù)免疫系統(tǒng)的部分免疫機理提出的一種新型智能算法[15]。而這種免疫系統(tǒng)的機理以細胞克隆選擇學(xué)說和獨特性免疫網(wǎng)絡(luò)原理為主。細胞克隆選擇學(xué)說認為，當某種抗原侵入機體后，機體內(nèi)會有識別該抗原的特異性免疫細胞，被激活、分化和增值，產(chǎn)生大量特異性的抗體，從而清除抗原。根據(jù)獨特性免疫網(wǎng)絡(luò)原理，在免疫系統(tǒng)中，抗體不僅識別抗原，同時也識別其他抗體和被其他抗體所識別。即在獨特型免疫網(wǎng)絡(luò)中，各抗體分子間是相互協(xié)調(diào)、相互促進和抑制的關(guān)系。

將進化過程中的抗原看作問題，抗體看成優(yōu)化問題的候選解，則抗體通過學(xué)習(xí)清除抗原的過程可看成尋求問題最優(yōu)解的過程。若將求最優(yōu)化問題解的過程模擬成體液免疫應(yīng)答過程，則得到免疫算法，見圖2。

圖2 免疫算法框圖

在圖2中，克隆選擇與抗體克隆將親和度較高的抗體進行一定數(shù)量的克隆，使其參與進化；親和突變將克隆的抗體進行免疫基因操作，使這些優(yōu)良抗體做一個局部搜索，從而搜索更有利于改善目標值的解空間；募集新成員則加強了種群抗體的多樣性。

2.2 抗體編碼及解碼

采用自然數(shù)編碼，將喂料槽分配與元件貼片順序統(tǒng)一編碼成1條染色體，對應(yīng)1個抗體。該染色體由兩部分組成：第一部分是喂料槽分配情況，基因位上的基因值表示喂料槽編號；第二部分是元件貼片順序的編碼，基因位上的基因值代表元件號，兩部分基因段通過元件類型相互聯(lián)系。例如在圖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 免疫算法相關(guān)概念設(shè)計

免疫算法中主要涉及的概念有抗體?抗原親和度、抗體間距、抗體?抗體親和力、抗體克隆規(guī)模、親和突變算子以及免疫選擇等。這些概念和算子設(shè)計的好壞直接影響免疫算法性能的高低。各種定義如下：

（1） 抗體?抗原親和度

抗體?抗原親和度對應(yīng)優(yōu)化問題解空間的解個體與目標函數(shù)的匹配程度。文中貼片機貼裝完所有元件的貼裝時間越短，抗體與抗原親和度越大。因此，定義抗體抗原親和度：

[Fitness=ZT] （2）

式中：[Z]是待設(shè)參數(shù)；[T]是優(yōu)化模型（1）的目標值。

（2） 抗體間距

設(shè)抗體[A=（a1，a2，…，an），]其中[a1，a2，…，an]是[1，2，…，n]的一個排列；類似，記抗體[B=（b1，b2，…，bn）]，定義抗體[A]與[B]之間的距離：

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

（3） 抗體?抗體親和力

抗體?抗體親和力反映了該抗體在抗體群中的濃度，親和力越小，則其濃度越大，即與其相似抗體的個數(shù)越多。設(shè)抗體群[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） 抗體克隆規(guī)模

根據(jù)獨特性免疫網(wǎng)絡(luò)原理，抗體間是相互促進和抑制的。將其應(yīng)用于免疫優(yōu)化算法中，對濃度較大的抗體采取抑制作用，使得搜索群體呈現(xiàn)多樣化，有利于算法的全局優(yōu)化。單個抗體的克隆數(shù)量與抗體?抗原親和度成正比，與該抗體?抗體親和力成反比。設(shè)抗體群[G={A1，A2，…，Ag}，]則抗體[Ai]的適應(yīng)度相對抗體群[G]適應(yīng)度的比例為：

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

則抗體[Ai]的克隆規(guī)模定義為：

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

其中：[Nc]為克隆規(guī)?？刂茀?shù)；[round{?}]是取整操作。

（5） 親和突變算子

親和突變算子類似于遺傳算法中的基因突變算子，是抗體空間中的局部搜索算子。由于抗體編碼由兩部分組成，故變異時采用抗體的兩段分別變異。變異算子對編碼的喂料槽部分采用隨機兩點交換，元件編號部分用三點隨機交換。

（6） 免疫選擇

采用精英保留與輪盤賭選擇相結(jié)合的選擇策略。

2.4 遺傳算法算子設(shè)計

為了便于免疫算法與遺傳算法進行比較，遺傳算法的染色體編碼與免疫算法中的抗體編碼一致；變異算子與免疫算法中親和突變算子相同；遺傳種群選擇策略與免疫選擇相同。

對于交叉算子，則定義如下：隨機生成交叉點，將兩個父個體交叉點前段基因分別作為兩個子個體前半部分基因；第一個子個體的后半部分基因從第二個父個體后半部分依次填補與子個體前半部分不重復(fù)的基因，剩余的基因位仍由第一個父個體補充。具體操作如圖4所示。

在圖4中，生成的隨機數(shù)是3，子個體1的前3個基因由父個體的前3個基因組成；子個體1的后半段4個基因中，依次由父個體2后半段中除去4，3剩余的6，2補充；剩余2個基因位仍由父個體1中除去重復(fù)部分基因后的基因5，7組成。類似地，子個體1也由此方法生成。

2.5 實例計算及分析

（1） 參數(shù)設(shè)計

為了比較遺傳算法和免疫算法的性能，將兩種算法都有的關(guān)鍵參數(shù)如種群規(guī)模、迭代次數(shù)均設(shè)置為相同值。具體如下：種群規(guī)模[Psize=100；]迭代次數(shù)[Iter=500]。其他參數(shù)設(shè)置通過多次實驗取各自的最好參數(shù)值，遺傳算法中交叉概率[Pc=0.7，]變異概率[Pm=0.2；]免疫算法中，募集新成員數(shù)占種群規(guī)模的比例[α=10%，]親和度公式中參數(shù)[Z=1 000，]克隆規(guī)模控制參數(shù)[Nc=40]。

（2） 計算實例與結(jié)果

對實際中4頭貼片機裝置進行仿真模擬，生成13個測試案例，其元件類型和元件數(shù)見表1。

從表2中可以看出，對13個實例中的每一個實例，將最小目標值、最大目標值分別進行比較，ImmA都要優(yōu)于GA；而且對所有實例，ImmA在20次運算中的最大目標值也小于GA得到的最小目標值，說明ImmA相對于GA具有明顯優(yōu)勢。

表3的統(tǒng)計結(jié)果表明， ImmA計算所得的平均目標值結(jié)果和平均計算時間都優(yōu)于GA。為清晰可見，13個實例用GA和ImmA求得的解的平均目標值和平均計算時間比較結(jié)果見圖5，圖6。

圖5和圖6直觀說明了ImmA不僅在求解質(zhì)量上占優(yōu)，且所需的計算時間大大優(yōu)于GA的結(jié)果。通過計算，ImmA的平均解質(zhì)量要比GA提高5%～10%，且能節(jié)約計算時間10%～25%。隨著問題規(guī)模的增大，ImmA比GA更具優(yōu)勢。

（3） 原因分析

從GA和ImmA的設(shè)計過程比較：GA是通過種群中個體交叉，然后進行變異，最后選擇得到新一代的種群；而ImmA主要通過變異算子獲取下一代種群。在ImmA中，一方面，所有個體均進行變異；另一方面，對親和度大的抗體進行更多次的局部搜索（主要體現(xiàn)在抗體的克隆規(guī)模上）。這兩方面保證了ImmA中的種群不僅具有廣泛的個體多樣性，且算法在迭代過程中更加集中搜索最有前途的解區(qū)域，使算法快速收斂到最優(yōu)解，從而在性能上要優(yōu)于GA。

3 結(jié) 語

貼片機貼裝元件過程是制約PCB生產(chǎn)線效率的瓶頸。本文提出一種免疫算法對帶多頭（以4貼片頭為例）的拱架式貼片機的貼裝過程進行優(yōu)化。通過設(shè)計合理的免疫算子和參數(shù)，并將免疫算法與遺傳算法進行比較，結(jié)果表明免疫算法能在更短的時間內(nèi)得到更優(yōu)的解，證實了免疫算法對解決該類問題的有效性。如何充分挖掘自然免疫系統(tǒng)的免疫機理，設(shè)計更合理的免疫算子和算法框架，使其更加有效解決各類貼片機貼裝優(yōu)化問題，還需要進一步探索。

參考文獻

[1] 胡以靜，胡躍明，吳忻生.高速高精度貼片機的貼裝效率優(yōu)化方法[J].電子工藝技術(shù)，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] 王君，羅家祥，胡躍明.基于改進蟻群算法的貼片機貼裝過程優(yōu)化[J].計算機工程，2011，37（14）：256?258.

[8] 曾又姣，金燁.基于遺傳算法的貼片機貼裝順序優(yōu)化[J].計算機集成制造系統(tǒng)，2004，10（2）：205?208.

[9] 杜軒，李宗斌，賈曉晨.基于遺傳算法的復(fù)合式貼片機貼裝過程優(yōu)化[J].西安交通大學(xué)學(xué)報，2009，43（5）：80?84.

[10] 倪郁東，董娟娟，何興康.基于遺傳算法的高精度貼片機集成優(yōu)化[J].合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2013，36（12）：1529?1533.

[11] 羅愛玲，龍緒明.應(yīng)用于貼片機貼裝順序優(yōu)化的遺傳算法的比較和改進[J].現(xiàn)代電子技術(shù)，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] 謝克明，郭紅波，謝剛，等.人工免疫算法及其應(yīng)用[J].計算機工程與應(yīng)用，2005，41（20）：77?80.

[16] 宋丹，賴旭芝，吳敏.非達爾文效應(yīng)多目標免疫算法[J].控制理論與應(yīng)用，2013，30（11）：1360?1368.

[17] 戚玉濤，劉芳，焦李成.求解大規(guī)模TSP問題的自適應(yīng)歸約免疫算法[J].軟件學(xué)報，2008，19（6）：1265?1273.

[18] 錢淑渠，武慧虹.約束動態(tài)免疫算法及對背包問題性能測試研究[J].計算機應(yīng)用與軟件，2012，29（5）：155?158.