涂維維,葛洪偉,楊金龍,袁運浩

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇無錫214211)

基于M-H采樣的快速反向微分進(jìn)化算法

涂維維,葛洪偉,楊金龍,袁運浩

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇無錫214211)

反向微分進(jìn)化(ODE)算法基于反向優(yōu)化對種群進(jìn)行初始化更新以保持種群多樣性。但該算法中反向個體容易偏離全局最優(yōu)個體,不能很快達(dá)到全局最優(yōu),在函數(shù)優(yōu)化過程中收斂速度慢且容易陷入局部最優(yōu)。為此,提出一種基于M-H采樣的快速反向微分進(jìn)化算法。M-H采樣用于ODE算法的變異操作,滿足馬爾可夫鏈可逆條件。馬爾可夫鏈的一步轉(zhuǎn)移概率根據(jù)個體等級分配的選擇概率進(jìn)行計算,既能選擇最優(yōu)個體,又能尋找優(yōu)化方向并保持種群多樣性。仿真結(jié)果表明,M-H采樣得到的個體具有馬爾可夫鏈平穩(wěn)分布特性,該算法在單峰函數(shù)和多峰函數(shù)優(yōu)化中都能快速收斂,全局和局部搜索性能達(dá)到平衡,具有較高的搜索精度及較好的魯棒性。

微分進(jìn)化算法;反向微分進(jìn)化算法;轉(zhuǎn)移概率;平穩(wěn)分布;馬爾可夫鏈蒙特卡洛;反向?qū)W習(xí)

1 概述

進(jìn)化算法是一種模擬生物進(jìn)化過程求解優(yōu)化問題的啟發(fā)式自適應(yīng)人工智能技術(shù)。1995年Storn和Price等人提出微分進(jìn)化(Differential Evolution, DE)［1-2］算法,其主要特點是算法簡單、收斂速度快、可調(diào)參數(shù)少、魯棒性好,相對于其他優(yōu)化算法有較強(qiáng)的全局收斂能力和穩(wěn)定性。變異操作是微分進(jìn)化的核心操作,對微分進(jìn)化的影響很大,文獻(xiàn)［3］是關(guān)于微分進(jìn)化算法的參數(shù)和變異策略的綜述和應(yīng)用。近年來DE成功應(yīng)用于不同領(lǐng)域,如:工程優(yōu)化設(shè)計,數(shù)字濾波器設(shè)計,圖像處理,數(shù)據(jù)挖掘,多傳感器融合等。但是微分進(jìn)化算法在高維多峰函數(shù)優(yōu)化中容易陷入局部最優(yōu),收斂速度慢、優(yōu)化性能不穩(wěn)定。針對DE算法的缺陷,許多學(xué)者提出了很多改進(jìn)方法,如文獻(xiàn)［4］采用自適應(yīng)控制參數(shù)來提高微分進(jìn)化算法的收斂性能,但是收斂速度依然較慢;文獻(xiàn)［5］在文獻(xiàn)［4］的基礎(chǔ)上增加了種群規(guī)模減少機(jī)制和3個變異策略,改善收斂速度和DE算法的魯棒性,但是算法性能不穩(wěn)定,易于陷入局部最優(yōu);文獻(xiàn)［6］引入基于排序的變異,將種群個體進(jìn)行適應(yīng)度排序后,進(jìn)行迭代更新,維持局部搜索和全局搜索的平衡;文獻(xiàn)［7］將種群分成多個子群,動態(tài)調(diào)整每個子種群的個體數(shù)目,增加子種群間個體信息交換,并且采用局部搜索和自適應(yīng)方法,然而該算法參數(shù)較多,選擇困難,且常由于參數(shù)選擇不當(dāng)導(dǎo)致性能不穩(wěn)定;文獻(xiàn)［8］提出一種分階段的二次變異,提高算法的全局搜索能力,但增加了時間復(fù)雜度;文獻(xiàn)［9］采用鄰域變異方法,在某個設(shè)定的領(lǐng)域內(nèi)取得變異的個體,這種方法易于陷入局部最優(yōu);文獻(xiàn)［10］通過求反向種群來保持種群多樣性,但是反向個體容易偏離全局最優(yōu)個體,更新速率較慢,不能很快地達(dá)到全局最優(yōu)。

