蟻群遺傳融合算法在移動機器人路徑規(guī)劃中的應用*

于樹科，瞿國慶，祁宏宇，趙開新

（1.江蘇商貿(mào)職業(yè)學院，江蘇 南通 226011；2.河南工學院，河南 新鄉(xiāng) 453002）

0 引言

路徑規(guī)劃是移動機器人導航領(lǐng)域研究的首要任務，也是機器人安全無碰撞地執(zhí)行各項任務的基本保障，目前在移動機器人路徑規(guī)劃過程中經(jīng)常使用的智能算法有蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡法、粒子群算法等［1］。針對傳統(tǒng)蟻群算法在路徑搜索初期存在盲目性，搜索空間大、效率較低，而遺傳算法全局搜索方面的能力較強，但在搜索后期啟發(fā)信息利用不足等缺陷［2］。本文融合蟻群和遺傳算法，并把融合后的算法應用到移動機器人路徑規(guī)劃中。

1 蟻群和遺傳算法分析

1.1 蟻群算法

蟻群算法（Ant Colony Algorithm，ACA）［3］是根據(jù)自然界中螞蟻覓食行為而提出的一種模擬進化算法。算法中要求螞蟻在搜索路徑時不能重復經(jīng)過同一節(jié)點，通過在算法中加入了禁忌表項來實現(xiàn)。表示第k只螞蟻在t時刻的i節(jié)點選擇向j節(jié)點移動的概率。

蟻群算法是一種求解組合最優(yōu)路徑問題的啟發(fā)式方法，該算法具有分布式計算、正反饋機制和良好的并行性、健壯性和可擴展性，并且螞蟻覓食行為與機器人路徑規(guī)劃有著天然的關(guān)聯(lián)性，因此，可以被應用到移動機器人路徑規(guī)劃中。但該算法在搜索初期存在盲目性大，在搜索后期存在著耗時長和容易出現(xiàn)停滯等缺陷。因此，傳統(tǒng)蟻群算法需要經(jīng)過改進后才能應用到移動機器人路徑規(guī)劃中。

1.2 遺傳算法

遺傳算法（Genetic Algorithm，GA）［4-5］是基于進化論遺傳學機理上產(chǎn)生的搜索優(yōu)化方法。遺傳算法具有良好的并行性和較強的通用性，并且該算法具有良好的全局優(yōu)化和穩(wěn)定性，操作簡單，但是當求解到一定范圍時也容易陷入局部最優(yōu)解。

2 蟻群和遺傳算法的改進與融合

蟻群算法［6］和遺傳算法［7］是目前應用比較廣泛的兩種智能仿生算法，已經(jīng)被應用到科研工程等相關(guān)領(lǐng)域。蟻群算法的正反饋機制使其具有更好的全局優(yōu)化能力以及分布并行計算能力，但在搜索初期由于信息素的匱乏，導致求解效率較低。遺傳算法在搜索初期速度快，又適合大范圍的搜索，但搜索后期由于無法充分利用系統(tǒng)中的反饋信息，會在冗余迭代上耗費大量的時間。為了克服兩種智能算法存在的缺陷，可以對蟻群和遺傳算法進有效的融合。

2.1 融合的策略

通過大量的分析研究與實驗論證，發(fā)現(xiàn)蟻群和遺傳兩種算法在求解速度與時間上的總體態(tài)勢如圖 1 所示［7-8］。

圖1 蟻群算法與遺傳算法的速度-時間曲線

由圖1可以看出，遺傳算法在搜索初期t0～tc時間段，求解速度較快，經(jīng)過tc時刻后，遺傳算法效率開始急速下滑；蟻群算法搜索初期由于信息素信息缺乏，在 t0～tc時刻，效率較低，過了 tc時刻后，蟻群算法效率開始快速上升，最后達到一個較高的穩(wěn)定狀態(tài)。

