結(jié)合模式搜索法的混合MIMIC算法

張 丹,夏桂梅

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

?

結(jié)合模式搜索法的混合MIMIC算法

張 丹,夏桂梅

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

分布估計(jì)算法是一種全局尋優(yōu)能力較強(qiáng)而局部求精能力較弱的優(yōu)化算法，為增強(qiáng)分布估計(jì)算法的局部尋優(yōu)能力，將局部求精能力強(qiáng)，收斂速度快的模式搜索法引入到分布估計(jì)算法中，提出一種結(jié)合模式搜索法的混合MIMIC算法(PS-MIMIC).通過(guò)測(cè)試函數(shù)測(cè)試算法性能，并與標(biāo)準(zhǔn)MIMIC算法結(jié)果進(jìn)行比較，結(jié)果表明該算法在解決優(yōu)化問(wèn)題時(shí)具有良好的性能，可以較快的尋找到最優(yōu)值。

分布估計(jì)算法；模式搜索法；MIMIC算法

分布估計(jì)算法(EDA)源于遺傳算法，是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的群體進(jìn)化算法[1]，最早在1996年提出并得到了迅猛的發(fā)展，目前已經(jīng)成為人工智能領(lǐng)域的研究熱點(diǎn)[2]。它的基本思想是從初始群體中選擇一部分優(yōu)秀個(gè)體，通過(guò)對(duì)當(dāng)前優(yōu)秀個(gè)體集合建立概率模型來(lái)指導(dǎo)新群體的生成，如此反復(fù)進(jìn)行，直到搜索到問(wèn)題的滿(mǎn)意解。概率分布的模型有很多種，目前，根據(jù)變量之間的相關(guān)性，分布估計(jì)算法可以分為變量無(wú)關(guān)分布估計(jì)算法，雙變量相關(guān)分布估計(jì)算法和多變量相關(guān)分布估計(jì)算法[3]。

由于分布估計(jì)算法的過(guò)程是一個(gè)不斷更新概率模型，從而使概率模型越來(lái)越能反映優(yōu)秀個(gè)體的分布的過(guò)程，所以在進(jìn)化過(guò)程中，容易對(duì)解空間分布過(guò)于依靠，導(dǎo)致算法在后期的進(jìn)化過(guò)程中速度變慢，種群的多樣性減少，這說(shuō)明分布估計(jì)算法具有比較強(qiáng)的全局搜索能力，但是局部求精能力弱。為了有效提高分布估計(jì)算法的求精能力，可以在分布估計(jì)算法中加入其他優(yōu)化算法，例如文獻(xiàn)[4]在分布估計(jì)算法的基礎(chǔ)上加進(jìn)了微粒群算法，文獻(xiàn)[5]是基于罰函數(shù)的分布估計(jì)算法。本文是在種群的進(jìn)化過(guò)程中加入了局部求精能力強(qiáng)，收斂速度快的模式搜索法(Pattern Search)，提出一種結(jié)合模式搜索法的分布估計(jì)算法(PS-MIMIC).

1 PS-MIMIC

1.1 模式搜索法

模式搜索法又叫Hooke-Jeeves方法[6]，是Hooke和Jeevs在1996年提出的。模式搜索法是對(duì)當(dāng)前迭代點(diǎn)按照固定模式和步長(zhǎng)進(jìn)行探索移動(dòng)，來(lái)尋求函數(shù)的下降方向的直接搜索方法，它不必要求目標(biāo)函數(shù)必須連續(xù)或者可導(dǎo)，是求解求導(dǎo)麻煩或者不可導(dǎo)優(yōu)化問(wèn)題的一種有效方法[7]。如文獻(xiàn)[8]，文獻(xiàn)[9]，和文獻(xiàn)[10]都是模式搜索法的應(yīng)用。

模式搜索法的基本思想是：算法從某個(gè)初始點(diǎn)開(kāi)始，交替進(jìn)行軸向移動(dòng)和模式移動(dòng)。軸向移動(dòng)是依次沿n個(gè)坐標(biāo)軸的方向進(jìn)行，目的是確定新的基點(diǎn)和有利于函數(shù)值下降的方向。模式移動(dòng)是沿著相鄰兩個(gè)基點(diǎn)的連線(xiàn)方向進(jìn)行，目的則是沿著有利方向加速運(yùn)動(dòng)[4]。

模式搜索算法的步驟如下：

步2 令y=xk；

步3 從y出發(fā)，依次作平行于單位矢量ej(j=1,…,n)的軸向探測(cè)移動(dòng)：

步4 令xk+1=y，若f(xk+1)

1.2 MIMIC算法

