一種結(jié)合信賴域算法的混合MIMIC算法

夏桂梅，張文林

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

一種結(jié)合信賴域算法的混合MIMIC算法

夏桂梅，張文林

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

針對分布估計(jì)算法在求解問題的過程中局部搜索能力較弱的缺點(diǎn)，引入了信賴域算法，提出了結(jié)合信賴域算法的分布估計(jì)算法．由于信賴域算法是一種很好的局部快速尋優(yōu)方法，因此在分布估計(jì)算法的基礎(chǔ)上，再對每一個粒子分別實(shí)施信賴域算法，能夠加強(qiáng)算法的局部搜索能力．新算法不僅保持了種群的多樣性，而且具備更全面的學(xué)習(xí)能力，提高了算法的尋優(yōu)能力，避免早熟收斂的發(fā)生．?dāng)?shù)值試驗(yàn)結(jié)果表明：該算法能收斂到滿足約束條件的最優(yōu)解，并且具有很強(qiáng)的搜索能力，為解決非線性約束優(yōu)化問題提供了一種新的有效途徑．

分布估計(jì)算法；信賴域算法；MIMIC算法

分布估計(jì)算法（Estimation of Distribution Algorithm，簡稱EDA）是1996年提出的一種基于概率模型的優(yōu)化算法[1]，EDA在進(jìn)化過程中通過統(tǒng)計(jì)方法建立解空間的概率分布模型，然后對模型進(jìn)行采樣得到新一代群體，如此反復(fù)進(jìn)行，直至實(shí)現(xiàn)種群的進(jìn)化．它不涉及在傳統(tǒng)算法中出現(xiàn)的交叉變異等操作步驟，減少了參數(shù)設(shè)置，簡化了計(jì)算過程，因而可解決一些傳統(tǒng)算法難以解決的優(yōu)化問題．根據(jù)變量之間的相關(guān)性，將分布估計(jì)算法分成下列三類：變量之間相互獨(dú)立的分布估計(jì)算法、雙變量相關(guān)的分布估計(jì)算法，以及多個變量相關(guān)的分布估計(jì)算法[2]．然而，EDA在后期進(jìn)化過程中速度很慢，且每一次的進(jìn)化改變也很小，究其原因在于EDA在構(gòu)建概率模型過程中，對空間內(nèi)解分布過于依靠，多次迭代后，種群多樣性減少，這些情況說明EDA的局部搜索能力較弱．鑒于EDA的此缺陷，在種群的進(jìn)化過程中加入局部搜索能力很高的信賴域算法[3]，提出一種結(jié)合信賴域算法的分布估計(jì)算法．新算法是在原分布估計(jì)算法基礎(chǔ)上加入信賴域算法，在每次迭代過程中，粒子在進(jìn)行完分布估計(jì)算法步驟后再對每一個粒子實(shí)施信賴域算法，尋找更優(yōu)個體，這樣，新算法不僅利用了分布估計(jì)算法全局搜索能力強(qiáng)的優(yōu)點(diǎn)，且利用了信賴域算法局部搜索能力強(qiáng)的優(yōu)點(diǎn)，同時保持了種群多樣性，因而具備更全面的學(xué)習(xí)能力，提高了算法的尋優(yōu)能力．

1 結(jié)合信賴域算法的混合MIMIC算法

1.1 罰函數(shù)法

罰函數(shù)法[4]的思想是將約束優(yōu)化問題通過構(gòu)造一個增廣目標(biāo)函數(shù)轉(zhuǎn)化為無約束優(yōu)化問題，從而利用有關(guān)的無約束問題來研究約束極值問題．經(jīng)常采用的方法是在原來的目標(biāo)函數(shù)上加上一個由約束函數(shù)組成的一個“懲罰項(xiàng)”來迫使迭代點(diǎn)逼近可行域．

罰函數(shù)的定義為：

其中，f(x)為約束優(yōu)化問題中的目標(biāo)函數(shù)，h(k)是隨著迭代次數(shù)在變化的動態(tài)罰值，k是種群的迭代次數(shù)，H(x)是多段映射懲罰因子，其定義如下：

