廣義逆向學習方法的自適應差分算法

劉昌芬，韓紅桂，喬俊飛

（1.北京工業大學 電子信息與控制工程學院， 北京100124; 2.計算智能與智能系統北京市重點實驗室, 北京100124）

?

廣義逆向學習方法的自適應差分算法

劉昌芬1,2，韓紅桂1,2，喬俊飛1,2

（1.北京工業大學 電子信息與控制工程學院， 北京100124; 2.計算智能與智能系統北京市重點實驗室, 北京100124）

針對差分算法（differential evolution, DE）在解決高維優化問題時參數設置復雜、選擇變異策略困難的現象，提出了廣義逆向學習方法的自適應差分進化算法（self-adaptive DE algorithm via generalized opposition-based learning, SDE-GOBL）。利用廣義的逆向學習方法（generalized opposition-based learning, GOBL）來進行多策略自適應差分算法（Self-adaptive DE, SaDE）的初始化策略調整，求出各個候選解的相應逆向點，并在候選解和其逆向點中選擇所需要的最優初始種群，然后再進行自適應變異、雜交、選擇操作，最后通過CEC2005國際競賽所提供的9個標準測試函數對SDE-GOBL算法進行驗證，結果證明該算法具有較快的收斂速度和較高的求解精度。

差分算法; 優化; 自適應; 逆向學習; 收斂速度; 精度; 高維; 初始化

DE（differential evolution）算法是由Storn和Price在1995年提出的簡單高效的基于群體的隨機搜索算法[1]，該算法采用實數編碼的方式，具有結構簡單、易于實現、魯棒性強等優點，因此，從該算法出現，便吸引了許多相關研究人員的探索[2-5]，并在很多領域取得了成功應用[6-8]。在研究過程當中，提出了很多種變異策略以適合求解不同的問題。但是，如何根據實際問題選擇最恰當的變異策略的過程是很復雜的。Qin和P.N.Suganthan首次提出自適應差分進化策略[9]，之后研究者們進行了很多通過自適應選擇DE中的變異策略的研究。而差分算法區別其他算法的最大特點就在于其差分變異算子的使用，該算子具有搜索方向和搜索步長自適應的特點。但是，算法對縮放因子F和雜交概率CR的大小設置很敏感，針對不同的問題需要多次運行選擇不同的合適經驗值。Abbas在文獻[10]中提出了自適應調整交叉概率CR的概念，Omran等在文獻[11]中提出了一種運用自適應方法調整縮放因子F的算法（self-adaptive differential evolution ,SDE），該算法中的CR是一正態分布數，提高了算法的性能，減少了控制參數，同時用4種標準測試函數測試后，顯示出了比其他差分算法更優的表現性能。除了自適應調整CR和F，Teo[12]提出了自適應種群差分算法（exploring dynamic self adaptive populations in DE, DESAP），該算法中群體大小NP也是自適應變化的。上述這些算法的選擇策略是唯一的，很難在眾多優化問題中進行推廣應用。Qin等提出的SaDE算法，采用廣義的隨機選擇方法對每一個目標向量選擇變異策略，并跟隨著演化代數的變化按規則進行自適應更新[13]，CR根據先前的經驗值反饋回來進行自適應更新。但是，隨著求解問題的復雜度的增加，種群的搜索空間增大，求解難度勢必會加大。Rahnamayan為解此問題，提出了基于逆向學習方法的差分進化算法（opposition based DE, ODE）[14]，該算法不僅可以應用到種群的初始化過程，而且也可用到進化過程，實現對群體的逆向搜索，大大增強了種群對搜索空間的利用能力。在國內，很多學者針對標準差分算法存在的早熟收斂和搜索停滯等缺陷進行了研究和改進。吳亮紅根據群體在運行過程中適應度方差的大小增加了一種新的變異操作，有效提高了算法的全局搜索能力[15]。陳亮提出改進的二進制差分進化算法，改進算法的變異策略的同時，在運行過程中自適應調整種群規模，提高了算法的優化精度[16]。針對算法在解決高維函數優化中存在的缺陷，劉榮輝引入了階段交叉差分算法，對交叉因子進行自適應控制，提高了算法的收斂精度[17]。Wang將GOBL引入到差分算法中，改進了ODE算法，提出廣義逆向學習差分（enhanced opposition-based DE, GODE）算法用來解決高維的函數優化問題，在算法的魯棒性、收斂速度、成功率等方面均取得了較好的測試效果[18]。

