貼片機貼裝路徑優化的改進遺傳算法

董健騰，龍緒明，曹宏耀，呂文強，胡少華，朱舜文，曾馳鶴

（西南交通大學，四川 成都 610031）

貼片機貼裝路徑優化的改進遺傳算法

董健騰，龍緒明，曹宏耀，呂文強，胡少華，朱舜文，曾馳鶴

（西南交通大學，四川 成都 610031）

貼片機貼裝順序是影響設備生產效率的重要問題，針對此問題，已有各種優化算法提出，包括遺傳算法。但是傳統的遺傳算法（GA）包括一些改進的遺傳算法，在解決這個問題上還是存在全局性差、收斂速度慢和易陷入局部最優解的問題。在此基礎上加入一個復合算子來優化種群，保證向最優解收斂的同時兼顧種群多樣性。配合有效的交叉算子和變異算子，在優化結果上有了更大的改進，能更有效地提高貼裝效率。

遺傳算法；貼片機；元件貼裝順序優化；復合算子

隨著表面組裝技術 SMT（Surface Mounted Technology）越來越廣泛的應用，電子產品裝配較之手工裝配發生了質的飛躍，SMT裝配線中的關鍵設備貼片機得到了廣泛的關注。為進一步的提高貼片機的性能，其關鍵因素之一就是提高貼片的效率。對于單臺貼片機而言，提高貼片的效率存在兩個關鍵的問題：即貼片機送料器位置分配問題和元件的貼裝順序優化問題。這兩者都屬于NP-Hard問題，其中后一個問題在單頭貼片機情況下一般被規劃為旅行商問題 （Traveling Salesman Problem，TSP）［2］。很多學者已經對此提出了各種算法來優化，包括不少遺傳算法（GA）［2，3］。但隨著貼片機技術的發展，貼片機的結構變得越來越復雜，多頭貼片機已成為市場的潮流，其頭數已多達12頭，甚至更多，結構的復雜化和貼片頭的增加使得這些算法不再適用。

本文針對元件的貼裝順序優化問題提出區別于傳統遺傳算法的改進算法，以解決傳統的遺傳算法包括一些改進的遺傳算法，在解決這個問題上仍存在全局性差、收斂速度慢和易陷入局部最優解的問題。本文通過加入一個復合算子來優化種群，保證向最優解收斂的同時兼顧種群多樣性。配合有效的交叉算子和變異算子，來達到優化貼裝效率的目的。

1 貼片機原理及數學模型

1.1 貼片機結構和貼裝問題描述

貼片機類型多樣，型號復雜。按自動化程度分有全自動貼片機、手動貼片機，按工作方式分有動臂式貼片機、轉塔式貼片機等，但它們的總體結構均有類似之處，一般貼片機的主要組成部分為：工作臺、供料槽，以及用來固定裝載元器件的供料器，裝載元器件的供料器固定在兩邊的供料槽上，每個供料器占據一個或多個供料槽，元器件的取貼、旋轉等動作都是由裝在貼片頭上的吸嘴來完成。圖1是一種通用轉塔式貼片機的內部結構示意圖。

貼裝工藝：（1）上板和定位：PCB板通過傳送帶送到指定位置定位夾緊，然后由貼片頭上的移動相機對其上的MARK點進行識別，從而得到PCB板的精確位置；（2）取料：貼片頭移動到對應的送料器槽位上進行取料；（3）視覺檢查：貼片頭運動到固定相機上進行視覺檢查，判斷芯片好壞，并得到元件的偏轉角度，距離中心的偏移位置等信息；（4）貼裝：根據工藝表和視覺檢查信息，貼片頭運動到準確的貼裝位置進行貼裝；（5）拋料：本組貼裝完畢后，運動到拋料點位置將視覺檢查不合格元件進行拋料；（6）重復第二至第五步驟直到貼裝完成；（7）下板：完成所有的貼裝點后，松開夾具，通過送板機構將貼裝完畢的PCB板送出。

圖1 貼片機的內部結構示意圖

