基于改進的樽海鞘群算法求解機器人路徑規劃問題

劉景森 袁蒙蒙 李 煜

1(河南大學智能網絡系統研究所 河南開封 475004) 2(河南大學軟件學院 河南開封 475004) 3(鄭州科技學院信息工程學院 鄭州 450052) 4(河南大學管理科學與工程研究所 河南開封 475004)

近年來，移動機器人技術得到國內外普遍關注，它被認為是近百年來最重要的技術發明之一，對經濟和社會發展具有重要意義.如今，移動機器人已涉及人類生活的各個領域，在工業、農業、服務業、太空探索、醫療康復等方面有著廣泛應用.路徑規劃技術是移動機器人領域的關鍵、核心技術，它是機器人完成任務、抵達目標及智能化程度的重要標志，也是機器人導航中最重要的任務模塊之一.路徑規劃問題是指基于某種優化策略和約束條件，在移動空間中尋找一條從起始點到目標點的最優或近似最優的安全路徑，如何規劃出能夠平滑繞避障礙的高效路徑是一個極具挑戰性的研究課題.

國內外許多學者對這一領域不斷進行研究，取得了較為豐碩的成果.提出和使用了A*算法[1]、柵格法[2]、人工勢場[3]、可視圖法[4]、Voronoi路線圖搜索[5]、拓撲法[6]、模糊邏輯算法[7]、神經網絡[8-9]、強化學習[10]、深度學習[11]等多種具有各自不同機制特點的規劃技術及方法.雖然這些技術為求解移動機器人路徑規劃問題帶來了可行有效的方法，但在實際規劃中也都或多或少存在著一些較明顯的缺點和不足.如：A*算法在求解大規模空間場景路徑規劃時，計算量和規劃時間爆發性增加，所規劃的路徑中可能含有冗余點，估價函數也難于構造和選取.柵格法中算法性能過于依賴柵格劃分粒度的大小，劃分粒度小，則計算量和存儲量急劇增加，環境干擾增強，柵格劃分粒度大，則環境分辨率下降，難以規劃出有效路徑.人工勢場法面對復雜障礙環境時引力勢場較難規劃，容易使機器人路徑陷入停滯、抖動和局部最優，不適于進行大規模全局路徑規劃.可視圖法靈活性較差，路徑起始點或目標點一旦有變，可視圖就要重新構建，而對于復雜環境中障礙物頂點較多時，規劃時間也會急劇增加.Voronoi路線圖搜索方法所規劃的路徑完整性和安全性較好，但最優路徑質量和路徑光滑性較差，而且路線圖的繪制較為冗瑣，難以應用到大規模場景規劃中.拓撲法中拓撲網絡的建立和更新都比較復雜，且拓撲圖所包含的環境信息較少，難以識別和區分場景中存在的相似位置節點，對規劃出的路徑質量有不利影響.模糊邏輯算法的路徑規劃質量主要依賴于規則庫，規則更新比較頻繁，當輸入輸出量增長時，推理規則將會呈指數級增加.神經網絡方法在求解復雜障礙環境時，需要的網絡規模較大，而且各節點的閾值及之間的權值都在不斷調整更新，對機器人的計算能力要求較高.強化學習方法不需先驗知識，但要不斷從環境中得到反饋，需要學習的參數較多，其路徑規劃質量取決于根據環境特征構建的模型，更適用于比較簡單的結構化環境.深度學習方法是一類能提取數據中更高階、更抽象隱藏特征的多層神經網絡，在對復雜場景進行規劃時計算量龐大、收斂較慢，同時處理空間不透明，決策性較差.因此，隨著對移動機器人路徑規劃問題研究和應用的不斷深入，規劃場景的類型、規模和復雜程度不斷變化和增加，移動機器人的有限資源能力和高實時性要求，使得這些算法在規劃時間和路徑結果上往往難以得到滿意效果.最近幾年，通過大量的研究和實驗發現，元啟發式智能優化算法在求解機器人路徑規劃方面具有獨特優勢，并且多種智能優化算法已經成功應用于路徑規劃的搜索策略中，如蟻群算法[12-14]、人工蜂群算法[15-16]、模擬退火算法[17]、遺傳算法[18-20]、粒子群算法[21-22]等.但目前的應用還比較初期，使用的規劃算法多為幾個基礎老算法，而對于當前智能計算領域中機制更優、能力更強、性能更好的新興基礎和改進算法研究很少，路徑規劃過程中也存在著一些各自的問題.如遺傳算法對環境改變的適應性較差，搜索效率偏低；蟻群算法收斂速度較慢，有時會產生機器人停滯現象.故此，探索求解效率更高、環境適應性更好、尋優能力和魯棒性更強的優化算法路徑規劃方案，是這一領域研究者們持續追求的目標和方向.

樽海鞘群算法(salp swarm algorithm, SSA)作為一種具有較高認可度和影響力的新型啟發式智能優化算法，由Mirjalili等人[23]于2017年提出.SSA算法模擬了樽海鞘群體的鏈式覓食行為，機制清晰、參數簡單、尋優性能優越，已成為智能計算領域廣受關注和研究的重要算法，并在光伏系統優化[24]、圖像處理[25]、生物醫學信號處理[26]等諸多領域和問題的優化中得到成功應用.

