高雷阜,佟盼

(遼寧工程技術(shù)大學(xué)理學(xué)院,遼寧阜新123000)

遺傳-人工蜂群融合算法及其Markov收斂性分析

高雷阜,佟盼

(遼寧工程技術(shù)大學(xué)理學(xué)院,遼寧阜新123000)

本文研究了遺傳算法易發(fā)生“早熟”以及人工蜂群算法在搜索初期尋優(yōu)速度慢的問題.基于將遺傳算法與人工蜂群算法融合以實(shí)現(xiàn)二者互補(bǔ)的思想,提出遺傳-人工蜂群融合算法（G-ABCA）,利用馬爾可夫理論對其收斂性進(jìn)行了理論分析,證明其適應(yīng)度函數(shù)值序列（即優(yōu)化解滿意值序列）是單調(diào)且收斂的,并利用四個(gè)經(jīng)典的多峰測試函數(shù)對遺傳-人工蜂群融合算法、改進(jìn)的遺傳算法以及人工蜂群算法進(jìn)行了對比實(shí)驗(yàn)分析,結(jié)果表明:遺傳-人工蜂群融合算法不僅收斂,而且其尋優(yōu)性能顯著優(yōu)于其它兩種算法.

遺傳算法;人工蜂群算法;融合;馬爾可夫過程;收斂性

1 引言

遺傳算法(Genetic Algorithm,GA)是一種隨機(jī)搜索算法,具有全局搜索能力和較強(qiáng)的魯棒性,但是,系統(tǒng)中的反饋信息得不到充分利用,容易陷入“早熟”[1-2],而且算法中的遺傳操作比較耗時(shí).

人工蜂群算法(Artificial Bee Colony Algorithm,ABCA)是Karaboga[3]在2005年提出的一種基于蜜蜂采蜜的群體智能優(yōu)化算法,在搜索過程中僅以適應(yīng)度函數(shù)作為進(jìn)化依據(jù)[4],反饋信息得到充分利用,在每次的迭代過程中都進(jìn)行全局和局部搜索,極大地提高了找到最優(yōu)解的概率,但是,算法在初期尋優(yōu)速度較慢.

遺傳-人工蜂群融合算法(Genetic-Artificial Bee Colony Algorithm,G-ABCA)正是基于遺傳算法與人工蜂群算法的優(yōu)缺點(diǎn),在初期采用改進(jìn)的遺傳算法得到“蜜源”分布,在后期采用人工蜂群算法尋找最優(yōu)解,實(shí)現(xiàn)二者的互補(bǔ),以提升算法的有效性.

2 遺傳-人工蜂群融合算法

2.1 遺傳-人工蜂群融合算法的原理

遺傳-人工蜂群融合算法的基本原理是:與袁艷花[5]提出的融合思想不同,不是將遺傳算法的交叉和變異算子融合到人工蜂群算法的搜索過程中,而是首先采用改進(jìn)的遺傳算法過程得到“蜜源”分布,然后根據(jù)得到的“蜜源”分布,采用人工蜂群算法進(jìn)行最優(yōu)解搜索.通過這種融合,避免遺傳算法發(fā)生“早熟”,并加速人工蜂群算法的尋優(yōu)速度.

2.2遺傳-人工蜂群融合算法的過程

2.2.1 G-ABCA中遺傳算法的設(shè)置

G-ABCA中的遺傳算法采用表達(dá)精確的實(shí)數(shù)編碼,以克服二進(jìn)制編碼的換算占用計(jì)算時(shí)間的問題[6];計(jì)算編碼后的染色體適應(yīng)度值,通過適應(yīng)度比例法[7]、自適應(yīng)的交叉和變異概率公式[8]進(jìn)行遺傳操作;同時(shí)采用最優(yōu)保存策略,以防止優(yōu)良的個(gè)體在遺傳操作中過早的丟失[9].記遺傳算法過程的最大迭代次數(shù)為maxgen,初始的交叉概率和變異概率為pc和pm,則其自適應(yīng)的交叉和變異概率公式為

