基于混沌求偶螢火蟲算法的移動機器人路徑規劃

侯志祥，成威，李鳳玲

(長沙理工大學汽車與機械工程學院，湖南長沙410114)

0 前言

移動機器人是集環境感知、動態決策與規劃、行為控制與執行等多功能于一體的智能化機器。近年來，隨著現代高科技產業的快速發展，移動機器人在工業、農業、醫學、生活服務、軍事等領域不斷地被開發和完善[1]。

路徑規劃作為移動機器人的核心研究內容，是實現移動機器人自主導航的必要條件[2-3]。路徑規劃實質是一個優化的問題，優化目標通常為路徑長度、時間、能耗、路徑平滑度或多個約束條件的加權等。目前，路徑規劃方法可分為兩類[4]：傳統經典算法和智能仿生算法。傳統經典算法具有實時性好、計算效率高的特點，但路徑規劃質量較差、使用場景有限，一般被用于實時性較高的動態路徑規劃，如A*算法、快速探索隨機樹RRT、人工勢場法等[5]。智能仿生算法具有規劃結果較優的特點，但算法存在易陷入局部最優、收斂速度慢等問題，一般被用于靜態或全局路徑規劃中，如蟻群算法、麻雀搜索算法、狼群算法、螢火蟲算法[6-7]等。

智能仿生算法比傳統經典算法具有更廣泛的適用場景。國內外學者為了得到更優的規劃結果，提出了各種改進的智能仿生算法。如ZHANG等[8]提出一種改進的麻雀搜索算法，該算法采用一種線性路徑策略和鄰域搜索策略，解決了算法收斂速度慢和精度低的問題，但算法在尋優效率和路徑安全上沒有明顯提升。LIU、LI[9]提出一種改進灰狼優化算法，該算法通過logistic混沌映射和自適應調整策略實現種群搜索與開發能力的平衡，提高算法的優化精度，有效地縮短路徑長度，但該算法中并未考慮時間因素。LI等[10]提出一種自適應種群螢火蟲算法，該算法采用自適應種群策略，平衡算法在迭代過程中種群與障礙物個數的匹配關系，提高了算法的探索能力和計算效率，但該算法中并未考慮時間穩定性和三維環境。

針對智能仿生算法在機器人路徑規劃中容易陷入局部最優和搜索精度低問題，本文作者提出一種混沌求偶螢火蟲算法(Chaotic Courtship Firefly Algorithm，CCFA)，用于移動機器人路徑規劃。在標準螢火蟲基礎上，通過采用Tent映射初始化種群，優化種群分布不均和搜索范圍不足的問題；同時，將種群分為雌性和雄性兩種種群，利用求偶學習策略使雄性螢火蟲向雌性螢火蟲學習，提高算法的收斂速度和求解精度；在每次尋優結束后，對最優個體螢火蟲進行高斯擾動，引導種群跳出局部極值點；最后，應用混沌求偶螢火蟲算法進行移動機器人路徑規劃仿真，驗證算法的可行性和有效性。

1 標準螢火蟲算法數學描述

標準螢火蟲算法是一種機制簡單的智能仿生算法，其特點主要有以下3點[11]：(1)螢火蟲之間通過亮度相互吸引，沒有性別差異；(2)螢火蟲吸引力的大小與它的亮度成正比；(3)螢火蟲的亮度或吸引度是由目標函數決定的。

標準螢火蟲算法的亮度和吸引度公式分別如式(1)和(2)所示：

(1)

(2)

式中：I和β分別為螢火蟲的亮度和吸引度；I0和β0分別為螢火蟲初始亮度和初始吸引度；γ為光吸收系數，一般取常數；rij為螢火蟲i和螢火蟲j的相對距離。

標準螢火蟲位置更新公式如式(3)所示：

(3)

式中：t為迭代次數；xi和xj分別表示第i只螢火蟲和第j只螢火蟲所處的位置；α為步長，取α∈[0，1]；ε為隨機數，取ε∈[-0.5，0.5]。

自FA算法被提出以來，研究人員開發了許多改進的FA算法。如ZHANG等[12]提出一種基于遺傳算法和螢火蟲算法的混合算法，該算法將局部最優的粒子進行交叉變異，解決算法陷入局部最優的問題，有效縮短了路徑長度，但該算法計算時間較長。FAN等[13]提出一種基于檔案學習的多目標螢火蟲算法，該算法將每一代最優粒子保存在外部存檔中，通過從外部檔案中隨機選取一個粒子作為螢火蟲的學習對象，提高了算法收斂速度和尋優精度；但該算法應用在路徑規劃中，路線較為曲折。為了解決標準FA算法存在的尋優精度低、收斂速度慢和易陷入局部最優等問題，本文作者提出一種混沌求偶螢火蟲算法。

2 混沌求偶螢火蟲算法

2.1 混沌映射策略

