基于改進蟻群算法的芯片擺盤路徑規劃研究

王蒙蒙，俞 洋

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

0 引 言

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

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

1 芯片擺盤路徑規劃的數學模型

1.1 問題描述

通過機械手完成將振動盤中的芯片擺放到芯片胚盤中的任務，已知在擺盤過程中，振動盤位置、芯片型號、芯片放置位置等信息存在以下3 點約束：（1）每個芯片位置只能走訪一次；（2）機械手一次性最多抓取三個芯片；（3）機械手只能從起點芯片放置盤位置出發，最后要返回到芯片放置盤位置。

本問題的目標是在滿足上述約束條件下，找出一條路徑最短的路線，將振動盤中的芯片全部擺放完。

1.2 建立模型

根據上述問題描述，結合芯片擺盤的實際問題進行分析，本文在已有研究的基礎上，將芯片封裝時的擺盤路徑問題抽象為旅行商售貨問題（TSP）的一種拓展延伸，構建一種以路徑最短為目標的優化數學模型。芯片在待擺盤前會被放置于振動盤中，振動盤在擺盤時會停止振動，且其中只會有同一型號的芯片存在，本文以ATA6662 型號芯片為目標物料建立數學模型。

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

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

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

約束條件如下：

式（2）為目標函數，式（3）確保每個芯片只抓取一次，式（4）中用Pijk表示是否訪問過芯片i和芯片j，取1 表示訪問過，反之則沒有訪問。將機械手k經過的所有芯片位置距離進行累加，從中選取距離最短的路徑作為所要求得的最優解。式（5）和（6）聲明每個位置只經過一次，且只有一個前任和后繼，式（7）表示機器一次最多抓取3 個芯片。

2 蟻群算法

蟻群算法是由Marco Dorigo 博士于1992年提出的，其通過觀察螞蟻覓食行為而得到靈感，在針對組合優化問題的研究中，呈現出了頗為優秀的效果。

2.1 構建路徑

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

其中：

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

2.2 更新信息素

在每一輪螞蟻遍歷完所有城市后，為了防止尋優過程中路徑上信息素積累過多，從而導致覆蓋還未訪問的城市的情況，需要對信息素進行更新處理，表達式如下：

式中：初始信息素為0；ρ為揮發系數，取值范圍為0～1；Δτij為信息素增加量；Q為常量；Dk表示螞蟻k訪問過的路徑長度。

3 改進蟻群算法

本文針對傳統蟻群算法作如下改進：一是調整信息素更新的方式；二是改進信息素揮發因子ρ；三是為防止所尋求出來的最優路徑存在交叉，進行路徑交叉消除。

3.1 改進信息素更新

在信息素更新方面做了如下調整：

（1）基于遺傳算法產生初始信息素分布；

（2）采用精英螞蟻策略代替傳統信息素更新規則；

（3）限制信息素范圍。

3.1.1 基于遺傳算法產生初始信息素

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

式中：M為種群數量；Dm為個體m所走過的路徑長度；S為一個常量。

3.1.2 精英螞蟻策略

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

式中：Dk表示螞蟻k所走過的路徑長度；Dbestk表示精英螞蟻所走的最優路徑；Δτij為初始信息素值。

3.1.3 限制信息素范圍

針對后期信息素積累過多導致陷入局部最優的情況，本文根據MMAS 思想，對信息素的取值范圍進行限制。

信息素最大值τmax的設置是根據式（10）和式（18）計算化簡而來，其中Dbestroute為尚未更新的最優解，Dnowbestroute為當前迭代中最優解，每次迭代τmax(t)都會根據當前路徑最優解與信息素揮發因子變化而變化。信息素最小值τmin是根據遺傳算法所獲得的初始信息素值而設置的。

3.2 改進信息素揮發因子

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

當搜尋到的新路徑越短，則Dnowbestroute值越小，那么T的值會越大，ρ的值也就會越大。

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

3.3 路徑交叉消除

在求解芯片擺盤最優路徑的過程中會出現所求得路徑存在著交叉，并非最優路徑。針對這一問題提出了路徑交叉消除[12]，進一步提高最優解的質量。

3.3.1 路徑交叉檢測

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

令

當r(D)=2，r(A)=2 時，說明方程組存在解，再判斷該解是否在線段范圍內，即：

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

