差分變異和領(lǐng)地搜索的平衡優(yōu)化算法及其機(jī)器人路徑規(guī)劃

張 貝,閔華松,張新明

(1.武漢科技大學(xué)機(jī)器人與智能系統(tǒng)研究院,湖北 武漢 430081;2.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院,河南 新鄉(xiāng) 453007)

1 引言

優(yōu)化問題在現(xiàn)實(shí)生活中無處不在,如二次指派問題[1]和機(jī)器人路徑規(guī)劃[2]等都是典型的優(yōu)化問題。

一般說來,優(yōu)化問題可以分為線性、非線性、連續(xù)、離散、單目標(biāo)、多目標(biāo)、有約束和無約束等優(yōu)化問題[3]。而解決好無約束單目標(biāo)問題是解決所有其它優(yōu)化問題的基礎(chǔ)[4],故本文主要討論此類優(yōu)化問題。

解決優(yōu)化問題的方法稱為優(yōu)化方法。優(yōu)化方法一般分為確定性方法和隨機(jī)性方法。傳統(tǒng)的確定性方法不能很好地解決全局優(yōu)化問題,且還需要優(yōu)化問題的大量信息[4]。因此,隨機(jī)性優(yōu)化方法引起了人們廣泛的關(guān)注。元啟發(fā)式算法MA(Meta- heuristic Algorithm)屬于隨機(jī)性優(yōu)化方法范疇。MA由于其簡單性、靈活性和無需太多優(yōu)化問題的信息等優(yōu)點(diǎn),在許多領(lǐng)域得到廣泛的應(yīng)用。因此,研究人員提出了許多MA,如差分進(jìn)化算法[4]、粒子群優(yōu)化PSO(Particle Swarm Optimization)算法[5]、人工蜂鳥算法AHA(Artificial Hummingbird Algorithm)[6]和堆優(yōu)化算法HBO(Heap-Based Optimizer)[7]等。隨著社會(huì)的快速發(fā)展,需要解決的優(yōu)化問題越來越多,且越來越復(fù)雜和多樣化。另外,根據(jù)無免費(fèi)午餐定理[8],一個(gè)算法在一類優(yōu)化問題上可能有杰出的表現(xiàn),但在另一類優(yōu)化問題上可能表現(xiàn)不佳,沒有一種MA可以解決所有的優(yōu)化問題。因此,新的和改進(jìn)的MA不斷被提出。

平衡優(yōu)化算法EO(Equilibrium Optimizer)是由Faramarzi等人[9]在2020年提出的一種新型的MA,受啟發(fā)于受控容器中液體的動(dòng)態(tài)質(zhì)量守恒模型,即在受控容器中進(jìn)入、離開和產(chǎn)生的液體質(zhì)量總和保持不變。在EO中,每種液體成分類似PSO中的粒子充當(dāng)搜索個(gè)體,而這些成分的濃度類似PSO中的粒子位置。每個(gè)粒子通過5個(gè)精英粒子的引導(dǎo)來更新其濃度,最終達(dá)到平衡狀態(tài)(最優(yōu)結(jié)果)。與現(xiàn)有的MA相比,EO具有獨(dú)特的搜索機(jī)制,在解決經(jīng)典的優(yōu)化問題時(shí)優(yōu)勢明顯[9]。然而,EO提出的時(shí)間較短,還有許多地方值得深入研究。因此,國內(nèi)外一些研究人員提出了一些EO的改進(jìn)算法,擴(kuò)展了其應(yīng)用范圍。例如,Gupta等人[10]提出了一種具有突變策略的EO,使種群保持足夠的多樣性,增強(qiáng)了EO的全局搜索能力;Wunnava等人[11]將一種自適應(yīng)EO——AEO(Adaptive EO)應(yīng)用于多閾值圖像分割,擴(kuò)展了EO的應(yīng)用范圍;Fan等人[12]基于反向?qū)W習(xí)策略和新穎的更新規(guī)則提出了一種改進(jìn)的EO,該算法在最優(yōu)解為零向量的問題上非常有效;羅仕杭等人[13]提出了一種多策略的EO——MEO(Multi-strategy EO),在經(jīng)典的優(yōu)化問題上獲得更好的性能;Zhang等人[14]提出了一種強(qiáng)化信息使用的EO——ISEO(Information utilization Strengthened EO),提升了EO的搜索能力。雖然這些EO的改進(jìn)算法在不同程度上改善了EO的優(yōu)化性能或擴(kuò)展了其應(yīng)用范圍。然而,它們?nèi)源嬖谒阉髂芰Σ蛔愕热毕?。此?它們大多都是在經(jīng)典函數(shù)上驗(yàn)證其有效性,幾乎沒有關(guān)于在CEC(Congress on Ewlntionary Computation)復(fù)雜優(yōu)化問題的測試集上測試EO改進(jìn)版本的研究,而且目前也無EO在機(jī)器人路徑規(guī)劃上應(yīng)用的研究。綜上所述,對(duì)EO的研究非常必要且有較大實(shí)際意義。

針對(duì)EO在解決復(fù)雜優(yōu)化問題時(shí)存在搜索能力不足和搜索效率低等問題,本文提出了一種改進(jìn)的EO,即差分變異和領(lǐng)地搜索的EO——DTEO(Differential mutation and Territorial search EO)。

2 平衡優(yōu)化算法

EO中粒子的濃度更新方式是依據(jù)質(zhì)量守恒定律所構(gòu)建的一階常微分方程推導(dǎo)而成[9],如式(1)所示:

(1)