標準FA算法中，隨機生成的螢火蟲初始位置分布不均勻，導致算法尋優不佳、收斂速度較慢。因此，本文作者提出一種混沌映射策略。該策略利用混沌算子具有不重復遍歷性、隨機性和規律性的特點，使算法保持種群多樣性，提高算法全局搜索性能?；煦缬成浞N類較多，并且不同的混沌算子對算法尋優有很大的影響。文獻[14]指出Tent映射比常用的Logistic映射具有較優的解。因此，本文作者采用Tent映射初始化種群。Tent映射迭代公式如式(4)所示：

(4)

式中：zt為第t代混沌序列當前值；ρ為控制參數，取ρ=0.5；初始值z0設為(0，1)區間的隨機數。當遍歷完整個二維空間后，混沌粒子被映射到環境模型搜索空間中，得到第一代螢火蟲初始位置，其映射公式如式(5)所示：

(5)

為了避免算法在后期尋優過程中出現停滯、早熟或陷入局部最優的情況[15]，本文作者將每一代全局最優的個體螢火蟲進行高斯擾動，引導種群跳出局部極值點。高斯擾動公式如式(6)和式(7)所示：

PGpos=PBpos·(1+Gaussian(δ))

(6)

(7)

2.2 求偶學習策略

為進一步優化混沌策略出現早熟或局部最優的問題，本文作者提出一種求偶學習策略。該策略的螢火蟲有性別差異，分為雌性螢火蟲和雄性螢火蟲。

求偶學習模型如圖1所示。A框表示雄性螢火蟲，內部機制與標準FA算法相同，通過亮度大小相互吸引。其中藍圈xi表示當前螢火蟲，灰圈xj表示比當前亮度低的螢火蟲，綠圈表示比當前亮度高的螢火蟲。B框表示雌性螢火蟲，內部采用存檔機制，對應個體用xk表示。存檔機制是將每一代最優個體保存在檔案B中。其中，第一代雌性螢火蟲種群Np通過混沌映射得到，隨后每一次迭代用最優個體螢火蟲取代最差雌性個體螢火蟲。

圖1 求偶學習模型圖解

A框中雄性螢火蟲位置更新時，假設被選中的螢火蟲是綠圈，則當前螢火蟲藍圈xi可直接向綠圈移動。反之被選中的螢火蟲是灰圈xj時，則在迭代過程中，由于灰圈xj亮度低于藍圈xi的亮度，導致當前螢火蟲藍圈xi并沒有移動，從而出現信息丟失的情況。因此，為了使雄性螢火蟲xi向雌性螢火蟲xk學習，通過概率的方式由檔案B中的優秀雌性個體紅圈xk引導當前雄性螢火蟲藍圈xi移動，進而達到信息利用的目的，提高算法搜索精度和逃逸局部最優的能力。

求偶學習策略主要表現在4個方面：(1)螢火蟲之間存在性別差異，分為雌性和雄性；(2)雄性螢火蟲通過亮度大小相互吸引。當被選定的雄性螢火蟲亮度低于當前雄性螢火蟲亮度時，雌性螢火蟲將引導雄性螢火蟲移動；(3)雌性螢火蟲采用存檔機制，并通過概率來選擇一個優秀雌性個體作為當前雄性螢火蟲的學習對象，參與種群進化和更新；(4)雌性和雄性螢火蟲的亮度均由目標函數來確定。

求偶學習模型中，雌性個體選擇方式尤為重要。首先計算檔案B中每只雌性螢火蟲的適應度值f(即亮度)，然后根據目標函數的優化目的(求最大值或最小值)來確定是否對每一只雌性螢火蟲采取縮放機制。假設適應度值較低的雌性螢火蟲是更好的選擇，則檔案B中每只雌性螢火蟲的適應度值轉化公式如式(8)所示：

(8)

式中：f(k)為第k只雌性螢火蟲的適應度；Sk為第k只雌性螢火蟲適應度的倒數；Np為雌性種群數。檔案B中的雌性個體按比例變換后，雌性個體的選擇概率公式如式(9)所示：

(9)

式中：P(k)表示第k只雌性個體的選擇概率。這種概率方法確保適應度低的雌性個體更容易被選擇到，也能避免算法陷入局部最優。如果采取索引排序的方式選取最優雌性個體，算法很難實現全局最優。

3 CCFA在移動機器人路徑規劃中的應用

3.1 環境建模

本文作者采用文獻[16]的方法進行環境建模。環境模型如圖2所示，設S為起始點、G為目標點。為簡化模型設障礙物為圓形障礙物，障礙物用{Ok(oxk,oyk),rk|k=1,2,…,m}表示，其中：(oxk,oyk)為第k個障礙物的圓心坐標；rk為第k個障礙物的半徑。

圖2 環境模型

3.2 螢火蟲編碼和距離計算

假設每只螢火蟲在解空間中有唯一候選路徑，每條路徑在平面上有n個主路徑點，每個路徑點都表示為pi=(xi，yi)。為了使路徑平滑，通過三次B樣條插值將路徑點增加到N(N?n)個，使路徑成為一個離散點的集合。因此，對應每只螢火蟲(path)編碼公式如式(10)所示：

P={S1，p2(x2，y2)，…，pN-1(xN-1，yN-1)，GN}

(10)

式中：P為一只螢火蟲的解；S1、GN分別為路徑的起點和終點。

