基于改進鯨魚優化算法的移動機器人多目標點路徑規劃

王步偉 潘鵬程*

（三峽大學電氣與新能源學院，湖北宜昌，443002）

0 引言

路徑規劃是移動機器人發展中至關重要的一環[1]，它可以提高任務完成的效率并降低成本。針對路徑規劃的傳統算法有快速搜索隨機樹（Rapidly-exploring Random Tree, RRT）算法[2]、A* 算法[3]和Dijkstra 算法[4]等。傳統路徑規劃算法往往僅適用于單個目標點的任務中，而在物流配送、無人機巡檢、機器人導航和公共交通規劃等問題中，往往需要在一個給定的環境中找到一條連接多個目標點的路徑，即多目標點路徑規劃。因此，為解決多目標點路徑規劃問題，需要使用優化算法尋得一條遍歷所有目標點的最短路徑，如粒子群優化（Particle Swarm Optimization, PSO）算法[5]、灰狼優化（Grey Wolf Optimization, GWO）算法[6]和鯨魚優化算法（Whale Optimization Algorithm, WOA）[7]等。

鯨魚優化算法是一種新型的生物啟發式優化算法，受到座頭鯨捕食行為的啟發，通過模擬鯨魚的捕食策略和社會行為來求解優化問題。WOA 的主要優點是全局搜索能力強，收斂速度快，并且能很好地平衡探索與開發能力，因此廣泛應用于函數優化、機器學習與路徑規劃等領域。與此同時，國內外研究者針對標準WOA 的不足之處也提出了多種改進[8-9]。楊炳媛等[10]提出了根據個體的集散程度自適應選擇全局搜索或局部搜索的方法，以實現WOA 的快速收斂；尹梅等[11]則通過采用自適應收斂因子來平衡算法的探索和開發能力。在處理多目標點路徑規劃等復雜問題時，標準鯨魚優化算法仍存在搜索精度不足，以及收斂速度較慢的問題。

針對以上問題，本文提出一種改進的鯨魚優化算法：引入自適應搜索控制系數和記憶庫列表策略提高算法收斂速度、精度和搜索能力，并與A*算法相結合，將A*算法單目標點路徑規劃生成的實際距離矩陣作為輸入，從而提高多目標點路徑規劃的精度和效率。

1 環境建模

柵格地圖的建模方法[12]具有地圖構建簡單、位置精度高、效率高等優點。假定環境地圖長為,寬為，將地圖平均劃分為個長寬相等的小柵格，用表示每個小柵格，整個地圖可用表示：

每個柵格有無障礙物信息表達式為：

如圖 1 所示，黑色部分表示障礙物，白色部分表示可自由通過區域。機器人在柵格地圖內采用8 鄰域[13]的搜索方式，紅色箭頭為可行走的8 個方向。

圖 1 柵格地圖模型

2 路徑規劃

2.1 單目標點路徑規劃

單目標點路徑規劃問題可表述為：為移動機器人在環境中尋找一條無碰撞、效率高且長度最短的路徑。

A*算法是一種基于傳統圖搜索的智能啟發式算法，它具有穩定性高、節點搜索效率高等優點[14]，因此普遍用于單目標點路徑規劃。主要原理為：以起點作為初始節點，搜索初始節點旁8 個鄰域，并通過啟發函數評估后選擇代價最小的節點，然后搜索這個節點的8 個鄰域，選擇下一個代價最小的節點，重復上述步驟，直到選擇的節點與目標點重合。最后，將這些代價最小的節點連接起來，便得到了一條最優路徑。A*算法的代價函數如下：

圖 2 A＊算法示意圖

由于A*算法充分考慮了障礙物對路徑的影響，更符合機器人的實際運行，故本文使用A*算法生成所有目標點之間的距離矩陣，表達式為：

2.2 多目標點路徑規劃

在規劃過程中，需要考慮移動機器人在障礙環境下的移動限制，通過使用 A*算法計算出的最短避障距離替換忽略障礙物的歐式距離，確保在有障礙物的場景下為移動機器人規劃出的路徑與實際最優路徑一致。本文旨在，結合A*算法的單目標點路徑規劃和鯨魚優化算法的多目標點優化，使得值最小。

3 鯨魚優化算法

在搜索最優解過程中，標準鯨魚優化算法有包圍獵物、隨機搜索、螺旋捕獵3 種行為方式可供選擇。

3.1 標準鯨魚優化算法

3.1.1 包圍獵物行為

