基于多參數(shù)優(yōu)化ACO的裝備零件回收路徑

孟小玲，溫海駿，祝錫晶，曾艾婧，邵延君

(中北大學(xué) 機(jī)械工程學(xué)院，山西 太原 030051)

0 引 言

現(xiàn)代機(jī)械裝備結(jié)構(gòu)復(fù)雜，技術(shù)含量高，升級(jí)速度快，服役狀態(tài)差異及失效性多樣，隨著信息化時(shí)代的推進(jìn)，裝備零件報(bào)廢數(shù)量猛增，損傷性能各異，如何做到快速、高效地回收機(jī)械裝備零件，合理地規(guī)劃回收路徑，已成為當(dāng)前裝備制造業(yè)亟需解決的問題[1-3]。蟻群算法在解決回收路徑問題上顯示出良好的適應(yīng)性，但其參數(shù)的選擇對(duì)路徑優(yōu)化結(jié)果影響較大，而傳統(tǒng)的參數(shù)選擇具有一定的局限性[4,5]，為了使蟻群算法求得裝備零件車輛回收的最短路徑，必須合理規(guī)劃回收點(diǎn)坐標(biāo)和最優(yōu)參數(shù)組合[6]。

針對(duì)蟻群算法回收路徑中參數(shù)優(yōu)化及算法改進(jìn)等問題，文獻(xiàn)[7]提出了一種基于柵格地圖模型和經(jīng)參數(shù)優(yōu)化的蟻群算法相結(jié)合的路徑規(guī)劃方法；文獻(xiàn)[8]提出了一種連續(xù)改進(jìn)的蟻群算法IACO R；文獻(xiàn)[9]提出了一種改進(jìn)三維蟻群算法以解決再制造服務(wù)信息網(wǎng)絡(luò)模型中基本的ITPO問題。在現(xiàn)有文獻(xiàn)中，很多文章直接設(shè)定關(guān)鍵參數(shù)的值，并沒有用實(shí)驗(yàn)求解的方法得到參數(shù)的精確值及最優(yōu)組合。

本文結(jié)合MATLAB和Design-Expert軟件，采用響應(yīng)曲面法(response surface method，RSM)對(duì)蟻群算法中的關(guān)鍵參數(shù)進(jìn)行優(yōu)化重置。選取信息素因子(A)、期望啟發(fā)因子(B)、最大迭代次數(shù)(C)和信息素?fù)]發(fā)因子(D)這4個(gè)關(guān)鍵參數(shù)，利用Design-Expert軟件設(shè)計(jì)算法參數(shù)實(shí)驗(yàn)方案，將路徑長(zhǎng)度(L)作為響應(yīng)變量進(jìn)行分析，建立回歸預(yù)測(cè)模型，然后采用軟件中Numerical模塊對(duì)4個(gè)參數(shù)進(jìn)行優(yōu)化，尋求使得裝備零件回收車輛路徑最短的參數(shù)組合。

1 問題描述與模型建立

1.1 問題描述

在某區(qū)域內(nèi)，由于性能下降而無法使用的機(jī)械裝備零件堆積在各個(gè)回收點(diǎn)中，回收點(diǎn)提前將可修復(fù)再制造的裝備零件歸置整理，某公司設(shè)置有再制造回收運(yùn)營(yíng)中心，中心定期派出車輛進(jìn)行廢舊裝備的統(tǒng)一回收修復(fù)。

為了更好地描述裝備回收路徑的問題，本文對(duì)實(shí)際問題簡(jiǎn)化后提出假設(shè)：

(1)本文只有1個(gè)回收中心，且該中心為車輛的起始點(diǎn)；

(2)設(shè)立50個(gè)回收點(diǎn)；

(3)派出一輛車對(duì)各個(gè)回收點(diǎn)的廢舊裝備進(jìn)行回收；

(4)每個(gè)回收點(diǎn)車輛只經(jīng)過一次；

(5)假設(shè)各個(gè)回收點(diǎn)的裝備數(shù)量在單位運(yùn)輸車的最大載重、容積范圍內(nèi)。

數(shù)學(xué)模型中的變量定義如下：

I、J：表示回收點(diǎn)總數(shù)，i={0,1,2,…,I},j={0,1,2,…,J}； 其中i=0,j=0表示回收中心，i=1,2,…,I，j=1,2,…,J表示回收點(diǎn)；

qi：每個(gè)回收點(diǎn)已知的裝備重量；

γi：每個(gè)回收點(diǎn)已知的裝備體積；

λj：每個(gè)回收點(diǎn)裝備供應(yīng)量可回收的概率；

