音凌一，向鳳紅，毛劍琳

（昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500）

移動(dòng)機(jī)器人路徑規(guī)劃是指：在給定的環(huán)境中，根據(jù)指定的評(píng)價(jià)標(biāo)準(zhǔn)規(guī)劃出一條從起點(diǎn)到目標(biāo)點(diǎn)的可行路徑，并保證移動(dòng)機(jī)器人在不會(huì)碰撞到障礙物的前提下，盡可能優(yōu)化路徑[1]。

隨著移動(dòng)機(jī)器人應(yīng)用場(chǎng)景的不斷拓展，對(duì)移動(dòng)機(jī)器人路徑規(guī)劃的要求越來越高，越來越多的研究學(xué)者開始在路徑規(guī)劃的問題研究上，使用群智能算法。如蟻群算法（ACO）[2]、粒子群算法（PSO）[3]和螢火蟲算法（FA）[4]等。

灰狼優(yōu)化算法（Grey wolf optimizer，GWO）是2014 年由澳大利亞學(xué)者M(jìn)irjalili 等提出的一種群智能優(yōu)化算法[5]。該算法是通過模擬灰狼種群的等級(jí)制度和捕獵行為，來實(shí)現(xiàn)優(yōu)化搜索的目的，具有原理簡(jiǎn)單、參數(shù)少、易于實(shí)現(xiàn)和有較強(qiáng)的全局搜索能力等特點(diǎn)。已經(jīng)被證明在函數(shù)優(yōu)化方面，在求解精度和收斂性上要明顯優(yōu)于粒子群優(yōu)化、引力搜索算法（GSA）[6]、差分進(jìn)化算法（DE）[7]和遺傳算法[8]的結(jié)果。目前灰狼優(yōu)化算法已經(jīng)在調(diào)度問題[9]、求解約束優(yōu)化問題[10]、高維優(yōu)化問題[11]和路徑規(guī)劃問題等方面得到成功的應(yīng)用。但是，GWO 算法和其它的群智能算法相似，也存在著求解精度低，收斂速度慢和易陷入局部最優(yōu)的問題。同時(shí)應(yīng)用在路徑規(guī)劃上，出現(xiàn)了易陷入局部最優(yōu)和效率低的問題。為克服這些問題，研究學(xué)者們提出了各種改進(jìn)方法。

Long 等[12]提出一種基于對(duì)數(shù)函數(shù)的非線性衰減參數(shù)a，將參數(shù)a改進(jìn)成先快后慢的非線性衰減，增加了算法局部搜索的時(shí)間，但這種非線性衰減方式，減少了全局搜索的時(shí)間；滕志軍等[13]受到PSO算法的啟發(fā)，將個(gè)體的歷史最佳位置引入到灰狼的位置更新公式中，同時(shí)采用二次函數(shù)，將線性衰減參數(shù)a改進(jìn)成先慢后快的非線性衰減；魏政磊等[14]利用α狼、β狼和δ狼的適應(yīng)度值，基于與適應(yīng)度值成正比的概率分布，改進(jìn)了位置更新公式，但忽略了算法在求解最大值問題時(shí)，α狼的占比會(huì)變成最小的情況；劉二輝等[15]根據(jù)路徑規(guī)劃的具體問題，引入了路徑微調(diào)算子和鄰域變異算子，有效的提高了算法在路徑規(guī)劃問題上的性能，但這種改進(jìn)的算法只針對(duì)路徑規(guī)劃問題，無法適用于解決其他問題；Zhang 等[16]根據(jù)灰狼之間的最大距離和平均距離，設(shè)置距離變化率，引入動(dòng)態(tài)權(quán)重，改進(jìn)了位置更新公式，并把改進(jìn)后的算法成功的應(yīng)用在三維路徑規(guī)劃問題上，但并沒處理算法應(yīng)用在路徑規(guī)劃上效率低的問題。趙江等[17]提出了特征柵格的概念，并通過仿真實(shí)驗(yàn)，證明特征柵格地圖，可以有效的加快群智能算法在路徑規(guī)劃問題上的求解速度，但設(shè)置的特征柵格提取規(guī)則和鄰接矩陣的建立都太過繁瑣。

