基于云推理的協方差矩陣自適應進化策略算法

喬　帥　續欣瑩　閻高偉

(太原理工大學信息工程學院　山西 太原 030024)

?

基于云推理的協方差矩陣自適應進化策略算法

喬帥續欣瑩閻高偉

(太原理工大學信息工程學院山西 太原 030024)

針對協方差矩陣自適應進化策略(CMA-ES)在求解某些問題時存在早熟收斂、精度不高等缺點，通過利用云模型良好的不確定性問題處理能力對CMA-ES的步長控制過程進行改進，得到一種基于云推理的改進CMA-ES算法。該算法通過建立步長控制的云推理模型，采用云模型的不確定性推理來實現步長的控制，避免了原算法采用確定的函數映射進行步長伸縮變化而忽視進化過程中不確定性的不足。最后通過測試函數驗證了改進算法具有較高的尋優性能。

協方差矩陣自適應進化策略云推理步長控制全局優化

0　引　言

協方差矩陣自適應進化策略(CMA-ES)是一種高效的群體隨機搜索進化策略算法，具有不依賴種群大小、收斂速度快、全局性能好等優點，以其優良的尋優性能在實值優化領域備受關注[1]。同其他進化類算法一樣，其在求解某些復雜的多峰函數問題時仍存在易早熟收斂、求解精度不高等缺點。

目前，許多學者從不同的角度對算法進行了改進。文獻[2]為算法設置重啟，通過動態地增大種群規模來獲得較強的全局搜索性能；文獻[3]通過正交設計構造正交試驗向量來引導算法跳出局部最優；文獻[4]通過限制協方差矩陣為對角陣來降低算法的時空復雜度。

云模型具有良好的不確定性建模與處理能力[5]。近年來，眾多學者將云模型應用于進化算法領域，取得了一定的成果。其中，文獻[6]提出云遺傳算法(CGA)，利用Y條件云實現交叉操作，基本云實現變異操作，最后證明了算法的有效性，具有一定的參考價值。文獻[7]提出了基于云模型的進化算法，在定性知識的控制下自適應地控制遺傳和變異的程度，較好地避免了傳統GA易陷入局部和早熟收斂等問題。文獻[8]將云模型與粒子群算法(PSO)結合，通過將粒子分群，利用X條件云自適應地控制普通粒子的慣性權重，具有較高的計算精度和較快的收斂速度。

進化過程充滿了不確定性，CMA-ES中種群進化的步長采用確定函數映射進行伸縮變化，其不能很好地反映進化過程的不確定性。本文基于云模型對不確定性問題良好的處理能力，通過利用云模型的不確定推理對CMA-ES步長控制進行改進，得到了一種基于云推理的CMA-ES改進算法。該算法利用云模型對不確定性問題良好的建模和推理能力來克服CMA-ES中步長確定性控制過程的不足，通過建立求解問題的步長控制云推理模型，來更好地處理和利用進化過程中的不確定性。最后通過測試函數的數值優化實驗，驗證了算法在求解成功率、求解精度、穩定性和收斂速度等方面的良好性能。

1　CMA-ES算法

CMA-ES算法是在進化策略(ES)算法的基礎上發展起來的一種算法，其繼承了基本ES的優點，并與高引導性的協方差矩陣結合起來。CMA-ES的主要操作是變異，變異操作通過采樣多維正態分布來實現，算法的實現過程為：

算法1CMA-ES算法

步驟1參數設置及初始化。設置求解問題的靜態參數λ、μ、wi=1,…,μ、cσ、dσ、c1、cc、cμ等；動態參數m∈RN，C=I∈RN×N，σ∈R+，進化路徑pσ=0，pc=0，代數g=0。

步驟2正態采樣。采樣多維正態分布生成由λ個個體組成的種群，采樣過程為：

(1)

步驟3評價與選擇。根據適應度函數逐個評價種群中的個體，并根據評價的結果進行排序，選出排名靠前的μ個個體組成當前最優子群。

步驟4根據步驟3的最優子群信息更新種群分布參數如下：

步驟4.1移動均值。均值m的更新計算如下：

(2)

步驟4.2協方差矩陣調整。

(3)

C(g+1)=(1-c1-cμ)C(g)+

(4)

步驟4.3全局步長控制。

(5)

(6)