Wmax、Wmin：回收車輛的最大、最小載重限制；

Rmax、Rmin：回收車輛的最大、最小容積限制；

dij：表示從回收點(diǎn)i到j(luò)的距離；

ωij：回收車輛從i到j(luò)的運(yùn)輸量；

Lmax：回收車輛所能允許的最大行駛距離。

決策變量定義如下

1.2 模型建立

目標(biāo)函數(shù)

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

式(1)為目標(biāo)函數(shù)，即總回收路徑D最短，式(2)、式(3)表示回收車輛的最大、最小載重限制，式(4)、式(5)表示回收車輛的最大、最小容積限制，式(6)、式(7)表示每個(gè)回收點(diǎn)只有一輛車經(jīng)過，式(8)表示從i到j(luò)的回收量大于j的供給量，式(9)表示回收車輛最大行駛距離約束。

1.3 算法設(shè)計(jì)

1.3.1 蟻群算法原理

(10)

其中，α為信息素因子，表示螞蟻在尋徑中對(duì)積累的信息量指導(dǎo)蟻群繼續(xù)搜索的相對(duì)重要度；β為期望啟發(fā)因子，表示蟻群在尋徑中確定性因素作用的強(qiáng)度；allowedk為螞蟻k下一步訪問的點(diǎn)[11-13]。

螞蟻循環(huán)后更新回收路徑上的信息素濃度，具體公式為

(11)

(12)

其中，ρ為信息素?fù)]發(fā)系數(shù)，取值范圍為：ρ?[0,1)； 1-ρ表示信息素殘留因子；Q為信息素強(qiáng)度；Lk為螞蟻?zhàn)哌^的路徑長(zhǎng)度。

本次仿真建模算法運(yùn)行的固定參數(shù)設(shè)置為：m=34，Q=100， 載重Wmax=5 t,Wmin=0.5 t， 容積Rmax=10 m3,Rmin=1 m3， 最大行駛距離Lmax=570 km。

1.3.2 算法參數(shù)優(yōu)化步驟

為了分析高空不同層大氣環(huán)流的特點(diǎn),選取NCEP/DOE(R2)第二套再分析資料,時(shí)間尺度為1980—2015年,垂直層為10 ～1 000 hPa共17層,分辨率為2.5°×2.5°的全球資料,氣象要素包括:水平風(fēng)速、垂直風(fēng)速、相對(duì)濕度、氣壓、溫度。

為獲取更優(yōu)的路徑長(zhǎng)度，對(duì)蟻群算法參數(shù)進(jìn)行優(yōu)化重置，具體步驟如下：

(1)選取4個(gè)關(guān)鍵因素作為優(yōu)化參數(shù)，一個(gè)結(jié)果作為響應(yīng)指標(biāo)，建立四因素三水平編碼水平表，并根據(jù)響應(yīng)曲面法中心復(fù)合實(shí)驗(yàn)(CCD)設(shè)計(jì)實(shí)驗(yàn)方案；

(2)借助Design-Expert對(duì)4個(gè)參數(shù)進(jìn)行回歸擬合分析，建立路徑長(zhǎng)度回歸模型并進(jìn)行方差分析；

(3)基于回歸預(yù)測(cè)模型，采用響應(yīng)面法直觀分析算法各因素之間交互作用對(duì)路徑響應(yīng)指標(biāo)的影響，得出具有顯著性交互作用的組合并做分析；

(4)采用Design Expert軟件中Numerical模塊對(duì)蟻群算法路徑規(guī)劃關(guān)鍵參數(shù)進(jìn)行優(yōu)化，得到最優(yōu)參數(shù)組合。

1.3.3 算法求解及參數(shù)優(yōu)化流程

在蟻群算法設(shè)置參數(shù)進(jìn)行仿真后，利用第一次得到的數(shù)據(jù)結(jié)果進(jìn)行響應(yīng)面實(shí)驗(yàn)，實(shí)驗(yàn)獲取最優(yōu)參數(shù)組合后再返回程序中進(jìn)行仿真驗(yàn)證，圖1為蟻群算法運(yùn)用MATLAB和Design Expert軟件優(yōu)化參數(shù)求解最短路徑的流程。

圖1 算法流程

2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

2.1 實(shí)驗(yàn)設(shè)計(jì)