基于以上分析，文中將GOBL應用到SaDE算法中，提出SDE-GOBL算法，用以解決高維優化問題，該算法能夠自適應選擇變異策略，較好平衡了DE算法的勘測能力與開采能力。并且利用國際上通用的標準測試函數在不同維度下進行驗證，結果表明：該算法在解決高維問題時，收斂速度快，尋優精度高，可以推廣應用到實際的優化問題中。

1 DE算法

差分算法起初主要用于求解實數優化問題，它的最重要的貢獻是差分變異算子的引用，該算子主要是針對父代個體，將同一群體中兩個不同的個體向量進行差分和縮放操作，再與群體的其他個體向量進行操作得到變異個體向量，根據變異操作方式不同分為不同的變異策略。使之與父個體向量進行雜交形成試驗向量，最后讓這一試驗向量的適應值與父個體向量的適應值進行比較，較優者將保存到下一代。通過以上變異、雜交和選擇等操作不斷進化，適者生存，一直到滿足終止條件停止。算法操作過程如下：

1）編碼與初始化

2）差分變異操作

3）雜交操作

（1）

式中:CR為交叉概率因子; jrand是介于維數[1,D]之間的一個均勻分布隨機整數，用來保證試驗向量Ui,G中至少有一維來自變異向量Vi,G，避免與父個體向量Xi,G相同。

雜交操作是為了增強新種群的離散程度，較大的CR值可以加快算法的收斂，同時其取值與所要求解的問題的特性有關系，當自變量相互獨立時，可以設置為[0,0.2]，相互依賴強偶合時，可設置成接近于1的數。

4）選擇操作

通過初始化、變異、雜交操作產生子代新群體以后，運行此操作步驟。主要是利用一對一貪婪選擇的方法將子個體向量與相對應的上一代父個體向量比較，淘汰不良個體，保留優良個體遺傳到下一代。通常求解最小化優化問題時，算法的選擇操作可表示為

式中：f（Xi,G）是個體Xi,G的適應值。采用一對一競標賽選擇，可以保證精英解在演化過程中不會丟失，且更能維持群體的多樣性。

2 DE-GOBL算法

2.1 SaDE算法

在解決不同的最優化問題時，實驗向量采用不同的DE策略進行迭代將產生不同的效果。SaDE算法將不同特性的策略放在一起形成一個候選策略庫，在迭代的過程中，根據一定概率pk從策略庫中選擇一個變異策略，在之前的迭代中越容易達到最優解的DE策略，越容易在此迭代操作中被選擇，而不是通過反復實驗來找到。然后再進行雜交操作。算法參數的設置如下：

1）初始化選擇概率pk為1/4，利用廣義隨機選擇的方法對每一個目標向量選擇相應的變異策略并經過LP次（一個學習周期）迭代演化以后，pk值更新為式（3） ：

式中：Sk,G按式（4）計算：

（4）

式中：G（G>LP）是當前的演化代數；nsk,G和nfk,G分別是前一次學習周期中第k個變異策略所產生子個體成功或者失敗進入下一代種群的個數；Sk,G為當前種群選擇第k個變異策略所產生的子個體成功進入下一代種群的成功概率；設置ε為一個很小的常數，可避免出現零值。

2）每個個體i的縮放因子Fi=rndni（0.5,0.3），是均值為0.5、方差為0.3的正態分布隨機數。

3）種群中每個個體選擇第k個策略時的雜交概率CRi,k=rndni（CRmk,0.1）,如其值不在[0,1]范圍內，則采用截斷方法限制在這一范圍內，CRmk初始為0.5，CRMemoryk為前LP代中第k個策略產生的子個體成功進入下一代時所保存的CR值，經過LP次迭代以后，每一代CRmk用CRMemoryk中所保存的CR值的中間值代替。

Qin在文獻[9]中將該算法與傳統DE算法以及另外3種自適應差分算法（ADE、SDE、jDE）通過26個有約束條件的優化測試函數進行了比較，結果表明：SaDE算法在獲得最優解時有相對較小標準差和更高的成功率，且收斂速度快。所以文中選擇改進后的高性能自適應算法，該算法在解決高維問題時，能以更快的速度達到收斂，滿足實際工程的需要。

2.2 基于逆向學習方法的最優化方法

根據概率理論，一個點有50%的可能性比它相應的逆向點獲得更好的適應值[19]。這樣將廣義逆向學習方法應用到差分算法中，可以有效利用群體和逆向群體的信息，提高了對種群的原搜索空間的利用能力，可以在不增大種群搜索空間的前提下，增加找到全局最優解的可能性，有效避免了在解決高維優化問題中算法搜索難度大、操作復雜的問題。

