極值個體引導的人工蜂群算法

2022-11-15 16:17:54王聯國

計算機與生活 2022年11期

關鍵詞：優化

陳蘭，王聯國

1.甘肅農業大學機電工程學院，蘭州730070

2.甘肅農業大學信息科學技術學院，蘭州730070

仿生智能計算是一類模擬自然界中“優勝劣汰”行為的算法，具有自適應、自組織、自學習等特點，智能優化算法在解決諸多復雜優化問題方面已展現出優異的性能和巨大的發展潛力，例如：周蓉等[1]針對粒子群（particle swarm optimization，PSO）算法容易早熟收斂、易陷入局部最優、精度低等缺點，提出一種基于灰狼優化的反向學習粒子群算法，提高算法的收斂精度和速度；史春天等[2]將傳統的人工智能和群體生物結合，在解空間中搜索最優解，為圖像分割技術提供了新的解決思路；傅文淵[3]用布谷鳥巢穴間存在的萬有引力進行加速搜索，提出了一種概率變異的方法，增大了種群多樣性；張孟健等[4]將多種智能優化算法用于求解帶約束的工程優化問題，通過基準測試函數的尋優測試，分析了智能優化算法的改進方法及其發展潛力。而人工蜂群算法（artificial bee colony，ABC）作為一種典型的仿生智能計算方法，是由土耳其學者Karaboga[5]于2005 年提出的，具有原理簡單、控制參數少、容易實現、收斂速度快等優點，且己被證明是一種優異的全局優化算法，許多學者和研究人員對其進行了研究與改進。其中，劉渝根等[6]利用ABC 算法優化支持向量機（support vector machine，SVM）的接地網腐蝕速率預測模型，表明相對BP 神經網絡模型和廣義回歸神經網絡模型，采用ABC 算法優化的模型預測結果精確度和穩定性更高；宋曉宇等[7]提出一種多策略混合搜索ABC算法，利用不同搜索策略的特征及合適的混合比例，實現算法在探索和開發之間的平衡；孔德鵬等[8]提出一種基于排序選擇和精英引導策略的ABC 算法，提高算法的收斂性能；趙鳳等[9]提出一種多目標粒子群和人工蜂群混合優化的閾值圖像分割算法，在雇傭蜂更新蜜源過程中引入PSO 算法中的全局最優解，改進搜索方程，使算法跳出局部最優解；杜振鑫等[10]提出了一種集成學習ABC 算法，挖掘種群中的有用信息來抑制早熟，使算法跳出局部最優解；郭佳等[11]提出一種基于馬爾可夫（Markov）鏈的ABC 算法，根據Markov 鏈預測已知解空間的發展趨勢，使改進算法在求解精度和收斂速度上高于基本ABC 算法；Huseyin[12]提出一種基于合格搜索策略的ABC 算法，使用四種不同的搜索方程提高算法的開發能力，實現全局和局部搜索之間的平衡；Gong 等[13]提出一種混合ABC 算法，設計有效的編碼、解碼、交叉和變異算子，并采用一種有效的局部搜索方法，提高了算法的收斂速度和開發能力；Zhao 等[14]提出了一種具有記憶功能的多種群ABC 算法，并將其應用到疏散管理中，在縮短時間的同時能有效地疏散多個場景中的密集人群；宋曉宇等[15]提出一種具有自適應搜索策略的混合ABC 算法，利用目標函數值和最優解的引導，提高算法的尋優能力；Anan[16]提出了一種基于圖像邊緣檢測的ABC算法，利用ABC算法來尋找最優的邊緣濾波器，在邊緣檢測過程中不斷優化閾值。

