BAS-LSA混合算法在裝配序列規(guī)劃的應(yīng)用*

任 云，劉 丹

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

0 引言

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

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

1 BAS和LSA的基本原理

1.1 LSA算法的基本原理

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

(2)

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

(3)

(4)

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

(5)

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

rl=e+g-rl

(6)

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

1.2 BAS算法的基本原理

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

BAS算法的基本原理為：天牛個(gè)體在尋找食物的過(guò)程中通過(guò)左右觸須來(lái)感受食物的強(qiáng)度，因?yàn)閮身毜奈恢貌灰粯?，所以?xún)身毸綔y(cè)的強(qiáng)度也不一樣，天牛最終朝強(qiáng)度更大的觸須所指的方向前進(jìn)一步，不斷重復(fù)上述流程，直到找到食物的具體位置。其中食物氣味相當(dāng)于尋優(yōu)函數(shù)，食物的具體位置相當(dāng)于尋優(yōu)函數(shù)的最優(yōu)解。根據(jù)天牛的覓食過(guò)程抽象出的BAS算法遵循如下原則[15]：①天牛在物理世界尋找食物的過(guò)程可以到虛擬天牛在任意維空間求解函數(shù)最優(yōu)值的情形；②天牛左右兩觸須對(duì)稱(chēng)；③天牛每次向前移動(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為符號(hào)函數(shù)；δ為搜索步長(zhǎng)，其大小是一個(gè)隨時(shí)間t逐漸衰減的函數(shù)值。t時(shí)刻的m與δ可表示為：

dt=etad*dt-1+0.01

(10)

δt=etaδ*δt-1

(11)

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

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

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

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

2.1 幾何可行性

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

(12)

(13)

(14)

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

2.2 連貫性

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

(15)

2.3 一致性

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

(16)

2.4 穩(wěn)定性

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

(17)

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

適應(yīng)度函數(shù)通過(guò)從幾何可行性、連貫性、一致性、穩(wěn)定性4個(gè)方面來(lái)評(píng)價(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為無(wú)支撐作用的次數(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求解的種群中不滿(mǎn)足幾何可行性的個(gè)體作為一個(gè)天牛須粒子以天牛須算法進(jìn)行優(yōu)化，提高LSA跳出局部最優(yōu)的能力和搜索精度。

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

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

步驟3：開(kāi)始循環(huán)，更新梯級(jí)先導(dǎo)尖端能量El，找到最差、最優(yōu)梯級(jí)先導(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è)體的幾何可行性，對(duì)于不滿(mǎn)足幾何可行性的個(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ī)引擎為例來(lái)進(jìn)行算法驗(yàn)證。該裝配體共包含18個(gè)零件。算法在MATLAB平臺(tái)上編寫(xiě)，選擇的最大迭代次數(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來(lái)描述各算法逃逸出局部最優(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對(duì)4種算法求出的裝配序列幾個(gè)關(guān)鍵評(píng)價(jià)指標(biāo)：干涉次數(shù)、無(wú)支持作用次數(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ù)值對(duì)比

表3對(duì)4種算法的性能進(jìn)行了對(duì)比。如表所示，混合算法的最優(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)對(duì)比可看出，在找到最優(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)，綜上所述表明混合算法在求解過(guò)程中，在全局搜索能力、搜索精度及跳出局部最優(yōu)方面有明顯優(yōu)勢(shì)。

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

圖3 算法收斂曲線

5 結(jié)論

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