差分進(jìn)化算法在煤礦井下移動(dòng)設(shè)備路徑規(guī)劃的應(yīng)用研究

韓國國，范柄堯

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

1 前言

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

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

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

鑒于差分進(jìn)化算法在連續(xù)域的突出表現(xiàn)，本文將其用于解決煤礦井下可移動(dòng)設(shè)備的無碰撞最短路徑規(guī)劃問題。

2 煤礦井下移動(dòng)設(shè)備路徑規(guī)劃問題模型

針對(duì)煤礦井下可移動(dòng)設(shè)備路徑規(guī)劃問題，設(shè)計(jì)使可移動(dòng)設(shè)備從起始點(diǎn)到目標(biāo)點(diǎn)的路徑模型。本文將可移動(dòng)設(shè)備縮小為一個(gè)質(zhì)點(diǎn)，將各個(gè)障礙物設(shè)置成不同半徑的圓，煤礦井下可移動(dòng)設(shè)備運(yùn)行的最短無碰撞路徑模型如下：

式中，f表示可移動(dòng)設(shè)備運(yùn)行的最短無碰撞路徑；設(shè)起始位置坐標(biāo)為目標(biāo)坐標(biāo)為x2，…xn為將x0和xn+1關(guān)于x軸n+1等分后的n個(gè)點(diǎn)，b為x0和xn+1的n+1等分值。y1，y2，…yn為x1，x2，…

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

3 基于差分進(jìn)化算法的路徑規(guī)劃

3.1 種群初始化

差分進(jìn)化算法的初始化種群設(shè)置如下為：

式中，NP為種群規(guī)模，D為維數(shù)。

3.2 變異操作

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

3.3 交叉操作

本文采用二項(xiàng)式交叉方式進(jìn)行操作，試驗(yàn)向量中至少有一個(gè)分量由變異向量產(chǎn)生。具體操作如式（7）所示：

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

3.4 選擇操作

為產(chǎn)生下一代的目標(biāo)向量yi,g+1，根據(jù)目標(biāo)向量yi,g和試驗(yàn)向量ui,g的適應(yīng)值f()?來選擇最優(yōu)個(gè)體，具體步驟如式(8)所示：

4 實(shí)驗(yàn)仿真

4.1 環(huán)境參數(shù)設(shè)置

針對(duì)煤礦井下可移動(dòng)設(shè)備無碰撞最短路徑規(guī)劃問題，本文將差分進(jìn)化算法(DE/rand/1/bin)進(jìn)行仿真實(shí)驗(yàn)，為了保證試驗(yàn)的公平性，針對(duì)算法的參數(shù)進(jìn)行如下設(shè)置：

移動(dòng)設(shè)備的環(huán)境條件設(shè)置如下：將移動(dòng)設(shè)備在以下兩個(gè)環(huán)境中進(jìn)行仿真試驗(yàn)，其中環(huán)境1中有兩個(gè)障礙物，障礙物的情況如下：半徑都為1，坐標(biāo)原點(diǎn)分別為(-15，-10)、（15，10）的圓；環(huán)境2中有三個(gè)障礙物，障礙物的情況如下：半徑為1，坐標(biāo)原點(diǎn)分別為（20，5)、(-20，-5)和(0，0)的圓。

參數(shù)設(shè)置：針對(duì)差分進(jìn)化算法，種群規(guī)模NP=15D，終止條件為，CR與F設(shè)置如下：CR=0.8，F(xiàn)min=0.1，F(xiàn)max=0.8。

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

式中，x0為出發(fā)點(diǎn)橫坐標(biāo)，xn+1為目標(biāo)點(diǎn)橫坐標(biāo)。

4.2 實(shí)例分析

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

圖1 最優(yōu)路徑圖

差分進(jìn)化算法能夠針對(duì)不同環(huán)境和路徑點(diǎn)間隔得到到高質(zhì)量的解，是一種有效的路徑規(guī)劃方法。

5 結(jié)語

本文提出將差分進(jìn)化算法用于解決煤礦井下可移動(dòng)設(shè)備在復(fù)雜環(huán)境下的無碰撞最短路徑規(guī)劃問題。實(shí)驗(yàn)結(jié)果顯示，差分進(jìn)化算法可以獲得高質(zhì)量的解，有效解決煤礦井下可移動(dòng)設(shè)備在復(fù)雜環(huán)境下的路徑尋優(yōu)問題。