其中qi(x)=max{0,pi(x)},i=1,2,…,m ，pi(x)為原約束優(yōu)化問題中的約束條件函數(shù)，包括等式函數(shù)與不等式函數(shù)，qi(x)是約束沖突函數(shù)，θ(qi(x))是一個多級賦值函數(shù)，γ(qi(x))是罰函數(shù)的力度，h(.)，θ(.)，γ(.)是依賴于具體的問題．

1.2 MIMIC算法

MIMIC算法（Mutual Information Maximization for Input Clustering）是最早提出的一種雙變量相關(guān)的分布估計(jì)算法[5]，它將變量之間的關(guān)系簡單化，只考慮相鄰的兩個變量之間的關(guān)系，避免了遺傳算法中的交叉和變異等操作，減少了參數(shù)的設(shè)置，更容易求解．

De Bonet等人[6]在1997年提出的MIMIC算法是用鏈?zhǔn)浇Y(jié)構(gòu)來表示變量之間的關(guān)系，其模型圖如圖1所示．

圖1 MIMIC概率圖模型Fig 1 The probabilistic graphical model of MIMIC

對于需要優(yōu)化的變量(x1,x2,…,xn)，存在一個最優(yōu)的排列π=(i1,i2,…,in)，使得根據(jù)優(yōu)勢群體估計(jì)出來的概率分布模型與優(yōu)勢群體的實(shí)際概率分布之間的K-L距離達(dá)到最?。渲?，π=(i1,i2,…,in)表示變量x1,x2,…,xn的一個排列；pl(xij|xij+1)表示第ij+1個變量取值為xij+1時，第ij個變量取值為xij的條件概率．因此，我們的任務(wù)是找到一個適當(dāng)?shù)呐帕笑?，使得根?jù)優(yōu)勢群體估計(jì)出來的概率分布模型與問題的實(shí)際概率分布模型盡可能的接近．K-L距離的定義為：

MIMIC算法構(gòu)建概率模型的過程為：先隨機(jī)產(chǎn)生xin，用條件概率pl (xin-1|xin)產(chǎn)生xin-1，以此類推得到xin-2,xin-3,…,x1；再利用貪婪算法[6]來最小化plπ(x)與plπ的K-L距離得到一個最優(yōu)排列π*=(i1,i2,…,in)；最后利用π*構(gòu)建優(yōu)勢群體的概率模型

1.3 信賴域算法

信賴域算法[7]作為一種非常重要的優(yōu)化算法，與傳統(tǒng)的線性搜索方法一樣，也是在優(yōu)化算法過程中求出每次迭代的位移，進(jìn)而確定新的迭代點(diǎn)，不同的是普通的線性搜索是先產(chǎn)生搜索方向，然后確定搜索步長，而信賴域算法則是直接去確定位移來產(chǎn)生新的迭代點(diǎn)．因此，信賴域算法是一種很好的局部尋優(yōu)方法，特別是對于一些病態(tài)最優(yōu)化問題具有非常穩(wěn)定的性能．文獻(xiàn)[7]將信賴域算法與微粒群算法結(jié)合應(yīng)用于求解約束優(yōu)化問題．

信賴域算法的基本思想是：先給定一個信賴域半徑，作為在位移過程中的上界，并把當(dāng)前迭代點(diǎn)作為中心點(diǎn)，用此半徑確定一個信賴域的閉球區(qū)域，通過求解這個區(qū)域內(nèi)的信賴域子問題的最優(yōu)點(diǎn)來確定“候選位移”．如果“候選位移”能夠使目標(biāo)函數(shù)有足夠的下降量，則該“候選位移”作為可接受位移，并且擴(kuò)大信賴域半徑，繼續(xù)進(jìn)行迭代，否則縮小信賴域半徑，通過去求解新的信賴域子問題進(jìn)而得到新的“候選位移”，這樣重復(fù)下去，直到滿足終止條件．

