基于MIMIC算法和RPCA的混合蟻群優(yōu)化算法

官娟 劉國(guó)華 劉天祺 秦健 張淼森

0 引言

元啟發(fā)式算法是一類(lèi)優(yōu)化技術(shù),在過(guò)去幾年中得到了越來(lái)越快的發(fā)展,并被應(yīng)用于許多問(wèn)題．蟻群算法是一類(lèi)比較典型和重要的元啟發(fā)式算法,最早由Colorni等在1992年提出[1],算法主要針對(duì)自然界的螞蟻覓食做了經(jīng)典實(shí)驗(yàn),通過(guò)將真實(shí)螞蟻的行為模型化,得出了人工螞蟻解決多目標(biāo)決策問(wèn)題的思路．基于此思想,Dorigo等開(kāi)創(chuàng)性地提出了蟻群算法[2]．蟻群算法的本質(zhì)是一個(gè)復(fù)雜的智能系統(tǒng)——螞蟻系統(tǒng)(AS),它具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制,以及易于與其他算法相結(jié)合等優(yōu)點(diǎn).

雖然蟻群算法具有許多優(yōu)點(diǎn),在低維問(wèn)題中可取得較好的效果,但對(duì)于大規(guī)模問(wèn)題全局尋優(yōu)性能急劇下降,存在一些缺陷,如收斂速度慢、容易陷入局部最優(yōu)解等,同時(shí)這也是大部分優(yōu)化算法所面臨的問(wèn)題．針對(duì)此現(xiàn)狀,近年來(lái)許多學(xué)者在蟻群算法的改進(jìn)方面進(jìn)行了研究,并提出了許多改進(jìn)的蟻群算法,包括蟻群優(yōu)化 (ACO) 的元啟發(fā)式方法[3]、蟻群系統(tǒng)(ACS)[4]、基于Q-學(xué)習(xí)的自適應(yīng)蟻群算法[5]、最大最小螞蟻系統(tǒng)(MMAS等)[6]．這些改進(jìn)的算法主要從信息素釋放方式、信息素更新規(guī)則、路徑選擇策略、參數(shù)的選擇等方面入手,對(duì)蟻群算法進(jìn)行了不同程度的改進(jìn),但仍存在一個(gè)很大的問(wèn)題,即隨機(jī)性對(duì)解搜索帶來(lái)的較強(qiáng)干擾,使得解變量之間的相關(guān)性和抽樣求解的效率太低、冗余度過(guò)高,嚴(yán)重制約了蟻群算法在高維空間中的優(yōu)化性能．已有的蟻群優(yōu)化算法中缺少對(duì)關(guān)于隨機(jī)變量間相關(guān)性的研究,Socha等[7]在研究連續(xù)域上的蟻群算法中有過(guò)相關(guān)問(wèn)題的探討,但并未對(duì)算法中變量相關(guān)性做進(jìn)一步的研究.

為更有效地處理大規(guī)模優(yōu)化問(wèn)題,提高算法性能,本文在蟻群算法中,加入變量相關(guān)性分析并根據(jù)決策變量的相關(guān)性定義,提出一種新的關(guān)于解分量之間的相關(guān)性定義——有效相關(guān)性與冗余相關(guān)性;然后,根據(jù)得到的有效相關(guān)性矩陣,運(yùn)用MIMIC(Mutual Information Maximization for Input Clustering)分布估計(jì)算法對(duì)解存檔建立決策變量間的概率圖模型,并根據(jù)概率模型采樣獲得新的解存檔,來(lái)提高蟻群優(yōu)化算法的全局搜索能力;接著,利用RPCA(Robust Principal Component Analysis)技術(shù)找到新的解存檔的低秩結(jié)構(gòu)矩陣,優(yōu)化搜索空間、降低計(jì)算復(fù)雜度,進(jìn)而在蟻群算法框架下,更新解存檔;最后,通過(guò)實(shí)驗(yàn)仿真測(cè)試算法性能,將所得結(jié)果與連續(xù)域上的蟻群優(yōu)化算法相比較,表明該算法可降低多個(gè)解分量之間的冗余相關(guān)性,在尋優(yōu)能力和收斂性方面都有顯著提高.

1 連續(xù)域上的蟻群優(yōu)化算法