本文用響應(yīng)面法對(duì)蟻群算法中的4個(gè)關(guān)鍵參數(shù)進(jìn)行優(yōu)化，進(jìn)而尋求更短的裝備零件回收路徑，實(shí)現(xiàn)高效率的回收作業(yè)[14-16]。對(duì)蟻群算法基本參數(shù)分析發(fā)現(xiàn)，信息素因子的大小反應(yīng)蟻群路徑搜索中隨機(jī)性因素作用的強(qiáng)度，期望啟發(fā)因子表示在尋徑中信息素已知螞蟻選擇路徑時(shí)的向?qū)?，最大迭代次?shù)的設(shè)定直接影響算法運(yùn)行能不能得到最優(yōu)解，信息素?fù)]發(fā)因子表示全局搜索能力及收斂速度，這4個(gè)參數(shù)對(duì)路徑長(zhǎng)度的影響最大。即選取蟻群算法中的信息素因子(A)、期望啟發(fā)因子(B)、最大迭代次數(shù)(C)和信息素?fù)]發(fā)因子(D)作為優(yōu)化變量，路徑長(zhǎng)度(L)作為響應(yīng)變量，建立回歸函數(shù)預(yù)測(cè)模型[17]。選取的4個(gè)單因素參數(shù)編碼水平見表1。

表1 蟻群算法參數(shù)編碼水平

表2 實(shí)驗(yàn)方案與實(shí)驗(yàn)結(jié)果

表2(續(xù))

2.2 實(shí)驗(yàn)結(jié)果分析

2.2.1 方差分析及顯著性檢驗(yàn)

基于實(shí)驗(yàn)結(jié)果，利用軟件對(duì)上表的參數(shù)因子及響應(yīng)數(shù)據(jù)進(jìn)行回歸擬合，得到響應(yīng)值(L)對(duì)各個(gè)因素(A，B，C，D)的目標(biāo)響應(yīng)函數(shù)如下

L=514.93+12.85×A-20.60×B-0.14×C-
41.51×D-0.24×A×B+0.02×A×C+
4.01×A×D-0.003×B×C-0.78×B×D+
0.03×C×D-1.11×A2+1.65×B2+
0.00006×C2+24.4×D2

在建立了回歸模型的基礎(chǔ)上，使用方差分析法對(duì)模型進(jìn)行分析以驗(yàn)證各響應(yīng)值與各因素間的統(tǒng)計(jì)關(guān)系，表3為路徑長(zhǎng)度的分析結(jié)果。

由表3參數(shù)對(duì)蟻群算法路徑長(zhǎng)度的影響模型中可知，單因素A(信息素因子)、B(期望啟發(fā)因子)對(duì)路徑長(zhǎng)度有極為顯著的影響(P<0.0001)，單因素C(最大迭代次數(shù))及雙因素交互作用AB、AC、AD對(duì)路徑長(zhǎng)度的影響較為顯著(P<0.05)。同時(shí)，比較各因素均方差值的大小可得，影響路徑長(zhǎng)度的單因素參數(shù)主次排序?yàn)椋篈>B>C>D，參數(shù)交互作用影響的順序?yàn)椋篈D>AC>AB>BD>CD>BC。

表3 路徑長(zhǎng)度回歸模型方差分析

圖2是路徑長(zhǎng)度(L)模型的殘差正態(tài)概率圖，圖中每個(gè)點(diǎn)都回歸于一條直線，無明顯偏離現(xiàn)象，表明誤差正常分布，該實(shí)驗(yàn)是可行的[18]。

圖2 路徑L的殘差正態(tài)概率

2.2.2 算法參數(shù)的影響分析

基于上述回歸預(yù)測(cè)模型，采用響應(yīng)面法直觀分析算法各因素之間交互作用對(duì)路徑響應(yīng)指標(biāo)的影響[19]，根據(jù)表3預(yù)測(cè)模型，可得AB、AC、AD這3項(xiàng)具有顯著性交互作用，圖3-圖5為各因素交互影響的響應(yīng)面。

圖3 信息素因子與期望啟發(fā)因子交互作用響應(yīng)面

圖4 信息素因子與期望啟發(fā)因子交互作用響應(yīng)面

圖5 信息素因子與期望啟發(fā)因子交互作用響應(yīng)面