其中Δk是信賴域半徑，||.||是向量范數(shù)，一般取其2范數(shù)．

設(shè)上述子問題的最優(yōu)解是dk，Δfk是f在第k次迭代的實(shí)際下降量，Δqk是對應(yīng)的預(yù)測下降量，Δqk一般取正數(shù)，且Δfk=fk-f(xk+dk)，Δqk=qk(0)-qk(dk)．定義它們的比值為rk，且．當(dāng)rk＜0時，有Δfk＜0，則xk+dk不能作為下一次的迭代點(diǎn)，因此需要縮小信賴域半徑來重新求解信賴域子問題；當(dāng)rk接近1時，則說明子問題與原目標(biāo)函數(shù)在此信賴域范圍內(nèi)有較好的近似，因此xk+1=xk+dk可以作為下一次的迭代點(diǎn)，并且下一次的迭代可以增大信賴域的半徑的值；對于其他的情況，信賴域的半徑則可以保持不變．

1.4 結(jié)合信賴域算法的混合MIMIC算法

MIMIC算法作為分布估計(jì)算法的一種，其用概率模型代替了遺傳算法中的交叉與變異的操作，避免了在遺傳算法中導(dǎo)致積木塊被破壞的問題，因此受到了許多學(xué)者的關(guān)注與研究，并且在此基礎(chǔ)上提出了許多的改進(jìn)策略[8]，在許多領(lǐng)域進(jìn)行了成功的研究應(yīng)用[9-11]．對于標(biāo)準(zhǔn)的MIMIC算法，雖然也能夠找到問題的全局最優(yōu)解，但在后期進(jìn)化的速度非常慢，每一代的改變程度也很小，這說明分布估計(jì)算法的全局搜索能力非常強(qiáng)，而局部搜索能力較弱，因此在MIMIC算法的基礎(chǔ)上加入一種局部尋優(yōu)方法非常強(qiáng)的信賴域算法來平衡粒子的搜索過程，進(jìn)而提高算法的搜索能力和效率．在實(shí)際操作中，對約束條件采用上文1.1中的罰函數(shù)法，將約束優(yōu)化問題轉(zhuǎn)化成為無約束的優(yōu)化問題進(jìn)行求解．

具體操作步驟如下：

Step 1：對群體初始化，同時設(shè)置參數(shù)，隨機(jī)的產(chǎn)生N個個體作為初始群體opop，k→0；

Step 2：利用罰函數(shù)法將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題；

Step 3：計(jì)算群體中每個個體的適應(yīng)值，若符合終止條件，則算法結(jié)束，否則轉(zhuǎn)下一步；

Step 4：用輪盤賭法和截?cái)喾ㄟx擇M＜N個個體來作為優(yōu)勢群體，并保留p個最優(yōu)個體；

Step 5：利用貪婪算法來尋找最優(yōu)排列建立優(yōu)勢群體的概率模型；

Step 6：利用逆序方法從模型中采樣m次，與上述p個個體構(gòu)成N個個體，其中m+p=N；Step 7：對上述N個個體執(zhí)行信賴域搜索，尋找更優(yōu)的個體，轉(zhuǎn)Step 3．

2 數(shù)值試驗(yàn)

2.1 測試函數(shù)

為了測試算法的性能，選取文獻(xiàn)[12]中的四個測試函數(shù)，并對所得結(jié)果進(jìn)行比較．

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

在Matlab試驗(yàn)中，算法的各個參數(shù)設(shè)置為：群體規(guī)模2 000，最大迭代次數(shù)為1 000，精度為10-6，分別進(jìn)行30次試驗(yàn)．

2.3 試驗(yàn)結(jié)果及分析

表1 本文算法與MIMIC算法對測試函數(shù)結(jié)果的比較Table 1 The comparison of the results of test functions with this algorithm and MIMIC algorithm

