強化信息交流的堆優(yōu)化算法及其機器人路徑規(guī)劃

摘要：堆優(yōu)化算法（HBO）是最近提出的一種新型和優(yōu)秀的智能優(yōu)化算法，但需完善并拓展其應用領域。針對HBO信息交流不足導致其搜索能力不強的缺陷，提出了一種改進的HBO，即強化信息交流的HBO （information interchange strengthened HBO，ISHBO）。首先，采用一種自身交流機制用于HBO中最高領導者的狀態(tài)更新，解決因它無直接領導和同事無法參與搜索過程從而導致搜索效率低下的問題；其次，提出了一種精英反向交流策略和一種精英引導的自由交流策略，以突破當前個體僅與直接領導及同事交流的限制；最后，將以上兩種交流策略有機融合用于HBO隨機選擇的三個個體的狀態(tài)更新上以提高其搜索能力。大量的、不同類型的和不同維度的函數優(yōu)化實驗結果表明，與HBO以及其他先進算法相比，ISHBO的搜索能力更強。另外，智能優(yōu)化算法用于機器人路徑規(guī)劃的仿真結果也表明，ISHBO在解決實際優(yōu)化問題上具有更強的競爭性。

關鍵詞：智能優(yōu)化算法；堆優(yōu)化算法；信息交流；機器人；路徑規(guī)劃中圖分類號：TP301.6文獻標志碼：A文章編號：1001-3695（2022）10-007-2935-08

doi：" 10.19734/j.issn.1001-3695.2022.04.0151

Information interchange strengthened heap-based optimizer and its application to robot path planning

Zhang Bei1， Min Huasong1， Zhang Xinming2

（1.Institute of Robotics amp; Intelligent System， Wuhan University of Science amp; Technology， Wuhan 430081， China; 2.College of Computer amp; Information Engineering， Henan Normal University， Xinxiang Henan 453007， China）

Abstract：

HBO is a novel and good intelligent optimization algorithm （IOA） proposed recently， and it needs improving and applying extensively. In view of its defects such as little information interchange resulting in poor search ability， this paper proposed an improved HBO， which named information interchange strengthened HBO （ISHBO）. Firstly， it used a self-interchange strategy to update the state of the best agent to improve the efficiency of HBO since the best agent didn’t participate in the search process. Secondly， it presented an elite opposition interchange and an elite guiding free exchange， which broke through the shackle of the individual’s communication only with its direct leader and colleagues， to improve the search ability. Finally， it integrated the two strategies to update the states of 3 random agents in HBO. A lot of experimental results on functions with diverse types and different dimensions show that compared with HBO and other state-of-the-art algorithms， the search ability of ISHBO is much stronger. Moreover， the results on IOAs’ application to robot path planning also indicate that ISHBO is more competitive in solving practical optimization problems.

Key words：intelligent optimization algorithm; heap based optimizer （HBO）; information interchange; robot; path planning

0引言

在現(xiàn)實生活中隨處都存在著優(yōu)化問題，諸如機器人路徑規(guī)劃問題［1］，此問題是指在一個包含障礙物的場景下，從起點到終點尋找到一條最優(yōu)或者近似最優(yōu)的路徑，并滿足諸如耗時最少和安全性最高等約束條件。以往人們依靠精確的數學分析來求得簡單優(yōu)化問題的最優(yōu)解，但在現(xiàn)實中需要解決的問題大多都是NP難問題，且傳統(tǒng)基于精確數學的方法需要優(yōu)化問題的信息較多，還不能很好地解決這些全局優(yōu)化問題。因此，許多受某些物理現(xiàn)象和動物社會行為等啟發(fā)的群智能優(yōu)化算法（swarm-based intelligent optimization algorithm，SIOA）被提出，它們具有原理簡單、無須問題信息和易于實現(xiàn)等特點，能更好地解決全局優(yōu)化問題，因此受到廣大學者的高度關注。但無免費午餐定理［2］表明，單個SIOA不可能解決所有的優(yōu)化問題，且隨著社會的快速發(fā)展，急需解決的優(yōu)化問題越來越多，越來越復雜，因此新的和改進的SIOA不斷提出。