但與此同時，SSA與其他元啟發式群智能優化算法類似，存在著全局搜索能力有所不足、尋優質量不夠穩定、有時易陷入局部極值等缺點，許多學者也針對這些問題提出了相應改進.Jia等人[27]在領導者和追隨者位置更新公式中分別引入交叉策略和萊維飛行軌跡，提高了算法的收斂速度和收斂精度.王夢秋等人[28]在算法中增加了自適應評估移動、鄰域最優引導以及反向學習擾動等策略，提高了樽海鞘群算法的尋優性能.Qais等人[29]基于高斯模型改進領導者公式中的參數，并在追隨者更新公式中引入隨機數，不但使算法更快收斂，而且增強了對高維函數的尋優能力，在變速風力發電機的應用中能夠獲得更高效率和更低成本.邢致愷等人[30]將萊維飛行機制應用于領導者位置更新，更好地平衡了算法的探索和挖掘能力，而后用改進算法進行圖像分割，取得了不錯結果.Ewees等人[31]將螢火蟲算法與樽海鞘群算法相結合，增強了SSA算法在局部區域的挖掘能力，并成功應用于平行機最小化調度問題.

為了更好地求解機器人全局路徑規劃問題、提高樽海鞘群算法的尋優性能、擴展其應用范圍，本文提出一種差異演化的寄生樽海鞘群算法(a parasitic salp swarm algorithm based on differential evolution, PDESSA).首先在領導者位置更新公式中引入上輪進化代對應領導者的位置信息，以增強算法的全局搜索繼承性，提升對局部最優點和局部極值區域的擺脫能力；同時還在該全局搜索公式中增加了隨進化代數自適應遞減的慣性權重，更合理有效地平衡了算法的前期廣泛探索和后期精細挖掘能力，提升求解性能和精度；最后將寄生-宿主雙種群的寄生行為和優勝劣汰機制引入算法的演化結構和策略中，進一步增強了樽海鞘個體的多樣性，提高了算法的搜索效率和擺脫局部極值能力.隨后，基于算法流程偽代碼和時間復雜度分析，證明了本文算法PDESSA與基本SSA算法時間復雜度相同.然后使用6種性能優越的代表性對比算法，在10個不同極值特征的標準測試函數上進行優化對比實驗，對測試結果的統計分析表明，PDESSA的尋優精度、收斂性能和求解穩定性相比于對比算法均有顯著優勢.最后，把改進后算法PDESSA結合三次埃爾米特插值方法，定義基于路徑上節點組合的個體編碼方式，構建能避開所有障礙并實現最小路徑的數學模型，進行機器人全局路徑規劃問題的優化求解.2種不同障礙環境下的路徑規劃算例求解實驗和對比分析顯示，融合三次埃爾米特差值的PDESSA算法對于解決機器人全局路徑規劃問題有著明顯的可行性和有效性，與其他對比算法和插值方法相比優越性顯而易見.

1 PDESSA算法

1.1 標準SSA算法

步驟1. 產生初始種群：

(1)

步驟2.計算種群中每個樽海鞘個體的目標函數值，并依據此適應度值將種群個體排序，適應度值最優的個體所在位置便是初始食物源.

步驟3.種群中前1/2個體稱為領導者，后1/2稱為追隨者.

步驟4.對樽海鞘領導者進行位置更新：

(2)

c1=2e-(4t/Max_iter)2,

(3)

其中，Max_iter為最大進化代數.

步驟5.對樽海鞘追隨者進行位置更新：

(4)

步驟6.對于更新后的樽海鞘個體進行逐維邊界處理，用各維邊界值替代個體在對應維度上的越界值，比較替換得到新的當前全局最優位置，并用其刷新食物源坐標.

步驟7.判斷迭代次數是否已達到最大進化代數.若是，就輸出得到的全局最優結果；若否，則轉回步驟3繼續執行尋優迭代過程.

1.2 改進領導者全局搜索方式

1.2.1 上代領導者位置信息的影響

在標準SSA的整個迭代過程中，占種群個體數量1/2的領導者，都是直接奔向當前全局最優解位置(食物源)的，這種位置更新方式會導致算法搜索過程中跳躍性過強，執行全局搜索的領導者多樣性較低，難以保證全局空間中搜索的充分性和完備性，易早熟收斂和滯困于局部最優.針對這一問題，本文將上輪迭代中對應的領導者信息引入領導者更新公式，使領導者既受到全局最優解的影響，又與上輪進化結果相關聯，既分享了整個樽海鞘群的全局進化成果，也保留了每個領導者的個體進化印記，從而提升了算法跳出局部極值區域找到全局最優的能力.改進事后的領導者位置更新：

(5)

1.2.2 非線性慣性權重

本文還在領導者位置更新公式中增加了自適應慣性權重w，權重值的大小控制著當前全局最優位置(食物源)對領導者位置更新的影響，從而決定了領導者的全局搜索能力.w的值隨著進化代數的遞增呈非線性遞減趨勢，迭代前期w比較大，領導者受食物源位置影響較強，從上代位置向較大空間范圍廣度搜索，而進化后期領導者已搜索至全局最優區域，此時較小的w取值能使領導者在上輪進化到達的位置附近精細挖掘，增強了算法全局和局部搜索的平衡性，提高了尋優能力和求解精度.w計算為

(6)

結合式(5)(6)，新的樽海鞘領導者位置更新：

