魏文紅，周建龍，陶　銘，袁華強

(1．東莞理工學院計算機學院，廣東東莞523808; 2．西安交通大學城市學院計算機系，陜西西安，710018)

?

一種基于反向?qū)W習的約束差分進化算法

魏文紅1，周建龍2，陶銘1，袁華強1

(1．東莞理工學院計算機學院，廣東東莞523808; 2．西安交通大學城市學院計算機系，陜西西安，710018)

摘要:差分進化算法是一種結(jié)構(gòu)簡單、易用且魯棒性強的全局搜索啟發(fā)式優(yōu)化算法，它可以結(jié)合約束處理技術(shù)來解決約束優(yōu)化問題．機器學習在進化算法中，經(jīng)?？梢砸龑ХN群的進化，而且被廣泛地應(yīng)用于無約束的差分進化算法中，但對于約束差分進化算法卻很少有應(yīng)用．針對這一情況，提出了一種基于反向?qū)W習的約束差分進化算法框架．該算法框架采用基于反向?qū)W習的機器學習方法，提高約束差分進化算法的多樣性和加速全局收斂速度．最后把該算法框架植入了兩個著名的約束差分進化算法: (μ+λ) -CDE和ECHT，并采用CEC 2010的18個Benchmark函數(shù)進行了實驗評估，實驗結(jié)果表明:與(μ+λ) -CDE和ECHT相比，植入后的算法具有更強的全局搜索能力、更快的收斂速度和更高的收斂精度．

關(guān)鍵詞:反向?qū)W習;差分進化;約束優(yōu)化;收斂性

1　引言

優(yōu)化問題(Optimization Problem，OP)一直都是人工智能領(lǐng)域研究的熱點，起初人們一直研究著無約束的優(yōu)化算法．但實際上許多的科學和工程問題都存在著各種各樣的約束條件，這就導致了人們加強了對約束優(yōu)化問題(Constrained Optimization Problem，COP)的研究［1］．在一般的進化算法(Evolution Algorithm，EA)中，約束條件的出現(xiàn)，會導致可行解區(qū)域減小并使得搜索解的過程變得更為復(fù)雜．雖然約束優(yōu)化問題復(fù)雜，但人們還是成功地在無約束優(yōu)化算法中加入約束處理機制來解決約束優(yōu)化問題．

差分進化算法(Differential Evolution，DE)是由Storn和Price提出的一種功能強大、結(jié)構(gòu)簡單、易用且魯棒性強的全局優(yōu)化算法［2］，該算法已經(jīng)被成功地用于各種不同的應(yīng)用領(lǐng)域．加入約束處理機制的差分進化算法可以解決約束優(yōu)化問題，如Storn［3］提出的約束適應(yīng)性差分進化算法(CADE)，它是一種多成員的差分進化算法; Lampinen［4］提出了一種基于帕雷托占優(yōu)約束處理技術(shù)的差分進化算法; Mezura-Montes等人［5］提出了一種基于多成員多樣性的差分進化算法(MMDE)，該算法允許每一個父輩可以產(chǎn)生多個子代; Wang等人［6］提出了(μ+λ) -CDE算法，該算法通過μ個種群產(chǎn)生λ個子代，然后把(μ+λ)個種群一起進行迭代; Mallipeddi等人［7］提出了一種合并多個約束處理技術(shù)的ECHT-DE算法;在CEC 2006［8］競賽中，基于ε約束處理技術(shù)的εDE算法獲得了第一名［9］．大多數(shù)的約束差分進化算法雖然在一定程度上解決了約束優(yōu)化問題，但它們卻存在容易過早收斂而陷入局部最優(yōu)且收斂速度較慢的缺點［10］．

機器學習(Machine Learning)在進化算法中起著重要的作用［11］，由于進化算法在迭代搜索過程中需要存儲搜索空間、問題特征和種群信息等大量的數(shù)據(jù)，因此機器學習方法可以分析這些數(shù)據(jù)的特征來提高搜索性能．即在全局優(yōu)化過程中，提取有用的信息來理解搜索行為，用以指導下一步的搜索方向．在許多應(yīng)用領(lǐng)域，引入機器學習方法的進化算法在收斂速度和問題求解精度方面都有所提高［11］．