其中,Xi為第i個(gè)粒子更新后的濃度;Ci為其已有的濃度,i∈[1,N],N為種群規(guī)模;Ce是從精英池(Cpool)中隨機(jī)選取的精英粒子的濃度;F為縮放因子向量;G為生成速度;λ為周轉(zhuǎn)速率;V表示容器的體積,常取值為1個(gè)體積單位;?表示2個(gè)向量中的對(duì)應(yīng)分量相乘。這些符號(hào)詳述如下:

精英池(Cpool)由5個(gè)精英粒子的濃度組成,如式(2)所示:

Cpool={Cα,Cβ,Cδ,Cγ,Cφ}

(2)

其中,Cα、Cβ、Cδ和Cγ分別為當(dāng)前種群中最優(yōu)、次優(yōu)、第3優(yōu)和第4優(yōu)粒子的濃度,最后一個(gè)精英的濃度Cφ通過式(3)計(jì)算獲得:

Cφ=(Cα+Cβ+Cδ+Cγ)/4

(3)

縮放因子向量F的計(jì)算如式(4)和式(5)所示:

F=a1×sign(r-0.5)?[e-z×λ-1]

(4)

z=(1-t/T)(a2×t/T)

(5)

其中,a1和a2為調(diào)整參數(shù);sign(·)是符號(hào)函數(shù);r與λ都是D維隨機(jī)向量,其每個(gè)分量是均勻分布在[0,1]的隨機(jī)數(shù);t為當(dāng)前迭代次數(shù);T為最大迭代次數(shù)。

生成速度G的表達(dá)式如式(6)～式(8)所示:

G=G0?F

(6)

G0=RG×(Ce-λ?Ci)

(7)

(8)

其中,RG為生成速度的控制參數(shù),由參數(shù)生成概率PG決定;r1和r2為均勻分布在[0,1]的隨機(jī)數(shù)。

從式(6)～式(8)可以看出,當(dāng)r2小于PG時(shí),G為零向量,故式(1)可以改寫為式(9):

(9)

根據(jù)式(1)～式(8)可知,式(1)右側(cè)的第1項(xiàng)是隨機(jī)選擇精英粒子的濃度,第2項(xiàng)和第3項(xiàng)包含了這個(gè)精英粒子和第i個(gè)粒子濃度之間的差值。EO的偽代碼如算法1所示。

算法1EO算法

輸入：參數(shù)V,a1,a2和PG等的值。

輸出：最優(yōu)解Cα。

1.隨機(jī)初始化種群中每個(gè)粒子的濃度;

2.計(jì)算粒子適應(yīng)度值,確定Cα、Cβ、Cδ、Cγ和Cφ,構(gòu)建精英池;

3.FORt=1 TOTDO

4.FORi=1 TONDO

5. 依據(jù)式(9)更新粒子的濃度,并對(duì)更新后的濃度進(jìn)行邊界控制;

6.ENDFOR

7.FORi=1 TONDO

8. 計(jì)算粒子的適應(yīng)度值,用貪婪算法選擇更新種群和更新精英池;

9.ENDFOR

10.ENDFOR

根據(jù)以上描述可知,EO具有以下優(yōu)點(diǎn):(1) 具有獨(dú)特的新解產(chǎn)生機(jī)制,如式(1)所示。(2) 具有一定的信息引導(dǎo)能力。從式(1)可以看出,在一定程度上精英粒子的信息可以引導(dǎo)其他粒子搜索。(3) 有較強(qiáng)的局部搜索能力。式(1)右側(cè)的3項(xiàng)都包含精英粒子的濃度,這表明精英粒子會(huì)引導(dǎo)種群朝著良好的方向搜索。(4) 具有一定的全局搜索能力。其一,在演化早期階段,F的各分量值較大且精英粒子與其他粒子之間的差異也較大,這有助于擴(kuò)大搜索范圍;其二,更新方程包含的一些隨機(jī)因素也增強(qiáng)了種群多樣性和有利于全局搜索。(5) 具有較強(qiáng)的靈活性和通用性,較多的可調(diào)參數(shù)可以調(diào)整算法使其適應(yīng)多種優(yōu)化問題。

3 改進(jìn)的平衡優(yōu)化算法

EO雖然在經(jīng)典函數(shù)上有較好的優(yōu)化性能,但在解決復(fù)雜的優(yōu)化問題時(shí)仍然存在一些不足:(1) 在EO中僅使用5個(gè)精英粒子與其他粒子共享信息,這種信息共享方式不僅單一,而且共享程度較低,導(dǎo)致搜索能力不足;(2) 濃度更新方程的計(jì)算復(fù)雜度高,同時(shí)搜索能力不足使得EO的搜索效率較低;(3) EO有較多參數(shù)需要調(diào)整,導(dǎo)致EO的可操作性較差。因此,針對(duì)EO在解決復(fù)雜優(yōu)化問題時(shí)存在的缺點(diǎn),本文提出了4種改進(jìn)策略:(1)融合領(lǐng)地搜索的隨機(jī)差分變異策略,提升最優(yōu)個(gè)體;(2)信息共享的隨機(jī)差分變異策略,提高算法的搜索能力;(3)簡化EO更新方程策略,提高算法的可操作性,降低計(jì)算復(fù)雜度;(4)精英與最差個(gè)體的差分變異策略,強(qiáng)化最差個(gè)體。

3.1 融合領(lǐng)地搜索的隨機(jī)差分變異策略

