任 云，劉 丹

(貴州大學(xué)現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴陽 550025)

0 引言

裝配是生產(chǎn)制造的重要環(huán)節(jié)，直接關(guān)系到產(chǎn)品質(zhì)量、性能、壽命和可維護(hù)性，裝配序列規(guī)劃是裝配工藝規(guī)劃的重要部分，序列的優(yōu)劣直接影響裝配質(zhì)量[1]。裝配序列規(guī)劃研究可以優(yōu)化裝配順序，使企業(yè)獲得生產(chǎn)成本更低、裝配效率更高、質(zhì)量更佳的裝配方案。裝配序列規(guī)劃是一個(gè)典型的非確定性多項(xiàng)式(Non deterministic polynomial,NP)組合優(yōu)化問題[2]，產(chǎn)品的裝配序列數(shù)量與產(chǎn)品的零部件數(shù)量呈指數(shù)增長關(guān)系，越復(fù)雜的產(chǎn)品越容易遇到裝配序列組合爆炸問題[3]，這給裝配規(guī)劃問題帶來了很大的挑戰(zhàn)。

為了更好解決這一問題，研究者將各類智能優(yōu)化算法如遺傳算法[4]、蟻群算法[5]、模擬退火算法[6]、神經(jīng)網(wǎng)絡(luò)算法[7]等應(yīng)用到裝配序列規(guī)劃中，這些算法在一定程度上克服以往方法中存在的組合爆炸問題及裝配的局限問題。遺傳算法是目前在裝配序列規(guī)劃中應(yīng)用最為廣泛的算法，但遺傳算法要求初始種群為可行序列，且全局收斂速度慢和存在大量重疊迭代的問題；蟻群算法在裝配序列規(guī)劃問題中也有廣泛的應(yīng)用，但它運(yùn)算效率較低，且開始階段信息素積累較慢，容易陷入局部最優(yōu)[8]，針對上述問題，論文根據(jù)裝配序列規(guī)劃問題的特點(diǎn)，提出將閃電搜索算法和天牛須算法運(yùn)用于裝配序列規(guī)劃之中。

閃電搜索算法(Lightning Search Algorithm,LSA)是Shareef H等受自然天氣中閃電現(xiàn)象的啟發(fā)提出的一種優(yōu)化算法[9]，Dorigo M等將其應(yīng)用于函數(shù)優(yōu)化和TSP(Traveling Salesman Problem)問題[10]，并取得了良好的優(yōu)化效果, Islam M M等提出了一種基于二進(jìn)制編碼的閃電搜索算法[11]，證明了該算法在搜索精度和收斂性方面性能表現(xiàn)良好。

由于LSA算法模擬閃電的快速傳播特性，因此收斂速度較快。但LSA算法本身存在求解精度不高、易陷于局部最優(yōu)等缺點(diǎn)。

天牛須搜索算法(Bettle Antennate Search Algorithm,BAS)在2017年由Jiang X等根據(jù)天牛個(gè)體用左右觸須感受食物氣味的方向逐漸接近食物這一特點(diǎn)提出的[12]。研究表明BAS算法在搜索速率與搜索精度上均可達(dá)到理想的結(jié)果。BAS算法局部搜索能力很強(qiáng)，但全局搜索能力不足。因此，本文結(jié)合天牛須搜索算法和閃電搜索算法的優(yōu)點(diǎn)，提出將天牛須搜索算法和閃電搜索算法混合的裝配序列規(guī)劃優(yōu)化方法,以此來解決閃電搜索算法容易陷入局部最優(yōu)的問題，提高跳出局部最優(yōu)的能力和搜索精度。

1 BAS和LSA的基本原理

1.1 LSA算法的基本原理

閃電搜索算法(LSA)是對閃電這種自然現(xiàn)象的觀察而得到的新新算法，當(dāng)閃電形成時(shí)，空氣中的“放電粒子”與空氣碰撞之后會產(chǎn)生一條電離路徑或通道，并形成一條梯級先導(dǎo)。LSA算法利用空間放電體、和引導(dǎo)放電體等概念建立分布函數(shù)模型來求解待解決的問題[13]，空間放電體試圖成為最優(yōu)梯級先導(dǎo)，引導(dǎo)放電體代表種群中的最優(yōu)個(gè)體[14]。

(1)在一個(gè)種群規(guī)模為N，初始種群的生成服從均勻分布，創(chuàng)建初始隨機(jī)種群，其概率密度函數(shù)f(xc)可以表示為：

(1)