受公司層次管理的啟示，2020年Askari等人［3］提出了一種新型的SIOA，即堆優(yōu)化算法（HBO）。與許多其他SIOA不同，HBO模擬了公司的層級結構，采用了堆（樹型數據結構）的概念形成個體之間的交互，由此構建新解的數學模型。與一些經典的SIOA如粒子群算法（PSO）和差分進化算法（DE）等相比，HBO在解決許多經典優(yōu)化問題上更具有優(yōu)勢［3］。但HBO也存在一些不足，例如由于群體中的信息交流方式單一、個體之間的信息交流程度不夠，以及每次迭代沒有對最優(yōu)個體的狀態(tài)進行更新，導致其在解決一些優(yōu)化問題時存在搜索能力不足、效率低下等問題。因此對HBO的研究非常必要和具有較大的實際意義。由于它提出的時間較短，目前國內外對它的研究相對較少。例如，張新明等人［4］提出了一種改進的HBO，通過添加差分擾動策略強調個體之間的信息交流來提高HBO搜索能力；Rizk-Allah等人［5］提出了一種信息交流和爬山策略的HBO用于解決太陽能單元問題，對于一些較優(yōu)秀的個體有更多機會采用信息交流策略以利于探索，對于最優(yōu)個體采用爬山策略提高其解的精度；Shaheen等人［6］提出了幾種最優(yōu)個體引導的HBO，并將其應用于解決電力系統(tǒng)問題，其中代表性算法是深度開采的HBO。雖然這些改進能在一定程度上提升HBO和拓展其應用領域，但仍然存在一些問題，如信息交流的程度不足。為此，本文提出了一種增強信息交流的HBO以提高其搜索能力和效率。首先，最優(yōu)個體采用一種自身交流機制對其狀態(tài)進行更新，解決因它無直接領導和同事無法信息交流從而不能參與搜索過程導致HBO效率低下的問題，并提高了搜索能力；其次，提出了一種精英反向交流策略和精英引導的自由交流策略，以突破當前個體僅與直接領導交流及同事交流的限制，提高群體中個體之間的信息交流級別；最后，將以上兩種交流策略巧妙融合嵌入到HBO中隨機選擇三個不同個體的狀態(tài)更新上，進一步提高了搜索能力，而其他個體仍采用原來的狀態(tài)更新方式，由此構建性能優(yōu)秀的ISHBO。

1堆優(yōu)化算法

HBO算法模擬公司層次結構建立的樹狀結構形成獨特搜索機制。它選擇的是三元堆或者三叉樹，如圖1所示。

圖1中節(jié)點X1所在的層為最高層（位于此節(jié)點上的個體為最優(yōu)個體，即公司最高領導者，其適應度值最高），第一層僅有一個節(jié)點；節(jié)點X2～X4所在的層為第二層，位于這些節(jié)點上的三個個體的適應度值低于第一層個體的適應度值，位于第一、二層上的個體本文稱為精英個體。節(jié)點X5～X13所在的層次為第三層，9個節(jié)點；如此，第四層有27個節(jié)點，構成一個滿三叉樹。所有位于這些節(jié)點上的個體組成一個群體，其大小為40。在HBO中，位于同一層次的所有個體均互為同事。以節(jié)點X9為例，位于此節(jié)點上個體的同事是在X5～X13節(jié)點上，且只有一個直接領導節(jié)點X3。然而對于位于根節(jié)點X1上的個體，它沒有直接領導，且也不存在同事。

企業(yè)層次管理的最終目標是以最好的方式和最高的效率完成企業(yè)任務，層次管理結構的核心主要包括個體與其直接領導的交互、與其同事的交互和自我貢獻三個方面。與直接領導交互的數學模型描述如下：

Iji（t+1）=Lj+γλ|Lj－Iji（t）|（1）

γ=|2－4×mod（t，25）/25|（2）

λ=2r－1（3）

其中：t是當前迭代次數；T是最大迭代次數；Iji是第i個體的第j維狀態(tài)，i∈［1，N］，N為種群大小；j∈［1，D］，D為搜索空間的維度；L是當前個體的直接領導的狀態(tài)；r是均勻分布在［0，1］的隨機數；在迭代過程中，γ是一個三角波，它的值在1的左右波動，從2～0或從0～2。

當前個體與其隨機選擇同事交互的數學模型如式（4）所示。

Iji（t+1）=Cjr+γλ|Cjr－Iji（t）|f（Cr）lt;f（Ii（t））

Iji+γλ|Cjr－Iji（t）|f（Cr）≥f（Ii（t）） （4）

其中：f為目標函數；Cr是當前個體同事的狀態(tài)。因本文僅討論最小值問題，若f（Cr）lt;f（Ii），則表示同事的適應度值優(yōu)于當前個體的適應度值，個體在Cr周圍探索；否則，個體探索Ii周圍的區(qū)域，以保證搜索向好的方向進行。

在自我貢獻的模型中，個體在前一次迭代中的一些狀態(tài)信息會一直保留到下一次迭代，即當前個體在下一次迭代中不會改變其第j個分量的值。

Iji（t+1）=Iji（t）（5）

在HBO中，p1、p2和p3決定當前個體選擇這三個模型中一個模型更新其成長狀態(tài)。選擇概率的計算方法如下：

p1=1－tT（6）

p2=p1+1－p12（7）

HBO通過p1選擇自我貢獻模型，通過p2選擇與直接領導交互的數學模型，通過p3選擇與同事交互的數學模型，其中p3=1。如此個體的狀態(tài)更新方程如式（8）所示。

Iji（t+1）=

Iji（t）p≤p1

Lj+γλj|Lj－Iji（t）|pgt;p1 amp; p≤p2

Cjr+γλj|Cjr－Iji（t）|pgt;p2 amp; p≤1 amp; f（Cr）lt;f（Ii（t））

Iji+γλj|Cjr－Iji（t）|pgt;p2 amp; p≤1 amp; f（Cr）≥f（Ii（t））

（8）

因此，從位于X2開始的所有個體都通過直接領導和同事的引導即式（8）對其狀態(tài)更新。HBO的偽代碼如算法1所示。

算法1堆優(yōu)化算法

1 設置參數并隨機初始化種群;

2 評估種群中每個個體的適應度值，選擇全局最優(yōu)解;

3 構建堆;

4 for t=1 to T do

5 "for i= 2 to N do

6 for j=1 to D do

7 "p=rand（0，1）;