(7)

其中，w的取值隨進化代數的不斷增加以雙曲正切函數的方式非線性減小，其值域為(0,1).自適應權重的使用，更好地平衡了算法在不同進化階段對領導者搜索能力的不同需求，使它們更有效、更合理地發揮領導作用，增強算法尋得全局最優解的可能和能力.

1.3 寄生和宿主雙種群

寄生是一種生物(寄生者)生活在其他生物(宿主)體表或體內，并從宿主中吸取營養以維持寄生者生存需要的現象.寄生者是生物界一種非常普遍的存在，如病毒、細菌、真菌等.依據寄生程度不同，可將寄生現象分為離開寄生無法獨立生活的專性寄生、既可寄生也可獨立生活的兼性寄生2種.

受寄生現象啟發，本文提出一種擁有雙種群及2套進化機制的改進算法結構，在算法演化過程中始終維持著宿主和寄生2個種群，每個種群的個體數量均為N.兩者的進化策略不同，獨立演化，其中宿主群使用標準SSA的位置更新公式，而寄生群則使用1.2節改進后的領導者更新方式.每隔一定進化代數M，就發生一次寄生群從宿主群吸收營養的寄生行為，即寄生群用P個適應度值最差的個體置換宿主群中前P個適應度值最好的個體.P是每次寄生行為的個體置換數，取值隨進化代數的增加自適應減小：

P=round(((Max_iter-t)/Max_iter)×N/4)，

(8)

其中，round()是四舍五入函數，用來對置換個數取整.隨著進化代數不斷增加，寄生行為也在不斷發生，宿主群中位置較優的個體(營養)不斷被寄生群吸走，寄生群已經得到了較多營養，因此交換個數也在不斷遞減，直到進化終止，寄生行為也隨之徹底結束.

為了保持宿主種群的個體質量和活躍性，每一次寄生行為后還要對宿主種群中一定比例的Q個較差樽海鞘進行隨機淘汰，替換以搜索空間中產生的隨機個體Q:

Q=round((0.5+rand()/2)×N/4).

(9)

宿主群進行優勝劣汰的步驟為：

fori=1:Q

ifrand()>0.5

淘汰替換當前個體;

end if

end for

通過對宿主種群中最差的Q個樽海鞘個體實行隨機劣汰，有效提升了宿主群的個體質量和多樣性，降低了算法陷入局部極值的可能性.同時這一策略也很好地契合了自然進化和優化搜索機制中的優勝劣汰思想，較好地解決了由于宿主群中高質量樽海鞘個體持續流失減少而導致種群活躍度較低、易陷入低效搜索的問題.

2 PDESSA的流程與時間復雜度

2.1 PDESSA流程偽代碼

算法1.PDESSA.

begin

設置算法中基本參數的初值;

計算寄生群和宿主群中樽海鞘個體的初始位置;

計算2個種群中個體的適應度值;

設置宿主群、寄生群的食物源位置;

while (t≤Max_iter)

由式(6)計算w;

fori=1 toN

if (i≤N/2)

forj=1 toD

由式(7)對寄生群中的領導者進行位置更新;

end for

else

由式(4)對寄生群中的追隨者進行位置更新；

end if

end for

fori=1 toN

if (i≤N/2)

forj=1 toD

由式(2)更新宿主群的領導者位置;

end for

else

由式(4)更新宿主群的追隨者位置;

end if

end for

if mod (t,M)==0

由式(8)執行寄生行為;

由式(9)計算優勝劣汰個體數Q;

對宿主群中Q個較差個體進行隨機劣汰替換;

end if

fori=1 toN

對2個種群更新后的樽海鞘個體進行邊界

處理;

計算宿主群、寄生群中個體的適應度值;

對宿主群、寄生群的食物源位置進行更新;

end for

t=t+1

end while

end

2.2 PDESSA時間復雜度分析

評價一個優化算法的優劣需要兼顧尋優性能和時間復雜度，時間復雜度是考量和評估算法運行效率的重要指標.下面對PDESSA的時間復雜度進行分析.

在文獻[32-33]中,我們都對標準SSA的時間復雜度做了詳細分析.設算法的總迭代次數為Max_iter，種群規模為N，個體維度為n.

在SSA算法的初始化階段，設初始化基本參數的時間為η0，產生個體位置中每一維初值的均勻分布隨機數的時間為η1，由目標函數計算每個個體適應度值的時間為f(n)，根據適應度值對種群個體進行排序并由此找到初始代全局最優個體(食物源位置)的時間為η2，則這一階段的時間復雜度為

T1=O(η0+N(nη1+f(n))+η2)=O(n+f(n)).

進入迭代循環，總迭代次數為Max_iter.

算法中樽海鞘領導者的數量為N/2.在更新領導者位置階段，c1的值在同輪迭代中保持不變，c2和c3則是隨個體和維度的變化而改變，設由式(3)求c1的時間為η3，c2和c3是均勻分布隨機數，其生成時間均同η1.在式(2)中，2種公式的計算時間完全一致，由式(2)更新每個個體每維位置的時間為η4，則該階段的時間復雜度為

T2=O(η3+(N/2)n(η1+η1+η4))=O(n).

算法中樽海鞘追隨者數量是其余的N/2.在追隨者位置更新階段，設由式(4)對每個追隨者位置進行更新的時間為η5，則此階段的時間復雜度為