步驟5判斷是否達到停止條件，若是，則停止，否則返回步驟2。

圖1　CMA-ES算法迭代尋優示意圖

2　云模型

云模型作為一種定性概念和定量數值之間的不確定性轉換模型，在知識表達時具有不確定中帶有確定性、穩定之中又有變化的特點，可以很好地表達進化知識。

2.1云模型的基本概念

定義1設U是一個用精確數值表示的定量論域，C是U上的一個定性概念，若定量值x∈U且x是定性概念C的一次隨機實現，x對C的確定度μ(x)∈[0,1]是有穩定傾向的隨機數，則x在論域U上的分布稱為云,每一個x稱為一個云滴。

云模型結合隨機性和模糊性，僅僅使用期望Ex、熵En和超熵He三個數字特征就勾畫出由大量云滴組成的云圖來表示一個定性概念，如圖 2所示，表示為C(Ex,En,He)。在多種云模型形態中，正態云模型具有普遍適應性[9]。

圖2　正態云圖及其數字特征

2.2云發生器

(1) 正向云發生器

正向云發生器實現從定性到定量的映射,它根據云模型的3個數字特征(Ex,En,He)產生滿足條件的一定數量的云滴[5]。

(2) 逆向云發生器

逆向云發生器是實現從定量到定性的映射，它可以將一定數量的精確數據轉換為用3個數字特征(Ex,En,He)表示的定性概念。在多種逆向云算法中，劉常昱等人[10]提出的無確定度逆向云算法在準確性和穩定性方面都優于現有的其他算法，應用最為廣泛。

(3) X條件云與Y條件云發生器

X條件云與Y條件云發生器構成了云推理規則的前件云和后件云。云規則發生器根據前件云CxA(ExA,EnA,HeA)，后件云CxB(ExB,EnB,HeB) 及前件云定量值xA產生滿足確定度μ的后件云滴drop(xB,μ)。“IfAThenB”的規則形式可以構成單條件單規則發生器，具體算法如下：

如果有多條“IfAThenB”的規則，則可以構成單條件多規則云發生器。對于某一個前件輸入定量值，如果激活多條云規則，則相應的后件有多個輸出定量值，可采取加權平均的方法得到一個最終的后件輸出定量值[11]。

3　基于云推理的變步長CMA-ES算法

圖3　CMA-ES中ρ與‖pσ‖的函數映射關系

3.1基于云推理的步長控制模型

基于云推理的步長控制過程主要是將算法1的步長控制過程替換為云推理步長控制過程，具體建模過程如下：

1) 確定輸入輸出概念：將‖pσ‖作為前件云概念，ρ作為后件云概念;

2) 概念程度劃分：將前件云概念劃分為“較小”、“適中”和“較大”3個等級；將后件云概念劃分為“減小”、“不變”和“增大”3個等級，從而得到3組控制規則：

規則1：如果‖pσ‖較小，則ρ減小；

規則2：如果‖pσ‖適中，則ρ不變；

規則3：如果‖pσ‖較大，則ρ增大。

3) 確定云參數：以CMA-ES運行過程中前件云概念和后件云概念的歷史數據作為輸入，通過逆向云算法確定前件云和后件云各等級概念的云參數。

通過上述步驟挖掘出的云規則可反映CMA-ES基本的步長控制規律，對規則云參數作進一步調整，從而得到最終的云推理規則庫。

3.2算法描述

根據3.1節的建模過程，本文的基于云推理的CMA-ES改進算法，命名為CR-CMA-ES算法，具體實現步驟如下：

算法2CR-CMA-ES算法

步驟1參數設置及初始化。執行算法1的步驟1。

步驟2CMA-ES尋優。執行算法1的步驟2、步驟3、步驟4.1和步驟4.2。

步驟3基于云推理的步長控制。確定求解問題的云推理步長控制規則，將根據式(5) 計算得到的‖pσ‖的大小作為云推理模型的輸入，推理的具體步驟為：

步驟3.1將輸入大小是否屬于概念的“3En”區間作為激活規則的依據，如果某條規則被激活，則計算該規則下的X條件云滴的確定度μi；

步驟3.2計算該規則下的滿足確定度為μi的Y條件云滴drop(yi,μi)；

步驟3.3采用加權平均的方法計算所有Y條件云滴的精確化輸出作為最終的輸出結果ρ；

