李寶磊，呂丹桔,張欽虎,施心陵,陳建華,張榆鋒

(1.南陽(yáng)師范學(xué)院物理與電子工程學(xué)院,河南南陽(yáng) 473061; 2.云南大學(xué)信息學(xué)院,云南昆明 650091)

?

基于多元優(yōu)化算法的路徑規(guī)劃

李寶磊1,2，呂丹桔2,張欽虎2,施心陵2,陳建華2,張榆鋒2

(1.南陽(yáng)師范學(xué)院物理與電子工程學(xué)院,河南南陽(yáng) 473061; 2.云南大學(xué)信息學(xué)院,云南昆明 650091)

本文提出了一種基于多元優(yōu)化算法和貝塞爾曲線的啟發(fā)式智能路徑規(guī)劃方法.該方法通過用貝塞爾曲線描述路徑的方法把路徑規(guī)劃問題轉(zhuǎn)化成最優(yōu)化問題.然后，使用多元優(yōu)化算法來尋找最優(yōu)的貝塞爾曲線控制點(diǎn)以獲得最優(yōu)路徑.多元優(yōu)化算法智能搜素個(gè)體協(xié)同合作交替的對(duì)解空間進(jìn)行全局、局部迭代搜索以找到最優(yōu)解.多元優(yōu)化算法的搜索個(gè)體(元)按照分工不同可以分為全局元和局部元.在一次迭代中，全局元首先探索整個(gè)解空間以找出更優(yōu)的潛在解區(qū)域.然后，局部元在各個(gè)潛在解區(qū)域進(jìn)行局部開采以改善解質(zhì)量.可見，搜索元具有分工不同的多元化特點(diǎn)，多元優(yōu)化算法也就因此而得名.分工不同的搜索元之間高效的溝通和合作保證了多元優(yōu)化算法的良好性能.為了評(píng)估多元優(yōu)化算法的性能，我們基于標(biāo)準(zhǔn)測(cè)試地圖比較了多元優(yōu)化算法與其它三種經(jīng)典啟發(fā)式智能路徑規(guī)劃算法.結(jié)果表明，我們提出的方法在最優(yōu)性，穩(wěn)定性和有效性上方面優(yōu)于其它方法.

多元優(yōu)化算法；全局元；局部元；路徑規(guī)劃；貝塞爾曲線

1 引言

路徑規(guī)劃問題的目標(biāo)是找到一條能夠滿足指定最優(yōu)化要求的可行路徑.路徑規(guī)劃是移動(dòng)機(jī)器人，視頻游戲等應(yīng)用中的一項(xiàng)基礎(chǔ)任務(wù)并且是一個(gè)NP(Non-deterministic Polynomial)完全問題[1].鑒于蟻群算法、遺傳算法和粒子群優(yōu)化算法等啟發(fā)式智能優(yōu)化算法在解決NP問題中表現(xiàn)出了計(jì)算效率高的特點(diǎn)[2].許多學(xué)者已經(jīng)把啟發(fā)式智能優(yōu)化算法應(yīng)用于解決路徑規(guī)劃問題[3,4].盡管它們已經(jīng)被證明能夠有效的解決路徑規(guī)劃問題[5,6].但是蟻群算法、遺傳算法和粒子群算法容易陷入由于路徑規(guī)劃環(huán)境中的障礙物產(chǎn)生的局部最優(yōu)解而停滯[7]，并且路徑編碼設(shè)計(jì)不合理導(dǎo)致尋優(yōu)過程中經(jīng)常產(chǎn)生不可行解[8].因此基于智能優(yōu)化算法的路徑規(guī)劃方法尋優(yōu)策略和路徑編碼設(shè)計(jì)方面仍有可改善的空間.近幾年，為了解決早熟收斂問題，許多學(xué)者提出了許多改進(jìn)的粒子群算法以及其它新穎的仿生優(yōu)化方法.其中螢火蟲算法(Firefly Algorithm，F(xiàn)A)被證明具有較強(qiáng)的魯棒性和自適應(yīng)性[9].螢火蟲算法受啟發(fā)于螢火蟲之間的相互吸引力與他們各自的亮度成正比與他們的距離成反比[10].盡管螢火蟲算法在路徑規(guī)劃問題中跳出局部最優(yōu)解的能力較遺傳算法和粒子群算法有所改善[11]，但是這些方法主要從高效信息傳播角度出發(fā)來改善算法的性能，而無法解決全局和局部搜索能力相互制約的問題.搜索個(gè)體分工不明確引起的全局、局部搜索不均衡會(huì)導(dǎo)致這些算法不能高效處理多峰復(fù)雜優(yōu)化問題[12].