基于反向?qū)W習(Opposition-based Learning，OBL)的機器學習方法是由Tizhoosh［12］首次提出的，該方法為了獲得更優(yōu)的解來進行下一代迭代，在每次迭代過程中，不僅要評價本次搜索到的最優(yōu)解，而且還要評價與該最優(yōu)解處于相反方向的解，然后得出最終的最優(yōu)解，用來進行下一次迭代．最近基于反向?qū)W習的機器學習方法被廣泛用于一些啟發(fā)式進化算法如差分進化、粒子群、人工神經(jīng)網(wǎng)絡(luò)、蟻群和人工蜜蜂算法等［13］．Rahnamayan等人［14］首次提出了基于反向?qū)W習的差分進化算法，在該算法中，采用基于反向?qū)W習的機制來初始化種群．接下來的幾年里，包括Rahnamayan自己在內(nèi)的許多專家學者，分別提出了改進的基于反向?qū)W習的差分進化算法［15～19］．Ahandani等人［15］利用基于反向?qū)W習策略提出了交換的差分進化算法(SDE) ; Omran［16］結(jié)合混沌搜索、基于反向?qū)W習、差分進化和量子機制提出了CODEQ算法; Miao等人［17］提出了一種自適應(yīng)的基于反向?qū)W習的差分進化算法(SAODE) ;最近Wang等人［18］推廣了基于反向?qū)W習的機制，提出了一種基于推廣反向?qū)W習的差分進化算法(GODE)．所有這些基于反向?qū)W習的差分進化算法都是處理無約束優(yōu)化問題的，然而對于基于反向?qū)W習的約束差分進化算法卻少見報道，目前Omran提出的CODEQ算法可以處理一些簡單的約束優(yōu)化問題［19］，然而該算法針對CEC 2006［8］中的24 個Benchmark函數(shù)只測試了5個約束函數(shù)，不能夠說明該算法具有很強的優(yōu)勢．在這種背景下，本文提出了一種基于反向?qū)W習的約束差分進化算法框架(OBLCDE)，并且把OBL-CDE植入到兩個著名的約束差分進化算法(μ+λ) -CDE和ECHT-DE中，針對CEC 2010［20］中的18個Benchmark函數(shù)全部進行了實驗測試．測試結(jié)果顯示，與(μ+λ) -CDE和ECHT-DE算法相比，我們的算法具有更強的全局搜索能力、更快的收斂速度和更高的收斂精度．

雖然OBL-CDE與CODEQ都是基于反向?qū)W習的約束差分進化算法，但OBL-CDE與CODEQ仍然存在本質(zhì)的區(qū)別: (1) CODEQ是一種具體的算法，OBL-CDE是一種算法框架．OBL-CDE可以植入其它的一些具體的約束差分進化算法中，而CODEQ卻不能; (2) CODEQ將混沌搜索、基于反向?qū)W習、差分進化和量子機制集于一體，使得算法結(jié)構(gòu)變得復(fù)雜;而OBL-CDE只包含了基于反向?qū)W習的機制，并不改變差分進化算法的主體結(jié)構(gòu)，因此算法結(jié)構(gòu)簡單，運算速度快; (3) CODEQ只測試了CEC 2006中24個Benchmark函數(shù)的5個，顯然不能證明該算法具有很強的優(yōu)勢，而OBL-CDE測試了CEC 2010中全部的Benchmark函數(shù)，并通過各種實驗比較說明了OBL-CDE的優(yōu)勢．

2　相關(guān)背景知識

2.1約束優(yōu)化問題

在約束優(yōu)化問題中，不但包括等式約束條件和不等式約束條件，還包括向量x的上界和下界，具體如下:

其中x = (x1，x2，…，xn)是一個n維決策向量，f(x)為目標函數(shù)，gj(x)≤0和hj(x) = 0分別表示q個不等式約束和m－q個等式約束．函數(shù)f，gj和hj為線性或非線性實數(shù)函數(shù)．ui和li分別為變量xi的上界和下界．另外，假定可行解空間中滿足所有約束的點集合用U表示，搜索空間中滿足上界和下界約束的點集合用S表示，其中SU．

一般地，在約束進化算法中，等式約束經(jīng)常需要轉(zhuǎn)化成不等式約束，具體如下:

其中j∈{ q +1，…，m}，δ為等式約束違反的容忍因子，一般取正整數(shù)，解x到第j個約束的距離可以表示為:

那么解x到可行解區(qū)域的邊界距離，即約束違反程度可以表示為:

2.2差分進化算法

差分進化算法是一類比較流行的進化算法，并且具有良好的性能，廣泛地應(yīng)用于各種應(yīng)用領(lǐng)域．在差分進化算法中，一般包括NP個種群，每個個體向量的維度為n．一般地，個體表示為: xri，t= (x1i，t，x2i，t，…，xni，t)，其中i =1，2，…，NP，NP為種群大小，n為個體向量的維度，t為當前種群的代數(shù)．差分進化算法包括三個主要的操作，分別是:變異，交叉和選擇［21］．

