融合混沌反學習與蜂群搜索算子的引力搜索算法①

丁知平

(清遠職業技術學院 信息技術與創意設計學院,清遠 511510)

引言

引力搜索算法(Gravitational Search Algorithm,GSA)[1]是繼遺傳算法[2]、粒子群算法[3,4]、混合蛙跳算法[5]之后的新的群智能優化算法. GSA算法源于對物理學中萬有引力定律進行模擬而提出,它為解決復雜優化問題提供了新的思路和手段. 由于具有結構簡單、易于實現、參數較少等優點,GSA算法一經提出便受到眾多學者的關注和研究,并取得廣泛應用[6-8].

在處理部分復雜、多維優化問題時,典型GSA算法容易陷入局部極值、收斂速度慢等不足. 文獻[9]提出將反向學習策略、邊界變異等策略引入算法,起到調節算法全局搜索和局部搜索能力的作用,獲得了較好的優化能力. 文獻[10]利用免疫信息處理機制來改善引力搜索算法的局部優化性能,明顯改善了GSA易陷入局部極值的問題. 文獻[11]提出一種基于權值的WGSA算法來提高標準GSA算法的性能,使得算法在進化初期搜索能力較強. 上述改進策略仍然受到初始種群的影響,并且,隨著優化問題規模和復雜程度不斷擴大,這些改進策略均很難在提高算法收斂速度和避免早熟收斂兩方面取得平衡.

針對典型引力搜索算法尋優能力不足的問題,本文提出了一種改進的引力搜索算法(GSA with Chaotic Opposition-based Learning and Artificial Bee Colony Operator,CA-GSA)以改善GSA算法的尋優能力. 首先采用混沌反學習的初始化種群以加快算法的全局收斂速度; 然后,在GSA中引入人工蜂群搜索算子對種群進行引導搜索,從而使種群中的個體盡快跳出局部最優點,平衡GSA算法的探索和開發能力,避免種群因個體陷入局部最優而導致早熟收斂的不足. 最后,通過13個基準測試函數進行仿真測試,驗證了CAGSA算法的有效性和優越性.

1 引力算法

假設由N個質點組成的種群,其中第i個質點的位置為表示質點i在d維空間的位置,s為優化問題的維數.

依據牛頓引力定理,在d時刻,第i個質點收到第j個質點的作用力F為

則作用在第i個質點的合力為

式中,randj是[0,1]中的一個隨機數.

基于牛頓第二定理,質點i在d維的加速度為

在GSA算法的每一次迭代過程中,按式(4)更新質點的速度按式(5)更新質點的位置

GSA是以適應度值為基礎的,依據適應度函數fiti給出質點的質量.

2 改進的引力算法

2.1 混沌反學習種群初始化方法

GSA算法開始于初始解,然后朝著改善解的方向進行優化,因此種群初始化方法是算法設計中一項至關重要的環節,其優劣程度會影響算法的收斂速度和解的精度. 在缺乏有關最優解的先驗信息時,GSA通常采用隨機初始種群. 然而,如果初始解遠離最優解,甚至最優解在初始解的對立解的周圍,隨機初始化的方式將會制約算法的收斂性能. 反向學習策略 (Opposition-Based Learning,OBL)[12]是計算智能領域出現的一種新技術并取得廣泛應用,其主要思想是：對一個可行解,同時計算并評估其反向解,從中選擇較優的解作為下一代個體. 因此,采用OBL方法進行種群初始化可以改善初始種群的質量. 除此之外,種群初始化盡可能均勻分布在可能的解空間,可以有效地提高尋找最優解的效率. 利用混沌算法的遍歷性產生分布均勻的初始種群可以得到質量較好的初始解群[13],進一步提高提高GSA算法尋優的計算效率.

式(6)所示為1維混沌自映射的表達式：

式(6)中,混沌變量xn在其相空間內總會有線性或非線性折疊現象以產生混沌,其中,混沌擾動的幅度為[-1,1],且迭代初值x0≠0,本文方法的初值設置x0=0.255,經過多次混沌迭代,系統輸出將遍歷整個解空間.

混沌反學習初始化種群算法描述如下所示.

結合二者優勢,提出混沌反學習算法來初始化GSA的種群. 基于混沌反向學習初始化方法,按照混沌運動自身規律和特性進行,無疑會比隨機種群更優越,因而優化到最優解的可能性也越大. 下面介紹算法具體步驟.

2.2 人工蜂群搜索策略

人工蜂群算法(Artificial Bee Colony Algorithm,ABC)是源于蜜蜂采蜜而提出的智能算法[14,15],ABC算法具有較好的優化性能,這主要得力于該算法具有很強的探索能力. 文獻[16]在原始ABC算法的基礎上給出了一個新的搜索策略,即

其中,wij是 慣性權值,其大小反映了對候選解xij的依賴程度;xg為最優位置; φij和 φij是[0,1]之間的隨機數;Φ1和 Φ2是控制最大步長的加速因子;xkj是隨機選擇的個體.