鯨魚優化算法假設當前種群中最優解為獵物位置或已接近目標獵物的位置，種群中其他鯨魚個體根據當前最優解更新自身位置。包圍獵物的過程可用數學模型表示為：

3.1.2 隨機搜索行為

鯨魚種群根據自己當前的位置、全局最優解和一定的隨機性來更新自己的位置，使得鯨魚能夠在搜索空間中以一定的概率跳出局部最優解，從而提高搜索到全局最優解的可能性。采用隨機搜索行為的條件是，可以用模型表示為：

3.1.3 螺旋捕獵行為

當鯨魚靠近全局最優解時，它們會以螺旋的方式在局部范圍內進行搜索。螺旋行為的策略是在當前位置和全局最優解的位置之間生成一個螺旋路徑，然后鯨魚沿著這個路徑進行移動。這樣可以使得鯨魚在靠近全局最優解的過程中，更好地探索局部解空間，提高找到更優解的概率。螺旋捕獵行為可用數學模型表示為：

3.2 改進鯨魚優化算法

3.2.1 自適應搜索控制系數

在標準鯨魚優化算法中，系數向量為均勻分布在[0,2]內的隨機數，是一個控制搜索速率的參數，故值是在每次迭代時隨機生成的，這可能導致搜索行為較為隨機，無法充分平衡算法全局搜索和局部搜索的能力，從而導致收斂精度不足。因此，本文提出一種自適應搜索控制系數，根據迭代次數來動態調整的大小，表達式如下：

3.2.2 記憶庫列表策略

在處理高維度或復雜問題時，WOA 的收斂速度較慢，僅靠三種位置更新機制已難以在迭代后期使算法跳出局部最優。因此，本文在鯨魚優化算法中添加一個記憶庫列表，使算法能夠記錄迭代過程中遇到過的當前最優解。達到最大迭代次數后，將最后一次迭代得到的最優解與記憶庫中的解進行比較，選取較優解作為最終結果，從而有效提高算法所得解的適應度，步驟如下：

1）在鯨魚種群初始化完成后建立一個記憶庫列表，用于儲存當前最優解。

2）將每次迭代后的最優解加入到記憶庫中，避免記憶庫容量過大，限制記憶庫列表長度，當達到最大容量時，使用和函數移除最差的解：

3）將最終解與記憶庫列表的最優解進行比較取較優解。

3.3 算法性能測試

為了驗證改進鯨魚優化算法的性能，本文選取4 個常用的標準測試函數對WOA 與本文算法的搜索精度以及效率進行比較，種群數量為30，函數維度為30，迭代次數為500。如表 1 所示，、為單模態測試函數，在搜索空間中只有一個全局最小值；、為多模態測試函數，在搜索空間中有許多局部最小值和一個全局最小值。兩種算法收斂精度對比如表 2所示， 收斂速度對比如圖 3所示。

表 1 測試函數

表 2 算法收斂精度對比

圖 3 算法收斂速度對比

3.4 多目標點路徑規劃步驟

本文基于改進鯨魚優化算法的多目標點路徑規劃步驟如下：

1）構建柵格地圖，設定初始參數：鯨魚種群數量、最大迭代次數，確定所有目標點坐標；

6）達到最大迭代次數后，將最終解與記憶庫列表中的最優解進行比較，取較優解作為最優遍歷順序；

7）根據步驟6）所得最優遍歷順序生成最優多目標點路徑規劃圖。

4 仿真實驗與分析

為驗證本文所提改進鯨魚優化算法的性能，在處理器為Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz、運行內存為16GB 的計算機上，利用Pycharm 平臺進行仿真實驗，python 版本為3.10。在相同地圖環境下對粒子群算法、標準鯨魚優化算法以及本文改進鯨魚優化算法進行仿真對比，種群數量均設為30，迭代次數設為500。

4.1 簡單場景下的仿真對比實驗

為驗證本文改進鯨魚算法在簡單場景下多目標點路徑規劃的精確度與收斂速度，在場景中選取9 個目標點進行規劃，首先使用A*算法獲得距離矩陣，然后分別使用三種優化算法獲得遍歷順序列表，如表 3 所示。規劃結果如圖 4 所示，圖中藍色五角星為目標點，黑色矩形為障礙物，紅色線條為算法所規劃的路徑。算法迭代曲線如圖 5 所示，算法性能對比如表 4 所示。

表 3 簡單場景下三種算法遍歷順序對比

表 4 簡單場景下三種算法路徑長度對比

圖 4 簡單場景下三種算法路徑規劃結果

