基于改進(jìn)的樽海鞘群算法求解機(jī)器人路徑規(guī)劃問(wèn)題

劉景森 袁蒙蒙 李 煜

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

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

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

樽海鞘群算法(salp swarm algorithm, SSA)作為一種具有較高認(rèn)可度和影響力的新型啟發(fā)式智能優(yōu)化算法，由Mirjalili等人[23]于2017年提出.SSA算法模擬了樽海鞘群體的鏈?zhǔn)揭捠承袨?，機(jī)制清晰、參數(shù)簡(jiǎn)單、尋優(yōu)性能優(yōu)越，已成為智能計(jì)算領(lǐng)域廣受關(guān)注和研究的重要算法，并在光伏系統(tǒng)優(yōu)化[24]、圖像處理[25]、生物醫(yī)學(xué)信號(hào)處理[26]等諸多領(lǐng)域和問(wèn)題的優(yōu)化中得到成功應(yīng)用.

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

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

1 PDESSA算法

1.1 標(biāo)準(zhǔn)SSA算法

步驟1. 產(chǎn)生初始種群：

(1)

步驟2.計(jì)算種群中每個(gè)樽海鞘個(gè)體的目標(biāo)函數(shù)值，并依據(jù)此適應(yīng)度值將種群個(gè)體排序，適應(yīng)度值最優(yōu)的個(gè)體所在位置便是初始食物源.

步驟3.種群中前1/2個(gè)體稱為領(lǐng)導(dǎo)者，后1/2稱為追隨者.

步驟4.對(duì)樽海鞘領(lǐng)導(dǎo)者進(jìn)行位置更新：

(2)

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

(3)

其中，Max_iter為最大進(jìn)化代數(shù).

步驟5.對(duì)樽海鞘追隨者進(jìn)行位置更新：

(4)

步驟6.對(duì)于更新后的樽海鞘個(gè)體進(jìn)行逐維邊界處理，用各維邊界值替代個(gè)體在對(duì)應(yīng)維度上的越界值，比較替換得到新的當(dāng)前全局最優(yōu)位置，并用其刷新食物源坐標(biāo).

步驟7.判斷迭代次數(shù)是否已達(dá)到最大進(jìn)化代數(shù).若是，就輸出得到的全局最優(yōu)結(jié)果；若否，則轉(zhuǎn)回步驟3繼續(xù)執(zhí)行尋優(yōu)迭代過(guò)程.

1.2 改進(jìn)領(lǐng)導(dǎo)者全局搜索方式

1.2.1 上代領(lǐng)導(dǎo)者位置信息的影響

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

(5)

1.2.2 非線性慣性權(quán)重

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

(6)

結(jié)合式(5)(6)，新的樽海鞘領(lǐng)導(dǎo)者位置更新：

(7)

其中，w的取值隨進(jìn)化代數(shù)的不斷增加以雙曲正切函數(shù)的方式非線性減小，其值域?yàn)?0,1).自適應(yīng)權(quán)重的使用，更好地平衡了算法在不同進(jìn)化階段對(duì)領(lǐng)導(dǎo)者搜索能力的不同需求，使它們更有效、更合理地發(fā)揮領(lǐng)導(dǎo)作用，增強(qiáng)算法尋得全局最優(yōu)解的可能和能力.

1.3 寄生和宿主雙種群

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

受寄生現(xiàn)象啟發(fā)，本文提出一種擁有雙種群及2套進(jìn)化機(jī)制的改進(jìn)算法結(jié)構(gòu)，在算法演化過(guò)程中始終維持著宿主和寄生2個(gè)種群，每個(gè)種群的個(gè)體數(shù)量均為N.兩者的進(jìn)化策略不同，獨(dú)立演化，其中宿主群使用標(biāo)準(zhǔn)SSA的位置更新公式，而寄生群則使用1.2節(jié)改進(jìn)后的領(lǐng)導(dǎo)者更新方式.每隔一定進(jìn)化代數(shù)M，就發(fā)生一次寄生群從宿主群吸收營(yíng)養(yǎng)的寄生行為，即寄生群用P個(gè)適應(yīng)度值最差的個(gè)體置換宿主群中前P個(gè)適應(yīng)度值最好的個(gè)體.P是每次寄生行為的個(gè)體置換數(shù)，取值隨進(jìn)化代數(shù)的增加自適應(yīng)減?。?/p>

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

