優(yōu)化的馬爾可夫鏈人工蜂群算法

郭 佳，馬朝斌，張紹博，苗萌萌

1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京100044

2.國(guó)家保密科技測(cè)評(píng)中心，北京100044

1 引言

人工蜂群算法（artificial bee colony algorithm，ABC）是Karaboga[1]于2005 年提出的一種全局優(yōu)化算法，具有計(jì)算簡(jiǎn)潔、易于實(shí)現(xiàn)、控制參數(shù)少等優(yōu)點(diǎn)[2]，但該算法更新迭代過(guò)程中隨機(jī)選擇鄰域解，蜜源進(jìn)化率較低。國(guó)內(nèi)外學(xué)者對(duì)ABC 算法進(jìn)行了諸多改進(jìn)，主要有三方面：一是通過(guò)算法融合進(jìn)行改進(jìn)，如Panniem 等[3]提出Modified ABC，用螢火蟲(chóng)算法產(chǎn)生新的位置來(lái)取代偵察蜂階段未更新的位置。耿璐等[4]利用差分進(jìn)化具有良好的局部更新能力，將ABC 與DE（differential evolution）差分算子結(jié)合提出adaptive modified differential ABC。Tian 等[5]將元胞自動(dòng)機(jī)與ABC 結(jié)合，利用元胞間的自動(dòng)更新保持解的多樣性。這些算法將ABC 算法與其他進(jìn)化算法進(jìn)行整體融合，提高了搜索精度，但增加了搜索的復(fù)雜度。二是利用局部最優(yōu)信息引導(dǎo)算法，如受粒子群算法啟發(fā)，Zhu 等[6]提出GABC（gbeat ABC）算法，用全局最優(yōu)解gbest代替隨機(jī)生成的鄰域解引導(dǎo)搜索。周新宇等[7]在文獻(xiàn)[6]的基礎(chǔ)上使用正交實(shí)驗(yàn)設(shè)計(jì)來(lái)產(chǎn)生新的食物源，確保偵察蜂在不同維度上保存放棄解和全局最優(yōu)解的有用信息。Jadon 等[8]在文獻(xiàn)[3]和文獻(xiàn)[6]的基礎(chǔ)上增加了選擇因子，以避免過(guò)快地收斂到局部最優(yōu)解。宋曉宇等[9]提出自適應(yīng)搜索策略混合人工蜂群算法，利用目標(biāo)函數(shù)值的反饋?zhàn)饔眠M(jìn)行自適應(yīng)調(diào)節(jié)，同時(shí)利用全局最優(yōu)解的引導(dǎo)信息來(lái)增強(qiáng)開(kāi)發(fā)能力。這些方法均以解空間上相對(duì)最優(yōu)的某個(gè)值作為引導(dǎo)，逐步找到函數(shù)最優(yōu)解，但是這類方法容易使算法過(guò)分依賴這個(gè)值，從而導(dǎo)致陷入局部最優(yōu)解。三是針對(duì)解空間進(jìn)行改進(jìn)，如Karaboga[10]于2014年提出快速人工蜂群算法，引入周邊食物源的概念，根據(jù)周邊食物源參數(shù)來(lái)判別出周邊食物源種群大小，從而提高蜂蜜采集效率。Jadon 等[11]利用全局和局部鄰域的差分進(jìn)化，更新食物源信息。Aydin 等[12]提出了增長(zhǎng)式蜂群算法，通過(guò)迭代讓蜂群規(guī)模逐漸增長(zhǎng)，以解決大規(guī)模持續(xù)優(yōu)化問(wèn)題。Kumar 等[13]提出了一種兩步人工蜂群算法，用K-means 算法代替隨機(jī)初始化食物源。但這些思想僅改進(jìn)了有限的局部解信息，沒(méi)有充分利用整個(gè)解空間的發(fā)展規(guī)律，對(duì)于多峰函數(shù)來(lái)說(shuō)，較容易陷入局部最優(yōu)解。

