基于云推理的協(xié)方差矩陣自適應(yīng)進(jìn)化策略算法

喬　帥　續(xù)欣瑩　閻高偉

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

?

基于云推理的協(xié)方差矩陣自適應(yīng)進(jìn)化策略算法

喬帥續(xù)欣瑩閻高偉

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

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

協(xié)方差矩陣自適應(yīng)進(jìn)化策略云推理步長控制全局優(yōu)化

0　引　言

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

目前，許多學(xué)者從不同的角度對(duì)算法進(jìn)行了改進(jìn)。文獻(xiàn)[2]為算法設(shè)置重啟，通過動(dòng)態(tài)地增大種群規(guī)模來獲得較強(qiáng)的全局搜索性能；文獻(xiàn)[3]通過正交設(shè)計(jì)構(gòu)造正交試驗(yàn)向量來引導(dǎo)算法跳出局部最優(yōu)；文獻(xiàn)[4]通過限制協(xié)方差矩陣為對(duì)角陣來降低算法的時(shí)空復(fù)雜度。

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

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

1　CMA-ES算法

CMA-ES算法是在進(jìn)化策略(ES)算法的基礎(chǔ)上發(fā)展起來的一種算法，其繼承了基本ES的優(yōu)點(diǎn)，并與高引導(dǎo)性的協(xié)方差矩陣結(jié)合起來。CMA-ES的主要操作是變異，變異操作通過采樣多維正態(tài)分布來實(shí)現(xiàn)，算法的實(shí)現(xiàn)過程為：

算法1CMA-ES算法

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

步驟2正態(tài)采樣。采樣多維正態(tài)分布生成由λ個(gè)個(gè)體組成的種群，采樣過程為：

(1)

步驟3評(píng)價(jià)與選擇。根據(jù)適應(yīng)度函數(shù)逐個(gè)評(píng)價(jià)種群中的個(gè)體，并根據(jù)評(píng)價(jià)的結(jié)果進(jìn)行排序，選出排名靠前的μ個(gè)個(gè)體組成當(dāng)前最優(yōu)子群。

步驟4根據(jù)步驟3的最優(yōu)子群信息更新種群分布參數(shù)如下：

步驟4.1移動(dòng)均值。均值m的更新計(jì)算如下：

(2)

步驟4.2協(xié)方差矩陣調(diào)整。

(3)

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

(4)

步驟4.3全局步長控制。

(5)

(6)

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

圖1　CMA-ES算法迭代尋優(yōu)示意圖

2　云模型

云模型作為一種定性概念和定量數(shù)值之間的不確定性轉(zhuǎn)換模型，在知識(shí)表達(dá)時(shí)具有不確定中帶有確定性、穩(wěn)定之中又有變化的特點(diǎn)，可以很好地表達(dá)進(jìn)化知識(shí)。

2.1云模型的基本概念

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

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

圖2　正態(tài)云圖及其數(shù)字特征

2.2云發(fā)生器

(1) 正向云發(fā)生器

正向云發(fā)生器實(shí)現(xiàn)從定性到定量的映射,它根據(jù)云模型的3個(gè)數(shù)字特征(Ex,En,He)產(chǎn)生滿足條件的一定數(shù)量的云滴[5]。

(2) 逆向云發(fā)生器

逆向云發(fā)生器是實(shí)現(xiàn)從定量到定性的映射，它可以將一定數(shù)量的精確數(shù)據(jù)轉(zhuǎn)換為用3個(gè)數(shù)字特征(Ex,En,He)表示的定性概念。在多種逆向云算法中，劉常昱等人[10]提出的無確定度逆向云算法在準(zhǔn)確性和穩(wěn)定性方面都優(yōu)于現(xiàn)有的其他算法，應(yīng)用最為廣泛。

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

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

如果有多條“IfAThenB”的規(guī)則，則可以構(gòu)成單條件多規(guī)則云發(fā)生器。對(duì)于某一個(gè)前件輸入定量值，如果激活多條云規(guī)則，則相應(yīng)的后件有多個(gè)輸出定量值，可采取加權(quán)平均的方法得到一個(gè)最終的后件輸出定量值[11]。

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

圖3　CMA-ES中ρ與‖pσ‖的函數(shù)映射關(guān)系

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

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

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

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

規(guī)則1：如果‖pσ‖較小，則ρ減??；

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

規(guī)則3：如果‖pσ‖較大，則ρ增大。

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

通過上述步驟挖掘出的云規(guī)則可反映CMA-ES基本的步長控制規(guī)律，對(duì)規(guī)則云參數(shù)作進(jìn)一步調(diào)整，從而得到最終的云推理規(guī)則庫。

3.2算法描述

根據(jù)3.1節(jié)的建模過程，本文的基于云推理的CMA-ES改進(jìn)算法，命名為CR-CMA-ES算法，具體實(shí)現(xiàn)步驟如下：