本文采用馬爾可夫鏈蒙特卡洛(Markov Chain Monte Carlo,MCMC)思想,提出基于 Metropolis-Hastings(M-H)采樣的算法用于反向微分進(jìn)化(Opposition Differential Evolution,ODE)［10］算法(MHODE)的變異操作。M-H算法具有馬爾可夫鏈的平穩(wěn)性,所采樣的個體具有平穩(wěn)分布的特性,根據(jù)該采樣進(jìn)行變異操作,能使M-HODE算法的收斂速度加快,收斂趨于平穩(wěn)。

2 微分進(jìn)化和反向微分進(jìn)化算法

2.1 微分進(jìn)化算法

圖1 DE算法流程

微分進(jìn)化算法流程:

(1)初始化種群

在決策空間X內(nèi),用式(1)隨機(jī)產(chǎn)生初始向量:

(2)變異操作

微分進(jìn)化算法的差分向量與縮放因子相乘后跟基向量進(jìn)行向量合成,一般采用DE/rand/1變異策略,變異操作的公式為:

(3)交叉操作

對變異產(chǎn)生的新個體和當(dāng)前個體進(jìn)行交叉操作,以增加種群個體的多樣性。經(jīng)過交叉操作得到實驗向量:

其交叉操作公式如下:

其中,j=1,2,…,D;CR∈［0,1］為交叉概率;jrand∈［1,D］為均勻選取的隨機(jī)整數(shù)。

(4)選擇操作

DE算法通過選擇操作,對實驗個體和當(dāng)前個體進(jìn)行適應(yīng)度評價,根據(jù)式(4)決定候選個體是否取代當(dāng)前個體。

2.2 反向微分進(jìn)化算法

2.2.1 反向?qū)W習(xí)理論

反向微分進(jìn)化算法是基于反向?qū)W習(xí)(Oppositionbased Learning,OBL)理論的微分進(jìn)化算法。OBL理論思想如下:

定義1(反向個體) 在多維空間R,p=(x1,x2,…,xD)是D維空間的一個個體,x1,x2,…,xD∈R,xi∈［a,b］?i∈{1,2,…,D},式(5)求反向個體=。

2.2.2 ODE算法步驟

ODE算法步驟具體如下:

步驟1 基于反向?qū)W習(xí)的種群初始化。

(1)隨機(jī)產(chǎn)生均勻分布的種群Po,大小為NP。

(2)用定義1中的式(5)來計算Po中每一個個體的反向個體opoi,j=aj+bj-poi,j,使用反向優(yōu)化方法從集合{po,Opo}中選NP個適應(yīng)度最好的個體作為初始種群。

步驟2 根據(jù)迭代條件,對種群個體進(jìn)行微分進(jìn)化算法的變異、交叉、選擇操作。

步驟3 隨機(jī)反向代跳操作,若隨機(jī)的rand(0, 1)＜Jr(Jr是跳轉(zhuǎn)概率),MINPj和MAXP

j分別是當(dāng)前種群P的區(qū)間最小和最大值,用式(6)求出反向個體,然后從集合{P,OP}選擇Np個最優(yōu)個體作為當(dāng)前代種群P。

opi,j=MINpj+MAXp

j-pi,j(6)

步驟4 判斷是否達(dá)到迭代終止條件,否則轉(zhuǎn)向步驟2。

3 基于M-H采樣的反向微分進(jìn)化算法

3.1 M-H采樣方法

3.1.1 馬爾可夫鏈基本思想

M-H算法是出現(xiàn)較早一般化的馬爾可夫鏈蒙特卡洛［11-12］采樣方法,下面先介紹馬爾可夫鏈(Markov Chain)。

