陳 蘭,王聯(lián)國
1.甘肅農(nóng)業(yè)大學 機電工程學院,蘭州730070
2.甘肅農(nóng)業(yè)大學 信息科學技術學院,蘭州730070
仿生智能計算是一類模擬自然界中“優(yōu)勝劣汰”行為的算法,具有自適應、自組織、自學習等特點,智能優(yōu)化算法在解決諸多復雜優(yōu)化問題方面已展現(xiàn)出優(yōu)異的性能和巨大的發(fā)展?jié)摿?,例如:周蓉等[1]針對粒子群(particle swarm optimization,PSO)算法容易早熟收斂、易陷入局部最優(yōu)、精度低等缺點,提出一種基于灰狼優(yōu)化的反向?qū)W習粒子群算法,提高算法的收斂精度和速度;史春天等[2]將傳統(tǒng)的人工智能和群體生物結合,在解空間中搜索最優(yōu)解,為圖像分割技術提供了新的解決思路;傅文淵[3]用布谷鳥巢穴間存在的萬有引力進行加速搜索,提出了一種概率變異的方法,增大了種群多樣性;張孟健等[4]將多種智能優(yōu)化算法用于求解帶約束的工程優(yōu)化問題,通過基準測試函數(shù)的尋優(yōu)測試,分析了智能優(yōu)化算法的改進方法及其發(fā)展?jié)摿?。而人工蜂群算法(artificial bee colony,ABC)作為一種典型的仿生智能計算方法,是由土耳其學者Karaboga[5]于2005 年提出的,具有原理簡單、控制參數(shù)少、容易實現(xiàn)、收斂速度快等優(yōu)點,且己被證明是一種優(yōu)異的全局優(yōu)化算法,許多學者和研究人員對其進行了研究與改進。其中,劉渝根等[6]利用ABC 算法優(yōu)化支持向量機(support vector machine,SVM)的接地網(wǎng)腐蝕速率預測模型,表明相對BP 神經(jīng)網(wǎng)絡模型和廣義回歸神經(jīng)網(wǎng)絡模型,采用ABC 算法優(yōu)化的模型預測結果精確度和穩(wěn)定性更高;宋曉宇等[7]提出一種多策略混合搜索ABC算法,利用不同搜索策略的特征及合適的混合比例,實現(xiàn)算法在探索和開發(fā)之間的平衡;孔德鵬等[8]提出一種基于排序選擇和精英引導策略的ABC 算法,提高算法的收斂性能;趙鳳等[9]提出一種多目標粒子群和人工蜂群混合優(yōu)化的閾值圖像分割算法,在雇傭蜂更新蜜源過程中引入PSO 算法中的全局最優(yōu)解,改進搜索方程,使算法跳出局部最優(yōu)解;杜振鑫等[10]提出了一種集成學習ABC 算法,挖掘種群中的有用信息來抑制早熟,使算法跳出局部最優(yōu)解;郭佳等[11]提出一種基于馬爾可夫(Markov)鏈的ABC 算法,根據(jù)Markov 鏈預測已知解空間的發(fā)展趨勢,使改進算法在求解精度和收斂速度上高于基本ABC 算法;Huseyin[12]提出一種基于合格搜索策略的ABC 算法,使用四種不同的搜索方程提高算法的開發(fā)能力,實現(xiàn)全局和局部搜索之間的平衡;Gong 等[13]提出一種混合ABC 算法,設計有效的編碼、解碼、交叉和變異算子,并采用一種有效的局部搜索方法,提高了算法的收斂速度和開發(fā)能力;Zhao 等[14]提出了一種具有記憶功能的多種群ABC 算法,并將其應用到疏散管理中,在縮短時間的同時能有效地疏散多個場景中的密集人群;宋曉宇等[15]提出一種具有自適應搜索策略的混合ABC 算法,利用目標函數(shù)值和最優(yōu)解的引導,提高算法的尋優(yōu)能力;Anan[16]提出了一種基于圖像邊緣檢測的ABC算法,利用ABC算法來尋找最優(yōu)的邊緣濾波器,在邊緣檢測過程中不斷優(yōu)化閾值。
ABC算法是一種簡單、高效的智能優(yōu)化方法,已成為解決全局和局部優(yōu)化問題的潛在工具。然而,對于某些優(yōu)化問題,目前還沒有一種特定的算法能夠達到最優(yōu)解。同時,ABC 算法也有一些缺點,例如開發(fā)能力差、易陷入局部最優(yōu)、收斂速度慢。針對這些問題,本文在基本ABC算法的基礎上,提出一種極值個體引導的人工蜂群算法(extreme individual guided artificial bee colony algorithm,EABC)。該算法在雇傭蜂和跟隨蜂階段發(fā)揮全局極值和鄰域極值個體的引導作用,改進了搜索方程。全局極值個體引導搜索有利于種群中優(yōu)良個體的保留和發(fā)展,避免算法陷入局部極值,向著全局最優(yōu)的方向進行,提高算法全局搜索能力;鄰域極值個體引導搜索使算法更快收斂,提高局部搜索能力;采用小概率變異方法,提高算法的搜索效率,增加種群多樣性;通過基于目標函數(shù)值的貪婪選擇,提高了算法的優(yōu)化性能,并通過仿真實驗驗證EABC算法的有效性。
ABC 算法包含雇傭蜂、跟隨蜂和偵察蜂三種蜜蜂,雇傭蜂和跟隨蜂主要負責食物源的開采過程,各占蜂群總數(shù)的一半,且與食物源數(shù)目相等。對于函數(shù)優(yōu)化問題,食物源的位置代表優(yōu)化問題的一個可行解,蜜蜂所帶的花蜜量代表函數(shù)的適應度值,求解函數(shù)最優(yōu)值的過程就是蜜蜂尋找最大花蜜量的過程。D為搜索空間的維數(shù),SN為食物源的數(shù)目,該算法模型如下:
雇傭蜂:每個雇傭蜂對應一個食物源,雇傭蜂在食物源附近采用式(1)進行鄰域搜索,并根據(jù)食物源的花蜜量進行貪婪選擇,生成一個候選解。
跟隨蜂:每只跟隨蜂按照式(2)、式(3)的輪盤賭概率選擇一個雇傭蜂進行跟隨,并在其附近通過式(1)進行鄰域搜索,產(chǎn)生候選食物源:
式中,fi為函數(shù)值;fiti為第i個食物源的適應度值;pi為第i只跟隨蜂的跟隨概率。
偵察蜂:如果一個食物源連續(xù)經(jīng)過limit次搜索之后仍然沒有得到改善,則該處的雇傭蜂將成為偵察蜂,并按式(4)隨機產(chǎn)生一個新的食物源。
ABC 算法中雇傭蜂和跟隨蜂采用式(1)進行搜索,該搜索過程在一定意義上是個體空間到個體空間的隨機映射,它的概率分布顯然只與當前的位置狀態(tài)有關,沒有利用全局或局部最優(yōu)個體對種群中其他個體的引導作用,因此在整個過程中收斂速度較慢。
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}中目標函數(shù)值最小的個體。
本文提出的EABC算法,在雇傭蜂和跟隨蜂搜索階段中引入了全局極值個體gbest和鄰域極值個體lbest,發(fā)揮其引導作用,改進的搜索公式為:
式中,r為隨機數(shù),r∈(0,1),gbestj為gbest的第j維分量,lbestj為lbest的第j維分量,K為常數(shù),通過多次實驗進行驗證,當K=5 時,算法優(yōu)化效果較好。
在式(5)中,等號右邊第二部分為全局極值個體引導項,表示當前個體向全局極值個體靠攏;第三部分為鄰域極值個體引導項,表示當前個體向K鄰域極值個體靠攏;第四部分為當前個體位置與隨機個體的差分項,表示在當前位置向量附近鄰域進行搜索。
改進搜索方式中,gbest引導新的候選解向全局最優(yōu)靠攏,增強算法的全局搜索能力;lbest引導蜜蜂個體進行局部搜索;隨機數(shù)r在平衡全局搜索和局部搜索方面起著重要的作用。結合ABC 算法中雇傭蜂、跟隨蜂局部搜索和偵查蜂全局搜索的轉(zhuǎn)換機制,當r較大時,雇傭蜂和跟隨蜂以gbest引導搜索為主,lbest引導搜索為輔,使算法不斷向全局最優(yōu)解靠攏,使算法跳出局部極值,避免早熟收斂,提高全局搜索能力;當r較小時,以lbest引導搜索為主,gbest引導搜索為輔,蜜蜂個體在局部范圍內(nèi)進行搜索,加快收斂速度,提高算法搜索精度和局部搜索能力。
EABC算法中,雇傭蜂和跟隨蜂采用相應搜索公式更新解后,為克服算法陷入局部極值點并出現(xiàn)早熟收斂的現(xiàn)象,對蜜蜂個體的各維度按式(6)以較小的概率進行變異,在搜索范圍內(nèi)隨機取值。
式中,φ3為隨機數(shù),φ3∈(0,1),當φ3<0.02 時,在搜索范圍內(nèi)隨機取值,否則,保持不變。小概率變異算子增加了群體的多樣性,有利于提高算法的全局搜索能力,使算法更容易跳出局部極值。
在ABC 算法中,三種蜜蜂都采用基于適應度值的貪婪選擇方法選擇食物源,若候選食物源的適應值優(yōu)于原來食物源的適應值,則將其取代。但是對于函數(shù)優(yōu)化問題,當目標函數(shù)值大于0 且無限接近0時,對應的適應值不具有區(qū)分度。為解決此問題,本文提出的改進算法采用基于目標函數(shù)值的貪婪選擇方法選擇食物源[17]。
EABC算法的實現(xiàn)步驟如下:
步驟1計算每個個體的目標函數(shù)值,并找出全局最優(yōu)個體;
步驟2雇傭蜂按式(5)、式(6)更新每個個體;
步驟3按式(2)、式(3)計算選擇概率;
步驟4跟隨蜂根據(jù)輪盤賭方式選擇蜜源,并按式(5)、式(6)更新每個個體;
步驟5執(zhí)行偵察蜂策略;
步驟6更新全局最優(yōu)個體;
步驟7終止條件是否滿足?若滿足,停止迭代并輸出全局最優(yōu)解,否則轉(zhuǎn)向步驟3。
EABC算法對應的偽代碼如下所示:
算法1極值個體引導的人工蜂群算法(EABC)
輸入?yún)?shù)并初始化:
算法的收斂性是衡量算法優(yōu)劣的一個重要指標,優(yōu)化算法的好壞很大程度上取決于其收斂性能和收斂速度,因此,不同的改進策略具有不同的收斂效果。如寧愛平等[18]利用隨機過程理論,并結合隨機搜索算法的全局收斂準則,證明了ABC 算法滿足隨機搜索算法全局收斂的兩個假設;火久元等[19]采用數(shù)形結合的方式,分析算法的收斂過程,證明了ABC算法的收斂優(yōu)勢及收斂概率的變化過程;Nasr等[20]基于ABC 算法變量與食物源更新方程通解之間的關系,證明了蜂群算法的收斂性;Bansal 等[21]利用馮·諾依曼穩(wěn)定性和收斂性判據(jù),證明了改進的ABC 算法依概率收斂。
綜合上述文獻,本文采用階段性分析的方法將EABC 算法的運行過程分為全局搜索階段和局部搜索階段。全局搜索階段,EABC算法的初始收斂概率較小,隨著迭代次數(shù)的增加,收斂概率逐漸變大。因此,此階段中算法的收斂速度較慢且需要進行多次迭代,從而收斂到全局最優(yōu)。局部搜索階段,EABC算法的轉(zhuǎn)移速度加快,任意兩點之間的區(qū)域長度以極快的速度減小,算法收斂概率變大,能較快收斂到全局最優(yōu)。因此,此階段算法的收斂速度快、精度高。此外,EABC 算法屬于隨機搜索算法的范疇,因此可以利用隨機算法收斂準則來判定EABC 算法的收斂性。根據(jù)收斂準則[22],EABC算法同時滿足假設1 和假設2,因此,在經(jīng)過一定次數(shù)的迭代后,算法依概率收斂。
綜上所述,本文提出的EABC算法通過全局極值和鄰域極值個體的引導,依概率收斂到全局最優(yōu)。
為了分析和比較EABC算法的優(yōu)化性能,使用表1中的28個基準函數(shù)[23]進行仿真實驗,這些函數(shù)具有單峰、多峰、可分和不可分等不同的性質(zhì)。函數(shù)的這些屬性在表1的C列中給出,M表示函數(shù)是多峰的,U表示函數(shù)是單峰的,S 表示函數(shù)是可分離的,N 表示不可分離函數(shù)的特性,D列表示各問題的維數(shù)。
表1 28個標準測試函數(shù)參數(shù)Table 1 Parameters of 28 standard test functions
表1 (續(xù))
為了驗證基于目標函數(shù)值的貪婪選擇的有效性,選擇表1中的部分函數(shù)f1、f3、f5、f8、f16、f17、f24、f26進行仿真實驗,并與基于適應度值的貪婪選擇方法進行比較,實驗中參數(shù)設置為維度D=30,種群規(guī)模S=30,最大迭代次數(shù)T=5 000,實驗獨立運行次數(shù)runtime=30,最大限制搜索次數(shù)limit=600,實驗結果采用30次的平均函數(shù)值。圖1是基于適應度值和目標函數(shù)值的貪婪選擇方法選擇食物源的收斂曲線圖。在每幅圖中,縱坐標用函數(shù)平均最優(yōu)值的對數(shù)表示,橫坐標為迭代次數(shù)。由圖1 可知,基于目標函數(shù)值的貪婪選擇方法的優(yōu)化效果更好。因此,在EABC算法中,利用目標函數(shù)值代替適應度值進行貪婪選擇,能有效地提高算法的優(yōu)化性能。
圖1 兩種貪婪選擇策略收斂曲線Fig.1 Convergence curves of two greedy selection strategies
3.3.1 結果與分析
為了評價EABC 算法的性能,分別用ABC 算法和EABC算法以求解28個測試函數(shù)的最小值為例進行仿真實驗,最終的測試結果采用獨立運行30 次后的平均值進行統(tǒng)計。
實驗中參數(shù)設置為:維度D=30,種群規(guī)模S=30,最大迭代次數(shù)T=5 000,實驗獨立運行次數(shù)runtime=30,最大限制搜索次數(shù)limit=600,兩種算法的比較結果如表2所示。
由表2中兩種算法的實驗結果比較可以看出:對于平均最優(yōu)值和標準差,EABC算法對f1、f2、f3、f4、f5、f7、f8、f16、f18、f19、f24、f26、f2813個函數(shù)的優(yōu)化效果遠遠好于ABC 算法,對f9、f13、f14、f21、f22等5個函數(shù)的優(yōu)化效果略優(yōu)于ABC算法,其余10個函數(shù)中,EABC算法和ABC算法的優(yōu)化效果相當;對于最差值和最優(yōu)值,EABC算法對f6、f11、f13、f15、f20、f21、f22、f23、f25、f2710 個函數(shù)的結果與ABC 算法相當,其余18個函數(shù)中,EABC算法求得的結果均優(yōu)于ABC算法;對于運行時間,EABC算法對f3、f6、f7、f8、f9、f11、f20、f21、f25、f2610 個函數(shù)的結果與ABC 算法相當,其余18個函數(shù)中,EABC算法的平均運行時間略小于ABC 算法,說明EABC 算法的時間復雜度與ABC相當。
此外,實驗中使用的基準測試函數(shù)優(yōu)化問題單峰、多峰、可分離性和不可分離性等不同性質(zhì)[23]。結合表2仿真實驗結果,對EABC算法處理不同類型數(shù)據(jù)集的能力進行分析:對于單峰函數(shù),只有一個局部極小值且為函數(shù)全局極小值。因此,很容易找到全局最優(yōu)值;對于多峰函數(shù),具有一個以上局部極小值,且要求優(yōu)化方法具有有效的全局和局部搜索能力。由于EABC 算法通過全局極值和鄰域極值個體的引導,具有很好的全局和局部搜索能力,能夠求得復雜多峰函數(shù)的全局最優(yōu)值;對于可分離函數(shù),可被重新表述為n個單變量函數(shù)的和。因此,能較快求得全局最優(yōu)值;對于不可分離函數(shù),函數(shù)的變量之間存在相互關系,當改變某一變量時其他變量將會受到影響[23]。因此,不可分離函數(shù)的最優(yōu)值求解過程較可分離函數(shù)困難得多。
表2 兩種算法的實驗結果Table 2 Experimental results of two optimization algorithms
3.3.2 維度擴展性比較
ABC算法作為一種基于群體智能的全局優(yōu)化算法,在優(yōu)化過程中,測試函數(shù)維度的增加會使算法復雜度增加,優(yōu)化性能下降。為了分析測試函數(shù)的維度對算法性能的影響,本文將測試函數(shù)的維度擴展到60、100維,其他參數(shù)不變,實驗結果見表3和表4。
從表3 中60 維的測試實驗結果分析得出:對于平均最優(yōu)值和標準差,EABC 算法對f10、f11、f12、f15、f20、f21、f24、f258 個函數(shù)的優(yōu)化效果與ABC 算法相當;其余20個函數(shù)中,EABC算法的優(yōu)化效果均好于ABC 算法;對于平均運行時間,EABC 算法對f1、f3、f8、f9、f10、f276 個函數(shù)的平均運行時間與ABC 算法相當,其余22個函數(shù)中,EABC算法的平均運行時間略低于ABC 算法。從表4 中100 維的測試實驗結果分析得出:對于平均最優(yōu)值和標準差,EABC 算法對f10、f11、f12、f19、f20、f25、f277個函數(shù)的優(yōu)化效果與ABC算法相當;其余21 個函數(shù)中,EABC 算法的優(yōu)化效果均好于ABC算法;對于平均運行時間,EABC算法對f1、f3、f7、f8、f9、f10、f14、f15、f21、f24、f25、f2812個函數(shù)的平均運行時間與ABC算法相當,其余16個函數(shù),EABC 算法的平均運行時間略低于ABC 算法。因此,在同一維度水平下,EABC 算法的優(yōu)化效果更好,隨著目標函數(shù)維度的增加,EABC 算法仍能保持較好的優(yōu)化性能。
表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.1 優(yōu)化性能比較
為考察EABC 算法的優(yōu)化性能,將其與ABC[5]、ABCVSS[23]、GABC[24]、ABCBest1[25]、MSSABC[26]和MABC[27]等較新的ABC改進算法進行比較。幾種算法中,種群大小N=30,維度D=30,最大迭代次數(shù)T=5 000,算法獨立運行次數(shù)runtime=30,最大限制搜索次數(shù)limit=600,實驗結果見表5和圖2,ABCVSS算法的實驗結果直接取自文獻[23],MABC算法的實驗結果直接取自文獻[27]。
由表5 可以看出,對于f1、f2、f3、f5、f8、f9、f13、f15、f16、f17、f21、f22、f24、f26、f2715 個函數(shù),EABC 算法的優(yōu)化效果更好;對于f7、f11、f12、f254個函數(shù),幾種算法的優(yōu)化效果一致,都達到了最優(yōu)值;其余9 個函數(shù)中,EABC 算法與其他幾種算法的優(yōu)化效果相當。由此說明EABC算法具有更高的優(yōu)化精度,能有效克服ABC 算法收斂速度慢和陷入局部最優(yōu)的缺點,具有更高的優(yōu)化性能。
圖2是選取表5中ABC、GABC、ABCBest1、MSSABC、EABC這五種算法對不同屬性的部分函數(shù)運行30 次后得到的收斂曲線圖。每幅圖中,縱坐標用函數(shù)平均最優(yōu)值的對數(shù)表示,橫坐標為迭代次數(shù)。
從圖2 中可以看出:在單峰可分離函數(shù)中,對于f1、f3、f8,EABC算法前期的收斂速度略低于MSSABC算法,但當?shù)螖?shù)達到3 700左右時,EABC算法優(yōu)于其他算法并達到理論最優(yōu)值;對于f9,幾種算法收斂趨勢一致,但EABC 算法收斂速度更快,優(yōu)化精度更高。在單峰不可分離函數(shù)中,對于f2、f5,當?shù)螖?shù)小于3 700 時,EABC 算法的收斂速度略低于MSSABC算法,當?shù)螖?shù)大于3 700時,EABC算法的收斂速度明顯加快,并且在迭代次數(shù)約4 500時開始收斂直到趨向全局最優(yōu)解。在多峰不可分離函數(shù)中,對于f16、f17,EABC 與MSSABC 算法收斂趨勢一致,EABC 算法前期的收斂速度略低于MSSABC 算法,當?shù)螖?shù)達到1 500 后,EABC 算法收斂速度快,優(yōu)化精度高;對于f26,相比其他5 種算法,EABC算法前期的收斂速度略低于MSSABC 和GABC 算法,但當?shù)螖?shù)達到3 500后,EABC算法的優(yōu)化精度高于其他算法。在多峰可分離函數(shù)中,對于f18,EABC與ABC算法收斂趨勢一致,且EABC算法收斂速度大于其他5種算法,優(yōu)化效果更好。
圖2 函數(shù)收斂曲線Fig.2 Convergence curve of functions
3.4.2 時間復雜度比較
在人工蜂群算法初始階段,時間復雜度一致,主要分析在雇傭蜂和跟隨蜂尋優(yōu)過程開始后的時間復雜度。假設T表示算法最大迭代次數(shù),S表示蜜蜂種群總數(shù),D表示算法的維數(shù)。
ABC算法的時間復雜度為:
MSSABC算法采用算術交叉方式,將當前個體、隨機選擇的個體和種群全局最優(yōu)個體進行組合,結合差向量的擾動,只是將搜索公式進行改進,因此時間復雜度仍為:
GABC 算法中將全局最優(yōu)解的信息引入到雇傭蜂和觀察蜂解的搜索方程中,不改變算法的時間復雜度,因此時間復雜度為:
ABCBest1 算法中每只蜜蜂只在前一次迭代的最優(yōu)解附近搜索,在產(chǎn)生初始種群和雇傭蜂時,采用混沌系統(tǒng),G為預設的最大混沌迭代次數(shù),時間復雜度為:
ABCVSS 算法使用五種搜索策略和計數(shù)器來更新解,每個更新策略都有一個常量計數(shù)器,在搜索過程中,這些計數(shù)器用于確定蜜蜂所選擇的策略,t為計數(shù)器最大選擇次數(shù),時間復雜度為:
MABC算法排除了概率選擇過程和偵察蜂搜索階段,在種群搜索過程中采用了混沌系統(tǒng)和基于反向的學習方法,M為預設最大混沌迭代次數(shù),時間復雜度為:
EABC算法在ABC算法的基礎上增加了全局極值和鄰域極值引導項,并引入小概率變異算子。其中,鄰域極值的求解只是一種比較算法,對算法的時間復雜度影響很小,而小概率變異算子的發(fā)生概率為0.02,對于時間復雜度的影響可以忽略不計,故其時間復雜度仍為:
綜上所述,相比其他智能優(yōu)化算法,本文提出的EABC算法并未增加時間復雜度,優(yōu)化性能較好。
本文針對ABC 算法開發(fā)能力差、易陷入局部最優(yōu)、收斂速度慢等問題,提出了一種極值個體引導的人工蜂群算法(EABC),所做的主要工作總結為:
(1)通過發(fā)揮極值個體的引導作用,改進雇傭蜂和跟隨蜂的搜索方程,全局極值個體有利于種群中優(yōu)良個體的保留和發(fā)展,使算法跳出局部極值,避免早熟收斂;鄰域極值個體有利于提高算法的收斂速度和精度。
(2)通過引入小概率變異算子,增加種群的多樣性,防止算法陷入局部極值。
(3)采用基于目標函數(shù)值的貪婪選擇,提高算法的優(yōu)化性能;通過仿真實驗驗證了該方法的有效性。
(4)以28 個測試函數(shù)的仿真實驗驗證EABC 算法的有效性,并通過EABC和ABC算法的擴維測試,表明隨著維度的增加,EABC算法的優(yōu)化性能仍優(yōu)于ABC算法。
(5)與其他改進算法進行比較,仿真實驗結果表明EABC算法具有較高的優(yōu)化性能。