融合遺傳算法與蟻群算法的機器人路徑規(guī)劃

虞馥澤，潘大志,2

(1.西華師范大學 數(shù)學與信息學院，四川 南充 637009；2.西華師范大學 計算方法與應用研究所，四川 南充 637009)

0 引 言

路徑規(guī)劃是指在有障礙物的環(huán)境中，依據(jù)一些標準搜索一條由起點到目標點的安全無碰撞路徑。常用路徑規(guī)劃算法大致可分為：傳統(tǒng)算法、圖形學法、智能仿生學法及其他算法。傳統(tǒng)算法有人工勢場法[1]、模糊控制算法[2]等。圖形學法有C空間法[3]、柵格法[4]等。智能仿生學算法有模擬退火算法[5]、蟻群算法[6]、粒子群算法[7]、遺傳算法[8]等。

蟻群算法是Marco Dorigo受螞蟻覓食啟發(fā)，于1992年提出的一種仿生算法[9]。為解決蟻群算法在路徑規(guī)劃上的不足，研究人員提出了對它的各種改進。牛龍輝等[10]提出的一種自適應蟻群算法，引入自適應信息素揮發(fā)系數(shù)，能較好地提高算法收斂速度，但是對于路徑平滑性的改進不夠；胡春陽等[11]利用頭尾搜索機制以及遺傳算法對改進后的蟻群算法進行參數(shù)優(yōu)化、引入獎懲因子以及多指標適應度函數(shù)，對避免局部最優(yōu)和收斂速度方面有很大改進；甄然等[12]提出的自適應多態(tài)融合蟻群策略，在多態(tài)蟻群算法的基礎上，引入自適應并行規(guī)則和偽隨機規(guī)則，以提高算法全局尋優(yōu)能力；趙靜等[13]通過改進啟發(fā)函數(shù)和信息素揮發(fā)因子以提升其全局搜尋能力；韓顏等[14]是根據(jù)粒子群算法最優(yōu)解調(diào)整路徑上初始信息素分布，解決蟻群算法中初始信息素缺乏的問題，并且利用簡化操作優(yōu)化路徑，優(yōu)化后的路徑距離短且相對平滑，但是對于局部路徑平滑性的改進依舊不足。趙開新等[15]提出將遺傳算法與蟻群算法相結(jié)合，利用遺傳算法得到的較優(yōu)個體設置蟻群的初始信息素，在蟻群算法更新全局最優(yōu)中，將當前最優(yōu)與全局最優(yōu)路徑通過交叉操作，更新當前最優(yōu)，進而更新全局最優(yōu)。

對靜態(tài)全局環(huán)境下求解路徑的規(guī)劃方法做出改進，提高算法的路徑規(guī)劃能力，是該文的研究目的。通過對兩種智能仿生算法進行分析，將遺傳算法及蟻群算法融合求解路徑規(guī)劃，利用遺傳算法得到的較優(yōu)路徑，來設置蟻群算法所需的初始信息素，引導蟻群算法進一步尋優(yōu)，最終得到全局最優(yōu)。

1 環(huán)境建模

進行路徑規(guī)劃之前先建立環(huán)境地圖，該文采用柵格法建立移動機器人的行走環(huán)境模型。將機器人處理為質(zhì)點，行走空間為二維空間，障礙物的大小、位置已知。

如圖1以4×4的柵格矩陣為例，map表示柵格環(huán)境矩陣，可行區(qū)域為白色，即map(i,j)=0；禁行區(qū)域為黑色，即map(i,j)=1。從左上角到右下角、從左到右、從上往下對柵格編號，依次為{1,2,…,16}。

圖1 柵格矩陣及柵格地圖

在環(huán)境模型中，每個柵格均與二維空間中的一個坐標(x,y)相對應。如圖1所示，柵格1對應坐標(0.5,3.5)、柵格2對應坐標(1.5,3.5)，以此類推，利用式(1)、(2)可將柵格序號轉(zhuǎn)化為對應坐標。

(1)

(2)

其中，N、M分別是柵格環(huán)境矩陣的行數(shù)、列數(shù)，index為柵格序號。

2 遺傳算法

2.1 染色體編碼

柵格序號形式簡單，易于遺傳操作，故采用柵格序號對染色體進行編碼。P={p1,p2,…,pn}表示一條路徑，其中pi(i=1,2,…,n)為路徑上第i個節(jié)點的柵格序號，p1、pn分別為起止柵格序號。