(8)

其中，round()是四舍五入函數(shù)，用來(lái)對(duì)置換個(gè)數(shù)取整.隨著進(jìn)化代數(shù)不斷增加，寄生行為也在不斷發(fā)生，宿主群中位置較優(yōu)的個(gè)體(營(yíng)養(yǎng))不斷被寄生群吸走，寄生群已經(jīng)得到了較多營(yíng)養(yǎng)，因此交換個(gè)數(shù)也在不斷遞減，直到進(jìn)化終止，寄生行為也隨之徹底結(jié)束.

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

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

(9)

宿主群進(jìn)行優(yōu)勝劣汰的步驟為：

fori=1:Q

ifrand()>0.5

淘汰替換當(dāng)前個(gè)體;

end if

end for

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

2 PDESSA的流程與時(shí)間復(fù)雜度

2.1 PDESSA流程偽代碼

算法1.PDESSA.

begin

設(shè)置算法中基本參數(shù)的初值;

計(jì)算寄生群和宿主群中樽海鞘個(gè)體的初始位置;

計(jì)算2個(gè)種群中個(gè)體的適應(yīng)度值;

設(shè)置宿主群、寄生群的食物源位置;

while (t≤Max_iter)

由式(6)計(jì)算w;

fori=1 toN

if (i≤N/2)

forj=1 toD

由式(7)對(duì)寄生群中的領(lǐng)導(dǎo)者進(jìn)行位置更新;

end for

else

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

end if

end for

fori=1 toN

if (i≤N/2)

forj=1 toD

由式(2)更新宿主群的領(lǐng)導(dǎo)者位置;

end for

else

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

end if

end for

if mod (t,M)==0

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

由式(9)計(jì)算優(yōu)勝劣汰個(gè)體數(shù)Q;

對(duì)宿主群中Q個(gè)較差個(gè)體進(jìn)行隨機(jī)劣汰替換;

end if

fori=1 toN

對(duì)2個(gè)種群更新后的樽海鞘個(gè)體進(jìn)行邊界

處理;

計(jì)算宿主群、寄生群中個(gè)體的適應(yīng)度值;

對(duì)宿主群、寄生群的食物源位置進(jìn)行更新;

end for

t=t+1

end while

end

2.2 PDESSA時(shí)間復(fù)雜度分析

評(píng)價(jià)一個(gè)優(yōu)化算法的優(yōu)劣需要兼顧尋優(yōu)性能和時(shí)間復(fù)雜度，時(shí)間復(fù)雜度是考量和評(píng)估算法運(yùn)行效率的重要指標(biāo).下面對(duì)PDESSA的時(shí)間復(fù)雜度進(jìn)行分析.

在文獻(xiàn)[32-33]中,我們都對(duì)標(biāo)準(zhǔn)SSA的時(shí)間復(fù)雜度做了詳細(xì)分析.設(shè)算法的總迭代次數(shù)為Max_iter，種群規(guī)模為N，個(gè)體維度為n.

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

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

進(jìn)入迭代循環(huán)，總迭代次數(shù)為Max_iter.

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

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

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

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

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

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

因此標(biāo)準(zhǔn)SSA的總時(shí)間復(fù)雜度為

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

在本文提出的PDESSA算法中，種群的規(guī)模、個(gè)體維數(shù)、初始化基本參數(shù)的時(shí)間、產(chǎn)生一個(gè)均勻分布隨機(jī)數(shù)的時(shí)間、計(jì)算目標(biāo)函數(shù)適應(yīng)度值的時(shí)間、按個(gè)體適應(yīng)度值對(duì)種群中個(gè)體排序并得到當(dāng)前最優(yōu)位置(食物源)的時(shí)間均與標(biāo)準(zhǔn)SSA相同.由于PDESSA中包含寄生群和宿主群2個(gè)種群，因此PDESSA在初始化階段的時(shí)間復(fù)雜度為

進(jìn)入迭代循環(huán)，總迭代次數(shù)為Max_iter.

算法中寄生、宿主2個(gè)種群的領(lǐng)導(dǎo)者數(shù)量均為N/2，而追隨者數(shù)量則為各自種群中剩余的N/2.

