丁知平
(清遠職業(yè)技術(shù)學院 信息技術(shù)與創(chuàng)意設(shè)計學院,清遠 511510)
引力搜索算法(Gravitational Search Algorithm,GSA)[1]是繼遺傳算法[2]、粒子群算法[3,4]、混合蛙跳算法[5]之后的新的群智能優(yōu)化算法. GSA算法源于對物理學中萬有引力定律進行模擬而提出,它為解決復雜優(yōu)化問題提供了新的思路和手段. 由于具有結(jié)構(gòu)簡單、易于實現(xiàn)、參數(shù)較少等優(yōu)點,GSA算法一經(jīng)提出便受到眾多學者的關(guān)注和研究,并取得廣泛應(yīng)用[6-8].
在處理部分復雜、多維優(yōu)化問題時,典型GSA算法容易陷入局部極值、收斂速度慢等不足. 文獻[9]提出將反向?qū)W習策略、邊界變異等策略引入算法,起到調(diào)節(jié)算法全局搜索和局部搜索能力的作用,獲得了較好的優(yōu)化能力. 文獻[10]利用免疫信息處理機制來改善引力搜索算法的局部優(yōu)化性能,明顯改善了GSA易陷入局部極值的問題. 文獻[11]提出一種基于權(quán)值的WGSA算法來提高標準GSA算法的性能,使得算法在進化初期搜索能力較強. 上述改進策略仍然受到初始種群的影響,并且,隨著優(yōu)化問題規(guī)模和復雜程度不斷擴大,這些改進策略均很難在提高算法收斂速度和避免早熟收斂兩方面取得平衡.
針對典型引力搜索算法尋優(yōu)能力不足的問題,本文提出了一種改進的引力搜索算法(GSA with Chaotic Opposition-based Learning and Artificial Bee Colony Operator,CA-GSA)以改善GSA算法的尋優(yōu)能力. 首先采用混沌反學習的初始化種群以加快算法的全局收斂速度; 然后,在GSA中引入人工蜂群搜索算子對種群進行引導搜索,從而使種群中的個體盡快跳出局部最優(yōu)點,平衡GSA算法的探索和開發(fā)能力,避免種群因個體陷入局部最優(yōu)而導致早熟收斂的不足. 最后,通過13個基準測試函數(shù)進行仿真測試,驗證了CAGSA算法的有效性和優(yōu)越性.
假設(shè)由N個質(zhì)點組成的種群,其中第i個質(zhì)點的位置為表示質(zhì)點i在d維空間的位置,s為優(yōu)化問題的維數(shù).
依據(jù)牛頓引力定理,在d時刻,第i個質(zhì)點收到第j個質(zhì)點的作用力F為
則作用在第i個質(zhì)點的合力為
式中,randj是[0,1]中的一個隨機數(shù).
基于牛頓第二定理,質(zhì)點i在d維的加速度為
在GSA算法的每一次迭代過程中,按式(4)更新質(zhì)點的速度按式(5)更新質(zhì)點的位置
GSA是以適應(yīng)度值為基礎(chǔ)的,依據(jù)適應(yīng)度函數(shù)fiti給出質(zhì)點的質(zhì)量.
GSA算法開始于初始解,然后朝著改善解的方向進行優(yōu)化,因此種群初始化方法是算法設(shè)計中一項至關(guān)重要的環(huán)節(jié),其優(yōu)劣程度會影響算法的收斂速度和解的精度. 在缺乏有關(guān)最優(yōu)解的先驗信息時,GSA通常采用隨機初始種群. 然而,如果初始解遠離最優(yōu)解,甚至最優(yōu)解在初始解的對立解的周圍,隨機初始化的方式將會制約算法的收斂性能. 反向?qū)W習策略 (Opposition-Based Learning,OBL)[12]是計算智能領(lǐng)域出現(xiàn)的一種新技術(shù)并取得廣泛應(yīng)用,其主要思想是:對一個可行解,同時計算并評估其反向解,從中選擇較優(yōu)的解作為下一代個體. 因此,采用OBL方法進行種群初始化可以改善初始種群的質(zhì)量. 除此之外,種群初始化盡可能均勻分布在可能的解空間,可以有效地提高尋找最優(yōu)解的效率. 利用混沌算法的遍歷性產(chǎn)生分布均勻的初始種群可以得到質(zhì)量較好的初始解群[13],進一步提高提高GSA算法尋優(yōu)的計算效率.
式(6)所示為1維混沌自映射的表達式:
式(6)中,混沌變量xn在其相空間內(nèi)總會有線性或非線性折疊現(xiàn)象以產(chǎn)生混沌,其中,混沌擾動的幅度為[-1,1],且迭代初值x0≠0,本文方法的初值設(shè)置x0=0.255,經(jīng)過多次混沌迭代,系統(tǒng)輸出將遍歷整個解空間.
混沌反學習初始化種群算法描述如下所示.
結(jié)合二者優(yōu)勢,提出混沌反學習算法來初始化GSA的種群. 基于混沌反向?qū)W習初始化方法,按照混沌運動自身規(guī)律和特性進行,無疑會比隨機種群更優(yōu)越,因而優(yōu)化到最優(yōu)解的可能性也越大. 下面介紹算法具體步驟.
人工蜂群算法(Artificial Bee Colony Algorithm,ABC)是源于蜜蜂采蜜而提出的智能算法[14,15],ABC算法具有較好的優(yōu)化性能,這主要得力于該算法具有很強的探索能力. 文獻[16]在原始ABC算法的基礎(chǔ)上給出了一個新的搜索策略,即
其中,wij是 慣性權(quán)值,其大小反映了對候選解xij的依賴程度;xg為最優(yōu)位置; φij和 φij是[0,1]之間的隨機數(shù);Φ1和 Φ2是控制最大步長的加速因子;xkj是隨機選擇的個體.
可以看出,新的搜索算子在隨機參數(shù)和最優(yōu)位置xg的引導下,在保證探索能力同時能夠提高開發(fā)能力.當處理復雜優(yōu)化問題時,GSA算法由于探索能力較弱而致使算法易陷入局部最優(yōu)點,進一步引導其余個體搜索軌跡向局部最優(yōu)點靠近而出現(xiàn)早熟現(xiàn)象. 因此,如何提高GSA的探索能力以幫助算法跳出局部最優(yōu)是改善算法優(yōu)化性能的關(guān)鍵. 本文結(jié)合ABC算法強的探索能力,采用最優(yōu)候選解xg幫助GSA種群中陷入局部最優(yōu)的質(zhì)點快速跳出局部最優(yōu),避免算法早熟.
針對典型引力搜索算法尋優(yōu)能力不足的問題,提出一種改進的GSA(CA-GSA)算法. CA-GSA是在標準GSA算法基礎(chǔ)上,引進了混沌反學習和人工蜂群搜索算子,使CA-GSA在繼承典型GSA算法出色的搜索能力下兼具上述兩種策略的優(yōu)勢,以達到改善GSA算法優(yōu)化性能的目的. CA-GSA算法的程序執(zhí)行流程如圖1所示. 具體步驟如下:
1) 初始化參數(shù):種群規(guī)模N=50、混沌迭代步數(shù)K=300、GSA算法的迭代次數(shù)NS=1000;
2) 初始化種群:在待優(yōu)化問題的空間中,采用混沌反學習算法產(chǎn)生N個質(zhì)點組成的種群;
3) 計算適應(yīng)度值,更新種群中最優(yōu)質(zhì)點xg;
4) 更新數(shù)據(jù)G(t),best(t),worst(t)和Mi;
7) 按式(5)更新質(zhì)點的位置;
8) 重復步驟3)到步驟8),直到滿足終止條件;9) 輸出最優(yōu)解及最優(yōu)值,運算結(jié)束.
圖1 CA-GSA程序流程圖
為了驗證CA-GSA的效果,對表1中13個標準基準函數(shù)進行仿真實驗. 表1給出了基準函數(shù)的搜索空間和最優(yōu)解,其中f1~f7為單模態(tài)函數(shù),主要用來考察算法的執(zhí)行能力并測試算法的尋優(yōu)精度;f8~f13是優(yōu)化領(lǐng)域中公認較難優(yōu)化的多模態(tài)函數(shù),具有大量的局部最優(yōu)點,它們主要用來檢驗算法是否具備避免早熟并搜索到全局最優(yōu)解的能力.
為了說明CA-GSA算法的有效,將CA-GSA與標準GSA、基于人工蜂群搜索算子的GSA(記為AGSA)進行對比研究. 為了比較的公平性,3種算法的迭代次數(shù)為1000,種群規(guī)模為50. 為有效減少隨機干擾的影響,均在相同條件下獨立運行30次. 表2記錄了3種算法測試基準函數(shù)分別在30維和50維情況下的平均收斂次數(shù)(C.I)、最優(yōu)解(Best)、平均最優(yōu)適應(yīng)度值(Mean)和標準差(SD)的統(tǒng)計數(shù)據(jù). C.I反映了算法的收斂速度,Best和Mean顯示了在給定函數(shù)評價次數(shù)下算法所能達到的精度,SD反映了算法的穩(wěn)定性.
表1 測試函數(shù)
從表2可以看出,無論是解的精度還是收斂速度,A-GSA和CA-GSA算法比標準GSA算法均有很大提高. 仿真結(jié)果可以看出,CA-GSA算法幾乎在所有基準函數(shù)上取得了最好的優(yōu)化結(jié)果. 所有函數(shù)的最優(yōu)值、平均值都等于或非常接近于全局最優(yōu)值,而且標準差都相當小. 具體地,對于f1、f2、f3、f4、f9、f11,均搜索到了全局最優(yōu)值. 特別地,當n=50,CA-GSA的優(yōu)化精度和標準差基本上接近n=30的精度和標準差. 進一步表明了CA-GSA的優(yōu)化效果、穩(wěn)定性和魯棒性并沒有隨著問題復雜程度的增加而減弱. GSA和A-GSA隨著維數(shù)的增加,絕大部分的優(yōu)化效果都呈現(xiàn)下降趨勢. 尤其是GSA算法,從表2可以看出,雖然標準GSA算法對大部分基準函數(shù)能夠優(yōu)化到較好的結(jié)果,但隨著問題復雜程度的增加,其穩(wěn)定性和優(yōu)化精度下降明顯.
相比GSA算法,A-GSA除了在f6和f12函數(shù)上性能略遜于標準GSA算法,在其他測試函數(shù)上,AGSA優(yōu)化精度等于或非常接近全局最優(yōu)值且優(yōu)于GSA算法. 尤其是f8,GSA無論在30維還是50維,其解均陷入局部最優(yōu),而A-GSA算法則能跳出局部最優(yōu),獲得較為滿意的解. 究其原因,是因為A-GSA算法引入了人工蜂群搜索算子,增強了算法的探索能力,進而增加了算法獲得全局最優(yōu)解的能力.
比較A-GSA和CA-GSA的性能,A-GSA和CAGSA的區(qū)別在于A-GSA算法中沒有采取混沌反學習進行種群初始化. 對于f1、f3、f9、f10、f11,二者雖然都能獲得相同的優(yōu)化結(jié)果,但CA-GSA的收斂速度較AGSA的收斂速度更快; 對于其余函數(shù),CA-GSA算法在全局收斂速度和優(yōu)化精度上均優(yōu)于A-GSA. 上述表明,混沌反向?qū)W習種群初始化方法能夠改善GSA算法的尋優(yōu)能力.
為更直觀地反映算法的尋優(yōu)效果,將CA-GSA、A-GSA和標準GSA算法進行比較. 3種算法對測試函數(shù)f1、f4、f5、f9、f11、f136個函數(shù)在 Dim=30情況下的尋優(yōu)曲線如圖2所示. 圖2可以看出,針對單峰測試函數(shù)f1、f4、f5,CA-GSA具有較快的收斂速度和更優(yōu)秀的解的精度; A-GSA算法由于沒有采用混沌反學習測量,影響了收斂速度,由于采用了蜂群搜索算子,其優(yōu)化性能明顯強于標準GSA算法. 針對多峰測試函數(shù),由于采用了混沌反學習的初始化種群策略和蜂群搜索算子,CA-GSA算法的優(yōu)化性能明顯優(yōu)于A-GSA和GSA算法. 綜上所述,CA-GSA算法在優(yōu)化性能上得到了明顯改善.
表2 3種優(yōu)化算法性能比較
針對GSA在復雜優(yōu)化問題中尋優(yōu)能力的不足的問題,提出了一種融合混沌反學習和人工蜂群搜索算子的引力搜索算法(CA-GSA). CA-GSA的初始種群在保持隨機性的前提下,提高了種群的遍歷性,進而改善了收斂速度; 同時,人工蜂群搜索算子的引入,平衡了GSA算法探索和開采能力,進一步改善了GSA的優(yōu)化能力. 通過對13基準測試函數(shù)進行仿真測試,驗證了CA-GSA算法的有效性和優(yōu)越性.
圖2 3種算法對函數(shù)f1、f4、f5、f9、f11、f13(n=30)的優(yōu)化性能比較
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飛行的粒子群優(yōu)化算法. 計算機應(yīng)用,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 張維平,任雪飛,李國強,等. 改進的萬有引力搜索算法在函數(shù)優(yōu)化中的應(yīng)用. 計算機應(yīng)用,2013,33(5):1317-1320.
10 楊晶,黎放,狄鵬. 免疫萬有引力搜索算法的研究與仿真.兵工學報,2012,33(12):1533-1538.
11 徐遙,王士同. 引力搜索算法的改進. 計算機工程與應(yīng)用,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 樊友洪,鄧韌,李生林,等. 基于混沌遺傳算子的人工魚群算法. 計算機系統(tǒng)應(yīng)用,2017,26(3):214-218. [doi:10.15888/j.csa.005664]
14 馬衛(wèi),孫正興. 基于精英蜂群搜索策略的人工蜂群算法. 計算 機 應(yīng) 用,2014,34(8):2299-2305. [doi:10.11772/j.issn.1001-9081.2014.08.2299]
15 王東云,徐艷平,瞿博陽. 基于改進蜂群算法的機器人路徑規(guī)劃. 計算機系統(tǒng)應(yīng)用,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]