基于改進(jìn)蟻群算法的芯片擺盤路徑規(guī)劃研究

王蒙蒙，俞 洋

（江蘇理工學(xué)院 電氣信息工程學(xué)院，江蘇 常州 213001）

0 引 言

現(xiàn)如今芯片在社會(huì)發(fā)展中的地位愈發(fā)重要，極大推動(dòng)了電子信息技術(shù)的發(fā)展[1]。而在工業(yè)生產(chǎn)過(guò)程中，在封裝芯片之前需要對(duì)其進(jìn)行特定的擺盤以便于后續(xù)的封裝。由于芯片具有體積微小、質(zhì)量要求嚴(yán)格、生產(chǎn)量大等特點(diǎn)，若使用傳統(tǒng)的人工擺盤，不僅會(huì)存在很高的錯(cuò)誤率，還會(huì)極大影響擺盤效率。企業(yè)想以更快的速度滿足客戶的需求，對(duì)芯片擺盤環(huán)節(jié)進(jìn)行優(yōu)化研究，縮短擺盤時(shí)間，具有極其重要的意義。芯片擺盤優(yōu)化的核心是擺盤路徑的規(guī)劃，這類問(wèn)題的關(guān)鍵就是在一定約束下找出最優(yōu)路徑。通常采用的方法是啟發(fā)式算法，包括：蟻群算法[2]、粒子群算法[3]、遺傳算法[4]、模擬退火算法[5]等。

本文針對(duì)芯片擺盤存在的問(wèn)題，提出了一種新的芯片擺盤方法，提高了芯片擺盤的效率。本方法通過(guò)改進(jìn)蟻群算法存在的缺陷[6-9]，利用遺傳算法尋找出較優(yōu)路徑集合，改進(jìn)信息素更新方式，采用精英螞蟻策略保證蟻群算法前期最優(yōu)解的搜索質(zhì)量，同時(shí)對(duì)生成的信息素值進(jìn)行限定。其次，為了提高適應(yīng)蟻群搜索的能力，采用自適應(yīng)信息素?fù)]發(fā)因子代替自定義揮發(fā)因子，合理地調(diào)整信息素濃度。最后，添加了路徑交叉檢測(cè)與消除來(lái)進(jìn)一步提高每一次迭代得到的最優(yōu)解的質(zhì)量。將改進(jìn)的算法應(yīng)用到芯片擺盤問(wèn)題中，通過(guò)實(shí)驗(yàn)證明了新的算法對(duì)芯片擺盤效率的提升作用。

1 芯片擺盤路徑規(guī)劃的數(shù)學(xué)模型

1.1 問(wèn)題描述

通過(guò)機(jī)械手完成將振動(dòng)盤中的芯片擺放到芯片胚盤中的任務(wù)，已知在擺盤過(guò)程中，振動(dòng)盤位置、芯片型號(hào)、芯片放置位置等信息存在以下3 點(diǎn)約束：（1）每個(gè)芯片位置只能走訪一次；（2）機(jī)械手一次性最多抓取三個(gè)芯片；（3）機(jī)械手只能從起點(diǎn)芯片放置盤位置出發(fā)，最后要返回到芯片放置盤位置。

本問(wèn)題的目標(biāo)是在滿足上述約束條件下，找出一條路徑最短的路線，將振動(dòng)盤中的芯片全部擺放完。

1.2 建立模型

根據(jù)上述問(wèn)題描述，結(jié)合芯片擺盤的實(shí)際問(wèn)題進(jìn)行分析，本文在已有研究的基礎(chǔ)上，將芯片封裝時(shí)的擺盤路徑問(wèn)題抽象為旅行商售貨問(wèn)題（TSP）的一種拓展延伸，構(gòu)建一種以路徑最短為目標(biāo)的優(yōu)化數(shù)學(xué)模型。芯片在待擺盤前會(huì)被放置于振動(dòng)盤中，振動(dòng)盤在擺盤時(shí)會(huì)停止振動(dòng)，且其中只會(huì)有同一型號(hào)的芯片存在，本文以ATA6662 型號(hào)芯片為目標(biāo)物料建立數(shù)學(xué)模型。