ABC算法是一種簡單、高效的智能優化方法，已成為解決全局和局部優化問題的潛在工具。然而，對于某些優化問題，目前還沒有一種特定的算法能夠達到最優解。同時，ABC 算法也有一些缺點，例如開發能力差、易陷入局部最優、收斂速度慢。針對這些問題，本文在基本ABC算法的基礎上，提出一種極值個體引導的人工蜂群算法（extreme individual guided artificial bee colony algorithm，EABC）。該算法在雇傭蜂和跟隨蜂階段發揮全局極值和鄰域極值個體的引導作用，改進了搜索方程。全局極值個體引導搜索有利于種群中優良個體的保留和發展，避免算法陷入局部極值，向著全局最優的方向進行，提高算法全局搜索能力；鄰域極值個體引導搜索使算法更快收斂，提高局部搜索能力；采用小概率變異方法，提高算法的搜索效率，增加種群多樣性；通過基于目標函數值的貪婪選擇，提高了算法的優化性能，并通過仿真實驗驗證EABC算法的有效性。

1 基本人工蜂群算法

ABC 算法包含雇傭蜂、跟隨蜂和偵察蜂三種蜜蜂，雇傭蜂和跟隨蜂主要負責食物源的開采過程，各占蜂群總數的一半，且與食物源數目相等。對于函數優化問題，食物源的位置代表優化問題的一個可行解，蜜蜂所帶的花蜜量代表函數的適應度值，求解函數最優值的過程就是蜜蜂尋找最大花蜜量的過程。D為搜索空間的維數，SN為食物源的數目，該算法模型如下：

雇傭蜂：每個雇傭蜂對應一個食物源，雇傭蜂在食物源附近采用式（1）進行鄰域搜索，并根據食物源的花蜜量進行貪婪選擇，生成一個候選解。

跟隨蜂：每只跟隨蜂按照式（2）、式（3）的輪盤賭概率選擇一個雇傭蜂進行跟隨，并在其附近通過式（1）進行鄰域搜索，產生候選食物源：

式中，fi為函數值；fiti為第i個食物源的適應度值；pi為第i只跟隨蜂的跟隨概率。

偵察蜂：如果一個食物源連續經過limit次搜索之后仍然沒有得到改善，則該處的雇傭蜂將成為偵察蜂，并按式（4）隨機產生一個新的食物源。

2 極值個體引導的人工蜂群算法

2.1 雇傭蜂和跟隨蜂搜索方式

ABC 算法中雇傭蜂和跟隨蜂采用式（1）進行搜索，該搜索過程在一定意義上是個體空間到個體空間的隨機映射，它的概率分布顯然只與當前的位置狀態有關，沒有利用全局或局部最優個體對種群中其他個體的引導作用，因此在整個過程中收斂速度較慢。

K鄰域極值個體lbest：雇傭蜂和跟隨蜂種群為{1,2,…,i,i+1,i+2,…,i+K-1,…,SN}，第i個個體的K鄰域為{i,i+1,i+2,…,i+K-1}，lbest為{i,i+1,i+2,…,i+K-1}中目標函數值最小的個體。

本文提出的EABC算法，在雇傭蜂和跟隨蜂搜索階段中引入了全局極值個體gbest和鄰域極值個體lbest，發揮其引導作用，改進的搜索公式為：

式中，r為隨機數，r∈(0,1)，gbestj為gbest的第j維分量，lbestj為lbest的第j維分量，K為常數，通過多次實驗進行驗證，當K=5 時，算法優化效果較好。

在式（5）中，等號右邊第二部分為全局極值個體引導項，表示當前個體向全局極值個體靠攏；第三部分為鄰域極值個體引導項，表示當前個體向K鄰域極值個體靠攏；第四部分為當前個體位置與隨機個體的差分項，表示在當前位置向量附近鄰域進行搜索。

改進搜索方式中，gbest引導新的候選解向全局最優靠攏，增強算法的全局搜索能力；lbest引導蜜蜂個體進行局部搜索；隨機數r在平衡全局搜索和局部搜索方面起著重要的作用。結合ABC 算法中雇傭蜂、跟隨蜂局部搜索和偵查蜂全局搜索的轉換機制，當r較大時，雇傭蜂和跟隨蜂以gbest引導搜索為主，lbest引導搜索為輔，使算法不斷向全局最優解靠攏，使算法跳出局部極值，避免早熟收斂，提高全局搜索能力；當r較小時，以lbest引導搜索為主，gbest引導搜索為輔，蜜蜂個體在局部范圍內進行搜索，加快收斂速度，提高算法搜索精度和局部搜索能力。

