基于M-H采樣的快速反向微分進化算法

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

(江南大學物聯網工程學院,江蘇無錫214211)

基于M-H采樣的快速反向微分進化算法

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

(江南大學物聯網工程學院,江蘇無錫214211)

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

微分進化算法;反向微分進化算法;轉移概率;平穩分布;馬爾可夫鏈蒙特卡洛;反向學習

1 概述

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

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

2 微分進化和反向微分進化算法

2.1 微分進化算法

圖1 DE算法流程

微分進化算法流程:

(1)初始化種群

在決策空間X內,用式(1)隨機產生初始向量:

(2)變異操作

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

(3)交叉操作

對變異產生的新個體和當前個體進行交叉操作,以增加種群個體的多樣性。經過交叉操作得到實驗向量:

其交叉操作公式如下:

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

(4)選擇操作

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

2.2 反向微分進化算法

2.2.1 反向學習理論

反向微分進化算法是基于反向學習(Oppositionbased Learning,OBL)理論的微分進化算法。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 基于反向學習的種群初始化。

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

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

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

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

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

opi,j=MINpj+MAXp

j-pi,j(6)

步驟4 判斷是否達到迭代終止條件,否則轉向步驟2。

3 基于M-H采樣的反向微分進化算法

3.1 M-H采樣方法

3.1.1 馬爾可夫鏈基本思想

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

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

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則狀態空間X上的馬爾可夫鏈關于π(·)可逆。

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

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

3.1.2 M-H采樣思想

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

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

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

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

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

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

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

(2)取隨機數U,使U服從(0,1)均勻隨機分布,令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算法描述

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

3.3 M-HODE算法步驟

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

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

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

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

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

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

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

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

(1)當rand(0,1)＞pr0且r0≠i條件滿足時,隨機選擇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條件滿足時隨機選取r3∈{1,NP}。/*隨機選取x3*/

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

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

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

4 仿真實驗與結果分析

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

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

表1 測試函數及相關參數

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

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

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

圖2 f1函數迭代曲線

圖3 f2函數迭代曲線

圖4f10函數迭代曲線

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

圖5 算法運行時間比較

5 結束語

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

［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］ 張雪霞,陳維榮,戴朝華.帶局部搜索的動態多群體自適應差分進化算法及函數優化［J］.電子學報,2010, 38(8):1825-1830.

［8］ 王筱珍,李 鵬,俞國燕.分階段二次變異的多目標混沌差分進化算法［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

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

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

2013-12-13

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

中文引用格式:涂維維,葛洪偉,楊金龍,等.基于M-H采樣的快速反向微分進化算法［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.