劉相旭，張永剛

(安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232001)

0 引言

路徑規(guī)劃技術(shù)[1]是指在滿足所有約束條件下，在有障礙物的環(huán)境中尋找到一條從起點(diǎn)到終點(diǎn)的最優(yōu)或次優(yōu)、安全、無(wú)碰撞的路徑。對(duì)于路徑規(guī)劃理論，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究，提出了許多算法，如智能仿生算法蟻群算法[2]、粒子群算法[3]、遺傳算法[4]等，還有其他類型的算法，如A*算法[5]、RRT算法[6]、人工勢(shì)場(chǎng)法[7]等。蟻群算法具有較強(qiáng)的魯棒性和搜索能力，但易陷入局部最優(yōu)，AJEIL等[8]提出老化蟻群算法，由路徑長(zhǎng)度決定信息素常量大小，提高算法效率；遺傳算法的全局搜索能力較強(qiáng)但收斂較慢，HAO等[9]將種群分成若干個(gè)小種群，用種群間的遷移取代了選擇機(jī)制，同時(shí)改進(jìn)了交叉變異算子，使其適用各種模式的地圖。

單一算法存在各種問(wèn)題，針對(duì)其缺點(diǎn)進(jìn)行優(yōu)化能有效提高路徑搜索效率，但仍無(wú)法滿足實(shí)際需求，于是學(xué)者們將單個(gè)算法與其它算法相互融合來(lái)提高算法的性能，如DAI等[10]將A*算法與蟻群算法啟發(fā)函數(shù)結(jié)合提出彎曲抑制算子，加快算法收斂性；SHI等[11]將遺傳算法與蟻群算法融合，改進(jìn)路徑評(píng)價(jià)標(biāo)準(zhǔn)。

針對(duì)蟻群算法搜索易陷入局部最優(yōu)問(wèn)題，改進(jìn)啟發(fā)式函數(shù)，自適應(yīng)調(diào)整揮發(fā)因子，利用A*算法提出回溯策略優(yōu)化死鎖問(wèn)題，提高搜索效率；針對(duì)遺傳算法收斂慢、轉(zhuǎn)彎多問(wèn)題，改進(jìn)遺傳算法的種群生成方式，提出通信機(jī)制交叉，調(diào)整適應(yīng)度函數(shù)和交叉變異因子；針對(duì)傳統(tǒng)融合算法收斂較慢的問(wèn)題，將優(yōu)化蟻群算法得出的次優(yōu)解引入遺傳算法優(yōu)化后的種群中，得到改進(jìn)的融合算法來(lái)優(yōu)化路徑。

1 環(huán)境建模

路徑地圖采用柵格法進(jìn)行環(huán)境建模，將工作環(huán)境分為N×N網(wǎng)格。對(duì)處于環(huán)境中的障礙物進(jìn)行膨化處理，該柵格只要被障礙物所觸及，就視為障礙物。地圖柵格以左下角為起點(diǎn)，右上角為終點(diǎn)。自由區(qū)域?yàn)榘咨珫鸥瘢勺杂赏ㄐ?；障礙區(qū)域?yàn)楹谏珫鸥?，無(wú)法通行。為便于計(jì)算，將智能車輛視為質(zhì)點(diǎn)，可在自由區(qū)域的柵格中心連線之間移動(dòng)。網(wǎng)格坐標(biāo)可表示為：

x=mod(i，n)+1

y=fix(i/n)+1

(1)

式中：mod為取余運(yùn)算，fix為取整函數(shù)，i為當(dāng)前柵格的序列數(shù)，n為柵格的行數(shù)和列數(shù)。

2 改進(jìn)蟻群和遺傳算法

2.1 傳統(tǒng)蟻群算法

蟻群算法是模擬自然界螞蟻利用信息素探索路徑的行為，螞蟻在探索路徑時(shí)會(huì)分泌信息素，較短的路徑上留下的信息素濃度較高，螞蟻會(huì)選擇信息素濃度較高的路徑，該路徑上分泌的信息素濃度持續(xù)增加，由此形成了正反饋。蟻群算法的兩個(gè)關(guān)鍵因素為路徑選擇和信息素更新。螞蟻根據(jù)路徑上信息素濃度和距離啟發(fā)函數(shù)來(lái)搜索路徑，螞蟻k在t時(shí)刻選擇下一點(diǎn)的概率

(2)

式中：α、β為信息素和距離啟發(fā)因子；allowedk為下一步可選擇的路徑點(diǎn)集合；τij為路徑上信息素濃度；ηij為距離啟發(fā)函數(shù)，ηij(t)=1/dij。