馬爾可夫鏈在啟發(fā)式算法中已有一些工作，比如文獻(xiàn)[14]將馬爾可夫鏈與ABC 算法結(jié)合提出MABC（Markov ABC）算法，但該算法利用的二維解空間缺少馬爾可夫性的理論推導(dǎo)。Wang 等[15]將遺傳算法與馬爾可夫鏈結(jié)合，采用遺傳算法優(yōu)化初始參數(shù)，以馬爾可夫模型作為分類器對(duì)大型點(diǎn)焊機(jī)加工過(guò)程的運(yùn)行狀態(tài)進(jìn)行識(shí)別。Yang 等[16]將馬爾可夫鏈用于遺傳算法運(yùn)行前的目標(biāo)分類，并將改進(jìn)算法應(yīng)用于基于藍(lán)牙的交通檢測(cè)。這些算法均將Markov 鏈用于進(jìn)化算法運(yùn)行前或者后的數(shù)據(jù)處理階段，提高了進(jìn)化算法的尋優(yōu)精度。

本文在文獻(xiàn)[14]的基礎(chǔ)上進(jìn)行改進(jìn)，將原來(lái)的二維解空間擴(kuò)展至三維，從時(shí)間維度組成馬爾可夫鏈進(jìn)行預(yù)測(cè)，提出IMABC（improved Markov ABC）算法。與文獻(xiàn)[15-16]中馬爾可夫鏈僅作用于進(jìn)化算法部分?jǐn)?shù)據(jù)和一段時(shí)間不同，IMABC 算法在空間上將馬爾可夫鏈作用于整個(gè)解空間，在時(shí)間上將馬爾可夫鏈作用于整個(gè)算法運(yùn)行過(guò)程。

2 基本算法

2.1 馬爾可夫鏈

馬爾可夫（Markov）鏈?zhǔn)敲枋鰟?dòng)態(tài)隨機(jī)現(xiàn)象的數(shù)學(xué)模型。它基于系統(tǒng)“狀態(tài)”和“狀態(tài)轉(zhuǎn)換”的概念[17-18]，根據(jù)概率分布，從一種狀態(tài)轉(zhuǎn)換為另一種狀態(tài)[19]，該方法已應(yīng)用于眾多實(shí)際領(lǐng)域[20-21]，其定義如下：

在有限或可數(shù)個(gè)值的隨機(jī)過(guò)程{Xn,n=1,2,…}中，把所取可能值的全體記為狀態(tài)空間S，用{Xn=i}表示過(guò)程在時(shí)刻n處于狀態(tài)i，假設(shè)每當(dāng)過(guò)程處于狀態(tài)i，則在下一個(gè)時(shí)刻將處于狀態(tài)j的概率是固定的pij，即對(duì)任意時(shí)刻n，P(Xn+1=j|Xn=i)=pij，若對(duì)任意狀態(tài)i1,i2,…,in，始終有P(Xn+1=j|Xn=in,Xn-1=in-1,…,X1=i1)=P(Xn+1=j|Xn=in)，這樣的離散過(guò)程被稱為馬爾可夫鏈。假設(shè)狀態(tài)空間是有限集，則稱為有限狀態(tài)馬爾可夫鏈。若對(duì)于任意的l，有P(Xt+l=j|Xl=i)=P(Xt=，即其轉(zhuǎn)移概率不依賴于l時(shí),{Xt,t≥0}稱為齊次馬爾可夫鏈[16]，轉(zhuǎn)移概率為：

其中，Li表示狀態(tài)Si出現(xiàn)的總次數(shù)，表示狀態(tài)Si經(jīng)n步轉(zhuǎn)移到狀態(tài)Sj的次數(shù)，根據(jù)轉(zhuǎn)移概率形成狀態(tài)轉(zhuǎn)移矩陣，并在下一個(gè)時(shí)刻進(jìn)行預(yù)測(cè)：

其中，Δl是狀態(tài)區(qū)間的下限，Δu是狀態(tài)區(qū)間的上限，f(x)是滾動(dòng)預(yù)測(cè)值。

2.2 人工蜂群算法

人工蜂群算法將蜜蜂分為雇傭蜂、跟隨蜂和偵察蜂。該算法的步驟如下：

（1）初始階段。確定蜜源大小SN；蜜蜂的數(shù)量與蜜源的數(shù)量一致，蜜源Xi=(xi1,xi2,…,xiD)代表候選解，其中i∈{1,2,…,SN}，D是蜜源的維度，蜜源范圍是[xmin,xmax]，首先按式（3）生成初始種群：

其中，rand是介于（0,1）之間的隨機(jī)數(shù)，j∈{1,2,…,D}，若xij超出了解空間范圍，則按式（4）變?yōu)檫吔缰担?/p>