MIMIC(Mutual Information Maximization for Input Clustering)算法，即輸入聚類(lèi)最大互信息算法，是在1997年由美國(guó)MIT人工智能實(shí)驗(yàn)室的De Bonet等人提出的一種雙變量分布估計(jì)算法[11]。在此算法中，用鏈?zhǔn)浇Y(jié)構(gòu)描述變量之間的關(guān)系，如下圖所示:

設(shè)隨機(jī)變量集合x(chóng)=(x1,x2,…,xn)的聯(lián)合概率分布是p(x)=p(x1,x2,…,xn)，即有

p(x)=p(x1|x2,…,xn)p(x2|x3,…xn)…

p(xn-1|xn)p(xn)

算法中解空間的概率模型描述為：

其中，h(X) = -∑xP(X=x)logp (X=x)，

h(X|Y)=-∑yh(X|Y=y)p(Y=y)，

h(X|Y=y)=

1.3 PS-MIMIC

模式搜索法是一種局部搜索算法，具有較強(qiáng)的局部求精能力，而MIMIC算法的全局搜索能力強(qiáng)，局部搜索能力較弱，所以在MIMIC算法進(jìn)化過(guò)程中可以加入模式搜索算法來(lái)提高算法的尋優(yōu)能力和效率。在MIMIC算法中，由于新個(gè)體的產(chǎn)生規(guī)則單一，導(dǎo)致新群體個(gè)性差異較小，為了增加種群的個(gè)性差異，同時(shí)又不背離群體的分布模型，在生成新的群體時(shí)，從當(dāng)前群體中隨機(jī)選擇出部分個(gè)體進(jìn)行模式搜索，將得到的新個(gè)體作為新群體中的一部分。具體步驟如下：

步1 初始化群體。隨機(jī)產(chǎn)生N個(gè)個(gè)體作為初始群體。

步2 評(píng)價(jià)適應(yīng)值。計(jì)算種群中每個(gè)個(gè)體的適應(yīng)值，若滿(mǎn)足算法終止條件，則算法結(jié)束，否則轉(zhuǎn)下一步。算法的終止條件為達(dá)到規(guī)定的進(jìn)化代數(shù)(500代)，或者連續(xù)若干代(25代)最優(yōu)值沒(méi)有變化，或者誤差在某個(gè)范圍內(nèi)(10-50)。對(duì)于約束問(wèn)題，利用罰函數(shù)法轉(zhuǎn)化為無(wú)約束問(wèn)題。

步3 選擇優(yōu)勢(shì)群體。采用截?cái)喾ê洼啽P(pán)賭法選擇S(N/2)個(gè)個(gè)體作為優(yōu)勢(shì)群體，并保留p個(gè)最優(yōu)個(gè)體。

步4 模式搜索法搜索。從當(dāng)前群體中選擇T個(gè)個(gè)體作為初始點(diǎn)進(jìn)行模式搜索，將得到的新個(gè)體作為新一代群體的一部分。

步5 根據(jù)貪婪算法尋找最優(yōu)排列構(gòu)建概率模型。

(3)計(jì)算出概率分布

pl(xi1|xi2)pl(xi2|xi3)…pl(xin-1|xin)pl(xin)

步6 采樣得到新個(gè)體。按逆序的方法依據(jù)概率模型采樣N-T-p次，與步3保留的p個(gè)最優(yōu)個(gè)體及模式搜索法得到的T個(gè)個(gè)體組成新一代群體，轉(zhuǎn)步2.

2 數(shù)值實(shí)驗(yàn)

2.1 測(cè)試函數(shù)

為了測(cè)試算法性能，并與基本的MIMIC算法進(jìn)行比較，對(duì)下面四個(gè)測(cè)試函數(shù)[12]進(jìn)行測(cè)試。

-10≤xi≤10

-5.12≤xi≤5.12

-10≤xi≤10

-600≤xi≤600

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

在實(shí)驗(yàn)中，算法的參數(shù)設(shè)置如下，群體規(guī)模N=200，截?cái)噙x擇S=N/2，保留最優(yōu)個(gè)體數(shù)p=20，進(jìn)行模式搜索法的初始點(diǎn)個(gè)數(shù)T=50，最大迭代次數(shù)500，精度10-6，加速系數(shù)γ=1.4，收縮系數(shù)θ=0.2，分別進(jìn)行30次實(shí)驗(yàn)。

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

為了測(cè)試PS-MIMIC的性能，本文采用如下三種性能指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

(1)在固定進(jìn)化代數(shù)內(nèi)，算法得到的最優(yōu)值及平均最優(yōu)值，本文采取固定進(jìn)化代數(shù)為500.

表1 500代內(nèi)算法優(yōu)化所得結(jié)果

