差分進化算法在煤礦井下移動設備路徑規劃的應用研究

韓國國，范柄堯

（1.山西天地王坡煤業有限公司，山西 晉城 043300；2.中國煤炭科工集團太原研究院，陜西 太原 030006）

1 前言

近年來，各大煤礦對井下安全生產的要求越來越高，設備自動化、智能化替代人力已成為重要的解決辦法。井下移動設備移動頻繁，一直以來都是安全生產的隱患，為保證移動設備的安全運行，確保人員及設備的安全，需要對可移動設備的運動規劃問題進行探討和研究。

移動設備包括綜采設備，連采設備和輔助運輸車輛和井下移動機器人，其中各大學者針對輔助運輸車輛和自主移動機器人在煤礦井下這一復雜環境下的運動規劃問題研究的較多，文獻[4]采用人工魚群算法對井下救援機器人進行路徑規劃，通過將環境模型中威脅區域距離檢測的與算法相結合，實現了在較短的時間內得到目前環境下的最優路徑。但是路徑點數量的選擇對算法效果的影響較大；文獻[5]通過改進人工勢場法對礦井中障礙物密集且移動較多的導航裝置進行路徑避障處理；文獻[6]通過局部到全局的梯度-坐標輪換法進行煤礦搜救機器人最優路徑規劃。另外，還有采用各類傳感器、視頻輔助等方法進行輔助運輸和避障處理，均取得了不錯的效果。本文主要采用差分進化算法針對輔助運輸車輛在煤礦井下這一復雜環境下的運動規劃問題進行探索。

差分進化(Differential Evolution，DE)算法是由Storn和Price提出的一種基于種群的智能優化算法，該算法能夠用來解決連續領域的優化問題。優點是在全局、并行搜索過程中具有魯棒性強，操作原理簡單以及尋優性能良好等，現在已經成為進化領域的研究熱點。

鑒于差分進化算法在連續域的突出表現，本文將其用于解決煤礦井下可移動設備的無碰撞最短路徑規劃問題。

2 煤礦井下移動設備路徑規劃問題模型

針對煤礦井下可移動設備路徑規劃問題，設計使可移動設備從起始點到目標點的路徑模型。本文將可移動設備縮小為一個質點，將各個障礙物設置成不同半徑的圓，煤礦井下可移動設備運行的最短無碰撞路徑模型如下：

式中，f表示可移動設備運行的最短無碰撞路徑；設起始位置坐標為目標坐標為x2，…xn為將x0和xn+1關于x軸n+1等分后的n個點，b為x0和xn+1的n+1等分值。y1，y2，…yn為x1，x2，…

xn所對應的路徑點；考慮到相鄰兩路徑點連線可能與障礙物相交而形成不可行路徑，使用懲罰函數ωi處理這種情況。ε＞1為懲罰因子，可以使不可行路徑變長；表示障礙物k的圓心到相鄰兩路徑點yi yi-1所在直線的垂直距離；表示第k個障礙物的影響范圍，Rk為第k個障礙物的半徑，為一個較小的數；Sk表示線段yi yi-1是否與第k個障礙物相交，相交Sk=0，否則Sk=1。

3 基于差分進化算法的路徑規劃

3.1 種群初始化

差分進化算法的初始化種群設置如下為：

式中，NP為種群規模，D為維數。

3.2 變異操作

DE算法有很多變異策略，本文采用的變異方式為DE/rand/1，此變異操作具體是指在每一代種群中選擇三個互異的個體yr1,g、yr2,g和yr3,g，把其中兩個個體yr2,g和yr3,g進行差分處理并經過縮放因子F( 1 0＜F＜ )縮放后，與第三個個體yr1,g相加得到變異向量vi,g，如式(6)所示。

3.3 交叉操作

本文采用二項式交叉方式進行操作，試驗向量中至少有一個分量由變異向量產生。具體操作如式（7）所示：

式中，j=1,2,…,D, CR∈(0,1)為交叉率，jrand為[1,D]內隨機選擇的整數。

3.4 選擇操作

為產生下一代的目標向量yi,g+1，根據目標向量yi,g和試驗向量ui,g的適應值f()?來選擇最優個體，具體步驟如式(8)所示：

4 實驗仿真

4.1 環境參數設置

針對煤礦井下可移動設備無碰撞最短路徑規劃問題，本文將差分進化算法(DE/rand/1/bin)進行仿真實驗，為了保證試驗的公平性，針對算法的參數進行如下設置：

移動設備的環境條件設置如下：將移動設備在以下兩個環境中進行仿真試驗，其中環境1中有兩個障礙物，障礙物的情況如下：半徑都為1，坐標原點分別為(-15，-10)、（15，10）的圓；環境2中有三個障礙物，障礙物的情況如下：半徑為1，坐標原點分別為（20，5)、(-20，-5)和(0，0)的圓。

參數設置：針對差分進化算法，種群規模NP=15D，終止條件為，CR與F設置如下：CR=0.8，Fmin=0.1，Fmax=0.8。

通過差分進化算法完成移動設備的路徑規劃時，算法的每一次循環矩陣的維數D和可移動設備路徑點的數量有密切關系，本文使用不包括開始點和目標點的路徑點n來表示數量(D=n)，由此得到本文的路徑點數量n和路徑點間隔d有關，關系式如下：

式中，x0為出發點橫坐標，xn+1為目標點橫坐標。

4.2 實例分析

圖1為DE的最優路徑，針對環境1和2，算法都能找到從開始點到目標點的最短路徑。如圖1(a)、(b)所示，特別是針對環境2這種障礙物較多的情形，DE算法也能夠找到最短路徑。

圖1 最優路徑圖

差分進化算法能夠針對不同環境和路徑點間隔得到到高質量的解，是一種有效的路徑規劃方法。

5 結語

本文提出將差分進化算法用于解決煤礦井下可移動設備在復雜環境下的無碰撞最短路徑規劃問題。實驗結果顯示，差分進化算法可以獲得高質量的解，有效解決煤礦井下可移動設備在復雜環境下的路徑尋優問題。