求解后使用適應(yīng)度函數(shù)來(lái)判斷蜜源質(zhì)量：

（2）雇傭蜂階段。每次采蜜時(shí)在蜜源附近按式（6）隨機(jī)產(chǎn)生候選解：

其中，xij是搜索空間中的第i個(gè)蜜源，xkj是不同于xij的另一個(gè)蜜源，k∈{1,2,…,SN}，rand是介于（0，1）之間的隨機(jī)數(shù)。雇傭蜂通過(guò)貪婪選擇算法決定是否由υij替換xij。

（3）跟隨蜂階段。通過(guò)輪盤(pán)賭算法，按式（7）計(jì)算收益率Pi在整個(gè)種群中的概率，確定是否選擇該蜜源，選擇蜜源后，跟隨蜂轉(zhuǎn)變?yōu)楣蛡蚍洹?/p>

（4）偵察蜂階段。當(dāng)一個(gè)蜜源達(dá)到開(kāi)采的上限Limit時(shí)，將淘汰蜜源，并根據(jù)式（3）隨機(jī)選擇一個(gè)新的蜜源。

3 算法的改進(jìn)

3.1 齊次馬爾可夫鏈性質(zhì)的分析

（1）有限性論證。在初始化階段，解空間的范圍為[xmin,xmax]，每個(gè)解的維度D有限，蜂群數(shù)量為NP，生成時(shí)步為1，隨著時(shí)步的推移，生成時(shí)步為t，每個(gè)維度的參數(shù)都是有限的，故所有蜂群狀態(tài)空間有限。

（2）齊次馬爾可夫性論證。當(dāng)雇傭蜂更新候選解的時(shí)候，t步概率表達(dá)式為：

其中，pxij→vij(t)為經(jīng)t步由狀態(tài)xij轉(zhuǎn)換到vij的概率，L為通過(guò)貪婪算法對(duì)解的選擇結(jié)果，若fit(xij)≤fit(vij)，L=1，否則等于0。根據(jù)式（6），為xij至xkj空間中任意一點(diǎn)的概率。由式（8）可以看出，除了考慮空間的上下界外，解從狀態(tài)xij轉(zhuǎn)換到vij的概率只與xij和隨機(jī)選擇的值xkj有關(guān)，也就是說(shuō)，個(gè)體的狀態(tài)轉(zhuǎn)移只與前一時(shí)刻有關(guān)。因此，人工蜂群算法的種群狀態(tài)序列為有限齊次Markov 鏈。

3.2 優(yōu)化的改進(jìn)算法

IMABC 算法將采蜜過(guò)程分為兩個(gè)階段，分割參數(shù)記為ω。第一階段為原始ABC 算法，運(yùn)行ω次后進(jìn)入第二階段，從初始狀態(tài)到第一階段結(jié)束，過(guò)程中所有歷史解記為Markov 解空間，即由xij擴(kuò)充為xijt，記為Xt=(xij1,xij2,…,xijω)，將Xt按照當(dāng)前解生成的時(shí)步順序ω進(jìn)行排序，最小時(shí)步的生成解在最前面，依次形成按時(shí)步遞進(jìn)的Markov 鏈解空間，再將Markov 鏈解空間劃分為N個(gè)狀態(tài)子空間，邊界值Qn如式（9）所示：

其中，n∈{1,2,…,N+1}，在確定D和SN的前提下，Xmin為Markov 三維解空間在時(shí)間維度的最小值，Xmax為Markov 三維解空間在時(shí)間維度的最大值，t∈{1,2,…,ω}。將狀態(tài)子空間記為Sn，按式（10）所示劃分：