在振動(dòng)盤a中，有N個(gè)待擺盤芯片，可以記作為n=1,2,3,...,N-1，N，待擺盤芯片的位置記作為l=1,2,...,i,j,L。芯片與芯片之間的距離可表示為：

式（1）表示歐氏距離[10]，其中（x，y）代表芯片的坐標(biāo)；n∈N表示振動(dòng)盤中所有待擺盤芯片；i，j∈L表示待擺盤芯片的位置；dij表示兩個(gè)芯片之間的距離。后文用Yaij表示振動(dòng)盤a中先擺放i再擺放j；Zia表示從振動(dòng)盤a的i位置吸取芯片；C表示機(jī)器一次最多抓取芯片的個(gè)數(shù)。

本模型忽略擺放到芯片放置盤中的具體位置之差，僅將其放置盤視為一個(gè)坐標(biāo)點(diǎn)，且擺放次序也是從左往右、從上到下。將擺盤的最短路徑作為目標(biāo)函數(shù)，目標(biāo)函數(shù)為：

約束條件如下：

式（2）為目標(biāo)函數(shù)，式（3）確保每個(gè)芯片只抓取一次，式（4）中用Pijk表示是否訪問(wèn)過(guò)芯片i和芯片j，取1 表示訪問(wèn)過(guò)，反之則沒(méi)有訪問(wèn)。將機(jī)械手k經(jīng)過(guò)的所有芯片位置距離進(jìn)行累加，從中選取距離最短的路徑作為所要求得的最優(yōu)解。式（5）和（6）聲明每個(gè)位置只經(jīng)過(guò)一次，且只有一個(gè)前任和后繼，式（7）表示機(jī)器一次最多抓取3 個(gè)芯片。

2 蟻群算法

蟻群算法是由Marco Dorigo 博士于1992年提出的，其通過(guò)觀察螞蟻覓食行為而得到靈感，在針對(duì)組合優(yōu)化問(wèn)題的研究中，呈現(xiàn)出了頗為優(yōu)秀的效果。

2.1 構(gòu)建路徑

假設(shè)將各個(gè)螞蟻隨機(jī)放置在不同的位置，要求每只螞蟻k訪問(wèn)完每一個(gè)城市且不重復(fù)，直至所有螞蟻訪問(wèn)結(jié)束。在此期間螞蟻選擇的下一個(gè)訪問(wèn)城市遵循選擇路徑規(guī)則和信息素分布規(guī)則，選擇的概率表示為：

其中：

式（8）中i、j分別為兩個(gè)節(jié)點(diǎn)，τij(t)為t時(shí)刻由i到j(luò)的信息素濃度；公式（9）中ηij(t)為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的期望值。根據(jù)公式可知，節(jié)點(diǎn)距離越小，信息素濃度越大，該節(jié)點(diǎn)被選擇的概率越大。

2.2 更新信息素

在每一輪螞蟻遍歷完所有城市后，為了防止尋優(yōu)過(guò)程中路徑上信息素積累過(guò)多，從而導(dǎo)致覆蓋還未訪問(wèn)的城市的情況，需要對(duì)信息素進(jìn)行更新處理，表達(dá)式如下：

式中：初始信息素為0；ρ為揮發(fā)系數(shù)，取值范圍為0～1；Δτij為信息素增加量；Q為常量；Dk表示螞蟻k訪問(wèn)過(guò)的路徑長(zhǎng)度。

3 改進(jìn)蟻群算法

本文針對(duì)傳統(tǒng)蟻群算法作如下改進(jìn)：一是調(diào)整信息素更新的方式；二是改進(jìn)信息素?fù)]發(fā)因子ρ；三是為防止所尋求出來(lái)的最優(yōu)路徑存在交叉，進(jìn)行路徑交叉消除。

3.1 改進(jìn)信息素更新

在信息素更新方面做了如下調(diào)整：