2.2 小概率變異

EABC算法中，雇傭蜂和跟隨蜂采用相應搜索公式更新解后，為克服算法陷入局部極值點并出現早熟收斂的現象，對蜜蜂個體的各維度按式（6）以較小的概率進行變異，在搜索范圍內隨機取值。

式中，φ3為隨機數，φ3∈(0,1)，當φ3＜0.02 時，在搜索范圍內隨機取值，否則，保持不變。小概率變異算子增加了群體的多樣性，有利于提高算法的全局搜索能力，使算法更容易跳出局部極值。

2.3 選擇策略

在ABC 算法中，三種蜜蜂都采用基于適應度值的貪婪選擇方法選擇食物源，若候選食物源的適應值優于原來食物源的適應值，則將其取代。但是對于函數優化問題，當目標函數值大于0 且無限接近0時，對應的適應值不具有區分度。為解決此問題，本文提出的改進算法采用基于目標函數值的貪婪選擇方法選擇食物源[17]。

2.4 算法實現步驟

EABC算法的實現步驟如下：

步驟1計算每個個體的目標函數值，并找出全局最優個體；

步驟2雇傭蜂按式（5）、式（6）更新每個個體；

步驟3按式（2）、式（3）計算選擇概率；

步驟4跟隨蜂根據輪盤賭方式選擇蜜源，并按式（5）、式（6）更新每個個體；

步驟5執行偵察蜂策略；

步驟6更新全局最優個體；

步驟7終止條件是否滿足？若滿足，停止迭代并輸出全局最優解，否則轉向步驟3。

EABC算法對應的偽代碼如下所示：

算法1極值個體引導的人工蜂群算法（EABC）

輸入參數并初始化：

2.5 算法收斂性分析

算法的收斂性是衡量算法優劣的一個重要指標，優化算法的好壞很大程度上取決于其收斂性能和收斂速度，因此，不同的改進策略具有不同的收斂效果。如寧愛平等[18]利用隨機過程理論，并結合隨機搜索算法的全局收斂準則，證明了ABC 算法滿足隨機搜索算法全局收斂的兩個假設；火久元等[19]采用數形結合的方式，分析算法的收斂過程，證明了ABC算法的收斂優勢及收斂概率的變化過程；Nasr等[20]基于ABC 算法變量與食物源更新方程通解之間的關系，證明了蜂群算法的收斂性；Bansal 等[21]利用馮·諾依曼穩定性和收斂性判據，證明了改進的ABC 算法依概率收斂。

綜合上述文獻，本文采用階段性分析的方法將EABC 算法的運行過程分為全局搜索階段和局部搜索階段。全局搜索階段，EABC算法的初始收斂概率較小，隨著迭代次數的增加，收斂概率逐漸變大。因此，此階段中算法的收斂速度較慢且需要進行多次迭代，從而收斂到全局最優。局部搜索階段，EABC算法的轉移速度加快，任意兩點之間的區域長度以極快的速度減小，算法收斂概率變大，能較快收斂到全局最優。因此，此階段算法的收斂速度快、精度高。此外，EABC 算法屬于隨機搜索算法的范疇，因此可以利用隨機算法收斂準則來判定EABC 算法的收斂性。根據收斂準則[22]，EABC算法同時滿足假設1 和假設2，因此，在經過一定次數的迭代后，算法依概率收斂。

綜上所述，本文提出的EABC算法通過全局極值和鄰域極值個體的引導，依概率收斂到全局最優。

3 仿真實驗

3.1 實驗設計

為了分析和比較EABC算法的優化性能，使用表1中的28個基準函數[23]進行仿真實驗，這些函數具有單峰、多峰、可分和不可分等不同的性質。函數的這些屬性在表1的C列中給出，M表示函數是多峰的，U表示函數是單峰的，S 表示函數是可分離的，N 表示不可分離函數的特性，D列表示各問題的維數。