為了加強(qiáng)全局搜索的同時(shí)保證局部搜索能力，我們提出了搜索個(gè)體(元)多元化分工、協(xié)同合作的多元化優(yōu)化算法以有效解決早熟收斂問題，從而保證算法的最優(yōu)性、穩(wěn)定性和效率.根據(jù)分工不同，搜索元可以分為全局元和局部元.全局元負(fù)責(zé)在整個(gè)搜索空間全局搜索以找到潛在最優(yōu)解區(qū)域.局部元負(fù)責(zé)對(duì)各個(gè)潛在解區(qū)域進(jìn)行局部搜索以期望找到該局部質(zhì)量更優(yōu)的解.搜索元多元化的分工解除了全局搜索和局部搜索之間的相互制約.這使得多元優(yōu)化算法能夠保證局部搜索的同時(shí)增強(qiáng)全局搜索以跳出局部最優(yōu)解[13].考慮到搜索元具有分工不同的多元化特點(diǎn)，我們以多元化優(yōu)化算法命名該算法.由于多元優(yōu)化算法獨(dú)特的特點(diǎn)，我們通過貝塞爾曲線技術(shù)把路徑規(guī)劃問題轉(zhuǎn)化為最優(yōu)化問題并利用多元優(yōu)化算法解決路徑規(guī)劃問題.

通過編碼規(guī)則把路徑規(guī)劃問題轉(zhuǎn)變?yōu)橐粋€(gè)最優(yōu)化問題是基于啟發(fā)式智能優(yōu)化算法的路徑規(guī)劃方法的關(guān)鍵.利用曲線描述路徑是一種簡(jiǎn)單有效的把路徑規(guī)劃問題轉(zhuǎn)變?yōu)橐粋€(gè)最優(yōu)化問題的方法.Liang教授比較了利用費(fèi)格森、η3和貝塞爾曲線來描述路徑的方法，并發(fā)現(xiàn)貝塞爾曲線是最適合[14].在該方法中，路徑是由控制點(diǎn)確定的貝塞爾曲線來描述的，啟發(fā)式智能優(yōu)化算法搜索解空間以找到最優(yōu)控制點(diǎn)位置.

本文利用多元優(yōu)化算法尋找最優(yōu)的貝塞爾曲線的控制點(diǎn)來解決路徑規(guī)劃問題.為了展示多元優(yōu)化算法的性能，本文基于標(biāo)準(zhǔn)測(cè)試地圖，進(jìn)行了利用智能優(yōu)化算法解決最短路徑優(yōu)化的對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，多元優(yōu)化算法在最優(yōu)性，穩(wěn)定性和效率三方面的性能優(yōu)于其它參比方法.

2 基本理論

2.1 多元優(yōu)化算法

多元優(yōu)化算法通過交替的全局、局部搜索對(duì)解空間進(jìn)行搜索.通過對(duì)歷史信息的篩選、記憶和共享來指導(dǎo)多元化搜索元分工合作對(duì)解空間分別進(jìn)行全面和細(xì)致的探索.算法基于如圖1所示的上三角型結(jié)構(gòu)體對(duì)歷史信息進(jìn)行篩選、記憶和共享.結(jié)構(gòu)體由一個(gè)全局有序鏈表和n個(gè)局部有序鏈表構(gòu)成.全局鏈表長(zhǎng)度為n，第i個(gè)局部鏈表長(zhǎng)度為n-i+1.全局鏈表基于全局元信息對(duì)潛在解區(qū)域的信息進(jìn)行記憶，更新與共享.每個(gè)局部鏈表基于該局部?jī)?nèi)局部元信息負(fù)責(zé)該區(qū)域內(nèi)歷史信息的記憶與更新.

多元優(yōu)化算法一次迭代包括全局搜索和局部搜索兩個(gè)階段.在全局搜索階段，按照式(1)在整個(gè)解空間隨機(jī)生成全局元對(duì)整個(gè)解空間進(jìn)行全局搜索.

G=[h1,…,hd]

hi=unifrnd(mini,maxi)

(1)