T3=O((N/2)η5).

在邊界處理和更新食物源階段，設每一個體做邊界處理的時間為η6，求個體適應度值的時間仍為f(n),按適應度值與食物源位置進行比較替換的時間為η7，則這一階段的時間復雜度為

T4=O(N(η6+f(n)+η7))=O(f(n)).

因此標準SSA的總時間復雜度為

T(n)=T1+Max_iter(T2+T3+T4)=O(n+f(n)).

在本文提出的PDESSA算法中，種群的規模、個體維數、初始化基本參數的時間、產生一個均勻分布隨機數的時間、計算目標函數適應度值的時間、按個體適應度值對種群中個體排序并得到當前最優位置(食物源)的時間均與標準SSA相同.由于PDESSA中包含寄生群和宿主群2個種群，因此PDESSA在初始化階段的時間復雜度為

進入迭代循環，總迭代次數為Max_iter.

算法中寄生、宿主2個種群的領導者數量均為N/2，而追隨者數量則為各自種群中剩余的N/2.

對于寄生群，設由式(6)求w的時間為t1，其值在同輪迭代中保持不變.在寄生群領導者位置更新階段，設由式(7)更新每個領導者位置中每一維度的時間為t2，則這一階段的時間復雜度為

在寄生群追隨者位置更新階段，由式(4)更新每個追隨者位置的時間與標準SSA相同，則這一階段的時間復雜度為

對于宿主群，所有個體(領導者、追隨者)的位置更新都分別與標準SSA相同，執行這些操作所花費的時間也相同，故而該階段的時間復雜度為

在寄生行為和宿主群優勝劣汰階段，設計算個體適應度值的時間為f(n)，按適應度值對樽海鞘個體進行排序的時間為t4，此時種群數為2，故執行寄生行為和宿主群優勝劣汰2步操作的總個體數為基本算法的2倍.設由式(8)計算寄生行為個體交換量P的時間為t5,交換寄生群和宿主群中P個個體的時間為t6，由式(9)計算宿主群中劣汰率Q的時間為t7，隨機新個體并替換劣質舊個體的時間為t8，則在2個種群間發生一次寄生并對宿主種群進行一次劣汰的時間為

在邊界處理和食物源更新階段，對每個個體進行邊界處理、由目標函數計算個體適應度值、按個體適應度值比較替換全局最優解位置(食物源)的時間都與標準SSA相同，而且對寄生群和宿主群的處理完全一致，因此該階段的時間復雜度為

由此得出，PDESSA算法總的時間復雜度為

與標準SSA相比，本文算法PDESSA的執行時間有所增長，但時間復雜度保持不變，PDESSA的機制改進沒有降低算法的運行效率.

3 PDESSA函數優化仿真實驗

為測試本文算法PDESSA的優化性能，使用10個具有不同極值特征的復雜標準測試函數，將本文提出的PDESSA算法與基本樽海鞘群算法(SSA)、改進樽海鞘群算法(ISSA)[28]、基于萊維飛行的樽海鞘群算法(LSSA)[30]、標準粒子群算法(PSO)[34]和PPSO(phasor particle swarm optimization)[35]共6種算法，分別在30維和100維上進行對比測試.其中，ISSA和LSSA算法是2個代表性SSA改進算法；PSO是求解機器人路徑規劃問題最常用和性能優越的群智能算法之一；PPSO是一種新的PSO改進算法，有效提高了PSO算法的收斂性和魯棒性.所有6種算法均在相同軟、硬件條件下獨立運行，環境為Windows8、處理器Intel i5-3337@1.8 GHz，內存為4 GB，編程環境為Matlab R2014a.算法參數方面，4種樽海鞘算法無需另外設置參數，而PSO，PPSO算法的慣性權重w=0.8，學習因子c1和c2均為1.5，都與各自算法的原文獻和源代碼保持一致.

3.1 測試函數

本文使用的10個不同尋優特性的典型復雜標準測試函數如表1所示.其中f1(x)～f2(x)為多維單峰函數，這類函數只有一個全局最優值，沒有局部極值，常用于驗證算法的收斂速度與求解精度；f3(x)～f10(x)為多維多峰函數，這類函數不僅具有大量的局部極值，而且最好的局部極值點與全局最優點距離較遠，主要用來測試算法擺脫局部極值的能力及全局、局部搜索的平衡性.

Table 1 Test Function表1 測試函數

3.2 尋優精度分析

為測試和檢驗PDESSA的尋優性能，將f1(x)～f10(x)的維度分別設置為d=30,100進行極值優化實驗.基于測試的客觀性和充分性，各算法在相同環境下獨立運行50次，種群規模N=30，最大進化代數Max_iter=1 000.表2統計了30維和100維下各算法運行50次得到的尋優結果的最佳值、平均值和方差，其中各項對應的最優值均做了加粗顯示.

觀察表2可以看出，除了很少數的個別情況外，PDESSA算法求解不同維度下各個函數的尋優精度和穩定性都明顯優于其他5種對比算法，且在全部10個測試函數的所有維度上，50次尋優結果的最佳值、平均值和方差皆優于基本SSA算法，顯示出本文算法對于SSA機制改進的顯著性和有效性.