其中pcross和pmutation表示新一代的交叉和變異概率,Pcross和Pmutation表示當(dāng)代的交叉和變異概率.顯然,pc、pm和maxgen是固定的常數(shù),由交叉和變異概率公式可知,新的個(gè)體是否進(jìn)行交叉或變異只與當(dāng)前的交叉或變異概率有關(guān),而與之前的交叉或變異概率以及時(shí)刻（即迭代次數(shù)）無關(guān),因此具有Markov性.

2.2.2 G-ABCA中人工蜂群算法的設(shè)置

G-ABCA中的人工蜂群算法采用標(biāo)準(zhǔn)模型[10],分別記Ns、Ne為蜜蜂總數(shù)、采蜜蜂種群規(guī)模,令跟隨蜂種群規(guī)模與采蜜蜂相同,記D為個(gè)體向量維數(shù),S為個(gè)體搜索空間,X(m)為第m代采蜜蜂種群,初始采蜜蜂種群X(0)為改進(jìn)的遺傳算法得到的結(jié)果.首先,由采蜜蜂尋找新蜜源,搜索公式為

其中,j∈{1,2,···,D},k∈{1,2,···,Ne}且為區(qū)間[-1,1]上的隨機(jī)數(shù),V∈S.顯然,該搜索只與當(dāng)前的蜜源位置有關(guān),而與之前的蜜源及時(shí)刻m無關(guān).

然后,采用貪婪選擇算子在新蜜源和原蜜源之間選出適應(yīng)度更優(yōu)的(這里以適應(yīng)度越小越優(yōu)為例)并保留,記作Tgs:S2→S,其概率分布與時(shí)刻無關(guān),為

跟隨蜂依照采蜜蜂種群的適應(yīng)度值選擇一個(gè)采蜜蜂,并在其鄰域內(nèi)按式(2.3)進(jìn)行新蜜源搜索并執(zhí)行貪婪選擇算子.當(dāng)某只采蜜蜂在蜜源周圍搜索的次數(shù)達(dá)到一定閾值仍未找到最優(yōu)位置時(shí),重新隨機(jī)初始化該采蜜蜂的位置,初始化公式為

該步驟通過增加種群的多樣性,防止了算法陷入局部最優(yōu),同時(shí)保證了搜索始終在鄰域內(nèi)進(jìn)行.

3 融合算法的Markov 收斂性分析

設(shè)SN={X=(X1,X2,···,XN),Xi∈S(i≤N)}為種群空間,S2={(X1,X2),Xi∈S(i=1,2)}為母體空間,S為個(gè)體空間,個(gè)體Xi的長度l稱為鏈長,N為種群規(guī)模.記n為遺傳算法過程的迭代次數(shù),m為人工蜂群算法的迭代次數(shù),P為SN上的概率分布.融合算法可以看作是改進(jìn)遺傳算法的擴(kuò)展,其中共包括四個(gè)過程:選擇算子Ts、交叉算子Tc、變異算子Tm、蜜源算子Tb,其基本定義如下:

定義3.1[11]適應(yīng)度函數(shù)為f:S→R,即為個(gè)體空間到實(shí)數(shù)空間的映射;全局最優(yōu)解為滿意解B=

定義3.2[11]選擇算子Ts:SN→S,即在種群中隨機(jī)選擇一個(gè)個(gè)體的映射,母體選擇算子的概率為

定義3.3[11]交叉算子Tc:S2→S,即母體空間到個(gè)體空間的映射,記k為可生成Y的基因位置的個(gè)數(shù),單點(diǎn)交叉算子的概率為

定義3.4[11]變異算子Tm:S→S,即個(gè)體空間到個(gè)體空間的隨機(jī)映射,變異算子的概率為

其中,d(X,Y)為X與Y的Hamming距離.

定義3.5蜜源算子Tb:SN→S,即在蜜源位置序列中選擇最優(yōu)個(gè)體的映射,蜜源算子的概率為