基于以上研究，本文提出了一種改進(jìn)灰狼優(yōu)化算法（Improved gray wolf,IGWO）在特征柵格地圖上的路徑規(guī)劃方法。先對(duì)灰狼算法進(jìn)行改進(jìn)，引入調(diào)節(jié)因子來控制參數(shù)a的衰減，又引入動(dòng)態(tài)權(quán)重和游走策略提高算法的性能；之后提出了判斷特征柵格的新方法，加快了特征柵格地圖的建立；同時(shí)為簡(jiǎn)化鄰接矩陣的建立，提出了遠(yuǎn)距離柵格和可視步長(zhǎng)。

1 灰狼優(yōu)化算法的改進(jìn)

灰狼是位于生物界食物鏈頂端的動(dòng)物。一般是群居生活，種群內(nèi)分為4 個(gè)等級(jí)：第一級(jí)是α狼，是領(lǐng)導(dǎo)整個(gè)種群的個(gè)體；第二級(jí)是β狼，主要是輔助α狼進(jìn)行決策；第三級(jí)是δ狼，執(zhí)行偵查和放哨等任務(wù)；第四級(jí)是ω狼，是最底層的灰狼，服從前三級(jí)狼的指揮?；依莾?yōu)化算法就是對(duì)灰狼種群按等級(jí)制度進(jìn)行捕獵行為的數(shù)學(xué)模擬，其數(shù)學(xué)描述為

1）包圍獵物

式中：t為當(dāng)前的迭代次數(shù)；A和C為協(xié)同向量系數(shù)；XP（t）為獵物位置；X為灰狼的位置向量。

向量A和C的計(jì)算公式為：

式中：a為在迭代過程中從2 線性減少到0；r1和r2是[0,1]中的隨機(jī)向量。

2）狩獵

式中：Xα、Xβ和Xδ分別為最優(yōu)解、次優(yōu)解和第三優(yōu)解的位置；Dα、Dβ和Dδ分別為灰狼個(gè)體到α狼、β狼和δ狼的距離。

3）搜尋和攻擊獵物

灰狼群體主要根據(jù)α狼、β狼和δ狼的信息來進(jìn)行捕獵，在數(shù)學(xué)描述中主要根據(jù)A向量來控制灰狼是搜尋獵物還是攻擊獵物。當(dāng)|A|＜1 時(shí)，強(qiáng)迫灰狼攻擊獵物；當(dāng)|A|＞1 時(shí)，迫使灰狼遠(yuǎn)離獵物，擴(kuò)大搜索范圍，去尋找下一個(gè)獵物

1.1 可調(diào)節(jié)非線性收斂因子

由前述可知，在灰狼優(yōu)化算法中調(diào)節(jié)算法全局搜索和局部搜索的平衡主要是由參數(shù)A決定的，從式（3）可以看出，參數(shù)A的變化由a決定。對(duì)于不同的實(shí)際情況，對(duì)算法是更傾向于全局搜索還是更傾向于局部搜索的要求是不同，如果只是將收斂因子a簡(jiǎn)單地改進(jìn)成非線性衰減，不符合實(shí)際要求的。為了達(dá)到根據(jù)具體要求對(duì)a的衰減進(jìn)行調(diào)節(jié)的目的，本文提出了一種基于調(diào)節(jié)因子n的可調(diào)節(jié)非線性收斂因子。根據(jù)算法應(yīng)用情況的不同，調(diào)節(jié)n的大小，使a以不同的衰減方式進(jìn)行衰減。

式中：t為當(dāng)前迭代次數(shù)；tm為最大迭代次數(shù)。

