基于多參數優化ACO的裝備零件回收路徑

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

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

0 引 言

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

針對蟻群算法回收路徑中參數優化及算法改進等問題，文獻[7]提出了一種基于柵格地圖模型和經參數優化的蟻群算法相結合的路徑規劃方法；文獻[8]提出了一種連續改進的蟻群算法IACO R；文獻[9]提出了一種改進三維蟻群算法以解決再制造服務信息網絡模型中基本的ITPO問題。在現有文獻中，很多文章直接設定關鍵參數的值，并沒有用實驗求解的方法得到參數的精確值及最優組合。

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

1 問題描述與模型建立

1.1 問題描述

在某區域內，由于性能下降而無法使用的機械裝備零件堆積在各個回收點中，回收點提前將可修復再制造的裝備零件歸置整理，某公司設置有再制造回收運營中心，中心定期派出車輛進行廢舊裝備的統一回收修復。

為了更好地描述裝備回收路徑的問題，本文對實際問題簡化后提出假設：

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

(2)設立50個回收點；

(3)派出一輛車對各個回收點的廢舊裝備進行回收；

(4)每個回收點車輛只經過一次；

(5)假設各個回收點的裝備數量在單位運輸車的最大載重、容積范圍內。

數學模型中的變量定義如下：

I、J：表示回收點總數，i={0,1,2,…,I},j={0,1,2,…,J}； 其中i=0,j=0表示回收中心，i=1,2,…,I，j=1,2,…,J表示回收點；

qi：每個回收點已知的裝備重量；

γi：每個回收點已知的裝備體積；

λj：每個回收點裝備供應量可回收的概率；

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

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

dij：表示從回收點i到j的距離；

ωij：回收車輛從i到j的運輸量；

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

決策變量定義如下

1.2 模型建立

目標函數

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

1.3 算法設計

1.3.1 蟻群算法原理

(10)

其中，α為信息素因子，表示螞蟻在尋徑中對積累的信息量指導蟻群繼續搜索的相對重要度；β為期望啟發因子，表示蟻群在尋徑中確定性因素作用的強度；allowedk為螞蟻k下一步訪問的點[11-13]。

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

(11)

(12)

其中，ρ為信息素揮發系數，取值范圍為：ρ?[0,1)； 1-ρ表示信息素殘留因子；Q為信息素強度；Lk為螞蟻走過的路徑長度。

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

1.3.2 算法參數優化步驟

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

為獲取更優的路徑長度，對蟻群算法參數進行優化重置，具體步驟如下：

(1)選取4個關鍵因素作為優化參數，一個結果作為響應指標，建立四因素三水平編碼水平表，并根據響應曲面法中心復合實驗(CCD)設計實驗方案；

(2)借助Design-Expert對4個參數進行回歸擬合分析，建立路徑長度回歸模型并進行方差分析；

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

(4)采用Design Expert軟件中Numerical模塊對蟻群算法路徑規劃關鍵參數進行優化，得到最優參數組合。

1.3.3 算法求解及參數優化流程

在蟻群算法設置參數進行仿真后，利用第一次得到的數據結果進行響應面實驗，實驗獲取最優參數組合后再返回程序中進行仿真驗證，圖1為蟻群算法運用MATLAB和Design Expert軟件優化參數求解最短路徑的流程。

圖1 算法流程

2 實驗設計與結果分析

2.1 實驗設計

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

表1 蟻群算法參數編碼水平

表2 實驗方案與實驗結果

表2(續)

2.2 實驗結果分析

2.2.1 方差分析及顯著性檢驗

基于實驗結果，利用軟件對上表的參數因子及響應數據進行回歸擬合，得到響應值(L)對各個因素(A，B，C，D)的目標響應函數如下

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

在建立了回歸模型的基礎上，使用方差分析法對模型進行分析以驗證各響應值與各因素間的統計關系，表3為路徑長度的分析結果。

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

表3 路徑長度回歸模型方差分析

圖2是路徑長度(L)模型的殘差正態概率圖，圖中每個點都回歸于一條直線，無明顯偏離現象，表明誤差正常分布，該實驗是可行的[18]。

圖2 路徑L的殘差正態概率

2.2.2 算法參數的影響分析

基于上述回歸預測模型，采用響應面法直觀分析算法各因素之間交互作用對路徑響應指標的影響[19]，根據表3預測模型，可得AB、AC、AD這3項具有顯著性交互作用，圖3-圖5為各因素交互影響的響應面。

圖3 信息素因子與期望啟發因子交互作用響應面

圖4 信息素因子與期望啟發因子交互作用響應面

圖5 信息素因子與期望啟發因子交互作用響應面

圖3為最大迭代次數(C)與信息素揮發因子(D)處于零水平時，信息素因子(A)與期望啟發因子(B)交互作用響應面圖。由圖3可清晰看出，當信息素因子為1時，期望啟發因子從1增加到9，路徑長度縮短幅度為50 km左右；當期望啟發因子為1時，信息素因子從1增加到9，路徑長度增大幅度為42 km左右，表明期望啟發因子的影響更大。隨著期望啟發因子的增加，路徑長度先減小后趨于平穩，當期望啟發因子達到5時，算法開始收斂，在區域[5，8]之間出現最小點，尋找到了最優解，說明在這個區域期望啟發因子的改變對路徑長度的影響很小。

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

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

3 參數優化和驗證

3.1 蟻群算法參數優化

在Design Expert分析軟件中對本次案例中的蟻群算法參數進行優化，設置響應的目標值，在給定范圍內設定路徑長度的目標值為最小，重要度設置為5。當算法性能達到最好，目標值路徑出現最低時，可得算法參數的最優值為：信息素因子(A)為1.02、期望啟發因子(B)為6.98、最大迭代次數(C)為184和信息素揮發因子(D)為0.56。

3.2 優化結果對比分析

3.2.1 本文算例分析

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

表4 優化前后對比結果

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

圖6 優化前路徑最優圖與迭代收斂效果

圖7 優化后路徑最優圖與迭代收斂效果

3.2.2 其它算例對比分析

為了進一步驗證此次蟻群算法參數優化的有效性及可靠性，本文在基本參數設置相同的情況下，利用分析得到的最優參數組合，選取與本文案例規模類似的國際通用TSPLIB標準數據庫中的oliver30、eil76與st70案例連續仿真20次進行對比分析。表5為路徑長度對比結果，表中已知最優解為TSPLIB數據庫中所提供的[20]；表6為算例運行時間對比表；表7為穩定性對比結果。

表5 路徑長度對比結果

表6 運行時間對比結果

表7 穩定性對比結果

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

4 結束語

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

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

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

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