表1給出了四個測試函數(shù)的已知最優(yōu)值f(x*)、運(yùn)用本文算法獨(dú)立運(yùn)行30次試驗(yàn)后的最優(yōu)值以及最優(yōu)值與函數(shù)已知最優(yōu)值的偏差，并且與文獻(xiàn)[4]中直接用MIMIC算法對測試函數(shù)運(yùn)行結(jié)果進(jìn)行了比較．由表1可以看出，本文算法與直接運(yùn)用MIMIC算法對四個測試函數(shù)都能找到最優(yōu)解，但本文算法得到的最優(yōu)解明顯要優(yōu)于MIMIC算法得到的，尤其對于函數(shù)1，本文算法與函數(shù)最優(yōu)值之間的偏差明顯要比MIMIC算法好．實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的可行性與有效性．

表2 四個測試函數(shù)收斂性的比較Table 2 The convergence comparison of four test functions

表2給出了本文算法與MIMIC算法對四個測試函數(shù)分別進(jìn)行30次試驗(yàn)得到的有效試驗(yàn)次數(shù)、運(yùn)行過程中找到最優(yōu)解的平均迭代次數(shù)以及收斂率的比較．由表2可知，對于四個測試函數(shù)，在有效次數(shù)、找到最優(yōu)解的平均進(jìn)化代數(shù)以及收斂率方面，本文算法明顯要優(yōu)于標(biāo)準(zhǔn)的MIMIC算法，尤其是對于函數(shù)3，本文算法能夠達(dá)到100%的收斂．試驗(yàn)結(jié)果表明，本文算法是一種尋優(yōu)能力和可靠性更高的優(yōu)化算法，其性能比標(biāo)準(zhǔn)MIMIC算法有明顯提高．

在仿真試驗(yàn)中，令優(yōu)勢群體個數(shù)從500開始，以100遞增直至1 000，進(jìn)而來探索優(yōu)勢群體個數(shù)與進(jìn)化時間的關(guān)系．為了方便觀察，將函數(shù)1和2放在圖2中，將函數(shù)3和4放在圖3中，如下所示．

圖2 優(yōu)勢群體個數(shù)與進(jìn)化時間關(guān)系圖Fig 2 The diagram of the relationship between the number of dominant groups and evolution time

圖3 優(yōu)勢群體個數(shù)與進(jìn)化時間關(guān)系圖Fig 3 The diagram of the relationship between the number of dominant groups and evolution time

由圖2圖3可知，函數(shù)進(jìn)化所需時間隨著優(yōu)勢群體個數(shù)的增加而增加，并且對于維數(shù)較高的函數(shù)，進(jìn)化時間也在增加．因此，選擇合適的優(yōu)勢群體個數(shù)在種群中所占的比例，有利于縮小搜索的范圍，提高解的收斂速度．對于高維函數(shù)進(jìn)化時間長的問題，由于連續(xù)域分布估計(jì)算法研究進(jìn)展相對緩慢，還有待于進(jìn)一步的研究和改進(jìn)．

3 結(jié) 論

MIMIC算法作為分布估計(jì)算法中的一種，是一種簡單的隨機(jī)優(yōu)化算法，其全局搜索能力很強(qiáng)，缺點(diǎn)是在進(jìn)化過程中種群比較單一，在進(jìn)化后期收斂速度較慢，導(dǎo)致局部收斂性較弱．針對以上缺點(diǎn)，本文將局部收斂性很強(qiáng)的信賴域算法加入到MIMIC算法中，提出了一種結(jié)合信賴域算法的混合MIMIC算法．

改進(jìn)后的MIMIC算法充分結(jié)合了信賴域算法局部搜索能力強(qiáng)的特點(diǎn)，又保持了分布估計(jì)算法全局搜索能力強(qiáng)的優(yōu)點(diǎn)，使得原來的算法在解決優(yōu)化問題時有了一定的改進(jìn)．把改進(jìn)后的算法應(yīng)用于處理非線性約束優(yōu)化問題，結(jié)果表明，本文提出的算法提高了算法的局部搜索能力，減少了進(jìn)化的代數(shù)，并且找到的最優(yōu)值與已知最優(yōu)值非常接近，收斂效率很高，其綜合性能比標(biāo)準(zhǔn)MIMIC算法有明顯的提高．