在EO中,所有粒子濃度的更新都是由精英粒子引導(dǎo)的,最優(yōu)個(gè)體屬于精英群中一員,發(fā)揮著重要的作用。若最優(yōu)個(gè)體位于局部最優(yōu)點(diǎn),可能會(huì)使EO陷入局部最優(yōu)。所以若能強(qiáng)化最優(yōu)個(gè)體,則通過式(9)中的精英信息引導(dǎo)能夠提升其它個(gè)體的搜索能力,故本文采用一種新型差分變異策略來更新最優(yōu)個(gè)體的濃度,以提升最優(yōu)個(gè)體。差分變異策略就是將2個(gè)解的差分向量經(jīng)過縮放加到第3個(gè)解向量上,對(duì)其每維的值進(jìn)行變異,從而得到一個(gè)新解。差分變異有多種形式,被廣泛應(yīng)用于MA中[4]。本節(jié)僅討論將2個(gè)隨機(jī)選擇粒子的濃度差分向量縮放后加到當(dāng)前粒子的濃度上,產(chǎn)生新濃度,表達(dá)式如式(10)和式(11)所示:

Xi=Ci+fr×(Cs-Cl)

(10)

fr=0.5×(sin(2π×0.25×t)×(t/T)+1)

(11)

其中,Cs和Cl分別為從當(dāng)前種群中隨機(jī)選擇的2個(gè)粒子的濃度,且s≠l≠i;fr為正弦模型的縮放因子[15]。

由文獻(xiàn)[15]可知,正弦模型使得fr的值在0.5上下波動(dòng)。在迭代前期,波動(dòng)幅度不大,但周期性的波動(dòng)有利于算法跳出局部最優(yōu)點(diǎn),準(zhǔn)確定位全局最優(yōu)點(diǎn);在迭代后期,fr波動(dòng)幅度較大,有時(shí)其值接近1,有時(shí)其值近似0,在算法陷于局部最優(yōu)時(shí),接近1的縮放因子值有利于算法跳出局部最優(yōu),當(dāng)算法搜索到有希望的全局最優(yōu)點(diǎn)時(shí),接近0的縮放因子值有利于精確搜索。因此,正弦縮放因子能夠很好地平衡探索與開采能力。

融合領(lǐng)地搜索隨機(jī)差分變異策略的基本原理是:在一個(gè)隨機(jī)數(shù)rand小于0.5或者Cs和Cl為零向量時(shí),最優(yōu)個(gè)體進(jìn)行領(lǐng)地搜索,否則采用隨機(jī)差分變異策略更新其濃度。在前期,各個(gè)粒子濃度之間的差異較大,Xi遠(yuǎn)離Ci,搜索范圍較大,有利于全局搜索。但是,到了后期各個(gè)粒子濃度之間的差異變小,有利于局部搜索,但無差異時(shí),Xi=Ci為無效解。為了應(yīng)對(duì)這種情況,本文將領(lǐng)地搜索策略融入到差分變異策略中。

領(lǐng)地搜索思想來自人工蜂鳥算法[6],其靈感來自于蜂鳥的領(lǐng)地覓食行為。在蜂鳥吃完了目標(biāo)花源的花蜜之后,它有可能在其附近搜索新的花源。因此,蜂鳥在它的領(lǐng)地里會(huì)移到當(dāng)前食物源附近,搜索也許更好的食物源作為候選解。這種搜索策略在本文稱為領(lǐng)地搜索策略,其表達(dá)式如式(12)所示:

Xi=Ci+fα×Di?Ci

(12)

其中,fα是領(lǐng)地搜索因子,服從標(biāo)準(zhǔn)的正態(tài)分布,即均值為0、方差為1的高斯分布;Di為第i個(gè)蜂鳥的飛行方向向量,模擬蜂鳥3種飛行方式(軸向飛行、對(duì)角飛行和全向飛行),即當(dāng)一個(gè)均勻分布在0～1的隨機(jī)數(shù)小于1/3時(shí),蜂鳥采用對(duì)角飛行,當(dāng)這個(gè)隨機(jī)數(shù)大于2/3時(shí)采用全向飛行,否則采用軸向飛行。在Di中,若一個(gè)隨機(jī)維的值為1,其它維的值全為0,則表示軸向飛行;若幾個(gè)隨機(jī)維的值為1,其它維的值為0,則表示對(duì)角飛行;若所有維的值全為1,則表示全向飛行。

從式(12)可知,Di是0-1向量,即每個(gè)分量要么是0,要么是1,故產(chǎn)生的新解Xi是在Ci自身的某些維或者全維變異獲得。這種搜索是一種局部搜索,能夠提升算法的收斂速度和解的精度。

將領(lǐng)地搜索融入到差分變異中的過程如算法2所示。

算法2融合領(lǐng)地搜索的差分變異策略

輸入：當(dāng)前最優(yōu)粒子。

輸出：更新后的最優(yōu)粒子濃度。

1.隨機(jī)選擇2個(gè)粒子;

2.IF(隨機(jī)選擇的2個(gè)粒子濃度相同) or (rand<0.5);

3. 采用式(12)領(lǐng)地搜索更新最優(yōu)粒子的濃度;

4.ELSE

5. 采用式(10)的隨機(jī)差分變異策略更新最優(yōu)粒子的濃度;

6.ENDIF

從算法2可以看出:(1) 領(lǐng)地搜索的差分變異策略替換式(9)僅用于最優(yōu)粒子的濃度更新,由此最優(yōu)粒子的濃度更新是得益于種群中其它粒子的信息和自身信息。(2) 在差分值為0和rand小于0.5時(shí)采用領(lǐng)地搜索,解決了差分變異策略尤其在迭代后期易產(chǎn)生無效解的問題。(3) 從式(12)可以看出,領(lǐng)地搜索作用于最優(yōu)粒子上,更能發(fā)揮領(lǐng)地搜索的作用,在最優(yōu)粒子的濃度周圍進(jìn)行精搜索更能加快算法收斂和提高解的精度。(4) 由于前期個(gè)體之間的差異較大,隨機(jī)選擇的2個(gè)個(gè)體的濃度相同的概率較低,這樣前期采用差分變異策略的機(jī)會(huì)較大,這有利于提高算法的全局搜索能力。(5)在迭代后期,采用領(lǐng)地搜索的概率較大,而領(lǐng)地搜索是一種局部搜索,所以在整個(gè)迭代過程中算法能夠從全局搜索自動(dòng)轉(zhuǎn)換到局部搜索。(6) 無論前期還是后期,差分變異和領(lǐng)地搜索隨機(jī)交替執(zhí)行,即全局搜索和局部搜索交替進(jìn)行,有利于平衡探索與開采能力。