對于貼片機貼裝路徑優化問題：已知印制板上各個元器件的裝配位置，尋求一個貼片機頭遍歷這些裝配位置的路徑，尋求開銷最小。該問題與經典的TSP問題有相似之處，屬于非對稱TSP問題，是遍歷整個集合，求最小值問題。不同的是，貼片機貼裝要分批進行，如1個4吸嘴的貼片頭一個貼裝循環內只能貼裝4個元器件，一次循環結束后貼片頭要返回工料站進行取料再開始下一個循環。

由上面的分析可知，貼片機貼裝時間包括：取料時間，貼裝時間，循環間吸取原料的時間及棄料拋料時間等。整個貼片機的貼裝過程是一個比較復雜的過程，幾個問題相互關聯，互相影響，很難一次解決，因此大量的研究都是將問題分解成若干個子問題進行研究，先求得局部的最優解，進而得到全局最優解。本文所研究的范圍，就是將送料器的位置固定，將元件取貼順序作為優化的目標。

1.2 數學模型

基于上一節的描述，本文參照文獻［4，5］做以下假設：（1）假設供料器位置為原點；（2）將不影響問題本質的貼裝頭的旋轉時間忽略；（3）假設吸嘴吸片時間固定，貼片時間固定。故一個完整的貼裝時間可以表示為：

式中，表示第i個循環內貼片頭總移動時間，表示貼片頭從第i個循環的最后一個元件貼裝完畢到移動至下一個循環的第一個元件的貼裝位置所需時間，ti表示第i個元件的貼片時間。在上文中已經提到，假設每個元件的貼片時間一定，故第三個參數不影響貼裝路徑優化。s表示總循環次數，n表示總元件個數。貼片機貼片運動按距離遠近，x、y方向的運動有加速-減速（短距離）、加速-恒速-減速（長距離）兩種形式。如果設定運動距離為S、加速度為a、恒速度為v可得到對應的運動時間t的計算公式：

式（2）為短距離時間，式（3）為長距離時間，因為v、a都是固定參數的設定值。故根據公式（1）和公式（2）、（3）求貼裝時間的最小值便可以簡化為求式（4）的最小值，即：

式（5）中a為固定標度轉換參數）

式（4）中d1表示貼裝循環內貼片頭要移動的距離，d2表示循環間貼片頭要移動的距離。距離的計算采用歐式距離，根據公式（4）可知，遺傳算法的適應度函數可參考公式（5），即對公式F最大值的尋優。

2 研究現狀與算法介紹

2.1 研究現狀

對于貼片機的貼裝順序優化問題，已經有很多學者做了研究，提出多種算法來解決，包括遺傳算法、蟻群算法、傘布搜索法、差分算法、模擬退火算法、啟發式算法等。

國外研究成果較多，比如 M.o.Ball和MJ. Magazine［10］提出了一種類似“郵遞員”問題的優化算法對單吸頭、電路板和供料器靜止的貼片機貼裝順序進行優化；Nevalainen［11］提出將整個優化問題可以分成兩個子問題，使用二次分配問題來解決供料器的分配問題，用非對稱旅行商問題來解決貼放順序問題；Edmund.K.Burke等人［13］提出一種整體模型使用啟發式算法對多頭拱架式貼片機進行優化研究。國內對此研究起步較晚，比如袁鵬等人［13］使用傘布搜索算法分別在元器件供料器位置固定的情況下，對多吸嘴拱架式貼片機進行優化研究；杜軒等人［14］使用遺傳算法在貼片順序確定的情況下進行供料器的分配優化研究；田福厚等人［15］使用遺傳算法對轉塔式貼片機貼裝過程進行優化研究。

貼片機上的優化問題屬于復雜的組合優化問題，從己有的數學模型來看都屬于NP-hard問題。隨著貼片機本身的結構和性能在不斷的更新和改進，人們也在探索新的方法來得到更好的結果。

2.2 遺傳算法