圖1 所示的是當(dāng)t=1 000 時(shí)，不同取值n對(duì)a衰減的影響，可以明顯看出當(dāng)n的取值不同時(shí)，a的衰減方式也是不同的。當(dāng)n取值越小時(shí)，a的值在迭代中會(huì)越早達(dá)到1，即A的值達(dá)到1 的時(shí)間也會(huì)越早，算法在局部搜索的時(shí)間會(huì)加長(zhǎng)；當(dāng)n取值越大時(shí)，a的值在迭代中會(huì)越遲達(dá)到1，即A的值達(dá)到1 的時(shí)間也會(huì)越遲，算法在全局搜索的時(shí)間會(huì)加長(zhǎng)。同時(shí)不管n的取值是多少時(shí)，a都是非線性衰減。

圖1 收斂因子對(duì)比圖Fig.1 Convergence factor comparison

1.2 動(dòng)態(tài)權(quán)重

標(biāo)準(zhǔn)灰狼算法中灰狼種群中，個(gè)體進(jìn)行位置更新是根據(jù)α狼、β狼和δ狼的位置進(jìn)行更新的，3 只狼起著一樣的作用，并沒有體現(xiàn)出α狼是最優(yōu)狼的重要性，這種平均作用，會(huì)使算法的整體收斂速度變慢。為加快算法的整體收斂速度，本文提出一種基于適應(yīng)度變化的動(dòng)態(tài)權(quán)重，在迭代中加大優(yōu)秀狼的作用，減少較差狼的作用。

式中：fα、fβ和fδ分別為α狼、β狼和δ狼的適應(yīng)度值。

根據(jù)式（8）可改寫為

1.3 游走策略

式（10）和式（11）通過動(dòng)態(tài)權(quán)重，加大了迭代過程中優(yōu)秀狼的作用，但這也減小了當(dāng)α狼陷入局部最優(yōu)時(shí)，算法逃離局部最優(yōu)的能力。為了增強(qiáng)算法避免陷入局部最優(yōu)的能力，提出了基于灰狼個(gè)體信息和最優(yōu)信息的游走策略。

基于個(gè)體信息的游走，則

基于最優(yōu)信息的游走，則

式中：i和j為種群中隨機(jī)的兩個(gè)不同的個(gè)體；rand 為（-1,1）之間的隨機(jī)數(shù)；o 為種群中最優(yōu)的個(gè)體。

1.4 改進(jìn)算法的具體步驟

改進(jìn)后算法的具體步驟如下：

步驟1 根據(jù)不同問題的需求，確定調(diào)節(jié)因子n的大小。

步驟2 初始化灰狼種群，設(shè)置種群大小N、最大迭代tmax。

步驟3 計(jì)算每個(gè)灰狼個(gè)體的適應(yīng)度，確定α狼，β狼和δ狼。

步驟4 計(jì)算參數(shù)a、A及C。

步驟5 根據(jù)式（11）更新灰狼個(gè)體。

步驟8 是否達(dá)到最大迭代次數(shù)。是，輸出最優(yōu)個(gè)體和最優(yōu)個(gè)體適應(yīng)度值；否，進(jìn)行步驟4。

2 改進(jìn)特征柵格地圖

2.1 特殊柵格的確定

文獻(xiàn)[17]提出了特征柵格的概念，通過對(duì)柵格地圖中特征柵格的提取，簡(jiǎn)化柵格地圖，以達(dá)到加快搜索速度，優(yōu)化搜索路徑的目的。具體是通過蒙特卡羅模擬，總結(jié)出12 種可以組成任何障礙物的基本形狀障礙柵格，在確定這12 種基本形狀柵格的特征柵格位置。如果要確定地圖中具體特征柵格的所在位置，首先確認(rèn)柵格地圖中障礙柵格是由哪幾種基本形狀組成后，之后才能確認(rèn)特征柵格的所在位置，通過這種方法來確認(rèn)特征柵格的位置，太過于繁瑣。本文基于特殊柵格的概念提出了一種只用通過探索每個(gè)柵格周圍9 鄰域柵格的障礙物是否存在，來確認(rèn)該柵格是否為特殊柵格的方法。

1）判斷柵格是否是障礙柵格，設(shè)機(jī)器人a所在的位置為（i,j），即（i,j）不能是障礙柵格。