將Markov解空間內(nèi)的解Xt分別置于N個(gè)子空間中。按式（1）計(jì)算m步狀態(tài)轉(zhuǎn)移概率，m∈{1,2,…,M}，形成M個(gè)狀態(tài)轉(zhuǎn)移概率矩陣P(m)，選取離預(yù)測(cè)值最近的M個(gè)時(shí)步的值進(jìn)行預(yù)測(cè)，以離預(yù)測(cè)時(shí)步的遠(yuǎn)近為順序，時(shí)步小在前，在狀態(tài)轉(zhuǎn)移矩陣中，選取與m時(shí)步相對(duì)應(yīng)的起始狀態(tài)所在的行向量，組成預(yù)測(cè)矩陣。計(jì)算狀態(tài)子空間Sn轉(zhuǎn)移到Sn′的總概率，如式（11）所示：

Table 1 State transition prediction表1 狀態(tài)轉(zhuǎn)移預(yù)測(cè)

根據(jù)表1 計(jì)算得出：

pbest所對(duì)應(yīng)的狀態(tài)空間即為預(yù)測(cè)解所在的最優(yōu)狀態(tài)子空間。獲得最優(yōu)狀態(tài)子空間后，按式（2）計(jì)算新解，代替適應(yīng)度最差的解。隨著t的增加，Xt中的元素逐漸增多，優(yōu)化過(guò)程變慢，需對(duì)Xt進(jìn)行處理，過(guò)濾掉初始階段對(duì)預(yù)測(cè)沒(méi)有意義的解，形成新的Markov 解空間V，如式（12）所示：

其中，t為迭代次數(shù)，λ為丟棄參數(shù)，介于(1,lnt)之間，用于控制丟棄比例。在早期階段，基于初始隨機(jī)解生成的解空間不能充分代表解空間的發(fā)展趨勢(shì)，應(yīng)被丟棄，故在時(shí)步t較小時(shí)，前期解丟棄的比例越大對(duì)預(yù)測(cè)進(jìn)行的干擾越少。隨著算法運(yùn)行時(shí)步t的增加，解空間具有兩方面的特點(diǎn)：一是范圍迅速擴(kuò)大；二是隨著適用度值逐漸增加，越來(lái)越趨于某一值。故如果按前期的丟棄數(shù)量進(jìn)行丟棄，解空間范圍沒(méi)有明顯縮小，算法運(yùn)行效率會(huì)越來(lái)越低；如果仍按前期的丟棄比例進(jìn)行丟棄，會(huì)加大收斂速度，但在局部最優(yōu)解較多的函數(shù)尋優(yōu)過(guò)程中，會(huì)減少算法的開(kāi)拓能力，導(dǎo)致算法尋優(yōu)結(jié)果為局部最優(yōu)解。故在Markov 解空間的變化過(guò)程中應(yīng)保證：隨著時(shí)步t的增加，丟棄解的數(shù)量增加，但占總時(shí)步比例減小。按式（12），取λ=1，計(jì)算對(duì)應(yīng)于不同循環(huán)時(shí)步的新Markov 解空間范圍如表2 所示。

Table 2 Range of solution space changing with time表2 隨時(shí)步增加而變化的解空間范圍

從表2 可以看出，在循環(huán)次數(shù)較小時(shí)，早期解丟棄的數(shù)量小，但占總時(shí)步比例大；隨著循環(huán)次數(shù)的增加，解丟棄的數(shù)量大，但占總時(shí)步比例小。在算法運(yùn)行效率和結(jié)果準(zhǔn)確性之間達(dá)到了一定平衡。

IMABC 的偽代碼如下，其中SN為蜜源數(shù)量，MaxCycles為最大迭代次數(shù)，D為解的維度；ub為解空間的上限，lb為解空間的下限，limit為單個(gè)蜜源的開(kāi)采次數(shù)上限，ω為分割參數(shù)，N為劃分的子空間數(shù)量。

IMABC 主函數(shù)偽代碼如下：

3.3 算法性能分析

3.3.1 算法收斂效率分析

