中圖分類號(hào)：TP242.2 文獻(xiàn)標(biāo)識(shí)碼：A

Path Planning for AGV Multi-objective Problem Based on Improved Whale Optimization Algorithm

LIU Yong，SUN Chuanzhu，F(xiàn)U Chaoxing （Collge of Mechanical and Electrical Engineering，Qingdao University，Qingdao 266071，China）

Abstract： To address the issue that traditional path planning algorithms cannot effectively solve the multi-objective problem of Automated Guided Vehicle （AGV） in path planning，the standard whale optimization algorithm is improved. Tent chaotic mapping and adaptive nonlinear dynamic inertia weight are introduced into the standard whale optimization algorithm，and the convergence factor and search coeficient are improved. Then，the improved algorithm is combined with the A ? algorithm for multi-objective point path planning. The iterative curve and running time of the improved whale optimization algorithm are tested using standard test functions， and a simulation comparison is conducted between the improved whale optimization algorithm and the standard whale optimization algorithm in the same map environment. The results show that，with a fixed population size，the improved whale optimization algorithm has a faster convergence speed and search accuracy compared to the standard whale optimization algorithm.

Keywords： path planning；multi-objective problem；whale optimization algorithm；AGV

隨著科學(xué)技術(shù)的不斷發(fā)展，AGV作為一種便捷的搬運(yùn)設(shè)備，廣泛應(yīng)用于汽車制造、航空航天及港口物流等領(lǐng)域。機(jī)器人路徑規(guī)劃已從單目標(biāo)點(diǎn)發(fā)展到多目標(biāo)點(diǎn)路徑規(guī)劃，是一種簡(jiǎn)化的旅行商問(wèn)題[1]。單機(jī)器人單目標(biāo)路徑規(guī)劃中，常使用Dijkstra 算法、A ? 算法、快速搜索隨機(jī)樹(shù)（Rapidly-exploring Random Tree，RRT）及其相關(guān)變體如RRT ? ，RRT-Connect算法等啟發(fā)式搜索方法，但啟發(fā)式搜索方法規(guī)劃效果較差，無(wú)法滿足實(shí)際需求。智能群體優(yōu)化算法通過(guò)比較和更新個(gè)體的最優(yōu)解，利用簡(jiǎn)單的數(shù)據(jù)模型求解高維度、多峰函數(shù)，實(shí)現(xiàn)復(fù)雜地形的最優(yōu)路徑規(guī)劃。各種路徑規(guī)劃問(wèn)題中，常使用粒子群算法[2]、蟻群算法[3]、遺傳算法[4]、狼群算法[5]以及鯨魚(yú)優(yōu)化算法[]等。智能群體優(yōu)化算法精度高，且尋優(yōu)速度快，能夠有效降低單機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃算法的復(fù)雜度，提高路徑規(guī)劃的效率，引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。白響恩等[針對(duì)無(wú)人水面艇在洋流環(huán)境下的多目標(biāo)路徑規(guī)劃問(wèn)題，改進(jìn)了粒子群算法，改進(jìn)后的算法有效縮短了路徑長(zhǎng)度，提高了路徑的平滑度;李軍濤等[8改進(jìn)了灰狼優(yōu)化算法的初始種群，控制參數(shù)及自適應(yīng)合作狩獵機(jī)制，仿真結(jié)果證明改進(jìn)后的灰狼優(yōu)化算法不僅能縮短多目標(biāo)路徑規(guī)劃長(zhǎng)度，而且能縮短單目標(biāo)路徑規(guī)劃長(zhǎng)度；丁俊峰等[9]改進(jìn)了傳統(tǒng)人工蜂群算法，改進(jìn)了Henon 混沌映射，并將其引入偵察蜂的搜索及蜜源的生成過(guò)程，有效縮短了多目標(biāo)路徑規(guī)劃時(shí)長(zhǎng);針對(duì)海洋中的多個(gè)船舶碰撞問(wèn)題，胡文興等[10]改進(jìn)了麻雀算法中發(fā)現(xiàn)者、加人者和警戒者的位置公式，在算法中加人精英選擇策略，性能得到了顯著提升。相較于常用的智能群體算法，鯨魚(yú)優(yōu)化算法參數(shù)少，易于實(shí)現(xiàn)[11]，，但仍存在搜索精度不足，收斂速度慢[12]等問(wèn)題。本文通過(guò)引入 Tent 混沌映射、改進(jìn)算法中的各項(xiàng)參數(shù)以及引入自適應(yīng)非線性動(dòng)態(tài)慣性權(quán)重3方面改進(jìn)鯨魚(yú)優(yōu)化算法，提高了算法的總體性能。

鯨魚(yú)優(yōu)化算法過(guò)程

鯨魚(yú)優(yōu)化算法（WhaleOptimization Algorithm，WOA）是一種基于群體的隨機(jī)優(yōu)化算法[13]，模擬座頭鯨的捕食行為，主要用于解決優(yōu)化問(wèn)題。

1.1 包圍獵物

鯨魚(yú)優(yōu)化算法中，最靠近獵物的鯨魚(yú)個(gè)體通常被視為當(dāng)前最優(yōu)解（即適應(yīng)度最好的個(gè)體），其他個(gè)體通過(guò)搜索接近最優(yōu)解，根據(jù)最優(yōu)解更新自身位置圍捕獵物，該過(guò)程表示為

X（t+1）=X_best（t）-A?D

D=∣CX_best（t）-X（t）∣

其中，t表示現(xiàn)階段迭代次數(shù)； X（t+1） 表示其他個(gè)體更新后的位置； X_best（t） 表示現(xiàn)階段全局最優(yōu)解的位置；D 表示最優(yōu)解與當(dāng)前鯨魚(yú)位置之間的距離。

A 和 C 表示搜索的系數(shù)為

A=2ar₁-a

C=2r₂

其中， r₁，r₂ 為0到1之間（包含0和1）的隨機(jī)數(shù)； a 是收斂因子，初始值為2，與迭代次數(shù)呈線性關(guān)系，隨著迭代次數(shù)的增加，最終線性下降為0。

a 與 Ψ_t 的關(guān)系為

其中， t_max 為最大迭代次數(shù)。

1.2 隨機(jī)搜索

圍捕獵物的過(guò)程中，鯨魚(yú)種群不斷更新自己的位置，隨機(jī)搜索可以增加跳出局部最優(yōu)解的概率。當(dāng)|A|gt;1 時(shí)，鯨魚(yú)采取隨機(jī)搜索的策略，表示為

其中， X_rand（t） 為隨機(jī)搜索的鯨魚(yú)位置。

此時(shí) D 為

D=∣CX_rand（t）-X（t）∣

1.3 螺旋氣泡網(wǎng)捕獵

當(dāng)鯨魚(yú)靠近獵物時(shí)，會(huì)以螺旋軌跡游向目標(biāo)，生成當(dāng)前位置和全局最優(yōu)解之間的路徑，更好地探索局部解空間，提高找到更優(yōu)解的概率，該過(guò)程表示為

其中，b為定義螺線形狀的常量系數(shù)； l 為 [-1，1] 內(nèi)的隨機(jī)數(shù)。

此時(shí) D 更新為

D=|X_best（t）-X（t）|

鯨魚(yú)圍捕獵物的過(guò)程中， Σ_P 為螺旋捕獵的概率， 1-?_P 為包圍獵物行為或隨機(jī)搜索行為的概率。

2 鯨魚(yú)優(yōu)化算法改進(jìn)

車載AGV硬件的計(jì)算資源相對(duì)有限，路徑規(guī)劃算法需在種群數(shù)量和迭代次數(shù)較低的情況下規(guī)劃最優(yōu)路徑。通過(guò)改進(jìn)鯨魚(yú)優(yōu)化算法，提高算法的計(jì)算速度和尋優(yōu)能力。

2.1 引入Tent混沌映射

標(biāo)準(zhǔn)鯨魚(yú)優(yōu)化算法中，鯨魚(yú)種群的初始位置使用偽隨機(jī)數(shù)生成，雖能使種群在空間中均有分布，但分布不夠均勻，導(dǎo)致算法尋優(yōu)效率低，收斂速度慢?；煦缬成渲貜?fù)性小，隨機(jī)性高，產(chǎn)生的隨機(jī)數(shù)能夠增加種群的多樣性，提高了算法的全局搜索性。特別是當(dāng)搜索空間有多個(gè)局部解時(shí)，算法更容易搜索到全局最優(yōu)解?；煦缬成浞N類繁多，其中 Tent 映射和Logistic 映射是當(dāng)下應(yīng)用較廣泛的混沌擾動(dòng)方程。侯志祥等[14]指出，相較于Logistic映射，Tent映射具有更優(yōu)的遍歷均勻性和更快的搜索速度，本文選用 Tent映射代替算法隨機(jī)數(shù)發(fā)生器進(jìn)行種群的初始化，Tent映射迭代過(guò)程為

其中， Z_i 為第 i 代混沌序列的當(dāng)前值； ρ 為控制參數(shù)，取 ρ=0.5 。

2.2 改進(jìn)收斂因子

收斂因子是從獵物勘探到捕獵過(guò)渡的控制因素。如式（5）所示，標(biāo)準(zhǔn)鯨魚(yú)優(yōu)化算法中，迭代過(guò)程線性收斂，但在自然界中，鯨魚(yú)的狩獵過(guò)程是復(fù)雜的，簡(jiǎn)單的線性變化無(wú)法有效表征狩獵過(guò)程。文獻(xiàn)[15]利用指數(shù)函數(shù)前期快速收斂的特點(diǎn)對(duì) Δ_a 進(jìn)行改進(jìn)，改進(jìn)的收斂因子 a 為

2.3 改進(jìn)搜索系數(shù) c

搜索系數(shù) c 是控制搜索速率的系數(shù)，見(jiàn)式（4），標(biāo)準(zhǔn)鯨魚(yú)優(yōu)化算法中， C 是[0，2]中的隨機(jī)數(shù)，會(huì)使鯨魚(yú)個(gè)體的搜索過(guò)程隨機(jī)性較高，易陷人局部最優(yōu)解，導(dǎo)致搜索精度不足?；谑剑?），將隨機(jī)數(shù) c 調(diào)整為根據(jù)迭代次數(shù)動(dòng)態(tài)變化的數(shù)值[16]，將 c 的原始系數(shù)2調(diào)整為2.8，增大種群個(gè)體間的差異及多樣性，避免算法陷入局部最優(yōu)，改進(jìn)后的搜索系數(shù) C 為

2.4引入自適應(yīng)非線性動(dòng)態(tài)慣性權(quán)重

慣性權(quán)重表示種群歷史搜索經(jīng)驗(yàn)對(duì)當(dāng)前搜索的影響，具有平衡種群搜索和捕獵的能力。偏大的慣性權(quán)重使算法具有較強(qiáng)的全局搜索能力，偏小的慣性權(quán)重使算法具有較強(qiáng)的局部搜索能力。引入一種后期較大，前期較小的自適應(yīng)非線性慣性權(quán)重 w ，提高算法搜索的速度以及準(zhǔn)確性。 w 值的計(jì)算為

由上式可知， ω 值隨迭代次數(shù)的增加而非線性增加。算法開(kāi)始迭代時(shí)，雖然 w 值較小，但此時(shí)目標(biāo)的模糊程度較高，對(duì)種群位置更新影響較小，算法迭代的后期，隨著 w 值增大，算法局部搜索能力增強(qiáng)，可更準(zhǔn)確快速的找到最優(yōu)解，有效提高算法收斂速度和尋優(yōu)能力，種群位置更新公式為

X（t+1）=wX_best（t）-AD，plt;0.5，|A|?1

X（t+1）=wX_rand（t）-AD，plt;0.5，|A|gt;

X（t+1）=Dexp（bl）cos（2πl(wèi)）+X_best（t），

2.5 算法流程

改進(jìn)鯨魚(yú)優(yōu)化算法流程描述如下：1）初始化該算法的所有參數(shù)，包括空間維度、種群規(guī)模、可搜索空間以及迭代次數(shù)；2）初始化種群的位置信息時(shí)加人Tent混沌映射，提高種群位置的復(fù)雜程度；3）參數(shù) a 由式（11）更新，參數(shù) A 由式（3）更新，參數(shù) w 由式（13）更新，參數(shù) c 由式（12）更新；4）當(dāng) ?lt;0.5 時(shí)，如果 |A|gt;1 ，則進(jìn)入步驟5，如果 |A|?1 ，則進(jìn)入步驟6；當(dāng) _/p? 0.5時(shí)，進(jìn)入步驟7；5）由式（15）對(duì)個(gè)體位置進(jìn)行更新，算法開(kāi)始進(jìn)行全局搜索；6）由式（14）對(duì)個(gè)體位置進(jìn)行更新，鯨魚(yú)個(gè)體采取包圍獵物策略；7）由式（16）對(duì)個(gè)體位置進(jìn)行更新，鯨魚(yú)個(gè)體采取螺旋氣泡網(wǎng)捕食策略；8）根據(jù)迭代結(jié)束的條件判斷當(dāng)前時(shí)刻算法是否已經(jīng)完成運(yùn)行，如果完成則輸出該算法的全局最優(yōu)解及鯨魚(yú)個(gè)體的位置信息，如果未完成則進(jìn)人步驟3繼續(xù)運(yùn)行。

STWOA的算法流程如圖1所示。

3 實(shí)驗(yàn)驗(yàn)證

3.1 迭代曲線與運(yùn)行時(shí)間測(cè)試

利用CEC 2O05 測(cè)試集多目標(biāo)優(yōu)化問(wèn)題測(cè)試函數(shù)中的F1O、F13函數(shù)對(duì) STWOA算法進(jìn)行迭代曲線和運(yùn)行時(shí)間測(cè)試，迭代次數(shù)為1000，種群數(shù)設(shè)置為50，結(jié)果如圖2和圖3所示。

由圖3可知，相比標(biāo)準(zhǔn)WOA，STWOA迭代曲線更優(yōu)，尋優(yōu)能力更強(qiáng)，F(xiàn)1O測(cè)試函數(shù)中，WOA運(yùn)算時(shí)間為0.144s，STWOA運(yùn)算時(shí)間為0.139s;F13測(cè)試函數(shù)中，WOA運(yùn)算時(shí)間為0.826 s，STWOA運(yùn)算時(shí)間為0.818s 。改進(jìn)后的算法在運(yùn)算時(shí)間表現(xiàn)上更優(yōu)，效率更高。

3.2 STWOA性能測(cè)試

使用MATLAB軟件驗(yàn)證STWOA性能，建立相同的地圖環(huán)境，對(duì)WOA以及STWOA進(jìn)行仿真，對(duì)比迭代次數(shù)與規(guī)劃路徑。2種算法均設(shè)置30個(gè)鯨魚(yú)個(gè)體，500次迭代次數(shù)。將地圖中的8個(gè)點(diǎn)設(shè)置為目標(biāo)點(diǎn)，使用 A* 算法獲得距離矩陣，分別用兩種優(yōu)化算法進(jìn)行路徑規(guī)劃。目標(biāo)點(diǎn)分布以及兩種算法規(guī)劃結(jié)果如圖4所示，圖中由藍(lán)色三角形表示的S點(diǎn)為路徑規(guī)劃的起始點(diǎn)，藍(lán)色圓形為路徑規(guī)劃的多個(gè)目標(biāo)點(diǎn)，黑色區(qū)域代表障礙物，藍(lán)色線條為算法規(guī)劃的路徑。

2種算法迭代曲線對(duì)比圖如圖5所示。

由圖5可知，WOA在迭代160次后收斂，規(guī)劃出的最短路徑為 142.5m ，STWOA在迭代110次后收斂，獲得的最短路徑為 123m 。經(jīng)過(guò)對(duì)比后可以看出，STWOA收斂速度更快，路徑規(guī)劃距離更短，能夠更好地解決多目標(biāo)路徑規(guī)劃問(wèn)題。

4結(jié)束語(yǔ)

針對(duì)傳統(tǒng)的路徑規(guī)劃算法無(wú)法較好地解決多目標(biāo)路徑規(guī)劃問(wèn)題，本文提出一種改進(jìn)鯨魚(yú)優(yōu)化算法。引入Tent混沌映射和自適應(yīng)非線性動(dòng)態(tài)慣性權(quán)重解決鯨魚(yú)優(yōu)化算法搜索精度不足，收斂速度慢的問(wèn)題，同時(shí)改進(jìn)收斂因子和搜索系數(shù)，并更新了種群位置公式，對(duì)比驗(yàn)證改進(jìn)后的算法與原始算法的收斂曲線、迭代曲線和規(guī)劃路線，解決了鯨魚(yú)優(yōu)化算法在多目標(biāo)點(diǎn)路徑規(guī)劃問(wèn)題中尋優(yōu)能力差、收斂時(shí)間慢的問(wèn)題。本文改進(jìn)的鯨魚(yú)優(yōu)化算法僅能解決單個(gè)機(jī)器人的多目標(biāo)路徑規(guī)劃問(wèn)題，后續(xù)研究中應(yīng)設(shè)計(jì)多個(gè)機(jī)器人多目標(biāo)路徑規(guī)劃算法，進(jìn)一步提高AGV的搬運(yùn)作業(yè)效率。

參考文獻(xiàn)

[1]董林威，高宏力，潘江．基于改進(jìn)粒子群算法的路徑規(guī)劃研究與應(yīng)用[J]．機(jī)械制造與自動(dòng)化，2023，52（6）：81－84.

[2]MO H W，XULF.Researchof biogeography particle swarm optimization forrobot path planning[J]. Neurocomputing，2015，148：91-99.

[3]邢協(xié)泓，黃坤榮，唐德文．基于改進(jìn)蟻群算法機(jī)器人路徑規(guī)劃[J]．機(jī)械管理開(kāi)發(fā)，2023，38（11）：1-4，9.

[4]WANG L H，TEN H K，YUG H.A Hybrid genetic algorithm for job shop scheduling problem[C]/28th Canadian Con-ference on Electrical and Computer Engineering，Halifax：IEEE，2Ol5：271-274.

[5]ARASH K，AHMADA.LDA-GWO： Utilizing LDA and gray wolf optimizer in diabetes diseases diagnosis[C]//20thCSI International Symposium on Artificial Intelligence and Signal Processing，Babol： IEEE，2024：1-7.

[6]BAS P，CAYREF. Achieving subspace or key security for WOA usingnatural or circular watermarking[J]. Workshopon Multimediaamp;. Security，2006：80-88.

[7]白響恩，孫廣志，徐笑鋒．基于改進(jìn)粒子群算法的海流環(huán)境下無(wú)人水面艇路徑規(guī)劃[J]．上海海事大學(xué)學(xué)報(bào)，2023，44（4）：1-7.

[8]李軍濤，侯星星，茆俊亞，等．時(shí)變海流干擾下深遠(yuǎn)海漁業(yè)無(wú)人船多目標(biāo)路徑規(guī)劃[J]．上海海洋大學(xué)學(xué)報(bào)，2023，32（5）：1090-1098.

[9]丁俊鋒，吳閩，吳振磊，等．無(wú)人機(jī)檢測(cè)橋梁多目標(biāo)點(diǎn)路徑規(guī)劃方法研究[J]．武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2024，48（2）：326-331.

[10]胡文興．基于改進(jìn)多目標(biāo)麻雀搜索算法的多船避碰決策[D]．大連：大連海事大學(xué)，2023.

[11] 朱玉．鯨魚(yú)優(yōu)化算法的改進(jìn)與應(yīng)用[D]．阜新：遼寧工程技術(shù)大學(xué)，2022.

[12] 王步偉，潘鵬程．基于改進(jìn)鯨魚(yú)優(yōu)化算法的移動(dòng)機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃[J]．機(jī)器人技術(shù)與應(yīng)用，2023（6）：14－19.

[13]武澤權(quán)，牟永敏．一種改進(jìn)的鯨魚(yú)優(yōu)化算法[J]．計(jì)算機(jī)應(yīng)用研究，2020，37（12）：3618－3621.

[14］侯志祥，成威，李鳳玲．基于混沌求偶螢火蟲(chóng)算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]．機(jī)床與液壓，2024，52（3）：55－59.

[15] 項(xiàng)清華，李立君，范子彥，等.基于改進(jìn)灰狼算法的智能除草機(jī)模糊避障研究[J].農(nóng)機(jī)化研究，2024，46（8）：50－56.

[16］王澤鵬．多目標(biāo)綠色車輛路徑規(guī)劃優(yōu)化研究[D]．廣州：廣東工業(yè)大學(xué)，2022.