在30維條件下，對于2個復雜單峰函數f1(x)～f2(x)，PDESSA的最佳值、平均值和方差都明顯優于其他5種對比算法，求解優勢突出.對于8個復雜多峰函數f3(x)～f10(x)，PDESSA的最佳值、平均值和方差也全部優于其余5種算法，尤其是對于函數f6(x)，PDESSA的最佳值、平均值和方差均為理論最優值，求解能力十分出色.

Table 2 Comparison of Optimization Results of 6 Algorithms Under Fixed Iteration Times表2 6種算法在固定迭代次數下的尋優結果比較

續表2

在100維條件下，由于維數增加6種算法的尋優精度都會有所下降，但PDESSA仍然表現出優越的求解能力和維度適應性，尋優結果受維數變化影響較小，尋優精度優于其他5種算法.對于2個單峰函數f1(x)～f2(x)，PDESSA的最佳值、平均值和方差都遠優于其他5種算法，求解能力依然出色.對于多峰函數f3(x)～f7(x)和f9(x)～f10(x)，PDESSA在這7個函數上得到的最佳值、平均值和方差都優于其他5種算法，特別是對于函數f6(x)，PDESSA尋優結果的最佳值、平均值和方差仍是理論最優值，求解效果優越且穩定.對于函數f8(x)，PDESSA的方差略遜于PPSO算法但優于其余4種算法，而最佳值和平均值則都是6種算法中最好的.

以上求解結果和分析表明，無論是單峰、多峰還是低維、高維，相比于5種求解性能較為優越的代表性對比算法，本文算法PDESSA整體呈現出較好的尋優性能，求解精度和穩定性更加出色，很好地解決了SSA算法在求解復雜函數全局優化時易陷入局部極值、尋優性能不穩定、求解精度有時不高的問題.

3.3 收斂曲線分析

一個算法的收斂曲線顯示了該算法在尋優過程中收斂速度的變化及陷入局部極值的次數，通過收斂曲線可以直觀地展現和對比出算法尋優性能的優劣.圖1～10給出了6種算法在d=100維時，求解10個復雜標準測試函數f1(x)～f10(x)的收斂曲線對比圖.

Fig. 1 Convergence curve of f1(x) function圖1 f1(x)函數的收斂曲線

Fig. 2 Convergence curve of f2(x) function圖2 f2(x)函數的收斂曲線

Fig. 3 Convergence curve of f3(x) function圖3 f3(x)函數的收斂曲線

Fig. 4 Convergence curve of f4(x) function圖4 f4(x)函數的收斂曲線

Fig.5 Convergence curve of f5(x) function圖5 f5(x)函數的收斂曲線

Fig. 6 Convergence curve of f6(x) function圖6 f6(x)函數的收斂曲線

Fig. 7 Convergence curve of f7(x) function圖7 f7(x)函數的收斂曲線

Fig. 8 Convergence curve of f8(x) function圖8 f8(x)函數的收斂曲線

Fig. 9 Convergence curve of f9(x) function圖9 f9(x)函數的收斂曲線

Fig. 10 Convergence curve of f10(x) function圖10 f10(x)函數的收斂曲線

圖1～10清晰展現出PDESSA及5種對比算法在整個迭代過程中當前最優適應度值的變化趨勢對比.可以看出，相較于其他5種算法，PDESSA的收斂速度更快，收斂曲線總體比較光滑，陷入局部極值的次數少，尋優能力更強.

在求解高維復雜單峰函數時，對于圖1和圖2，SSA，ISSA，LSSA，PSO和PPSO算法從迭代開始曲線的下降就極其緩慢，收斂基本陷于停滯狀態；而PDESSA算法從迭代開始到結束，始終保持較快下降趨勢，最終收斂于理論最優值附近.

在求解高維復雜多峰函數時，對于圖3和圖8，SSA，ISSA和LSSA算法從迭代開始到結束收斂速度一直很慢，PSO和PPSO算法前期收斂速度略快于PDESSA，但600代后收斂速度已全部慢于PDESSA算法.對于圖4和圖7，PDESSA算法從迭代開始到結束都以很快的速度收斂，而其他5種算法從迭代進化的早期便陷于局部極值中無法擺脫.對于圖5，PDESSA在進化前期也曾落入局部最優，但隨著迭代的不斷進行能在后期成功擺脫，并以較快速度收斂到全局最優解附近；而SSA，ISSA和LSSA算法的收斂速度始終很慢；PSO算法的收斂速度雖然在進化早期快于PDESSA，但100代時陷入局部極值無法跳出；PPSO算法在迭代前期收斂速度略快于PDESSA，但在100代之后就明顯慢于PDESSA算法，到500代時更是陷入局部極值無法跳出.對于圖6，PSO算法在進化初期便早早落困于局部最優無法擺脫；而PPSO，SSA，ISSA，LSSA算法的收斂速度則一直很慢，未能收斂到全局最優解；PDESSA前期雖然也曾受困于局部最優，但后期不但可以成功脫離，而且還能以較快速度收斂至理論最優解.對于圖9和圖10，PDESSA進化初期同樣困滯于局部最優，但400代時成功擺脫，并以較快速度收斂，直至迭代結束到達全局最優解附近，而其他5種算法則是從迭代初期就陷入局部極值無法跳出.

由實驗結果和分析可知，本文提出的PDESSA算法具有較為出色的優化性能，其尋優精度、收斂速度、求解結果的穩定性都優于其他5種性能優越的代表性對比算法.