式中，hi表示第i個(gè)待尋優(yōu)參數(shù)，d是待尋優(yōu)參數(shù)的個(gè)數(shù)，也就是待優(yōu)化問題的維度；mini和maxi分別為解空間第i維的下限和上限；unifrnd(mini,maxi)函數(shù)返回一個(gè)均勻分布在mini和maxi之間的隨機(jī)數(shù).為了指導(dǎo)下一步的局部搜索，新生成的全局元與全局鏈表中的元比較，適應(yīng)度值較好的全局元被作為潛在解區(qū)域的中心記錄在結(jié)構(gòu)體的全局鏈表中.在局部搜索階段，根據(jù)式(2)在以全局元G為中心，r為半徑的局部鄰域內(nèi)隨機(jī)生成局部元實(shí)現(xiàn)對(duì)各個(gè)潛在解區(qū)域的局部搜索.

L=G+r×[l1,…,ld]

(2)

式中，li(i=1,…,d)是-1到1之間的隨機(jī)數(shù).新生成的局部元與局部鏈表中的元比較，較好的元作為歷史信息保留下來.如果局部元優(yōu)于該區(qū)域的全局元，則該局部元將取代全局元作為新的潛在解區(qū)域中心進(jìn)入全局鏈表，以此向該局域的最優(yōu)解逼近.

2.2 基于多元優(yōu)化算法的路徑規(guī)劃

在我們提出的方法中，多元優(yōu)化算法被用來尋找貝塞爾曲線的最優(yōu)控制頂點(diǎn)以確定一條最優(yōu)路徑.本文以可行條件下，路徑長(zhǎng)度最短為最優(yōu)目標(biāo)，基于貝塞爾曲線的最優(yōu)路徑問題定義為：

(3)

式中P是由貝塞爾曲線Pc所表示的路徑，flen(P)是路徑P的長(zhǎng)度.二維坐標(biāo)系中，由搜索元確定的貝塞爾曲線Pc可以由式(4)描述.

(4)

貝塞爾曲線控制點(diǎn)坐標(biāo)被作為待尋優(yōu)參數(shù)編碼為搜索元.多元優(yōu)化算法搜索元通過全局局部交替尋優(yōu)，進(jìn)行迭代更新，實(shí)現(xiàn)對(duì)貝塞爾曲線控制點(diǎn)的調(diào)整，以發(fā)現(xiàn)長(zhǎng)度最短的可行路徑，給出路徑規(guī)劃問題尋優(yōu)解.

圖2展示了基于多元優(yōu)化算法的路徑規(guī)劃方法的偽代碼.其中Xi,j是位于結(jié)構(gòu)表的第i行，第j列節(jié)點(diǎn)中的搜索元.

設(shè)置每次迭代中全局元個(gè)數(shù)m；第i個(gè)局部?jī)?nèi)分配的局部元個(gè)數(shù)mi；局部半徑r；最大迭代次數(shù)Imax；問題的維度d；解空間第i維的上、下限mini和maxi．以新生成的全局元，局部元Xi，j(i=1，2，…，m；j=mi)及其適應(yīng)度值初始化結(jié)構(gòu)體．Whilek

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

本文利用多元優(yōu)化算法解決最短路徑規(guī)劃問題，所以在可行的條件下路徑越短則越優(yōu).搜索元的適應(yīng)度就是它所確定的路徑的代價(jià).一條路徑P的代價(jià)函數(shù)定義如下:

(5)

式中flen(P)是路徑P的長(zhǎng)度，m是用來確定用來描述路徑的連續(xù)點(diǎn)的個(gè)數(shù)的，如果m取值過小，相鄰兩點(diǎn)距離較大，會(huì)出現(xiàn)由這些點(diǎn)連成的路徑與較小障礙物交叉的現(xiàn)象.本文實(shí)驗(yàn)中m取一個(gè)較大的值1000，即P是由1000個(gè)點(diǎn)描述的.如果用于表示路徑的1000個(gè)點(diǎn)都在可行區(qū)域，我們認(rèn)為這條路徑是可行的，否則其是不可行的.對(duì)于不可行的路徑我們實(shí)施懲罰策略.λ是平衡路徑長(zhǎng)度和懲罰的常數(shù)，其被設(shè)置為遠(yuǎn)大于實(shí)際最短路徑長(zhǎng)度的值500.Nim是路徑P上非可行區(qū)以及地圖外點(diǎn)的個(gè)數(shù).

3 實(shí)驗(yàn)