3.2 信息共享的隨機(jī)差分變異策略

MA通過群體中的信息共享和個(gè)體與環(huán)境的適應(yīng)性等來搜索整個(gè)空間,從而找到最優(yōu)解或者次優(yōu)解[14]。因此,為了增強(qiáng)EO中粒子之間的信息共享程度,除了最優(yōu)粒子和最差粒子外,本文在其它粒子的濃度更新上采用一種信息共享的隨機(jī)差分變異策略,其數(shù)學(xué)模型如式(10)所示。

雖然信息共享的隨機(jī)差分變異策略仍然采用3.1節(jié)的式(10),但由于這種隨機(jī)差分變異策略作用在多個(gè)粒子上,且Cs和Cl的隨機(jī)選擇滿足均勻分布,隨著迭代次數(shù)的增加,使得種群中所有粒子都有可能被選擇。這些差分值是種群內(nèi)所有粒子貢獻(xiàn)的信息,如此增強(qiáng)了種群內(nèi)粒子之間的信息共享。

3.3 簡化EO濃度更新策略

為了更好地與信息共享的隨機(jī)差分變異策略融合,增強(qiáng)可操作性和縮短運(yùn)行時(shí)間,本文在保證EO優(yōu)勢的情況下,提出一種簡化EO更新策略,其表達(dá)式如式(13)所示:

Xi=Ce-(Ce-Ci)?F+

0.5×r1×(Ce-Ci)?F?(1-F)

(13)

F=2×sign(r-0.5)×[e-η-1]

(14)

η=(1-t/T)(t/T)

(15)

從式(13)～式(15)可以看出,與原EO更新策略相比,簡化更新策略有以下差異:(1) 舍棄了λ、V、a1、a2和PG等參數(shù),只保留了F、r和r1。這3個(gè)參數(shù)不需要人工調(diào)整,大幅度提高了EO的可操作性。(2) 去掉了參數(shù)λ,式(13)～式(15)減少了許多基于維度和基于指數(shù)的運(yùn)算,這些都大幅度降低了計(jì)算量。(3) 由式(13)可知,簡化后的更新策略是精英粒子濃度與當(dāng)前粒子濃度的差分向量,經(jīng)過縮放后加到精英粒子的濃度上,這實(shí)際上也是一種差分變異策略,更加突出了精英粒子的引導(dǎo)作用,如此強(qiáng)化開采能力。

雖然簡化操作保持了EO較強(qiáng)開采能力的優(yōu)勢,降低了計(jì)算復(fù)雜度,提高了可操作性,但它并沒有改變EO的整體搜索模式。此外,簡化策略去掉了隨機(jī)參數(shù)λ并采用一種更新模式,降低了種群的多樣性,在一定程度上削弱了EO的全局搜索能力。為了增強(qiáng)全局搜索能力,本文通過動(dòng)態(tài)調(diào)整的方法將信息共享的隨機(jī)差分變異策略和簡化EO更新策略相結(jié)合。動(dòng)態(tài)調(diào)整融合2種策略的流程圖如圖1所示。其中,η是融合2種更新策略的動(dòng)態(tài)調(diào)整參數(shù),如式(15)所示,隨著迭代次數(shù)的增加,它從1遞減到0;r2是均勻分布在[0,1]的隨機(jī)數(shù)。從圖1可以看出,當(dāng)r2≥η時(shí),使用簡化EO更新策略對(duì)當(dāng)前粒子的濃度進(jìn)行更新;否則,使用信息共享的隨機(jī)差分變異策略進(jìn)行更新。在迭代初期,η值較大,大部分粒子采用信息共享的差分變異策略更新其濃度,少數(shù)粒子采用簡化EO更新策略更新其濃度。此時(shí)粒子之間的差異也較大,種群具有較強(qiáng)的多樣性,有助于全局搜索。在迭代后期,η值較小,大部分粒子采用開采能力強(qiáng)的簡化EO更新策略更新,少數(shù)粒子采用信息共享策略更新。此時(shí)粒子之間的差異較小,信息共享的差分變異策略也在一定程度上有利于算法的局部搜索。因此,動(dòng)態(tài)調(diào)整2種策略有效地平衡算法的探索和開采能力,在提高全局搜索能力的同時(shí)保持了原算法局部搜索能力強(qiáng)的優(yōu)勢。另外,為了防止差分變異操作產(chǎn)生無效解,在式(10)和式(13)中的差分向量為零向量時(shí)采用領(lǐng)地搜索,發(fā)揮領(lǐng)地搜索的優(yōu)勢。

Figure 1 Process of hybrid differential mutation and simplified updating strategies圖1 融合差分變異策略和簡化更新策略的過程

3.4 精英與最差個(gè)體的差分變異策略

強(qiáng)化最差個(gè)體能夠提高算法的整體性能,進(jìn)而提升算法的搜索效率[1]。故針對(duì)最差個(gè)體,本文提出了一種精英與最差個(gè)體的差分變異策略。如此有別于其它個(gè)體的更新方式,使最差粒子的搜索能力大幅度提高。其數(shù)學(xué)模型如式(16)所示:

(16)