2）判斷柵格是否在障礙物的頂角。（i+1,j+1）、（i+1,j-1）、（i-1,j+1）和（i-1,j-1）中，至少有一個(gè)柵格存在著障礙物，也就是圖2 中黑色區(qū)域位置。

圖2 特征柵格的判定Fig.2 Determination of characteristic grids

3）判斷柵格的連通性是否完好。（i+1,j）、（i-1,j）、（i,j+1）和（i,j-1）中，至少有兩個(gè)柵格中沒有障礙物，也就是圖2 中紅色區(qū)域位置。

4）滿足1）～3）條件的柵格即為特征柵格。

此方法只需要對(duì)柵格周圍的9 鄰域柵格進(jìn)行簡(jiǎn)單的判斷，就能準(zhǔn)確快速的確認(rèn)柵格是否為特征柵格。建立20×20 的柵格地圖，利用本文提出的判斷特征柵格的方法，對(duì)柵格地圖中的柵格進(jìn)行判斷并提取，其中提取出的特征柵格用藍(lán)色的“+”標(biāo)記出來，如圖3 所示。

圖3 提取特征柵格Fig.3 Extraction of feature grids

2.2 遠(yuǎn)距離特征柵格

對(duì)于大多數(shù)的路徑規(guī)劃問題來說，最短的路徑都是產(chǎn)生在起點(diǎn)與終點(diǎn)的連線附近?；谶@種思想，本文設(shè)立了距離限制D，判斷特征柵格與起點(diǎn)和終點(diǎn)連線線段的距離，去掉與起點(diǎn)和終點(diǎn)連線線段距離過遠(yuǎn)的特征柵格。

式中：（a1，b1）為起點(diǎn)坐標(biāo)；（a2，b2）為終點(diǎn)坐標(biāo)；（i，j）為特征柵格點(diǎn)的坐標(biāo)。當(dāng)a1=a2，即起點(diǎn)和終點(diǎn)在一條縱軸上，距離為|i-a1|。

具體的距離限制D的大小，要根據(jù)地圖的實(shí)際情況設(shè)置。設(shè)置D的大小后，對(duì)所有特征柵格進(jìn)行判斷，滿足dij＞D的特征柵格全部認(rèn)為是遠(yuǎn)距離特征柵格。設(shè)置D=6，起點(diǎn)為（1,1），終點(diǎn)為（20,20），去除特征柵格中的遠(yuǎn)距離特征柵格，處理過后的特征柵格地圖如圖4a）所示；設(shè)置D=10，起點(diǎn)為（1,1），終點(diǎn)為（1,20），除去特征柵格中的遠(yuǎn)距離特征柵格，處理過后的特征柵格地圖如圖4b）所示。其中紅色的“+”號(hào)是除去的遠(yuǎn)距離柵格，可以明顯看出特征柵格減少了許多。

圖4 遠(yuǎn)距離柵格的去除Fig.4 Removal of distant grids

2.3 設(shè)置可視步長(zhǎng)

確定特征柵格后，因?yàn)樘卣鳀鸥裰g的連通性并不能保證，所以要對(duì)所有的特征柵格進(jìn)行可視性判斷。圖4a）雖然對(duì)20×20 的柵格地圖已經(jīng)進(jìn)行了特征柵格的提取和對(duì)遠(yuǎn)距離特征柵格的去除，但是保留下來的特征柵格仍然還有60 個(gè)，如果對(duì)所有的特征柵格點(diǎn)進(jìn)行可視性判斷，將要進(jìn)行次。但是當(dāng)兩個(gè)特征柵格的相隔距離過長(zhǎng)時(shí)，它們之間可視的概率也會(huì)降低，可視性判斷大部分都是不可視的。為此設(shè)置可視步長(zhǎng)L，用來減少特征柵格之間可視性判斷的次數(shù)和提高建立鄰接矩陣的速度。設(shè)特征柵格點(diǎn)的坐標(biāo)為（i,j），即最遠(yuǎn)只會(huì)對(duì)（i+L,j+L）,（i+L,j-L）,（i-L,j+L）和（i-L,j+L）這4 個(gè)柵格點(diǎn)進(jìn)行可視性判斷。雖然這樣構(gòu)成的鄰接矩陣還是60×60 的，但是減少了可視性判斷的次數(shù)，同時(shí)也簡(jiǎn)化了鄰接矩陣構(gòu)成。