圖 5 簡單場景下三種算法迭代曲線

由圖 4 以及表 4 中數據可知，本文改進鯨魚優化算法相比于PSO 算法和WOA，最小路徑長度分別減少14.43%、6.58%，平均路徑長度分別減少14.02%、6.39%。由圖 5 可知，PSO 算法收斂速度優于WOA，但由于過早陷入局部最優，導致路徑長度不如預期。WOA 雖然在中途陷入局部最優，得益于其隨機搜索行為，在迭代100次左右跳出局部最優解，但最終導致WOA 收斂速度變慢。本文所提出的改進鯨魚優化算法采用了自適應搜索控制策略和記憶庫列表策略，在收斂速度和路徑長度方面，改進鯨魚優化算法均表現出優于PSO 算法和WOA 的性能。這說明本文的改進方法在解決簡單場景下多目標點路徑規劃問題時具有更高的效率和準確性。

4.2 復雜場景下的仿真對比實驗

為驗證本文改進算法在復雜場景下的性能，在復雜場景1 下取13 個目標點進行規劃，在相同仿真條件下，同樣對比三種算法的性能。遍歷順序對比如表 5 所示，規劃結果如圖 6 所示，算法迭代曲線如圖 7 所示，算法性能對比如表 6 所示。

表 5 復雜場景1 下三種算法遍歷順序對比

表 6 復雜場景1 下三種算法路徑長度對比

圖 6 復雜場景1 下三種算法路徑規劃結果

圖 7 復雜場景1 下三種算法迭代曲線

由圖 6 以及表 6 中數據可知，在復雜場景1 下，本文改進鯨魚優化算法相比于PSO 和WOA，最小路徑長度分別減少14.92%、22.71%，平均路徑長度分別減少19.08%、22.31%。由圖 7 可知，在復雜度更高的場景中，三種算法均可能陷入局部最優解。WOA 在迭代后期難以跳出局部最優解，導致生成的路徑存在過多交叉，并且最小路徑長度不如預期。PSO 算法雖然兩次跳出局部最優解，但其收斂速度較慢。相對而言，本文所提出的算法在迭代初期也可能陷入局部最優解，然而通過引入記憶庫列表策略，使算法能夠迅速擺脫局部最優解，在50次迭代內便完成了收斂。

為進一步驗證本文改進算法在復雜場景下的性能，在復雜場景2 下取16 個目標點進行規劃，在相同仿真條件下，同樣對比三種算法的性能。遍歷順序對比如表 7所示，規劃結果如圖 8 所示，算法迭代曲線如圖 9 所示，算法性能對比如表 8 所示。

表 7 復雜場景2 下三種算法遍歷順序對比

表 8 復雜場景2 下三種算法路徑長度對比

圖 8 復雜場景2 下三種算法路徑規劃結果

圖 9 復雜場景2 下三種算法迭代曲線

由圖 8 以及表 8 中數據可知，在復雜場景2 下，本文改進鯨魚優化算法相比于PSO 算法和WOA，最小路徑長度分別減少23.12%、25.63%，平均路徑長度分別減少26.48%、28.13%。由圖 9 可知，PSO 算法和WOA 均陷入多次局部最優，導致最小路徑長度不如預期。而本文算法在收斂速度以及路徑長度方面均優于其它兩種算法，具有較好的魯棒性。

5 結論

本文針對移動機器人多目標點路徑規劃存在效率不高、準確性較低的問題，提出一種改進鯨魚優化算法來改善上述不足：

1）通過引入自適應搜索控制系數，提高了算法平衡全局搜索和局部搜索的能力；

2）提出一種記憶庫列表策略，通過增加記憶庫列表存儲最優解并進行維護更新，從而提高了算法所得解的質量并降低陷入局部最優的概率。

最后，在python 編程環境下，對 PSO 算法、WOA 以及本文算法進行仿真對比實驗。研究結果表明，隨著場景復雜度的增加，本文算法相較于WOA 所得出的最小路徑長度分別減少6.58%、22.71%、25.63%，相較于PSO算法所得出的最小路徑長度分別減少14.43%、14.92%、23.12%。

綜上所述，場景復雜度越高，本文提出的算法相較于其他兩種算法展現出更為顯著的優勢。因此，本文改進算法實現了路徑規劃效率和準確性的雙重優化，對移動機器人的多目標點路徑規劃有著重要意義。將本文提出的新方法應用到多機器人的多目標點路徑規劃是下一步的研究內容。