8 "通過式（8）產生新的狀態(tài)分量值;

9 end for

10 新的成長狀態(tài)邊界控制;

11 計算更新狀態(tài)后個體適應度值;

12 貪心選擇更新個體;

13 更新堆，更新全局最優(yōu)解;

14 "end for

15 "end for

16 輸出全局最優(yōu)解。

其中，邊界控制原則是：當Ij小于Bjl（下界），則Ij=Bjl；當Ij大于Bju （上界） ，則Ij=Bju。

從以上算法的描述可以看出，HBO具有如下主要優(yōu)勢：a）采用獨特的三元堆結構搜索機制，雖然除了最高領導者，所用個體采用同一種搜索機制，但不同層次由于受到不同的直接領導和不同同事的引導，產生的解會有較大不同，如此會獲得種群多樣性；b）從算法1可知，由于每產生一個新解就對其邊界進行控制和計算其適應度值，同時采用貪心選擇更新對應的個體，隨后更新后的優(yōu)秀個體參與后續(xù)新解的產生（如此的選擇稱為動態(tài)貪心選擇），形成一種正反饋來加快算法的收斂速度，另外式（8）的更新方式可以保證個體向更好的方向演化，從而獲得好的收斂性能；c）隨機選擇同事產生新解也有利于增強種群的多樣性；d）每次更新個體后更新堆可以在一定程度上實現(xiàn)個體間的信息交流，從而保證整個群體協(xié)同工作。

2強化信息交流的堆優(yōu)化算法（ISHBO）

雖然HBO有許多優(yōu)點，但由于提出時間較短，仍有許多地方需要完善。

a）搜索效率不高。從算法1的第5行可以看出，for循環(huán)是從2開始的，即最優(yōu)個體不參與搜索過程。這是由于最優(yōu)個體既無直接領導也無同事，無法利用式（8）更新其成長狀態(tài)，故與經典的IOA如PSO相比，搜索效率不足。

b）個體之間信息共享不足。雖然在每次迭代中，當前個體與其直接領導和同事有一定的信息交流，但與其他個體之間無直接信息交流，雖然通過更新個體后更新堆，從而達到與其他個體的信息交流，但這種交流方式有限。對于SIOA，若群內個體之間無信息交流，則不能發(fā)揮群智能的優(yōu)勢，即退化為單點優(yōu)化算法；若信息交流不足，則個體之間的協(xié)同作用受損，難以獲得強大的搜索能力。

c）解的精度不高。雖然采用動態(tài)貪心選擇方法和式（8）的更新方式可以保證個體向更好的方向演化，進而獲得一定的精度，但動態(tài)貪心算法使得算法容易陷于局部最優(yōu)，而式（8）的更新方式也會降低精度。

d）運行速度較慢。與已有的優(yōu)秀算法，諸如GWO相比，由于HBO需要創(chuàng)建堆棧和每次迭代更新堆棧，需要的時間較多。

一般說來，對于一個優(yōu)秀的SIOA，群中個體之間的信息能夠充分使用非常關鍵，應當盡可能多地使用彼此的信息來提高搜索能力。因此許多學者通過強化信息交流程度來提升現(xiàn)有的IOA。這些強化信息交流的方法包括強化信息引導和強化信息共享兩個主要方面。信息引導是指用優(yōu)秀個體的信息來引導其他個體搜索以加快算法收斂。信息共享是指個體之間的信息彼此互相使用來提高整個群搜索能力。相關的改進綜述見文獻［7］。因此針對HBO的不足，本文提出了一種強化個體信息交流的HBO。

2.1最優(yōu)個體的自身交流策略

針對HBO的最優(yōu)個體無法參與搜索過程導致搜索效率低下的問題，提出了一種最優(yōu)個體的自身交流策略，即特征隨機置換策略。其原理如下：在最優(yōu)解向量中，當前分量值可以通過本向量其他分量的值置換得到，從而產生一個新解，由于最優(yōu)個體具有最好的適應度值，它的大多數特征值應該是所有個體的特征值中最優(yōu)秀的，將其他某個優(yōu)秀的特征值遷移到當前特征值上能夠發(fā)揮其優(yōu)勢。其更新最優(yōu)個體狀態(tài)的方程如式（9）所示。

Ijg（t+1）=Ikg（t）（9）

其中：Ig是最優(yōu)個體的成長狀態(tài)；k是一個隨機整數，其取值為1～D。

從式（9）可以看出，最優(yōu)個體當前維度的值接收自身一個隨機維度的值；從整體來看，最優(yōu)個體所有的維度值被隨機重置了，即自身信息交流了，在保持最優(yōu)個體優(yōu)秀特征的基礎上，為最優(yōu)個體產生了一個新狀態(tài)，即新解，如此充分發(fā)揮了最優(yōu)個體的作用，使其有效參加了搜索過程，提高了HBO的搜索效率，也提高了其搜索能力。

2.2精英反向交流策略