如圖5 所示，設(shè)A點(diǎn)的坐標(biāo)為（i，j），可視步長(zhǎng)為L(zhǎng)=2。對(duì)A點(diǎn)進(jìn)行可視性的判斷，即A點(diǎn)的可視范圍最遠(yuǎn)（i+2,j+2）,（i+2,j-2）,（i-2,j+2）和（i-2,j-2），i為紅色標(biāo)記的柵格。

圖5 可視性判斷Fig.5 Visibility determination

1）兩個(gè)特征柵格之間的連線不經(jīng)過障礙物，如圖中A柵格和B柵格的情況，判斷特征柵格可視，路徑L1可以行走。

2）兩個(gè)特征柵格之間的連線不經(jīng)過障礙物，但是與障礙物的頂點(diǎn)相切，因?yàn)槭菍C(jī)器人視為質(zhì)點(diǎn)，且柵格都進(jìn)行了膨脹處理，所以如圖5 中A柵格和C柵格的情況，判斷為特征柵格可視，路徑L2可以行走。

3）兩個(gè)特征柵格之間的連線經(jīng)過障礙物，如圖5中A柵格和D柵格的情況，判斷特征柵格不可視，路徑L3不可以行走。

4）兩個(gè)特征柵格超出了可視范圍，如圖中A柵格和E柵格的情況，判斷特征柵格不可視，路徑L4不可行走。

通過以上4 點(diǎn)判斷可以快速的確認(rèn)特征柵格之間的可視性，建立所對(duì)應(yīng)的鄰接矩陣。

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

3.1 標(biāo)準(zhǔn)測(cè)試函數(shù)實(shí)驗(yàn)仿真

為證明改進(jìn)算法的性能，本文使用單峰函數(shù)、多峰函數(shù)和固定多峰函數(shù)3 種具有不同特點(diǎn)的標(biāo)準(zhǔn)測(cè)試函數(shù)測(cè)試改進(jìn)算法的有效性，表1 給出了具體的標(biāo)準(zhǔn)測(cè)試函數(shù)。此次仿真實(shí)驗(yàn)為避免單次仿真實(shí)驗(yàn)結(jié)果的偶然性，會(huì)進(jìn)行50 次重復(fù)實(shí)驗(yàn)，計(jì)算仿真結(jié)果的標(biāo)準(zhǔn)差和平均值，用平均值來表示算法的精度，用標(biāo)準(zhǔn)差來表示算法穩(wěn)定性。在與GWO 算法、PSOGWO 算法[13]和EGWO 算法[18]進(jìn)行比較。在仿真中，IGWO1 算法和IGWO2 算法是采用本文所提出可調(diào)節(jié)收斂因子的方法進(jìn)行改進(jìn)的算法,只不過調(diào)節(jié)因子n的大小不同，IGWO3 算法是采用本文所提出的可調(diào)節(jié)收斂因子和動(dòng)態(tài)權(quán)重的方法進(jìn)行改進(jìn)的算法。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)Tab.1 Standard test functions

本次仿真實(shí)驗(yàn)的參數(shù)設(shè)置，最大迭代次數(shù)tmax=1 000、種群大小N=30；PSOGWO 算法中學(xué)習(xí)因子c1=c2=2；IGWO1 算法、IGWO3 算法和IGWO 中調(diào)節(jié)因子為n=600；IGWO2 算法調(diào)節(jié)因子為n=800。