其中,Xw為最差粒子更新后的濃度,Cw為最差粒子原有的濃度,r3為均勻分布在[0,1]的隨機(jī)數(shù),fr的含義如式(11)所示。

從式(16)可以看出,在最差粒子原有濃度的基礎(chǔ)上,添加一個(gè)精英粒子與最差粒子的濃度差分值,這可以保證最差粒子在精英信息的引導(dǎo)下向著最優(yōu)方向趨近,強(qiáng)化最差個(gè)體的開采能力。同時(shí),在0.5的概率下,其差分值受到(0.5+0.5×rand)和fr縮放因子的擾動(dòng),如此縮放最差粒子的搜索范圍,以此在強(qiáng)化最差粒子局部搜索能力的同時(shí)兼顧全局搜索能力。因此,精英與最差個(gè)體差分變異策略能夠有效地增強(qiáng)最差個(gè)體的性能,減少最差粒子對(duì)整個(gè)種群的不利影響。同樣當(dāng)差分為零向量時(shí),采用領(lǐng)地搜索,以避免產(chǎn)生無效解。

3.5 DTEO流程

DTEO的流程圖如圖2所示。

由圖2可知,DTEO采用了4種濃度更新方式:融合領(lǐng)地搜索的隨機(jī)差分變異策略用于更新最優(yōu)粒子的濃度;精英與最差粒子的差分變異策略用于更新最差粒子的濃度;而信息共享的隨機(jī)差分變異策略主要用于其它個(gè)體在迭代前期的濃度更新;簡化EO更新策略主要使用在迭代后期。雖然這4種改進(jìn)策略都使用了差分變異策略和領(lǐng)地搜索,但隨機(jī)差分變異策略在搜索前期主要用于全局搜索,而領(lǐng)地搜索主要用于局部搜索,也為了避免差分變異策略產(chǎn)生無效解。所以,在DTEO中,差分變異策略與領(lǐng)地搜索有機(jī)結(jié)合能夠提高搜索效率?？傊?DTEO在保持EO優(yōu)勢的同時(shí),增強(qiáng)了種群中的信息利用率,克服了EO的不足,較好地平衡了探索和開采性能。

Figure 2 Flow chart of DTEO圖2 DTEO算法流程圖

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境與評(píng)價(jià)標(biāo)準(zhǔn)

為了驗(yàn)證DTEO的性能,將其用于CEC2014復(fù)雜函數(shù)測試集的優(yōu)化實(shí)驗(yàn)。CEC2014包含4類函數(shù):單峰函數(shù)(f1～f3)、多峰函數(shù)(f4～f16)、組合函數(shù)(f17～f22)和復(fù)合函數(shù)(f23～f30),具體細(xì)節(jié)見文獻(xiàn)[16]。主頻3.4 GHz的Intel?CoreTMi7-3770 CPU和8 GB內(nèi)存的PC機(jī)實(shí)驗(yàn)環(huán)境下,操作系統(tǒng)采用64位的Windows 10系統(tǒng)。用于統(tǒng)計(jì)分析的軟件是IBM SPSS Statistics 24,編程語言采用MATLAB2014A。

本文采用均值(Mean)、方差(Std)、排名(Rank)、平均排名和總排名等指標(biāo)來評(píng)價(jià)一個(gè)MA的優(yōu)化性能好壞。對(duì)于一個(gè)極小值問題,一個(gè)MA所獲得的均值越小,表示它的優(yōu)化性能越好。方差越小,穩(wěn)定性越強(qiáng)。排名規(guī)則如下:在每個(gè)函數(shù)上,算法得到的均值越小,排名靠前;若幾個(gè)算法的均值相同,再比較方差,方差越小,則排名靠前;如果均值和方差相同,則排名相同。

4.2 對(duì)比算法及參數(shù)設(shè)置

為了全面評(píng)價(jià)DTEO的表現(xiàn),包括優(yōu)化性能、運(yùn)行時(shí)間和搜索效率等,本文選擇了一些最先進(jìn)的代表性算法作為其對(duì)比算法。它們包括EO[9]及其改進(jìn)算法AEO[11]、MEO[13]和ISEO[14],也包括其它最新的優(yōu)秀算法AHA[6]、DDHBO(Differential Disturbance HBO)[7]、XPSO(eXpanded PSO)[5]和BWCOA(Best and Worst coyotes strengthened Coyote Optimization Algorithm)[1]。XPSO是具有多榜樣學(xué)習(xí)的PSO變體,而PSO是經(jīng)典智能優(yōu)化算法的代表。AHA是人工蜂鳥算法,是最新提出的MA,它和DTEO都采用了領(lǐng)地搜索策略。BWCOA是強(qiáng)化最優(yōu)和最差個(gè)體的郊狼優(yōu)化算法,它和DTEO都采用了強(qiáng)化最優(yōu)和最差個(gè)體策略。DDHBO是最新的HBO改進(jìn)變體,它與DTEO都采用了差分變異策略。ISEO是強(qiáng)化信息使用的EO,它與DTEO的共同目的就是強(qiáng)化信息使用,且它和MEO都是2022年提出的算法。這些對(duì)比算法均具有極強(qiáng)的代表性和可比性。

為了公平比較,根據(jù)文獻(xiàn)[16]的公共參數(shù)最佳設(shè)置建議,所有算法的公共參數(shù)設(shè)置相同:最大函數(shù)評(píng)價(jià)次數(shù)(Mnef)為D×10000,獨(dú)立運(yùn)行次數(shù)為51。算法的不同參數(shù)設(shè)置將導(dǎo)致不同的實(shí)驗(yàn)結(jié)果,因此對(duì)比算法的其他參數(shù)設(shè)置是根據(jù)相應(yīng)參考文獻(xiàn)中的最佳推薦進(jìn)行設(shè)置的,如表1所示。