3.3.2 交叉消除

當路徑i→i+1 與j→j+1 存在交叉，其中i+1

3.4 算法描述

首先利用遺傳算法求出較優路徑[13]，產生蟻群算法所需要的初始信息素，解決蟻群算法缺乏初始信息素的問題。

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

根據禁忌表中的數據判斷是否已經遍歷完所有芯片所在位置，若已經全部途經過，則機械手返回起始位置處，結束本次迭代；否則，機械手繼續計算狀態轉移尋找下一個芯片，重復上述步驟。

在每輪迭代結束后，利用路徑交叉檢測判斷最優路徑中是否存在交叉，若存在，則進行路徑交叉消除，并只更新最優路徑上的信息素，代替傳統信息素更新方式。

判斷是否已經達到最大迭代次數，若判斷為真，則結束算法運行，并輸出最優解；反之繼續進行下一輪迭代。改進后的蟻群算法的流程如圖1所示。

圖1 改進蟻群算法流程

4 實驗仿真與結果分析

針對芯片封裝環節中的擺盤問題，對提出的改進蟻群算法的芯片擺盤進行實驗仿真分析。使用MATLAB 作為仿真工具，隨機設置了31 個坐標，其中一個為芯片胚盤位置，作為起始點，其余坐標為振動盤中待擺盤芯片位置，如圖2所示。設置改進的蟻群算法的各個參數值，蟻群算法中的螞蟻數量設置為80，最大迭代次數設置為150，保證尋優的同時也縮短算法運行時間。經測試得，將信息素重要系數設置為1 時，搜索性能最好。啟發函數系數的初始值設置為5，信息素啟發因子初始值設置為0.8 時，可以保證信息素的合理分配，提高算法的全局尋優能力。

圖2 胚盤及芯片位置分布

圖2標注的起點是芯片所需擺放到的胚盤位置，其余30個坐標為芯片所在的位置坐標。分別使用蟻群算法、文獻[7]中算法和改進后的蟻群算法進行搜索遍歷，并對這三種算法的最優路徑進行對比。

圖3為傳統蟻群算法搜索遍歷的最優路徑，其最短距離為389.644 7。圖4為文獻[7]算法下的最優路徑，其最短距離為376.711 4。圖5為改進融合后的遺傳-蟻群算法搜索遍歷的最優路徑，其最短距離為368.589 1。

圖3 傳統蟻群算法下的最優路徑

圖4 文獻[7]算法下的最優路徑

圖5 改進蟻群算法下的最優路徑

對比三種算法的實驗結果，如圖6的最優路徑對比圖所示，可知使用改進后的蟻群算法所得到的最優路徑距離最短。

圖6 算法最優路徑

由表1中的數據可知，改進的蟻群算法在最優路徑距離方面，較傳統蟻群算法提高了5.4%，較文獻[7]算法提高了2.16%；在最優迭代點上，均比其他兩種算法提早尋找到最優解，驗證了改進后算法的性能更優。

表1 實驗算法數據

5 結 語

結合芯片生產中的實際情況，對芯片擺盤問題進行分析，本文提出了改進蟻群算法的芯片擺盤路徑規劃。為了避免算法陷入局部最優，提高算法的全局搜索能力，本文從如下方面對蟻群算法進行改進：

（1）先利用遺傳算法求出較優路徑，然后根據適應度的大小進行排序，選擇適應度值較大的個體產生初始信息素，解決蟻群算法缺乏初始信息素的問題；并改進信息素更新方式，每次迭代只使用最優路徑的信息素值，同時對信息素值設置了限定的區間。

（2）改進信息素揮發因子，采用自適應信息素揮發因子來代替人為設定固定值，合理地調整信息素揮發因子的大小，增強蟻群搜索的能力。

（3）針對最優解中存在路徑交叉問題，添加了路徑交叉檢測與消除，對所求得最優解進一步進行優化。

本文通過MATLAB 工具進行仿真，從定點出發遍歷搜索完所有點再回到起始點。實驗結果表明，改進融合的蟻群算法較傳統蟻群算法，最優解距離減少了5.4%；較文獻[7]算法最優解距離減少了2.16%，在尋找最優解和前期搜索效率方面都要優于傳統算法，提高了芯片擺盤的效率，驗證了本算法的有效性。