一種結合微粒群算法的混合MIMIC算法

一種結合微粒群算法的混合MIMIC算法

張文林，夏桂梅

(太原科技大學應用科學學院，太原 030024)

摘要：分布估計算法是基于遺傳算法的基礎上發(fā)展起來的一種新型的優(yōu)化算法，它采用的是概率圖的模型來表示基因中變量之間的關系，從而構建優(yōu)良解集的概率分布模型進行采樣來實現迭代進化。但是分布估計算法在問題求解過程中容易陷入局部最優(yōu)，針對此缺點，引入微粒群算法，提出了一種結合微粒群算法的分布估計算法。這種算法將分布估計算法與微粒群算法的思想緊密結合起來，不僅保持了種群的多樣性，而且具有更全面的學習能力，提高了算法的尋優(yōu)能力以及避免早熟收斂的能力。通過對測試函數的仿真試驗，表明該算法具有良好的性能。

關鍵詞：分布估計算法；微粒群算法；MIMIC算法

收稿日期：2015-03-10

基金項目：山西省自然基金(2014011006-2)

作者簡介：張文林(1989-)，男，碩士研究生，主要研究方向為最優(yōu)化理論與應用；通信作者：夏桂梅，副教授，E-mail：xiaguimeiznn@163.com

中圖分類號：0221文獻標志碼：A

分布估計算法(簡稱EDA)[1]是在1996年提出的一種基于概率模型的優(yōu)化算法，當前已成為進化領域研究的重要內容。分布估計算法是通過一個概率模型來描述候選解在空間的分布，然后采用統計學習的手段從群體宏觀的角度去建立一個描述解分布的概率模型，最后對概率模型隨機采樣產生新一代的種群，如此反復進行，最終實現種群的進化。根據變量之間的相關性，可以將分布估計算法分成以下三類：變量相互獨立的分布估計算法、雙變量相關的分布估計算法和多變量相關的分布估計算法[2]。

然而分布估計算法在進化的過程中對概率模型進行學習時，很容易對問題解空間的分布過于依靠，導致算法構建的概率模型不能夠準確的表達解空間的信息，在算法多次迭代后，種群的多樣性減少，并且進化的速度非常慢，每一代的改變也很小，這些情況說明分布估計算法的全局搜索能力強，而局部搜索能力弱。鑒于分布估計算法的此弱點，在生成新群體的過程中加入微粒群算法[3]，提出一種結合微粒群算法的分布估計算法(PSO-MIMIC).

1結合微粒群算法的混合MIMIC算法(PSO-MIMIC)

1.1微粒群算法

在標準的微粒群算法中，假設一個由m個粒子組成的群體在D維的空間中以一定的速度飛行，每個粒子在搜索時，考慮到了粒子本身搜索到的歷史最優(yōu)點，以及群體內其他粒子的歷史最優(yōu)點，在此基礎上進行位置的更新。如文獻[4]和文獻[5]都是利用微粒群算法求解約束優(yōu)化問題。

第i個粒子的位置可以表示為xi=(xi1,xi2，…,xiD)；第i個粒子的速度可以表示為vi=(vi1,vi2,…,viD)，其中1≤i≤m,1≤d≤D；第i個粒子經過的歷史最優(yōu)點可以表示為pi=(pi1,p=i2,…,piD) ；群體內所有粒子經過的最優(yōu)點可以表示為pg=(pg1,pg2,…,pgD)；

每一個粒子的位置和速度按以下公式進行更新：

(1)

(2)

其中，w稱為慣性權重，其表示粒子對當前速度的繼承能力，選擇合適的w可以使粒子具有全局搜索能力和局部搜索能力；c1和c2稱為學習因子，c1表示粒子具有自我總結的能力，c2表示粒子從群體中優(yōu)秀個體學習的能力，從而使得粒子向自身的歷史最優(yōu)點以及群體內粒子的歷史最優(yōu)點靠近；ξ和η是[0,1]之內的隨機數。

1.2MIMIC算法

MIMIC算法[6]是最早提出的一種雙變量相關的分布估計算法，它把遺傳算法與統計學思想結合起來，對解空間的個體分布，利用統計學的思想來建立概率模型，避免了遺傳算法中的交叉和變異等操作，減少了參數的設置，更容易求解。在MIMIC算法模型中，將隨機向量中各變量之間考慮成一種鏈式結構，即只有相鄰之間的節(jié)點間存在依賴關系，其概率模型圖如下：