引理3.1改進(jìn)的遺傳算法種群序列{X(n);n≥0}是有限齊次Markov鏈,且以概率1收斂到滿意種群集G?的子集即

證因?yàn)椴捎米顑?yōu)保存策略的遺傳算法的種群序列是有限齊次Markov鏈,并且以概率1收斂到滿意種群集的子集[12-14],改進(jìn)的遺傳算法采用了最優(yōu)保存策略,并且其改進(jìn)的交叉和變異概率公式對算法的收斂性沒有影響,能保持Markov性,因此,改進(jìn)的遺傳算法種群序列仍是有限齊次Markov鏈,且以概率1收斂到滿意種群集G?的子集.

引理3.2引入適應(yīng)度函數(shù)的人工蜂群系統(tǒng)序列{X(m),f?(m);m=1,2,···}是有限齊次Markov鏈.

證因?yàn)槿斯し淙核惴ㄐ蛄衶X(m);m=1,2,···}是有限齊次Markov鏈且以概率1收斂[15],適應(yīng)度函數(shù)序列具有Markov性,因此,類比引入適應(yīng)度函數(shù)的螞蟻系統(tǒng)序列[16]仍是有限齊次Markov鏈可知,引入適應(yīng)度函數(shù)的人工蜂群系統(tǒng)序列是有限齊次Markov鏈.

定理3.1G-ABCA算法的種群序列{X(n);n≥0}是有限齊次Markov鏈.

證由引理3.1知,改進(jìn)的遺傳算法X(n+1)只與X(n)有關(guān),與迭代次數(shù)n無關(guān).由引理3.2知,人工蜂群系統(tǒng){X(m+1),f?(m+1)}只與{X(m),f?(m)}有關(guān),而與迭代次數(shù)m無關(guān).同時(shí),由人工蜂群算法的設(shè)置可知,算法每一次只更新最優(yōu)蜜源位置,具有改進(jìn)的遺傳算法的所有特征.因此取

其中,i0=表示使f(Xj(n))取最小值的個(gè)體為Xj(n),種群轉(zhuǎn)移概率矩陣:

上述表明X(n+1)只與X(n)有關(guān),而與迭代次數(shù)n無關(guān).因此,G-ABCA算法的種群序列{X(n);n≥0}是有限齊次Markov鏈.

定理3.2G-ABCA算法Markov鏈的適應(yīng)度函數(shù)值序列是單調(diào)不增的,即?n≥0,f(X(n+1))≤f(X(n)).

證由于G-ABCA中采用的是改進(jìn)的遺傳算法,,所以

又由于人工蜂群算法以改進(jìn)的遺傳算法結(jié)果為初始蜜源分布,具有優(yōu)值繼承性,因此?n≥0, f(X(n+1))≤f(X(n)),即G-ABCA算法Markov鏈的適應(yīng)度函數(shù)值序列是單調(diào)不增的.

定理3.3G-ABCA算法的Markov序列以概率1收斂到滿意解集B的子集(Y1,Y2,···,YN);YN∈B},即

證設(shè)X′是f(X)的唯一最小值解,由引理3.1、定理3.1以及人工蜂群算法也以概率1收斂可知P{X,Y}具有如下性質(zhì):

故

推論3.1G-ABCA算法的種群序列{X(n);n≥0}如果對于任意滿意解集收斂,則必收斂到全局最優(yōu)解集.

證因?yàn)閷τ谌我獾摩牛?,有滿意解集

其中X?表示最優(yōu)解,即X?∈M,也即全局最優(yōu)解集M是所有滿意解集的交集,M為最小滿意解集.所以,若{X(n);n≥0}對于任意滿意解集收斂,則必收斂到全局最優(yōu)解集.

4 數(shù)值實(shí)驗(yàn)分析