反向學習策略被廣泛用于IOA的改進中，其主要用來降低算法陷于局部最優(yōu)的概率。從目前引入此策略的IOA來看，實施反向學習策略需要注意選擇哪個解的反向點、在哪個個體實施反向學習和邊界是靜態(tài)確定還是動態(tài)確定三個方面。一般說來，將反向學習策略用于IOA的方法是采用靜態(tài)邊界，并將當前解的反向點作為當前個體產生的新解，這種反向學習策略稱為一般反向學習策略。目前已經有許多改進的優(yōu)化算法提出了不同的反向學習策略。例如何小龍等人［8］提出了一種精英反向學習策略，這種策略將精英個體的反向點構建反向種群，并與當前種群合并，選出優(yōu)秀個體進入下一代群體中增加了種群的多樣性，既降低了算法陷入局部最優(yōu)的幾率，又吸收當前種群中精英個體的有用搜索信息。受此啟發(fā)，本文提出了一種精英反向交流策略，具體如式（10）所示。

Ii（t+1）=Bl+Bu－Ie（t）（10）

其中：Ie表示從四個精英中隨機選擇一個精英的狀態(tài)向量。

與文獻［8］的精英反向學習策略相比，本文精英反向學習策略主要有如下不同和優(yōu)勢：

a）實施對象不同。前者的對象是當前種群所有個體，采用m個精英個體的反向點作為更新解，而后者的對象是當前種群中的三個隨機個體，主要原因是個體的選擇隨機性和反向策略同時作用會進一步降低算法陷于局部最優(yōu)的概率。若算法陷入局部最優(yōu)，則精英解可能陷入局部最優(yōu)，因此采用反向學習策略使其有機會跳出局部最優(yōu)，而隨機個體采用精英的反向解更加提高了種群的多樣性，增加獲得全局最優(yōu)解的概率。采用三個個體進行反向學習既有利于避免算法陷于局部最優(yōu)，又不至于影響收斂速度，因為過多的個體采用反向學習雖然能增加種群的多樣性，但會影響收斂速度和解的精度。

b）邊界不同。前者的邊界值分別表示所有個體位置每一維上的最小值和最大值，每次迭代需要計算它們，即動態(tài)調整，是動態(tài)邊界，如此增加了計算復雜度。而本文反向學習策略中的Bjl和Bju分別表示搜索空間中的下邊界和上邊界，是一個優(yōu)化問題預先告知的參數，每次迭代不變，無須計算，是靜態(tài)邊界。

c）無須進行參數調整。文獻［8］精英反向學習需要確定參數精英個數m，即需要在實驗中多次手動調整，而本文的精英反向學習策略無調整參數，直接在三個隨機個體上實施反向學習策略。

2.3精英引導的自由交流策略

在HBO中當前個體僅與直接領導和同事有信息交換，與種群中其他個體之間沒有信息交流導致搜索能力不足。因此，本文提出了一種精英引導的自由交流策略，包含兩組差分。最優(yōu)個體/精英個體的狀態(tài)與當前個體的狀態(tài)差分和隨機選擇兩個個體的狀態(tài)差分，前一組差分代表引導，后一組差分代表自由交流，具體如式（11）和（12）所示。

Ii（t+1）=Ii（t）+fr×（Ig（t）－Ii（t）+Im（t）－In（t））（11）

Ii（t+1）=Ii（t）+fr×（Ie（t）－Ii（t）+Im（t）－In（t））（12）

fr=0.5×（sin（0.5×π×t）×tT+1）（13）

其中：Im和In是指從當前種群的歷史最優(yōu)解中隨機選擇的兩個解；fr是差分縮放因子。

在式（11）中，最優(yōu)個體狀態(tài)Ig引導當前個體狀態(tài)的更新，故式（11）模型稱為最優(yōu)引導的自由交流策略，在式（12）中Ie是在四個精英群中隨機選擇的一個精英的狀態(tài)，故式（12）模型稱為精英引導的自由交流策略。由式（13）可得，fr采用正弦模型，其值在0.5上下波動，迭代前期波動平緩，后期波動劇烈。當fr值較大時，可以增大當前個體的搜索范圍，有助于全局搜索；當fr值較小時，可以在當前解附近搜索更精細，有助于局部搜索。在搜索前期，在0.5上下波動幅度較小，另外，個體之間差異較大，即差值較大，這些都有利于搜索到全局最優(yōu)點；在搜索后期，在接近最優(yōu)點的0.5上下波動幅度較大，不僅有利于精搜索，而且能夠避免陷于局部最優(yōu)，另外個體之間差異較小，差值較小，這也有利于精搜索。

從式（11）（12）可知，當前個體的狀態(tài)更新受到了四個不同個體狀態(tài)的影響，最優(yōu)個體或精英個體，其本身隨機選擇的兩個個體不受限制地進行自由交流。個體在進化的過程中不僅受到了最優(yōu)個體的引導或受到精英個體的引導，可以向著更好的方向進化，加快收斂速度。同時，也受到了不同個體的相互影響，從而增強種群的多樣性，實現(xiàn)不同個體之間信息共享，提升搜索能力。另外，為了進一步發(fā)揮兩種策略的作用，在前半迭代期采用式（12），在后半迭代期采用式（11）。這是因為，采用式（12）既考慮精英引導，加快算法收斂，又考慮精英隨機選擇，降低陷于局部最優(yōu)的概率；采用式（11）更有利于后期局部搜索。

2.4改進算法的構造與流程

將2.2和2.3節(jié)的兩種交流策略融合用到隨機選擇的三個個體成長狀態(tài)更新上，其算法的偽代碼如算法2所示。

算法2兩種信息交流策略的融合