連續(xù)域上的蟻群優(yōu)化算法ACOR(Ant Colony Optimization for Continuous Domains)[7]均勻隨機(jī)產(chǎn)生k個(gè)解作為初始解存檔,如圖1所示．每個(gè)解都是一個(gè)D維向量,其實(shí)值解決策分量xi∈[xmin,xmax],其中i=1,…,D．本文假定優(yōu)化問(wèn)題中只存在box有界約束．根據(jù)目標(biāo)函數(shù)值從優(yōu)至劣對(duì)解存檔中k個(gè)解進(jìn)行排序,每個(gè)解Sk都關(guān)聯(lián)了一個(gè)權(quán)重ωk．該權(quán)重使用高斯函數(shù)計(jì)算,如下所示:

(1)

其中r(j)是排序解存檔中解Sj的序號(hào),q是算法的一個(gè)參數(shù).

2 基于MIMIC算法和RPCA的混合蟻群算法

2.1 變量相關(guān)性

現(xiàn)有的蟻群優(yōu)化算法中,隨機(jī)性對(duì)解的搜索帶來(lái)了較強(qiáng)的干擾,使得解變量之間的相關(guān)性太低、抽樣求解的效率太低、冗余度過(guò)高,嚴(yán)重制約了蟻群算法的優(yōu)化性能．因此,顯著提高蟻群算法的優(yōu)化性能就必須克服抽樣解選取過(guò)程中的相關(guān)性問(wèn)題.

基于以上考慮,本文首先根據(jù)決策變量間的相關(guān)性定義,給出解分量之間的有效相關(guān)性和冗余相關(guān)性的定義.

2.1.1 解分量與解分量之間的相關(guān)性

根據(jù)文獻(xiàn)[8-9],兩個(gè)決策變量xi和xj被稱(chēng)為相關(guān),如果?x=(x1,x2,…,xn),x′i,x′j滿(mǎn)足下列條件:

f(x1,…,xi,…,xj,…,xn)

f(x1,…,xi,…,x′j,…,xn)>f(x1,…,x′i,…,x′j,…,xn)，

(2)

其中x是候選決策向量,x′i,x′j分別被第i和第j個(gè)決策變量替換,“∧”表示邏輯符號(hào)“且”.

2.1.2 解分量與解分量之間的有效相關(guān)性

設(shè)X為當(dāng)前解,samplei為對(duì)第i個(gè)分量進(jìn)行采樣的采樣算子,>opt代表更優(yōu)化的比較算子,即只要存在一個(gè)可行解,滿(mǎn)足式(2),則說(shuō)明解分量xi與解分量xj關(guān)于目標(biāo)函數(shù)f存在相關(guān)性,然而式(2)只刻畫(huà)了變量間相關(guān)性的存在性,并未指出對(duì)優(yōu)化過(guò)程具有有效促進(jìn)作用的部分相關(guān)性,因此定義一個(gè)有效相關(guān)性如下:

?x=(x1,x2,…,xn),x′i=samplei(X),x′j

s.tf(x1,…,x′i,…,x′j,…,xn)>opt

f(x1,…,xi,…,x′j,…,xn)

∨

?x=(x1,x2,…,xn),x′i,x′j=samplei(X)

s.tf(x1,…,x′i,…,x′j,…,xn)>opt

f(x1,…,x′i,…,xj,…,xn)

(3)

其中“∨”表示邏輯符號(hào)“或”.

2.1.3 解分量與解分量之間的冗余相關(guān)性

相應(yīng)地,稱(chēng):

?x=(x1,x2,…,xn),x′i=samplei(X),x′j

s.tf(x1,…,x′i,…,x′j,…,xn)

f(x1,…,xi,…,x′j,…,xn)

∧

?x=(x1,x2,…,xn),x′i,x′j=samplei(X)

s.tf(x1,…,x′i,…,x′j,…,xn)

f(x1,…,x′i,…,xj,…,xn)

(4)

為解分量xi與xj關(guān)于f的冗余相關(guān)部分.