（1）基于遺傳算法產(chǎn)生初始信息素分布；

（2）采用精英螞蟻策略代替?zhèn)鹘y(tǒng)信息素更新規(guī)則；

（3）限制信息素范圍。

3.1.1 基于遺傳算法產(chǎn)生初始信息素

為解決缺乏初始信息素的情況，提出先利用遺傳算法快速尋找出較優(yōu)路徑集合，然后根據(jù)適應(yīng)度的大小進(jìn)行排序，選擇適應(yīng)度值較大的前40%個(gè)體產(chǎn)生信息素，作為蟻群算法的初始信息素。由式（13）和式（14）得到初始信息素分布情況。

式中：M為種群數(shù)量；Dm為個(gè)體m所走過(guò)的路徑長(zhǎng)度；S為一個(gè)常量。

3.1.2 精英螞蟻策略

針對(duì)信息素更新使得信息素累積較快導(dǎo)致陷入局部最優(yōu)的情況，調(diào)整信息素更新方式。傳統(tǒng)的蟻群算法中，當(dāng)螞蟻遍歷完所有城市后路徑上的信息素隨著時(shí)間的推移會(huì)按照一定規(guī)則進(jìn)行揮發(fā)，但在此過(guò)程中容易造成算法陷入局部最優(yōu)的問(wèn)題。因此，針對(duì)該問(wèn)題提出改進(jìn)信息素更新規(guī)則，采用精英螞蟻策略，當(dāng)一次迭代后全部螞蟻都已經(jīng)走完自己的路徑后，選擇出最短路徑的個(gè)體，讓其再一次重復(fù)信息素的更新過(guò)程，這樣可以使得信息素更新更加合理。公式（15）～（17）為信息素更新。

式中：Dk表示螞蟻k所走過(guò)的路徑長(zhǎng)度；Dbestk表示精英螞蟻所走的最優(yōu)路徑；Δτij為初始信息素值。

3.1.3 限制信息素范圍

針對(duì)后期信息素積累過(guò)多導(dǎo)致陷入局部最優(yōu)的情況，本文根據(jù)MMAS 思想，對(duì)信息素的取值范圍進(jìn)行限制。

信息素最大值τmax的設(shè)置是根據(jù)式（10）和式（18）計(jì)算化簡(jiǎn)而來(lái)，其中Dbestroute為尚未更新的最優(yōu)解，Dnowbestroute為當(dāng)前迭代中最優(yōu)解，每次迭代τmax(t)都會(huì)根據(jù)當(dāng)前路徑最優(yōu)解與信息素?fù)]發(fā)因子變化而變化。信息素最小值τmin是根據(jù)遺傳算法所獲得的初始信息素值而設(shè)置的。

3.2 改進(jìn)信息素?fù)]發(fā)因子

以往的蟻群算法中信息素?fù)]發(fā)因子是通過(guò)人為設(shè)定一個(gè)介于0～1 之間的值，若ρ設(shè)置過(guò)小，容易導(dǎo)致太早就收斂，最優(yōu)解的全局性降低；若ρ設(shè)置過(guò)大，會(huì)造成算法收斂速度慢[11]。由此可以發(fā)現(xiàn)人為設(shè)定值存在不確定性，導(dǎo)致信息素分布并不合理，影響了算法的精確性。因此本文提出信息素因子自適應(yīng)策略，增加了螞蟻搜索路徑的任意性。

當(dāng)搜尋到的新路徑越短，則Dnowbestroute值越小，那么T的值會(huì)越大，ρ的值也就會(huì)越大。

算法的初期是尋優(yōu)階段，考慮到全局尋優(yōu)，因此需要ρ大一些，保證信息素含量控制的盡量低一些，提高算法的全局搜索能力，減輕信息素早期的誘導(dǎo)能力。在后期隨著尋優(yōu)階段的結(jié)束，需要加快算法的收斂速度，因此要求ρ小一些，保證信息素含量盡量高一些，增強(qiáng)算法的收斂能力。

3.3 路徑交叉消除