1 if rand（0，1）lt;0.5

2 從四個精英中隨機選擇一個精英個體

3 執(zhí)行式（10）

4 else

5 "if tlt;T/2

6 執(zhí)行式（12）

7 "else

8 執(zhí)行式（11）

9 "end if

10 end if

將算法2和自身交流策略融入到HBO中構成ISHBO，其算法流程如圖2所示。

從圖2可以看出，與HBO相比，ISHBO在四個個體的成長狀態(tài)更新上不同。首先最優(yōu)個體采用自身交流策略，充分發(fā)揮最優(yōu)個體的作用，使其有效參加了搜索過程，提高了搜索效率；然后在當前種群中，除了最優(yōu)個體外，隨機選擇三個兩兩不同的個體，采用算法2更新其成長狀態(tài)，其余個體成長狀態(tài)仍采用HBO的原更新方式。算法2引入了多種信息引導和共享策略，強化了信息交流，提高了群體算法（即HBO）的搜索能力。另外，ISHBO采用靜態(tài)貪心算法［9］，使得邊界控制和目標函數評價的并行計算可行，如此不僅可提高運行速度，而且提高了算法的穩(wěn)定性。因文獻［5，6］的改進算法僅僅是一種簡單改進，重點是其應用。所以本文重點比較文獻［4］的DDHBO與ISHBO的異同點。首先作用對象和個數不同。兩者都有基于個體的狀態(tài)更新方式，但前者將隨機差分擾動、最優(yōu)最差差分擾動、多層差分擾動用于最優(yōu)個體、最差個體和一般個體的三個不同個體上，并且還將基于維的差分擾動策略嵌入到式（8）中以便作用于其他個體，而后者如前文所述僅僅將三種狀態(tài)更新策略作用于四個個體上。所以前者復雜，需要確定不同的個體；而后者簡單，易于實現(xiàn)。雖然兩者都有增強信息交流的目的，但側重點不同。前者的四差分擾動策略更強調信息共享，提高探索能力；而后者在精英引導的自由交流策略強調信息共享的同時也重視信息引導，而其他兩種策略更注重最優(yōu)個體的引導作用。故前者更重視探索，而后者重視探索與開采的平衡。

3實驗結果及其分析

3.1實驗環(huán)境和評價標準

為了驗證ISHBO的性能，在經典函數優(yōu)化測試集中選擇了難以優(yōu)化的15個基準函數進行優(yōu)化實驗。這些基準函數的簡單描述如表1所示。其中， f1～f5是單峰函數， f6～f10是多峰函數， f11～f15是旋轉函數。單峰函數一般用于驗證算法的局部搜索能力；多峰函數驗證算法的全局搜搜能力；旋轉函數是較為復雜的函數，用來驗證算法處理復雜問題的能力。實驗環(huán)境采用Intel CoreTMi5-7400 CPU，主頻3.00 GHz和內存8 GB的PC機，操作系統(tǒng)采用64位的Windows 10，編程語言采用MATLAB 2017A。

由于SIOA是隨機算法，每次運行的結果會所不同，故在本文中采用均值（mean）、方差（std）和排名來評估一個算法的優(yōu)劣，mean用來評價算法的優(yōu)化能力，std用來衡量算法的穩(wěn)定性。對于一個最小值的優(yōu)化問題，若一個SIOA在獨立運行一定次數后獲得的均值越小，表示其性能越好，排名越高；在均值相同的情況下，若方差越小，表明其穩(wěn)定性越強和排名越高。若兩者相同，則排名相同。另外，表中最好的結果均用粗體表示。

3.2與不完全算法比較

為了驗證本文提出的三種策略對ISHBO的貢獻，本節(jié)進行不完全算法實驗。這些不完全算法包括ISHBOa、ISHBOb和ISHBOc。其中，ISHBOa是ISHBO無最優(yōu)個體自身交流策略的不完全算法，即ISHBOa中的最優(yōu)個體與HBO中的最優(yōu)個體一樣不參與搜索過程；ISHBOb是ISHBO無精英反向交流策略的不完全算法；ISHBOc是ISHBO無精英引導自由交流策略的不完全算法。受版面限制和為了更能說明問題，選擇了四個具有代表性的函數進行實驗。它們是單峰函數f3、多峰函數f7和f10以及旋轉函數f14。HBO、ISHBO和其三個不完全算法的參數設置相同，ISHBO的參數設置見3.3節(jié)。五個算法在4個函數30維上的實驗結果如表2所示。從表2可以看出，在4個函數上，ISHBO都排名第一，而HBO都排名最后，三個排名第四，一個排名第五，而三個不完全算法的排名位于ISHBO和HBO之中。這說明本文提出的每一種改進策略都是有效的，各自都在不同程度上提升了HBO的性能。但只有三種策略融合在一起構建的ISHBO才會使HBO的性能最大化，證明了本文提出的三種改進策略不可或缺和它們的融合并嵌入到HBO的方式是合適的。

3.3與最先進的算法比較