IMABC 算法的迭代分為初期、中期和后期三部分。前期為迭代次數(shù)小于分割參數(shù)階段，因IMABC算法依賴于已經(jīng)產(chǎn)生的解空間，故需先運(yùn)行ABC 算法，產(chǎn)生用于迭代的初始解空間，此時(shí)算法的收斂效率和運(yùn)行時(shí)間與原始的ABC 算法一致，按式（6），算法復(fù)雜度為T(mén)ABC=sn×(d+1)，其中搜索的復(fù)雜度是sn×d，計(jì)算每個(gè)食物源適應(yīng)度值的復(fù)雜度是sn。中期為根據(jù)初始解空間進(jìn)行迭代更新尋找最優(yōu)值的階段，此時(shí)解空間的維度是sn×d×t，其中t從ω開(kāi)始。在已有初始解空間的基礎(chǔ)上，IMABC 算法依時(shí)步的增加不斷更新解空間，既保留了已有解的有效信息，又避免了依賴某一最優(yōu)解導(dǎo)致的算法早熟，可以高效準(zhǔn)確地找到最優(yōu)點(diǎn)。但同時(shí)，隨著迭代次數(shù)t的增加，解空間也隨之增加，按式（12）進(jìn)行處理后解空間維度變?yōu)?，此時(shí)算法復(fù)雜度為。后期為t較大的階段，此時(shí)IMABC 算法的搜索時(shí)間明顯變長(zhǎng)，故IMABC算法雖然可以顯著提高算法的精度，卻要犧牲一定的時(shí)間成本。但同時(shí)也要考慮，在實(shí)際尋優(yōu)過(guò)程中，往往會(huì)在算法達(dá)到一定精度后觸發(fā)停止條件，因此IMABC 算法會(huì)比ABC 提前達(dá)到收斂所需精度，減少I(mǎi)MABC 算法的復(fù)雜度和運(yùn)行時(shí)間。

3.3.2 算法尋優(yōu)能力分析

ABC 算法本身具有的特點(diǎn)就是重勘探輕開(kāi)采，即具有良好的全局尋優(yōu)能力，但是局部尋優(yōu)能力差，IMABC 算法在初期采用原始的ABC 算法，且通過(guò)分割參數(shù)控制原始ABC 算法在整體算法中的比重，可以有效地保留算法的全局尋優(yōu)能力。

當(dāng)逐漸趨于最優(yōu)值的時(shí)候，需要盡量多地保留解空間的優(yōu)質(zhì)解信息，但在ABC 算法中，雇傭蜂階段按式（6）找到新蜜源，由于xkj的隨機(jī)性，蜂群的先驗(yàn)信息丟失，適應(yīng)度高的蜜源被放棄，造成算法震蕩。但是若按以文獻(xiàn)[6]為代表的最優(yōu)值引導(dǎo)收斂算法，會(huì)導(dǎo)致過(guò)分依賴gbest，在有多個(gè)局部極值點(diǎn)的情況下算法易趨向于局部最小值。IMABC 最大限度地保留了解空間的優(yōu)質(zhì)解信息，并根據(jù)適應(yīng)度值預(yù)測(cè)出最佳子解空間，進(jìn)一步更新迭代，避免了搜尋過(guò)程中的盲目和過(guò)分引導(dǎo)，提高了局部尋優(yōu)能力。

4 實(shí)驗(yàn)驗(yàn)證

本章包括4 個(gè)實(shí)驗(yàn)，第1、2 個(gè)實(shí)驗(yàn)分別從結(jié)果的準(zhǔn)確性、收斂效率和運(yùn)行時(shí)間上比較了IMABC 算法、GABC 算法和ABC 算法，第3 個(gè)實(shí)驗(yàn)比較了不同分割參數(shù)對(duì)IMABC 算法的影響，第4 個(gè)實(shí)驗(yàn)比較了不同維度對(duì)IMABC 算法的影響。

選擇9 種經(jīng)典測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)，不同函數(shù)的公共參數(shù)設(shè)置相同，如表3 所示。