Table 1 Parameters setting of 9 comparison algorithms表1 對(duì)比算法的參數(shù)設(shè)置

4.3 與其不完全算法的性能對(duì)比

為了驗(yàn)證每種改進(jìn)對(duì)DTEO優(yōu)化性能的貢獻(xiàn),本節(jié)將DTEO與其不完全算法在CEC2014的30維函數(shù)上進(jìn)行實(shí)驗(yàn)對(duì)比。不完全算法的描述如下:DTEOwd為無信息共享差分變異策略的EO,DTEOww為無精英與最差個(gè)體差分變異策略的EO,DTEOwb為無融合領(lǐng)地搜索差分變異策略的EO。表2給出了DTEO與其不完全算法的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果,顯著性水平值設(shè)為0.05。3種不完全算法及EO的參數(shù)設(shè)置與DTEO的保持一致?！皀”表示CEC2014測試集函數(shù)的數(shù)目30,“+”表示DTEO優(yōu)于對(duì)比算法,“≈”表示DTEO與對(duì)比算法的實(shí)驗(yàn)結(jié)果近似,“-”表示DTEO劣于對(duì)比算法。表3列出了5種算法的平均排名結(jié)果。

由表2可知,DTEO優(yōu)于4種對(duì)比算法,例如DTEO優(yōu)于和劣于EO的個(gè)數(shù)分別是27和3,說明本文對(duì)EO的改進(jìn)是有效的。

從表3可以看出,EO、DTEOwd、DTEOww、DTEOwb和DTEO的平均排名值分別為4.27,3.23,2.6,2.57和1.93。DTEO排名第一,DTEO在5種算法中獲得了最好的優(yōu)化性能,EO排名最后,其性能最差。這表明本文的改進(jìn)是有效的,并且每種改進(jìn)缺一不可,其中信息共享的隨機(jī)差分變異策略對(duì)DTEO的貢獻(xiàn)最大,而融合領(lǐng)地搜索差分變異策略貢獻(xiàn)最小。

4.4 與最先進(jìn)算法的優(yōu)化性能對(duì)比

為了驗(yàn)證DTEO的有效性,本節(jié)將其在CEC2014的30維函數(shù)上進(jìn)行實(shí)驗(yàn),并將結(jié)果與最先進(jìn)算法的結(jié)果進(jìn)行對(duì)比。對(duì)比算法包括AEO、AHA、BWCOA、XPSO、ISEO、MEO和DDHBO。表4列出了DTEO與對(duì)比算法的實(shí)驗(yàn)結(jié)果,其中最優(yōu)結(jié)果以粗體顯示。

由表4可知,在平均排名上,DTEO為2.43,總排名第一,而MEO、AEO和ISEO分別為6.47,5.57和3.57,這表明它們?cè)诮鉀Q復(fù)雜問題上搜索能力不足,而本文提出的DTEO在解決復(fù)雜優(yōu)化問題上比3種已有的EO改進(jìn)算法更優(yōu)。在3個(gè)單峰函數(shù)上,DTEO在f1上排名第一,在f2和f3上都排名第二。這說明DTEO具有更強(qiáng)的局部搜索能力,這得益于EO自身開采能力強(qiáng)的優(yōu)勢、領(lǐng)地搜索和精英粒子對(duì)最差粒子的引導(dǎo)等。在多峰函數(shù)f6和f14上,DTEO獲得的結(jié)果均優(yōu)于其對(duì)比算法的結(jié)果,雖然在其它多峰函數(shù)上獲得的結(jié)果優(yōu)勢不明顯,但比MEO和AEO的結(jié)果要好得多。顯然,信息共享的差分變異策略使得DTEO具有不錯(cuò)的全局搜索能力。在混合和組合函數(shù)上,DTEO在10個(gè)函數(shù)f17、f18、f20、f21、f23～f25和f27～f29上排名第一,且排名第一的次數(shù)最多。這表明DTEO較好地平衡了探索和開采能力,能更好地處理更為復(fù)雜的優(yōu)化問題。DTEO的平均排名為2.43,XPSO、DDHBO、BWCOA、AHA、ISEO、MEO和AEO的平均排名分別為6.07,3.73,3.23,4.63,3.57,6.47和5.57。顯然,與最先進(jìn)的算法相比,DTEO獲得了最好的優(yōu)化性能。這再次說明本文的4種改進(jìn)策略是有效的,與EO及其改進(jìn)算法相比,DTEO具有更強(qiáng)的搜索能力。

Table 2 Statistical results of DTEO and its incomplete algorithms表2 DTEO vs不完全算法的統(tǒng)計(jì)結(jié)果

Table 3 Ranking results of DTEO and its incomplete algorithms表3 DTEO與不完全算法的排名結(jié)果

4.5 運(yùn)行時(shí)間對(duì)比分析

為了討論DTEO的運(yùn)行時(shí)間,直接采用4.4節(jié)的實(shí)驗(yàn),本節(jié)僅記錄DTEO及其對(duì)比算法在CEC2014測試集30維函數(shù)上的運(yùn)行時(shí)間。9種算法獨(dú)立運(yùn)行51次獲得的平均運(yùn)行時(shí)間如圖3所示,時(shí)間單位為s。

Figure 3 Comparison of average time of 9 algorithms on 30-demensional functions圖3 9種算法在30維函數(shù)上的平均時(shí)間對(duì)比