在求解芯片擺盤最優(yōu)路徑的過(guò)程中會(huì)出現(xiàn)所求得路徑存在著交叉，并非最優(yōu)路徑。針對(duì)這一問(wèn)題提出了路徑交叉消除[12]，進(jìn)一步提高最優(yōu)解的質(zhì)量。

3.3.1 路徑交叉檢測(cè)

判斷路徑是否存在交叉，可類比于判斷兩條線段是否有交點(diǎn)。設(shè)存在線段i→i+1 與j→j+1，兩條線段的端點(diǎn)分別為(Xi,Yi)、(Xi+1,Yi+1)、(Xj,Yj)、(Xj+1,Yj+1)，可得這兩條線段的方程為：

令

當(dāng)r(D)=2，r(A)=2 時(shí)，說(shuō)明方程組存在解，再判斷該解是否在線段范圍內(nèi)，即：

若皆滿足，則確定存在路徑交叉。

3.3.2 交叉消除

當(dāng)路徑i→i+1 與j→j+1 存在交叉，其中i+1

3.4 算法描述

首先利用遺傳算法求出較優(yōu)路徑[13]，產(chǎn)生蟻群算法所需要的初始信息素，解決蟻群算法缺乏初始信息素的問(wèn)題。

機(jī)械手從芯片放置盤處出發(fā)，計(jì)算其轉(zhuǎn)移概率PKij確定從i點(diǎn)轉(zhuǎn)移到j(luò)點(diǎn)處，并判斷機(jī)械手抓取是否達(dá)到最大抓取容量C，若未達(dá)到最大容量，則返回到芯片放置盤處，保留本次的行經(jīng)路線，并再重新創(chuàng)建一條新路徑，更新當(dāng)前的位置；反之則機(jī)械手移動(dòng)到下一個(gè)待抓取芯片處并更新局部信息素。

根據(jù)禁忌表中的數(shù)據(jù)判斷是否已經(jīng)遍歷完所有芯片所在位置，若已經(jīng)全部途經(jīng)過(guò)，則機(jī)械手返回起始位置處，結(jié)束本次迭代；否則，機(jī)械手繼續(xù)計(jì)算狀態(tài)轉(zhuǎn)移尋找下一個(gè)芯片，重復(fù)上述步驟。

在每輪迭代結(jié)束后，利用路徑交叉檢測(cè)判斷最優(yōu)路徑中是否存在交叉，若存在，則進(jìn)行路徑交叉消除，并只更新最優(yōu)路徑上的信息素，代替?zhèn)鹘y(tǒng)信息素更新方式。

判斷是否已經(jīng)達(dá)到最大迭代次數(shù)，若判斷為真，則結(jié)束算法運(yùn)行，并輸出最優(yōu)解；反之繼續(xù)進(jìn)行下一輪迭代。改進(jìn)后的蟻群算法的流程如圖1所示。

圖1 改進(jìn)蟻群算法流程

4 實(shí)驗(yàn)仿真與結(jié)果分析

針對(duì)芯片封裝環(huán)節(jié)中的擺盤問(wèn)題，對(duì)提出的改進(jìn)蟻群算法的芯片擺盤進(jìn)行實(shí)驗(yàn)仿真分析。使用MATLAB 作為仿真工具，隨機(jī)設(shè)置了31 個(gè)坐標(biāo)，其中一個(gè)為芯片胚盤位置，作為起始點(diǎn)，其余坐標(biāo)為振動(dòng)盤中待擺盤芯片位置，如圖2所示。設(shè)置改進(jìn)的蟻群算法的各個(gè)參數(shù)值，蟻群算法中的螞蟻數(shù)量設(shè)置為80，最大迭代次數(shù)設(shè)置為150，保證尋優(yōu)的同時(shí)也縮短算法運(yùn)行時(shí)間。經(jīng)測(cè)試得，將信息素重要系數(shù)設(shè)置為1 時(shí)，搜索性能最好。啟發(fā)函數(shù)系數(shù)的初始值設(shè)置為5，信息素啟發(fā)因子初始值設(shè)置為0.8 時(shí)，可以保證信息素的合理分配，提高算法的全局尋優(yōu)能力。

