基于遺傳-蟻群算法的表面貼裝順序優化研究

摘要本文針對拱架型貼片機，提出了一種在供料器的位置確定后，對包含多個貼片頭、多種類型元件的PCB表面貼裝系統的貼裝順序進行優化的有效算法。該算法在遺傳算法中融入蟻群算法，利用遺傳算法在大范圍內提高收斂速度，同時進一步利用蟻群算法在區域內提高解的精確性，以縮短PCB上元件的裝配時間，提高SMT系統的生產效率。文中通過與遺傳算法的計算結果進行比較，驗證了本文提出的算法的高效性和可靠性。

中圖分類號：TP23 文獻標識碼：A

Research of Surface Mounting Sequence Optimization Based on GAAA

LI Pengcheng， LONG Xuming， HUANG Hao

（Chengdu Electromechanical College， Chengdu， Sichuan 610031)

AbstractFor the arch-type mounter， an effective algorithm is presented in this paper used to optimize the mounting sequence of the surface mounting system on printed circuit board (PCB) with multi- mounting heads and element types when the position of feeder is confirmed. The algorithm integrates ant algorithm (AA) into genetic algorithm (GA). GA is applied to advance convergence speed in a large range and AA is used to elevate the accuracy of the solutions to shorten element mounting time on PCB and improve production efficiency of Surface Mounted Technology (SMT) system. The results by GA are compared by the algorithm proposed in this paper to confirm the validity and reliability of the algorithm.

Key wordssurface mounted technology; mounter; genetic algorithm; ant colony algorithm; printed circuit board

0 引言

隨著芯片制造工藝的升級，芯片的封裝向小型化方向發展。使得在PCB有效面積內放置更多的元器件成為可能。芯片封裝也由原來的DIP、SOIC等大封裝向QFN、BGA等封裝發展。芯片封裝形式的改變，使得貼片機在PCB制造工藝上的重要性日益加大。

PCB焊接工廠現在使用的貼片機根據結構的不同可分為：拱架式、復合式、轉塔式和大型并行系統。其中又以拱架式貼片機應用范圍更廣，進入我國時間更早。同時，由于此類型貼片機原有算法比較落后，使得PCB焊接效率比較低，對于此類型貼片機的算法優化緊迫而重要。貼片機的組裝問題涉及兩個彼此相關的問題，即供料器分配及元器件貼裝順序問題。對于前一問題，可歸結為二次指派問題，可應用專門算法進行優化。對于元器件貼裝順序問題可歸結為旅行商問題(TSP)。本文以此問題算作為主要研究對象以尋找最優的解決方案。

很多文獻對于TSP問題，進行了研究給出了解決此問題的優化算法。其中以蟻群算法及遺傳算法效率較高。但這兩種算法各有其缺點。其中蟻群算法利用信息素的正反饋使結果收斂于其最優組合，但此算法在計算的初期由于信息素匾乏，算法的事件整個計算周期較長。而遺傳算法雖然有大范圍全局搜索的能力，但在求解的過程中當解縮小到一定范圍后，會有大量的冗余迭代。同時對于求解過程中的反饋信息沒有很好的利用。正是基于遺傳算法在求解過程中前期的快速搜索特性和蟻群算法在后期的正反饋收斂效應。本文在計算初期采用遺傳算法生成若干組優化解，作為蟻群算法的初始信息素。在計算后期利用信息素正反饋進行快速精確求解。采用遺傳-蟻群算法（GAAA）對貼片機的元器件貼裝順序問題進行了優化，通過遺傳蟻群兩種算法的相互結合取長補短，優勢互補，實現了貼裝順序的最優求解。

1 貼片系統描述及數學建模

貼片機系統如圖1所示，按照其功能可劃分為三大部分：供料器、供料槽及工作臺。根據元器件封裝及外包裝的不同，供料器可分為盤式和帶式。每個供料器只能裝載一種封裝的器件，裝載同種封裝的供料器可占據一個或多個供料槽。供料器固定在供料槽上，供料槽分列在工作臺兩邊。工作臺是拱架式貼片機的核心部件，元器件取、貼、旋轉由固定在貼片頭上的吸嘴完成，為了能同時吸取多個元器件，每個貼片機上可安裝多個貼片頭，貼片頭的間距是供料間距的整數倍。貼片頭安裝在拱架上，由固定在工作臺上的拱架拖動完成貼片頭的移動。

貼片機的貼片流程是一個重復循環的過程，一個基本的貼片循環由取料，校正和貼放完成。首先前道工序完成的PCB板被傳送到相應位置，并固定下來，拱架拖動貼片頭移動到供料器相應位置順序吸取一個或多個元器件，然后根據PCB板上的MARK點進行視覺校正，之后貼片頭移動到PCB板相應位置進行依次貼裝。重復循環取料，校正和貼放的基本動作，直到PCB板對應的BOM表中貼片元器件貼裝完成，將PCB板傳送到下道工序，進而完成一塊PCB板的貼裝工序。

由貼片機貼片流程，可分析出一個基本的貼片循環時間由以下部分組成：取料時間T1，校正時間，貼片時間T2，貼片頭貼放結束移動到取料位置時間Dij，貼片頭移動的加減速時間變量。其中校正時間和貼片頭移動加減速移動的變量時間相對較短且由貼片機本身硬件決定，可以省略。貼片的循環次數P由PCB板貼片元器件及供料器分配決定。由分析可得出如下目標方程：

(1)

其中x ij是布爾型變量，判斷取貼循環i，j是否相鄰。其約束條件如下式（2-5），這些約束條件保證每次基本循環只被計算一次。

Xij∈{ 0 ，1} ， i ， j = 1 ，2 ， …， p， i≠j(2)

