基于變尺度搜索算法的混沌MIMIC算法

趙晉彬,夏桂梅

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院,山西 太原 030024)

分布估計算法(EDAs)的基本思想是利用變量間的概率分布來表示變量之間的相關(guān)關(guān)系,并經(jīng)過迭代進(jìn)化,迫近問題的最優(yōu)值,降低了對問題先驗知識的要求,是一個很好的連鎖學(xué)習(xí)算法[1]。混沌算法是一種收斂較快的優(yōu)化算法,具有遍歷性和隨機(jī)性。這樣的特征,可用于局部優(yōu)化,但它有初值選擇的敏感性,因此傳統(tǒng)的混沌算法對目標(biāo)難以瞄準(zhǔn)。變尺度搜索可以縮小搜索區(qū)間,使得算法更容易找到最優(yōu)解[2]。在MIMIC算法和混沌搜索算法結(jié)合的前提下,引入變尺度搜索,優(yōu)化搜索空間,提出基于變尺度搜索算法的混沌MIMIC算法(MSCS-MIMIC)。

1 MSCS-MIMIC

1.1 MIMIC算法

MIMIC算法是一個在雙變量相關(guān)、鏈?zhǔn)浇Y(jié)構(gòu)依賴假設(shè)基礎(chǔ)上提出的分布估計算法,其概率圖模型如圖1所示[3]。

圖1 MIMIC的概率圖模型Fig.1 Probabilistic graphical model of MIMIC

1.2 混沌算法(CS)

在混沌優(yōu)化算法中,通常選擇Logistic映射所產(chǎn)生決策變量,其形式如下[4-5]:

(1)

其中:μ為操控參數(shù),當(dāng)μ=4時,處于完全混沌的狀態(tài),且xn在(0,1)范圍內(nèi)是遍歷的。

混沌搜索算法步驟如下:

1.3 變尺度搜索(MS)

1.3.1搜索空間映射

由Logistic映射所產(chǎn)生的決策變量xn∈[0,1]必須映射到向量空間,即混沌搜索的上限和下限[a,b]。本文采用的映射公式如下[6]:

x′n=ci+dixn

(2)

式中，ci和di為與邊界有關(guān)的系數(shù),ci=a，di=b-a.

1.3.2變尺度搜索

以當(dāng)前最優(yōu)解x*為中心,通過[7-9]

(3)

(4)

(5)

將式(5)和a=ci，b=ci+di分別代入式(3)即得式(2)。

圖2 變尺度搜索示意圖Fig.2 Schematic diagram of mutative scale optimizing search

1.4 MSCS-MIMIC算法

混沌搜索算法與MIMIC算法結(jié)合,旨在解決MIMIC算法局部搜索問題和CS算法對初值的高要求問題[10-11],在算法中引入變尺度搜索,可以重構(gòu)優(yōu)化變量取值空間,大大提高了結(jié)果的準(zhǔn)確性。

算法實現(xiàn)過程如下:

步驟1:隨機(jī)生成若干個體組成初始種群N。

步驟2:評估初始群N,如果連續(xù)搜索至相同值或找到最終的最優(yōu)解,算法結(jié)束,否則進(jìn)入下一步驟。

步驟3:使用截斷選擇、輪賭選擇,將S個變量選出作為主導(dǎo)變量群,其中S=N/2。

步驟4:按照貪婪算法構(gòu)建優(yōu)勢模型:

a.根據(jù)in=argminjhl(Xj)找出排列π=(i1,i2,…,in)中的in；

b.對任意k=n-1,…，1,根據(jù)ik=argminjhl(Xj|Xk+1),其中k≠ik+1…,in，計算出排列π=(i1,i2，…,in)；

步驟5:優(yōu)勢群體用CS算法進(jìn)行搜索,對搜索后的優(yōu)化值進(jìn)行評價,并更新已知的最優(yōu)值[12]。