變異在變異操作中，對于每個種群產(chǎn)生目標向量vi，t，變異策略主要如下:

其中下標r1、r2、r3、r4和r5都是隨機從集合{ 1，2，…，NP} { i}中選取的，另外xbest，t為種群在第t代最好的個體．縮放因子F為實數(shù)，F(xiàn)∈［0，1］．

交叉交叉操作主要產(chǎn)生試驗向量ui，t= (u1i，t，u2i，t，…，uni，t)，具體如下:

其中i =1，2，…，NP，j = 1，2，…，n，jrand是屬于從1到n之間的一個隨機整數(shù)，randj(0，1)為對于每個j產(chǎn)生［0，1］均勻分布的隨機數(shù)．使用參數(shù)jrand是為了保證試驗向量ui，t不同于目標向量xi，t．交叉概率因子CR的取值通常在0－1之間．

選擇在選擇操作中，目標向量xi，t和試驗向量ui，t根據(jù)它們的適應(yīng)值進行比較，選擇適應(yīng)值更優(yōu)的進入下一代種群:

2.3基于反向?qū)W習

為了更形象地、更清楚地解釋基于反向?qū)W習的概念，必須先理解反向點的概念．圖1顯示了區(qū)間［a，b］之間x的反向點的例子．

如果對于一個n維向量的反向點，則用如下定義表示．

定義2假設(shè)P = (x1，x2，…，xn)為一個n維向量空間的點，其中有了反向點的定義之后，那么基于反向?qū)W習的優(yōu)化可以定義如下．

定義3假設(shè)P = (x1，x2，…，xn)為一個n維向量空間的點(比如P是候選解)，f(·)是候選解的目標函數(shù)適應(yīng)值，另外根據(jù)反向點的定義可知P的反向點為．如果，則表示比P具有更好的適應(yīng)值，此時選擇珔P代替P，否則保持P不變．

3　算法框架

本文提出的算法并不是一種新的約束差分進化算法，而是基于反向?qū)W習機制的一種通用算法框架以改善約束差分進化算法的搜索性能，特別是搜索求解的精度和收斂速度．由定義3可知，基于反向?qū)W習的機制需要比較種群與反向種群的適應(yīng)值，而約束優(yōu)化問題的適應(yīng)值不能簡單地由目標函數(shù)值決定，因此我們就采用一種適應(yīng)值變換的方法來處理基于反向?qū)W習機制中的適應(yīng)值比較問題．

3.1適應(yīng)值變換

一般情況下，在無約束差分進化算法中，適應(yīng)值都等于目標函數(shù)值，但是在約束差分進化算法中，由于約束的存在，不能簡單地考慮適應(yīng)值等于目標函數(shù)值，必須要考慮約束條件的存在．比如，對于最小值優(yōu)化問題，解向量X的目標函數(shù)值比Y小，但X卻違反了約束條件，而Y沒有違反約束條件．此時，應(yīng)該考慮可能解向量Y比X更優(yōu)．為了更好地處理約束差分進化算法中的適應(yīng)值，采用適應(yīng)值變換(Adaptive Fitness Transformation，簡稱AFT)［22］方法把種群分成三種狀態(tài):不可行狀態(tài)、半可行狀態(tài)和可行狀態(tài)．

不可行狀態(tài)在不可行狀態(tài)下，種群只包含了不可行解，因此不用考慮目標函數(shù)值，只需要考慮約束違反程度．約束違反程度可以通過式(7)計算，此時適應(yīng)值計算公式如下:

半可行狀態(tài)在半可行狀態(tài)下，種群既包含了部分可行解又包含了部分不可行解，因此就必須在目標函數(shù)值和約束違反程度之間找到一個平衡點．從解的層面分析，此時把種群細分為可行解組(Z1)和不可行解組(Z2)．因此解xi的目標函數(shù)值f'(xi)就可以轉(zhuǎn)換成:

其中φ是上一代種群的可行解比率，xbest和xworst分別是可行解組Z1最優(yōu)和最差的解．進一步把式(16)歸一化為:

式(7)可以計算約束違反程度，在此狀態(tài)下，式(7)歸一化為:

因此最終的適應(yīng)值可以表示為:

可行狀態(tài)在可行狀態(tài)下，種群中所有個體都是可行解，因此就可以看作是無約束優(yōu)化問題來處理．此時適應(yīng)值就等于目標函數(shù)值f(xi) ，具體如下:

3.2算法描述