這9 個(gè)函數(shù)[22-24]中f1、f4、f5、f7和f8為單峰函數(shù)，僅有一個(gè)極值點(diǎn)，其中f5會(huì)在給定的間隔上出現(xiàn)不同的階躍現(xiàn)象，并伴隨產(chǎn)生大量局部極值，f2、f3、f6和f9是典型的非線性多模態(tài)函數(shù)，在解空間中存在大量的局部極小值點(diǎn)，算法對(duì)此類函數(shù)進(jìn)行尋優(yōu)極易陷入局部最優(yōu)解。

4.1 結(jié)果準(zhǔn)確性比較

該實(shí)驗(yàn)從結(jié)果的準(zhǔn)確性上比較IMABC 算法、GABC 算法和ABC 算法，設(shè)置維度D=30，分割參數(shù)ω=1 000，后續(xù)實(shí)驗(yàn)將擴(kuò)展比較D和ω。不同文獻(xiàn)給出的SN參考值不同，本文采用文獻(xiàn)[1]中的取值30。Limit的大小直接決定IMABC 算法的性能，其值越小，食物源被放棄的可能性越大，算法執(zhí)行率越高。IMABC 算法的Limit參數(shù)有3 種典型值100、200和SN×D，本文采用Limit的最小值100，以實(shí)現(xiàn)函數(shù)的最高執(zhí)行率。設(shè)置最大循環(huán)數(shù)MaxCycle=10 000。進(jìn)行30 次實(shí)驗(yàn)，記錄每個(gè)值并計(jì)算平均值、標(biāo)準(zhǔn)差、最佳值和最差值。測(cè)試結(jié)果如表4 所示。

從表4 可以看出，在本節(jié)設(shè)定的實(shí)驗(yàn)參數(shù)前提下，ABC 算法、GABC 算法和IMABC 算法均求出了函數(shù)f5的最優(yōu)解，尋優(yōu)精度一致。在其他函數(shù)尋優(yōu)過(guò)程中，改進(jìn)的IMABC 算法比原始ABC 算法和GABC 算法的結(jié)果精度有明顯提高。

4.2 收斂速度比較

該實(shí)驗(yàn)從算法收斂效率和運(yùn)行時(shí)間上比較了IMABC 算法、GABC 算法和ABC 算法，設(shè)置維度D=30，MaxCycle=500，分割參數(shù)ω=100，SN=30 。首先，為每個(gè)測(cè)試功能設(shè)置預(yù)設(shè)精度，如果在最大循環(huán)時(shí)間內(nèi)達(dá)到預(yù)設(shè)精度，則認(rèn)為該操作成功，否則為失敗。進(jìn)行10 次實(shí)驗(yàn)，測(cè)試結(jié)果列于表5。其中，“最小運(yùn)行次數(shù)”為函數(shù)重復(fù)尋優(yōu)過(guò)程10 次中達(dá)到預(yù)設(shè)精度值時(shí)的最小運(yùn)行次數(shù)，“最大運(yùn)行次數(shù)”為函數(shù)重復(fù)尋優(yōu)過(guò)程10 次中達(dá)到預(yù)設(shè)精度值時(shí)的最大運(yùn)行次數(shù)，“算法成功率”為函數(shù)重復(fù)尋優(yōu)過(guò)程10 次中達(dá)到預(yù)設(shè)精度的比率，“平均運(yùn)行次數(shù)”為10 次函數(shù)重復(fù)尋優(yōu)過(guò)程所有運(yùn)行次數(shù)的平均值，其中沒(méi)有達(dá)到預(yù)設(shè)精度的運(yùn)行次數(shù)不算在內(nèi)，“/”表示函數(shù)重復(fù)尋優(yōu)過(guò)程中沒(méi)有一次達(dá)到預(yù)設(shè)精度，“運(yùn)行時(shí)間”為10 次函數(shù)尋優(yōu)過(guò)程運(yùn)行時(shí)間的平均數(shù)。

Table 3 Standard test function表3 測(cè)試函數(shù)

Table 4 Comparison of optimization accuracy results of different algorithms表4 不同算法的優(yōu)化精度結(jié)果比較