螞蟻在搜索路徑時(shí)會(huì)留下信息素，同時(shí)信息素根據(jù)揮發(fā)因子進(jìn)行揮發(fā)，當(dāng)所有螞蟻?zhàn)咄曷窂綍r(shí)，算法進(jìn)行迭代由公式(3)～(5)更新路徑上的信息素含量：

τij(t+1)=(1-ρ)τij+Δτij(t)，

(3)

(4)

(5)

式中：ρ為信息素?fù)]發(fā)因子，τij(t)為螞蟻在本次搜索路徑中增加的信息素濃度，Q為信息素常量，Lk為路徑的長(zhǎng)度。

2.2 改進(jìn)蟻群算法

針對(duì)蟻群算法易陷入局部最優(yōu)及收斂差的問(wèn)題進(jìn)行改進(jìn)。

2.2.1 改進(jìn)距離啟發(fā)函數(shù)

傳統(tǒng)距離啟發(fā)函數(shù)在搜索中存在搜索效率和尋優(yōu)能力不足的問(wèn)題，改進(jìn)方法是在距離啟發(fā)函數(shù)中加入對(duì)目的點(diǎn)的引導(dǎo)作用，增加搜索的目的性，有助于跳出局部最優(yōu)解。新的公式

(6)

式中：dij為當(dāng)前點(diǎn)i到下一可行點(diǎn)j的距離，die為當(dāng)前點(diǎn)i到終點(diǎn)的距離，dje為下一可行點(diǎn)j到終點(diǎn)的距離。

2.2.2 結(jié)合A*算法的回溯策略優(yōu)化死鎖問(wèn)題

蟻群算法在搜索過(guò)程中存在螞蟻?zhàn)呷胨篮那闆r即死鎖問(wèn)題，該路徑作廢且影響算法搜索效率，針對(duì)該問(wèn)題結(jié)合A*算法提出回溯策略。

當(dāng)出現(xiàn)死鎖時(shí)，由死鎖點(diǎn)向前回溯至起點(diǎn)找出所有走過(guò)的點(diǎn)并組成集合，由A*算法找出路徑點(diǎn)集合中到終點(diǎn)代價(jià)最小的點(diǎn)，回溯至代價(jià)最小點(diǎn)繼續(xù)搜索。若螞蟻在單次路徑搜索中觸發(fā)2次以上回溯策略時(shí)，則令路徑無(wú)效，由下只螞蟻進(jìn)行搜索。A*算法公式為：

f(n)=g(n)+h(n)，

(7)

式中：g(n)為實(shí)際代價(jià)指當(dāng)前點(diǎn)到下一點(diǎn)的距離，h(n)為估計(jì)代價(jià)指下一點(diǎn)到終點(diǎn)的距離。

在其他條件相同時(shí)針對(duì)死鎖問(wèn)題進(jìn)行無(wú)死鎖改進(jìn)，回退策略(回退一格搜索)和融合A*算法的回溯策略進(jìn)行仿真試驗(yàn)，結(jié)果如圖1所示，回溯策略能在算法前期保證螞蟻數(shù)量較多，提高搜索效率。

圖1 有效螞蟻數(shù)量對(duì)比圖

2.2.3 調(diào)整自適應(yīng)揮發(fā)因子

揮發(fā)因子固定導(dǎo)致路徑上信息素分布不均，影響螞蟻尋優(yōu)效率。改進(jìn)的自適應(yīng)改進(jìn)揮發(fā)因子

(8)

式中：T為蟻群算法的總迭代次數(shù)，t為算法當(dāng)前的迭代次數(shù)，ρmin為揮發(fā)因子最小值。

算法初期，揮發(fā)因子較大使得螞蟻全局搜索能力提高，此時(shí)信息素濃度對(duì)螞蟻的引導(dǎo)作用較弱，蟻群可以搜尋更多的路徑；但隨著迭代次數(shù)增加，揮發(fā)因子逐漸減小，負(fù)反饋減弱，路徑上信息素濃度提高，濃度對(duì)于螞蟻的引導(dǎo)作用加強(qiáng)，螞蟻會(huì)集中于濃度較大的路徑上。

改進(jìn)的蟻群算法在搜索能力上有一定的增強(qiáng)，不易陷入局部最優(yōu)。但引入自適應(yīng)揮發(fā)因子后，揮發(fā)因子隨著迭代增加由大變小，在算法后期較短路徑上的信息素濃度會(huì)過(guò)大，導(dǎo)致螞蟻集中于這些路徑上，而最短路徑可能會(huì)出現(xiàn)沒(méi)有螞蟻?zhàn)哌^(guò)的情況，該路徑上濃度較低，致使改進(jìn)的蟻群算法得到了一條次優(yōu)解。