圖3為最大迭代次數(shù)(C)與信息素?fù)]發(fā)因子(D)處于零水平時(shí)，信息素因子(A)與期望啟發(fā)因子(B)交互作用響應(yīng)面圖。由圖3可清晰看出，當(dāng)信息素因子為1時(shí)，期望啟發(fā)因子從1增加到9，路徑長(zhǎng)度縮短幅度為50 km左右；當(dāng)期望啟發(fā)因子為1時(shí)，信息素因子從1增加到9，路徑長(zhǎng)度增大幅度為42 km左右，表明期望啟發(fā)因子的影響更大。隨著期望啟發(fā)因子的增加，路徑長(zhǎng)度先減小后趨于平穩(wěn)，當(dāng)期望啟發(fā)因子達(dá)到5時(shí)，算法開始收斂，在區(qū)域[5，8]之間出現(xiàn)最小點(diǎn)，尋找到了最優(yōu)解，說明在這個(gè)區(qū)域期望啟發(fā)因子的改變對(duì)路徑長(zhǎng)度的影響很小。

圖4為期望啟發(fā)因子(B)與信息素?fù)]發(fā)因子(D)處于零水平時(shí)，信息素因子(A)與最大迭代次數(shù)(C)交互作用響應(yīng)面圖。由圖4可得，當(dāng)信息素因子為1時(shí)，最大迭代次數(shù)從50次增加到200次，路徑長(zhǎng)度縮短幅度為17 km 左右；當(dāng)最大迭代次數(shù)為50次時(shí)，信息素因子從1增加到9，路徑長(zhǎng)度增大幅度為30 km左右，可見信息素因子的影響更為顯著。同時(shí)，從圖中可以看出，路徑長(zhǎng)度隨著最大迭代次數(shù)的增大而緩慢減小，說明在迭代次數(shù)為200次以內(nèi)時(shí)越接近最大次數(shù)路徑長(zhǎng)度越短。

圖5為期望啟發(fā)因子(B)與最大迭代次數(shù)(C)處于零水平時(shí)，信息素因子(A)與信息素?fù)]發(fā)因子(D)交互作用響應(yīng)圖。由圖5可得，當(dāng)信息素因子為1時(shí)，信息素?fù)]發(fā)因子從0.1增大到0.9，路徑長(zhǎng)度縮短幅度為10 km左右；當(dāng)信息素?fù)]發(fā)因子為0.1時(shí)，信息素因子從1增加到9，路徑長(zhǎng)度增大幅度為30 km左右，信息素因子的影響程度更大。另外可看出路徑長(zhǎng)度隨著信息素?fù)]發(fā)因子的增大先緩慢減小后平穩(wěn)，在中間區(qū)域出現(xiàn)最小值。

3 參數(shù)優(yōu)化和驗(yàn)證

3.1 蟻群算法參數(shù)優(yōu)化

在Design Expert分析軟件中對(duì)本次案例中的蟻群算法參數(shù)進(jìn)行優(yōu)化，設(shè)置響應(yīng)的目標(biāo)值，在給定范圍內(nèi)設(shè)定路徑長(zhǎng)度的目標(biāo)值為最小，重要度設(shè)置為5。當(dāng)算法性能達(dá)到最好，目標(biāo)值路徑出現(xiàn)最低時(shí)，可得算法參數(shù)的最優(yōu)值為：信息素因子(A)為1.02、期望啟發(fā)因子(B)為6.98、最大迭代次數(shù)(C)為184和信息素?fù)]發(fā)因子(D)為0.56。

3.2 優(yōu)化結(jié)果對(duì)比分析

3.2.1 本文算例分析

將上述最優(yōu)參數(shù)組合帶入本文算例進(jìn)行20次模擬仿真，得到的裝備零件車輛回收最短路徑為424.504 km，最短運(yùn)行時(shí)間為5.78 s，算法穩(wěn)定度為4.18。表4為算法優(yōu)化前后性能的對(duì)比表，從表中可得：運(yùn)用響應(yīng)面法對(duì)蟻群算法關(guān)鍵參數(shù)進(jìn)行優(yōu)化后，廢舊裝備零件的車輛回收最短路徑比優(yōu)化前縮短了5.9%，算法運(yùn)行時(shí)間降低了7.5%，算法穩(wěn)定性提高了22.9%，說明該響應(yīng)面模型的預(yù)測(cè)精度較高。

表4 優(yōu)化前后對(duì)比結(jié)果

圖6與圖7分別為優(yōu)化前后的算法路徑最優(yōu)圖與迭代收斂效果圖。從路徑圖中可以看出，參數(shù)優(yōu)化后的算法大幅提高了有效螞蟻尋徑數(shù)量，在迭代過程中更易得到最優(yōu)路徑；從迭代圖中可得算法優(yōu)化前和優(yōu)化后分別在接近100次和20次時(shí)達(dá)到最優(yōu)，且優(yōu)化后平均距離更穩(wěn)定，說明參數(shù)優(yōu)化后的算法收斂速度更快，迭代效果更優(yōu)。