可以看出,新的搜索算子在隨機參數和最優位置xg的引導下,在保證探索能力同時能夠提高開發能力.當處理復雜優化問題時,GSA算法由于探索能力較弱而致使算法易陷入局部最優點,進一步引導其余個體搜索軌跡向局部最優點靠近而出現早熟現象. 因此,如何提高GSA的探索能力以幫助算法跳出局部最優是改善算法優化性能的關鍵. 本文結合ABC算法強的探索能力,采用最優候選解xg幫助GSA種群中陷入局部最優的質點快速跳出局部最優,避免算法早熟.

2.3 改進的引力搜索算法

針對典型引力搜索算法尋優能力不足的問題,提出一種改進的GSA(CA-GSA)算法. CA-GSA是在標準GSA算法基礎上,引進了混沌反學習和人工蜂群搜索算子,使CA-GSA在繼承典型GSA算法出色的搜索能力下兼具上述兩種策略的優勢,以達到改善GSA算法優化性能的目的. CA-GSA算法的程序執行流程如圖1所示. 具體步驟如下：

1) 初始化參數：種群規模N=50、混沌迭代步數K=300、GSA算法的迭代次數NS=1000;

2) 初始化種群：在待優化問題的空間中,采用混沌反學習算法產生N個質點組成的種群;

3) 計算適應度值,更新種群中最優質點xg;

4) 更新數據G(t),best(t),worst(t)和Mi;

7) 按式(5)更新質點的位置;

8) 重復步驟3)到步驟8),直到滿足終止條件;9) 輸出最優解及最優值,運算結束.

圖1 CA-GSA程序流程圖

3 仿真實驗

為了驗證CA-GSA的效果,對表1中13個標準基準函數進行仿真實驗. 表1給出了基準函數的搜索空間和最優解,其中f1～f7為單模態函數,主要用來考察算法的執行能力并測試算法的尋優精度;f8～f13是優化領域中公認較難優化的多模態函數,具有大量的局部最優點,它們主要用來檢驗算法是否具備避免早熟并搜索到全局最優解的能力.

為了說明CA-GSA算法的有效,將CA-GSA與標準GSA、基于人工蜂群搜索算子的GSA(記為AGSA)進行對比研究. 為了比較的公平性,3種算法的迭代次數為1000,種群規模為50. 為有效減少隨機干擾的影響,均在相同條件下獨立運行30次. 表2記錄了3種算法測試基準函數分別在30維和50維情況下的平均收斂次數(C.I)、最優解(Best)、平均最優適應度值(Mean)和標準差(SD)的統計數據. C.I反映了算法的收斂速度,Best和Mean顯示了在給定函數評價次數下算法所能達到的精度,SD反映了算法的穩定性.

表1 測試函數

從表2可以看出,無論是解的精度還是收斂速度,A-GSA和CA-GSA算法比標準GSA算法均有很大提高. 仿真結果可以看出,CA-GSA算法幾乎在所有基準函數上取得了最好的優化結果. 所有函數的最優值、平均值都等于或非常接近于全局最優值,而且標準差都相當小. 具體地,對于f1、f2、f3、f4、f9、f11,均搜索到了全局最優值. 特別地,當n=50,CA-GSA的優化精度和標準差基本上接近n=30的精度和標準差. 進一步表明了CA-GSA的優化效果、穩定性和魯棒性并沒有隨著問題復雜程度的增加而減弱. GSA和A-GSA隨著維數的增加,絕大部分的優化效果都呈現下降趨勢. 尤其是GSA算法,從表2可以看出,雖然標準GSA算法對大部分基準函數能夠優化到較好的結果,但隨著問題復雜程度的增加,其穩定性和優化精度下降明顯.

相比GSA算法,A-GSA除了在f6和f12函數上性能略遜于標準GSA算法,在其他測試函數上,AGSA優化精度等于或非常接近全局最優值且優于GSA算法. 尤其是f8,GSA無論在30維還是50維,其解均陷入局部最優,而A-GSA算法則能跳出局部最優,獲得較為滿意的解. 究其原因,是因為A-GSA算法引入了人工蜂群搜索算子,增強了算法的探索能力,進而增加了算法獲得全局最優解的能力.

比較A-GSA和CA-GSA的性能,A-GSA和CAGSA的區別在于A-GSA算法中沒有采取混沌反學習進行種群初始化. 對于f1、f3、f9、f10、f11,二者雖然都能獲得相同的優化結果,但CA-GSA的收斂速度較AGSA的收斂速度更快; 對于其余函數,CA-GSA算法在全局收斂速度和優化精度上均優于A-GSA. 上述表明,混沌反向學習種群初始化方法能夠改善GSA算法的尋優能力.