2.3 傳統(tǒng)遺傳算法

遺傳算法將函數(shù)的解(路徑)視為種群中的個(gè)體，通過(guò)隨機(jī)方式生成初始種群，每一個(gè)個(gè)體以實(shí)數(shù)編碼，視為基因，用于選擇、交叉、變異進(jìn)行逐步尋優(yōu)。算法中將單一路徑視為個(gè)體，路徑組成部分視為基因。

種群生成模式為在路徑的每一行中隨機(jī)選擇一點(diǎn)，判斷是否連續(xù)，不連續(xù)采用平均值法插入一點(diǎn)，然后依次組成連續(xù)路徑；選擇操作結(jié)合適應(yīng)度函數(shù)進(jìn)行選擇，適應(yīng)度較高個(gè)體保留概率越高；交叉模式為在兩個(gè)個(gè)體中選出某一相同位置后交換其余部分；變異操作為隨機(jī)選擇個(gè)體中的2點(diǎn)重新組成新的路徑片段。

2.4 改進(jìn)遺傳算法

算法生出的初始種群適應(yīng)度較小，前期搜索效率較低，固定交叉變異因子在中后期影響算法的尋優(yōu)能力，針對(duì)這些問(wèn)題進(jìn)行改進(jìn)。

2.4.1 改進(jìn)初始種群生成

傳統(tǒng)種群生成模式得出的路徑過(guò)長(zhǎng)，前期搜索效率較低，改進(jìn)后的生成方式為：采用鄰接矩陣的形式建立所有自由柵格點(diǎn)的下一步可走點(diǎn)集合，由起始點(diǎn)開(kāi)始選出下一步可走點(diǎn)集合，分別計(jì)算終點(diǎn)坐標(biāo)減去當(dāng)前點(diǎn)i坐標(biāo)的數(shù)值n1，可選點(diǎn)集合中的坐標(biāo)到當(dāng)前點(diǎn)i坐標(biāo)的數(shù)值n2；結(jié)合反余弦函數(shù)計(jì)算n1、n2的內(nèi)積與n1、n2范數(shù)之積，得出當(dāng)前點(diǎn)到每一可走點(diǎn)的概率，采用輪盤(pán)賭法選出下一步的點(diǎn)，由此重復(fù)直至得到完整的路徑。

采用改進(jìn)的初始種群生成可有效降低單一個(gè)體(路徑)的冗余部分，提高了個(gè)體的適應(yīng)度，加快了算法的收斂。

2.4.2 改進(jìn)適應(yīng)度函數(shù)

適應(yīng)度決定個(gè)體適應(yīng)能力的大小，適應(yīng)度較高的個(gè)體更易生存，反之更易淘汰。傳統(tǒng)適應(yīng)度函數(shù)僅由路徑長(zhǎng)度組成，與實(shí)際情況不相符，車輛在路徑規(guī)劃中通過(guò)轉(zhuǎn)彎躲避障礙物，轉(zhuǎn)彎角度不同，能量損耗也不同。改進(jìn)的適應(yīng)度函數(shù)集合長(zhǎng)度因子、能耗因子、安全因子三部分共同組成：

fit=a×fit1+b×fit2+c×fit3，

(9)

2.4.3 改進(jìn)交叉模式及交叉變異因子

提出一種基于通信機(jī)制的交叉模式：選出兩個(gè)個(gè)體，并找出兩個(gè)個(gè)體中所有相同的部分，建立集合C；從集合C中依次取出連續(xù)的兩個(gè)元素如Ci與Ci-1或Ci與Ci+1，將兩點(diǎn)返回原先個(gè)體中得出路徑片段S1和S2；計(jì)算S1和S2的路徑片段長(zhǎng)度，選擇長(zhǎng)度片段較短的一方，依次組成一條完整的路徑；判斷得出的新路徑與父輩個(gè)體是否相同，若不相同，則另一新路徑為父輩適應(yīng)度較大的一方，若相同，則采用父輩的兩個(gè)個(gè)體。改進(jìn)的交叉模式能將優(yōu)秀的路徑片段集中于單個(gè)個(gè)體中，能有效提高算法的收斂速度。

傳統(tǒng)算法的交叉與變異概率為固定值，對(duì)交叉來(lái)說(shuō)，概率越大，適應(yīng)度較高的個(gè)體被破壞的幾率會(huì)增加；概率較小，算法的搜索速度會(huì)減慢。對(duì)變異來(lái)說(shuō)，概率較小，算法跳出局部最優(yōu)的能力變差；概率較大，可能會(huì)破壞較優(yōu)解。改進(jìn)后的自適應(yīng)概率