4 PDESSA算法與三次埃爾米特插值方法相結合求解機器人路徑規劃問題

4.1 三次埃爾米特插值方法

在求解插值問題時，為構建更貼近契合于原函數的插值函數，我們要求在節點處，不僅原函數和插值多項式的函數值相同，兩者的一階或更高階導數值也相同，這種插值就是埃爾米特插值方法，其插值多項式稱為埃爾米特插值多項式.

設在節點a≤x0

H(xi)=yi，

(10)

H′(xi)=mi(i=0,1,…,n)，

(11)

因插值節點一共有n+1個，當給出2n+2個條件時，便可唯一確定一個次數不超過2n+1的多項式H2n+1(x)=H(x)，其表達式的形式為

H2n+1(x)=a0+a1x+…+a2n+1x2n+1.

(12)

在由基函數構造埃爾米特插值多項式時，先求出插值基函數αi(x),βi(x)(i=0,1,…,n)，因而共得到2n+2個基函數，每個基函數為一個2n+1次多項式，并且滿足:

(13)

(14)

βi(xk)=0，

(15)

(16)

由式(10)～(16)條件構造出的埃爾米特插值多項式為

(17)

作為分段式插值方法，埃爾米特插值在區間內生成一系列中間插值節點，從而構造出一條較光滑曲線.將埃爾米特插值方法融合到機器人全局路徑的規劃構建上，能夠使機器人在移動過程中更加自然地避開障礙，形成更符合動力學原理特性的平滑路徑.

三次埃爾米特插值問題的數學描述為：設y=f(x)是[a,b]上的實函數，x0,x1是[a,b]上相異的2點，且x0

(18)

H3(x)稱為三次埃爾米特插值多項式，式(18)即為此問題的插值條件.

4.2 構建模型與適應度函數

4.2.1 求解問題的數學模型與算法編碼方式

為了將智能算法更好地應用于移動機器人全局路徑規劃問題，充分發揮算法的優化作用，在建立該問題的數學模型時做3個假設：

1) 機器人的移動場景為2維有限空間；

2) 移動空間中任意分布著有限個靜態障礙物，這些障礙物的位置可知且能以外切圓表示，無需考慮其高度；

3) 機器人被看作質點，其大小形狀可以忽略.

基于算法處理的效率和統一性以及所規劃出機器人路徑的光滑性考慮，將各種不同形狀的障礙物抽象為其各自的外切圓，以圓形表示.模型中正方形表示機器人的路徑起點、終點，圓形區域為障礙區，其余為可移動區域.本文將基于這類環境和場景，進行移動機器人的全局路徑規劃，而這樣的環境也能夠與無人車間、智能倉庫、特殊環境作業等許多實際應用場景相吻合.

在該問題模型的基礎上，可使用本文算法PDESSA或其他群智能優化算法，求解出一條最優路徑，而與三次埃爾米特插值方法相結合，各插值段的轉折連接點即為路徑節點.在本文的編碼策略中，1條路徑映射為算法中的1個個體，個體位置的每一維便依次對應于所映射路徑的各節點坐標，即1個d維個體的1個維度值由1個路徑節點的坐標數組(x,y)構成，而維數d則是路徑上所有節點的個數.

設1條路徑上共有m個節點，各節點的坐標為(xnode1,ynode1)，(xnode2,ynode2),…,(xnodem,ynodem)，路徑的起點、終點坐標為(x0,y0),(xn+1,yn+1)，用三次埃爾米特方法對各節點間的連線進行插值，共產生n個插值點，坐標可表示為(xi,yi),i=1,2,…,n，那么由該路徑的起點、包含m個路徑節點在內的n個插值點、路徑終點共n+2個有序點，即(xi,yi),i=0,1,…,n+1構成的連線就是機器人的移動路線.

4.2.2 構建目標函數

目標函數用于求解機器人全局路徑問題的最優解，其適應度值便是評價求解結果和性能的量化值.評判所得到的1個路徑是否最優，需要滿足：

1) 不經過任何障礙物區域(沒有碰撞)；

2) 產生的路徑最短.

基于此2條件所構造的機器人路徑規劃問題適應度函數為

F=L(1+ρ×Z),

(19)

其中，懲罰系數ρ的值要足夠大，以起到若發生碰撞便死刑懲罰的作用，本文取ρ=100，從而排除進化求解過程中那些穿越障礙物圓形區域的路徑.L為從起點、每個插值點直到終點的序列點距離和，即路徑長度，其計算為

(20)

其中，xi,yi和xi+1,yi+1分別是第i個和第i+1個插值點的橫坐標與縱坐標.

Z用來判斷插值點是否位于障礙物區域，即該路徑是否經過障礙物，其初值為0，計算Z的代碼段為：

fork=1:CN

Pk=max(1-Dk/CRk,0)；

Z=Z+mean(Pk)；

end for

其中，x，y分別是路徑上全部插值點橫、縱坐標的集合，CN是障礙數，CXk和CYk分別是障礙k的圓心橫、縱坐標，CRk則是障礙k的圓形區域半徑.Dk用于存儲障礙k圓心到路徑上各插值點的距離值.Pk為標志數組，用來判別每個插值點是否位于障礙k的圓形區域內，當路徑中存在落入障礙區域的插值點時，說明路徑未能避開障礙，此時Pk中對應于該插值點的標志值為正，有Z>0；否則數組Pk的所有元素都是0，有Z=0，這說明此路徑沒有經過任一障礙區域，所對應的目標函數適應度值為L.