Table 5 Comparison of algorithm success rate under given accuracy表5 在給定精度下算法成功率的比較

根據(jù)表5 可以看出，在指定預(yù)設(shè)精度的函數(shù)尋優(yōu)過(guò)程中，對(duì)于函數(shù)f2、f3、f6和f8，算法ABC 和GABC 的成功率為0，而IMABC 達(dá)到了100%。對(duì)于函數(shù)f1和f4，算法ABC 的成功率為0，GABC 有部分達(dá)到了收斂精度，而IMABC 的收斂成功率達(dá)到了100%。對(duì)于函數(shù)f7，算法IMABC 比ABC 和GABC算法的成功率高。對(duì)于函數(shù)f5和f9，3 個(gè)算法均在500 次循環(huán)內(nèi)找到了函數(shù)的最優(yōu)值，算法成功率達(dá)到了100%，但平均運(yùn)行次數(shù)差不多。因?yàn)閒5為階躍函數(shù)，函數(shù)值計(jì)算的過(guò)程中采用取底運(yùn)算，f9的函數(shù)值計(jì)算過(guò)程中采用絕對(duì)值運(yùn)算，故這兩個(gè)函數(shù)均存在多個(gè)不同的解對(duì)應(yīng)于一個(gè)函數(shù)值的情況，也就是不同的解對(duì)應(yīng)相同的適應(yīng)度值，導(dǎo)致IMABC 算法無(wú)法有效地判斷Markov 解空間內(nèi)子空間的優(yōu)劣，故在迭代次數(shù)較少時(shí)IMABC算法的收斂效率與ABC相差不多。

表5 最后一列為10 次函數(shù)重復(fù)尋優(yōu)運(yùn)行時(shí)間的平均數(shù)，從函數(shù)f9所用時(shí)間可以看出，IMABC 算法的運(yùn)行時(shí)間約為ABC 和GABC 算法的4 倍，可見(jiàn)IMABC 算法以時(shí)間換取精度。但因在預(yù)設(shè)精度的尋優(yōu)過(guò)程中，IMABC 算法達(dá)到停止條件所用迭代次數(shù)少，所用尋優(yōu)時(shí)間明顯降低，f3在IMABC 算法下的尋優(yōu)時(shí)間甚至還要少于ABC 及GABC 算法。

圖1 為本次實(shí)驗(yàn)中達(dá)到預(yù)設(shè)精度時(shí)的函數(shù)收斂曲線。

從圖1 可以看出除函數(shù)f5和f9外，其余7 個(gè)函數(shù)通過(guò)IMABC 算法的收斂效率明顯高于ABC 算法和GABC 算法。從圖1 還可以看出IMABC 算法的收斂曲線相對(duì)平滑，ABC 和GABC 算法的收斂曲線呈階梯狀較明顯。因?yàn)镮MABC 算法的尋優(yōu)過(guò)程是基于整個(gè)解空間的迭代更新，函數(shù)迭代過(guò)程中基本每一次均會(huì)更新解，而ABC 算法迭代過(guò)程中新解的更新依賴于隨機(jī)選取的鄰域解，存在多次迭代仍未更新的現(xiàn)象，故在函數(shù)尋優(yōu)過(guò)程中呈階梯下降狀態(tài)。同樣，GABC 利用最優(yōu)解引導(dǎo)尋優(yōu)過(guò)程，會(huì)出現(xiàn)一次明顯的函數(shù)值變化后長(zhǎng)期處于不更新的狀態(tài)。

在本次實(shí)驗(yàn)中，函數(shù)的尋優(yōu)過(guò)程如圖2所示，因圖形較多，僅選取單峰函數(shù)f1、f7和多峰函數(shù)f2。

Fig.1 Curve of function convergence result圖1 函數(shù)收斂結(jié)果曲線

根據(jù)圖2 的（a）至（c）可以看出，因本次實(shí)驗(yàn)分割參數(shù)設(shè)為100，故在迭代次數(shù)小于100 時(shí)IMABC 與ABC、GABC算法收斂速度基本一致，但是隨著迭代次數(shù)的增加，根據(jù)圖2的（d）至（f）可以看出，在150到200階段，IMABC 算法已能顯出較好的收斂速度，隨著迭代次數(shù)的進(jìn)一步增加，就達(dá)到如圖1所示的收斂結(jié)果。