融合算法的思路是在融合算法前期，用遺傳算法產(chǎn)生的最優(yōu)解來初始化蟻群算法的信息素。融合算法后期利用蟻群算法的收斂速度快來尋找最優(yōu)路徑。在遺傳算法階段，統(tǒng)計迭代過程中子代種群的進化率，如果連續(xù)n代的進化率都小于預先設定的迭代次數(shù)的最小進化率，則遺傳算法終止，蟻群算法執(zhí)行。

2.2 蟻群算法的改進

在蟻群算法中，路徑上的信息素的值會隨著時間的流逝而減小，在本文中用Rij來進行表示，通過一個遞減的指數(shù)函數(shù)來表示。

式中，tij是螞蟻從節(jié)點i到節(jié)點j所花費的時間，是一個常數(shù)，Rij的值越大，代表著螞蟻從節(jié)點i到節(jié)點j的路徑越好。

在每次迭代過程中，只有在指定時間內(nèi)，最優(yōu)的螞蟻才會更新此路徑上信息素的值。在式（4）中是最優(yōu)的螞蟻經(jīng)過該路徑后此路徑上信息素的改變量。Lk第k只螞蟻走過的路徑，是第k只螞蟻從i節(jié)點到k節(jié)點花費的時間，是第k只螞蟻從i節(jié)點到k節(jié)點學習到的信息。

3 融合算法在移動機器人路徑規(guī)劃中的應用

本文提出融合蟻群和遺傳算法（Fusing of Ant Colony and Genetic Algorithm，F(xiàn)ACGA），并把該算法應用到移動機器人路徑規(guī)劃中，應用的流程如下頁圖2。在融合算法中設置遺傳算法的最小迭代次數(shù)為Gmin，最大迭代次數(shù)為Gmax，最小進化率為Gratio，當給定迭代次數(shù)范圍內(nèi)連續(xù)Gend代的進化率低于Gratio，則終止遺傳算法搜索，用遺傳算法得到的信息來初始蟻群算法中信息素的初始值，轉(zhuǎn)入蟻群算法求解。算法的步驟如下。

步驟1：初始化交叉概率pc，變異概率pm，以及最大進化代數(shù)Gmax，最小進化代數(shù)Gmin，最小進化率Gratio，進化結(jié)束代數(shù) Gend。

步驟2：設置種群規(guī)模為S得初始群體G，使Gmin＜G＜Gmax，根據(jù)實際問題進行編碼，確定適應度函數(shù)，計算種群中個體的適應度值。

步驟3：對種群個體進行解碼，執(zhí)行選擇、交叉、變異操作。

步驟4：比較新個體與原父代種群中的個體，根據(jù)結(jié)果進行個體的優(yōu)劣替換，選擇優(yōu)良個體作為下一代新的子個體。

步驟 5：若 Gmin＜G＜Gmax且 Gend的進化率 ＞Gratio，則轉(zhuǎn)向步驟3，否則轉(zhuǎn)向步驟6。

步驟6：用遺傳算法生成的較優(yōu)解初始化蟻群算法信息素的初始值。

步驟7：設置蟻群算法最大循環(huán)次數(shù)為Nmax，螞蟻個數(shù)為m，循環(huán)次數(shù)k為0。

步驟8：每只螞蟻根據(jù)狀態(tài)移動規(guī)則式（1）選擇下一個節(jié)點。

步驟9：當螞蟻k到達終點End時，按式（2）～式（4）對其經(jīng)過路段上的信息濃度進行更新。

步驟10：重復步驟8、步驟9，直至所有螞蟻都到達終點End。

步驟11：更新本次迭代最差路徑長度及其所包含路段信息，全局最優(yōu)路徑長度及其包含路段信息。

步驟12：把m只螞蟻的位置重置為起點Start，置空禁忌表。

步驟13：若循環(huán)次數(shù)k＞Nmax則程序結(jié)束，否則轉(zhuǎn)到步驟8。

4 仿真實驗