式中，xc是一個(gè)候選解，a和b分別是“放電粒子”范圍的最小值和最大值。

(2)引導(dǎo)放電體表示為HL，由正態(tài)概率密度函數(shù)f(xk)來生成位置：

(2)

式中，μ為形狀參數(shù)，引導(dǎo)放電體HL在下一次迭代的位置為：

(3)

(4)

形狀參數(shù)μ會影響CS和HL之間的距離，CS在下一次迭代的位置為：

(5)

(4)分叉是放電體的另一特性，在LSA算法中分叉有兩種方式，首先分叉會形成兩個(gè)互相對稱的通道：

rl=e+g-rl

(6)

其中，e和g表示邊界，rl和rl分別表示原來的通道和分叉產(chǎn)生的對稱通道。為了保證種群大小不變，兩通道只保留一個(gè)。

1.2 BAS算法的基本原理

天牛須搜索算法(BAS)是一種新的啟發(fā)式算法，它的特點(diǎn)是僅有一個(gè)天牛個(gè)體，所以運(yùn)算速度很快，計(jì)算量低。

BAS算法的基本原理為：天牛個(gè)體在尋找食物的過程中通過左右觸須來感受食物的強(qiáng)度，因?yàn)閮身毜奈恢貌灰粯樱詢身毸綔y的強(qiáng)度也不一樣，天牛最終朝強(qiáng)度更大的觸須所指的方向前進(jìn)一步，不斷重復(fù)上述流程，直到找到食物的具體位置。其中食物氣味相當(dāng)于尋優(yōu)函數(shù)，食物的具體位置相當(dāng)于尋優(yōu)函數(shù)的最優(yōu)解。根據(jù)天牛的覓食過程抽象出的BAS算法遵循如下原則[15]：①天牛在物理世界尋找食物的過程可以到虛擬天牛在任意維空間求解函數(shù)最優(yōu)值的情形；②天牛左右兩觸須對稱；③天牛每次向前移動(dòng)的距離與兩須之間的距離成比例；④天牛每次前進(jìn)后身體的方向不確定[16]。

根據(jù)以上原則，BAS 算法的數(shù)學(xué)表達(dá)如下：

(1)假設(shè)隨機(jī)產(chǎn)生的天牛方向?yàn)閐，質(zhì)心位置為x，右邊觸須位置為xr，左須為xl，兩須之間的距離為m，mt表示天牛在t時(shí)刻的兩須之間的距離，根據(jù)天牛的方向可以計(jì)算出左須和右須的位置：

xr=xt+dtb

(7)

xl=xt-dtb

(8)

(2)計(jì)算適應(yīng)度值f(xl)和f(xr)的大小，比較兩者的大小，再?zèng)Q定天牛下一步的走向：

xt=xt-1+δtbsign(f(xr)-f(xl))

(9)

其中，xt為t時(shí)天牛的位置，sign為符號函數(shù)；δ為搜索步長，其大小是一個(gè)隨時(shí)間t逐漸衰減的函數(shù)值。t時(shí)刻的m與δ可表示為：

dt=etad*dt-1+0.01

(10)

δt=etaδ*δt-1

(11)

其中，eta_m和eta_δ分別為兩須之間的距離和步長的遞減系數(shù)，通常小于1。

(3)判斷求解結(jié)果是否達(dá)到理想的精度或迭代次數(shù)超過最大迭代次數(shù)，滿足一個(gè)條件就完成迭代，否則重復(fù)式(7)～式(10)的步驟。

2 裝配關(guān)系模型的構(gòu)建

由于機(jī)械產(chǎn)品的裝配具有多種裝配方案，零件裝配序列有多種選擇，這增加了產(chǎn)品的復(fù)雜性，影響裝配時(shí)間、裝配成本以及裝配質(zhì)量的因素有很多種，其中零件的幾何可行性、裝配方向、裝配工具的改變次數(shù)、零件之間的穩(wěn)定性是主要影響因素，所以本文將以上4個(gè)因素作為評價(jià)指標(biāo)。

2.1 幾何可行性

在裝配體上裝配零件Pi時(shí)，須考慮當(dāng)前零件的裝配可行性，即Pi從無窮遠(yuǎn)處沿方向v裝配時(shí)，前i-1個(gè)零件對Pi是否干涉。須首先構(gòu)建6個(gè)方向的干涉矩陣[17]，如式子(12)所示，其中Pij表示零件j在裝配時(shí)零件i對零件j的干涉，有干涉Pij=1，無干涉Pij=0。并根據(jù)式(13)、式(14)判斷零件的裝配可行性。