對(duì)于寄生群，設(shè)由式(6)求w的時(shí)間為t1，其值在同輪迭代中保持不變.在寄生群領(lǐng)導(dǎo)者位置更新階段，設(shè)由式(7)更新每個(gè)領(lǐng)導(dǎo)者位置中每一維度的時(shí)間為t2，則這一階段的時(shí)間復(fù)雜度為

在寄生群追隨者位置更新階段，由式(4)更新每個(gè)追隨者位置的時(shí)間與標(biāo)準(zhǔn)SSA相同，則這一階段的時(shí)間復(fù)雜度為

對(duì)于宿主群，所有個(gè)體(領(lǐng)導(dǎo)者、追隨者)的位置更新都分別與標(biāo)準(zhǔn)SSA相同，執(zhí)行這些操作所花費(fèi)的時(shí)間也相同，故而該階段的時(shí)間復(fù)雜度為

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

在邊界處理和食物源更新階段，對(duì)每個(gè)個(gè)體進(jìn)行邊界處理、由目標(biāo)函數(shù)計(jì)算個(gè)體適應(yīng)度值、按個(gè)體適應(yīng)度值比較替換全局最優(yōu)解位置(食物源)的時(shí)間都與標(biāo)準(zhǔn)SSA相同，而且對(duì)寄生群和宿主群的處理完全一致，因此該階段的時(shí)間復(fù)雜度為

由此得出，PDESSA算法總的時(shí)間復(fù)雜度為

與標(biāo)準(zhǔn)SSA相比，本文算法PDESSA的執(zhí)行時(shí)間有所增長(zhǎng)，但時(shí)間復(fù)雜度保持不變，PDESSA的機(jī)制改進(jìn)沒(méi)有降低算法的運(yùn)行效率.

3 PDESSA函數(shù)優(yōu)化仿真實(shí)驗(yàn)

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

3.1 測(cè)試函數(shù)

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

Table 1 Test Function表1 測(cè)試函數(shù)

3.2 尋優(yōu)精度分析

為測(cè)試和檢驗(yàn)PDESSA的尋優(yōu)性能，將f1(x)～f10(x)的維度分別設(shè)置為d=30,100進(jìn)行極值優(yōu)化實(shí)驗(yàn).基于測(cè)試的客觀性和充分性，各算法在相同環(huán)境下獨(dú)立運(yùn)行50次，種群規(guī)模N=30，最大進(jìn)化代數(shù)Max_iter=1 000.表2統(tǒng)計(jì)了30維和100維下各算法運(yùn)行50次得到的尋優(yōu)結(jié)果的最佳值、平均值和方差，其中各項(xiàng)對(duì)應(yīng)的最優(yōu)值均做了加粗顯示.

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

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

Table 2 Comparison of Optimization Results of 6 Algorithms Under Fixed Iteration Times表2 6種算法在固定迭代次數(shù)下的尋優(yōu)結(jié)果比較

續(xù)表2

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

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

3.3 收斂曲線分析

一個(gè)算法的收斂曲線顯示了該算法在尋優(yōu)過(guò)程中收斂速度的變化及陷入局部極值的次數(shù)，通過(guò)收斂曲線可以直觀地展現(xiàn)和對(duì)比出算法尋優(yōu)性能的優(yōu)劣.圖1～10給出了6種算法在d=100維時(shí)，求解10個(gè)復(fù)雜標(biāo)準(zhǔn)測(cè)試函數(shù)f1(x)～f10(x)的收斂曲線對(duì)比圖.

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

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

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

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

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

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

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

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

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

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

圖1～10清晰展現(xiàn)出PDESSA及5種對(duì)比算法在整個(gè)迭代過(guò)程中當(dāng)前最優(yōu)適應(yīng)度值的變化趨勢(shì)對(duì)比.可以看出，相較于其他5種算法，PDESSA的收斂速度更快，收斂曲線總體比較光滑，陷入局部極值的次數(shù)少，尋優(yōu)能力更強(qiáng).

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

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

由實(shí)驗(yàn)結(jié)果和分析可知，本文提出的PDESSA算法具有較為出色的優(yōu)化性能，其尋優(yōu)精度、收斂速度、求解結(jié)果的穩(wěn)定性都優(yōu)于其他5種性能優(yōu)越的代表性對(duì)比算法.