(10)

(11)

式中：T為總迭代次數(shù)，t為當(dāng)前的迭代次數(shù)，Pm為變異因子的最大值。隨著迭代次數(shù)的增加，Pc由大變小，Pm由小變大。Pc在前期較大易于搜索較優(yōu)解，在中后期減小使較優(yōu)解不易被破壞，Pm在前期較小不易破壞較優(yōu)解，在中后期易于讓個(gè)體跳出局部最優(yōu)。

3 融合算法的改進(jìn)

3.1 加入剪枝優(yōu)化算子和刪除算子

針對(duì)遺傳初始種群個(gè)體出現(xiàn)局部繞路的情況，采用剪枝優(yōu)化算子來(lái)進(jìn)行優(yōu)化，步驟如下：在當(dāng)前路徑上初始化一條新路徑，設(shè)i為個(gè)體的起點(diǎn)，并將i放入新路徑中；定義j為個(gè)體的終點(diǎn)，并判斷j是否為i的相鄰節(jié)點(diǎn)，若不是，則j沿著路徑向前回溯一點(diǎn)并繼續(xù)判定，若是，則令i=j，將新的i放入新路徑中，j回到終點(diǎn)重新判定；當(dāng)i為原路徑終點(diǎn)時(shí)，優(yōu)化結(jié)束，輸出新路徑。

融合算法結(jié)束后采用刪除算子對(duì)路徑進(jìn)行優(yōu)化。針對(duì)路徑的轉(zhuǎn)折點(diǎn)進(jìn)行判定，若移去該點(diǎn)后仍為可行路徑則進(jìn)行移除，同時(shí)保證新路徑的轉(zhuǎn)折點(diǎn)少于原路徑。該優(yōu)化是在保證轉(zhuǎn)折點(diǎn)不增加的同時(shí)盡可能優(yōu)化現(xiàn)有路徑。

3.2 算法融合

蟻群優(yōu)化算法搜索能力得到提升，但自適應(yīng)揮發(fā)因子隨著迭代次數(shù)增加而減少，在相對(duì)較短的路徑上信息素積累較多，導(dǎo)致螞蟻搜索最優(yōu)路徑的概率減少，算法最終得到次優(yōu)解。傳統(tǒng)的蟻群與遺傳算法融合方式為：遺傳算法得出路徑后交由蟻群算法進(jìn)行初始信息素的鋪設(shè)，之后進(jìn)行路徑搜索，但算法在遺傳階段的種群多樣性下降較快，影響融合算法搜索效率。

針對(duì)該問(wèn)題提出改進(jìn)融合算法：將蟻群優(yōu)化算法得出的次優(yōu)解加入到遺傳算法優(yōu)化后的種群中，形成新種群；新種群的篩選采用精英保留策略(保留適應(yīng)度前50%的個(gè)體)，后續(xù)采用通信和傳統(tǒng)交叉共同作用的模式、精英保留策略及自適應(yīng)變異優(yōu)化種群直至算法結(jié)束；最后利用刪除算子優(yōu)化最終解。通過(guò)這一過(guò)程得到了改進(jìn)融合算法，改進(jìn)融合算法流程圖如圖2所示。其中用于通信交叉的個(gè)體為總個(gè)體的40%，傳統(tǒng)交叉為總個(gè)體的60%。

圖2 融合算法流程圖

4 仿真試驗(yàn)對(duì)比

將改進(jìn)融合算法(ant colony&a* and backtracking genetic fusion algorithm，A*ACO-BGA)與遺傳算法(genetic algorithm，GA)、傳統(tǒng)融合算法(genetic and ant colony fusion algorithm，GA-ACO)和文獻(xiàn)[11]算法(improved ant colony and genetic fusion algorithm，IACO-GA)在MATLAB軟件下進(jìn)行仿真對(duì)比，分別在20×20的簡(jiǎn)單(障礙物占比少)和復(fù)雜(障礙物占比多)地圖中進(jìn)行測(cè)試，每種地圖進(jìn)行20次仿真試驗(yàn)，取一組結(jié)果進(jìn)行比較。蟻群和遺傳算法參數(shù)如表1所示。

表1 蟻群與遺傳算法參數(shù)

4.1 簡(jiǎn)單環(huán)境下仿真對(duì)比