表2 為50 次仿真實(shí)驗(yàn)的平均值和標(biāo)準(zhǔn)差。由表2 明顯可見IGWO 算法在單峰值函數(shù)f1～f3和多峰值函數(shù)f5～f8上表現(xiàn)較好，而IGWO1 算法在這些函數(shù)上表現(xiàn)較差，這說明動(dòng)態(tài)權(quán)重和隨機(jī)游走策略對(duì)算法的收斂精度和收斂速度有著正面的影響。而從固定多峰函數(shù)f9～f12上來看IGWO1 和IGWO2的改進(jìn)效果要明顯好于IGWO 和IGWO3 的效果。由式（15）可知，新的位置更新公式是根據(jù)α狼、β狼和δ狼的適應(yīng)度值的絕對(duì)值大小占比來自適應(yīng)的調(diào)整α狼、β狼和δ狼在灰狼位置更新公式中的占比，這個(gè)辦法可以保證α狼在整個(gè)尋優(yōu)的過程中所占的權(quán)重一直是最大的，有效加快算法的收斂精度和收斂速度，但是當(dāng)α狼陷入局部最優(yōu)時(shí)，根據(jù)公式α狼的占比依舊是最大的，這就會(huì)導(dǎo)致算法陷入局部最優(yōu)，所以本文提出了游走策略，防止算法陷入局部最優(yōu)。由IGWO3 算法和IGWO 算法在固定多峰函數(shù)f9～f12的對(duì)比可以看出，游走策略在避免局部最優(yōu)問題上，具有較好的效果。

表2 標(biāo)準(zhǔn)測(cè)試函數(shù)仿真結(jié)果Tab.2 Simulation results for standard test functions

綜上所述，在解決單峰和多峰函數(shù)時(shí)IGWO 具有更好的效果，在解決固定多峰函數(shù)時(shí)IGWO1 和IGWO2 的改進(jìn)策略，具有更好的效果。

為進(jìn)一步測(cè)試改進(jìn)算法的性能，在單峰、多峰和固定多峰函數(shù)中各選出兩個(gè)函數(shù)，分析收斂曲線，收斂曲線如圖6 所示。從圖6a）～圖6d）中可以看出，相比其它算法，IGWO 算法和IGWO3 算法的收斂速度有著大幅度的提高，其中IGWO 算法的收斂速度更快，說明游走策略對(duì)收斂速度有一定積極的影響，但是影響不大。從圖6c）～圖6f）中可以看出算法IGWO 相比IGWO3 算法的收斂曲線多出許多折線，說明游走策略在α狼陷入局部最優(yōu)時(shí)，可幫助算法逃離局部最優(yōu)。對(duì)比IGWO1 算法和IGWO2算法的收斂曲線，會(huì)發(fā)現(xiàn)兩種算法的收斂速度、收斂精度以及穩(wěn)定性都是不一樣的，說明調(diào)節(jié)因子n的改變會(huì)影響算法的性能。證明了根據(jù)實(shí)際問題，設(shè)置調(diào)節(jié)因子n，調(diào)節(jié)參數(shù)a的衰減方式的方法是有效的。

圖6 收斂曲線Fig.6 Convergence curve

為驗(yàn)證算法在路徑規(guī)劃問題上的性能，下文將把IGWO 算法應(yīng)用在柵格地圖和改進(jìn)的特征柵格地圖上，來證明IGWO 算法在路徑規(guī)劃問題上的具體性能。

3.2 路徑規(guī)劃仿真實(shí)驗(yàn)

在路徑規(guī)劃問題中，灰狼個(gè)體儲(chǔ)存的其實(shí)是一個(gè)一個(gè)的節(jié)點(diǎn)。這里的節(jié)點(diǎn)是整數(shù)，并不會(huì)存在小數(shù)，但是灰狼優(yōu)化算法的位置更新公式和游走策略，會(huì)產(chǎn)生小數(shù)，所以在此次迭代中所有小數(shù)進(jìn)行取整操作。同時(shí)在普通柵格地圖中，游走策略可能會(huì)產(chǎn)生障礙物節(jié)點(diǎn)，當(dāng)產(chǎn)生這樣的節(jié)點(diǎn)時(shí)，用距離障礙物最近的一個(gè)非障礙物節(jié)點(diǎn)代替。

IGWO 算法在路徑規(guī)劃上的具體步驟：

步驟1 設(shè)置種群規(guī)模N，最大迭代次數(shù)tmax和變量的維數(shù)。