3.1 測(cè)試環(huán)境

為了構(gòu)造不同復(fù)雜程度的路徑規(guī)劃問題，本文從游戲Dragon Age：Origins標(biāo)準(zhǔn)地圖中選擇具有多樣性、復(fù)雜性的den400d[15]為實(shí)驗(yàn)環(huán)境.測(cè)試路徑規(guī)劃問題的起點(diǎn)、終點(diǎn)及多元優(yōu)化算法找到的最短路徑如圖3所示，其中可行區(qū)域?yàn)榘咨?，障礙物用黑色表示.‘□’和‘*’是問題起點(diǎn)和終點(diǎn)標(biāo)識(shí)符號(hào).

3.2 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)使用Matlab7.1在英特爾CPU T1600和內(nèi)存為2.5GB的計(jì)算機(jī)上進(jìn)行.所有算法的種群規(guī)模和最大迭代次數(shù)都分別設(shè)置為65和450，所以最大評(píng)價(jià)函數(shù)次數(shù)為29250.參與比較的算法和參數(shù)設(shè)置如下：

(1)精英保留策略的基因算法(GA with Elitist，EGA)：EGA算法是一種改進(jìn)GA算法，EGA迭代中，當(dāng)前種群最優(yōu)解以概率1被保留下來，目的是為了防止找到的最優(yōu)解丟失.該算法出處文獻(xiàn)中建議80%的新的一代是由輪盤賭選擇產(chǎn)生的，20%是由交叉產(chǎn)生的，基因突變概率為0.01[16].

(2)遞減慣性權(quán)重粒子群優(yōu)化算法(PSO with inertia weight，PSO-w)：慣性權(quán)重從1.4減少到0.5，加速度常數(shù)c1=c2=1.49445[17].

(3)螢火蟲算法：隨機(jī)參數(shù)α是0.2，吸引力β0設(shè)置為1，光吸收系數(shù)γ的值為1[18].

(4)多元優(yōu)化算法：局部鄰域的半徑值r為20.所使用的結(jié)構(gòu)體為上三角結(jié)構(gòu)，其中全局鏈表長(zhǎng)度是10，第i個(gè)局部鏈表長(zhǎng)度是10-i.因此，搜索群由10個(gè)全局元和55個(gè)局部元組成.

3.3 性能指標(biāo)

本文用30次獨(dú)立測(cè)試獲得的統(tǒng)計(jì)結(jié)果來比較不同方法的性能.以下三個(gè)標(biāo)準(zhǔn)分別用于評(píng)估不同方法的最優(yōu)性[19]，穩(wěn)定性和有效性.

(1)可行路徑長(zhǎng)度.30次測(cè)試中獲得的無碰撞可行的最短路徑長(zhǎng)度的均值Mf作為主要指標(biāo)，找到無碰撞可行的最短路徑的頻率Fr和T檢驗(yàn)(Student's t test)結(jié)果作為輔助指標(biāo)來評(píng)價(jià)算法的最優(yōu)性.最小的Mf值表明算法找到的最短路徑具有最優(yōu)性.可行最短路徑長(zhǎng)度的均值僅考慮了算法找到了可行路徑的測(cè)試，因此有必要統(tǒng)計(jì)可行率.可行率也就是30次測(cè)試中找到可行路徑的測(cè)試次數(shù)與總測(cè)試次數(shù)的比率.同時(shí)，利用T檢驗(yàn)來分析獲得最小Mf值的算法與其它算法在30次測(cè)試中獲得的結(jié)果的差異性.定義算法改善不顯著為原假設(shè).h=0表示以5%的顯著水平接受原假設(shè)，即算法改善不顯著.h=1表示以5%的顯著水平拒絕原假設(shè)，即算法改善明顯.

(2)成功速率(success rate),表示為Rs.成功速率是指算法找到的路徑長(zhǎng)度小于預(yù)設(shè)的可接受閾值(精度)的測(cè)試次數(shù)與總測(cè)試次數(shù)的比率.較高的成功速率表示在一個(gè)可接受的精度水平內(nèi)，算法解決問題的穩(wěn)定性較好.

(3)適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)均值(average number of fitness function evaluations)，表示為Afe.適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)均值是指30次測(cè)試中算法找到的路徑長(zhǎng)度小于預(yù)設(shè)可接受閾值所需要的適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)的平均值.較小適應(yīng)度函數(shù)評(píng)價(jià)均值表明較高的效率性.