步驟6:使用變尺度方法略微減小變量的取值區(qū)間,即以當(dāng)前最優(yōu)解為中心,通過(3)式所述,調(diào)整ci和di來重構(gòu)優(yōu)化變量的值空間。

步驟7:合并種群,將根據(jù)模型產(chǎn)生的優(yōu)勢變量與保留的優(yōu)勢群體組成新的種群,轉(zhuǎn)到步2。

2 算法性能測試及分析

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

為檢測新算法的性能,并與CS-MIMIC算法、MIMIC算法比對,對下面6個無約束函數(shù)進(jìn)行檢驗[13]。

在實驗中,MIMIC算法的參數(shù)設(shè)置如下[14]:群體數(shù)量N=300,截斷選擇為N/2,最大迭代次數(shù)范圍[10,50],這里選擇30次。進(jìn)行混沌搜索法的迭代次數(shù)為30次,對優(yōu)勢群體的20%進(jìn)行迭代實驗。

函數(shù)1:

minf(x)=f(1,1,…,1)=0

函數(shù)2:

minf(x)=f(0,0,…,0)=-105

函數(shù)3:

函數(shù)4:

minf(x)=f(0,0,…,0)=0

函數(shù)5:

minf(x)=f(0,0,…,0)=0

2.2 實驗結(jié)果及分析

本文通過三種情況對實驗數(shù)據(jù)進(jìn)行歸納總結(jié),得出MSCS-MIMIC算法的優(yōu)勢。

1)在種群更新代數(shù)、迭代次數(shù)以及維數(shù)相同的情況下,三種算法是不是能夠收斂到最優(yōu)解。本文取更新代數(shù)為200,迭代次數(shù)30次,維數(shù)M=2。

表1 200代內(nèi)算法優(yōu)化所得結(jié)果Table 1 The results of optimization within 200 generations

表1顯示了三種算法進(jìn)行30次獨立實驗的結(jié)果?？梢钥闯?對于測試函數(shù)f1,MIMIC算法收斂到了最優(yōu)值,而MSCS-MIMIC算法以CS-MIMIC算法更高的精度收斂到最優(yōu)值附近,說明引入變尺度算法提高了新算法的收斂能力。其余函數(shù),第一、二種算法的搜索結(jié)果對應(yīng)于函數(shù)的最佳值,而MIMIC算法只找到了f2的最佳值。

2)在維數(shù)不變的情況下,算法運行結(jié)束后進(jìn)化代數(shù)的均值。取維數(shù)M=2,進(jìn)化代數(shù)為200。

表2 到達(dá)確定最優(yōu)值的平均進(jìn)化代數(shù)

表2是三種算法平均進(jìn)化代數(shù)的比較結(jié)果。可以看出,MSCS-MIMIC算法的結(jié)果都較小,其中對于函數(shù)1,MSCS-MIMIC算法精度更高的前提下,算法的平均進(jìn)化代數(shù)更小,這與算法中引入混沌搜索算法有很大的關(guān)系。而且在其余函數(shù)的試驗中,MSCS-MIMIC算法都在收斂到最優(yōu)值的前提下,運行了更少的進(jìn)化代數(shù)。

3 結(jié)論

基于變尺度搜索算法的混沌MIMIC算法(MSCS-MIMIC)不僅繼承了CS-MIMIC算法尋優(yōu)能力高和運行速度快的特點,此外它還提升了算法的細(xì)化能力和穩(wěn)定性,是一種有效的優(yōu)化算法。從兩組實驗得出的數(shù)據(jù)可以看出,結(jié)合了變尺度搜索算法的混沌MIMIC算法能夠以較高的精度收斂到最優(yōu)值附近,或者直接收斂到全局最優(yōu)值,并且最優(yōu)值可以在較小的進(jìn)化代數(shù)內(nèi)找到,這對改進(jìn)類似優(yōu)化算法提出一種新的嘗試。