在進化算法中，基于反向?qū)W習的機制基本上都是用于種群初始化和代跳躍階段．在種群初始化階段，對于隨機生成的初始種群P0(其中種群大小為NP，個體向量的維度為n)，通過公式OPji，0= aj+ bj－Pji，0計算出相應(yīng)的反向種群OP0，式中i = 1，2，…，NP，j = 1，2，…，n．然后再從種群P0和OP0中選出適應(yīng)值更優(yōu)的個體組成新的初始種群P0．在種群代跳躍階段，與初始化階段不同的是，首先，該階段的執(zhí)行必須滿足一個代跳躍概率Jr，在絕大部分情況下Jr= 0．3［14］．其次，反向種群的計算公式為OPji，t= MIN(Pji，t) + MAX(Pji，t)－Pji，t，其中MIN(Pji，t)和MAX(Pji，t)分別表示第t代種群中最差和最優(yōu)的個體．OBL-CDE算法偽代碼如下:

算法1 OBL-CDE偽代碼

算法1中的函數(shù)Select－Fitbest－Individual(P，OP)表示從種群P和反向種群OP中選取最優(yōu)的個體組成新的種群，函數(shù)Select－Fitbest－Individual(P，OP)詳細描述如下:

算法2 Select－Fitbest－Individual(P，OP)

從算法描述中可以看出，OBL-CDE算法簡單且容易操作，它可以植入到所有的約束差分進化算法中．另外，OBL-CDE的時間復(fù)雜度為O(Gmax·NP·n)，其中Gmax表示迭代的最大代數(shù)．如果植入到其它約束差分進化中，并不會增加它們的時間復(fù)雜度．

3.3OBL-CDE算法移植討論

根據(jù)OBL-CDE算法的描述和偽代碼，可以看出OBL-CDE算法核心有兩部分: (1)在種群初始階化段采用OBL機制求出該初始種群的反向種群，然后使用適應(yīng)值變換方法從原始種群和其反向種群中選擇最優(yōu)的種群作為新的初始種群; (2)在子種群的生存選擇之后，采用代跳躍方法使當前的子種群跳入到新的候選解中以加速收斂速度．也就是說，求出當前子種群的反向種群，然后也使用適應(yīng)值變換方法從當前子種群和其反向種群中選擇最優(yōu)的種群作為新的子種群．由于所有的CDE算法都有種群初始化和生存選擇兩部分，所以我們只要把OBLCDE算法中求初始反向種群和代跳躍兩部分的代碼植入到其它CDE算法中種群初始化和生存選擇的位置便可完成植入過程．由于只需要修改兩個位置的代碼就可完成OBL-CDE框架到其它CDE算法的植入，所以該植入過程簡單可靠，而且通用性強．

4　實驗測試

我們對(μ+λ) -CDE和OBL-(μ+λ) -CDE、ECHTDE和OBL-ECHT-DE四個算法選取CEC 2010中18個Benchmark函數(shù)的10維(10D)測試函數(shù)和30維(30D)測試函數(shù)分別進行了對比實驗測試．實驗環(huán)境為64位的Windows 7系統(tǒng)，其中CPU為Intel Core TM 2.83GHz，內(nèi)存為4GB．我們沒有對50維(50D)或更高維的測試函數(shù)進行實驗，是因為目前的進化算法求解效果都很差，難以分出勝負．與此同時，我們也沒有選取CEC 2006中的Benchmark函數(shù)做實驗測試，因為目前絕大多數(shù)的約束差分進化算法對于CEC 2006中的24 個Benchmark函數(shù)都能求解到最優(yōu)解．另外，由于目前大多數(shù)的約束差分進化算法都是針對CEC 2006進行實驗測試的，而OBL-(μ+λ) -CDE和OBL-ECHT-DE算法對于CEC 2006中的24個Benchmark函數(shù)也同樣能求解到最優(yōu)解，因此無法區(qū)分出優(yōu)劣．所以我們的算法只和CEC 2010競賽中冠軍算法εDEag［23］進行了對比測試．

4.1實驗參數(shù)設(shè)置

為了比較公平，OBL-(μ+λ) -CDE與(μ+λ) -CDE設(shè)置相同的參數(shù)，具體如下［6］: (1)種群大小:μ= 70 (NP =μ)，λ=210; (2)交叉概率: CR = 0．9; (3)縮放因子: F =0．8; (4)代跳躍概率: Jr=0．3．

其它參數(shù)的設(shè)置也與文獻［6］相同，根據(jù)文獻［6］，變異策略概率pm=0.05，用戶自定義參數(shù)g =200，閾值代因子k =0.6和容忍因子δ=0.0001．