4 結(jié)果分析

表1列出了可行路徑長(zhǎng)度的平均值、可行率和T檢驗(yàn)統(tǒng)計(jì)結(jié)果.最好的結(jié)果用黑體字標(biāo)出.從表1中我們可以得到以下結(jié)論：

(1)在除了P2以外的所有問題中，多元優(yōu)化算法具有最小的Mf值.這說明與精英保留策略的基因算法、遞減慣性權(quán)重粒子群優(yōu)化算法和螢火蟲算法相比，多元優(yōu)化算法找到的路徑較優(yōu).

(2)多元優(yōu)化算法和螢火蟲算法都以100%的可行率找到了可行路徑,而EGA和PSO-w不能保證100%的可行率.這說明EGA和PSO-w易陷入局部最優(yōu)解而無法找到可行路徑.但是多元優(yōu)化算法和螢火蟲算法具有跳出局部最優(yōu)解的能力.

(3)多元優(yōu)化算法獲得最小Mf值時(shí)，除了問題P4外，其它方法T檢驗(yàn)獲得的h值都為1.這表明，在大部分測(cè)試中多元優(yōu)化算法獲得的最短路徑較其它幾個(gè)方法有明顯改善.

綜上所述，多元優(yōu)化算法能夠以較高的可行率獲得較優(yōu)的路徑且改善水平顯著.因此，多元優(yōu)化算法在最優(yōu)性方面優(yōu)于精英保留策略的基因算法，遞減慣性權(quán)重粒子群優(yōu)化算法和螢火蟲算法.

表1 路徑長(zhǎng)度統(tǒng)計(jì)結(jié)果

在路徑規(guī)劃問題中，方法的穩(wěn)定性和效率也是一個(gè)重要的指標(biāo).表2中列出了成功率和適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)的均值.為了統(tǒng)計(jì)成功率，所有方法找到的最小Mf值的1.1倍作為可接受閾值.對(duì)于問題P1～P6，閾值分別是170，156，241，215，299和269.

表2 成功率和適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)均值

由表2我們可以得出以下結(jié)論：

(1)多元優(yōu)化算法解決所有測(cè)試問題的成功率均為100%，都大于精英保留策略的基因算法，遞減慣性權(quán)重粒子群優(yōu)化算法和螢火蟲算法.可見，多元優(yōu)化算法在穩(wěn)定性上優(yōu)于其它幾個(gè)參與比較的方法.

(2)與精英保留策略的基因算法、遞減慣性權(quán)重粒子群優(yōu)化算法和螢火蟲算法相比，多元優(yōu)化算法規(guī)劃出路徑長(zhǎng)度低于指定可接受閾值所需要的適應(yīng)度值函數(shù)評(píng)價(jià)次數(shù)均值較小.這說明多元優(yōu)化算法具有較高的效率.

綜上所述，多元優(yōu)化算法能夠在較少的適應(yīng)度值評(píng)價(jià)次數(shù)內(nèi)獲得較高的成功率.

5 結(jié)論

本文利用多元優(yōu)化算法尋找最優(yōu)貝塞爾曲線的控制點(diǎn)來解決最短路徑規(guī)劃問題.基于標(biāo)準(zhǔn)測(cè)試地圖，我們進(jìn)行了對(duì)比試驗(yàn)，從最優(yōu)性、穩(wěn)定性和效率三個(gè)方面比較了多元優(yōu)化算法以及其它三個(gè)常用智能優(yōu)化算法的性能.結(jié)果表明，多元優(yōu)化算法在最優(yōu)性，穩(wěn)定性和效率方面優(yōu)于其它參與比較方法的.

基于多元優(yōu)化算法的路徑規(guī)劃方法需要根據(jù)地圖的大小，人工調(diào)整局部鄰域半徑r，以獲得較好的性能.下一步的工作將集中在利用局部鏈表中的歷史信息自適應(yīng)調(diào)整局部鄰域半徑r以期望保證算法效率和穩(wěn)定性的同時(shí)提高最優(yōu)解質(zhì)量.

[1]Canny J,Reif J.New lower bound techniques for robot motion planning problems[A].IEEE Symposium on the Foundations of Computer[C].Los Angeles,CA,USA:IEEE,1987.49-60.

[2]Raja P,Pugazhenthi S.Optimal path planning of mobile robots:A review[J].International Journal of Physical Sciences,2012,7(9):1314-1320.