Wang將此方法應用在DE算法中，提出了GODE算法。選用9個高維連續最優化問題[20]檢驗算法的性能，在維數D=50、100、200、500、1 000下，GODE算法比DE、CHC、G-CMA-ES算法運行效果都好，但是在運行F3（shifted rosenbrock's function）、F8（schwefel's problem 1.2）以及F3的混合組成函數F13和F17時，卻很難找到最優解。

2.3 基于GOBL的自適應差分算法

為有效利用種群有限的搜索空間，降低尋找最優點的難度，將GOBL運用到SaDE這種高效能的自適應DE算法中，能很好地改善算法在解決高維復雜優化問題的收斂性能。采用GOBL初始化種群，如果隨機數rand（0,1）滿足小于逆向學習概率p0的條件，就運行GOBL更新種群，否則運行SaDE算法中的變異、雜交操作。

一般來說，選擇哪種策略放在策略庫中是個很嚴謹的問題。一個好的策略庫應在減少一些不必要的策略的同時，仍可以滿足不同實際優化問題在種群進化的不同階段的需要。為了比較的方便，仍選用Qin在SaDE算法中選用的策略庫。

策略庫中包含4種變異策略：DE/rand/1/bin、DE/rand-to-best/2/bin、DE/rand/2/bin和DE/current -to-rand/1，4種變異策略的公式如 式（6）～（9）所示。其中，DE/rand/1/bin、DE/rand-to-best/2/bin在很多DE算法的改進工作中頻繁使用，是比較經典的兩種變異策略；DE/rand/2/bin由于加上了高斯擾動使算法具有很好的探測能力；DE/current- to-rand/1可以更有效地解決多目標函數優化問題。DE/rand/1/bin:

DE/rand-to-best/2/bin:

DE/rand/2/bin:

（8）

DE/current-to-rand/1:

綜上所述，SDE-GOBL算法的具體流程如圖1所示。

圖1 SDE-GOBL算法流程

3 性能分析

3.1 測試函數

為檢驗文中提出的算法的有效性，采用CEC2005國際競賽所提供的前9個標準測試函數，這9個測試函數多次用來測試算法的性能，具有不同的特性，可抽象的表示實際生活的不同問題。

F1.Shifted Sphere Function；

F2: Shifted Schwefel’s Problem 1.2；

F3: Shifted Rotated High Conditioned Elliptic Function；

F4: Shifted Schwefel’s Problem 1.2 with Noise in Fitness；

F5: Schwefel’s Problem 2.6 with Global Optimum on Bounds；

F6: Shifted Rosenbrock’s Function；

F7: Shifted Rotated Griewank’s Function without Bounds；

F8: Shifted Rotated Ackley’s Function with Global Optimum on Bounds；

F9: Shifted Rastrigin’s Function.

每一個測試函數具有不同的特征，分別抽象地描述了現實生活的不同問題，其中函數F1～F5是單峰函數，函數F6～F9是多峰函數且極值點的個數非常多，所有的測試函數的最優解皆為0。各個測試函數的詳細介紹可參照文獻[20]。

以上9個函數都進行了中心偏移旋轉，最優值不在原點，不能采用輸出結果接近于0的程度作為評價指標，只能采用輸出結果與正確結果之間的距離來比較算法的優劣性，這樣做是為防止某些算法傾向于優化那些最小值在原點處的函數[16]。因此文中采用解誤差測度法評價各個算法的性能，即理想的輸出結果與實際輸出結果之間的誤差距離，定義Derror=f（x）-f（x*），其中，x是算法找尋到的最優解，x*則是目標函數f（x）的已知全局最優解。

3.2 結果分析

SDE-GOBL算法與SaDE算法都是參數自適應差分進化算法，交叉因子F和縮放因子CR在算法運行時自動生成并且調整，為進行公平比較，將兩個算法的運行條件設置相同，分別設置維數D=30、50（高維），種群大小NP=50，最大評價次數為10 000×D，獨立運行2種算法20次，得到測試函數最優值之和。

1）收斂速度

用MATLAB運行測試函數后，得到仿真圖如圖2～10，記錄找到最優點的迭代次數（如表1所示）。由此可知，SDE-GOBL算法的收斂速度明顯高于SaDE算法，特別是在算法收斂初期表現尤為明顯。

2）尋優精度

在D=30和D=50下運行9個測試函數20次，分別記錄SaDE算法和SDE-GOBL算法找到最優解的次數 （如表2所示）。由表2可知，除了F7以外, SDE-GOBL算法的尋優精度皆優于SaDE算法。特別是在D=50時，效果更加明顯。