(12)

(13)

(14)

式中，n為裝配序列零件的個(gè)數(shù)，u為±X，±Y，±Z的一個(gè)方向，Ci=0表示零件pi裝配時(shí)會發(fā)生干涉，Ci=1中表示在某一方向上裝配是可行的。

2.2 連貫性

連貫性是指零件裝配過程中，相鄰零件Pi與Pi-1裝配方向是否相同。對于比較復(fù)雜的裝配體，裝配方向的改變會增加裝配難度，加大了對裝配工具的要求，同時(shí)還會明顯增加裝配時(shí)間和成本。由式(15)判斷零件pi與pi-1的裝配方向是否相同。

(15)

2.3 一致性

一致性是指裝配相鄰兩個(gè)零件時(shí)使用相同的裝配工具，如裝配零件的前后裝配工具不相同，中途還需更換裝配工具，這也增加了裝配的步驟，應(yīng)盡量減少裝配過程工具的裝換次數(shù)，由式(16)判斷裝配工具的裝配次數(shù)。

(16)

2.4 穩(wěn)定性

穩(wěn)定性是指裝配零件pi時(shí)，前一個(gè)零件pi-1對pi是否有支撐作用，如沒有支撐作用，則還需額外的支撐工具支撐pi的裝配，這就給裝配過程帶來額外的工作量，因此零件裝配過程需要考慮零件pi-1對pi的支撐作用，提高裝配效率，由式(17)評價(jià)裝配序列的穩(wěn)定性。

(17)

2.5 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)通過從幾何可行性、連貫性、一致性、穩(wěn)定性4個(gè)方面來評價(jià)序列。適應(yīng)度函數(shù)如式(18)所示：

F(n)=w1*ng+w2*nd+w3*nt+w4*ns

(18)

其中，n為種群中第n個(gè)序列，ng為一條序列干涉次數(shù)之和，nd為裝配方向的改變次數(shù)，nt為裝配工具的改變次數(shù)，ns為無支撐作用的次數(shù)；w1、w2、w3、w4為權(quán)重系數(shù)；其中一條可行裝配序列的干涉次數(shù)應(yīng)該為0，即ng=0，F(xiàn)越小表明這條序列越優(yōu)。

3 LAS-BAS混合算法改進(jìn)及步驟

LSA算法有求解精度低、容易陷入局部最優(yōu)的缺點(diǎn)。BAS算法在全局的搜索能力較弱，且個(gè)體具有單一性，但局部搜索能力很強(qiáng)的特點(diǎn)，考慮將每一代經(jīng)LSA求解的種群中不滿足幾何可行性的個(gè)體作為一個(gè)天牛須粒子以天牛須算法進(jìn)行優(yōu)化，提高LSA跳出局部最優(yōu)的能力和搜索精度。

步驟1：設(shè)置算法的初始參數(shù)：最大迭代次數(shù)Nmax、種群規(guī)模N、梯級先導(dǎo)尖端能量El和最大通道時(shí)間T。

步驟2：生成隨機(jī)初始種群，計(jì)算放電體能量Ep和目標(biāo)函數(shù)值大小。

步驟3：開始循環(huán)，更新梯級先導(dǎo)尖端能量El，找到最差、最優(yōu)梯級先導(dǎo)。

步驟4：通道時(shí)間每次加一，如達(dá)到最大通道時(shí)間T，則淘汰適應(yīng)度值最差的通道并重置通道時(shí)間。

步驟5：更新放電體方向和能量Ep，并計(jì)算引導(dǎo)放電體和空間放電體適應(yīng)度值。

步驟6：計(jì)算放電體能量Ep，如果Ep>El，那么進(jìn)入步驟6.1，否則進(jìn)入步驟6.2；

步驟6.2：放電體的位置保持不變。

步驟7:計(jì)算種群中個(gè)體的幾何可行性，對于不滿足幾何可行性的個(gè)體，用天牛須搜索算法進(jìn)行優(yōu)化，并計(jì)算經(jīng)優(yōu)化后的個(gè)體適應(yīng)度值，如果更優(yōu)則替代當(dāng)前個(gè)體，否則個(gè)體不變。

步驟8：如果迭代次數(shù)達(dá)到最大迭代次數(shù)，即結(jié)束迭代，進(jìn)入步驟9，否則轉(zhuǎn)到步驟3，繼續(xù)增加迭代次數(shù)和通道時(shí)間，繼續(xù)迭代；