為了驗證ISHBO的性能，進行大量的對比實驗。因為HBO是新型SIOA，在當前的研究中，有少量的改進研究報道。為了凸顯ISHBO的性能，選取的對比算法除了HBO［3］和其變體DDHBO［4］外，還選擇了較為流行的SIOA最新改進算法。它們是LEOWOA［8］、GCCOA［9］、XPSO［10］、HCLDMS-PSO［11］、LPalmDE［12］、HGWOA［13］和HBBOS［14］。其中，XPSO 和HCLDMS-PSO是PSO的最新改進算法；LPalmDE是最近提出的優(yōu)秀DE變體；LEOWOA和GCCOA 分別是鯨魚優(yōu)化算法和郊狼優(yōu)化算法的改進算法；HGWOA是ABC和GWO的混合算法；HBBOS是BBO和SFLA的混合算法，一般來說，混合算法的最大優(yōu)勢在于它的性能優(yōu)于其構建的單一算法。這些對比算法具有較強的代表性和可比性。

為了公平起見，所有對比算法的公共參數設置相同：獨立運行次數為30次；D=30，最大目標函數評價次數（Mnef）設置為50 000；D=50，Mnef為70 000。HBO、DDHBO和ISHBO參數設置相同，依據文獻［3］，種群數N為40。對比算法的其他參數直接采用相應的文獻中推薦的最佳設置。10種算法在30維和50維的實驗結果如表3所示。

從表3可以看出，無論在30維或50維上，ISHBO獲得了絕對的優(yōu)勢，除了f3在所有的函數上都排名第一，即排名第一的個數都是14，在大多數情況下獲得了理想的最優(yōu)值0。在平均排名上，ISHBO為1.07，而HBO為7.83，排名第10，這說明本文提出的改進措施大幅度提升了HBO的性能，改進策略是有效的。具體分析如下：在30維的五個單峰函數上，HBO獲得三個排名最后，一個排名第五和一個排名第九，這說明ISHBO大幅度提高了HBO的開采能力；在五個多峰函數上，HBO的性能優(yōu)于在單峰函數上的性能，但仍劣于ISHBO的性能，這證明本文提出的改進策略強化了HBO的探索能力；在五個旋轉函數上，HBO的均值和方差都劣于ISHBO的均值和方差，這說明ISHBO比HBO具有更強的處理復雜優(yōu)化問題的能力。以上都說明ISHBO提高了HBO的搜索能力。在50維上的結果與在30維上的結果類似，雖然50維的問題更加難以優(yōu)化，但與HBO相比，ISHBO仍然獲得了更好的結果，這也說明ISHBO具有更強的擴展性和普適性。另外，與其他九個對比算法相比，無論是在30維還是50維上，ISHBO都獲得更好的均值和方差。這說明ISHBO具有更好的精度和穩(wěn)定性，再次證明本文算法改進策略是有效的。

3.4時間對比

評價一個改進算法的好壞不僅要考察它的優(yōu)化性能好壞，還應評價它的運行速度快慢。為了討論ISHBO的運行速度，本節(jié)對其進行時間的測試和分析。實驗環(huán)境見3.1節(jié)，時間單位為s，10個算法在30維和50維函數上獨立運行30次的平均時間如圖3所示。

從圖3可以看出，ISHBO的耗時在10個算法中是最少的，其耗時為0.25 s，分別是HBO（0.93 s）、XPSO（3.46 s）、DDHBO（0.3 s）、LPamDE（0.48 s）、HGWOA （1.11 s）、HCLDMS-PSO（2.28 s）、 HBBOS（0.65 s）、LEOWOA（0.93 s） 和GCCOA（1.08 s）耗時的27%、7%、83%、52%、11%、23%、11%、38%、27%和23%。ISHBO的耗時比HBO的耗時少，主要原因是在ISHBO采用了目標函數和邊界控制等并行計算，以及采用比式（2）復雜度低的式（9）～（12）。

從3.3節(jié)可得ISHBO性能最好，本節(jié)又證明了它的運行時間最少，因此它的搜索效率是10種算法中最高的。

3.5統(tǒng)計分析

為了驗證ISHBO與對比算法的顯著性差異，對ISHBO獲得的結果和其對比算法的結果進行Wilcoxon符號秩檢驗分析。Wilcoxon符號秩檢驗［15］是一種非參數的統(tǒng)計性分析方法。檢驗的數據直接來自表3，檢驗的結果如表4所示。其中，R+代表正秩的總和，R-代表負秩的總和，當ISHBO與對比算法性能相同時，對應的秩平分給R+和R-，p值是由R+和R-得到。“n/w/t/l”分別表示在n個函數上ISHBO與對比算法相比，取得了性能優(yōu)異w次，相同t次，較差l次。檢驗實驗中，顯著水平定為0.05。若p≤0.05，表明兩個對比算法有顯著性的差異，否則其差異不顯著。

從表2可以看出，所有的p值都小于0.05，表明ISHBO的優(yōu)化性能都顯著地優(yōu)于對比算法的優(yōu)化性能，進一步證明了本文算法是可行和有效的。

4ISHBO應用到機器人路徑規(guī)劃上

隨著社會和科技的快速發(fā)展，移動機器人被應用到許多領域，代替或協(xié)助人類完成在軍事、危險或復雜環(huán)境中的很多工作。機器人路徑規(guī)劃在本質上是NP難問題，受多種因素影響而難以求解的問題，所以在特定的環(huán)境下找到高效安全的方法，使其行走路徑得到優(yōu)化具有較強的實際意義。較為經典的方法如Dijkstra算法、A*算法和人工勢場法等傳統(tǒng)方法，以及基于粒子群算、遺傳算法和蟻群算法等現(xiàn)代SIOA［1］。因基于SIOA的方法有許多優(yōu)勢，已被廣泛應用到路徑規(guī)劃中。