步驟3.4全局步長更新，σ=σρ。

步驟4判斷是否達到停止條件，若是，則停止;否則返回步驟2。

圖4　單條件三規則云推理模型

總之，CR-CMA-ES算法的步長控制通過圖4所示的推理過程來實現。對于給定的前件定量值‖pσ‖，得到帶有不確定性的μ，后件云在該μ值的控制下，最終得到一個同樣不確定的后件定量值作為當前的ρ，從而實現了步長的不確定性更新與傳遞。

4　仿真實驗與分析

4.1測試函數

為了檢驗本文CR-CMA-ES算法的性能，選取了10個測試函數[12]進行數值優化實驗。表 1給出了各測試函數的函數名、維數、搜索空間、理論最優值等內容。其中，F1-F9為多峰函數，在搜索空間中有多個局部或全局極值，F1有760個局部極小值和18個全局最小值，F2有1個全局最小值和兩個局部極小值，F3的全局最小值非常靠近局部極小值，F4有6個局部極小值，F5-F9隨著維數的增加，具有大量的局部極值，這些函數常用來測試算法的全局探索與開采能力；F10為單峰函數，在搜索空間中只有一個全局最小值，是優化算法的經典測試函數。

表1　測試函數表

4.2參數設置

CMA-ES算法的初始均值m設為求解問題搜索空間內滿足均勻分布的一個隨機向量，初始全局步長σ設為搜索空間范圍的0.618倍，其他參數的設置見文獻[1]。CR-CMA-ES算法中云推理步長控制規則庫采用表 2所示的一組云模型控制參數，其中Ep為歸一化進化路徑在隨機選擇下的期望長度E(‖N(0,I)‖)，其他參數設置同CMA-ES。

兩種算法的停止條件均設置為求解誤差達到10-10或最大迭代次數達到1000。

表2　前件云與后件云實驗參數

4.3仿真結果與分析

將兩種算法分別獨立運行30次，得到表 3的測試結果。其中：Best表示30次獨立實驗中的最好值，Mean 表示平均值， STD 表示標準偏差，SR表示成功率。Mean 可以反映算法在給定最大迭代次數下的求解精度，STD可以反映算法的求解穩定性。

表3　兩種算法對10個測試函數的測試結果

從表 3中可以看出：對于F1、F2，CR-CMA-ES在求解精度和求解成功率上均優于CMA-ES，特別地，CR-CMA-ES的求解成功率可以達到100%；對于F3，在給定最大迭代次數下，兩種算法均未收斂到全局最優，但CR-CMA-ES可以很好地逼近全局最優解的鄰域；對于F4，CR-CMA-ES在求解成功率上得到進一步提高；對于F5和F6，CR-CMA-ES表現出100%的求解成功率，并獲得較高的求解精度；對于F7、F8和F9，兩種算法表現出相同的求解成功率和求解精度；對于F10，CR-CMA-ES的表現明顯優于CMA-ES，不僅在求解精度上得到大幅度提高，而且可以保持100%的求解成功率。通過STD的結果對比可以看出，CR-CMA-ES較CMA-ES表現出較高的求解穩定性。可見， CR-CMA-ES利用云模型良好的不確定性處理能力可以更好地控制步長，表現出較高的求解效率。

為了能更直觀地分析算法的性能，可分析算法的歸一化成功執行經驗分布圖[12]，如圖5所示。其中，SP(Success Performance)代表成功執行，為算法對某一測試函數求解成功時所需要的函數評價次數，具體的計算如下：

(7)

其中，#fevalsforsuccessfulruns代表所有成功運行的函數評價次數， #ofsuccessfulruns代表成功運行的次數，#ofallruns代表運行的總次數(如本文為30次)。SPbest為所有算法對該測試函數的SP的最小值，SP/SPbest為所有算法對該測試函數的歸一化成功執行。縱軸數據為橫軸數據SP/SPbest的經驗分布值，可反映求解的成功率。從圖5中可以看出：

1) CR-CMA-ES的分布曲線總是位于CMA-ES 之上，表明CR-CMA-ES較CMA-ES可以更好地解決這些優化問題；

2) 在SP/SPbest數值較小時，CR-CMA-ES較CMA-ES可以更快地收斂，說明CR-CMA-ES能夠以較少的評價次數來更好地解決這些優化問題。