遺傳算法是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機智能搜索方法。遺傳算法在群體進化過程中發生繁殖、雜交和突變現象，不斷發現重要基因。尋找較好模式的過程中，高適應度的個體被選擇的概率大于低適應度的個體，則好的基因得以遺傳下來，不好的基因被剔除，經過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優解或次優解。算法主要包括3部分：多樣性初始種群的產生，種群的優化更新（其中的算子包括復制算子、交叉算子和變異算子），最優個體的出現。

在對貼片機貼裝順序優化的應用中，遺傳算法展現出了優勢，但傳統的遺傳算法在全局性和收斂速度上都存在缺點，而且貼片機高速發展，現在需要更有效率的算法，本文提出了一種有效的改進算法。

3 改進遺傳算法

3.1 復合算子

遺傳算法簡單通用，具有很強的全局搜索能力，但是，大量的實踐數據表明，遺傳算法在優化過程中局部搜索能力差，容易陷入早熟收斂，群體的多樣性急劇降低，導致個體之間的競爭力度大大降低，群體的進化能力基本喪失。其表現就是遺傳算法往往收斂不到全局最優解。為此本文提出改進遺傳算法流程圖，見圖2所示。

圖2 改進遺傳算法流程圖

為了使遺傳算法具有快速局部尋優能力，對其進行改進優化，我們必須解決兩個關鍵問題：（1）保證最優解的搜索方向；（2）維持群體的多樣性。我們提出的改進遺傳算法的思路就是將復合算子，融入到遺傳算法中，起到引導群體搜索方向，改善群體多樣性的作用。

復合算子的設計思路源自文獻［3］，它將貼裝優化過程簡化成一個非對稱的TSP問題，提出用單親進化遺傳算法（PEGA）解決問題。主體思路是盡可能的利用父染色體中基因片段的信息，將貼片間距大于某一閾值的基因串打斷，由此將個體分成一個個的子串，保留優秀子串。但是該算法亦存在種群多樣性差，易陷入局部解的問題。本文在它的基礎上提出復合算子，步驟如下：

步驟一：以10個元件為例，計算種群中每一個個體的適應度函數，并進行排序；

步驟二：挑出適應度較高的一半個體，比如其中一個個體為：

F為2 4 5 9 6 1 3 7 8 0，貼片移動距離di為（2，4），（4，5），（5，9），（9，6），（6，1），（1，3），（3，7），（7，8），（8，0）；

步驟三：計算這一半個體di的均值并設定為閾值；

步驟四：在另一半個體中根據閾值進行過濾，統計di大于閾值的次數，超過設定個數則淘汰之；

步驟五：用高適應度個體通過反射函數，在約束條件確定的可行域內形成N個新個體，替換掉原來被淘汰掉的N個個體。

該算子在優化問題中，就是通過不斷產生靠近最優個體的優良個體來代替當前群體中的最差個體，達到不斷改善群體結構，加速收斂進程的目的，這與遺傳算法核心理念是一致的。

3.2 復制算子

遺傳算法中通過個體的適應度來對群體中個體的好壞程度進行評判，復制算子把當前群體中的個體按照與適應度成比例的概率復制到新的群體中。本文采用經典的輪盤賭選擇方法：每個個體進入下一代的概率等于它的適應度值與整個種群中個體適應度之和的比例，適應度值越高，進入下一代的概率就越大。

3.3 交叉算子

生物的進化中，父代根據基因交配進行遺傳信息的重組，誕生子代。交叉算子是依據較大的概率從群體中選擇兩個父代，交換兩個個體之間的某個或某些基因位，繼承父代的基本特征。遺傳算法的收斂性主要取決于交叉算子的收斂性［9］。

在此采用一種高效的交叉算子，使最優解出現的更快，算法效率更高。操作過程如下：

（1）對種群個體兩兩組合形成父代雙親。

（2）隨機產生一個交叉點P，并在交叉點到最后節點之間產生一個隨機數S。

（3）分別把雙親中每個個體自交叉點后的S個基因位按照原序列放在另一個體前面，后依次刪去重復的基因位，如此產生出子代。