[3]Hu Y,Yang S X.A knowledge based genetic algorithm for path planning of a mobile robot[A].2004 IEEE International Conference on Robotics and Automation[C].New Orleans,LA,USA:IEEE,2004.4350-4355.

[4]柳長(zhǎng)安,鄢小虎,劉春陽(yáng),等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J].電子學(xué)報(bào),2011,39(5):1220-1224.

Liu Chang-an，Yan Xiao-hu，Liu Chun-yang,et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J].Acta Electronic Sinica,2011,39(5):1220-1224.(in Chinese)

[5]周蘭鳳，洪炳熔.用基于知識(shí)的遺傳算法實(shí)現(xiàn)移動(dòng)機(jī)器人路徑規(guī)劃[J].電子學(xué)報(bào),2006,34(5):911-914.

Zhou Lan-feng,Hong Bin-rong.A knowledge based genetic algorithm for path planning of a mobile robot[J].Acta Electronic Sinica,2006,34(5):911-914.(in Chinese)

[6]吳憲祥,郭寶龍,王娟.基于粒子群三次樣條優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃算法[J].機(jī)器人,2009,31(6):556-560.

Wu Xian-xiang,Guo Bao-long,Wang Juan.Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J].Robot,2009,31(6):556-560.(in Chinese)

[7]徐曉晴,朱慶保.動(dòng)態(tài)環(huán)境下基于多人工魚群算法和避碰規(guī)則庫(kù)的機(jī)器人路徑規(guī)劃[J].電子學(xué)報(bào),2012,40(8):1694-1700.

Xu Xiao-qing,Zhu Qing-bao.Multi-artificial fish-swarm algorithm and a rule library based dynamic collision avoidance algorithm for robot path planning in a dynamic environment[J].Acta Electronic Sinica,2012,40(8):1694-1700.(in Chinese)

[8]陳剛，沈林成.復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法[J].機(jī)器人，2001，23(1)：40-44.

Chen Gang,Shen Lin-cheng.Genetic path planning algorithm for complex environment path planning[J].Robot,2001,23(1):40-44.(in Chinese)

[9]Fister I,Yang X S,Fister D,et al.Firefly Algorithm:A Brief Review of the Expanding Literature[M].Berlin：Springer,2014,347-360.

[10]Yang X S.Firefly Algorithms for Multimodal Optimization[M].Berlin:Springer,2009:169-178.

[11]Liu C,Gao Z,Zhao W.A new path planning method based on firefly algorithm[A].2012 Fifth International Joint Conference on Computational Sciences and Optimization[C].Harbin:IEEE,2012.775-778.

[12]Ostadmohammadi Arani B,Mirzabeygi P,Shariat Panahi M.An improved PSO algorithm with a territorial diversity-preserving scheme and enhanced exploration-exploitation balance[J].Swarm and Evolutionary Computation,2013,11(2013):1-15.

[13]Li B L,Shi X L,Gou C X,et al.Multivariant optimization algorithm for multimodal optimization[A].Proceedings of the International Conference on Mechanical Engineering,Materials and Energy[C].Switzerland:Trans Tech Publications Ltd，2014.453-457.

[14]Liang J J,Song H,Qu B Y,et al.Comparison of three different curves used in path planning problems based on particle swarm Optimizer[J].Mathematical Problems in Engineering,2014，2014(2014):(1-15).

[15]Sturtevant N R.Benchmarks for grid-based path finding[J].IEEE Transactions on Computational Intelligence and AI in Games,2012,4(2):144-148.

[17]Shi Y,Eberhart R.A modified particle swarm optimizer[A].1998 IEEE International Conference on Computational Intelligence[C].Anchorage,AK:IEEE,1998.69-73.

[18]Yang X S.Firefly algorithm,stochastic test functions and design optimisation[J].International Journal of Bio-Inspired Computation,2010,2(2):78-84.

[19]曲道奎,杜振軍,等.移動(dòng)機(jī)器人路徑規(guī)劃方法研究[J].機(jī)器人,2008,30(2):97-101.

Qu D K,Du Z J,et al.Research on path planning for a mobile robot[J].Robot,2008,30(2):97-101.(in Chinese)

