遺傳算法解決多頭動臂式貼片機的路徑優化

王寶仁， 胡曉琳

（山東科技大學，山東 青島 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.