與前面類似，OBL-ECHT-DE與ECHT-DE設(shè)置相同的參數(shù)［7］: (1)種群大小:μ=50(NP =μ) ; (2)交叉概率: CR = 0．7; (3)縮放因子: F =0．9; (4)代跳躍概率: Jr=0．3．

4.2性能評價指標

(1)可行解比率:在算法所有次數(shù)的運行過程中，成功找到可行解的個數(shù)占所有種群個數(shù)的比率平均值．該可行解比率的最大值等于1，最小值等于0．值越大，表示算法能成功找到可行解的性能越好．

(2)收斂圖:用來表示算法在求解過程中，向最優(yōu)解靠近的一種漸近走向．該走向的趨勢下降的越快，表示收斂性越好．

(3) Wilcoxon符號秩檢驗［24］:該方法是在成對觀測數(shù)據(jù)的符號檢驗基礎(chǔ)上發(fā)展起來的，比傳統(tǒng)的單獨用正負號的檢驗更加有效，是非參數(shù)的統(tǒng)計測試方法．例如，A算法和B算法進行Wilcoxon符號秩檢驗測試，如果在測試結(jié)果中，A算法對于B算法的R+比R－的值要大，則表明A算法優(yōu)于B算法．

(4) Friedman測試［25］:與Wilcoxon符號秩檢驗不同的是，F(xiàn)riedman測試可以針對三個及以上算法進行Rank測試，Rank值越小，表明算法性能越好．

4.3實驗結(jié)果分析

根據(jù)CEC 2010的要求，實驗中的每一個算法對于每一個測試函數(shù)都運行50次，在每一次運行過程中，對于10D測試函數(shù)設(shè)置Max－FEs =2×105，對于30D測試函數(shù)設(shè)置Max－FEs =6×105．

(1) OBL-(μ+λ) -CDE與(μ+λ) -CDE比較

我們對OBL-(μ+λ) -CDE和(μ+λ) -CDE算法針對CEC 2010的Benchmark函數(shù)進行了實驗測試，結(jié)果顯示在表1中，其中粗體表示該算法的值更優(yōu)．從表中的結(jié)果來看，在10D測試函數(shù)方面，對于平均值，OBL-(μ+λ) -CDE比(μ+λ) -CDE勝出16個函數(shù)，有2個函數(shù)處于劣勢;對于可行解比率，OBL-(μ+λ) -CDE比(μ +λ) -CDE也是勝出16個函數(shù)，有2個函數(shù)處于劣勢．而在30D測試函數(shù)方面，對于平均值，OBL-(μ+λ) -CDE比(μ+λ) -CDE勝出17個函數(shù)，只有1個函數(shù)處于劣勢;對于可行解比率，OBL-(μ+λ) -CDE比(μ+ λ) -CDE勝出15個函數(shù)，有3個函數(shù)相等．比較結(jié)果說明了對于高維測試函數(shù)，OBL-(μ+λ) -CDE更有優(yōu)勢．另外，我們對10D和30D測試函數(shù)各隨機選取了一個測試函數(shù)進行了收斂性測試，并畫出了它們的收斂圖，如圖2所示．其中圖2(a)為10D測試函數(shù)c13的收斂圖，圖2(b)為30D測試函數(shù)c15的收斂圖．從圖2中很明顯可以看出，無論是10D測試函數(shù)還是30D測試函數(shù)，OBL-(μ+λ) -CDE的收斂性都好于(μ+λ) -CDE．

(2) OBL-ECHT-CDE與ECHT-CDE比較

我們也對OBL-ECHT-CDE和ECHT-CDE算法針對CEC 2010的Benchmark函數(shù)進行了實驗測試，表2顯示了比較結(jié)果，其中粗體表示該算法的值更優(yōu)．從表2中可以看到，對于10D測試函數(shù)，OBL-ECHT-DE在平均值方面比ECHT-DE勝出14個函數(shù)，有4個函數(shù)處于劣勢;可行解比率方面的情況與平均值差不多，OBL-ECHT-DE 比ECHT-DE勝出13個函數(shù)，有1個函數(shù)相等，4個函數(shù)處于劣勢．而對于30D測試函數(shù)，在平均值方面，OBLECHT-DE比ECHT-DE勝出16個函數(shù)，只有2個函數(shù)處于劣勢;在可行解比率方面，OBL-ECHT-DE比ECHTDE勝出14個函數(shù)，有3個函數(shù)相等，只有1個函數(shù)處于劣勢．比較結(jié)果也說明了對于高維測試函數(shù)，OBLECHT-DE優(yōu)勢更明顯．圖3給出了OBL-ECHT-CDE 與ECHT-CDE的收斂圖，從圖中可以看出，無論是10D測試函數(shù)還是30D測試函數(shù)，OBL-ECHT-CDE的收斂性都明顯優(yōu)于ECHT-CDE．