從圖3可以看出,DTEO的運(yùn)行時(shí)間比EO、 AEO、MEO和ISEO的少,且在9種算法中,其耗時(shí)也是最少的。按耗時(shí)的升序排名,DTEO排名第一,隨后是DDHBO、ISEO、EO、BWCOA、AEO、AHA、MEO和XPSO,耗時(shí)最多的是XPSO。DTEO的耗時(shí)(4.57 s)分別是EO(7.03 s)、AEO(10.03 s)、MEO(15.52 s)、ISEO(5.52 s)、DDHBO(4.82 s)、BWCOA(7.20 s)、AHA(15.01 s)和XPSO(22.55 s)的65.00%,45.56%,29.45%,82.79%,94.81%,63.47%,30.45%和20.27%。限于篇幅,本節(jié)僅簡單討論DTEO耗時(shí)少的原因。DTEO耗時(shí)少的主要原因是:(1) 本文提出的改進(jìn)策略都是替代策略,不是添加策略,即用本文提出的更新策略替換原來的更新策略,沒有增加額外的計(jì)算;而AEO、MEO和ISEO都添加了新操作,例如AEO為每個(gè)粒子與當(dāng)前種群平均適應(yīng)度值進(jìn)行比較,故耗時(shí)比EO的耗時(shí)長。而ISEO添加了交叉操作,故在耗時(shí)上比DTEO的長。(2) 雖然引入了4種新的濃度更新方式,但任何更新方程都比EO的更新方程更簡單。(3) 對(duì)EO更新方程的簡化處理,大幅度降低了計(jì)算復(fù)雜度,節(jié)省了運(yùn)行時(shí)間。而EO中包含大量的向量運(yùn)算和指數(shù)運(yùn)算,造成了EO的運(yùn)行時(shí)間長。

4.6 Wilcoxon符號(hào)秩檢驗(yàn)

為了測試DTEO與對(duì)比算法的顯著性差異,本節(jié)進(jìn)行差異性統(tǒng)計(jì)分析。Wilcoxon符號(hào)秩檢驗(yàn)是一種非參數(shù)統(tǒng)計(jì)檢驗(yàn)[1],它常用于檢驗(yàn)2種算法之間差異的顯著性。本節(jié)采用此方法檢驗(yàn)DTEO與表4中對(duì)比算法之間的顯著性。當(dāng)DTEO的性能優(yōu)于對(duì)比算法時(shí),其秩為正;性能劣于對(duì)比算法時(shí),其秩為負(fù);性能與對(duì)比算法持平時(shí),對(duì)應(yīng)的秩平分。表5列出了DTEO與對(duì)比算法的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果,顯著性水平值設(shè)置為0.05。其中,p為實(shí)際顯著性水平值,R+和R-分別表示正秩和負(fù)秩,“n/w/l/t”表示在n個(gè)函數(shù)上DTEO優(yōu)于和劣于對(duì)比算法分別為w次和l次,相同結(jié)果為t次。如果p<0.05,則表明DTEO顯著優(yōu)于對(duì)比算法。相反,DTEO與對(duì)比算法無差異或更差。

Table 5 Wilcoxon signed rank test results表5 Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果

從表5可以看出,在30個(gè)函數(shù)上DTEO優(yōu)于XPSO、DDHBO、BWCOA、AHA、ISEO、MEO和AEO的函數(shù)個(gè)數(shù)分別為25,22,19,29,19,26和27。并且除了BWCOA的p值為5.709 6E-02外,DTEO與其它對(duì)比算法相比的p值均小于0.05,這表明DTEO顯著優(yōu)于這6種對(duì)比算法。

5 DTEO應(yīng)用于機(jī)器人路徑規(guī)劃

隨著科技的快速發(fā)展,移動(dòng)機(jī)器人被廣泛應(yīng)用到諸多領(lǐng)域,替代或協(xié)助人類完成很多危險(xiǎn)或復(fù)雜等工作。機(jī)器人路徑規(guī)劃RPP(Robot Path Planning)是受多種因素影響且難以求解的問題,所以在特定的環(huán)境下找到更為高效和安全的方法具有較強(qiáng)的實(shí)際意義。目前因MA有許多優(yōu)勢,已被廣泛應(yīng)用到路徑規(guī)劃中[2]。

5.1 MA運(yùn)用到機(jī)器人路徑規(guī)劃的基本原理

機(jī)器人路徑規(guī)劃的主要目的是在環(huán)境地圖中搜索出一條從起點(diǎn)到終點(diǎn)的距離最短的安全無碰撞路徑。圖4是機(jī)器人路徑規(guī)劃的示意圖。起點(diǎn)和終點(diǎn)分別用方形和星形表示,障礙物用圓表示。在二維直角坐標(biāo)系中,每個(gè)圓可以用式(17)表示:

r2=(x-a)2+(y-b)2

(17)

其中,(x,y)為點(diǎn)坐標(biāo),(a,b)為圓心坐標(biāo),r為半徑。

Figure 4 Best path maps of DTEO in two scenes圖4 DTEO在2個(gè)場景中獲得的最優(yōu)路徑圖

RPP要求確定一條由起點(diǎn)(x0,y0)到終點(diǎn)(xn+1,yn+1)的路徑{(x0,y0),(x1,y1),(x2,y2),…,(xn,yn),(xn+1,yn+1) },使決策目標(biāo)最優(yōu),其中,(x1,y1),(x2,y2),…,(xn,yn)為待優(yōu)化的控制點(diǎn)坐標(biāo)?？刂泣c(diǎn)的數(shù)量n決定了RPP的維度。為了降維和使路徑更加精確,常引入插值方法。本文在每次迭代中,在兩兩控制點(diǎn)間采用Spline插值法插入100個(gè)點(diǎn)。RPP的決策目標(biāo)是以帶約束的線路長度作為目標(biāo)函數(shù),并在其中引入懲罰函數(shù)法構(gòu)建規(guī)避障礙物約束,以便機(jī)器人避開障礙物,該數(shù)學(xué)模型如式(18)所示:

(18)

其中,v(k)為避障約束函數(shù),r(k)為第k個(gè)障礙物的半徑,(ak,bk)為第k個(gè)障礙物的圓心坐標(biāo)。m為障礙物個(gè)數(shù);ε為懲罰系數(shù),在本文設(shè)置為100。

將一個(gè)MA運(yùn)用到RPP的主要步驟如下:(1) 將式(18)作為目標(biāo)函數(shù),求此函數(shù)的最小值對(duì)應(yīng)的決策變量;(2) 將起點(diǎn)到終點(diǎn)之間n個(gè)控制點(diǎn)的坐標(biāo),包括橫坐標(biāo)和縱坐標(biāo)作為決策變量,在本文中n=3,則優(yōu)化問題的維度為2n;(3) 確定這n個(gè)點(diǎn)坐標(biāo)對(duì)應(yīng)的上界和下界;(4) 輸入以上信息到一個(gè)MA中;(5) 運(yùn)行MA;(6) 輸出最優(yōu)解所對(duì)應(yīng)的坐標(biāo)。

5.2 機(jī)器人路徑規(guī)劃的仿真結(jié)果及分析

為了檢驗(yàn)DTEO在路徑規(guī)劃中的性能,將其應(yīng)用到大量較為復(fù)雜的路徑規(guī)劃中。為了簡要說明問題,以2個(gè)場景的路徑規(guī)劃為示例進(jìn)行描述:場景1:4個(gè)障礙物的圓心坐標(biāo)分別是(12,40),(36,26),(45,52)和(80,60),其半徑都為8。起點(diǎn)(x0,y0)=(0,50),終點(diǎn)(xn+1,yn+1)=(90,55)。場景2:7個(gè)障礙物的圓心坐標(biāo)分別是(6,7),(20,11),(23,6),(9,15),(7,24),(16,23)和(24,23),其半徑分別為3,2,1,3,1,2和2。起點(diǎn)(x0,y0)=(1,1),終點(diǎn)(xn+1,yn+1)=(29,29)。對(duì)比算法見表1。對(duì)比算法的公共參數(shù)設(shè)置相同:Mnef為10 000,獨(dú)立運(yùn)行次數(shù)為30。DTEO獲得的最優(yōu)路徑如圖4a和圖4b所示,9種算法在2個(gè)場景中的性能分別如圖5a和圖5b所示。其中為了更清晰反映各個(gè)算法的性能,采用了各個(gè)算法獲得的實(shí)際路徑長度與它們獲得最好路徑長度之差(誤差)的對(duì)數(shù)值。9種算法獲得的均值、方差、最大值和最小值如表6所示。

Figure 5 Performance curves of different optimization algorithms圖5 不同優(yōu)化算法的性能曲線

從表6可以看出,除了場景2方差排名第二外,在其它方面,DTEO都排名第一,平均排名值為1.13,總排名第一,在9種算法中獲得了絕對(duì)優(yōu)勢。而EO的平均排名值為8.13,總排名第九,再次證明DTEO提升了EO的搜索能力,所提出的改進(jìn)策略是有效的。

從圖5a和圖5b也可以直觀看到,在9種對(duì)比算法中,無論在場景1還是在場景2中,DTEO的收斂曲線隨著目標(biāo)函數(shù)評(píng)價(jià)次數(shù)的增加,都是下降最快的,即收斂速度最快,獲得了最好的收斂性能。

總的來說,DTEO在解決RPP時(shí),優(yōu)于對(duì)比算法。這表明DTEO能夠更好地處理復(fù)雜的問題RPP,具有更強(qiáng)的競爭性。

6 結(jié)束語

針對(duì)EO中存在搜索能力不足、可操作性差和搜索效率低的問題,本文提出了一種改進(jìn)的EO,即差分變異和領(lǐng)地搜索的EO。它包括4種新型濃度更新策略:(1)融合領(lǐng)地搜索的隨機(jī)差分變異策略,提升最優(yōu)個(gè)體;(2)信息共享的隨機(jī)差分變異策略,提高算法的搜索能力;(3)簡化EO更新方程策略,提高算法的可操作性,降低計(jì)算復(fù)雜度;(4)精英與最差個(gè)體的差分變異策略,強(qiáng)化最差個(gè)體。在CEC2014測試集30維函數(shù)上的實(shí)驗(yàn)結(jié)果表明,與EO以及一些最先進(jìn)的優(yōu)化算法相比,DTEO具有更好的優(yōu)化性能。機(jī)器人路徑規(guī)劃的實(shí)驗(yàn)結(jié)果也表明,DTEO具有更強(qiáng)的競爭力,由此證明本文的改進(jìn)是有效的。2類實(shí)驗(yàn)結(jié)果表明,DTEO采用的4種濃度更新方式是有效的,不僅增加了新解方式的多樣性,也增強(qiáng)了種群多樣性,有利于全局搜索和解決不同的優(yōu)化問題。盡管DTEO的整體優(yōu)化性能優(yōu)于對(duì)比算法的,但其優(yōu)勢在CEC2014測試集多峰函數(shù)上并不明顯。因?yàn)镋O是最近提出的算法,許多方面還需要進(jìn)一步研究,如理論研究、改進(jìn)研究和應(yīng)用研究。本文僅是一種改進(jìn)研究的嘗試。另外,在CEC系列的其它復(fù)雜函數(shù)測試集和其它實(shí)際優(yōu)化問題上效果如何也是今后的研究內(nèi)容。

Table 6 Experimental results of DTEO and 8 comparison algorithms on RPP表6 DTEO與8種對(duì)比算法在路徑規(guī)劃上的實(shí)驗(yàn)結(jié)果