因?yàn)槎喾鍞?shù)值函數(shù)求極值問題是常見的優(yōu)化問題,更是測試連續(xù)優(yōu)化算法的試金石,所以這里借助Matlab編程,利用四個(gè)經(jīng)典的多峰測試函數(shù)[17]:Sphere函數(shù)、Griewank函數(shù)、Rosenbrock函數(shù)、Rastrigin函數(shù)來測試G-ABCA算法的尋優(yōu)性能,并與改進(jìn)的GA和ABCA進(jìn)行尋優(yōu)性能對比.這四個(gè)經(jīng)典的測試函數(shù)的全局極小值均為0,其搜索空間均為(-100,100)d,并均將維數(shù)設(shè)置為d=50.G-ABCA算法中遺傳算法的最大迭代次數(shù)設(shè)為100,編碼精度設(shè)為10-5,初始的交叉、變異概率分別設(shè)為0.9和0.005,G-ABCA算法中人工蜂群算法的蜜蜂總數(shù)設(shè)為20,采蜜蜂數(shù)設(shè)為10,最大搜索次數(shù)設(shè)為100,最大迭代次數(shù)設(shè)為800;改進(jìn)的GA和ABCA最大迭代次數(shù)均為800,其余參數(shù)設(shè)置與G-ABCA算法一致.實(shí)驗(yàn)結(jié)果見表1至表4、圖1至圖4.

表1:Sphere測試函數(shù)的實(shí)驗(yàn)結(jié)果

表2:Griewank測試函數(shù)的實(shí)驗(yàn)結(jié)果

表3:Rosenbrock測試函數(shù)的實(shí)驗(yàn)結(jié)果

表4:Rastrigin測試函數(shù)的實(shí)驗(yàn)結(jié)果

表1至表4反映三種算法對于各測試函數(shù)極小值解的一次尋優(yōu)結(jié)果.可以看出,對于四個(gè)測試函數(shù),改進(jìn)的GA收斂到最優(yōu)解的進(jìn)化代數(shù)都非常小,得到的最優(yōu)解與測試函數(shù)的全局極小值都相差很大,說明均出現(xiàn)“早熟”;ABCA雖然僅在Griewank函數(shù)測試中得到的最優(yōu)解與其全局極小值有較小的偏差,但是其收斂到最優(yōu)解的進(jìn)化代數(shù)顯著高于G-ABCA算法.由此可見,G-ABCA算法確實(shí)有效避免了遺傳算法的“早熟”,并且通過加快ABCA的初始搜索速度,提高了算法的整體收斂速度.另外,從計(jì)算時(shí)間上可以看出,雖然G-ABCA算法是改進(jìn)的GA與ABCA的融合,但是其并沒有比ABCA算法多費(fèi)時(shí)很多,甚至其在Sphere函數(shù)測試中的計(jì)算時(shí)間略低于ABCA算法;而改進(jìn)的GA由于“早熟”導(dǎo)致其計(jì)算時(shí)間很短,因此不具有可比性.

圖1:Sphere測試函數(shù)的對比結(jié)果

圖2:Griewank測試函數(shù)的對比結(jié)果

圖1至圖4反映三種算法對于各測試函數(shù)極小值解的一次尋優(yōu)過程對比結(jié)果.可以直觀地看出,G-ABCA算法是逐步收斂的,其收斂性能顯著優(yōu)于GA(即改進(jìn)的GA)算法和ABCA算法,而且GA算法明顯過早收斂,發(fā)生“早熟”.

圖3:Rosenbrock測試函數(shù)的對比結(jié)果

圖4:Rastrigin測試函數(shù)的對比結(jié)果

結(jié)論:改進(jìn)的遺傳算法與人工蜂群算法的融合,實(shí)現(xiàn)了兩種算法的互補(bǔ),不僅避免了遺傳算法發(fā)生“早熟”,而且解決了人工蜂群算法初始搜索速度慢的問題.數(shù)值實(shí)驗(yàn)結(jié)果表明, G-ABCA算法在經(jīng)過改進(jìn)的遺傳算法得到“蜜源”分布之后,ABCA算法以極快的速度逼近全局最優(yōu)解,驗(yàn)證了G-ABCA算法具有收斂性以及良好的尋優(yōu)性能.