表1 28個標準測試函數參數Table 1 Parameters of 28 standard test functions

表1 （續）

3.2 兩種選擇策略的性能比較

為了驗證基于目標函數值的貪婪選擇的有效性，選擇表1中的部分函數f1、f3、f5、f8、f16、f17、f24、f26進行仿真實驗，并與基于適應度值的貪婪選擇方法進行比較，實驗中參數設置為維度D=30，種群規模S=30，最大迭代次數T=5 000，實驗獨立運行次數runtime=30，最大限制搜索次數limit=600，實驗結果采用30次的平均函數值。圖1是基于適應度值和目標函數值的貪婪選擇方法選擇食物源的收斂曲線圖。在每幅圖中，縱坐標用函數平均最優值的對數表示，橫坐標為迭代次數。由圖1 可知，基于目標函數值的貪婪選擇方法的優化效果更好。因此，在EABC算法中，利用目標函數值代替適應度值進行貪婪選擇，能有效地提高算法的優化性能。

圖1 兩種貪婪選擇策略收斂曲線Fig.1 Convergence curves of two greedy selection strategies

3.3 兩種算法的性能比較

3.3.1 結果與分析

為了評價EABC 算法的性能，分別用ABC 算法和EABC算法以求解28個測試函數的最小值為例進行仿真實驗，最終的測試結果采用獨立運行30 次后的平均值進行統計。

實驗中參數設置為：維度D=30，種群規模S=30，最大迭代次數T=5 000，實驗獨立運行次數runtime=30，最大限制搜索次數limit=600，兩種算法的比較結果如表2所示。

由表2中兩種算法的實驗結果比較可以看出：對于平均最優值和標準差，EABC算法對f1、f2、f3、f4、f5、f7、f8、f16、f18、f19、f24、f26、f2813個函數的優化效果遠遠好于ABC 算法，對f9、f13、f14、f21、f22等5個函數的優化效果略優于ABC算法，其余10個函數中，EABC算法和ABC算法的優化效果相當；對于最差值和最優值，EABC算法對f6、f11、f13、f15、f20、f21、f22、f23、f25、f2710 個函數的結果與ABC 算法相當，其余18個函數中，EABC算法求得的結果均優于ABC算法；對于運行時間，EABC算法對f3、f6、f7、f8、f9、f11、f20、f21、f25、f2610 個函數的結果與ABC 算法相當，其余18個函數中，EABC算法的平均運行時間略小于ABC 算法，說明EABC 算法的時間復雜度與ABC相當。

此外，實驗中使用的基準測試函數優化問題單峰、多峰、可分離性和不可分離性等不同性質[23]。結合表2仿真實驗結果，對EABC算法處理不同類型數據集的能力進行分析：對于單峰函數，只有一個局部極小值且為函數全局極小值。因此，很容易找到全局最優值；對于多峰函數，具有一個以上局部極小值，且要求優化方法具有有效的全局和局部搜索能力。由于EABC 算法通過全局極值和鄰域極值個體的引導，具有很好的全局和局部搜索能力，能夠求得復雜多峰函數的全局最優值；對于可分離函數，可被重新表述為n個單變量函數的和。因此，能較快求得全局最優值；對于不可分離函數，函數的變量之間存在相互關系，當改變某一變量時其他變量將會受到影響[23]。因此，不可分離函數的最優值求解過程較可分離函數困難得多。

表2 兩種算法的實驗結果Table 2 Experimental results of two optimization algorithms

3.3.2 維度擴展性比較

ABC算法作為一種基于群體智能的全局優化算法，在優化過程中，測試函數維度的增加會使算法復雜度增加，優化性能下降。為了分析測試函數的維度對算法性能的影響，本文將測試函數的維度擴展到60、100維，其他參數不變，實驗結果見表3和表4。

