貼片機(jī)貼裝路徑優(yōu)化的改進(jìn)遺傳算法

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

（西南交通大學(xué)，四川 成都 610031）

貼片機(jī)貼裝路徑優(yōu)化的改進(jìn)遺傳算法

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

（西南交通大學(xué)，四川 成都 610031）

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

遺傳算法；貼片機(jī)；元件貼裝順序優(yōu)化；復(fù)合算子

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

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

1 貼片機(jī)原理及數(shù)學(xué)模型

1.1 貼片機(jī)結(jié)構(gòu)和貼裝問題描述

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

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

圖1 貼片機(jī)的內(nèi)部結(jié)構(gòu)示意圖

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

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

1.2 數(shù)學(xué)模型

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

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

式（2）為短距離時間，式（3）為長距離時間，因?yàn)関、a都是固定參數(shù)的設(shè)定值。故根據(jù)公式（1）和公式（2）、（3）求貼裝時間的最小值便可以簡化為求式（4）的最小值，即：

式（5）中a為固定標(biāo)度轉(zhuǎn)換參數(shù)）

式（4）中d1表示貼裝循環(huán)內(nèi)貼片頭要移動的距離，d2表示循環(huán)間貼片頭要移動的距離。距離的計(jì)算采用歐式距離，根據(jù)公式（4）可知，遺傳算法的適應(yīng)度函數(shù)可參考公式（5），即對公式F最大值的尋優(yōu)。

2 研究現(xiàn)狀與算法介紹

2.1 研究現(xiàn)狀

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

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

貼片機(jī)上的優(yōu)化問題屬于復(fù)雜的組合優(yōu)化問題，從己有的數(shù)學(xué)模型來看都屬于NP-hard問題。隨著貼片機(jī)本身的結(jié)構(gòu)和性能在不斷的更新和改進(jìn)，人們也在探索新的方法來得到更好的結(jié)果。

2.2 遺傳算法

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

在對貼片機(jī)貼裝順序優(yōu)化的應(yīng)用中，遺傳算法展現(xiàn)出了優(yōu)勢，但傳統(tǒng)的遺傳算法在全局性和收斂速度上都存在缺點(diǎn)，而且貼片機(jī)高速發(fā)展，現(xiàn)在需要更有效率的算法，本文提出了一種有效的改進(jìn)算法。

3 改進(jìn)遺傳算法

3.1 復(fù)合算子

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

圖2 改進(jìn)遺傳算法流程圖

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

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

步驟一：以10個元件為例，計(jì)算種群中每一個個體的適應(yīng)度函數(shù)，并進(jìn)行排序；

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

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）；

步驟三：計(jì)算這一半個體di的均值并設(shè)定為閾值；

步驟四：在另一半個體中根據(jù)閾值進(jìn)行過濾，統(tǒng)計(jì)di大于閾值的次數(shù)，超過設(shè)定個數(shù)則淘汰之；

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

該算子在優(yōu)化問題中，就是通過不斷產(chǎn)生靠近最優(yōu)個體的優(yōu)良個體來代替當(dāng)前群體中的最差個體，達(dá)到不斷改善群體結(jié)構(gòu)，加速收斂進(jìn)程的目的，這與遺傳算法核心理念是一致的。

3.2 復(fù)制算子

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

3.3 交叉算子

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

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

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

（2）隨機(jī)產(chǎn)生一個交叉點(diǎn)P，并在交叉點(diǎn)到最后節(jié)點(diǎn)之間產(chǎn)生一個隨機(jī)數(shù)S。

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

如父代雙親為：

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

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

若隨機(jī)產(chǎn)生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］

刪去重復(fù)基因得到新的子代個體：

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

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

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

3.4 變異算子

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

（1）隨機(jī)產(chǎn)生位于［1，N］的基因突變位，假設(shè)變異位為i；

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

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

假設(shè)N=10，i=5。

個體變異前的基因序列：

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

個體變異后的基因列：

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

通過對種群進(jìn)行單點(diǎn)基因位對稱變異，從局部的角度進(jìn)行優(yōu)化搜索，最終向整體最優(yōu)解收斂。

4 實(shí) 驗(yàn)

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

表1 元器件坐標(biāo)mm

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

圖3 傳統(tǒng)遺傳算法和本文算法優(yōu)化過程圖（實(shí)線為改進(jìn)遺傳算法）

從圖3不難看出，傳統(tǒng)遺傳算法在解決貼片機(jī)貼裝路徑優(yōu)化上效果并不是很好，算法收斂速度慢，全局性差，難以達(dá)到最優(yōu)解。從圖4可以看出，單親進(jìn)化遺傳算法雖然有比較好的收斂速度和全局性，但是因?yàn)閷Ω复N群選擇的過度優(yōu)化，導(dǎo)致收斂過快，影響全局性，陷入局部最優(yōu)解的困境，而難以達(dá)到全局最優(yōu)解。

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