分布估計(jì)算法[10-11]是一種基于種群的搜索算法．它利用解存檔建立概率分布模型,然后根據(jù)概率分布模型來(lái)指導(dǎo)個(gè)體進(jìn)行搜索,其過(guò)程是一個(gè)不斷更新概率模型,從而使概率模型越來(lái)越能反映優(yōu)秀個(gè)體分布的過(guò)程．所以,分布估計(jì)算法具有比較強(qiáng)的全局搜索能力.

蟻群優(yōu)化算法搜索時(shí)間長(zhǎng),易陷入局部最優(yōu)解是其最為突出的缺點(diǎn).為了提高蟻群算法的尋優(yōu)能力,可以在蟻群優(yōu)化算法中混合分布估計(jì)算法.

2.2.1 MIMIC算法

MIMIC算法,即輸入聚類(lèi)的最大互信息算法,最早由美國(guó)MIT人工智能實(shí)驗(yàn)室的de Bonet 等提出的一種基于雙變量相關(guān)模型的分布估計(jì)算法[12]．在MIMIC算法中,變量之間的關(guān)系可以用鏈?zhǔn)接邢驁D表示(圖2).

設(shè)決策變量集合x(chóng)=(x1,x2,…,xn)的聯(lián)合概率分布為p(x)=p(x1,x2,…,xn),且

p(x)=p(x1|x2,…,xn)p(x2|x3,…,xn)…p(xn-1|xn).

(5)

算法中解空間的概率模型可以描述為

xin)…pl(xin-1|xin),

(6)

其中π=(i1,i2,…,in)表示變量x1,x2,…,xn的一個(gè)排列,pl(xij|xij+1)表示第ij+1個(gè)變量取值為xij+1時(shí)第ij個(gè)變量取值為xij的條件概率.

(7)

其中:

對(duì)于優(yōu)化變量x=(x1,x2,…,xn),存在一個(gè)最優(yōu)排列π=(i1,i2,…,in)使得條件概率之積fπ(x)=f(xi1|xi2)…f(xin-1|xin)·f(xi1)與解存檔的概率分布f(x)之間的K-L距離達(dá)到最小.

2.3 RPCA

如果搜素空間的維數(shù)過(guò)高,會(huì)嚴(yán)重影響蟻群算法的性能,需要一種技術(shù)來(lái)降低解分量之間的冗余相關(guān)性．在連續(xù)域上的蟻群優(yōu)化算法和MIMIC算法中,候選解是根據(jù)高斯密度函數(shù)進(jìn)行采樣的,所以如果要對(duì)高維空間進(jìn)行降維處理,并且降低解分量之間的冗余相關(guān)性,最常使用的技術(shù)是主成分分析(PCA)技術(shù)[14],但由于PCA技術(shù)的魯棒性較差,在尋優(yōu)過(guò)程中容易出現(xiàn)停滯的狀況．所以本文選擇使用RPCA技術(shù),既可以降低解分量之間的冗余相關(guān)性,也可以保證蟻群系統(tǒng)的魯棒性.

RPCA(Robust PCA)[15]是在PCA基礎(chǔ)上加入一個(gè)可以測(cè)量在各個(gè)維度以?xún)?nèi)異常點(diǎn)的魯棒函數(shù),并且想辦法去除異常點(diǎn)和修正恢復(fù)主要結(jié)構(gòu)空間的一種方法．它很好地解決了傳統(tǒng)PCA在處理大誤差時(shí)不具有魯棒性的問(wèn)題.

2.3.1 RPCA模型

設(shè)新的解矩陣S′=B+E,其中B是低秩矩陣,E為稀疏(噪聲)矩陣[16]．RPCA模型解決的問(wèn)題是從帶有稀疏大噪聲的數(shù)據(jù)中精確地恢復(fù)出低秩矩陣．此模型可以表示為

min‖B‖*+λ‖E‖1, s.t.S′=B+E,

(8)

其中‖·‖1為矩陣的1范數(shù),‖·‖*為矩陣的和范數(shù),是需要恢復(fù)的低秩結(jié)構(gòu)矩陣，E是未知的噪聲矩陣，S′是包含噪聲的新的解矩陣.

2.3.2 RPCA模型求解[17]

對(duì)模型(8)構(gòu)建拉格朗日函數(shù)得:

Lμ(B,E,Z)=‖B‖*+λ‖E‖1+

(9)