4.1SIOA運用到機器人路徑規(guī)劃的基本原理

路徑規(guī)劃的研究目的是在環(huán)境地圖中搜索出一條從起點到終點的長度最短的安全無碰撞路徑。圖4給出了機器人路徑規(guī)劃（robot path planning， RPP）的示意圖。起點和終點分別用方形和星形表示，用圓表示障礙物。在二維直角坐標系中，每個圓可以用式（14）表示：

r2=（x－a）2+（y－b）2（14）

其中：（a，b）為障礙物的圓心; r 為半徑。

RPP要求確定一條由連接起點（x0，y0）和終點（xn+1，yn+1）的路徑P={（x0，y0）， （x1，y1）， （x2，y2），…， （xn，yn）， （xn+1，yn+1） }，從而使決策目標最優(yōu)。其中，（x1，y1）， （x2，y2），…， （xn，yn）為待優(yōu)化的導航點坐標。導航點的數碼n決定了當前優(yōu)化問題的維度。為了消除連接線明顯的棱角，本文引入了spline插值方法。RPP常常以帶約束的線路長度作為目標函數，并在其中引入懲罰函數法構建規(guī)避障礙物約束，以便解決機器人避開障礙物，如此的數學模型如式（15）所示。

L=∑ni=0（xi+1-xi）2+（yi+1-yi）2+ε∑mk=1v（k）

v（k）=max1-（xi-ai）2+（yi-bk）2r（k），0（15）

其中：v（k）為避障約束函數；r（k）為第k個障礙物的半徑；（ak， bk）為第k個障礙物的圓心坐標；m為障礙物個數; ε為懲罰系數，在本文設置為100。

4.2ISHBO運用到機器人路徑規(guī)劃的仿真結果及分析

將ISHBO運用到路徑規(guī)劃中，就是以式（15）作為目標函數，以導航點坐標作為參量尋找使L值最小的路徑。

為了證明ISHBO在路徑規(guī)劃中的性能，將其應用到大量和較為復雜的路徑規(guī)劃中。為了簡要說明問題，以七個障礙物的路徑規(guī)劃為示例進行描述。七個障礙物的圓心坐標分別是（6，6）（20，11）（23，6）（9，15）（7，24）（16，23）和（24，23），其半徑分別為3、2、1、3、1、2和2。（x0，y0）=（1，1），（xn+1，yn+1）=（29，29）。對比算法選擇了HBO和改進算法DDHBO，以及在第3.3節(jié)中排名第二的LEOWOA和第三的HBBOS作為對比算法。四種算法的公共參數設置相同：依據文獻［16］，Mnef為10 000，獨立運行次數為30，其他參數的設置見相應的文獻最佳設置。四種算法獲得的最優(yōu)路徑如圖4所示。實驗也記錄了四種算法獲得的均值、方差、最大值和最小值。另外選擇六個算法PSO、FF（農田肥力算法）、HS（和聲搜索算法）、IWO（入侵雜草優(yōu)化算法）和DDAO（動態(tài)差分退火優(yōu)化算法）作為對比算法，這些算法的實驗數據直接來自文獻［16］，實驗結果如表5所示。

從表5可以看出，在均值和最差值上，ISHBO排名第一，它的均值為41.054；其最差值為41.833 4，該值甚至比HS、IWO、DDAO和HBO的最好值還要好。雖然ISHBO在最好值上排名第二，但其總排名第一。從圖4也可以直觀地看到，ISHBO的獲取最優(yōu)路徑要比HBO獲取的路徑短，也不同于DDHBO和HBBOS所獲得的最優(yōu)路徑。

總的來說，ISHBO在解決RPP時，優(yōu)于對比算法，表明ISHBO能較好地處理RPP，具有較強的競爭性。

5結束語

HBO是最近提出的一種新型智能優(yōu)化算法，雖然具有許多優(yōu)勢，但仍需要改進和完善以及擴展其應用領域。本文針對HBO信息交流不足導致搜索能力不強等缺陷，提出了一種改進的HBO算法，即強化信息交流的HBO（ISHBO）。首先，采用一種自身交流策略用于HBO中最高領導者的狀態(tài)更新以提升搜索能力，并解決因它無直接領導和同事無法信息交流導致HBO效率低下的問題；其次，提出一種精英反向交流策略和一種精英引導的自由交流策略，以突破個體交流僅與直接領導及同事交流的限制；最后，將以上交流方式融合嵌入到HBO中隨機選擇三個不同個體的狀態(tài)更新上，更進一步提高HBO的搜索能力，而其他個體的狀態(tài)更新仍采用原來的更新方式；另外，采用靜態(tài)貪心算法強化了算法的穩(wěn)定性，如此形成ISHBO，并將ISHBO運用在RPP上。15個不同維度和不同類型基準函數集的實驗結果表明，與HBO和其他先進算法相比，ISHBO的搜索能力更強，運行速度最快，精度和效率最高。RPP的實驗結果也表明與對比算法相比，ISHBO有更強的競爭性。雖然ISHBO在實驗和應用中獲得了較好的性能，但還存在一些不足：a）同HBO一樣，ISHBO是否收斂到全局最優(yōu)解需要理論證明；b）在迭代前期，p1的值很大，接近1，此時通過式（8）進行更新，可能產生的新解與原解相同，此新解是無效的，使得算法在迭代前期的搜索能力較差。因此，ISHBO還需要進一步完善。另外HBO是最近提出的SIOA，有許多地方值得研究，如理論研究、改進研究和應用研究。