步驟9：得到最優(yōu)先導(dǎo)，輸出最優(yōu)解x。

根據(jù)上述步驟，LSA的基本流程如圖1所示。

圖1 LSA-BAS算法流程圖

4 實(shí)例驗(yàn)證及分析

如圖2所示，本文以蒸汽發(fā)動(dòng)機(jī)引擎為例來進(jìn)行算法驗(yàn)證。該裝配體共包含18個(gè)零件。算法在MATLAB平臺上編寫，選擇的最大迭代次數(shù)Nmax為200，種群規(guī)模N為20。為了考察閃電搜索算法—天牛須搜索算法(LSA-BAS)的優(yōu)化性能，將其與差分進(jìn)化算法(DE)、粒子群算法(PSO)、閃電搜索算法(LSA)相比較，比較參數(shù)為最優(yōu)適應(yīng)度值、最優(yōu)值迭代次數(shù)、跳出局部最優(yōu)的能力等方面。

本文定義一個(gè)參數(shù)Q來描述各算法逃逸出局部最優(yōu)的能力，Q的數(shù)值越小表明算法的逃脫局部最優(yōu)的能力越強(qiáng)，其中L為最大迭代次數(shù)，ΔL表示找到最優(yōu)適應(yīng)度值前的所有局部最優(yōu)區(qū)間，max(ΔL)表示其中所有局部區(qū)間的最大區(qū)間值，如式(19)所示：

(19)

圖2 蒸汽發(fā)動(dòng)機(jī)引擎裝配爆炸圖

表1為4種算法求出的最優(yōu)序列，表2對4種算法求出的裝配序列幾個(gè)關(guān)鍵評價(jià)指標(biāo)：干涉次數(shù)、無支持作用次數(shù)、裝配方向改變次數(shù)、裝配工具的改變次數(shù)進(jìn)行比較。如表2所示，各算法干涉次數(shù)皆為0，這表明所有序列都是可行裝配序列，其中LSA-BAS混合算法的支撐方向、裝配方向、裝配工具的次數(shù)改變之和為30，是4種算法中最小的，其中差分進(jìn)化算法(DE)為35，粒子群算法(PSO)為32，閃電搜索算法(LSA)為32；LSA-BAS支撐方向的改變次數(shù)為9，是4個(gè)算法中最小的，工具的改變次數(shù)為11，同樣也是最小的。

表1 算法最優(yōu)序列表

表2 裝配序列及相關(guān)數(shù)值對比

表3對4種算法的性能進(jìn)行了對比。如表所示，混合算法的最優(yōu)適應(yīng)度值為3.35，比其它3種算法的適應(yīng)度值都小，找到最優(yōu)值的迭代次數(shù)為109，也比其它3種算法的迭代次數(shù)小，這表明混合算法的收斂速度及搜索精度強(qiáng)于其它3種算法。

表4中L為最大迭代次數(shù)，圖3為算法收斂曲線，從中可以得到局部最優(yōu)最大區(qū)間。從表4算法局部最優(yōu)對比可看出，在找到最優(yōu)值迭代次數(shù)之前，混合算法陷入局部最優(yōu)的最大代數(shù)為38代，Q值為0.19，遠(yuǎn)小于其它3個(gè)算法的Q值，這表明LSA-BAS混合算法逃逸處局部最優(yōu)的能力遠(yuǎn)大于其它3種算法，并且最終除LSA-BAS混合算法外其它算法未能跳出局部最優(yōu)，綜上所述表明混合算法在求解過程中，在全局搜索能力、搜索精度及跳出局部最優(yōu)方面有明顯優(yōu)勢。

表3 算法結(jié)果對比表

圖3 算法收斂曲線

5 結(jié)論

LSA算法是一種新的元啟發(fā)式算法，LSA算法在求解過程中存在收斂速度較慢、容易陷于局部最優(yōu)的缺點(diǎn)，針對LSA算法的不足，本文首次提出了把BAS算法中天牛個(gè)體的覓食過程融入閃電搜索算法的混合算法，該算法利用BAS算法局部搜索能力較強(qiáng)的特點(diǎn)，使天牛須的感知與閃電粒子的傳播過程相結(jié)合，有效的解決了閃電搜索算法易陷入局部最優(yōu)的問題，加快了算法的收斂速度，提高了算法的搜索精度和全局搜索能力。通過實(shí)例驗(yàn)證和算法對比，該算法在解決裝配序列規(guī)劃問題方面具有良好的收斂性能和跳出局部最優(yōu)的能力。