∑pj=1Xij= 1，i = 1， 2 …， p(3)

∑pi=1Xij =1， i =1， 2 …， p (4)

∑pj=1Xij∑pi=1Xij = p-1(5)

2 遺傳算法設計

2.1 染色體編碼

在貼裝PCB板 時，根據PCB 上的元件封裝種類，通常需要一種或多種吸嘴，這些吸嘴分配給指定的貼片頭。每個貼片頭上吸嘴的基本動作吸取，貼放構成染色體的一個節點。每一種吸嘴貼裝的元件構成染色體一條子鏈，各子鏈中的相應節點組成一個基因，代表一個基本的取貼循環。

2.2 種群生成與染色體選擇

利用rand函數隨機生成一定數據的十進制實數編碼種群，以總的貼裝時間做為染色體的適應值的衡量標準，總貼裝時間越少，染色體的適應度越高。染色體的選擇根據優勝劣汰的方式，適應值被選中的概率較大，本文使用輪盤賭進行染色體的篩選。

2.3 交叉算子

染色體的交叉是通過其子鏈的交叉來實現的。設dij為元器件i與元器件j間的距離，它由兩部分組成：取料距離和貼裝距離。做如下定義：

dij＞dk1 if ＞(6)

dij＞dk1if =and ＞ (7)

dij = dk1if = and = (8)

dij＜dk1 if＜ (9)

dij＜dk1if =and ＜(10)

2.4 變異算子

采取逆轉變異方法，所謂“逆轉”，如染色體（1－2－3－4－5－6）在區間2－3和區間5－6處發生斷裂，斷裂片段又以反向順序插入，于是逆轉后的染色體變為（1－2－5－4－3－6）。這里的“進化”，是指逆轉算子的單方向性，只有經過逆轉后，適應值有提高的才被接受下來，否則逆轉無效。

表1測試板特性

3 蟻群算法的設計

GAAA中對蟻群算法選擇基于最大-最小螞蟻系統MMAS算法。為了對MMAS與GA更好的對接，需要對信息素的初始化及信息更新進行處理。

3.1 信息素的初值設置

在基本的MMAS中，為了更好的進行尋優，把每路信息素的初值都設為最大值max。在這里我們使用遺傳算法己得出了一組優化解，使用這組優化組獲取了一定的路徑信息素。

所以信息素初值可設為S = C + G其中可根據PCB板中元器件中的多少定義一個信息素常數，這個數相當于MMAS中的min，G是遺傳算法求解結果轉換的信息素值。

3.2 信息素更新模型

采用螞蟻圈模型進行信息素更新，即一圈中只有最短路徑的螞蟻才進行信息素修改增加，其軌跡強度的更新方程和螞蟻的轉移概率可定義為：

ij (t + 1) =.ij (t) +∑kij(t)(11)

其中為路徑ij (i， j)在t時刻的信息素軌跡強度；kij (t)為螞蟻k在路徑(i， j)留下的單位長度軌跡信息素數量；表示軌跡的持久性，0≤＜1，將（1－）理解為軌跡衰減度。

4 程序流程圖

本文用matlab編寫了基于GAAA算法的貼片機貼裝順序優化程序，程序流程圖如圖2所示。

5 算法評估

在JUKI－2010貼片機使用本算法與使用GA算法的貼片時間進行對比。以固定大小的電路，板面積固定為20 cm €?0 cm，元件封裝類型從小到大逐漸增加到40種，元件數量根據元件封裝類型數量生成，所測試的數據如表1所示，測試結果如圖3所示。從圖3中可看出整體的優化效果算法GAAA比GA 提高了近20%。這表明GAAA的全局搜索性能更好。此外，隨著元件數量的增加， GAAA算法的優化性能也更好。

6 結論

本文以貼片機貼裝順序優化問題為研究對象，綜合遺傳算法與蟻群算法的優點，分步計算待優化的研究對象，在計算過程的前期使用遺傳算法大范圍全局搜索的能力得出一組優化解，以這組優化解為基礎初始化蟻群算法的初始信息素。在計算過程的后期，利用蟻群算法快速收斂的特性來快速、精確地確定貼片順序的最優化組合。仿真結果表明，使用GAAA算法比單純的GA算法提高了近20%，特別是當元件封裝類型及數量增多后，GAAA算法的優勢更加明顯。

參考文獻

[1]KHOO L P， NG T K. A genetic algorithm-based planning system for PCB component placement [J]. International Journal of Production Economics， 1998.54(3): 293-307.

[2]LEU M C， WONG HJI Z. Planning of component placement/insertion sequence and feeder setup in PCB assembly using genetic algorithms [J]. Journal of Electronic Packaging， Transaction of the ASME， 1993.115(4):424-432.

[3]K．Altinkemer， B.Kazaz， M.Koksalan， ect. Optimization of printed circuit board manufacturing: integrated modeling and algorithms [J]. European Journal of Operational Research. 2000.124(2): 409-421.

[4]徐光宇.基于蟻群算法的表面貼裝優化研究[D].西安電子科技大學碩士學位論文，2007.

[5]曾又姣，金燁.基于遺傳算法的貼片機貼裝順序優化[J].計算機集成制造系統，2004.10(2):205-208.

[6]段海濱.蟻群算法原理及其應用[M].北京:航空航天大學出版社，2005:15-98.

[7]曾又姣，金燁，嚴峻琪.印刷電路板裝聯過程中元器件貼裝的優化模型[J].計算機工程，2003.29(11):156-158.

[8]雷英杰，張善文，李續武，周創明.MATLAB遺傳算法工具箱及應用[M].西安電子科技大學出版社，2005:84-175.