4 PDESSA算法與三次埃爾米特插值方法相結(jié)合求解機(jī)器人路徑規(guī)劃問(wèn)題

4.1 三次埃爾米特插值方法

在求解插值問(wèn)題時(shí)，為構(gòu)建更貼近契合于原函數(shù)的插值函數(shù)，我們要求在節(jié)點(diǎn)處，不僅原函數(shù)和插值多項(xiàng)式的函數(shù)值相同，兩者的一階或更高階導(dǎo)數(shù)值也相同，這種插值就是埃爾米特插值方法，其插值多項(xiàng)式稱為埃爾米特插值多項(xiàng)式.

設(shè)在節(jié)點(diǎn)a≤x0

H(xi)=yi，

(10)

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

(11)

因插值節(jié)點(diǎn)一共有n+1個(gè)，當(dāng)給出2n+2個(gè)條件時(shí)，便可唯一確定一個(gè)次數(shù)不超過(guò)2n+1的多項(xiàng)式H2n+1(x)=H(x)，其表達(dá)式的形式為

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

(12)

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

(13)

(14)

βi(xk)=0，

(15)

(16)

由式(10)～(16)條件構(gòu)造出的埃爾米特插值多項(xiàng)式為

(17)

作為分段式插值方法，埃爾米特插值在區(qū)間內(nèi)生成一系列中間插值節(jié)點(diǎn)，從而構(gòu)造出一條較光滑曲線.將埃爾米特插值方法融合到機(jī)器人全局路徑的規(guī)劃構(gòu)建上，能夠使機(jī)器人在移動(dòng)過(guò)程中更加自然地避開障礙，形成更符合動(dòng)力學(xué)原理特性的平滑路徑.

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

(18)

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

4.2 構(gòu)建模型與適應(yīng)度函數(shù)

4.2.1 求解問(wèn)題的數(shù)學(xué)模型與算法編碼方式

為了將智能算法更好地應(yīng)用于移動(dòng)機(jī)器人全局路徑規(guī)劃問(wèn)題，充分發(fā)揮算法的優(yōu)化作用，在建立該問(wèn)題的數(shù)學(xué)模型時(shí)做3個(gè)假設(shè)：

1) 機(jī)器人的移動(dòng)場(chǎng)景為2維有限空間；

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

3) 機(jī)器人被看作質(zhì)點(diǎn)，其大小形狀可以忽略.

基于算法處理的效率和統(tǒng)一性以及所規(guī)劃出機(jī)器人路徑的光滑性考慮，將各種不同形狀的障礙物抽象為其各自的外切圓，以圓形表示.模型中正方形表示機(jī)器人的路徑起點(diǎn)、終點(diǎn)，圓形區(qū)域?yàn)檎系K區(qū)，其余為可移動(dòng)區(qū)域.本文將基于這類環(huán)境和場(chǎng)景，進(jìn)行移動(dòng)機(jī)器人的全局路徑規(guī)劃，而這樣的環(huán)境也能夠與無(wú)人車間、智能倉(cāng)庫(kù)、特殊環(huán)境作業(yè)等許多實(shí)際應(yīng)用場(chǎng)景相吻合.

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

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

4.2.2 構(gòu)建目標(biāo)函數(shù)

目標(biāo)函數(shù)用于求解機(jī)器人全局路徑問(wèn)題的最優(yōu)解，其適應(yīng)度值便是評(píng)價(jià)求解結(jié)果和性能的量化值.評(píng)判所得到的1個(gè)路徑是否最優(yōu)，需要滿足：

1) 不經(jīng)過(guò)任何障礙物區(qū)域(沒(méi)有碰撞)；

2) 產(chǎn)生的路徑最短.

基于此2條件所構(gòu)造的機(jī)器人路徑規(guī)劃問(wèn)題適應(yīng)度函數(shù)為

F=L(1+ρ×Z),

(19)

其中，懲罰系數(shù)ρ的值要足夠大，以起到若發(fā)生碰撞便死刑懲罰的作用，本文取ρ=100，從而排除進(jìn)化求解過(guò)程中那些穿越障礙物圓形區(qū)域的路徑.L為從起點(diǎn)、每個(gè)插值點(diǎn)直到終點(diǎn)的序列點(diǎn)距離和，即路徑長(zhǎng)度，其計(jì)算為