用VC++6.0和MATLAB構(gòu)建仿真平臺，在柵格環(huán)境下建模對蟻群算法（ACA）、遺傳算法（GA）和本文提出的算法（FACGA）進行分析，設置仿真環(huán)境如圖3，設定障礙物分布在全局靜態(tài)10×10的柵格矩陣中，螞蟻起點為圖3中Start，終點為End，蟻群算法中參數(shù)為：螞蟻數(shù)量m=20，信息啟發(fā)算子α和期望啟發(fā)算子β分別為1和5；信息揮發(fā)系數(shù)ρ=0.6，遺傳算法中參數(shù)為：初始種群G為60，運行遺傳算法Gmax為60次，每次產(chǎn)生260代，變異概率pm為0.07，交叉概率pc為0.8，圖3中障礙物為黑色填充單元格。

仿真結(jié)果表明在相同的環(huán)境下，在搜索初始階段，由于基本蟻群算法（ACA）搜索的盲目性，增加了不必要的搜索范圍，降低了搜索效率，并且難以搜尋到最優(yōu)路徑；而遺傳算法（GA）搜索后期由于無法充分利用系統(tǒng)中的反饋信息，在冗余迭代上需要耗費大量的時間，并且陷入了局部最優(yōu)。融合蟻群和遺傳算法（FACGA）在搜索前期通過把遺傳算法的最優(yōu)解引入到蟻群算法的初始化信息素中，縮小了算法的查詢范圍，搜索后期又切換到蟻群算法，從而避免了算法陷入局部最優(yōu)，縮短了尋找最優(yōu)路徑的時間，獲得了從Start到End的全局最優(yōu)路徑。驗證了本文所提算法的隨機性、有效性和全局收斂性。

圖2 蟻群遺傳融合算法路徑規(guī)劃流程圖

圖3 3種算法路徑規(guī)劃圖對比

圖4 3種算法路徑長度迭代次數(shù)對比圖

圖4中當采用ACA算法進行路徑規(guī)劃時算法收斂需迭代39次，最優(yōu)路徑長度為17.914，當采用GA算法進行路徑規(guī)劃時算法收斂需迭代45次，最優(yōu)路徑長度為17.438，當采用FACGA算法進行路徑規(guī)劃時算法收斂需迭代22次，最優(yōu)路徑長度為16.352，可以看出本文所設計算法FACGA收斂速度更快，收斂路徑更短，效率更高。

5 結(jié)論

本文通針對蟻群算法和遺傳算法在移動機器人路徑規(guī)劃中存在的搜索盲目性大、效率低以及容易陷入局部最優(yōu)等缺陷，改進了蟻群算法中信息素更新的方法，并且提出了一種基于改進蟻群和遺傳算法的融合方案（FACGA），該方案使蟻群和遺傳算法優(yōu)勢互補。實驗結(jié)果表明，本文所提出的方案能提高移動機器人搜索效率，快速找到從起點到終點的較優(yōu)路徑。

［1］趙開新，魏勇.改進蟻群算法在DSR路由協(xié)議中的應用［J］.火力與指揮控制，2015，40（7）:135-138.

［2］胡飛虎，田朝暉.基于遺傳算法的應急物資分層聯(lián)動調(diào)度研究［J］.計算機應用研究，2016，33（11）:439-443.

［3］趙開新，魏勇.改進蟻群算法在P2P網(wǎng)絡資源搜索中的應用［J］.火力與指揮控制，2015，40（5）:139-142.

［4］韓建妙，劉業(yè)政.基于遺傳算法的超市最短導購路徑推薦［J］.計算機工程與應用，2016，52（4）:238-242.

［5］石悅，邱雪松.基于改進遺傳算法的電力光傳輸網(wǎng)規(guī)劃方法［J］.通信學報，2016，37（1）:116～122.

［6］羅建，薛鋒.旅客列車線路選擇的蟻群算法求解［J］.計算機工程與應用，2013，49（11）:11-15.

［7］李琳.基于免疫遺傳算法的移動機器人軌跡跟蹤［J］.華南理工大學學報，2013，47（7）:13-18.

［8］黃永青，楊善林.交互式蟻群遺傳算法［J］.小型微型計算機系統(tǒng)，2016，37（11）：2567-2570.