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

虞馥澤，潘大志,2

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

0 引 言

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

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

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

1 環境建模

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

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

圖1 柵格矩陣及柵格地圖

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

(1)

(2)

其中，N、M分別是柵格環境矩陣的行數、列數，index為柵格序號。

2 遺傳算法

2.1 染色體編碼

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

2.2 適應度函數及選擇策略

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

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

2.3 交叉策略

采用單點交叉，具體過程為：先找出兩父代個體中除去起止點外所有相同的點構成集合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}，產生一個隨機正整數R=2，則交換路徑節點I(R)后面的路徑，得到子代{1,8,11,14,18,19,28,30}和{1,6,8,9,13,14,17,19,21,22,26,30}。

2.4 變異策略

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

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

3 蟻群算法

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

(3)

(4)

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

3.1 信息素規則

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

(5)

(6)

其中，ganum為種群規模，Q為常數，Lm為個體m所走路徑長。

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

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

(7)

(8)

(9)

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

3.2 簡化操作

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

圖2 簡化路徑示意圖

4 遺傳-蟻群算法設計

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

圖3 遺傳-蟻群算法流程

遺傳-蟻群算法步驟：

步驟1：初始化遺傳算法參數；初始化染色體；保留當前全局最優。

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

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

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

步驟5：蟻群參數初始化。

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

步驟7：更新全局最優，簡化路徑。

步驟8：若達到最大迭代次數，則輸出最優值。否則返回步驟6。

5 仿真結果分析

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

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

(a)傳統蟻群算法

(b)文獻[11]算法

(c)文獻[13]算法

(d)文獻[15]算法

(e)文中算法

(f)迭代圖

表1 實驗一算法指標

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

(a)傳統蟻群算法

(b)文獻[11]算法

(c)文獻[13]算法

(d)文獻[15]算法

(e)文中算法

(f)迭代圖

表2 實驗二算法指標

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

6 結束語

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