(20)

其中，xi,yi和xi+1,yi+1分別是第i個(gè)和第i+1個(gè)插值點(diǎn)的橫坐標(biāo)與縱坐標(biāo).

Z用來(lái)判斷插值點(diǎn)是否位于障礙物區(qū)域，即該路徑是否經(jīng)過(guò)障礙物，其初值為0，計(jì)算Z的代碼段為：

fork=1:CN

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

Z=Z+mean(Pk)；

end for

其中，x，y分別是路徑上全部插值點(diǎn)橫、縱坐標(biāo)的集合，CN是障礙數(shù)，CXk和CYk分別是障礙k的圓心橫、縱坐標(biāo)，CRk則是障礙k的圓形區(qū)域半徑.Dk用于存儲(chǔ)障礙k圓心到路徑上各插值點(diǎn)的距離值.Pk為標(biāo)志數(shù)組，用來(lái)判別每個(gè)插值點(diǎn)是否位于障礙k的圓形區(qū)域內(nèi)，當(dāng)路徑中存在落入障礙區(qū)域的插值點(diǎn)時(shí)，說(shuō)明路徑未能避開障礙，此時(shí)Pk中對(duì)應(yīng)于該插值點(diǎn)的標(biāo)志值為正，有Z>0；否則數(shù)組Pk的所有元素都是0，有Z=0，這說(shuō)明此路徑?jīng)]有經(jīng)過(guò)任一障礙區(qū)域，所對(duì)應(yīng)的目標(biāo)函數(shù)適應(yīng)度值為L(zhǎng).

4.3 機(jī)器人路徑規(guī)劃

為驗(yàn)證PDESSA算法對(duì)于機(jī)器人全局路徑規(guī)劃的有效性，將第3節(jié)的6種算法在相同環(huán)境下進(jìn)行算例求解仿真實(shí)驗(yàn)，從而全面檢驗(yàn)和分析PDESSA及5種對(duì)比算法分別與三次埃爾米特插值相結(jié)合，求解這一問(wèn)題的尋優(yōu)結(jié)果和性能.

為保障比較的公平性，6種算法均獨(dú)立運(yùn)行求解過(guò)程30次，種群規(guī)模N=50，最大迭代次數(shù)Max_iter=100.各算法的運(yùn)行環(huán)境及參數(shù)設(shè)置也都與第3節(jié)相同，即參數(shù)值與各自算法的源文獻(xiàn)和源代碼保持一致.

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

1) 算例1：普通場(chǎng)景下6種對(duì)比算法的求解實(shí)驗(yàn)分析.

Fig. 11 Space scene diagram of case 1圖11 算例1的空間場(chǎng)景圖

算例1為普通障礙場(chǎng)景，機(jī)器人移動(dòng)的起點(diǎn)和終點(diǎn)坐標(biāo)分別是(0.0,0.0)和(6.0,6.0)，場(chǎng)景空間中障礙物的個(gè)數(shù)為6，將路徑節(jié)點(diǎn)數(shù)設(shè)置為3，插值點(diǎn)個(gè)數(shù)設(shè)置為400.圖11給出了機(jī)器人移動(dòng)時(shí)的空間場(chǎng)景，表3則列出了此場(chǎng)景中各個(gè)障礙物的位置與大小.

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

表4統(tǒng)計(jì)了對(duì)于普通障礙場(chǎng)景的算例1，6種算法30次求解得到的路徑長(zhǎng)度最佳值、平均值和方差.圖12給出了本文算法PDESSA求解規(guī)劃出的一條機(jī)器人移動(dòng)路線.

Table 4 Solution Results of the Six Algorithms for Example 1表4 6種算法對(duì)算例1的求解結(jié)果

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

2) 算例2：復(fù)雜場(chǎng)景下6種算法的求解實(shí)驗(yàn)分析.

算例2為較復(fù)雜障礙場(chǎng)景，機(jī)器人移動(dòng)的起點(diǎn)和終點(diǎn)坐標(biāo)分別是(0.0,0.0)和(6.0,6.0)，場(chǎng)景空間中障礙物的個(gè)數(shù)為10，將路徑節(jié)點(diǎn)數(shù)設(shè)置為5，插值點(diǎn)個(gè)數(shù)設(shè)置為600.圖13給出了機(jī)器人移動(dòng)時(shí)的空間場(chǎng)景，表5則列出了此場(chǎng)景中各個(gè)障礙物的位置與大小.