表1　OBL-(μ+λ) -CDE與(μ+λ) -CDE實驗結(jié)果比較

表2　OBL-ECHT-DE與ECHT-DE實驗結(jié)果比較

表3　OBL-(μ+λ) -CDE、OBL-ECHT-DE與其εDEag算法比較結(jié)果

(3) OBL-(μ+λ) -CDE、OBL-ECHT-DE與εDEag算法比較

εDEag算法是CEC 2010競賽中的冠軍算法，即在目前求解CEC 2010的18個Benchmark函數(shù)的差分進化算法中，εDEag算法是最優(yōu)的．在表3和表4中，具有灰色底紋加粗的數(shù)據(jù)表示最優(yōu)，僅僅加粗的數(shù)據(jù)表示次優(yōu)．

從OBL-(μ+λ) -CDE與εDEag的比較可以看出，對于10D函數(shù)，在最優(yōu)值方面，OBL-(μ+λ) -CDE勝出3個函數(shù)，有11個函數(shù)相等，只有4個函數(shù)處于劣勢;在平均值方面，OBL-(μ+λ) -CDE勝出4個函數(shù)，有3個函數(shù)相等，有11個函數(shù)處于劣勢;在最差值方面，基本情況與平均值差不多，只是多勝出1個函數(shù)，即共勝出5個函數(shù)．對于30D函數(shù)，在最優(yōu)值方面，OBL-(μ+ λ) -CDE勝出5個函數(shù)，有1個函數(shù)相等，有13個函數(shù)接近或略差于εDEag算法;在平均值方面，OBL-(μ+ λ) -CDE也勝出了3個函數(shù)，有15個函數(shù)接近或略差于εDEag算法;在最差值方面，與平均值的情況相同．從OBL-ECHT-CDE與εDEag的比較可以看出，對于10D函數(shù)，在最優(yōu)值方面，OBL-ECHT-CDE勝出4個函數(shù)，有11個函數(shù)相等，只有3個函數(shù)處于劣勢;在平均值方面，OBL-ECHT-CDE勝出4個函數(shù)，有3個函數(shù)相等，其它函數(shù)是接近或略差于εDEag算法，在最差值方面，與平均值的情況相同;對于30D函數(shù)，在最優(yōu)值方面，OBL-ECHT-CDE勝出6個函數(shù)，有1個函數(shù)相等，其它函數(shù)是接近或略差于εDEag算法．在平均值方面，OBL-ECHT-CDE勝出2個函數(shù)，其它函數(shù)是接近或略差于εDEag算法，在最差值方面，與平均值的情況相同．

表4　OBL-(μ+λ) -CDE、OBL-ECHT-DE與其εDEag算法比較結(jié)果(續(xù))

我們對于OBL-(μ+λ) -CDE、(μ+λ) -CDE、OBLECHT-DE、ECHT-DE四個算法進行了Friedman測試，測試結(jié)果如表5所示．從測試數(shù)據(jù)很明顯可以看出，無論是對于10D測試函數(shù)還是30D測試函數(shù)，OBL-(μ+ λ) -CDE和OBL-ECHT-DE的排名都分別排在(μ+λ) -CDE和ECHT-DE的前面．另外還可以看出，對于10D測試函數(shù)，OBL-(μ+λ) -DE稍優(yōu)于ECHT-DE;而對于30D測試函數(shù)，OBL-(μ+λ) -DE則明顯優(yōu)于ECHT-DE．

最后我們對于OBL-(μ+λ) -CDE、(μ+λ) -CDE、OBL-ECHT-DE、ECHT-DE和εDEag算法進行了Wilcoxon符號秩檢驗測試，表6是這個幾個算法的Wilcoxon符號秩檢驗測試結(jié)果，從結(jié)果中可以知道，OBL-(μ+ λ) -CDE和OBL-ECHT-DE分別明顯優(yōu)于(μ+λ) -CDE 和ECHT-DE，稍差于εDEag，但OBL-ECHT-DE在10D函數(shù)的最優(yōu)值方面要優(yōu)于εDEag．

通過與εDEag算法的比較，我們發(fā)現(xiàn)OBL-(μ+λ) -CDE和OBL-ECHT-DE算法并沒有很大的優(yōu)勢，甚至稍弱于εDEag算法．這是因為我們提出的是一種算法框架，而不是某一個具體的算法，因此在與εDEag算法比較時，能否超越εDEag算法，還要取決于OBL-CDE植入的母體算法(如(μ+λ) -CDE、ECHT-CDE等)．當然，我們將來的工作，可以考慮將OBL-CDE植入到εDEag算法中，以證明我們所提出的算法框架的優(yōu)越性．