從表3 中60 維的測試實驗結果分析得出：對于平均最優值和標準差，EABC 算法對f10、f11、f12、f15、f20、f21、f24、f258 個函數的優化效果與ABC 算法相當；其余20個函數中，EABC算法的優化效果均好于ABC 算法；對于平均運行時間，EABC 算法對f1、f3、f8、f9、f10、f276 個函數的平均運行時間與ABC 算法相當，其余22個函數中，EABC算法的平均運行時間略低于ABC 算法。從表4 中100 維的測試實驗結果分析得出：對于平均最優值和標準差，EABC 算法對f10、f11、f12、f19、f20、f25、f277個函數的優化效果與ABC算法相當；其余21 個函數中，EABC 算法的優化效果均好于ABC算法；對于平均運行時間，EABC算法對f1、f3、f7、f8、f9、f10、f14、f15、f21、f24、f25、f2812個函數的平均運行時間與ABC算法相當，其余16個函數，EABC 算法的平均運行時間略低于ABC 算法。因此，在同一維度水平下，EABC 算法的優化效果更好，隨著目標函數維度的增加，EABC 算法仍能保持較好的優化性能。

表3 ABC和EABC的實驗結果（D=60）Table 3 Experimental results of ABC and EABC(D=60)

表4 ABC和EABC的實驗結果（D=100）Table 4 Experimental results of ABC and EABC(D=100)

3.4 EABC與其他智能優化算法的比較

3.4.1 優化性能比較

為考察EABC 算法的優化性能，將其與ABC[5]、ABCVSS[23]、GABC[24]、ABCBest1[25]、MSSABC[26]和MABC[27]等較新的ABC改進算法進行比較。幾種算法中，種群大小N=30，維度D=30，最大迭代次數T=5 000，算法獨立運行次數runtime=30，最大限制搜索次數limit=600，實驗結果見表5和圖2，ABCVSS算法的實驗結果直接取自文獻[23]，MABC算法的實驗結果直接取自文獻[27]。

由表5 可以看出，對于f1、f2、f3、f5、f8、f9、f13、f15、f16、f17、f21、f22、f24、f26、f2715 個函數，EABC 算法的優化效果更好；對于f7、f11、f12、f254個函數，幾種算法的優化效果一致，都達到了最優值；其余9 個函數中，EABC 算法與其他幾種算法的優化效果相當。由此說明EABC算法具有更高的優化精度，能有效克服ABC 算法收斂速度慢和陷入局部最優的缺點，具有更高的優化性能。

圖2是選取表5中ABC、GABC、ABCBest1、MSSABC、EABC這五種算法對不同屬性的部分函數運行30 次后得到的收斂曲線圖。每幅圖中，縱坐標用函數平均最優值的對數表示，橫坐標為迭代次數。

從圖2 中可以看出：在單峰可分離函數中，對于f1、f3、f8，EABC算法前期的收斂速度略低于MSSABC算法，但當迭代次數達到3 700左右時，EABC算法優于其他算法并達到理論最優值；對于f9，幾種算法收斂趨勢一致，但EABC 算法收斂速度更快，優化精度更高。在單峰不可分離函數中，對于f2、f5，當迭代次數小于3 700 時，EABC 算法的收斂速度略低于MSSABC算法，當迭代次數大于3 700時，EABC算法的收斂速度明顯加快，并且在迭代次數約4 500時開始收斂直到趨向全局最優解。在多峰不可分離函數中，對于f16、f17，EABC 與MSSABC 算法收斂趨勢一致，EABC 算法前期的收斂速度略低于MSSABC 算法，當迭代次數達到1 500 后，EABC 算法收斂速度快，優化精度高；對于f26，相比其他5 種算法，EABC算法前期的收斂速度略低于MSSABC 和GABC 算法，但當迭代次數達到3 500后，EABC算法的優化精度高于其他算法。在多峰可分離函數中，對于f18，EABC與ABC算法收斂趨勢一致，且EABC算法收斂速度大于其他5種算法，優化效果更好。