4.3 機器人路徑規劃

為驗證PDESSA算法對于機器人全局路徑規劃的有效性，將第3節的6種算法在相同環境下進行算例求解仿真實驗，從而全面檢驗和分析PDESSA及5種對比算法分別與三次埃爾米特插值相結合，求解這一問題的尋優結果和性能.

為保障比較的公平性，6種算法均獨立運行求解過程30次，種群規模N=50，最大迭代次數Max_iter=100.各算法的運行環境及參數設置也都與第3節相同，即參數值與各自算法的源文獻和源代碼保持一致.

4.3.1 基于三次埃爾米特插值方法的算法對比

1) 算例1：普通場景下6種對比算法的求解實驗分析.

Fig. 11 Space scene diagram of case 1圖11 算例1的空間場景圖

算例1為普通障礙場景，機器人移動的起點和終點坐標分別是(0.0,0.0)和(6.0,6.0)，場景空間中障礙物的個數為6，將路徑節點數設置為3，插值點個數設置為400.圖11給出了機器人移動時的空間場景，表3則列出了此場景中各個障礙物的位置與大小.

Table 3 Location and Size of Obstacles in the Scene of Example 1表3 算例1中各障礙物的位置與大小

表4統計了對于普通障礙場景的算例1，6種算法30次求解得到的路徑長度最佳值、平均值和方差.圖12給出了本文算法PDESSA求解規劃出的一條機器人移動路線.

Table 4 Solution Results of the Six Algorithms for Example 1表4 6種算法對算例1的求解結果

Fig. 12 Path planning curve of case 1 by PDESSA圖12 算例1中PDESSA規劃的路徑曲線

2) 算例2：復雜場景下6種算法的求解實驗分析.

算例2為較復雜障礙場景，機器人移動的起點和終點坐標分別是(0.0,0.0)和(6.0,6.0)，場景空間中障礙物的個數為10，將路徑節點數設置為5，插值點個數設置為600.圖13給出了機器人移動時的空間場景，表5則列出了此場景中各個障礙物的位置與大小.

Fig. 13 Space scene diagram of case 2圖13 算例2的空間場景圖

Table 5 Location and Size of Obstacles in the Scene of Example 2

表6統計了對于較復雜障礙場景的算例2，6種算法30次求解得到的路徑長度最佳值、平均值和方差.圖14給出了本文算法PDESSA求解規劃出的一條機器人移動路線.

Table 6 Solution Results of the Six Algorithms for Example 2表6 6種算法對算例2的求解結果

Fig. 14 Path planning curve of case 2 by PDESSA圖14 算例2中PDESSA規劃的路徑曲線

表4和表6分別統計了6種算法各自獨立運行30次來求解2種不同復雜程度場景的算例1和算例2，規劃出的路徑長度的最佳值、平均值和方差.由表4和表6中的統計數據可以看出，無論對于普通亦或是較為復雜的障礙場景，PDESSA所求出的路徑長度平均值和方差都是6種算法中最小的，這說明其求解效果和穩定性都更為出色.在最佳值方面，對于普通障礙場景，本文算法PDESSA的最佳值也是6種算法中最優的；對于較為復雜的障礙物環境，本文算法PDESSA的最佳值與SSA幾乎相同，明顯優于其他4種算法.由于PDESSA算法的最佳值始終名列前茅，而且平均值和方差更是優于其他5種對比算法，充分說明了其求解結果的有效性.同時，觀察圖12和圖14也可看出，由PDESSA算法規劃出的路徑曲線平滑自然且能有效繞避空間中存在的各個障礙.實驗結果和分析可知，在求解機器人路徑規劃問題上，相比于其他5種對比算法，PDESSA算法顯現出明顯的優越性，并具有更好的可靠性.

4.3.2 不同插值方法的對比和選擇

1) 基于三次樣條插值的算例求解對比實驗

在求解移動機器人全局路徑規劃時，本文中采用了將PDESSA和其他群智能優化算法與三次埃爾米特插值方法相結合的方案，而與此同時，三次樣條插值也是求解這一類問題時常被用到的方法.三次樣條插值也是一種經典的分段式插值方法，能夠通過一系列基于三次多項式的插值區間，構造出一條平滑流暢的曲線，該方法已被成功地應用到求解移動機器人全局路徑規劃問題中[36-37].下面在相同對比算法、參數設置、算例場景和實驗條件下，將這6種算法分別與三次樣條插值相結合，求解不同障礙場景下的機器人全局路徑規劃問題，如算例1和算例2，并與本文融合三次埃爾米特插值的求解方案進行對比分析，以便選擇出一種更具優勢和有效性的分段式插值方法，從而更好地與PDESSA等群智能優化算法相結合，高效、優越地求解移動機器人全局路徑規劃問題.

表7和表8分別統計了6種算法融合三次樣條插值方法，各自獨立運行30次，求解普通和較復雜障礙場景的算例1和算例2，得到的路徑長度的最佳值、平均值和方差.

Table 7 Solution Results of the Six Algorithms Based on Cubic Spline Interpolation for Example 1表7 6種基于三次樣條插值方法的算法對算例1的求解結果