圖2 F1函數的收斂曲線比較

圖3 F2函數的收斂曲線比較

圖4 F3函數的收斂曲線比較

圖5 F4函數的收斂曲線比較

圖6 F5函數的收斂曲線比較

圖7 F6函數的收斂曲線比較

圖8 F7函數的收斂曲線比較

圖9 F8函數的收斂曲線比較

圖10 F9函數的收斂曲線比較Fig.10 Convergence curves' comparison of F9

表1 找尋到最優值所需迭代次數Table 1 The number of iterations to find optimum

表2 兩算法尋優精度比較Table 2 Comparison of two algorithms’ Accuracy

DE算法產生早熟收斂的根本原因是隨著迭代次數的增加，種群的多樣性快速下降[21]。而在解復雜高維問題時，單純的增加種群的規模，只會增加算法的運算量，不能從根本上解決早熟收斂問題。文中通過引入逆向學習方法，對算法的初始化種群在進行變異之前進行處理，利用概率論的知識，在不增加種群個數的前提下精煉了初始解，保證了種群的多樣性，提高了算法的精度。

對DE算法的3個控制參數：群體大小NP、縮放因子F和雜交概率CR的設置，會對算法的性能產生直接影響，設置不合理將會導致過早收斂或算法停滯。為了彌補此不足，文中采用SaDE算法對參數的設置方法，自適應選擇變異策略，各策略根據先前經驗值自適應更新CR，使各個策略具有不同的CR，由于GOBL方法的引入，NP的大小不需要再設置在[3D,8D][22]，提高了算法的收斂速度。

4 結束語

針對一般差分算法在解決高維優化問題時遇到的求解難度大的問題，首次將廣義的逆向學習方法應用到多策略自適應差分算法中，有效地解決了傳統差分算法求解難度大、運行速度慢且精度低的問題；同時，利用9個標準的測試函數分別在不同高維下展現了算法的優良性能，具有結構簡單、容易實現、收斂快速、魯棒性強等優點，且算法穩定、成功率高。在該算法中，引入了新的參數p0，這一概率參數的設定是由經驗獲得，后期可以設計有效的參數自適應策略來更好地解決優化問題，也可以將該算法應用到實際的工程優化問題中，以實現造價低、運行簡便等優化目標。

[1]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.

[2]ALATAS B, AKIN E. MODENAR: multi-objective differential evolution algorithm for mining numeric association rules[J]. Applied Soft Computing, 2008, 8（1）:646-656.

[3]DAS S, ABRAHAM A. Automatic clustering using an improved differential evolution algorithm[J].IEEE Trans on Systems Man and Cybernetics, 2008, 38（1）: 218-237.

[4]FEOKTISTOV V. Differential evolution: in search of solutions[M]. New York: Springer Verlag, 2006: 205-276.

[5]CHAKRABORTY U. Advances in differential evolution[M]. Berline: Springer Verlag, 2008: 800-805.

[6]QING A. Differential evolution: fundamentals and applications in electrical engineering[M]. IEEE & John Wiley, 2009: 580-590.

[7]QING A, LEE C K. Differential evolution in electromagnetics[M]. Berlin: Springer Verlag, 2010:508-530.

[8]ONWUBOLU G C, DAVENDRA D. Differential evolution: a handbook for global permutation-based combinatorial optimization[M]. Berlin: Springer Verlag, 2009: 301-320.

[9]QIN A K, SUGANTHAN P N. Self-adaptive differential evolution algorithm for numerical optimization[J]. Proc IEEE Congr Evolut Comput, 2005, 2 （2）: 1785-1791.

[10]ABBASS H A. The self-adaptive Pareto differential evolution algorithm[J]. Proc Congr Evolut Comput, 2002, 1: 831-836.

[11]OMRAN M G H, SALMAN A, ENGELBRECHT A P. Self-adaptive differential evolution[J]. Lecture Notes in Artificial Intelligence, 2005, 3801: 192-199.

[12]TEO J. Exploring dynamic self-adaptive populations in differential evolution[J]. Soft Comput, 2006, 10 （8）: 637-686.

[13]QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE Trans Evolut Comput, 2009, 13（2）: 398-417.

[14]RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Opposition based differential evolution[J].IEEE Trans Evolut Comput, 2008, 12（1）: 64-79.

[15]吳亮紅，王耀南，袁小芳.自適應二次變異差分進化算法[J].控制與決策， 2006, 21（8）: 898-902.

WU Lianghong, WANG Yaonan, YUAN Xiaofang. Differential evolution algorithm with adaptive second mutation[J].Control and Decision, 2006, 21（8）: 898- 902.

