趙 杰， 王馨陽， 王 賀

(黑龍江科技大學 電氣與控制工程學院， 哈爾濱 150022)

0 引 言

自然災害的發(fā)生會造成很大的人員傷亡以及經(jīng)濟損失，為挽救生命財產(chǎn)，提高救援機器人[1]的救援效率，目前，已成為國內(nèi)外機器人控制領域[2]的重點研究方向。因此，使其迅速地抵達受災后地點進行援助，規(guī)劃一個有效、無障礙和最短安全的路徑對提高救援效率是至關重要的[3]。

研究相關機器人路徑規(guī)劃的學者較多，Zanlongo等[4]應用RRT和A*算法設計出由操作員控制多個機器人的方法，但是該方法中算法搜索速度較慢，可能陷入局部最優(yōu)。Rogonondo等[5]應用VFH+算法，給出能探索未知環(huán)境的機器人路徑規(guī)劃的方法，但其存在避障時左右徘徊、閾值敏感及增加搜索時間等缺點。Zafar等[6]結合GWO和APF算法，設計了改進GWO算法，確保在容易出現(xiàn)障礙物的場景中無碰撞優(yōu)化路徑，但所使用的障礙物模型較簡單，不具有普遍性，搜索時間較高。Lu等[7]提出的A*算法，結合圖像處理和激光傳感器，可以在未知環(huán)境下得到所需目標的最短路徑，但需要處理大量的圖像信息，搜索效率低、路徑不平滑等缺點。針對目前救援機器人路徑規(guī)劃研究的現(xiàn)狀，在救援機器人路徑規(guī)劃中采用遺傳算法，對該算法搜索較慢、局部搜索差及不能保證算法收斂，以及用于救援機器人路徑規(guī)劃時，其得到的路徑長度較長，路徑拐點多等問題，筆者提出一系列策略改進遺傳算法，通過仿真實驗驗證改進算法的搜索效率，以提高救援機器人救援能力。

1 柵格法環(huán)境建模

環(huán)境建模是對救援機器人實際的運動過程中所經(jīng)歷的環(huán)境信息的構建，在救援機器人尋優(yōu)路徑時就是要先將環(huán)境信息由實際形式經(jīng)過連續(xù)處理變成為符合路徑尋優(yōu)的虛擬形式，而最為關鍵的是怎么表現(xiàn)障礙物。合理的，有效的建模才可以使尋優(yōu)路徑中的信息量減少，才可以有助于減少時間。各種各樣的路徑規(guī)劃方法是基于不同的建模方法來進行的。

柵格法構建的地圖模型不僅可以直觀有效地表示現(xiàn)實環(huán)境中的信息，而且其是由矩陣數(shù)組表示的，從左到右，從下到上每一個小方格，與遺傳算法的種群個體一樣都是用實數(shù)編碼的，運用遺傳算法在柵格地圖中規(guī)劃路徑，有助于選擇、交叉、變異的操作，因此，文中選擇柵格法建立模型。

為方便計算，將救援機器人看作運動的質點，模型中障礙物已知其位置，并不會改變。構建柵格地圖時，其方格范圍將影響實際信息描述，設備存儲和算法尋優(yōu)搜索時間。文中建模的范圍是 20 m×20 m，對表示障礙物的方格取值1，表示無障礙物方格取值0，并在Matlab仿真軟件中得出如圖1的柵格環(huán)境模型。

圖1 柵格的環(huán)境模型Fig. 1 Grid environment model

由圖1可見，黑色代表障礙物，白色代表可以行走通過[8]。用(x,y)來表示柵格位置，單位為m。起點為(Xs,Ys),終點為(Xe,Ye)，設柵格編號(1,1)為0，(20,20)為399。柵格坐標(x,y)和編號n(n的取值范圍0～399)的關系為

x=mod(n,20)+1，
y=fix(n/20)+1，

式中：mod——取余運算；

fix——取整函數(shù)。

2 遺傳算法的改進

2.1 傳統(tǒng)的遺傳算法

