基于Minmax算法的混沌MIMIC算法

趙晉彬，夏桂梅

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

分布估計(jì)算法(EDAs)的基本思想是利用變量間的概率分布來(lái)表示變量之間的相關(guān)關(guān)系，并經(jīng)過(guò)迭代進(jìn)化，逼近問(wèn)題的最優(yōu)值，降低了對(duì)問(wèn)題先驗(yàn)知識(shí)的要求，是一個(gè)很好的連鎖學(xué)習(xí)算法[1]。

對(duì)優(yōu)化算法進(jìn)行改進(jìn)以提高算法優(yōu)化效率的能力是進(jìn)化計(jì)算領(lǐng)域的熱門研究課題。將算法進(jìn)行融合，構(gòu)建混合算法是算法改進(jìn)的常用途徑?；旌纤惴梢匀诤隙喾N優(yōu)化算法的優(yōu)勢(shì)，提高算法的性能，更好地平衡算法的收斂性和群體多樣性。DE/EDA[2]將差分進(jìn)化算法與分布估計(jì)算法相結(jié)合，解決了連續(xù)域中的全局優(yōu)化問(wèn)題，研究表明DE/EDA要優(yōu)于DE和EDA算法。PSO-MIMIC算法將微粒群算法(PSO)和分布估計(jì)算法相結(jié)合，保持群體多樣性的同時(shí)，具備更好的收斂能力，并結(jié)合罰函數(shù)法應(yīng)用于約束優(yōu)化問(wèn)題，效果顯著[3]。

首先將分布估計(jì)算法與混沌算法[4]進(jìn)行結(jié)合，提出混沌MIMIC算法(CS-MIMIC)，實(shí)驗(yàn)證明該算法可以收斂到無(wú)約束函數(shù)的最優(yōu)解[5]。

在生產(chǎn)和實(shí)際優(yōu)化設(shè)計(jì)中，大多優(yōu)化問(wèn)題為非線性約束優(yōu)化問(wèn)題，其數(shù)學(xué)模型可以表述為[6]：

minf(x)，x∈D

(1)

其中D是可行域。由于混沌MIMIC算法可以大概率搜索到測(cè)試函數(shù)的閾值，對(duì)于以上問(wèn)題，本文給出另一種思路，就是通過(guò)Minmax算法將原問(wèn)題轉(zhuǎn)換為無(wú)約束問(wèn)題，并利用混沌MIMIC算法進(jìn)行迭代搜索，提出基于Minmax算法的混沌MIMIC算法(MxCS-MIMIC)。

1 MxCS-MIMIC

1.1 MIMIC算法

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

1.2 混沌算法(CS)

在混沌算法中，通常選擇Logistic映射所產(chǎn)生決策變量，其形式如下[9]：

(2)

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

混沌算法步驟如下：

1.3 Minmax算法

約束優(yōu)化問(wèn)題因?yàn)楸旧砭哂屑s束條件，使得求解此類問(wèn)題，具有一定的難度，應(yīng)用某種方法將其轉(zhuǎn)換為無(wú)約束問(wèn)題，是一種常見(jiàn)的解決方式。Minmax算法是一種可以解決這類問(wèn)題的方法[13]。Minmax一般定義：

約束問(wèn)題函數(shù):

minF(x)

s.t.gi(x)≤0，i=1，…，m

(3)

轉(zhuǎn)化后的無(wú)約束問(wèn)題函數(shù)：

(4)

其中，αi(αi>0)為參數(shù)，類似于罰函數(shù)中的罰參數(shù)μ.能夠證明式(3)問(wèn)題對(duì)充分大的αi等價(jià)于式(4)問(wèn)題。

1.4 MSCS-MIMIC算法

算法實(shí)現(xiàn)過(guò)程如下：

步1：隨機(jī)生成若干個(gè)體組成初始種群N；

步2：利用Minmax算法將約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題；

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

步4：使用截?cái)噙x擇、輪賭選擇，將S個(gè)變量選出作為主導(dǎo)變量群體，其中S=N/2；

步5：按照貪婪算法構(gòu)建優(yōu)勢(shì)模型[14]：

(1)根據(jù)in=argminjhl(Xj)找出排列π=(i1，i2，…，in)中的in

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

步6：用混沌算法對(duì)優(yōu)勢(shì)群體進(jìn)行搜索，對(duì)搜索后的優(yōu)化值進(jìn)行評(píng)價(jià)，并更新已知的最優(yōu)值；