算法2CR-CMA-ES算法

步驟1參數(shù)設(shè)置及初始化。執(zhí)行算法1的步驟1。

步驟2CMA-ES尋優(yōu)。執(zhí)行算法1的步驟2、步驟3、步驟4.1和步驟4.2。

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

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

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

步驟3.3采用加權(quán)平均的方法計(jì)算所有Y條件云滴的精確化輸出作為最終的輸出結(jié)果ρ；

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

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

圖4　單條件三規(guī)則云推理模型

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

4　仿真實(shí)驗(yàn)與分析

4.1測試函數(shù)

為了檢驗(yàn)本文CR-CMA-ES算法的性能，選取了10個(gè)測試函數(shù)[12]進(jìn)行數(shù)值優(yōu)化實(shí)驗(yàn)。表 1給出了各測試函數(shù)的函數(shù)名、維數(shù)、搜索空間、理論最優(yōu)值等內(nèi)容。其中，F(xiàn)1-F9為多峰函數(shù)，在搜索空間中有多個(gè)局部或全局極值，F(xiàn)1有760個(gè)局部極小值和18個(gè)全局最小值，F(xiàn)2有1個(gè)全局最小值和兩個(gè)局部極小值，F(xiàn)3的全局最小值非?？拷植繕O小值，F(xiàn)4有6個(gè)局部極小值，F(xiàn)5-F9隨著維數(shù)的增加，具有大量的局部極值，這些函數(shù)常用來測試算法的全局探索與開采能力；F10為單峰函數(shù)，在搜索空間中只有一個(gè)全局最小值，是優(yōu)化算法的經(jīng)典測試函數(shù)。

表1　測試函數(shù)表

4.2參數(shù)設(shè)置

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

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

表2　前件云與后件云實(shí)驗(yàn)參數(shù)

4.3仿真結(jié)果與分析

將兩種算法分別獨(dú)立運(yùn)行30次，得到表 3的測試結(jié)果。其中：Best表示30次獨(dú)立實(shí)驗(yàn)中的最好值，Mean 表示平均值， STD 表示標(biāo)準(zhǔn)偏差，SR表示成功率。Mean 可以反映算法在給定最大迭代次數(shù)下的求解精度，STD可以反映算法的求解穩(wěn)定性。

表3　兩種算法對(duì)10個(gè)測試函數(shù)的測試結(jié)果

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

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

(7)

其中，#fevalsforsuccessfulruns代表所有成功運(yùn)行的函數(shù)評(píng)價(jià)次數(shù)， #ofsuccessfulruns代表成功運(yùn)行的次數(shù)，#ofallruns代表運(yùn)行的總次數(shù)(如本文為30次)。SPbest為所有算法對(duì)該測試函數(shù)的SP的最小值，SP/SPbest為所有算法對(duì)該測試函數(shù)的歸一化成功執(zhí)行?？v軸數(shù)據(jù)為橫軸數(shù)據(jù)SP/SPbest的經(jīng)驗(yàn)分布值，可反映求解的成功率。從圖5中可以看出：

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

2) 在SP/SPbest數(shù)值較小時(shí)，CR-CMA-ES較CMA-ES可以更快地收斂，說明CR-CMA-ES能夠以較少的評(píng)價(jià)次數(shù)來更好地解決這些優(yōu)化問題。

圖5　兩種算法的歸一化成功執(zhí)行經(jīng)驗(yàn)分布圖

總之，本文的CR-CMA-ES算法不僅在求解精度、穩(wěn)定性上有明顯的提高，而且通過歸一化成功執(zhí)行經(jīng)驗(yàn)分布圖可以看出，CR-CMA-ES在求解成功率和評(píng)價(jià)次數(shù)上也優(yōu)于CMA-ES。

5　結(jié)　語

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

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

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

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

[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] 黃亞飛,梁昔明,陳義雄.求解全局優(yōu)化問題的正交協(xié)方差矩陣自適應(yīng)進(jìn)化策略算法[J].計(jì)算機(jī)應(yīng)用,2012,32(4):981-985.

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

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

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

[7] 張光衛(wèi),何銳,劉禹,等.基于云模型的進(jìn)化算法[J].計(jì)算機(jī)學(xué)報(bào),2008,31(7):1082-1091.

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

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

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

[11] 陳昊,李兵.基于云模型的不確定性推理方法[J].小型微型計(jì)算機(jī)系統(tǒng),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。國家自然科學(xué)基金項(xiàng)目(61450011);山西省自然科學(xué)基金項(xiàng)目(2011011012-2)。喬帥，碩士生，主研領(lǐng)域：智能信息處理與進(jìn)化計(jì)算。續(xù)欣瑩，副教授。閻高偉，教授。

TP306.1

A

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