4.3 分割參數(shù)的擴(kuò)展比較

分割參數(shù)值ω的不同直接影響函數(shù)優(yōu)化結(jié)果，本實(shí)驗(yàn)驗(yàn)證不同分割參數(shù)對(duì)IMABC 算法的影響。設(shè)維度D=30，MaxCycle=1 000，SN=10。本實(shí)驗(yàn)從ω=100 開(kāi)始，每增加100 進(jìn)行一次運(yùn)算。當(dāng)ω=1 000 時(shí)，表示未運(yùn)行IMABC 算法，等效于ABC 算法。分別選擇單峰測(cè)試函數(shù)f1，多峰測(cè)試函數(shù)f2和f3，進(jìn)行30次實(shí)驗(yàn)，記錄每個(gè)值并計(jì)算平均值、標(biāo)準(zhǔn)差、最優(yōu)值和最差值，測(cè)試結(jié)果如表6 所示。

從表6 可看出，ω值小于1 000 時(shí)的實(shí)驗(yàn)結(jié)果均優(yōu)于ω等于1 000 時(shí)的性能，進(jìn)一步證明了IMABC算法的性能優(yōu)于ABC 算法。

Fig.2 Curve of function convergence process圖2 函數(shù)收斂過(guò)程曲線

Table 6 Comparison of optimization results of different segmentation parameters表6 不同分割參數(shù)的優(yōu)化結(jié)果比較

同時(shí)可以看出，在函數(shù)f1的尋優(yōu)過(guò)程中，最優(yōu)值出現(xiàn)在ω=500 時(shí)，而在f2和f3的尋優(yōu)過(guò)程中，最優(yōu)值出現(xiàn)在ω=300 時(shí)。因?yàn)閒2和f3均是多峰函數(shù)，有多個(gè)局部極值點(diǎn)，尋找極值點(diǎn)較困難，故越早使用IMABC 算法越有助于函數(shù)尋優(yōu)。

4.4 不同維度的擴(kuò)展比較

本實(shí)驗(yàn)驗(yàn)證不同維度對(duì)IMABC 算法性能的影響。設(shè)分割參數(shù)ω=100，MaxCycle=5 000，SN=10，維度D從10 開(kāi)始，每增加20 進(jìn)行一次運(yùn)算，增至90。分別選擇單峰測(cè)試函數(shù)f1，多峰測(cè)試函數(shù)f2和f3，進(jìn)行30 次實(shí)驗(yàn)，記錄每個(gè)值并計(jì)算平均值、標(biāo)準(zhǔn)差、最優(yōu)值和最差值，測(cè)試結(jié)果如表7 所示。

Table 7 Comparison of optimization results of different dimensions表7 不同維度的優(yōu)化結(jié)果比較

如表7 所示，隨著維度的增加，尋優(yōu)難度增大，精度逐漸降低。

5 結(jié)束語(yǔ)

本文將馬爾可夫鏈與人工蜂群算法融合，提出IMABC 算法。IMABC 算法分為兩個(gè)階段，第一階段運(yùn)行ABC 算法得出初始解空間，第二階段利用馬爾可夫鏈對(duì)第一階段產(chǎn)生的解空間進(jìn)行重構(gòu)，并進(jìn)一步預(yù)測(cè)新解。通過(guò)實(shí)驗(yàn)驗(yàn)證得出IMABC算法具有較高的精度和收斂速度，但算法運(yùn)行時(shí)間較長(zhǎng)。在后續(xù)研究中，將進(jìn)一步完善IMABC 算法，研究最優(yōu)解狀態(tài)空間的動(dòng)態(tài)變化，提取有用信息，逐漸縮小解空間，減少馬爾可夫鏈預(yù)測(cè)過(guò)程中消耗的運(yùn)行步驟，從而進(jìn)一步減小算法的運(yùn)行時(shí)間。