[1]張愛華,曹曉剛,鐘守楠.求多峰函數(shù)全部全局最優(yōu)解的改進(jìn)遺傳算法[J].數(shù)學(xué)雜志,2009,29(1): 56–60.

[2]馬永杰,云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2012,29(4):1201–1210.

[3]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Kayseri:Erciyes Univ.,2005.

[4]秦全德,程適,李麗等.人工蜂群算法研究綜述[J].智能系統(tǒng)學(xué)報(bào),2014,9(2):127–135.

[5]袁艷花.遺傳蜂群算法及其應(yīng)用[D].南京:南京理工大學(xué)碩士學(xué)位論文,2012.

[6]王芳,楊虎山.實(shí)數(shù)編碼混合遺傳算法在參數(shù)估計(jì)中的應(yīng)用[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào),2013,35(4): 375–384.

[7]Wu Q H,Zhang J H,Xu X H.An ant colony algorithm with mutation features[J].J.Comp.Res. Evel.,1999,36(10):1240–1245.

[8]劉東平,單甘霖.基于改進(jìn)遺傳算法的支持向量機(jī)參數(shù)優(yōu)化[J].微計(jì)算機(jī)應(yīng)用,2010,31(5):11–15.

[9]楊淑瑩,張樺.群體智能與仿生計(jì)算[M].北京:電子工業(yè)出版社,2012.

[10]段海濱,張祥銀,徐春芳.仿生智能計(jì)算[M].北京:科學(xué)出版社,2011.

[11]張文修,梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安:西安交通大學(xué)出版社,2000.

[12]劉峰,劉貴忠,張茁生.遺傳算法的Markov鏈分析與收斂速度估計(jì)[J].系統(tǒng)工程學(xué)報(bào),1998,13(4): 81–87.

[13]鄺溯瓊.遺傳算法參數(shù)自適應(yīng)控制及收斂性研究[D].長沙:中南大學(xué),2009.

[14]Rudolph G.Convergence properties of canonical genetic algorithms[J].IEEE Trans.Neural Networks,1994,5(1):96–101.

[15]Xu C F,Duan H B.Artificial bee colony optimized edge potential function approach to target recognition for low-altitude aircraft[J].Patt.Recog.Lett.,2010,31(13):1759–1772.

[16]Gutjahr W J.A graph-based ant system and its convergence[J].Future Gener.Comp.Sys.,2000, 16(8):873–888.

[17]Duan H B,Xu C F,Zhang X Y.A hybrid artificial bee colony optimization and quantum evolutionary algorithm for continuous optimization problems[J].Intern.J.Neural Sys.,2010,20(1):39–50.

COMBINATION ALGORITHM OF GENETIC-ARTIFICIAL BEE COLONY AND ITS MARKOV CONVERGENCE ANALYSIS

GAO Lei-fu,TONG Pan
(College of Science,Liaoning Technical University,Fuxin 123000,China)

In this paper,we study the problems that genetic algorithm’s prematurity and artificial bee colony algorithm is slow at the beginning of the search.Based on the idea that combining genetic algorithm and artificial bee colony algorithm to achieve complementary,this paper proposes Genetic-Artificial Bee Colony Algorithm(G-ABCA),and analyses the convergence of G-ABCA by Markov theory.And it proves that the sequence of fitness function,which is also called the solution sequence,is monotonous and convergent.Meanwhile,it carries out the contrasting experiment and analysis of G-ABCA,improves genetic algorithm and artificial bee colony algorithm based on four classical multi-modal test functions,the results show that not only G-ABCA is convergent,but also its optimal capability is better than other two algorithms.

genetic algorithm;artificial bee colony algorithm;combination;Markov process;convergence

tion:49M30

O224

A

0255-7797(2017)01-0215-08

2014-09-19接收日期:2014-12-16

高校博士學(xué)科點(diǎn)專項(xiàng)科研聯(lián)合資助基金資助(20132121110009).

高雷阜(1963–),男,遼寧阜新,教授,主要研究方向:最優(yōu)化理論與應(yīng)用.