基于IAFSA和AGA混合算法的移動(dòng)機(jī)器人路徑規(guī)劃

劉寧寧 陳志軍 閆學(xué)勤

關(guān)鍵詞： 移動(dòng)機(jī)器人; 路徑規(guī)劃; 改進(jìn)人工魚群算法; 自適應(yīng)遺傳算法; 標(biāo)準(zhǔn)人工魚群算法; 標(biāo)準(zhǔn)遺傳算法

中圖分類號： TN911.1?34; TP242 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）03?0157?06

Abstract： The artificial fish swarm algorithm is easy to fall into local optimization， and has the problem of inaccurate result for path planning of mobile robot， and the genetic algorithm has the problems of easy prematurity and slow convergence speed for path planning. Therefore， a mobile robot path planning method based on improved artificial fish swarm algorithm （IAFSA） and adaptive genetic algorithm （AGA） is proposed. The grid method is used to establish the environment model of mobile robot， and then the IAFSA is used to search the initial feasible path of mobile robot. The searched initial feasible path is taken as the initial population of AGA. The AGA is adopted to optimize the global optimal path of mobile robot. The simulation results show that the hybrid algorithm is superior to the standard artificial fish swarm algorithm in the aspects of result accuracy and stability， and is superior to the standard genetic algorithm in the aspects of local optimization avoidance and convergence speed.

Keywords： mobile robot; path planning; improved artificial fish swarm algorithm; adaptive genetic algorithm; standard artificial fish swarm algorithm; standard genetic algorithm

0 ?引 ?言

路徑規(guī)劃被認(rèn)為是根據(jù)距離、時(shí)間、成本、能量等標(biāo)準(zhǔn)進(jìn)行最優(yōu)路徑的計(jì)算，距離和時(shí)間是最常用的準(zhǔn)則。移動(dòng)機(jī)器人能夠根據(jù)距離和時(shí)間這兩個(gè)準(zhǔn)則自主決策出一條連接起始位置和目標(biāo)位置的避撞最優(yōu)或次優(yōu)路徑[1]。

目前，基于遺傳算法（GA）、蟻群算法（ACO）、人工神經(jīng)網(wǎng)絡(luò)算法（ANN）、人工魚群算法（AFSA）等智能算法的移動(dòng)機(jī)器人路徑規(guī)劃是非常普遍的應(yīng)用，盡管這些智能算法優(yōu)化了移動(dòng)機(jī)器人的路徑，但是優(yōu)化效果并不理想。像遺傳算法[2]易出現(xiàn)早熟現(xiàn)象且收斂速度慢;蟻群算法[3]的信息素在求解初期比較匱乏，所以蟻群算法的前期求解速度較慢;人工神經(jīng)網(wǎng)絡(luò)[4]結(jié)構(gòu)比較復(fù)雜，參數(shù)也不容易確定，且易生成局部最優(yōu)路徑;人工魚群算法[5]由于魚群聚群和追尾而導(dǎo)致算法易陷入局部最優(yōu)，同時(shí)在算法后期由于魚群隨機(jī)覓食而不能求取高精度的最優(yōu)解等。針對單一智能算法的缺陷，現(xiàn)在需要解決的主要問題是如何選擇智能算法來優(yōu)化移動(dòng)機(jī)器人的路徑。

通過將兩種改進(jìn)后的算法相結(jié)合來實(shí)現(xiàn)移動(dòng)機(jī)器人的全局路徑規(guī)劃是近些年研究的熱點(diǎn)。因?yàn)檫z傳算法種群進(jìn)化能力強(qiáng)，所以對全局搜索的范圍十分有利，但是這種算法易受種群質(zhì)量的影響，從而影響算法的計(jì)算效率和收斂速度。人工魚群算法的搜索速度快并且尋優(yōu)能力強(qiáng)，但由于其存在隨機(jī)移動(dòng)的特性，使得該算法較難獲取高精度的全局最優(yōu)路徑。通過對上述遺傳算法和人工魚群算法的優(yōu)點(diǎn)及其存在的缺陷進(jìn)行分析，提出一種改進(jìn)人工魚群算法和自適應(yīng)遺傳算法相結(jié)合的混合算法優(yōu)化移動(dòng)機(jī)器人的路徑。該算法用改進(jìn)人工魚群算法生成初始種群，解決遺傳算法容易受初始種群影響的缺點(diǎn)，用自適應(yīng)遺傳算法彌補(bǔ)人工魚群算法后期搜索精度差及其后期尋優(yōu)速度慢的缺陷，從而獲得了高精度、高質(zhì)量、收斂速度快的尋優(yōu)能力。

式中：[Fmax]表示群體最大適應(yīng)度;[Fav]表示每代群體的平均適應(yīng)度值;[F]表示要變異個(gè)體的適應(yīng)度值;[k3]，[k4]表示[0，1]區(qū)間內(nèi)的任意常數(shù)。

4） 刪除算子

在生成個(gè)體路徑時(shí)，由于初始路徑的產(chǎn)生和變異操作的連接過程可能會產(chǎn)生相同的柵格序號，從而影響尋優(yōu)速度，所以用刪除算子刪除掉兩相同柵格中的一個(gè)柵格和兩相同柵格之間的冗余柵格，將得到的路徑作為下一代種群的個(gè)體。

2.2.4 ?移動(dòng)機(jī)器人路徑優(yōu)化流程