圖5　兩種算法的歸一化成功執行經驗分布圖

總之，本文的CR-CMA-ES算法不僅在求解精度、穩定性上有明顯的提高，而且通過歸一化成功執行經驗分布圖可以看出，CR-CMA-ES在求解成功率和評價次數上也優于CMA-ES。

5　結　語

1)基本的CMA-ES算法中步長采用確定性函數映射進行伸縮變化，其在一定程度上忽略了進化過程的不確定性；

2)云模型具有良好的不確定性問題處理能力，能夠很好地對CMA-ES步長控制過程進行數據建模和規則提取；

3)采用基于云推理的步長控制方法可以更好地處理和利用進化過程的不確定性，從而更好地表達進化過程。測試驗證結果表明：CR-CMA-ES能夠提高求解成功率，并在求解精度、穩定性和收斂速度等方面得到進一步提高。

本文的步長控制云推理模型建模過程簡單，模型可靠，取得了較好的尋優效果。下一步將探索更好的步長控制云推理系統建模方法以及更優的云參數調整方法，并將其應用于更多問題的求解。

[1] Hansen N,Ostermeier A.Completely Derandomized Self-Adaption in Evolution Strategies[J].IEEE Transactions on Evolutionary Computation,2001,9(2):159-195.

[2] Auger A,Hansen N.A restart CMA evolution strategy with increasing population size[C]//The 2005 IEEE Congress on Evolutionary Computation,2005,2:1769-1776.

[3] 黃亞飛,梁昔明,陳義雄.求解全局優化問題的正交協方差矩陣自適應進化策略算法[J].計算機應用,2012,32(4):981-985.

[4] Ros R,Hansen N.Parallel Problem Solving from Nature-PPSN X[M].Springer Berlin Heidelberg,2008.

[5] 李德毅,杜鹢.不確定性人工智能[M].北京:國防工業出版社,2005．

[6] 戴朝華,朱云芳,陳維榮,等.云遺傳算法及其應用[J].電子學報,2007,35(7):1419-1424.

[7] 張光衛,何銳,劉禹,等.基于云模型的進化算法[J].計算機學報,2008,31(7):1082-1091.

[8] 韋杏瓊,周永權,黃華娟,等.云自適應粒子群算法[J].計算機工程與應用,2009,45(1):48-50.

[9] 李德毅,劉常昱.論正態云模型的普適性[J].中國工程科學,2004,6(8):28-34.

[10] 劉常昱,馮芒,戴曉軍.基于云X 信息的逆向云新算法[J].系統仿真學報,2004,16(11):2417-2420.

[11] 陳昊,李兵.基于云模型的不確定性推理方法[J].小型微型計算機系統,2011,12(32):2449-2455.

[12] Karaboga D,Akay B.A comparative study of Artificial Bee Colony algorithm[J].Applied Mathematics & Computation,2009,214(1):108-132.

[13] Hansen N.Compilation of results on the 2005 CEC benchmark function set[OL].Online,2006.

IMPROVED CMA-ES ALGORITHM BASED ON CLOUD REASONING

Qiao ShuaiXu XinyingYan Gaowei

(CollegeofInformationEngineering,TaiyuanUniversityofTechnology,Taiyuan030024,Shanxi,China)

In order to overcome the shortcomings of covariance matrix adaptation evolution strategy (CMA-ES) such as premature convergence and low precision when being used in some optimisation problems,by making use of the good ability of cloud model in dealing with uncertainty problems,we improve the step-size control process of CMA-ES and find a cloud reasoning-based improved CMA-ES algorithm.After building the cloud reasoning model of step-size control,the improved algorithm achieves step-size control by using uncertainty reasoning of cloud model,and avoids the deficiency of original algorithm that it uses deterministic function mapping for step-size scale but ignores the uncertainty in evolution process.Finally,through test functions we verify that the improved algorithm has higher optimisation performance.

Covariance matrix adaptation evolution strategy (CMA-ES)Cloud reasoningStep-size controlGlobal optimisation

2015-03-27。國家自然科學基金項目(61450011);山西省自然科學基金項目(2011011012-2)。喬帥，碩士生，主研領域：智能信息處理與進化計算。續欣瑩，副教授。閻高偉，教授。

TP306.1

A

10.3969/j.issn.1000-386x.2016.08.054