2.2 適應度函數(shù)及選擇策略

由于在生物遺傳進化過程中，適應度較高的個體遺傳到下一代的概率較大，反之則較小。故該文將適應度函數(shù)設定為機器人從起點到終點所經(jīng)歷的路徑長度的倒數(shù)。

采用輪盤賭的方式選擇出下一代個體，確保部分非最優(yōu)的個體進入下一代，有效地避免算法陷入局部最優(yōu)。

2.3 交叉策略

采用單點交叉，具體過程為：先找出兩父代個體中除去起止點外所有相同的點構(gòu)成集合I，若I非空，則隨機選擇其中的一個基因，在父代中將其之后的路徑進行交叉；反之則不交叉。

例如，父代個體分別為{1,8,11,14,17,19,21,22,26,30}、{1,6,8,9,13,14,18,19,28,30}，I={8,14,19}，產(chǎn)生一個隨機正整數(shù)R=2，則交換路徑節(jié)點I(R)后面的路徑，得到子代{1,8,11,14,18,19,28,30}和{1,6,8,9,13,14,17,19,21,22,26,30}。

2.4 變異策略

隨機選取父代個體中除起點和終點以外的兩個不相鄰柵格，刪去這兩個柵格之間的路徑，再分別以這兩個柵格為起止點，使用路徑初始化方法對這兩個柵格進行連續(xù)化操作。若無法產(chǎn)生新的連續(xù)路徑，則重新選擇兩個不相鄰柵格執(zhí)行連續(xù)化操作。

例如，對于父代{1,8,11,14,17,19,21,22,26,30}，隨機選兩個柵格11和22，若連續(xù)化操作得到{11,13,16,17,18,21,22}，則得到新個體{1,8,11,13,16,17,18,21,22,26,30}。

3 蟻群算法

蟻群算法是一種仿生算法，在路徑規(guī)劃中的應用主要分為覓食規(guī)則、行走規(guī)則及信息素規(guī)則。覓食規(guī)則要求建立禁忌表，規(guī)定螞蟻可行位置；行走規(guī)則要求螞蟻k在當前節(jié)點i轉(zhuǎn)移到下一節(jié)點j的轉(zhuǎn)移概率由信息素濃度和啟發(fā)式函數(shù)決定，即式(3)決定。

(3)

(4)

其中，dj, end為柵格j距目標柵格的歐氏距離[16]。

3.1 信息素規(guī)則

初始信息素產(chǎn)生規(guī)則。針對初始信息素匱乏的問題，采用遺傳算法尋找初始較優(yōu)路徑集合，按照適應度排序，選取前50%的較優(yōu)個體，不考慮信息素的揮發(fā)，只考慮對走過的路徑進行信息素增加，根據(jù)式(5)、(6)得到蟻群算法所需的初始信息素。

(5)

(6)

其中，ganum為種群規(guī)模，Q為常數(shù)，Lm為個體m所走路徑長。

信息素更新規(guī)則。隨著時間的推移，螞蟻在運動中留下信息素的同時，路徑上已存的信息素按照一定比例丟失。蟻群完成一次循環(huán)后，各路徑上的信息素按式(7)～式(9)更新。

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

(7)

(8)

(9)

其中，ρ∈(0,1)為信息素揮發(fā)因子，antnum為螞蟻數(shù)，Q為常數(shù)，Lk為螞蟻k所走路徑長。

3.2 簡化操作

為進一步優(yōu)化路徑及其長度，加入簡化操作。圖2給出了簡化操作示意圖。從起點開始遍歷，與當前點不相鄰的點相連接，得到的路徑不經(jīng)過障礙物，則刪去冗余節(jié)點并重新計算適應度。

圖2 簡化路徑示意圖

4 遺傳-蟻群算法設計

利用遺傳算法對蟻群算法的信息素進行優(yōu)化，解決蟻群算法初始信息素缺乏的問題，以此來提高算法精度。具體做法是利用遺傳算法得到的較優(yōu)解，計算得到蟻群算法所需的初始信息素，再用蟻群算法求解最優(yōu)路徑。遺傳-蟻群算法流程如圖3所示。

圖3 遺傳-蟻群算法流程

遺傳-蟻群算法步驟：

步驟1：初始化遺傳算法參數(shù)；初始化染色體；保留當前全局最優(yōu)。