首先用改進(jìn)人工魚群算法產(chǎn)生移動(dòng)機(jī)器人的初始路徑，然后用自適應(yīng)遺傳算法中選擇、交叉和變異等操作對生成的初始路徑尋優(yōu)，路徑優(yōu)化步驟如下：

Step1：自適應(yīng)遺傳算法初始化，設(shè)種群最大進(jìn)化代數(shù)為MAX，設(shè)進(jìn)化代數(shù)初始值[t=1]。

Step2：對移動(dòng)機(jī)器人工作環(huán)境進(jìn)行柵格建模，利用改進(jìn)人工魚群算法得到機(jī)器人的初始路徑，將初始路徑作為自適應(yīng)遺傳算法的初始種群。

Step3：采用適應(yīng)度函數(shù)計(jì)算種群中的每個(gè)個(gè)體適應(yīng)度值。

Step4：用輪盤賭的方法執(zhí)行選擇操作，從而復(fù)制出下一代個(gè)體。

Step5：任意選擇兩個(gè)個(gè)體，判斷這兩個(gè)個(gè)體是否滿足交叉概率，若滿足，則分別在兩個(gè)個(gè)體中隨機(jī)產(chǎn)生一個(gè)交叉位，進(jìn)而執(zhí)行交叉操作。

Step6：根據(jù)變異概率執(zhí)行變異操作。

Step7：路徑中若有重合路徑點(diǎn)，則執(zhí)行刪除操作，直到滿足無重合路徑點(diǎn)的條件。

Step8：如果[t≥MAX]，轉(zhuǎn)Step9;否則，令[t=t+1]，轉(zhuǎn)Step3。

Step9：循環(huán)結(jié)束，輸出最優(yōu)個(gè)體。

3 ?仿真研究

3.1 ?實(shí)驗(yàn)1

在10[×]10的柵格環(huán)境下對本文混合算法和單一的標(biāo)準(zhǔn)人工魚群算法進(jìn)行仿真比較，仿真過程中的相關(guān)參數(shù)設(shè)置為：人工魚總數(shù)[N=10]，視野域Visual=4，擁擠度因子[delta=0.7]，最大選擇次數(shù)try_number=3，最大迭代次數(shù)[M=10]，跳轉(zhuǎn)因子[η]=5，常系數(shù)[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，種群最大進(jìn)化代數(shù)MAX=10。在此環(huán)境下，仿真結(jié)果如圖3所示。

通過對圖3a），圖3b）的對比可以發(fā)現(xiàn)，本文算法比標(biāo)準(zhǔn)人工魚群算法能獲得更短的路徑。

為了更好地說明本文混合算法在優(yōu)化精度和穩(wěn)定性上要優(yōu)于標(biāo)準(zhǔn)人工魚群算法，分別對標(biāo)準(zhǔn)人工魚群算法和本文混合算法進(jìn)行10次仿真比較，仿真結(jié)果如表1所示。

從表1中可以看出，本文混合算法在結(jié)果精度和穩(wěn)定性方面優(yōu)于標(biāo)準(zhǔn)人工魚群算法。在最優(yōu)結(jié)果精度上，本文混合算法較標(biāo)準(zhǔn)人工魚群算法提高4.2%;在穩(wěn)定性方面，本文混合算法相比標(biāo)準(zhǔn)人工魚群算法提高了79.7%。

3.2 ?實(shí)驗(yàn)2

在15[×]15的柵格環(huán)境下，對本文混合算法和標(biāo)準(zhǔn)遺傳算法應(yīng)用到移動(dòng)機(jī)器人路徑規(guī)劃方面進(jìn)行了仿真比較，仿真過程中的相關(guān)參數(shù)設(shè)置為：人工魚的總數(shù)[N=]10，視野域Visual=4，擁擠度因子delta=0.7，最大選擇次數(shù)try_number=3，最大迭代次數(shù)[M=50]，跳轉(zhuǎn)因子[η]=5，常系數(shù)[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，種群最大進(jìn)化代數(shù)MAX=50;遺傳算法初始種群大小設(shè)置為50，最大迭代次數(shù)設(shè)置為50，標(biāo)準(zhǔn)遺傳算法的交叉概率設(shè)置為固定概率[pc]=0.6，變異概率設(shè)置為固定概率[pm]=0.01。在此環(huán)境下，本文混合算法和標(biāo)準(zhǔn)遺傳算法尋找最優(yōu)路徑結(jié)果和收斂曲線分別如圖4，圖5所示。

從圖4和圖5能夠看出，本文混合算法在尋優(yōu)能力上要優(yōu)于標(biāo)準(zhǔn)遺傳算法。

為了更好地說明本文混合算法的優(yōu)越性，分別對本文混合算法和標(biāo)準(zhǔn)遺傳算法進(jìn)行多次仿真，仿真結(jié)果如表2所示。

通過表2可以看出，本文混合算法與標(biāo)準(zhǔn)遺傳算法相比，規(guī)劃長度、規(guī)劃時(shí)間和所需迭代次數(shù)都有明顯改善。實(shí)驗(yàn)數(shù)據(jù)有力說明了本文混合算法具有路徑規(guī)劃能力強(qiáng)、搜索效率高以及收斂速度快等優(yōu)點(diǎn)，驗(yàn)證了本文混合算法的優(yōu)越性。

4 ?結(jié) ?論

本文所設(shè)計(jì)的IAFSA?AGA混合算法優(yōu)化了移動(dòng)機(jī)器人的路徑，為今后探索路徑規(guī)劃算法提供了一種思維模式及其較大的參考與學(xué)術(shù)價(jià)值。