李寶磊 男,1987年4月出生，河南駐馬店人.2009年畢業(yè)于延邊大學(xué)通信工程系，2012年獲得云南大學(xué)通信與信息系統(tǒng)專業(yè)碩士研究生學(xué)位，2012年進(jìn)入云南大學(xué)信息與通信工程專業(yè)攻讀博士學(xué)位，現(xiàn)在為南陽(yáng)師范學(xué)院講師，從事自適應(yīng)信號(hào)處理、智能優(yōu)化算法方面的有關(guān)研究.

E-mail:bl-li@qq.com

呂丹桔 女,1977年11月出生，云南昭通人,副教授.分別于2000年、2012年在云南大學(xué)獲工學(xué)學(xué)士和工學(xué)碩士,2012年進(jìn)入云南大學(xué)信息與通信工程專業(yè)，現(xiàn)為博士研究生,主要從事智能優(yōu)化算法、信號(hào)檢測(cè)方面的有關(guān)研究.

E-mail：lvdanjv@gmail.com

張欽虎 男,1988年8月出生，四川南充人.2012年畢業(yè)于內(nèi)江師范學(xué)院電子信息工程，于2012年進(jìn)入云南大學(xué)信息學(xué)院攻讀碩士研究生學(xué)位，從事自適應(yīng)信號(hào)處理、智能優(yōu)化算法方面的有關(guān)研究.

E-mail:472765713@qq.com

施心陵(通信作者) 男,1956年4月出生，云南昆明人.1983年畢業(yè)于云南大學(xué)無線電電子學(xué)專業(yè),現(xiàn)為云南大學(xué)信息學(xué)院教授、博士生導(dǎo)師.主要從事智能優(yōu)化算法、生物醫(yī)學(xué)、自適應(yīng)信號(hào)處理等方面的研究工作.

E-mail:xlshi@ynu.edu.cn

張榆鋒 男,1965年出生，云南昆明人.1986年、1989年和2009年分別在云南大學(xué)獲工學(xué)學(xué)士、工學(xué)碩士和工學(xué)博士學(xué)位,現(xiàn)為云南大學(xué)信息學(xué)院教授、博士生導(dǎo)師.主要從事物醫(yī)學(xué)工程與超聲醫(yī)學(xué)工程等方面的研究工作.

E-mail:zhangyf@ynu.edu.cn

陳建華 男,1964年出生，云南昆明人.現(xiàn)為云南大學(xué)信息學(xué)院電子工程系教授、博士生導(dǎo)師,主要從事信息傳輸理論與應(yīng)用,信號(hào)處理等方面的研究工作.

E-mail：chenjh@ynu.edu.cn

A Path Planner Based on Multivariant Optimization Algorithm

LI Bao-lei1,2,Lü Dan-jü2,ZHANG Qin-hu2,SHI Xin-ling2,CHEN Jian-hua2,ZHANG Yu-feng2

(1.PhysicsandElectronicEngineeringCollege,NanyangNormalUniversity,Nanyang,Henan473061,China;2.SchoolofInformationScienceandEngineering,YunnanUniversity,Kunming,Yunnan650091,China)

A heuristic intelligent path planning method based on the multivariant optimization algorithm and the Bezier curve is presented.The path planning problem is transformed into an optimization problem through using the Bezier curve to represent a path in this method.Then,the multivariant optimization algorithm is applied to find the optimal control points of the best Bezier curve,aiming at finding the optimal path.The multivariant optimization algorithm searches the solution space through iterations of alternative global and local search.According to the different responsibilities,the search individuals (atoms) could be divided into two types:the global atoms and the local atoms.In each iteration,global atoms explore the whole solution space to local potential areas,and then,local atoms exploit each potential area.Obviously,atoms are characterized by multivariant responsibilities,hence the name of the multivariant optimization algorithm.The good performance of the multivariant optimization algorithm is ensured by the efficient communication and cooperation of multivariant atoms.To evaluate the performance of the multivariant optimization algorithm,comparative experiments against the other three classical heuristic path planning algorithms are carried out based on a standard testing map.The results show that our proposed method is superior to the other methods in optimality,stability and efficiency.

multivariant optimization algorithm;global atom;local atom;path planning;Bezier curve

2014-06-06;

2015-03-05;責(zé)任編輯:梅志強(qiáng)

國(guó)家自然科學(xué)基金(No.61261007，No.61403349，No.11303094);云南省自然科學(xué)基金重點(diǎn)項(xiàng)目(No.2013FA008)

TP242

A

0372-2112 (2016) 09-2242-06

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.032