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

高雷阜,佟盼

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

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

高雷阜,佟盼

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

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

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

1 引言

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

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

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

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

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

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

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

2.2.1 G-ABCA中遺傳算法的設置

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

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

2.2.2 G-ABCA中人工蜂群算法的設置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證因為人工蜂群算法序列{X(m);m=1,2,···}是有限齊次Markov鏈且以概率1收斂[15],適應度函數(shù)序列具有Markov性,因此,類比引入適應度函數(shù)的螞蟻系統(tǒng)序列[16]仍是有限齊次Markov鏈可知,引入適應度函數(shù)的人工蜂群系統(tǒng)序列是有限齊次Markov鏈.

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

證由引理3.1知,改進的遺傳算法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).同時,由人工蜂群算法的設置可知,算法每一次只更新最優(yōu)蜜源位置,具有改進的遺傳算法的所有特征.因此取

其中,i0=表示使f(Xj(n))取最小值的個體為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鏈的適應度函數(shù)值序列是單調(diào)不增的,即?n≥0,f(X(n+1))≤f(X(n)).

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

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

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

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

故

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

證因為對于任意的ε＞0,有滿意解集

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

4 數(shù)值實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

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

[2]馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,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)學報,2014,9(2):127–135.

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

[6]王芳,楊虎山.實數(shù)編碼混合遺傳算法在參數(shù)估計中的應用[J].高等學校計算數(shù)學學報,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]劉東平,單甘霖.基于改進遺傳算法的支持向量機參數(shù)優(yōu)化[J].微計算機應用,2010,31(5):11–15.

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

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

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

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

[13]鄺溯瓊.遺傳算法參數(shù)自適應控制及收斂性研究[D].長沙:中南大學,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

高校博士學科點專項科研聯(lián)合資助基金資助(20132121110009).

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