遺傳算法具備較好的全局搜索能力，尤其是在復雜環(huán)境下的優(yōu)化問題中的搜索能力和穩(wěn)定性。應用于救援機器人的路徑規(guī)劃基本思想是：首先將所求函數(shù)的所有解(所有的路徑)視為種群中每一個體，所有個體用實數(shù)編碼，視為基因，然后采用選擇、交叉和變異[9]依次進行尋優(yōu)，進而對種群優(yōu)化，選擇出更適應環(huán)境模型的下一代群體。尋優(yōu)路徑過程中，可以將所有可能的路徑視為種群中的個體，假若群體中總共是n個個體(相當于n條路徑)，另外，每個個體中有m個基因(相當于中間含有地圖方格節(jié)點數(shù)量)，最后通過一代一代的進化，對種群進行三個遺傳算子的操作，選擇出最合適的個體，即最優(yōu)路徑。

2.2 改進的Sine混沌映射初始化種群

遺傳算法，在求解救援機器人的路徑規(guī)劃的問題時，在迭代后期種群的多樣性會減小，容易陷入局部最優(yōu)解當中，導致收斂準確度下降，不能得到最優(yōu)路徑。為提高算法的搜索能力，避免迭代后期種群多樣性減小，考慮到混沌映射中，具有隨機性、遍歷性、規(guī)律性優(yōu)點，而Sine混沌映射與其他混沌映射相比較簡便，保證了更高的隨機性、遍歷性、規(guī)律性和安全性。

傳統(tǒng)的混沌映射中，正弦函數(shù)具有非常重要的地位，而且均與其自身相關。Sine混沌映射是以正弦函數(shù)為基礎的混沌映射[10]。正弦映射是一種動態(tài)的系統(tǒng)[11]，定義為

yn+1=βsin(πyn)，

式中，β——控制參數(shù)，取值范圍0.87～0.93。

一般當β取值在0.95～1時會有混沌現(xiàn)象，但是產(chǎn)生該現(xiàn)象的區(qū)間中有可能會有混沌現(xiàn)象消失的部分，只有當β無限趨于1時，混沌現(xiàn)象才會越好。

Sine混沌映射的構造雖然簡單，但迭代的序列容易被預測到，混沌序列的直方圖如圖2所示。Sine混沌映射在[0, 0.05]和[0.95, 1]的取值概率要遠遠高于其他各區(qū)間的取值概率，呈現(xiàn)出兩頭大中間小，各段的值相差大的現(xiàn)象，分布不均勻，控制參數(shù)β范圍小等缺陷，影響了算法在尋找最優(yōu)路徑的速度和精度。

圖2 Sine混沌序列直方圖Fig. 2 Sine chaotic sequence histogram

文中設計出一種改進型Sine混沌映射為

(1)

式中：mod——取余運算；

rand——生成(0,1)之間的隨機數(shù)；

a——控制參數(shù)。

其混沌序列的直方圖如圖3所示。其用于初始化種群。

圖3 改進型Sine混沌序列直方圖Fig. 3 Improved sine chaotic sequence histogram

由式(1)可得改進型Sine混沌序列，遺傳算法的初始化種群由yn+1經(jīng)式(2)進行線性變換可得：

pi=lb+(ub-lb)yn+1，

(2)

式中：lb——變量空間下界；

ub——變量空間上界。

比較圖2和3可以發(fā)現(xiàn)，改進型的Sine混沌映射在[0,1]間有更好的遍歷性和規(guī)律性，分布更加均勻，而且控制參數(shù)a的取值范圍是任意實數(shù)。改進型Sine混沌映射相對于傳統(tǒng)的Sine混沌映射性能更加優(yōu)秀，用于初始化遺傳算法種群可以使其更加均勻地分布于初始解空間，文中最后用改進型的Sine混沌映射進行遺傳算法種群的初始化。

2.3 適應度函數(shù)的設計