步驟2 初始化灰狼種群，隨機(jī)產(chǎn)生灰狼個(gè)體（在特征柵格地圖中灰狼個(gè)體儲(chǔ)存的節(jié)點(diǎn)為特征柵格），對(duì)每個(gè)灰狼個(gè)體進(jìn)行評(píng)估，看是否滿足約束條件。

步驟3 計(jì)算每個(gè)灰狼個(gè)體的適應(yīng)度，確定當(dāng)前α狼，β狼和δ狼。

步驟4 計(jì)算參數(shù)a、A及C。

步驟5 根據(jù)式（11）更新灰狼個(gè)體。（取整操作）

步驟6 隨機(jī)選取N/4 的灰狼個(gè)體，根據(jù)式（12）和式（13）操作）；

步驟7 計(jì)算3N/2 個(gè)灰狼個(gè)體的適應(yīng)度，選取前N的作為新的種群，更新α狼，β狼和δ狼。

步驟8 是否達(dá)到最大迭代次數(shù)。是，輸出最優(yōu)個(gè)體和最優(yōu)個(gè)體適應(yīng)度值；否，進(jìn)行步驟4。

在實(shí)驗(yàn)環(huán)境相同的情況下，建立20×20 和50×50 的普通柵格地圖，再建立同等大小的特征柵格地圖。分別用GA 算法、PSO 算法、GWO 算法和IGWO算法在不同地圖上進(jìn)行路徑規(guī)劃。其中設(shè)置初始種群N=30，最大迭代次數(shù)tmax=100，GA 算法中交叉概率為0.8，變異概率為0.1；PSO 算法中學(xué)習(xí)因子c1=c2=2，慣性權(quán)值ωini=0.9，ωend=0.4；IGWO 算法中調(diào)節(jié)因子n=600；20×20 的特征柵格地圖中，距離限制D=5，可視步長(zhǎng)L=5；50×50 的特征柵格地圖中，距離限制D=15，可視步長(zhǎng)L=10。

圖7 和圖8 是算法在20×20 和50×50 的柵格地圖及特征柵格地圖的仿真結(jié)果。從圖7a）與圖7b）和圖8a）與圖8b）中可以看出，IGWO 算法的路徑明顯更短，節(jié)點(diǎn)個(gè)數(shù)也更少。從圖7c）與圖7d）和圖8c）與圖8d）中看出，不管是在20×20 簡(jiǎn)單地圖上，還是在50×50 復(fù)雜地圖上，相比其它算法的收斂曲線，IGWO 算法的收斂曲線更優(yōu)。IGWO 算法的曲線下降的更快，說明設(shè)置動(dòng)態(tài)權(quán)重加大優(yōu)秀狼的作用的改進(jìn)是有效的，同時(shí)IWO 算法的曲線沒有出現(xiàn)快速下降后陷入局部最優(yōu)的情況，在迭代后期依然有著折線，說明了游走策略的有效性。

圖7 20×20 路徑規(guī)劃結(jié)果Fig.7 20×20 path planning results

圖8 50×50 路徑規(guī)劃結(jié)果Fig.8 50×50 path planning results

表3 是算法在柵格地圖和特征柵格地圖上，20 次仿真結(jié)果的平均值。從路徑長(zhǎng)度來看，相比于其它算法，IGWO 算法尋優(yōu)的結(jié)果是最好的，節(jié)點(diǎn)個(gè)數(shù)也是最少的。在20×20 的普通柵格地圖上，IGWO算法的路徑長(zhǎng)度，要比GA 算法、PSO 算法和GWO算法優(yōu)化了3.93、2.91 和1.07。在50×50 的普通柵格地圖上IGWO 算法的路徑長(zhǎng)度要比GA 算法、PSO 算法和GWO 算法優(yōu)化了9.94、7.32 和4.19。說明對(duì)GWO 算法的改進(jìn)，有效的改善了GWO 算法在求解路徑規(guī)劃易陷入局部最優(yōu)的問題。

表3 20 次仿真平均結(jié)果Tab.3 Average results from 20 simulations