Fig. 13 Space scene diagram of case 2圖13 算例2的空間場(chǎng)景圖

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

表6統(tǒng)計(jì)了對(duì)于較復(fù)雜障礙場(chǎng)景的算例2，6種算法30次求解得到的路徑長(zhǎng)度最佳值、平均值和方差.圖14給出了本文算法PDESSA求解規(guī)劃出的一條機(jī)器人移動(dòng)路線.

Table 6 Solution Results of the Six Algorithms for Example 2表6 6種算法對(duì)算例2的求解結(jié)果

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

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

4.3.2 不同插值方法的對(duì)比和選擇

1) 基于三次樣條插值的算例求解對(duì)比實(shí)驗(yàn)

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

表7和表8分別統(tǒng)計(jì)了6種算法融合三次樣條插值方法，各自獨(dú)立運(yùn)行30次，求解普通和較復(fù)雜障礙場(chǎng)景的算例1和算例2，得到的路徑長(zhǎng)度的最佳值、平均值和方差.

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

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

觀察表7和表8中的統(tǒng)計(jì)數(shù)據(jù)可以很清楚地看出，對(duì)于2種不同復(fù)雜程度障礙場(chǎng)景的算例1和算例2，PDESSA算法與三次樣條插值方法相結(jié)合所求得的路徑長(zhǎng)度的平均值和方差依然全部?jī)?yōu)于其他5種算法.在最佳值方面，對(duì)于算例1，本文算法PDESSA的最佳值也是6種算法中最優(yōu)的；對(duì)于算例2，本文算法PDESSA的最佳值與ISSA，SSA算法基本相當(dāng)，明顯優(yōu)于另外3種算法，而平均值和方差更是顯著優(yōu)于ISSA，SSA和其他對(duì)比算法，充分說(shuō)明了其求解路徑長(zhǎng)度值的優(yōu)越性和穩(wěn)定性.

這些結(jié)果再次證明了本文算法PDESSA在求解移動(dòng)機(jī)器人全局路徑規(guī)劃問(wèn)題上，具有出色的穩(wěn)定性和良好的適用性.

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

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

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

通過(guò)以上測(cè)試結(jié)果的比較和分析，可以清楚地看到對(duì)于不同復(fù)雜程度的障礙場(chǎng)景，融合三次埃爾米特插值的求解方案規(guī)劃出的路徑長(zhǎng)度，跳躍性較小，穩(wěn)定性更強(qiáng)，整體更為可靠，尤其是在較為復(fù)雜的障礙環(huán)境下，采用三次埃爾米特插值的方案求解效果更佳，優(yōu)勢(shì)更突顯.

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

表9統(tǒng)計(jì)了6種算法分別融合引入三次樣條、三次埃爾米特2種不同的插值方法，各自獨(dú)立運(yùn)行30次求解算例1和算例2，得到的算法平均執(zhí)行時(shí)間.

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

由關(guān)于2種不同插值方式下路徑長(zhǎng)度和算法執(zhí)行時(shí)間的實(shí)驗(yàn)結(jié)果與分析可知，采用融合三次埃爾米特插值的求解方案，求解移動(dòng)機(jī)器人全局路徑規(guī)劃問(wèn)題時(shí)，所規(guī)劃出路徑的長(zhǎng)度整體更短也更加穩(wěn)定，

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

并且執(zhí)行算法所花費(fèi)的平均時(shí)間也更少.因此，本文采用將三次埃爾米特插值方法與PDESSA算法相結(jié)合，求解移動(dòng)機(jī)器人全局路徑規(guī)劃問(wèn)題的方案是合理而且有效的.

5 結(jié) 論

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

作者貢獻(xiàn)聲明：劉景森提出算法機(jī)制和應(yīng)用方案，負(fù)責(zé)并參與論文的寫作和修改；袁蒙蒙參與論文的撰寫，提出算法和方案的實(shí)現(xiàn)代碼，測(cè)試和分析實(shí)驗(yàn)數(shù)據(jù)；李煜參與論文的寫作與修改，對(duì)研究方案進(jìn)行理論分析.