種群個體是否為精英個體取決于適應度函數(shù)值大小，即決定了個體的生存能力。其值高時容易存活，低時就會死亡，因此，可作為判斷個體的優(yōu)劣的標準[12]。在傳統(tǒng)遺傳算法的應用里，通常用路徑長度為適應度函數(shù)，雖然其結構簡單便于計算，但是規(guī)劃的路徑中通常拐點數(shù)量較多，尤其在一些轉彎角度較小的拐點中，容易使救援機器人移動救援過程中造成安全問題，路徑規(guī)劃效率也會大幅降低。

針對傳統(tǒng)路徑長度適應度函數(shù)存在的問題，為更好判斷種群個體的優(yōu)劣，文中提出了一種適用于救援機器人路徑規(guī)劃的適應度安全評價函數(shù)Te，其對遺傳算法尋找最優(yōu)路徑的效率和精度有巨大的影響。Te包含了路徑規(guī)劃中的路徑長度f1和路徑平滑評價度f2，Te函數(shù)為

Te=mf1+nf2，

式中：m——f1權重；

n——f2權重；

(xi,yi)——路徑點i節(jié)點坐標;

(xi+1,yi+1)——路徑點i+1節(jié)點坐標;

M——路徑中節(jié)點的數(shù)量。

由于轉彎的角度不能太大，因此，救援機器人轉彎時應有合適的懲罰權重，降低轉彎概率。文中利用余弦定理、cos函數(shù)及arccos函數(shù)三者依次來判斷轉彎角度及設置相應的轉彎角度及對應的懲罰權重為

b=(xi-xi+1)2+(yi-yi+1)2，

c=(xi+2-xi+1)2+(yi+2-yi+1)2，

a=(xi-xi+2)2+(yi-yi+2)2，

w=arccosA，

Ai=Ai-1+α，91Ai=Ai-1+γ，47Ai=Ai-1+ε，w≤47，

式中：xi+2、yi+2——路徑點i+2節(jié)點坐標;

α、γ、ε——轉彎角度對應的懲罰權重。

α、γ、ε按照柵格環(huán)境模型中的黑色和白色柵格的數(shù)量和位置來取值。當模型范圍較大或黑色柵格較多，分布復雜時，應當選取較大的值，區(qū)分出種群個體中的高、低適應度值的個體來。權重m、n根據(jù)模型的復雜程度和路徑實際特點進行取值，為下一步進行一系列遺傳操作奠定基礎。

為驗證文中所提出的適應度安全評價函數(shù)Te的優(yōu)越性，對遺傳算法分別以傳統(tǒng)路徑長度為適應度函數(shù)和以安全評價函數(shù)Te為適應度函數(shù)，進行兩組仿真實驗。算法的主要參數(shù)設定為：種群數(shù)量200，pc=0.9，pm=0.2，α=3，γ=15，ε=20，最大迭代次數(shù)Mg=70。從兩組仿真實驗得出，以傳統(tǒng)適應度函數(shù)的路徑中轉彎的平均次數(shù)是17次，以Te為適應度函數(shù)的路徑中轉彎平均次數(shù)是12次。

由傳統(tǒng)適應度函數(shù)的路徑圖4和以Te為適應度函數(shù)的路徑圖5中可以看出，以Te為適應度函數(shù)的路徑更光滑平穩(wěn)，路徑轉折次數(shù)大為減少。因此，文中所采用的安全評價函數(shù)Te作為適應度函數(shù)減小了轉彎的概率，提高了救援機器人移動路徑的平滑程度，平均提高了29.41%，增加了救援工作的安全效率。

圖4 傳統(tǒng)適應度函數(shù)的路徑Fig. 4 Path of traditional fitness function

圖5 Te為適應度函數(shù)的路徑Fig. 5 Path with Te as fitness function

2.4 遺傳的自適應選擇操作

蟻群算法基本原理：在初始種群隨機走過路徑的概率是相同的，通過在走過的路徑上分泌信息素的方式，另外并將信息反饋給種群。其在路徑上越多，其他個體走這個路徑的可能性越大，而該算法的種群是在未給予任何信息的情況下找到一條從初始節(jié)點到最終節(jié)點之間最短路徑[13]，而信息素最多的路徑就是最短路徑。