迭代低秩矩陣B為

Dμ-1{S′-E+μ-1Z}，

(10)

迭代稀疏矩陣E為

Sλμ-1{S′-B+μ-1Z}，

(11)

其中矩陣Z是拉格朗日乘子,μ為一個(gè)正數(shù).

2.4混合蟻群優(yōu)化算法

蟻群算法在低維問(wèn)題中取得了較好的效果,具有較強(qiáng)的局部搜索能力,但對(duì)于大規(guī)模問(wèn)題全局優(yōu)化性能急劇下降,而MIMIC算法的全局尋優(yōu)能力強(qiáng),局部搜索能力較弱,RPCA可以恢復(fù)高維空間的低維結(jié)構(gòu)空間,并保持系統(tǒng)的魯棒性,所以在ACOR算法的整體框架下加入MIMIC分布估計(jì)算法和RPAC以提高算法的尋優(yōu)能力和效率．在ACOR算法中,決策變量分量之間相互獨(dú)立,未考慮解分量之間的相關(guān)性,導(dǎo)致抽樣效率不高,所以在混合蟻群算法中,建立初始解存檔之后,我們根據(jù)提出的有效相關(guān)性定義計(jì)算解存檔的有效相關(guān)性矩陣指導(dǎo)后續(xù)算法采樣．整個(gè)更新解存檔的具體步驟如下:

對(duì)于解存檔

(12)

根據(jù)定義式(3),計(jì)算解分量之間的有效相關(guān)性矩陣:

(13)

samsolkl=(sk1,…,samplei(s),…,slj,…,skn),

3)根據(jù)有效相關(guān)性矩陣,計(jì)算概率分布fπ(s)=f(si1|si2)f(si2|si3)…f(sin-1|sin)f(sin).

步驟4.對(duì)步驟3得到低秩結(jié)構(gòu)矩陣B的解分量進(jìn)行評(píng)估,并更新解的目標(biāo)函數(shù)值.

步驟5.將m條新的解所對(duì)應(yīng)的目標(biāo)函數(shù)值與原來(lái)的解存檔空間的k個(gè)解的目標(biāo)函數(shù)值重新進(jìn)行由優(yōu)至劣的順序排序,選取前k個(gè)解,作為新的解存檔.

3 數(shù)值實(shí)驗(yàn)

3.1 測(cè)試函數(shù)

為測(cè)試算法的性能,并與連續(xù)域上的蟻群優(yōu)化算法進(jìn)行比較,本文對(duì)下面6個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)進(jìn)行測(cè)試.

Sumcan函數(shù):

Sphere函數(shù):

Giewangk函數(shù):

Schwefel函數(shù):

Rastrigin函數(shù):

Easom函數(shù):

f(x)=-cos(x1)cos(x2)e-((x1-π)2+(x2-π)2),-100≤x1,x2≤100;minf(x)=f(π,π)=-1.

3.2 參數(shù)設(shè)置

在實(shí)驗(yàn)中,算法的參數(shù)設(shè)置如下:螞蟻個(gè)數(shù)m=50,保留最優(yōu)解個(gè)數(shù)k=10,最大迭代次數(shù)為50,精度為10-6,調(diào)試不同啟發(fā)因子q與信息素?fù)]發(fā)率τ,分別進(jìn)行10次實(shí)驗(yàn).

3.3 實(shí)驗(yàn)結(jié)果與分析

為測(cè)試混合蟻群優(yōu)化算法的性能,本文采用下列4種性能指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析,其中設(shè)定函數(shù)的維數(shù)n=10.

1)在固定最大迭代次數(shù)內(nèi)算法得到的最優(yōu)值及平均最優(yōu)值如表1所示．由表1知,混合ACOR算法對(duì)6個(gè)測(cè)試函數(shù)進(jìn)行10次實(shí)驗(yàn)后都可以很快地找到函數(shù)的最優(yōu)值,并且與函數(shù)實(shí)際理論的最優(yōu)值相同,說(shuō)明混合ACOR算法在固定的最大迭代次數(shù)內(nèi)能夠得到很好的優(yōu)化結(jié)果,算法是可行的．同時(shí),也可由表1看出,混合ACOR算法的最優(yōu)值和平均值都優(yōu)于原來(lái)的ACOR算法,這是由于混合ACOR算法考慮變量之間的相關(guān)性,結(jié)合全局尋優(yōu)能力強(qiáng)的MIMIC分布估計(jì)算法和RPCA技術(shù),降低了變量之間的冗余相關(guān)性和陷入局部最優(yōu)值的概率,收斂速度加快,在尋優(yōu)能力上有了很大的提高.