任意兩只螢火蟲之間的距離rij如式(11)所示：

rij=dis[P(i)，P(j)]

(11)

3.3 適應度函數

適應度函數是評價螢火蟲生成路徑質量的重要性能指標。針對移動機器的路徑規劃問題，需要綜合考慮路徑代價PL和避障代價PCollis來制定適應度函數。路徑代價PL由三次B樣條曲線擬合出的路徑長度決定，如式(12)所示：

(12)

式中：d(pj，pj+1)是兩個連續路徑點pi和pi+1之間的距離。

避障代價PCollis如式(13)所示：

(13)

式中：mean為每條路徑中各散點碰撞量的均值函數；dkj為路徑中散點到障礙物中心距離；rk為障礙物的半徑；max(1-dkj/rk,0)為障礙k與路徑點pj的碰撞程度。只有當dkj

因此，文中總適應度函數如式(14)所示：

f(i)=PL(i)·(1+?·PCollis(i))

(14)

式中：?為碰撞系數，取?=1 000。當路徑與障礙物發生碰撞，PCollis≠0，導致適應度f變大而放棄該路徑；當路徑與障礙物無碰撞時，PCollis=0，適應度f才會變小變優。

3.4 CCFA算法路徑規劃流程

步驟1，建立環境模型，設置目標函數和路徑規劃的起點S、終點G；

步驟2，初始化參數γ、β0、α，種群Np，最大迭代次數nmax，主路徑點n；

步驟3，采用Tent混沌映射初始化第一代雌雄種群，并由式(14)計算每只螢火蟲的適應度f；

步驟4，根據適應度f比較螢火蟲的亮度，如果f(j)

步驟5，根據式(6)(7)對全局最優個體進行擾動，引導種群跳出局部極值點；

步驟6，更新雄性種群A和雌性存檔B；

步驟7，判斷是否到達最大迭代次數，“是”則進入步驟8，“否”則返回步驟4；

步驟8，輸出最終結果。

4 仿真驗證和分析

為了驗證混沌求偶螢火蟲算法的有效性和優越性，本文作者對標準螢火蟲算法(FA)、混沌求偶螢火蟲算法(CCFA)和粒子群算法(PSO)進行30次仿真測試，并比較和分析實驗結果。所有實驗均在Win10系統、AMD R5-3600x處理器，主頻3.8 GHz、MATLAB 2020a仿真平臺下進行。

移動機器人起點S和終點G分別設為(0，0)和(100，5)，障礙物參數如表1所示。為簡化模型，障礙物設為圓形障礙物。為保證測試的公平性，設CCFA和FA的參數相同。種群Np=30，吸引度β0=1，光吸收系數γ=1，步長α=1。PSO算法參數同文獻[16]所述。3種算法統一設置最大迭代次數nmax=100，主路徑點n=3。

表1 障礙物參數

3種算法路徑規劃結果如圖3所示，分別為FA算法、CCFA算法、PSO算法的某次尋優結果?？梢姡?種算法均可以在避障的同時找到一條可行路徑，使移動機器人安全到達終點。FA算法和PSO算法在不同程度上陷入局部最優，未能找到最優路徑，而CCFA算法能夠找到最優路徑。

圖3 三種算法路徑規劃結果

適應度迭代結果如圖4所示，FA算法、CCFA算法、PSO算法最優適應度值分別為104.828 2、100.525 3、104.664 8 m，可見CCFA算法擁有更優尋優精度，且收斂速度比標準FA算法快。

3種算法30次仿真結果箱型圖如圖5所示?？梢姡篊CFA算法最優適應度值波動較?。籉A算法和PSO算法的最優適應度值波動較大，表明FA算法和PSO算法在求解路徑規劃問題中容易陷入局部最優，導致尋優結果產生較大的偏差。

為了更直觀分析CCFA算法的性能，30次仿真結果統計結果如表2所示，可知：不論路徑長度的最優值、均值還是標準差，CCFA算法均優于FA算法和PSO算法。CCFA算法比標準FA、PSO算法在路徑均值長度上分別縮短了3.075%和2.428%，體現了CCFA算法在全局搜索能力和逃逸局部最優情況上的優越性和穩定性。

表2 仿真結果統計

5 結論

為提高移動機器人的路徑規劃效率，本文作者提出一種混沌求偶螢火蟲算法。該算法主要有以下特點：(1)利用混沌映射初始化種群，使種群具有較優的初始解，提高算法全局搜索能力；(2)利用求偶學習策略，使雄性螢火蟲向雌性螢火蟲學習，提高算法搜索精度和逃逸局部最優的能力；(3)對每一代最優個體螢火蟲進行高斯擾動，避免算法在迭代過程中出現停滯而陷入局部最優。應用混沌求偶螢火蟲算法進行移動機器人路徑規劃仿真，仿真結果表明：CCFA算法比標準FA、PSO算法在路徑長度上分別縮短了3.075%和2.428%，收斂速度比標準FA算法有明顯的提升，能夠有效地改進移動機器人路徑規劃效率。文中所提算法的運行時間較長，后續將對算法計算時間進行深入優化。