應用改進Sine混沌映射進行遺傳算法種群的初始化后，選擇個體時，高適應度的路徑有未被選中的可能性。因此，為降低此類情況發(fā)生的概率，文中根據(jù)蟻群算法的原理和輪盤賭算法，得出文中改進算法自適應選擇操作：首先，文中設計一個自適應選擇算子因子Pi，如式(3)所示，其次，按照自適應選擇算子因子Pi將路徑(種群個體)分為高適應度路徑(精英個體)、 低適應度路徑(非精英個體)，從低到高排序，然后，通過rand隨機數(shù)判斷選擇哪條路徑時，會降低選擇低適應度路徑的可能性，增加選擇高適應度路徑的可能性。路徑適應度值越大，選擇該路徑的可能性就越大。

(3)

式中：Tei——第i代路徑的適應度；

Mg——最大迭代次數(shù)；

η——適應度重要程度因子。

η的Sigmoid激活函數(shù)為

雖然該方法能快速選擇種群適應度較高的個體，提高算法收斂速度，但其會降低種群的多樣性，可得到局部較短路徑。因此，文中通過非線性交叉操作和線性變異操作防止陷入局部最優(yōu)，使種群維持較高的適應度，不會降低種群的多樣性，并向更好更優(yōu)的方向進化。

2.5 非線性交叉與線性變異操作

交叉操作選用單點交叉[14]。其是指如果搜索到的路徑中，有兩個路徑(兩個種群個體)存在相同的節(jié)點或多個相同的節(jié)點，則根據(jù)交叉概率pc判斷是否將這兩個路徑作為父代執(zhí)行交叉操作；若進行交叉(隨機選擇相同的節(jié)點進行)，則交叉后留下較短的路徑。在進行交叉操作后，下一代個體的適應度可能大于父代的，從而尋找最優(yōu)路徑。

變異操作在尋優(yōu)過程中將已知的上一代個體以變異概率pm在某一節(jié)點隨機性向各方向臨近節(jié)點進行突變，其有可能會出現(xiàn)變異之前路徑無障礙物，變異之后路徑有障礙物，增加了障礙路徑產(chǎn)生的概率。為解決這問題，文中采取的方法是，在某一路徑進行變異操作后，判斷變異后是否為障礙路徑，若是則刪除這條路徑，取消變異操作；若不是則保留。例如，在圖6中，假設路徑為[1 6 11 12 16]，隨機突變在6號柵格；那么突變的可能性就如圖6中的箭頭所示，當突變后的路徑有5號柵格，就刪除這條路徑，取消變異操作。

圖6 變異操作Fig. 6 Mutation operation

改進遺傳算法的流程如圖7所示。經(jīng)典遺傳算法的pc和pm一般是固定不變的，但是這容易增加破壞適應度高的路徑概率，降低種群的多樣性，對種群的產(chǎn)生有害進化。因此，引入SoftSign激活函數(shù)的導數(shù)設計出了非線性交叉操作，公式為

圖7 改進遺傳算法的流程Fig. 7 Improved genetic algorithm process

式中：pcmax——交叉概率上限；

pcmin——交叉概率下限；

i——當前迭代次數(shù)。

結合非線性交叉操作可能得到適應度更高的下一代個體(路徑)，但有可能在迭代后期降低種群的多樣性。而在變異操作中，假如pm較小，則會有路徑不突變的可能性，且降低種群的多樣性，算法的搜索能力減小，但pm不能太大，否則突變的路徑變多。雖然極大增加了種群的多樣性，但不利于全局搜索；因此，文中在非線性交叉操作之后，又設計出了線性變異操作如式(4)，能使算法盡可能較多地尋找到個體(路徑)，有利于其逃離局部最優(yōu)解，提高迭代后期的種群的多樣性。

(4)

式中：pmmin——變異概率下限；

pmmax——變異概率上限；

p1、p2——變異概率的因子。

3 仿真結果與對比分析