[1] Larranaga P,Lozano J A. Estimation of distribution algorithms: a new tool for evolutionary computation [M]. Boston: Kluwer Press,2002: 1-126.

[2] 周樹德，孫增圻．分布估計(jì)算法綜述[J]．自動化學(xué)報(bào)，2007，33（2）：115-118．

[3] 馬昌鳳．最優(yōu)化方法及其Matlab程序設(shè)計(jì)[M]．北京：科學(xué)出版社，2010：74-99．

[4] 張金風(fēng)，夏桂梅，王泰．一種基于罰函數(shù)的混合分布估計(jì)算法[J]．西南民族大學(xué)學(xué)報(bào)，2015，41（1）：120-123．

[5] Jordan M I,Lecun Y,Solla S A. Advances in neural information processing systems [M]. Cambridge: MIT Press,1997: 1-63.

[6] De Bonet J S,Isbell C L,Viola P. MIMIC: finding optima by estimating probability densities [EB/OL]. [2014-08-08]. http://www.cc.gatech.edu/～isbell/papers/isbell-mimic-nips-1997.pdf.

[7] 李金萊，香清．一種求解約束優(yōu)化問題的信賴域微粒群算法[J]．計(jì)算機(jī)工程與應(yīng)用，2011，47（10）：54-56．

[8] 程玉虎，王雪松，郝名林．一種多樣性保持的分布估計(jì)算法[J]．電子學(xué)報(bào)，2010，38（3）：194-197．

[9] 張金風(fēng)，夏桂梅，張文林．基于MIMIC算法的備件優(yōu)化模型[J]．太原科技大學(xué)學(xué)報(bào)，2015，36（2）：154-159．

[10] 羅國軍，張學(xué)良，郭曉冬，等．MIMIC算法在非線性多約束機(jī)械優(yōu)化問題中的應(yīng)用[J]．太原科技大學(xué)學(xué)報(bào)，2013，34（6）：440-444．

[11] 孫濤，朱生鴻，李玥，等．改進(jìn)的分布估計(jì)算法在配網(wǎng)重構(gòu)中的應(yīng)用[J]．電力系統(tǒng)及其自動化學(xué)報(bào)，2014，26（6）：54-59．

[12] Michalewicz Z,Schoenauer M. Evolutionary algorithms for constrained parameter optimization problems [J]. Evolutionary Computation,1996,4(1): 1-32.

A Hybrid MIMIC Algorithm Integrated with Trust-region Algorithm

XIA Guimei,ZHANG Wenlin
(School of Applied Science,Taiyuan University of Science and Technology,Taiyuan,China 030024)

The Trust-region algorithm is introduced in this paper in allusion to the defect with the estimation of distribution algorithms which is weak in local search capability. Meanwhile,the distributed estimation algorithm integrated with the trust-region algorithm is proposed. Due to the trust-region algorithm is a partial optimal seeking method,the local search capability of the trust-region algorithm is strengthened with each particle implemented respectively. The new algorithm not only maintains the diversity of population,but also possesses a more comprehensive learning ability,which improves the searching capability of the algorithm,and avoids the occurrence of premature convergence. Numerical experiments show that the proposed algorithm is in position to converge the optimal solution which meets every constraint condition. Therefore,it is a very strong searching ability and provides a brand-new effective way to solve nonlinear constrained optimization problems.

Estimation of Distribution Algorithms; Trust-region Algorithm; MIMIC Algorithm

O221

：A

：1674-3563(2017)02-0001-07

10.3875/j.issn.1674-3563.2017.02.001 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

(編輯：封毅)

2015-11-10

山西省自然基金(2014011006-2)；太原科技大學(xué)研究生教改項(xiàng)目(20133001)

夏桂梅(1968-)，女，山西大同人，副教授，研究方向：最優(yōu)化理論與應(yīng)用