如父代雙親為：

P1=［8，7，2，6，5，1，9，10，3，4］

P2=［2，4，6，5，9，10，1，3，8，7］

若隨機產生P=2，S=3，

則步驟2之后

P1'=［6，5，9，8，7，2，6，5，1，9，10，3，4］

P2'=［2，6，5，2，4，6，5，9，10，1，3，8，7］

刪去重復基因得到新的子代個體：

P1=［6，5，9，8，7，2，1，10，3，4］

P2=［2，6，5，4，9，10，1，3，8，7］

比較兩個父代和子代的適應度，選擇適應度最大的留下來，作為最終的子代個體。這樣保證了每次都遺傳最好的基因，加快了最優解出現的速度。

3.4 變異算子

變異算子是以較小概率，一般為0.001至0.1，對個體某些基因位進行改變，傳統的二進制編碼是通過“0”、“1”互換方式產生新個體。但本課題中元件染色體上的基因不再是非0即1的二元結果，而是隨元件貼裝點的個數變化的某一區間。依據上文雙點交叉算子的思想，我們提出了基于單點的基因位對稱變異算子。假設：設貼裝總數為N，變異基因位為i，M代表某一位基因位，選擇某個體進行變異操作。

（1）隨機產生位于［1，N］的基因突變位，假設變異位為i；

（2）若個體基因位為偶數時，交換Mi與MN+1-i兩個位置上的基因；

（3）若個體基因位為基數時，除基因位i= （N+1）/2的基因不發生改變，其他情況交換Mi與MN+1-i兩個位置上的基因；

假設N=10，i=5。

個體變異前的基因序列：

8-＞7-＞2-＞6-＞5-＞9-＞3-＞1-＞10-＞4

個體變異后的基因列：

8-＞7-＞2-＞6-＞9-＞5-＞3-＞1-＞10-＞4

通過對種群進行單點基因位對稱變異，從局部的角度進行優化搜索，最終向整體最優解收斂。

4 實 驗

實驗以一個擁有20個元器件的PCB板為例，其中PCB板的尺寸為200 mm×100 mm，供料器坐標位置為（0，0），各個元件的坐標如表1所示。

表1 元器件坐標mm

設定初始種群大小為30，迭代次數為300，交叉概率為0.9，變異概率為0.01，則采用傳統遺傳算法、單親進化遺傳算法和本文提出的改進遺傳算法的優化過程對比圖分別如圖3和圖4所示。

圖3 傳統遺傳算法和本文算法優化過程圖（實線為改進遺傳算法）

從圖3不難看出，傳統遺傳算法在解決貼片機貼裝路徑優化上效果并不是很好，算法收斂速度慢，全局性差，難以達到最優解。從圖4可以看出，單親進化遺傳算法雖然有比較好的收斂速度和全局性，但是因為對父代種群選擇的過度優化，導致收斂過快，影響全局性，陷入局部最優解的困境，而難以達到全局最優解。

Application of Improved Genetic Algorithm in Optimization of Placement Path of Placement Machine

DONG Jianteng，LONG Xuming，CAO Hongyao，LV Wenqiang，HU Shaohua，ZHU Shunwen，ZENG Chihe
（College of Electrical Engineering，Southwest Jiaotong University，Chengdu 610031，China）

The sequence of placement has a great influence to the efficiency of the placement machine. In view of this problem，there are various optimization algorithms，including genetic algorithm mentioned in this paper.But the traditional genetic algorithm （GA），including some improved genetic algorithm，in the solution of the problem or the existence of the global poor，slow convergence speed and easy to fall into local optimal solution.In this paper，a composite operator is added to optimize the population，which is guaranteed to converge to the optimal solution.With the effective crossover operator and mutation operator，the optimization results and the efficiency of mounting have a greater improvement.

Genetic algorithm；Chip mounter；Component placement sequence optimization；Complex operator

TN605

A

1004-4507（2015）12-0017-06

2015-11-19