為更直觀地反映算法的尋優效果,將CA-GSA、A-GSA和標準GSA算法進行比較. 3種算法對測試函數f1、f4、f5、f9、f11、f136個函數在 Dim=30情況下的尋優曲線如圖2所示. 圖2可以看出,針對單峰測試函數f1、f4、f5,CA-GSA具有較快的收斂速度和更優秀的解的精度; A-GSA算法由于沒有采用混沌反學習測量,影響了收斂速度,由于采用了蜂群搜索算子,其優化性能明顯強于標準GSA算法. 針對多峰測試函數,由于采用了混沌反學習的初始化種群策略和蜂群搜索算子,CA-GSA算法的優化性能明顯優于A-GSA和GSA算法. 綜上所述,CA-GSA算法在優化性能上得到了明顯改善.

表2 3種優化算法性能比較

4 結論

針對GSA在復雜優化問題中尋優能力的不足的問題,提出了一種融合混沌反學習和人工蜂群搜索算子的引力搜索算法(CA-GSA). CA-GSA的初始種群在保持隨機性的前提下,提高了種群的遍歷性,進而改善了收斂速度; 同時,人工蜂群搜索算子的引入,平衡了GSA算法探索和開采能力,進一步改善了GSA的優化能力. 通過對13基準測試函數進行仿真測試,驗證了CA-GSA算法的有效性和優越性.

圖2 3種算法對函數f1、f4、f5、f9、f11、f13(n=30)的優化性能比較

1 Rashedi E,Nezamabadi-pour H,Saryazdi S. GSA：A gravitational search algorithm. Information Sciences,2009,179(13)：2232-2248. [doi：10.1016/j.ins.2009.03.004]

2 Mahmoodabadi MJ,Nemati AR. A novel adaptive genetic algorithm for global optimization of mathematical test functions and real-world problems. Engineering Science and Technology,an International Journal,2016,19(4)：2002-2021. [doi：10.1016/j.jestch.2016.10.012]

3 Garg H. A hybrid PSO-GA algorithm for constrained optimization problems. Applied Mathematics and Computation,2016,274：292-305. [doi：10.1016/j.amc.2015.11.001]

4 付強,葛洪偉,蘇樹智. 引入螢火蟲行為和Levy飛行的粒子群優化算法. 計算機應用,2016,36(12)：3298-3302. [doi：10.11772/j.issn.1001-9081.2016.12.3298]

5 Liu C,Niu PF,Li GQ,et al. Enhanced shuffled frog-leaping algorithm for solving numerical function optimization problems. Journal of Intelligent Manufacturing,2015. [doi：10.1007/s10845-015-1164-z]

6 Xiao JH,Niu YY,Chen P,et al. An improved gravitational search algorithm for green partner selection in virtual enterprises. Neurocomputing,2016,217：103-109. [doi：10.1016/j.neucom.2016.03.092]

7 Zhang AZ,Sun GY,Ren JC,et al. A dynamic neighborhood learning-based gravitational search algorithm. IEEE Transactions on Cybernetics,2016. [doi：10.1109/TCYB.2016.2641986]

8 Niu PF,Liu C,Li PF,et al. Optimized support vector regression model by improved gravitational search algorithm for flatness pattern recognition. Neural Computing and Applications,2015,26(5)：1167-1177. [doi：10.1007/s00521-014-1798-3]

9 張維平,任雪飛,李國強,等. 改進的萬有引力搜索算法在函數優化中的應用. 計算機應用,2013,33(5)：1317-1320.

10 楊晶,黎放,狄鵬. 免疫萬有引力搜索算法的研究與仿真.兵工學報,2012,33(12)：1533-1538.

11 徐遙,王士同. 引力搜索算法的改進. 計算機工程與應用,2011,47(35)：188-192. [doi：10.3778/j.issn.1002-8331.2011.35.053]

12 Gao WF,Liu SY,Huang LL. Particle swarm optimization with chaotic opposition-based population initialization and stochastic search technique. Communications in Nonlinear Science and Numerical Simulation,2012,17(11)：4316-4327. [doi：10.1016/j.cnsns.2012.03.015]

13 樊友洪,鄧韌,李生林,等. 基于混沌遺傳算子的人工魚群算法. 計算機系統應用,2017,26(3)：214-218. [doi：10.15888/j.csa.005664]

14 馬衛,孫正興. 基于精英蜂群搜索策略的人工蜂群算法. 計算 機 應 用,2014,34(8)：2299-2305. [doi：10.11772/j.issn.1001-9081.2014.08.2299]

15 王東云,徐艷平,瞿博陽. 基于改進蜂群算法的機器人路徑規劃. 計算機系統應用,2017,26(2)：145-150. [doi：10.15888/j.csa.005601]

16 Li GQ,Niu PF,Xiao XJ. Development and investigation of efficient artificial bee colony algorithm for numerical function optimization. Applied Soft Computing,2012,12(1)：320-332. [doi：10.1016/j.asoc.2011.08.040]