定義3(馬爾可夫鏈) 假定隨機(jī)序列{X0,X1,…}滿足馬爾可夫性,即在任意時刻t≥0時,序列中某時刻t+1的狀態(tài)Xt+1由條件分布p(Xt+1|Xt)產(chǎn)生,它只依賴時刻t的狀態(tài),與之前的狀態(tài){X0,X1,…,Xt-1}無關(guān),這樣的一個隨機(jī)序列被稱為馬爾可夫鏈,馬爾可夫鏈的轉(zhuǎn)移核表示如下:

p(x,x′)=p(x→x′)=p(xt+1=x′|xt=x) (7)

定義4(馬爾可夫鏈可逆) 若π(dx)P(x,dy)= π(dy)p(y,dx),x,y∈X則狀態(tài)空間X上的馬爾可夫鏈關(guān)于π(·)可逆。

定義5(平穩(wěn)分布) 設(shè)πj(t)=π{X(t)=j},j∈X,如果關(guān)于π(x)可逆的馬爾可夫鏈{X(t),t≥0}滿足: πj=lim

t→∞πj(t),j∈X,則稱π(x)為該馬爾可夫鏈的平穩(wěn)分布,平穩(wěn)分布馬爾科夫鏈的狀態(tài)轉(zhuǎn)移與初始值狀態(tài)無關(guān),只與時間間隔有關(guān)。

3.1.2 M-H采樣思想

MCMC［13-14］基本原理是建立一個平穩(wěn)分布,采樣得到的馬爾可夫鏈樣本是一個π(x)樣本,其基本步驟可概括為:

(1)構(gòu)造馬爾可夫鏈,在空間X的樣本上選擇一個合適的馬爾可夫鏈,轉(zhuǎn)移核設(shè)為p(*,*),使其收斂到平穩(wěn)分布π(x)。

(2)樣本提取過程:由空間X的某一點出發(fā)X0,用步驟(1)構(gòu)造的馬爾可夫鏈進(jìn)行抽樣模擬,產(chǎn)生序列X1,X2,…,Xn。

(3)蒙特卡洛積分:對任意整數(shù)m和任意足夠大的整數(shù)n,任一個目標(biāo)函數(shù)的f(x)期望估計為: f(x(t)) (8)

M-H方法最早由Metropolis等人提出,之后由Hastings加以推廣,形成Metropolis-Hastings方法。

原理如下:假設(shè)馬爾可夫鏈第t個時刻的狀態(tài)為xt,π(x)是求解問題的目標(biāo)分布,W(x,xt)是對稱的轉(zhuǎn)移函數(shù)。Metropolis-Hasting算法通過以下2步得到t+1時刻的狀態(tài):

(1)從轉(zhuǎn)移分布W(x,x′)中得到x′,這里W(x, x′)是對稱的概率轉(zhuǎn)移函數(shù),即W(x,x′)=W(x′,x)。

(2)取隨機(jī)數(shù)U,使U服從(0,1)均勻隨機(jī)分布,令r=min(1,π(x′)W(x′,x) π(x)W(x,x′) E［f(x)］= 1 n-m

n

t=m+1

∑

),如果U≤r,則令xt+1=x′;否則令xt+1=x。

3.2 M-HODE算法描述

微分進(jìn)化算法中最核心的操作是變異操作,MHODE算法提出一種,將Metropolis-Hastings采樣方法用于ODE的變異操作,M-HODE在初始化種群后求反向種群,合并初始種群和反向種群并計算每個種群的適應(yīng)度值,根據(jù)適應(yīng)度值大小進(jìn)行升序排列,選取前NP個個體作為初始種群。在變異操作中用M-H采樣方法選擇基向量和差分向量,采樣個體組成的馬爾可夫鏈滿足馬爾可夫平穩(wěn)分布。在進(jìn)行變異,交叉,選擇操作后,隨機(jī)的進(jìn)行反向種群更新,保持了種群的多樣性,利于 M-HODE算法的全部優(yōu)化。

3.3 M-HODE算法步驟

M-HODE算法步驟具體如下:

步驟1 隨機(jī)產(chǎn)生均勻分布的種群P0,種群大小為NP,用式(5)計算得到種群個體的反向個體opoi,j=aj+bj-poi,j。從集合 P0,OP0),則可得r=min(1, π(x′) π(x) { }中選NP個個體作為初始種群。

步驟2 將種群里所有個體的按適應(yīng)度值進(jìn)行升序排列,計算排列后每一個個體的等級 Ri,公式為:

Ri=Np-i,i=1,2,…,Np (9)

步驟3 對每個向量個體進(jìn)行等級分配后,計算每個個體的選擇概率,這里用到已提出的平方模型式(10)［15］,向量xi的選擇概率計算公式為:

pi= RiNp ,i=1,2,…,Np (10)

步驟4 使用Metropolis-Hastings算法進(jìn)行抽樣參加變異操作的個體。以DE/rand/1策略作為實例,選取xr0,xr1,xr2,xr3為馬爾可夫鏈。

M-H采樣方法具體如下:

(1)當(dāng)rand(0,1)＞pr0且r0≠i條件滿足時,隨機(jī)選擇r0∈{1,Np}。/*xr0作為馬爾可夫鏈的初始

■■

2

■■向量*/

(3)如果U≤r,則x1=xr1,否則x1=xr0。/*選取x1為基向量*/

(5)如果U≤r,則x2=xr2,否則x2=xr1并且x1=xr2。/*x2作為差分向量*/

(6)r3≠r1、r3≠r0和r3≠i條件滿足時隨機(jī)選取r3∈{1,NP}。/*隨機(jī)選取x3*/

步驟5 當(dāng)函數(shù)評價次數(shù)小于最大評價次數(shù)以及迭代次數(shù)小于最大迭代次數(shù)2個條件滿足時,進(jìn)行差分進(jìn)化算法的變異、交叉、選擇操作得到種群P。

步驟6 隨機(jī)反向代跳操作:如果跳轉(zhuǎn)概率Jr大于(0,1)間的一個隨機(jī)數(shù),那么根據(jù)式(6)求出種群P的反向種群OP,然后從集合{P,OP}中選擇NP個個體作為當(dāng)前代種群P。

步驟7 重復(fù)迭代到算法停止迭代的條件為止。

4 仿真實驗與結(jié)果分析

為測試M-HODE算法的有效性和正確性,這里用11個常用的標(biāo)準(zhǔn)測試函數(shù)進(jìn)行仿真評價,將MHODE,DE,JDE及ODE算法進(jìn)行比較。這11個測試函數(shù)中既有高維單峰也有高維多峰函數(shù)。其中,f4,f5,f73個函數(shù)是特殊維數(shù),分別是10維、2維、2維,其他函數(shù)均是30維,另外,f6是一個噪聲函數(shù)。測試函數(shù)的部分參數(shù)設(shè)置如表1所示。f5的最優(yōu)值fmin=-1,其他函數(shù)的最優(yōu)值fmin都為0。

本文實驗仿真環(huán)境為Matlab2012,運行于Intel (R)Pentium(R)4,CPU 2.93 GHz,1 GB內(nèi)存的聯(lián)想臺式電腦。仿真時設(shè)置最大迭代次數(shù)MAXIter= 1 000,函數(shù)適應(yīng)度最大評價次數(shù)Max_NFFES= 10 000×D,縮放因子和交叉概率初始值分別設(shè)置為F=0.5和CR=0.8,反向操作的跳轉(zhuǎn)概率Jr按照ODE算法的Jr取一樣值。為驗證該算法的精確性,將每個算法獨立運行50次,取50次實驗結(jié)果的平均值和標(biāo)準(zhǔn)方差作為評價算法的主要性能指標(biāo),為驗證算法的快速收斂,在實驗條件的基礎(chǔ)上加上目標(biāo)值VTR=1.0E-10的條件,計算50次所用平均時間。

表1 測試函數(shù)及相關(guān)參數(shù)

表2是DE,JDE,ODE及M-HODE算法的實驗結(jié)果,加粗?jǐn)?shù)據(jù)表示最優(yōu)值。統(tǒng)計表2中的測試函數(shù)數(shù)據(jù),f0～f4這5個高維單峰函數(shù)中有4個函數(shù)M-HODE均值優(yōu)于DE,JDE,ODE算法;2維函數(shù)f5的實驗結(jié)果都是一樣的,針對噪聲函數(shù)f6,M-HODE方差比其他3個算法方差更小,說明M-HODE具有更好的抗噪性;多峰函數(shù)f7～f10中有3個函數(shù) MHODE均值優(yōu)于DE,JDE,ODE算法,M-HODE方差比其他3個算法較小,該優(yōu)越性歸功于M-HODE算法中M-H采樣的平穩(wěn)性?？梢?針對一些高維多峰函數(shù)優(yōu)化,M-HODE具有明顯優(yōu)勢。