Tab.1 The results of the algorithm within 500 generations

函數(shù)f(x*)PS-MIMIC最優(yōu)值PS-MIMIC平均值MIMIC最優(yōu)值MIMIC平均值10001.0891.913200004.011300000400000.223

由表1可知，PS-MIMIC算法對(duì)測(cè)試函數(shù)進(jìn)行30次試驗(yàn)后都可以找到最優(yōu)值，且與函數(shù)已知最優(yōu)值一樣，說(shuō)明PS-MIMIC算法在固定的進(jìn)化代數(shù)內(nèi)可以得到很好的優(yōu)化結(jié)果。同時(shí)，也可由表中看出，與標(biāo)準(zhǔn)的MIMIC算法相比較，PS-MIMIC算法在求精能力上有了進(jìn)一步的提高，說(shuō)明該算法具有一定的優(yōu)勢(shì)。

(2)到達(dá)確定閾值時(shí)的平均進(jìn)化代數(shù)。

表2 到達(dá)確定閾值的平均進(jìn)化代數(shù)

Tab.2 The average evolution algebra to determined threshold

函數(shù)PS-MIMICMIMIC1125—2621143342500479143

表2給出PS-MIMIC算法和標(biāo)準(zhǔn)MIMIC算法到達(dá)確定閾值的平均進(jìn)化代數(shù)，四個(gè)函數(shù)的閾值均為0.通過(guò)表2可以看出，對(duì)于四個(gè)測(cè)試函數(shù)，PS-MIMIC算法的平均進(jìn)化代數(shù)都要明顯優(yōu)于MIMIC算法，說(shuō)明與標(biāo)準(zhǔn)MIMIC算法相比，PS-MIMIC算法具有較快的收斂能力，其中函數(shù)1，MIMIC算法在最大進(jìn)化代數(shù)內(nèi)沒(méi)有達(dá)到確定閾值，所以沒(méi)有進(jìn)化代數(shù)。

(3)達(dá)標(biāo)率

表3 到達(dá)預(yù)設(shè)閾值時(shí)的達(dá)標(biāo)率

Tab.3 The target rate while reaching the preset threshold

函數(shù)PS-MIMICMIMIC1100%02100%13.33%3100%100%4100%33.33%

表3給出了MIMIC算法和PS-MIMIC算法到達(dá)預(yù)設(shè)閾值時(shí)達(dá)標(biāo)率的比較結(jié)果，由表3可以看出，對(duì)于四個(gè)測(cè)試函數(shù)，PS-MIMIC算法的達(dá)標(biāo)率都達(dá)到了100%，而在MIMIC算法下，函數(shù)1 的達(dá)標(biāo)率為0，函數(shù)2的達(dá)標(biāo)率為13.33%，函數(shù)3的達(dá)標(biāo)率為100%，函數(shù)4的達(dá)標(biāo)率為33.33%，所以PS-MIMIC算法的達(dá)標(biāo)率明顯優(yōu)于標(biāo)準(zhǔn)MIMIC算法，說(shuō)明PS-MIMIC算法的有效性和可靠性。

下圖1-4分別給出了函數(shù)1-函數(shù)4的MIMIC 算法和改進(jìn)后的算法在相同進(jìn)化代數(shù)下的函數(shù)值的仿真實(shí)驗(yàn)圖，從圖中可以看出與標(biāo)準(zhǔn)的MIMIC算法相比，PS-MIMIC算法可以快速的找到最優(yōu)值附近且收斂速度上要明顯優(yōu)于標(biāo)準(zhǔn)的MIMIC算法。

綜上所述，結(jié)合模式搜索發(fā)的混合MIMIC算法是一個(gè)有效的，可行的優(yōu)化算法，具有較強(qiáng)的尋優(yōu)能力和較快的收斂速度，相比標(biāo)準(zhǔn)的MIMIC算法具有一定的優(yōu)勢(shì)。

圖1 兩種算法在函數(shù)1所獲收斂曲線(xiàn)比較

Fig.1 Comparison of the convergence curves of two kinds of algorithms on f1

圖2 兩種算法在函數(shù)2所獲收斂曲線(xiàn)比較

Fig.2 Comparison of the convergence curves of two kinds of algorithms on f2

圖3 兩種算法在函數(shù)3所獲收斂曲線(xiàn)比較

Fig.3 Comparison of the convergence curves of two kinds of algorithms on f3

圖4 兩種算法在函數(shù)4所獲收斂曲線(xiàn)比較

Fig.4 Comparison of the convergence curves of two kinds of algorithms on f4

4 結(jié)束語(yǔ)