步驟2：選擇、交叉、變異操作；更新全局最優(yōu)。

步驟3：利用截斷選擇，根據(jù)式(5)、(6)更新信息素。

步驟4：若是達到最大迭代次數(shù)，或當前全局最優(yōu)與前若干次全局最優(yōu)相同，則停止迭代，輸出次優(yōu)解；否則返回步驟2。

步驟5：蟻群參數(shù)初始化。

步驟6：利用式(2)移動螞蟻；計算路徑長度；利用式(7)～式(9)更新信息素。

步驟7：更新全局最優(yōu)，簡化路徑。

步驟8：若達到最大迭代次數(shù)，則輸出最優(yōu)值。否則返回步驟6。

5 仿真結(jié)果分析

為驗證遺傳-蟻群算法的性能，構(gòu)建地圖模型進行仿真對比實驗。遺傳算法參數(shù)：ganum=30、pc=0.8、pm=0.2、Q=1；蟻群算法參數(shù)：antnum=50、α=5、β=2.5、Q=1、ρ=0.01。為了增加對比性，分析文中算法的有效性，分別做了以下兩組對比實驗。

實驗一采用文獻[11]的30×30柵格地圖。由圖4知，各個算法均可找到一條由起點抵達終點的路徑，基本蟻群算法(如圖4(a))、文獻[11]算法(如圖4(b))、文獻[13]算法(如圖4(c))及文獻[15]算法(如圖4(d))的最優(yōu)路徑長分別為56.769 6、44.526 9、42.183 8、45.526 9，文中算法(如圖4(e))的最優(yōu)路徑長為41.471 2，效果最好。圖4(f)所示為算法每次迭代的最優(yōu)路徑，可知文中算法收斂速度更快且最優(yōu)路徑更短。為驗證文中算法的優(yōu)越性，采用最優(yōu)路徑長、運行若干次的平均最優(yōu)路徑長、最佳迭代次數(shù)作為對比算法相關(guān)指標，其詳細數(shù)據(jù)如表1所示。綜合對比易知，文中算法在提高全局搜索能力以及收斂速度方面有很大改進。

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

(b)文獻[11]算法

(c)文獻[13]算法

(d)文獻[15]算法

(e)文中算法

(f)迭代圖

表1 實驗一算法指標

實驗二采用40×40柵格地圖。各算法找到的最優(yōu)路徑如圖6，傳統(tǒng)蟻群算路徑長為67.497 5，文獻[11]算法路徑長為64.426 4，文獻[13]算法路徑長為61.012 2，文獻[15]算法路徑長為65.598 0，文中算法最優(yōu)路徑長為58.110 5。將算法指標記入表2，同時如圖5(f)最優(yōu)路徑迭代可知，在復雜環(huán)境下，文中算法相比于其他算法仍具有較好的全局搜索能力。

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

(b)文獻[11]算法

(c)文獻[13]算法

(d)文獻[15]算法

(e)文中算法

(f)迭代圖

表2 實驗二算法指標

實驗結(jié)果表明：提出的遺傳-蟻群算法相比于其他算法具有全局搜索能力強且收斂速度快的優(yōu)點，能快速、準確、高效地實現(xiàn)機器人的路徑規(guī)劃。

6 結(jié)束語

針對蟻群算法在靜態(tài)環(huán)境下的機器人路徑規(guī)劃中存在的初始信息素缺乏、易陷入局部最優(yōu)、搜索效率低等缺陷，提出了將遺傳算法和蟻群算法融合的方案。相對于傳統(tǒng)蟻群算法按照經(jīng)驗設定初始信息素的方式，該文采取對遺傳算法每次迭代得到的種群按照適應度降序排列，選取種群前50%的較優(yōu)個體，根據(jù)初始信息素產(chǎn)生規(guī)則得到蟻群算法所需的初始信息素；由于混合算法涉及到算法之間的轉(zhuǎn)換時間問題，文中設計相應的控制策略來控制遺傳算法向蟻群算法轉(zhuǎn)換的時機；為使規(guī)劃路徑更平滑且距離更短，對蟻群算法得到的全局最優(yōu)路徑采取簡化操作。在柵格環(huán)境下對機器人路徑規(guī)劃進行仿真實驗，結(jié)果表明，該算法具有全局搜索能力強、收斂速度快的優(yōu)點，在路徑規(guī)劃上是可行且有效的。