表5　四個算法針對CEC 2010的Friedman測試結(jié)果

表6　Wilcoxon符號秩檢驗結(jié)果

5　結(jié)束語

在過去的幾年中，加入約束處理技術(shù)的差分進化算法可以用于解決約束優(yōu)化問題，但大數(shù)的約束差分進化算法容易陷入局部最優(yōu)．基于反向?qū)W習的機制是機器學習中一種常用的方法，它用于約束差分進化算法中，通過設(shè)置反向種群引導算法跳出局部最優(yōu)的限制．本文提出了一種基于反向?qū)W習的約束差分進化算法框架，它采用基于反向?qū)W習的機制引導種群進化，以提高求解精度和收斂速度．最后我們把該算法框架應(yīng)用于(μ+λ)－CDE和ECHT-DE算法，并針對CEC 2010中的18個Benchmark函數(shù)進行了實驗測試，實驗結(jié)果表明，我們的算法植入(μ+λ) -CDE和ECHT-DE后，對(μ+λ) -CDE和ECHT-DE算法都有相當明顯的改進．將來的工作就是如何把我們的算法框架植入到更多的約束差分進化算法或其它具有約束的進化算法中，以改進它們的性能．

參考文獻

［1］Runarsson T P，Yao X．Search biases in constrained evolutionary optimization［J］．IEEE Transactions on Systems，Man，and Cybernetics-Part C: Applications and Reviews，2005，35(2) : 233－243．

［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］Storn R．System design by constraint adaptation and differential evolution［J］．IEEE Transactions on Evolutionary Computation，1999，3(1) : 22－34．

［4］Lampinen J．A constraint handling approach for the differential evolution algorithm［A］．IEEE Congress on Evolutionary Computation［C］．Honolulu，HI: IEEE Computational Intelligence Society，2002．1468－1473．

［5］Mezura-Montes E，Velazquez-Reyes J，Coello Coello C A．Promising infeasibility and multiple offspring incorporated to differentialevolution for constrained optimization［A］．Proceedings of the Conference on Genetic and Evolutionary Computation［C］．Washington DC: ACM Press，2005．225 －232．

［6］Wang Y，Cai Z．Constrained evolutionary optimization by means of (μ+λ) -differential evolution and improved adaptive trade-off model［J］．Evolutionary Computation，2011，19(2) : 249－285．

［7］Mallipeddi R，Ponnuthurai P，Suganthan N．Ensemble of constraint handling techniques［J］．IEEE Transactions on Evolutionary Computation，2010，14(4) : 561－579．

［8］Liang J J，et al．Problem definitions and evaluation criteria for the CEC 2006 special session on constrained realparameter optimization［R］．Singapore: Nanyang Technological University，Technical Report，2006．1－24．

［9］Takahama T，Sakai S．Constrained optimization by the ε constrained differential evolution with gradient-based mutation and feasible elites［A］．IEEE Congress on Evolutionary Computation［C］．Vancouver，BC: IEEE Computational Intelligence Society，2006．1－8．

［10］Das S，Suganthan P N．Differential evolution: A survey ofthe state-of-the-art［J］．IEEE Transactions on Evolutionary Computation，2011，15(1) : 4－31．

［11］Zhang J，Zhan Z，Lin Y，et al．Evolutionary computation meets machine learning: A survey［J］．IEEE Computational Intelligence Magazine，2011，6(4) : 68－75．

［12］Tizhoosh H R．Opposition-based learning: A new scheme for machine intelligence［A］．Proceedings of the International Conferenceon Computational Intelligence for Modelling，Control and Automation，and International Conference on Intelligent Agents，Web Technologies and Internet Commerce［C］．Vienna: IEEE Computer Society，2005．695－701．

［13］Xu Q Z，Wang L，Wang N，et al．A review of oppositionbased learning from 2005 to 2012［J］．Engineering Applications of Artificial Intelligence，2014，29(1) : 1－12．

［14］Rahnamayan S，Tizhoosh H R，Salama M M A．Opposition-based differential evolution algorithms［A］．IEEE Congress on Evolutionary Computation［C］．Vancouver，BC: IEEE Computational Intelligence Society，2006．2010 －2017．

［15］Ahandani M A，Alavi-Rad H．Opposition-based learning in the shuffled differential evolution algorithm［J］．Soft Computing，2012，16(8) : 1303－1337．