表1 50次迭代內(nèi)算法優(yōu)化結(jié)果Table 1 Optimization results of algorithms within 50 iterations

2)表2是混合ACOR算法與標(biāo)準(zhǔn)ACOR算法達(dá)到理論最優(yōu)值時(shí)的平均迭代次數(shù)的比較結(jié)果,其中Sumcan函數(shù)的最優(yōu)值為-105,Sphere、Giewangk、Schwefel和Rastrigin函數(shù)最優(yōu)值為0,Easom函數(shù)最優(yōu)值為-1,“50+”代表算法在50次迭代后仍未達(dá)到理論最優(yōu)值．由表2可以看出,對(duì)于6個(gè)測(cè)試函數(shù),混合ACOR算法的平均迭代次數(shù)遠(yuǎn)遠(yuǎn)優(yōu)于標(biāo)準(zhǔn)ACOR算法,平均迭代次數(shù)都很小,很快就達(dá)到了迭代次數(shù)少、收斂速度快的理想狀態(tài).

表2 到達(dá)理論最優(yōu)值的平均迭代次數(shù)Table 2 Average number of iterations reaching the theoretical optimal value

所有函數(shù)的標(biāo)準(zhǔn)ACOR算法在最大迭代次數(shù)內(nèi)沒(méi)有達(dá)到理論最優(yōu)值,部分函數(shù)后續(xù)迭代的最優(yōu)值都在某個(gè)值上停留,所以認(rèn)為算法很大可能已經(jīng)陷入局部最優(yōu)值．這說(shuō)明與標(biāo)準(zhǔn)ACOR算法相比,混合ACOR算法收斂速度非?？?陷入局部最優(yōu)解的概率非常小,基本能在最大迭代次數(shù)內(nèi)收斂到最優(yōu)值,大大減少收斂時(shí)的迭代次數(shù),提高了解更新效率.

3)達(dá)標(biāo)率指算法達(dá)到理論最優(yōu)值的次數(shù)與實(shí)驗(yàn)總次數(shù)的比例．表3給出了標(biāo)準(zhǔn)ACOR算法和混合ACOR算法達(dá)到理論最優(yōu)值時(shí)達(dá)標(biāo)率的比較結(jié)果．由表3可以看出,對(duì)于6個(gè)測(cè)試函數(shù),在混合ACOR算法中都成功找到了函數(shù)理論最優(yōu)值,達(dá)標(biāo)率為100%,即算法尋優(yōu)過(guò)程中,陷入局部最優(yōu)解的概率非常小;而標(biāo)準(zhǔn)的ACOR算法除了Easom函數(shù)在10次實(shí)驗(yàn)中9次達(dá)到最優(yōu)值,其他函數(shù)均未在固定迭代次數(shù)內(nèi)找到理論最優(yōu)值,達(dá)標(biāo)率為0,也就是說(shuō),標(biāo)準(zhǔn)的ACOR算法在固定迭代次數(shù)內(nèi),函數(shù)收斂于局部最優(yōu)值的概率較大,特別容易在尋優(yōu)過(guò)程中發(fā)生停滯的現(xiàn)象．混合ACOR算法的達(dá)標(biāo)率遠(yuǎn)遠(yuǎn)優(yōu)于標(biāo)準(zhǔn)ACOR算法的達(dá)標(biāo)率,這說(shuō)明混合ACOR算法有很高的有效性和可靠性.

表3 到達(dá)理論最優(yōu)值的次數(shù)與實(shí)驗(yàn)次數(shù)的比例Table 3 Ratio of the number of arrivals at the theoretical optimal value to the number of experiments %