圖2～圖4給出了f1,f2和f103個具有典型高維測試函數(shù)的迭代曲線,迭代次數(shù)為1 000次,按一定比例用線條標(biāo)出,從圖2～圖4可以看出,M-HODE算法、DE算法、JDE算法、ODE算法曲線趨勢相似,但是M-HODE算法有更快的收斂速度和更優(yōu)的精度。圖4對于f10函數(shù),M-HODE算法表現(xiàn)出更加明顯的收斂速度和收斂精度。這歸功于M-HODE采樣方法的穩(wěn)定性和反向進(jìn)化的種群多樣性,促進(jìn)了算法的快速收斂。針對其余的測試函數(shù),實驗也獲得了相似的進(jìn)化曲線。

表2 DE,JDE,ODE,M-HODE算法均值和方差

圖2 f1函數(shù)迭代曲線

圖3 f2函數(shù)迭代曲線

圖4f10函數(shù)迭代曲線

圖5是DE,JDE,ODE和M-HODE算法運行時間比較,仿真設(shè)置為VTR=1.0E-10,最大迭代次數(shù)MaxIter=1 000,函數(shù)適應(yīng)度最大評價次數(shù)Max_NFFES=10 000D。從圖5可以看出,在運行時間上M-HODE優(yōu)于DE,JDE,ODE這3個算法,針對有些函數(shù)M-HODE算法所用迭代時間甚至可以快到上百倍。M-H采樣很大程度上不僅可以提高差微分進(jìn)化函數(shù)的優(yōu)化精度,而且可以加快函數(shù)優(yōu)化的收斂速度,使優(yōu)化很快趨于平穩(wěn),并減少時間復(fù)雜度。

圖5 算法運行時間比較

5 結(jié)束語

本文提出一種基于M-H采樣的快速反向微分進(jìn)化算法,將M-H采樣策略用于反向微分進(jìn)化算法中,M-H采樣個體組成平穩(wěn)分布的馬爾可夫鏈,能改進(jìn)ODE算法的變異操作。通過對11個典型的Benchmark函數(shù)進(jìn)行測試,結(jié)果表明,M-HODE算法不僅在高維單峰函數(shù)和高維多峰函數(shù)優(yōu)化中具有較高的精度,而且M-H采樣能加快M-HODE算法的收斂速度,避免陷入局部最優(yōu),從而實現(xiàn)M-H快速反向微分進(jìn)化算法。

［1］ Storn R,Price K.Differential Evolution——A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces［R］.Berkley,USA:ICSI,Technical Report:TR-95-012,1995.

［2］ Storn R,Price K.Differential Evolution——A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces［J］.Journal of Global Optimization,1997,11(4): 341-359.

［3］ Mallipeddi R,Suganthan P N,Pan Q K,etal.Differential Evolution Algorithm With Ensembleof Parameters and Mutate on Strategies［J］.Applied Soft Computing,2011,11(2):1679-1696.

［4］ Brest J,Greiner S,Boskovic B,et al.Self-adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems［J］.IEEE Transactions on Evolutionary Computation, 2006,10(6):646-657.

［5］ Brest J,Maucec M S.Self-adaptive Differential Evolution Algorithm Using Population Size Reduction and Three Stragies［J］.Soft Computing,2011,15(11):2157-2174.

［6］ Gong Wenyin,Cai Zhihua.Differential Evolution with Ranking-based Mutation Operators［J］.IEEE Transactions on Evolutionary Computation,2013,43(6):1-16.