圖2 胚盤及芯片位置分布

圖2標(biāo)注的起點(diǎn)是芯片所需擺放到的胚盤位置，其余30個(gè)坐標(biāo)為芯片所在的位置坐標(biāo)。分別使用蟻群算法、文獻(xiàn)[7]中算法和改進(jìn)后的蟻群算法進(jìn)行搜索遍歷，并對(duì)這三種算法的最優(yōu)路徑進(jìn)行對(duì)比。

圖3為傳統(tǒng)蟻群算法搜索遍歷的最優(yōu)路徑，其最短距離為389.644 7。圖4為文獻(xiàn)[7]算法下的最優(yōu)路徑，其最短距離為376.711 4。圖5為改進(jìn)融合后的遺傳-蟻群算法搜索遍歷的最優(yōu)路徑，其最短距離為368.589 1。

圖3 傳統(tǒng)蟻群算法下的最優(yōu)路徑

圖4 文獻(xiàn)[7]算法下的最優(yōu)路徑

圖5 改進(jìn)蟻群算法下的最優(yōu)路徑

對(duì)比三種算法的實(shí)驗(yàn)結(jié)果，如圖6的最優(yōu)路徑對(duì)比圖所示，可知使用改進(jìn)后的蟻群算法所得到的最優(yōu)路徑距離最短。

圖6 算法最優(yōu)路徑

由表1中的數(shù)據(jù)可知，改進(jìn)的蟻群算法在最優(yōu)路徑距離方面，較傳統(tǒng)蟻群算法提高了5.4%，較文獻(xiàn)[7]算法提高了2.16%；在最優(yōu)迭代點(diǎn)上，均比其他兩種算法提早尋找到最優(yōu)解，驗(yàn)證了改進(jìn)后算法的性能更優(yōu)。

表1 實(shí)驗(yàn)算法數(shù)據(jù)

5 結(jié) 語(yǔ)

結(jié)合芯片生產(chǎn)中的實(shí)際情況，對(duì)芯片擺盤問(wèn)題進(jìn)行分析，本文提出了改進(jìn)蟻群算法的芯片擺盤路徑規(guī)劃。為了避免算法陷入局部最優(yōu)，提高算法的全局搜索能力，本文從如下方面對(duì)蟻群算法進(jìn)行改進(jìn)：

（1）先利用遺傳算法求出較優(yōu)路徑，然后根據(jù)適應(yīng)度的大小進(jìn)行排序，選擇適應(yīng)度值較大的個(gè)體產(chǎn)生初始信息素，解決蟻群算法缺乏初始信息素的問(wèn)題；并改進(jìn)信息素更新方式，每次迭代只使用最優(yōu)路徑的信息素值，同時(shí)對(duì)信息素值設(shè)置了限定的區(qū)間。

（2）改進(jìn)信息素?fù)]發(fā)因子，采用自適應(yīng)信息素?fù)]發(fā)因子來(lái)代替人為設(shè)定固定值，合理地調(diào)整信息素?fù)]發(fā)因子的大小，增強(qiáng)蟻群搜索的能力。

（3）針對(duì)最優(yōu)解中存在路徑交叉問(wèn)題，添加了路徑交叉檢測(cè)與消除，對(duì)所求得最優(yōu)解進(jìn)一步進(jìn)行優(yōu)化。

本文通過(guò)MATLAB 工具進(jìn)行仿真，從定點(diǎn)出發(fā)遍歷搜索完所有點(diǎn)再回到起始點(diǎn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)融合的蟻群算法較傳統(tǒng)蟻群算法，最優(yōu)解距離減少了5.4%；較文獻(xiàn)[7]算法最優(yōu)解距離減少了2.16%，在尋找最優(yōu)解和前期搜索效率方面都要優(yōu)于傳統(tǒng)算法，提高了芯片擺盤的效率，驗(yàn)證了本算法的有效性。