Table 8 Solution Results of the Six Algorithms Based on Cubic Spline Interpolation for Example 2表8 6種基于三次樣條插值方法的算法對算例2的求解結果

觀察表7和表8中的統計數據可以很清楚地看出，對于2種不同復雜程度障礙場景的算例1和算例2，PDESSA算法與三次樣條插值方法相結合所求得的路徑長度的平均值和方差依然全部優于其他5種算法.在最佳值方面，對于算例1，本文算法PDESSA的最佳值也是6種算法中最優的；對于算例2，本文算法PDESSA的最佳值與ISSA，SSA算法基本相當，明顯優于另外3種算法，而平均值和方差更是顯著優于ISSA，SSA和其他對比算法，充分說明了其求解路徑長度值的優越性和穩定性.

這些結果再次證明了本文算法PDESSA在求解移動機器人全局路徑規劃問題上，具有出色的穩定性和良好的適用性.

2) 基于2種不同插值方法得到的路徑長度

將表4，6與表7，8中統計的路徑長度數據進行比較可以看出，在求解普通障礙場景的算例1時，對于PSO算法，用三次埃爾米特插值方法所求出的路徑長度最佳值、平均值和方差都優于用三次樣條插值方法求出的值；對于ISSA和SSA算法，用三次埃爾米特插值方法求出的路徑長度的平均值和方差都優于用三次樣條插值方法；對于LSSA，其采用三次埃爾米特方法求出的路徑長度最佳值和平均值更優；只有PPSO算法使用三次埃爾米特方法求出的值稍遜于三次樣條插值方法；對于本文算法PDESSA，用三次埃爾米特插值方法求出的路徑長度的最優值和方差都優于三次樣條插值方法.這些結果表明用三次埃爾米特插值方法求出的路徑長度并不是全都優于三次樣條插值方法，但整體而言結果較優，而且每次運行求出的路徑差異性較小，求解性能更穩定可靠.

對于較復雜的障礙場景，基于三次埃爾米特插值的求解方案優勢更加顯著，其中SSA，PSO，PPSO以及本文算法PDESSA使用三次埃米爾特方案求解算例2得到的路徑長度的最佳解、平均值和方差，全都優于該算法采用三次樣條插值的求解方案，使用三次埃爾米特插值的求解效果明顯更為出色.

通過以上測試結果的比較和分析，可以清楚地看到對于不同復雜程度的障礙場景，融合三次埃爾米特插值的求解方案規劃出的路徑長度，跳躍性較小，穩定性更強，整體更為可靠，尤其是在較為復雜的障礙環境下，采用三次埃爾米特插值的方案求解效果更佳，優勢更突顯.

3) 采用2種不同插值方法的算法平均執行時間

表9統計了6種算法分別融合引入三次樣條、三次埃爾米特2種不同的插值方法，各自獨立運行30次求解算例1和算例2，得到的算法平均執行時間.

由表9可以看出，在求解算例1和算例2時，由于6種算法的尋優機制各異，這些算法的平均執行時間也各不相同.但當6種算法融合三次埃爾米特插值方法時，求解各算例所需的平均執行時間都小于該算法融合三次樣條插值方法時求解同一算例的平均執行時間，顯然前者的執行時間更短、效率更高.

由關于2種不同插值方式下路徑長度和算法執行時間的實驗結果與分析可知，采用融合三次埃爾米特插值的求解方案，求解移動機器人全局路徑規劃問題時，所規劃出路徑的長度整體更短也更加穩定，

Table 9 Average Execution Time of Algorithms with Different Interpolation Methods表9 采用不同插值方法的算法平均執行時間 s

并且執行算法所花費的平均時間也更少.因此，本文采用將三次埃爾米特插值方法與PDESSA算法相結合，求解移動機器人全局路徑規劃問題的方案是合理而且有效的.

5 結 論

為了更好地求解移動機器人全局路徑規劃問題，進一步拓展樽海鞘群算法的應用空間，本文針對樽海鞘群算法所存在的不足進行改進.首先在樽海鞘領導者位置更新公式中，引入上一代位和慣性權重，然后在整個算法的進化機制中引入具有不同進化機制的寄生-宿主雙種群思想和生物學中的優勝劣汰思想，增強了算法的全局搜索能力，平衡了領導者廣度搜索與深度挖掘之間的平衡，提高了對于局部極值的擺脫能力.而后通過對6種算法在10個不同特征測試函數上進行對比分析，仿真結果證明改進算法具有可靠的尋優能力.最后將改進算法與埃爾米特插值方法相結合，定義了編碼方式，構造了以繞避障礙和最短路徑為目標的適應度函數，求解機器人路徑規劃問題.通過6種算法在2種不同障礙環境下進行對比實驗，驗證了本文算法對于求解機器人路徑規劃問題的優越性.下一步將繼續改進樽海鞘群算法的尋優能力和性能，進一步增強算法的穩定性和適應性，將其應用到更多復雜實際問題的優化求解中.

作者貢獻聲明：劉景森提出算法機制和應用方案，負責并參與論文的寫作和修改；袁蒙蒙參與論文的撰寫，提出算法和方案的實現代碼，測試和分析實驗數據；李煜參與論文的寫作與修改，對研究方案進行理論分析.