［7］ 張雪霞,陳維榮,戴朝華.帶局部搜索的動態(tài)多群體自適應(yīng)差分進(jìn)化算法及函數(shù)優(yōu)化［J］.電子學(xué)報,2010, 38(8):1825-1830.

［8］ 王筱珍,李 鵬,俞國燕.分階段二次變異的多目標(biāo)混沌差分進(jìn)化算法［J］.控制與決策,2011,26(3):457-463.

［9］ Qu B Y,Suganthan P N,Liang J J.Differential Evolution with Neighborhood Mutation for Multimodal Optimization［J］.IEEE Transactions on Evolutionary Computation,2012,16(5):601-614.

［10］ Rahnamayan S,Tizhoosh H R,Salama M M A.Oppositionbased Differential Evolution［J］.IEEE Transactions on Evolutionary Computation,2008,12(1):64-79.

［11］ Karandikar R L.On the Markov Chain Monte Carlo (MCMC)Method［J］.Sadhana,2006,31(2):81-104.

［12］ Gallagher K,Charvin K,Nielsen S,et al.Markov Chain Monte Carlo(MCMC)Sampling Methods to Determine Optimal Models,Model Resolution and Model Choice for Earth Science Problems［J］.Marine and Petroleum Geology,2009,26(4):525-535.

［13］ Chen Peide.Hasting-metropolis Algorithms and Reference Measures［J］.Elsevier Statistics&Probability Letters,1998, 38(4):323-328.

［14］ Eidsvik J,Tjelmeland H.On Directional Metropolis——Hastings Algorithms［J］.Statistics and Computing, 2006,16(1):93-106.

［15］ Kalelo P,Ali M M.Differential Evolution Algorithm Using Hybrid Mutation［J］.Computational Optimization and Application,2007,37(2):231-246.

編輯 陸燕菲

Fast Opposition Differential Evolution Algorithm Based on M-H Sampling

TU Weiwei,GE Hongwei,YANG Jinlong,YUAN Yunhao
(School of IOT Engineering,Jiangnan University,Wuxi 214211,China)

In Differential Evolution(DE)algorithm,the population initialization is updated by using opposition optimization rule,so as to maintain the population diversity.However,the reverse individuals are easy to deviate from the global optimal solution,has slow convergence speed and easy to fall into local optimum in function optimization.This paper proposes a fast Opposition Differential Evolution(ODE)algorithm based on M-H(Metropolis-Hastings)sampling method.M-H sampling is used in the mutation operation of ODE.M-H sampling satisfies Markov Chain reversible conditions.One step transition probability of Markov Chain is calculated according to the selecting probability of individual ranking-assignment,not only chooses the best individual,but also searches for the optimal direction and keeps the population diversity.Simulation results show these individuals from M-H sampling have Markov stationary distribution property.The algorithm can accelerate the speed of convergence in unimodal functions and multimodal functions,balance the performance of global searching and local searching,and has higher precision and better robustness.

Differential Evolution(DE)algorithm;Opposition Differential Evolution(ODE)algorithm;transition probability;stationary distribution;Markov Chain Monte Carlo(MCMC);Opposition-based Learning(OBL)

1000-3428(2014)11-0155-05

A

TP301.6

10.3969/j.issn.1000-3428.2014.11.031

國家自然科學(xué)基金資助項目(61305017);江蘇省自然科學(xué)基金資助項目(BK20130154);江蘇高校優(yōu)勢學(xué)科建設(shè)工程基金資助項目。

涂維維(1987-),女,碩士研究生,主研方向:微分進(jìn)化,人工智能,模式識別;葛洪偉,教授、博士;楊金龍、袁運浩,副教授、博士。

2013-12-13

2014-01-13E-mail:tuweiweier@163.com

中文引用格式:涂維維,葛洪偉,楊金龍,等.基于M-H采樣的快速反向微分進(jìn)化算法［J］.計算機(jī)工程,2014,40(11): 155-159.

英文引用格式:Tu Weiwei,Ge Hongwei,Yang Jinlong,et al.Fast Opposition Differential Evolution Algorithm Based on M-H Sampling［J］.Computer Engineering,2014,40(11):155-159.