国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

一種結(jié)合微粒群算法的混合MIMIC算法

2015-12-25 01:24張文林,夏桂梅

一種結(jié)合微粒群算法的混合MIMIC算法

張文林,夏桂梅

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

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

關(guān)鍵詞:分布估計(jì)算法;微粒群算法;MIMIC算法

收稿日期:2015-03-10

基金項(xiàng)目:山西省自然基金(2014011006-2)

作者簡介:張文林(1989-),男,碩士研究生,主要研究方向?yàn)樽顑?yōu)化理論與應(yīng)用;通信作者:夏桂梅,副教授,E-mail:xiaguimeiznn@163.com

中圖分類號:0221文獻(xiàn)標(biāo)志碼:A

分布估計(jì)算法(簡稱EDA)[1]是在1996年提出的一種基于概率模型的優(yōu)化算法,當(dāng)前已成為進(jìn)化領(lǐng)域研究的重要內(nèi)容。分布估計(jì)算法是通過一個(gè)概率模型來描述候選解在空間的分布,然后采用統(tǒng)計(jì)學(xué)習(xí)的手段從群體宏觀的角度去建立一個(gè)描述解分布的概率模型,最后對概率模型隨機(jī)采樣產(chǎn)生新一代的種群,如此反復(fù)進(jìn)行,最終實(shí)現(xiàn)種群的進(jìn)化。根據(jù)變量之間的相關(guān)性,可以將分布估計(jì)算法分成以下三類:變量相互獨(dú)立的分布估計(jì)算法、雙變量相關(guān)的分布估計(jì)算法和多變量相關(guān)的分布估計(jì)算法[2]。

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

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

1.1微粒群算法

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

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

每一個(gè)粒子的位置和速度按以下公式進(jìn)行更新:

(1)

(2)

其中,w稱為慣性權(quán)重,其表示粒子對當(dāng)前速度的繼承能力,選擇合適的w可以使粒子具有全局搜索能力和局部搜索能力;c1和c2稱為學(xué)習(xí)因子,c1表示粒子具有自我總結(jié)的能力,c2表示粒子從群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力,從而使得粒子向自身的歷史最優(yōu)點(diǎn)以及群體內(nèi)粒子的歷史最優(yōu)點(diǎn)靠近;ξ和η是[0,1]之內(nèi)的隨機(jī)數(shù)。

1.2MIMIC算法

MIMIC算法[6]是最早提出的一種雙變量相關(guān)的分布估計(jì)算法,它把遺傳算法與統(tǒng)計(jì)學(xué)思想結(jié)合起來,對解空間的個(gè)體分布,利用統(tǒng)計(jì)學(xué)的思想來建立概率模型,避免了遺傳算法中的交叉和變異等操作,減少了參數(shù)的設(shè)置,更容易求解。在MIMIC算法模型中,將隨機(jī)向量中各變量之間考慮成一種鏈?zhǔn)浇Y(jié)構(gòu),即只有相鄰之間的節(jié)點(diǎn)間存在依賴關(guān)系,其概率模型圖如下:

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

(3)

(4)

(5)

1.3PSO-MIMIC算法

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

Step 1對群體初始化,同時(shí)設(shè)置參數(shù),隨機(jī)的產(chǎn)生2n個(gè)個(gè)體作為初始群體pop°,k→0;

Step 2利用罰函數(shù)法將約束問題轉(zhuǎn)化為無約束問題;

Step 3計(jì)算群體中每一個(gè)個(gè)體的適應(yīng)值,若滿足終止條件,則算法結(jié)束,否則轉(zhuǎn)下一步;

Step 4用輪盤賭法和截?cái)喾ㄟx擇n個(gè)個(gè)體作為優(yōu)勢群體;

Step 5將Step 4中n個(gè)個(gè)體根據(jù)設(shè)置的參數(shù)利用微粒群算法進(jìn)行更新,得到M1個(gè)新個(gè)體:

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

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

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

2.1測試函數(shù)

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

函數(shù)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

函數(shù)2:

函數(shù)3:

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

0≤xi≤10,i=1,2

函數(shù)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

函數(shù)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

函數(shù)6:

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

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

在試驗(yàn)中,算法的各個(gè)參數(shù)設(shè)置如下:群體規(guī)模2 000,最大迭代次數(shù)為500,精度10-3,慣性權(quán)重w=0.5,加速權(quán)重c1=c2=0.494 45,各自獨(dú)立進(jìn)行10次試驗(yàn)。

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

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

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

表1 測試函數(shù)試驗(yàn)結(jié)果

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

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

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

圖1 MIMIC關(guān)系圖

圖2 PSO-MIMIC關(guān)系圖

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

3結(jié)論

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

參考文獻(xiàn):

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

[2]葉寶林.分布估計(jì)算法的一種改進(jìn)與應(yīng)用[D].太原:太原科技大學(xué)學(xué)報(bào),2011:1-81.

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

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

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

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

[7]吳紅梅.非線性約束優(yōu)化問題的信賴域算法[D].蘭州:蘭州理工大學(xué),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

三河市| 漠河县| 石首市| 会同县| 依兰县| 呼伦贝尔市| 原阳县| 灌云县| 达拉特旗| 西青区| 卢龙县| 肥东县| 芦溪县| 镇平县| 渭源县| 新安县| 东方市| 迭部县| 德钦县| 得荣县| 甘孜县| 永兴县| 虎林市| 泊头市| 贵德县| 临颍县| 井陉县| 色达县| 虎林市| 江达县| 平湖市| 西昌市| 东乌| 遂川县| 炉霍县| 顺平县| 汶上县| 平舆县| 抚州市| 天长市| 新巴尔虎左旗|