圖6 優(yōu)化前路徑最優(yōu)圖與迭代收斂效果

圖7 優(yōu)化后路徑最優(yōu)圖與迭代收斂效果

3.2.2 其它算例對(duì)比分析

為了進(jìn)一步驗(yàn)證此次蟻群算法參數(shù)優(yōu)化的有效性及可靠性，本文在基本參數(shù)設(shè)置相同的情況下，利用分析得到的最優(yōu)參數(shù)組合，選取與本文案例規(guī)模類似的國(guó)際通用TSPLIB標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中的oliver30、eil76與st70案例連續(xù)仿真20次進(jìn)行對(duì)比分析。表5為路徑長(zhǎng)度對(duì)比結(jié)果，表中已知最優(yōu)解為TSPLIB數(shù)據(jù)庫(kù)中所提供的[20]；表6為算例運(yùn)行時(shí)間對(duì)比表；表7為穩(wěn)定性對(duì)比結(jié)果。

表5 路徑長(zhǎng)度對(duì)比結(jié)果

表6 運(yùn)行時(shí)間對(duì)比結(jié)果

表7 穩(wěn)定性對(duì)比結(jié)果

分析表中對(duì)比結(jié)果可得，算例oliver30中，優(yōu)化參數(shù)后的實(shí)驗(yàn)路徑最優(yōu)解和平均解分別比優(yōu)化前縮短3.6%和2.8%，運(yùn)行時(shí)間降低5.4%，算法穩(wěn)定度提高24.3%；算例eil76中，優(yōu)化參數(shù)后的實(shí)驗(yàn)路徑最優(yōu)解和平均解分別比優(yōu)化前縮短3.1%和2.7%，運(yùn)行時(shí)間降低4.0%，算法穩(wěn)定度提高9.5%；算例st70中，優(yōu)化參數(shù)后的路徑最優(yōu)解和平均解分別比優(yōu)化前縮短2.7%和3.2%，運(yùn)行時(shí)間降低8.9%，算法穩(wěn)定度提高14.6%。說明參數(shù)優(yōu)化后的蟻群算法不僅在本次裝備零件的回收路徑上有適用性，在其它類似規(guī)模地圖中也表現(xiàn)出了很好的優(yōu)越性，進(jìn)一步表明此次的參數(shù)優(yōu)化具有更好的尋優(yōu)能力，穩(wěn)定性和可靠性更強(qiáng)。

4 結(jié)束語

本文針對(duì)廢舊裝備零件的回收路徑，基于響應(yīng)面法對(duì)蟻群算法中的信息素因子(A)、期望啟發(fā)因子(B)、最大迭代次數(shù)(C)和信息素?fù)]發(fā)因子(D)這4個(gè)參數(shù)進(jìn)行優(yōu)化研究。運(yùn)用Design-Expert軟件，選取路徑長(zhǎng)度(L)作為響應(yīng)變量并建立影響因素回歸預(yù)測(cè)模型，通過方差分析得到單個(gè)因素及其交互作用對(duì)響應(yīng)指標(biāo)的影響，并對(duì)算法參數(shù)進(jìn)行了優(yōu)化。

(1)由方差分析及響應(yīng)面圖得出蟻群算法參數(shù)對(duì)路徑長(zhǎng)度的影響顯著性由大到小依次是信息素因子(A)、期望啟發(fā)因子(B)、最大迭代次數(shù)(C)、信息素?fù)]發(fā)因子(D)；且優(yōu)化變量AB、AC、AD的交互作用影響比較顯著。

(2)基于響應(yīng)面法分析得到蟻群算法在求解回收路徑問題上的最優(yōu)參數(shù)組合為：信息素因子=1.02，期望啟發(fā)因子=6.98，最大迭代次數(shù)=184，信息素?fù)]發(fā)因子=0.56，此時(shí)MATLAB程序運(yùn)行得到的最短路徑L=424.504 km。用最優(yōu)參數(shù)組合對(duì)TSPLIB數(shù)據(jù)庫(kù)中的oliver30、eil76與st70案例仿真分析，進(jìn)一步驗(yàn)證了本次參數(shù)優(yōu)化的可行性。

(3)本文運(yùn)用響應(yīng)面法對(duì)蟻群算法求解廢舊裝備回收路徑的最優(yōu)參數(shù)組合進(jìn)行規(guī)劃分析；對(duì)于處理大規(guī)模地圖時(shí)，本文算法參數(shù)優(yōu)化有尋優(yōu)能力差、迭代不穩(wěn)定等問題，在今后的研究中可以進(jìn)一步改善。