基于免疫算法的拱架式貼片機貼裝過程優化

許繼影　陳仕軍

摘 要： 提出一種免疫算法來優化帶多頭的拱架式貼片機貼裝過程。通過設計合理的問題編碼、免疫算子以及參數，對貼裝過程進行優化求解，并與遺傳算法進行比較。以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.