從仿真實(shí)驗(yàn)結(jié)果可以看出，與標(biāo)準(zhǔn)的MIMIC算法相比，結(jié)合模式搜索法的混合MIMIC算法可以更精確的求得最優(yōu)值，且到達(dá)確定閾值時(shí)的進(jìn)化代數(shù)和達(dá)標(biāo)率都要優(yōu)于標(biāo)準(zhǔn)的MIMIC算法，所以結(jié)合模式搜索法的混合MIMIC算法既結(jié)合了MIMIC算法的全局搜索能力強(qiáng)的優(yōu)點(diǎn)，又結(jié)合了模式搜索法局部求精能力強(qiáng)，收斂速度快的優(yōu)點(diǎn)，使得該算法在解決優(yōu)化問(wèn)題時(shí)具有較強(qiáng)的尋優(yōu)能力和較快的收斂速度，它不要求優(yōu)化函數(shù)必須連續(xù)或者可導(dǎo)，它是求解不可導(dǎo)或者求導(dǎo)麻煩的函數(shù)的一種有效方法。

由于該算法結(jié)合了兩種算法，涉及參數(shù)較多，所以對(duì)于參數(shù)設(shè)置的問(wèn)題有待做進(jìn)一步的研究，在保證更快的收斂速度前提下尋找更精確的解。

[1] LARRANAGA P, LOZANOJ A. Estimation of distribution algorithms: A new tool for evolutionary computation [M]. Boston: Kluweer Press, 2002.

[2] 王麗芳,曾建潮,洪毅. 利用Copula函數(shù)估計(jì)概率模型并采樣的分布估計(jì)算法[J]. 控制與決策,2011,26(9):1333-1337.

[3] 周樹(shù)德,孫增圻.分布估計(jì)算法綜述[J].自動(dòng)化學(xué)報(bào),2007,33(2):115-118.

[4] 龔純,王正林.精通Matlab最優(yōu)化計(jì)算[M].北京：電子工業(yè)出版社,2012.

[5] 張文林,夏桂梅.一種結(jié)合微粒群算法的混合MIMIC算法[J].太原科技大學(xué)學(xué)報(bào),2015,36(5):406-410

[6] 張金鳳,夏桂梅,王泰.一種基于罰函數(shù)的混合分布估計(jì)算法[J].西南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2015,41(1):120-123

[7] 吳興遠(yuǎn).模式搜索法在最優(yōu)化問(wèn)題中的應(yīng)用[J].軟件導(dǎo)刊,2009,8(8)：122-123.

[8] 唐超宏，莫海鴻，劉少躍.模式搜索法在邊坡穩(wěn)定性分析中的應(yīng)用[J]. 華南理工大學(xué)學(xué)報(bào),2000,28(2)：42-46.

[9] 淳靜,吳宇列,戴一帆等. 模式搜索法在光纖有源自動(dòng)對(duì)準(zhǔn)中的應(yīng)用[J]. 光學(xué)精密工程,2006,14(2)：236-241.

[10] 莫海鴻,唐超宏,劉少躍. 應(yīng)用模式搜索法尋找最危險(xiǎn)滑動(dòng)圓弧[J]. 巖土工程學(xué)報(bào)，1999，21(6)：696-699.

[11] DE BONET J S, ISBELL C L, VIOLA P. MIMIC: Finding optima by estimating probability densities [J]. Advances in Neural Information Processing Systems, 1997, 9:424-430.

[12] 王麗芳.copula分布估計(jì)算法[M].機(jī)械工業(yè)出版社,2012.

A Hybrid MIMIC Algorithm Combined with Pattern Search Algorithm

ZHANG Dan, XIA Gui-Mei

(School of Applied Science, Taiyuan University of Science and Technology, Taiyuan 030024)

Estimation of distribution algorithm is an algorithm with higher global optimization ability but lower partial refinement ability. To enhance the partial refinement capacity of this algorithm, this paper introduced pattern search algorithm which belongs strong local refinement ability and fast convergence rate to the estimation of distribution algorithm, and then proposed a hybrid MIMIC algorithm combined with pattern search algorithm. Through testing the performance of the algorithm with test function and comparing the results with the standard MIMIC algorithm, we conclude that the algorithm has good performance in dealing with optimization problem and the optimal value can be found rapidly.

estimation of distribution algorithms, pattern search, MIMIC algorithm

1673-2057(2016)06-0490-05

2016-01-28

太原科技大學(xué)校研究生教改項(xiàng)目(20133001)

張丹(1990-)，女，碩士研究生，研究方向：最優(yōu)化理論與應(yīng)用；通信作者：夏桂梅副教授，Email:xiaguimeiznn@163.com

0221

A

10.3969/j.issn.1673-2057.2016.06.014