[16]陳亮.改進自適應差分算法及其應用研究[D]. 上海：東華大學，2012:39-40. CHEN Liang. Improved adaptive differential evolution algorithm and its applications[D]. Shanghai: Donghua University, 2010: 39-40.

[17]劉榮輝. 多階段自適應差分進化算法及應用研究[D].上海：東華大學， 2012: 23-29. LIU Ronghui. Multi-stage self-adapting differential evolution algorithm and its application[D].Shanghai: Donghua University, 2010: 39-40.

[18]WANG Hui, WU Zhijian, RAHNAMAYAN S . Enha nced opposition-based differential evolution for solving high-dimensional continuous optimization problems[J]. Soft Comput, 2010, 15（11）: 2127-2140.

[19]RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Opposition versus randomness in soft computing techniques[J]. Soft Comput, 2008, 8（2）: 906-918.

[20]SUGANTHAN P N, HANSEN N, LIANG J J, et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[J]. KanGAL Report, 2005, 2005005.

[21] 賈麗媛，張弛.自適應差分演化進化算法[J].中南大學學報:自然科學版, 2013, 44（9）: 3759-3765. JIA Liyuan, ZHANG Chi. Self-adaptive differential evolution[J]. Journal of Central South University: Science and Technology, 2013, 44（9）: 3759-3765.

[22]G?MPERLE R, MüLLER S D, KOUMOUTSAKOS P. A parameter study for differential evolution[J]. Advances in Intelligent Systems, Fuzzy Systems, Evolutionary Computation, 2002, 10: 293-298.

劉昌芬，女，1990年生，碩士研究生，主要研究方向為智能控制理論及應用。

韓紅桂，男，1983年生，教授，主要研究方向為污水處理過程建模、優化與控制。入選北京市科技新星計劃、北京市組織部優秀人才等。申請國家發明專利13項，獲專利授權7項。近5年來，發表學術論文30余篇。參與編寫專著3部。

喬俊飛，男，1968年生，教授，博士生導師，主要研究方向為智能信息處理、智能優化控制。國家杰出青年基金獲得者，教育部新世紀優秀人才，北京市精品課程負責人。教育部科技進步獎一等獎和北京市科學技術獎三等獎各1項，獲國家發明專利授權12項。近5年發表學術論文近70篇，被SCI收錄15篇。

Self-adaptive DE algorithm via generalized opposition-based learning

LIU Changfen1,2， HAN Honggui1,2， QIAO Junfei1,2

（1.College of Electronic and Control Engineering, Beijing University of Technology, Beijing 100124, China; 2. Beijing Key Laboratory of Computational Intelligence and Intelligence System， Beijing 100124, China）

The problem related to defects of complex parameter setting and difficult selection of mutation strategies existing in the differential evolution （DE） algorithm when solving high-dimensional optimization problem is studied. This paper proposed a new self-adaptive DE algorithm based on generalized opposition-based learning （SDE-GOBL）. The generalized opposition-based learning （GOBL） is utilized for the adjustment of initiation strategy on multi-strategy self-adaptive DE （SaDE） algorithm. The corresponding reverse points of each candidate solution are figured out. In addition, the necessary optimal initial population is selected among the candidate solutions and its reverse points. Next, the self-adaptive mutation, hybridization and selection operations are conducted. Finally, nine standard test functions provided in CEC2005 International Competition are applied for demonstrating SDE-GOBL algorithm. The result showed that the algorithm has fast convergence speed and high solution precision.

differential evolution; optimization; generalized opposition-based learning; convergencespeed; accuracy; highdimension; initialization

2013-10-25.

日期：2015-01-13.

國家自然科學基金資助項目（61034008，61203099，61225016）；北京市自然科學基金資助項目（4122006）；教育部博士點新教師基金資助項目（20121103120020）；北京市科技新星計劃資助項目（Z131104000413007）.

喬俊飛. E-mail：liuchangfen2009@163.com.

10.3969/j.issn.1673-4785.201310068

http://www.cnki.net/kcms/detail/23.1538.TP.20150113.1130.007.html

TP18; O224

A

1673-4785（2015）01-0131-07

劉昌芬，韓紅桂，喬俊飛. 基于廣義逆向學習方法的自適應差分算法[J]. 智能系統學報， 2015, 10（1）: 131-137.

英文引用格式：LIU Changfen， HAN Honggui，QIAO Junfei. Self-adaptive DE algorithm via generalized opposition-based learning[J]. CAAI Transactions on Intelligent Systems, 2015, 10（1）: 131-137.