為驗證所提出的理論和改進的遺傳算法，在Matlab仿真軟件下進行實驗。分別對遺傳算法、改進的算法和蟻群算法，在簡單地圖和復雜地圖中，并改變起點和終點的坐標，進行2組仿真對比。

文中算法的主要參數(shù)設定為：種群數(shù)量200，a=64，lb=-100，ub=100，m=n=1，α=3，γ=15，ε=20，pc_max=0.9，pc_min=0.3，pm_max=0.8，pm_min=0.2，最大迭代次數(shù)Mg=70。

經(jīng)典遺傳算法的種群數(shù)量，最大迭代次數(shù)與文中算法的一致，而pc和pm的取值分別為0.9和0.2。為便于比較兩個算法，在兩個算法中均以Te為適應度函數(shù)。極大提高了救援機器人的救援能力和在復雜地圖中搜索效率的有效性。為進一步驗證改進的遺傳算法，與蟻群算法救援機器人路徑規(guī)劃進行對比。第一組仿真實驗，簡單地圖的障礙物覆蓋率為21%。

由仿真實驗結果圖8和9，以及表1的對比數(shù)據(jù)可得，改進的遺傳算法與經(jīng)典遺傳算法相比，最優(yōu)路徑長度平均減小了5.24%，收斂速度提高了30.00%，搜索時間平均減少了3.54%；與蟻群算法相比，雖然兩者的最優(yōu)路徑長度相差不大，但前者搜索效率更高，收斂速度提高了46.15%，搜索時間平均減少了88.50%，文中算法極大提高了救援機器人的救援能力和在復雜地圖中搜索效率的有效性。

圖8 簡單地圖中三個算法的路徑規(guī)劃Fig. 8 Path planning of three algorithms in simple map

表1 簡單地圖中算法仿真結果Table 1 Simulation results of algorithm in simple map

圖9 簡單地圖中三個算法的路徑收斂曲線Fig. 9 Path convergence curves of three algorithms in simple map

為更一步的證明文中算法的優(yōu)越性，在更復雜的地圖中進行仿真實驗。仿真結果如圖10和11所示。第二組仿真實驗，復雜地圖的障礙物覆蓋率為28%，并改變起點和終點的坐標。

圖10 復雜地圖中三個算法的路徑規(guī)劃 Fig. 10 Path planning of three algorithms in complex map

圖11 復雜地圖中三個算法的路徑收斂曲線Fig. 11 Path convergence curves of three algorithms in complex map

根據(jù)仿真實驗圖10和11，以及表2的對比數(shù)據(jù)可得，在復雜地圖中改進的遺傳算法與經(jīng)典遺傳算法相比，最優(yōu)路徑長度平均減小了2.16%，收斂速度提高了27.08%，搜索時間平均減少了4.01%；與蟻群算法相比，收斂速度提高了37.50%，搜索時間平均減少了91.67%，在更復雜地圖中，雖然兩者的最優(yōu)路徑長度相差不大，但平均搜索時間減小幅度比在簡單地圖中更大，這證明了文中改進遺傳算法在更復雜，更困難的環(huán)境中縮短在救援時間上的優(yōu)越性。

表2 復雜地圖中算法仿真結果Table 2 Simulation results of algorithm in complex map

4 結 論

(1)為了使救援機器人更好快速地到達救災現(xiàn)場進行救援，文中提出了改進的Sine混沌映射、自適應選擇、非線性交叉與線性變異操作，設計了帶有懲罰權重的適應度安全評價函數(shù)Te，增加了機器人路徑的平滑程度策略改進了遺傳算法。解決了算法在尋優(yōu)中存在種群多樣性低，易選擇低適應度的路徑，陷入局部最優(yōu)，且在迭代后期尋優(yōu)速率慢等問題。

(2)通過改進遺傳算法分別與經(jīng)典的遺傳算法和蟻群算法的仿真實驗對比，在兩種地圖中與蟻群算法相比，救援時間分別減少了88.50%，91.67%，證明了文中改進遺傳算法更適用于復雜、困難的環(huán)境中。