定義解空間概率分布模型：

(3)

(4)

(5)

1.3PSO-MIMIC算法

針對非線性多約束優(yōu)化問題[7]，本文提出了一種結合微粒群算法與MIMIC算法的PSO-MIMIC算法。新算法中每一個粒子的信息一部分來自于所有個體最優(yōu)值的概率模型，另一部分來自粒子的當前解與全局最優(yōu)解。這樣粒子的當前解，所有個體最優(yōu)值和全局最優(yōu)值都參與了新解的生成過程，利用了分布估計算法的思想并且繼承了微粒群算法的思想，保持了種群的多樣性，同時具有更全面的學習能力，提高了算法的尋優(yōu)能力以及避免早熟收斂的能力。其中，當我們對有約束條件的優(yōu)化問題進行研究時，可以采用罰函數法，將約束優(yōu)化問題轉化成為無約束的優(yōu)化問題進行求解。具體步驟如下：

Step 1對群體初始化，同時設置參數，隨機的產生2n個個體作為初始群體pop°，k→0；

Step 2利用罰函數法將約束問題轉化為無約束問題；

Step 3計算群體中每一個個體的適應值，若滿足終止條件，則算法結束，否則轉下一步；

Step 4用輪盤賭法和截斷法選擇n個個體作為優(yōu)勢群體；

Step 5將Step 4中n個個體根據設置的參數利用微粒群算法進行更新，得到M1個新個體：

Step 6將Step 4中n個個體執(zhí)行以下操作：

Step 7按逆序從概率模型中采樣M2次(其中M2=2n-M1)，與更新后的M1個個體組成新一代群體popk+1，轉Step3.

2數值試驗

2.1測試函數

為了測試算法的性能，選取文獻[9]中6個測試函數，并對所得結果進行比較。

函數1：

minf(x)=(x1-10)3+(x2-20)3

s.t. g1(x)=-(x1-5)2-(x2-5)2+100≤0

g2(x)=(x1-6)2+(x2-5)2-82.81≤0

13≤x1≤100

0≤x2≤100

函數2：

函數3：

g2(x)=-x1+(x2-4)2+1≤0

0≤xi≤10,i=1,2

函數4：

x4-x3+0.55≥0x3-x4+0.55≥0

s.t. 1000sin(-x3-0.25)+1000sin(-x4-0.25)+894.8-x1=0

1000sin(x3-0.25)+1000sin(x3-x4-0.25)+894.8-x2=0

1000sin(x4-0.25)+1000sin(x4-x3-0.25)+1294.8=0

0≤xi≤1200,i=1,2

-0.55≤xi≤0.55,i=3,4

函數5：

40792.141

s.t. 0≤85.334407+0.0056858x2x5+0.00026x1x4-0.0022053x3x5≤92

20≤9.300961+0.0047026x3x5+0.0012547x1x3+0.0019085x3x4≤25

78≤x1≤102,33≤x2≤45,27≤xi≤45,

i=3,4,5

函數6：

-10≤xi≤10,i=1,2,…,7

2.2參數設置

在試驗中，算法的各個參數設置如下：群體規(guī)模2 000，最大迭代次數為500，精度10-3，慣性權重w=0.5，加速權重c1=c2=0.494 45，各自獨立進行10次試驗。

2.3試驗結果及分析

表1給出了每個測試函數的最優(yōu)值f(x*)以及運用本算法獨立運行10次試驗后的最好值，平均值及偏差。

由表1可知每個測試函數在獨立進行10次試驗后都能找到最優(yōu)值，而且測試函數已知的最優(yōu)值同本文算法求出的最優(yōu)值的偏差接近于0，說明了本文算法具有有效性和可行性。但是，隨著函數維數的增加，其最優(yōu)值與已知最優(yōu)值偏差逐漸增大，說明該算法對于維數較低的函數有較好的效果，而對于維數較高的函數還存在一定的欠缺。

表1　測試函數試驗結果

表2給出了本文算法(PSO-MIMIC)與MIMIC算法對測試函數結果與測試函數已知最優(yōu)值f(x*)的比較。

由表2可以看出本文算法與標準MIMIC算法對測試函數的最好值及平均值與函數本身最優(yōu)值的比較。尤其對于函數1、2、3，由本文算法得到的平均值明顯比MIMIC算法得到的平均值更接近于最優(yōu)值。而對于維數高的函數5和6，其結果稍次于MIMIC算法，但也能找到接近最優(yōu)解的值。