4種算法在20×20的簡(jiǎn)單環(huán)境中輸出路徑如圖3所示，遺傳算法經(jīng)16次轉(zhuǎn)彎到達(dá)終點(diǎn)，傳統(tǒng)混合算法經(jīng)11次轉(zhuǎn)彎到達(dá)終點(diǎn)，IACO-GA算法和改進(jìn)融合算法路徑重合經(jīng)2次轉(zhuǎn)彎后到達(dá)終點(diǎn)，能耗有所降低。

圖3 簡(jiǎn)單地圖四種算法路徑對(duì)比

從圖4可看出，4種算法分別在28、19、13和11次迭代后得到長(zhǎng)度31.80、30.97、30.97和30.97的最優(yōu)路徑。

圖4 簡(jiǎn)單地圖四種算法迭代對(duì)比

20次試驗(yàn)結(jié)果見(jiàn)表2，IACO-GA算法和改進(jìn)融合算法搜索到的路徑較優(yōu)，轉(zhuǎn)彎次數(shù)較少。與遺傳算法和傳統(tǒng)混合算法相比，在迭代次數(shù)上減少約70%和57%；轉(zhuǎn)彎次數(shù)減少約84%和75%。與IACO-GA算法相比轉(zhuǎn)彎次數(shù)無(wú)明顯波動(dòng)但迭代次數(shù)減少36%。改進(jìn)融合算法在簡(jiǎn)單地圖中對(duì)比遺傳算法和傳統(tǒng)混合算法在收斂速度和能耗上有著一定的優(yōu)勢(shì)，對(duì)比IACO-GA算法，在得到最優(yōu)路徑的同時(shí)，收斂速度有所增加。

表2 簡(jiǎn)單柵格四種算法迭代數(shù)據(jù)總結(jié)

4.2 復(fù)雜環(huán)境下仿真對(duì)比

在復(fù)雜地圖中再次進(jìn)行仿真試驗(yàn)，參數(shù)與簡(jiǎn)單地圖相同，路徑規(guī)劃如圖5所示。由圖5可知遺傳算法經(jīng)16次轉(zhuǎn)彎后到達(dá)終點(diǎn)，能耗較高；傳統(tǒng)融合算法經(jīng)9次轉(zhuǎn)彎到達(dá)終點(diǎn)；IACO-GA算法經(jīng)11次轉(zhuǎn)彎到達(dá)終點(diǎn)；改進(jìn)融合算法得到路徑相對(duì)平滑且轉(zhuǎn)彎次數(shù)較少，有8次轉(zhuǎn)彎。

圖5 復(fù)雜地圖四種算法路徑對(duì)比

從圖6可看出，4種算法分別在42、30、11、9次迭代后搜索到最優(yōu)路徑且路徑長(zhǎng)度分別為34.97、32.38、32.14、31.20。改進(jìn)算法能搜索到轉(zhuǎn)彎次數(shù)較少，路徑較優(yōu)且收斂較快的路徑。

20次試驗(yàn)結(jié)果見(jiàn)表3，障礙物的增加使得傳統(tǒng)算法在尋路過(guò)程中可走路線減少，收斂較慢。改進(jìn)融合算法相較于遺傳算法，傳統(tǒng)融合算法和IACO-GA算法的迭代次數(shù)減少約80%，70%和38%，轉(zhuǎn)彎次數(shù)減少約43%、18%和19%。

表3 復(fù)雜地圖四種算法迭代數(shù)據(jù)總結(jié)

從表2、3可看出，在簡(jiǎn)單和復(fù)雜地圖中相較于其余3種算法，改進(jìn)融合算法在收斂速度上有著一定的優(yōu)勢(shì)，且輸出路徑較優(yōu)，轉(zhuǎn)彎次數(shù)減少，可有效降低能耗，有著更好的路徑規(guī)劃能力。

5 結(jié)論

針對(duì)傳統(tǒng)融合算法存在收斂慢、轉(zhuǎn)彎多的問(wèn)題提出了一種改進(jìn)的融合算法，并進(jìn)行了仿真驗(yàn)證。將優(yōu)化蟻群算法得出的次優(yōu)解加入遺傳算法優(yōu)化后的種群中，通過(guò)精英策略，通信機(jī)制交叉和傳統(tǒng)交叉相結(jié)合的模式來(lái)搜索路徑。改進(jìn)的融合算法解決了傳統(tǒng)融合算法轉(zhuǎn)彎次數(shù)多、路徑不平滑的問(wèn)題，通過(guò)仿真驗(yàn)證可以看出，在簡(jiǎn)單和復(fù)雜地圖中改進(jìn)后的融合算法能搜索到路徑更短、能耗更低的路徑，對(duì)比傳統(tǒng)融合算法在收斂速度和搜索效率上有著一定的優(yōu)勢(shì)。