步7：合并種群，將根據(jù)模型產(chǎn)生的優(yōu)勢(shì)值與保留的優(yōu)勢(shì)群體組成新的種群，轉(zhuǎn)到步2.

2 算法性能測(cè)試及分析

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

為檢測(cè)算法的性能，對(duì)下面六個(gè)約束函數(shù)進(jìn)行檢驗(yàn)[15]。

在實(shí)驗(yàn)中，MIMIC算法的參數(shù)設(shè)置如下：群體數(shù)量N=300，截?cái)噙x擇為N/2，最大迭代次數(shù)范圍[10，50]，這里選擇30次?；煦缢惴▍?shù)設(shè)置如下：迭代次數(shù)為30次，對(duì)優(yōu)勢(shì)群體的20%進(jìn)行迭代實(shí)驗(yàn)。

函數(shù)1：

minf(x)=(x1-2)2+(x2-1)2

函數(shù)2：

minf(x)=(x1-10)2+5(x2-12)2+

4x6x7-10x6-8x7

函數(shù)3：

函數(shù)4：

函數(shù)5：

函數(shù)6：

37.293 239x1-407 92.141

0≤85.334 407+0.005 685 8x2x5+

0.000 26x1x4-0.002 205 3x3x5≤92

s.t.90≤80.512 49+0.007 131 7x2x5+

20≤9.300 961+0.004 702 6x3x5+

0.001 254 7x1x3+0.001 908 5x3x4≤25

78≤x1≤102，33≤x2≤45，

27≤xi≤45，i=3，4，5

2.2 實(shí)驗(yàn)結(jié)果及分析

本文將從兩種情況分析算法的性能，并與結(jié)合了Minmax法的MIMIC算法進(jìn)行比較。

由于6個(gè)函數(shù)在維數(shù)、運(yùn)算復(fù)雜度和約束條件上有所不同，因此針對(duì)不同的函數(shù)，算法進(jìn)化代數(shù)上也做出了相應(yīng)的調(diào)整。在經(jīng)過(guò)大量的實(shí)驗(yàn)運(yùn)算之后，本文找出MxCS-MIMIC算法在測(cè)試6個(gè)函數(shù)能達(dá)到最優(yōu)值(或算法陷入局部最優(yōu))時(shí)，算法所設(shè)置的固定進(jìn)化代數(shù)如下：Nf1=100，Nf2=150，Nf3=50，Nf4=200，Nf5=50，Nf6=500.

(1)算法能否收斂到函數(shù)的最優(yōu)值

表1所示是算法在經(jīng)過(guò)30次迭代后的數(shù)據(jù)結(jié)果。可以看出，對(duì)于6個(gè)測(cè)試函數(shù)，MxCS-MIMIC算法找到了函數(shù)1、3、5的最優(yōu)值，MIMIC算法找到了函數(shù)3、5的最優(yōu)值，以及函數(shù)1的近似值；對(duì)于函數(shù)2、4，MxCS-MIMIC算法搜索到了最優(yōu)值附近，且誤差較小，MIMIC算法也搜索到了最優(yōu)值附近，并且函數(shù)2的誤差比MxCS-MIMIC小，函數(shù)4的誤差比MxCS-MIMIC大；對(duì)于函數(shù)6，算法在經(jīng)過(guò)500代更新后，兩種算法都未找到最優(yōu)值，但是MxCS-MIMIC算法比較接近最優(yōu)值，MIMIC算法在500代內(nèi)并沒(méi)有得出較好的結(jié)果。

表1 兩種算法優(yōu)化所得結(jié)果Tab.1 The optimization results of the two algorithms

(2)算法的平均進(jìn)化代數(shù)

表2是算法在經(jīng)過(guò)30次迭代后的平均進(jìn)化代數(shù)，可以看出，相較于結(jié)合了Minmax法的MIMIC算法，MxCS-MIMIC算法在尋優(yōu)能力較強(qiáng)的情況下，運(yùn)用了較少的進(jìn)化代數(shù)達(dá)到了最優(yōu)值，這與算法結(jié)合了混沌算法，提高了算法的收斂效率是分不開(kāi)的。

表2 到達(dá)確定最優(yōu)值的平均進(jìn)化代數(shù)Tab.2 Average evolution algebra to determine optimal value

3 結(jié)論

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