但是對(duì)比尋優(yōu)時(shí)間，可以明顯看出IGWO 算法的尋優(yōu)時(shí)間較長(zhǎng)，這是因?yàn)橛巫卟呗缘脑O(shè)置，使算法變得復(fù)雜，降低了求解效率。為解決這一問題，建立特征柵格地圖。對(duì)比特殊柵格地圖和普通柵格地圖的結(jié)果，可以明顯看出，IGWO 算法在特征柵格地圖上的尋優(yōu)時(shí)間更短，節(jié)點(diǎn)更少。相比于普通柵格地圖，IGWO 算法在20×20 的特征柵格地圖上尋優(yōu)時(shí)間優(yōu)化了3.04 倍，節(jié)點(diǎn)個(gè)數(shù)減少了3.81；在50×50的特征柵格地圖上尋優(yōu)時(shí)間優(yōu)化了8.12 倍，節(jié)點(diǎn)個(gè)數(shù)少了19.38。說明特征柵格地圖的建立，有效的提高了IGWO 算法求解路徑規(guī)劃問題的效率。

3.3 與其它算法的對(duì)比

由于灰狼優(yōu)化算法較為新穎，目前在二維路徑規(guī)劃上的相關(guān)文獻(xiàn)較少，所以本文選擇對(duì)比文獻(xiàn)[19]改進(jìn)的蟻群算法，來驗(yàn)證本文算法的有效性。蟻群算法的參數(shù)設(shè)置與文獻(xiàn)[19]保持一致。特征柵格地圖中的距離限制D=7，可視步長(zhǎng)L=15。

圖9 所示的是兩種算法在30×30 地圖上的路徑規(guī)劃結(jié)果。實(shí)際數(shù)據(jù)如表4 所示。本文算法對(duì)比文獻(xiàn)[19]算法，路徑的節(jié)點(diǎn)個(gè)數(shù)少了5，尋優(yōu)時(shí)間優(yōu)化了5.328 8 s，并且與障礙物頂點(diǎn)相切的點(diǎn)也減少了一半，極大地增加了路徑規(guī)劃的安全性。但從數(shù)據(jù)中可以發(fā)現(xiàn)最優(yōu)路徑長(zhǎng)度相較于文獻(xiàn)[19]增加了1.227 3，這是路徑與障礙物頂點(diǎn)相切的點(diǎn)減少所導(dǎo)致的。

表4 30×30 地圖實(shí)驗(yàn)結(jié)果對(duì)比Tab.4 Comparison of experimental results on 30×30 maps

圖9 30×30 路徑規(guī)劃結(jié)果Fig.9 30×30 path planning results

4 結(jié)論

提出一種改進(jìn)灰狼優(yōu)化算法在特征柵格地圖上的路徑規(guī)劃方法。引入可調(diào)節(jié)收斂因子n根據(jù)實(shí)際情況調(diào)節(jié)全局搜索和局部搜索的平衡；為加大更新過程中α 狼的比重，引入動(dòng)態(tài)權(quán)重，加快算法的收斂速度，同時(shí)使用游走策略減小因動(dòng)態(tài)權(quán)重策略而導(dǎo)致的局部最優(yōu)的概率；提出建立特征柵格的新方法，利用遠(yuǎn)距離柵格和可視步長(zhǎng)的概念，加快特征特征柵格地圖和鄰接矩陣的建立；通過將特征柵格地圖與改進(jìn)灰狼優(yōu)化算法結(jié)合，提高了灰狼優(yōu)化算法初始種群的質(zhì)量和求解路徑規(guī)劃問題的效率。標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn)證明IGWO 算法相對(duì)于其它算法，不管在收斂速度還是在收斂精度上都有著明顯的優(yōu)勢(shì)，在固定多峰測(cè)試函數(shù)上也有較好的性能；路徑規(guī)劃仿真實(shí)驗(yàn)證明IGWO 算法在求解路徑規(guī)劃問題上能有效的避免局部最優(yōu)；證明特征柵格地圖能有效地提高IGWO 算法求解路徑規(guī)劃問題的效率。