遺傳算法解決多頭動臂式貼片機的路徑優(yōu)化

王寶仁， 胡曉琳

（山東科技大學，山東 青島 266590）

0 引言

隨著電子制造業(yè)的迅猛發(fā)展，目前由晶體管、電子管等電子元器件組成的電子設備日益小型化、微型化，生產技術也向著批量化、自動化發(fā)展。表面貼裝技術（Surface Mounted Technology，SMT）應運而生，這一技術的產生加速了電子產品的更新?lián)Q代，是印制板制造和研究的主流方向［1］。

表面貼裝技術（SMT）是一門涉及電子元器件、組裝裝備、焊接方法等多學科的綜合性技術［2］。貼片機是SMT組裝生產線上最核心、最關鍵的設備［3］。隨著貼片機技術的發(fā)展，貼片機的結構變得越來越復雜 ，多頭貼片機己成為市場的潮流，結構的復雜化和貼片頭的增加對解決算法提出了新的要求。

文中針對多頭動臂式貼片機，探討在供料器位置確定后，分析元件貼裝順序的優(yōu)化問題，采用遺傳算法來解決該問題。

1 貼裝工藝簡介及建模

貼片機是由計算機控制，通過吸取、移動、對中、放置等步驟將元件準確放置在PCB已定位置［4］。貼片工藝過程如下：首先PCB通過輸送帶被輸送到相應位置并固定，然后裝有貼片頭的動臂移到供料器的相應位置依次吸取元件，之后移到 PCB上的相應位置，依次貼裝這些元件。如此循環(huán)取貼，直到所有元件取貼完畢后卸掉PCB。

多頭動臂式貼片機貼裝路徑包括元件拾取和元件貼裝兩部分，一次取貼循環(huán)可以實現(xiàn)多個元件的貼裝，將一次循環(huán)中取貼的元件稱為一組，那么元件的拾取問題包括兩個部分：組內元件的拾取和組間元件的拾取。組內元件拾取時動臂移動距離必須最短，并且要求元件的拾取次數(shù)盡可能等于吸嘴個數(shù)以減少組間往返次數(shù)。元件組間的拾取則需要根據元件的貼裝順序來進行求解，以減少循環(huán)過程中動臂拾取元件組的移動距離。

拾取元件時，動臂的移動距離為

式中：K表示取貼循環(huán)的次數(shù)；L表示同一組拾取元件的個數(shù)（本文中采用 4 頭貼片機，L=4）；dl，（l－1）表示同一元件組內拾取元件時動臂的移動距離。

元件的貼裝順序包括組內元件的貼裝順序和組間元件的貼裝順序。組內元件的貼裝順序是指完成一組（L個元件）的貼裝順序。對于吸嘴上的L個元件，確定各個元件在PCB板上的貼裝位置后根據遺傳算法優(yōu)化元件的貼裝順序，從而獲得最短的貼裝距離。元件組間的貼裝順序是元組之間拾取和貼裝的順序，這需要根據組內元件順序和供料槽上元件的分布位置來決定。

元件貼裝時，動臂的移動距離可以表示為

其中：更換吸嘴時，

不需要更換吸嘴時，

式中：H為動臂上吸嘴的個數(shù)；h為第k個元件組內貼裝的順序編號；di，（i+1）為組內2個相鄰貼裝元件間動臂的移動距離；d（k-1），k為第 k-1 次取貼循環(huán)和第 k 次取貼循環(huán)之間動臂移動的距離；PHk-1為第k-1組元件中最后一個貼裝元件的貼裝位置；P1k為第 k組元件中第一個貼裝元件的貼裝位置；S1k為第 k組元件中第一個拾取元件所在供料槽位置；SHk為第k組元件中最后一個拾取元件所在供料槽位置；PANC為吸嘴更換處的位置；更換吸嘴時動臂先由上一次循環(huán)的最后貼裝點移動到吸嘴更換處（ANC）更換吸嘴，后由ANC移動到供料槽下一次循環(huán)需要吸取的第一個元件的供料槽位置，順次吸取H個元件后，由最后的元件供料槽位置返回PCB板進行本次循環(huán)的元件貼裝。不需要更換吸嘴時，動臂只需往返于PCB與供料槽之間，因此貼裝過程要盡量少地更換吸嘴，以達到最佳的貼裝路徑。

2 遺傳算法

遺傳算法是由美國密歇根大學John Holland教授受自然界生物進化過程的啟發(fā)所提出的一種全局隨機搜索優(yōu)化算法［6］。該算法把問題的解表達成“染色體”，在執(zhí)行算法之前，先給出一群“染色體”即假設解。然后把這群“染色體”放置在問題的環(huán)境中，按照適者生存的原則，較適應的“染色體”存活下來進行復制，再經過交叉、變異的過程產生更適應環(huán)境的下一代"染色體"群。這樣一代一代地進化，最后收斂到最適應環(huán)境的一個染色體，這就是問題的最優(yōu)解［7］。

2.1 種群初始化

根據遺傳算法內容，用n個自然數(shù)編碼PCB板上n個元器件的貼裝位置，這n個自然數(shù)的不同排列方式就代表n個元器件貼裝的不同次序，也就是貼片機頭的不同路徑。

2.2 適應度計算

在適應度計算過程中，不僅要考慮組內元件的貼裝過程（式（2）～式（4））；還要考慮元件拾取時，動臂的移動距離（式（1））。因此，先計算元件貼裝過程的移動距離D2（包括吸嘴更換的路徑距離），其中每4個元件之間插入一個拾取元件時動臂移動距離D1，之后計算整個裝配過程的路徑之和。

2.3 遺傳操作

1）選擇方法。采用輪盤賭方法來進行選擇，先計算各個路徑的適應值和適應起止區(qū)間，通過輪盤賭方法選擇是否保留該個體以獲得一個新種群。然后求新種群的適應值，再根據輪盤賭方法來選擇是否保留這個個體。

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）交叉。交叉過程首先產生一個隨機數(shù)，隨機數(shù)與交叉概率Pc比較，當這個隨機數(shù)小于Pc時，進行交叉，否則不執(zhí)行。

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）變異。變異過程也是先產生一個隨機數(shù)，隨機數(shù)與變異概率Pm進行比較，當這個隨機數(shù)小于Pm時，則進行變異，否則不執(zhí)行。

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，遺傳代數(shù)為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 結語

對多頭動臂式貼片機的貼裝過程進行分析，利用遺傳算法解決貼裝路徑的最優(yōu)化問題，利用概率轉移原則進行計算的，而不是單一從一點出發(fā)沿一條線來尋找最優(yōu)路徑，在整個解空間同時搜索這樣有效避免陷入局部最優(yōu)解。將貼裝過程分解成拾取元件和元件組內的貼裝順序，并考慮到了吸嘴更換、元件布置策略等實際問題的影響，使優(yōu)化結果更具與可行性。

［1］ 謝青松，趙立博.SMT表面貼裝技術工藝應用與探討［J］.船電技術，2009，29（10）:36-38.

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

［3］ 賈春艷.貼片機研究與結構設計［D］.哈爾濱:哈爾濱工程大學，2008:1-35.

［4］ 郎為民，稽英華.表面組裝技術（SMT）及其應用［M］.北京 :機械工業(yè)出版社，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］ 曾又姣，金燁.基于遺傳算法的貼片機貼裝順序優(yōu)化［J］.計算機集成制造系統(tǒng)，2004，10（2）:205-208.

［7］ 王小平，曹立明.遺傳算法-理論、應用與軟件實現(xiàn)［M］.西安:西安交通大學出版社，2002.