參考文獻：

［1］王梓強，胡曉光，李曉筱，等. 移動機器人全局路徑規(guī)劃算法綜述 ［J］. 計算機科學，2021，48（10）： 19-29. （Wang Ziqiang，Hu Xiao-guang，Li Xiaoxiao，et al. Overview of global path planning algorithms for mobile robots ［J］. Computer Science，2021，48（10）： 19-29.）

［2］Wolpert D H，Macready W G. No free lunch theorems for optimization ［J］. IEEE Trans on Neural Networks，1997，1（1）： 67-82.

［3］Askari Q，Saeed M，Younas I. Heap-based optimizer inspired by corporate rank hierarchy for global optimization ［J］. Expert Systems with Applications，2020，161（12）： 113702.

［4］張新明，溫少晨，劉尚旺. 差分擾動的堆優(yōu)化算法 ［J］. 計算機應用，2022，42（8）：2519-2527. （Zhang Xinming，Weng Shaochen，Liu Shangwang. Differential disturbance heap-based optimizer ［J］. Journal of Computer Applications，2022，42（8）：2519-2527.）

［5］Rizk-Allah R M，El-Fergany A. Emended heap-based optimizer for characterizing performance of industrial solar generating units using triple-diode model ［J］. Energy，2021，237（12）： 121561.

［6］Shaheen A M，Elsayed A M，Ginidi A R，et al. A heap-based algorithm with deeper exploitative feature for optimal allocations of distri-buted generations with feeder reconfiguration in power distribution networks ［J］. Knowledge-Based Systems，2022，241（4）： 108269.

［7］Zhang Xinming，Lin Qiuying. Information-utilization strengthened equilibrium optimizer ［J］. Artificial Intelligence Review，2022，55（6）： 4241-4274.

［8］何小龍，張剛，陳躍華，等. 融合Lévy飛行和精英反向學習的WOA-SVM多分類算法［J］. 計算機應用研究，2021，38（12）： 3640-3645. （He Xiaolong，Zhang Gang，Chen Yuehua，et al. Multi-class algorithm of WOA-SVM using Lévy flight and elite opposition-based learning ［J］. Application Research of Computers，2021，38（12）： 3640-3645. ）

［9］張新明，付子豪，陳海燕，等. 全局引導和相互作用的郊狼優(yōu)化算法及其應用 ［J］. 計算機應用研究，2020，37（9）： 2711-2717. （Zhang Xinming，F(xiàn)u Zihao，Chen Haiyan，et al. Coyote optimization algorithm with global guidance and coyote interaction and its application ［J］. Application Research of Computers，2020，37（9）： 2711-2717.）

［10］Xia Xuewen，Gui Ling，He Guoliang，et al. An expanded particle swarm optimization based on multi-exemplar and forgetting ability ［J］. Information Sciences，2020，508（1）： 105-120.

［11］Wang Shengliang，Liu Genyou，Gao Ming，et al. Heterogeneous comprehensive learning and dynamic multi-swarm particle swarm optimizer with two mutation operators［J］. Information Sciences，2020，540（11）： 175-201.

［12］Meng Zhenyu，Pan J S，Tseng K K. PaDE： an enhanced differential evolution algorithm with novel control parameter adaptation schemes for numerical optimization ［J］. Knowledge-Based System，2019，168（3）： 80-99.

［13］張新明，王霞，康強，等. GWO與ABC的混合優(yōu)化算法及其聚類優(yōu)化 ［J］. 電子學報，2018，46（10）： 2430-2442. （Zhang Xinming，Wang Xia，Kang Qiang，et al. Hybrid grey wolf optimizer with artificial bee colony and its application to clustering optimization ［J］. Acta Electronica Sinica，2018，46（10）： 2430-2442. ）

［14］Zhang Xinming，Kang Qiang，Wang Xia.Hybrid biogeography-based optimization with shuffled frog leaping algorithm and its application to minimum spanning tree problems ［J］. Swarm and Evolutionary Computation，2019，49（9）： 245-265.

［15］Derrac J，Garica S，Molina D，et al.A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms ［J］. Swarm and Evolutionary Computation，2011，1（1）： 3-18.

［16］Ghafil H N，Jarmai K，Dynamic differential annealed optimization： new metaheuristic optimization algorithm for engineer applications ［J］. Applied Soft Computing，2020，93（8）： 106392.

收稿日期：2022-04-15；修回日期：2022-05-23

作者簡介：張貝（1988-），男，湖北孝感人，工程師，碩士研究生，主要研究方向為機器人和智能優(yōu)化算法（myspace01@qq.com）；閔華松（1969-），男，湖北應城人，教授，博導，博士，主要研究方向為嵌入式系統(tǒng)與智能機器人；張新明（1963-），男，湖北孝感人，教授，碩導，主要研究方向為智能優(yōu)化算法、數字圖像處理和模式識別等.