表2　PSO-MIMIC與MIMIC算法對測試函數性能的比較

圖1　MIMIC關系圖

圖2　PSO-MIMIC關系圖

圖1和圖2給出了本文算法與標準MIMIC算法對具有代表性的函數1、3和6從優(yōu)勢群體個數和進化代數的關系方面進行比較的關系圖。其中優(yōu)勢群體個數從1 000開始，按100的個數遞增，直到2 000為止，分別進行仿真試驗所得結果動態(tài)圖如圖1、圖2.由圖可知，隨著優(yōu)勢群體個數的增加，進化代數也呈增加的趨勢，尤其對于函數6，其穩(wěn)定性與進化代數明顯優(yōu)于標準MIMIC算法，試驗結果初步驗證了本文算法的有效性和合理性，說明本文算法具有一定的優(yōu)勢。

3結論

PSO-MIMIC算法充分結合了微粒群算法結構簡單的特點，又克服了分布估計算法在種群進化過程中個體單一的缺點，使得原來的算法在解決優(yōu)化問題時有了一定的改進。把改進后的算法應用于處理非線性約束優(yōu)化問題，結果表明，本文提出的PSO-MIMIC算法具有一定的優(yōu)勢，能夠找到滿足約束條件的最優(yōu)解，并且最優(yōu)值與已知最優(yōu)值非常接近，收斂效率很高，尤其對于維數較低的函數具有非常好的效果，而對于維數較高的函數，其效果稍次于其他算法，究其原因是在對約束條件的處理方法上導致的，如果在本算法的進化過程中能找到其他合適的處理約束條件的方法，其效果可能會更好，其方法有待于進一步研究。

參考文獻：

[1]周樹德，孫增圻.分布估計算法綜述[J].自動化學報，2007，33(2)：115-118.

[2]葉寶林.分布估計算法的一種改進與應用[D].太原：太原科技大學學報，2011：1-81.

[3]屈向紅，夏桂梅，王希云.求解約束優(yōu)化問題的改進微粒群算法[J].太原科技大學學報，2012，33(5)：406-409.

[4]熊鷹，周樹民，祁輝.一種新型的求解約束優(yōu)化問題的微粒群算法[J].廣東廣播電視大學學報，2006，59(15)：32-35.

[5]李金萊，盧香清.一種求解約束優(yōu)化問題的信賴域微粒群算法[J].計算機工程與應用，2011，47(10)：198-200.

[6]羅國軍，張學良，郭曉東，等.MIMIC算法在非線性多約束機械優(yōu)化問題中的應用[J].太原科技大學學報，2013，34(6)：440-444.

[7]吳紅梅.非線性約束優(yōu)化問題的信賴域算法[D].蘭州：蘭州理工大學，2007：1-53.

[8]DE BONET J S，ISBELL C L，VOILA P.MIMIC：Finding Optima by Estimating Probability Densities[C].In：Advances in Neural Information Processing Systems，Cambrige：MIT Press，1997，(9)：424-430.

[9]ZBIGNIEW MICHALEWICZ，MARC SCHOENAUER.Evolutionary Algorithms for Constrained Parameter Optimization Problems[J].Evolutionary Computation，1996，4(1)：1-32.

A Hybrid MIMIC Algorithm Combining With Hybrid Particle Algorithm

ZHANG Wen-Lin，XIA Gui-Mei

(School of Applied Science，Taiyuan University of Science and Technology，Taiyuan 030024，China)

Abstract：The estimation of distribution algorithm is developed on the basis of genetic algorithm；it is a kind of new optimization algorithm which uses probability graph model to express the relationship among variables to construct the gene so as to build excellent solution set of probability distribution model for sampling to realize iterative evolution.But the estimation of distribution algorithm easily falls into local optimum in the problem solving process.Aiming at this disadvantage，the particle swarm algorithm is proposed to estimate algorithm combined with the distribution of particle swarm optimization algorithm.The new algorithm combines the estimation of distribution algorithm with particle swarm algorithm，keeps the diversity of population， has more comprehensive learning ability and improves searching ability to avoid premature convergence.Through simulation test of test function， the algorithm is proved to have good performance.

Key words：estimation of distribution algorithms，hybrid particle algorithm，MIMIC algorithm