圖3a—3f分別為6個(gè)函數(shù)的標(biāo)準(zhǔn)ACOR算法和混合ACOR算法在相同迭代次數(shù)下的函數(shù)值的仿真實(shí)驗(yàn)結(jié)果．從圖中可以很清晰地看出,與標(biāo)準(zhǔn)的ACOR算法相比,混合的ACOR算法可以在最初的幾次迭代中快速成功找到函數(shù)的理論最優(yōu)值,甚至如果選擇合適的參數(shù),對(duì)于部分函數(shù),算法在第一次迭代就能成功找到函數(shù)的全局最優(yōu)值,進(jìn)而快速收斂;相比之下,標(biāo)準(zhǔn)的ACOR算法在固定迭代次數(shù)內(nèi),全局尋優(yōu)能力和收斂速度上都不是很理想.

4)在迭代次數(shù)不變的條件下,改變函數(shù)維數(shù),比較兩種算法的尋優(yōu)性能(表4和表5)．下面是測(cè)試函數(shù)維數(shù)分別為10維和30維的情況下,標(biāo)準(zhǔn)ACOR算法和混合ACOR算法函數(shù)最優(yōu)值與平均值的比較,實(shí)驗(yàn)結(jié)果可以體現(xiàn)不同維數(shù)對(duì)兩種算法的影響．表4是不同維度下兩種算法最優(yōu)值的比較,表5是不同維度下兩種算法平均值的比較,其中本次實(shí)驗(yàn)的固定迭代次數(shù)為50次.

由表4和表5可以看出,隨著測(cè)試函數(shù)維數(shù)的增多,標(biāo)準(zhǔn)ACOR算法尋找最優(yōu)值的能力在減弱,但是混合ACOR算法并沒(méi)有表現(xiàn)出明顯的尋優(yōu)能力下降的趨勢(shì),不管是30維還是10維,混合ACOR算法在實(shí)驗(yàn)中得出的最優(yōu)值和平均值都比標(biāo)準(zhǔn)的ACOR算法要好得多,且維數(shù)越高,優(yōu)勢(shì)越明顯．這是由于當(dāng)函數(shù)維數(shù)增大時(shí),混合ACOR算法考慮了變量之間的相關(guān)性,并且利用RPCA技術(shù)盡可能精確地保留有效相關(guān)系數(shù)大的解分量,去除大的異常解分量和冗余的解分量,所以,雖然函數(shù)維數(shù)增大,但是最終得到的對(duì)函數(shù)值起主要作用的解分量并沒(méi)有增加,反而因?yàn)榫S數(shù)的增加,優(yōu)化了搜索空間,可以更容易找到全局最優(yōu)值的搜索鄰域,從而提高算法的尋優(yōu)性能.

表4 不同維度下兩種算法最優(yōu)值的比較Table 4 Comparison of optimal values between the two algorithms under different dimensions

表5 不同維度下兩種算法平均值的比較Table 5 Comparison of the average values between the two algorithms under different dimensions

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

本文針對(duì)標(biāo)準(zhǔn)的ACOR算法存在的不足,考慮算法中決策變量之間的相關(guān)性,根據(jù)變量有效相關(guān)性的定義,提出一種基于MIMIC算法和RPCA的混合蟻群算法．經(jīng)仿真實(shí)驗(yàn)結(jié)果驗(yàn)證,與標(biāo)準(zhǔn)ACOR算法相比,混合ACOR算法可以十分精確地找到最優(yōu)值,且到達(dá)理論最優(yōu)值時(shí)的迭代次數(shù)和達(dá)標(biāo)率都遠(yuǎn)遠(yuǎn)優(yōu)于標(biāo)準(zhǔn)算法．混合蟻群優(yōu)化算法有MIMIC算法全局搜索能力強(qiáng)的優(yōu)點(diǎn),又包含蟻群算法的局部求精能力強(qiáng)、收斂速度快的優(yōu)點(diǎn);對(duì)于高維空間上的尋優(yōu)過(guò)程,由于混合ACOR算法加入RPCA技術(shù),在保證變量之間的有效相關(guān)性和系統(tǒng)魯棒性的同時(shí),保留主要解空間結(jié)構(gòu),降低計(jì)算復(fù)雜度與解變量之間的冗余相關(guān)性,優(yōu)化搜索空間,使得該算法在解決高維優(yōu)化問(wèn)題時(shí)仍具有很強(qiáng)的尋優(yōu)能力.