［16］Omran M G H．CODEQ: An effective metaheuristic for continuous global optimization［J］．International Journal of Metaheuristics，2010，1(2) : 108－131．

［17］Miao X F，Mu D J，Han X W，et al．A hybrid differential evolution for numerical optimization［A］．International Conference on Biomedical Engineering and Informatics ［C］．Tianjin: IEEE Engineering in Medicine and Biology Society，2009．1－5．

［18］Wang H，Rahnamayan S，Wu Z J．Parallel differential evolution with self adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems［J］．Journal of Parallel and Distributed Computing，2013，73(1) : 62－73．

［19］Omran M G H，Salman A．Constrained optimization using CODEQ［J］．Chaos，Solitons Fractals，2009，42(2) : 662 －668．

［20］Mallipeddi R，Suganthan P N．Problem definitions and evaluation criteria for the CEC 2010 competition on constrained real-parameter optimization［R］．Singapore: Nanyang Technological University，Technical Report，2010．1－16．

［21］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．

［22］Gong W，Cai Z，Liang D．Engineering optimization by means of an improved constrained differential evolution［J］．Computer Methods in Applied Mechanics and Engineering，2014，268(1) : 884－904．

［23］Takahama T，Sakai S．Constrained Optimization by the ε constrained differential evolution with an archive and gradient-based mutation［A］．IEEE Congress on Evolutionary Computation［C］．Barcelona: IEEE Computational Intelligence Society，2010．1－9．

［24］Derrac J，Garc?a S，Molina D，et al．A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms［J］．Swarm and Evolutionary Computation，2011，1 (1) : 3－18．

［25］Corder G，F(xiàn)oreman D．Nonparametric Statistics for Non-Statisticians: A Step-by-Step Approach［M］．Hoboken，NJ: John Wiley，2009．38－56．

魏文紅男，1977年9月生于江西南昌，東莞理工學院副教授，博士，主要研究方向:高性能計算、進化算法、多目標優(yōu)化處理．

E-mail: weiwh@ dgut．edu．cn

周建龍男，1974年6月出生于甘肅臨洮，西安交通大學城市學院特聘教授，博士，研究興趣包括:人機交互、體視化、增強現(xiàn)實、認知計算以及機器學習．

E-mail: zhou－jianlong@ hotmail．com

陶銘男，1986年6月生于安徽馬鞍山，東莞理工學院副研究員，博士，主要研究方向:移動IP技術(shù)．

E-mail: taom@ dgut．edu．cn

袁華強(通信作者)男，1966年12月生于湖南衡東，東莞理工學院教授，博士，主要研究方向:智能計算．

E-mail: hyuan66@163．com

Constrained Differential Evolution Using Opposition-Based Learning

WEI Wen-hong1，ZHOU Jian-long2，TAO Ming1，YUAN Hua-qiang1
(1．School of Computer，Dongguan University of Technology，Dongguan，Guangdong 523808，China; 2．Department of Computer，Xi’an Jiaotong University City College，Xi’an，Shaanxi 710018)

Abstract:Differential evolution is a global heuristic algorithm，which is simple，easy-to-use and robust in practice．Combining with the constraint-handling techniques，it can solve constrained optimization problems．Machine learning often guides population to evolve in the evolution computation，and is widely applied to unconstrained differential evolution algorithm．However，machine learning is rarely applied to constrained differential evolution algorithm，so this paper proposed a constrained differential evolution algorithm framework using opposition-based learning．The algorithm can improve the diversity and convergence of differential evolution．At last，the proposed algorithm framework is applied to two popular constrained differential evolution variants，that is (μ+λ) -CDE and ECHT-DE．And 18 benchmark functions presented in CEC 2010 are chosen as the test suite，experimental results show that comparing with (μ+λ) -CDE and ECHT-DE，our algorithms are able to improve global search ability，convergence speed and accuracy in the majority of test cases．

Key words:opposition-based learning; differential evolution; constrained optimization; convergence

作者簡介

基金項目:國家自然科學基金(No．61103037，No．61300198) ;廣東省自然科學基金(No．S2013010011858) ;廣東省高?？萍紕?chuàng)新項目(No．2013KJCX0178) ;陜西省工業(yè)科技攻關(guān)項目(No．2015GY012) ;陜西省自然科學基礎(chǔ)研究計劃項目(No．2015JM6331) ;西安交通大學城市學院科研項目(No．2015KZ01，2015KZ02)

收稿日期:2015-04-10;修回日期: 2015-07-08;責任編輯:馬蘭英

DOI:電子學報URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．026

中圖分類號:TP38

文獻標識碼:A

文章編號:0372-2112 (2016) 02-0426-11