基于改進(jìn)種群熵的遺傳算法過渡收斂問題研究

基于改進(jìn)種群熵的遺傳算法過渡收斂問題研究

1種群多樣性優(yōu)化遺傳算法是生物自然選擇和進(jìn)化機(jī)制發(fā)展起來的一種高度平行、隨機(jī)的、適應(yīng)性的搜索方法。ga提供了解決復(fù)雜優(yōu)化問題的一般框架，不依賴于特定問題領(lǐng)域的知識，并具有很強(qiáng)的魯棒性。遺傳算法的參數(shù)中交叉概率和變異概率的選擇時影響遺傳算法行為和性能的關(guān)鍵所在。標(biāo)準(zhǔn)遺傳算法采用固定的交叉、變異概率,對于不同的優(yōu)化問題,很難找到適應(yīng)于每個問題的最佳值,并且在對復(fù)雜函數(shù)進(jìn)行尋優(yōu)時,無法根據(jù)種群的當(dāng)前狀態(tài)對進(jìn)化過程進(jìn)行動態(tài)調(diào)整,往往導(dǎo)致種群多樣性過早流失,算法陷入局部最優(yōu)解,引起過早收斂。針對這一問題,國內(nèi)外不少研究人員致力于標(biāo)準(zhǔn)遺傳算法的改進(jìn),提出了多種交叉、概率可變的改進(jìn)遺傳算法,如Srinvivas等提出的一種自適應(yīng)遺傳算法(AdaptiveGA,簡稱AGA)。本文根據(jù)種群多樣性與遺傳操作之間的關(guān)系,提出了一種基于種群多樣性評價的自適應(yīng)遺傳算法,通過種群多樣性變化控制當(dāng)前種群交叉率、變異率的范圍,并對不同個體的操作概率在當(dāng)前范圍內(nèi)進(jìn)行微調(diào)。經(jīng)實驗證明,該方法在保持種群多樣性,提高問題求解的精度等方面有較好的效果。2種群熵與種群最大熵遺傳算法通過對大量個體實施遺傳操作推動種群的進(jìn)化,種群的規(guī)模越大,包含的不同個體越多,搜索到更優(yōu)個體的幾率就越大。而通常情況下,種群規(guī)模是一定的,種群多樣性越大,種群就越有可能產(chǎn)生出更優(yōu)子代,而種群多樣性減小,種群個體間不斷趨于一致,過早收斂現(xiàn)象就越容易發(fā)生。因此,保持種群多樣性成為遺傳算法有效運行的重要方法之一,正確評價種群的多樣性程度對遺傳算法性能的改進(jìn)起著非常重要的作用。種群熵是種群的多樣性定量評價的指標(biāo)之一。其具體定義如下:定義1:假設(shè)P(t)為第t代種群,種群規(guī)模為N,根據(jù)個體的不同類型可將種群劃分為m個部分:P1(t)、P2(t)…Pm(t),顯然,∪i=1mPi(t)=P(t)并且對于?i,j∈{1,2,…m}均有Pi(t)∩Pj(t)=?。設(shè)k1、k2…km分別為P1(t)、P2(t)…Pm(t)中個體的數(shù)目,則∑i=1mki=N。定義第t代種群的熵為:Et=?∑i=1mpilogpi,其中,pi=ki/N。由定義1可知,當(dāng)種群中N個個體各不相同,即m=N時,熵取最大值Emax=logN;當(dāng)種群中個體均相同,即m=1時,熵取最小值Emin=0。種群中個體類型越多,分布越均勻,熵越大。種群熵反映了種群中不同類型個體的分布情況。通過種群熵與種群最大熵的比較,可以衡量出當(dāng)前種群的多樣性程度,令α=Et/Emax,顯然,α∈[0,1]并且α越大,種群中不同個體的數(shù)目越多,種群的多樣性越大,反之,種群的多樣性越小。但是過早收斂現(xiàn)象發(fā)生時,往往僅是適應(yīng)度暫時較大的個體趨于一致,適應(yīng)度較小的個體在種群空間中依然是離散分布的,此時,α值仍然較高,等到α的取值明顯下降時,種群已經(jīng)嚴(yán)重早熟收斂了,這說明種群熵對種群個體過早收斂程度的評價具有一定的滯后性。因此,本文采用較優(yōu)個體熵作為判斷種群過早收斂的指標(biāo),其定義如下:定義2:假設(shè)P(t)為第t代種群,fˉ為當(dāng)前種群的平均適應(yīng)度,取適應(yīng)度大于fˉ的個體組成較優(yōu)個體群,用定義1中的方法計算較優(yōu)個體群的熵,即為當(dāng)前種群的較優(yōu)個體熵,記為E*t,并令E*max為較優(yōu)個體最大熵,α*=E*t/E*max為第t代種群較優(yōu)個體的多樣性程度,α*∈[0,1]。根據(jù)定義2,較優(yōu)個體群由適應(yīng)度大于平均適應(yīng)度的個體組成,排除了適應(yīng)度小于平均適應(yīng)度的差個體對種群分布帶來的影響。α*與α相比,更能夠及時反應(yīng)種群當(dāng)前多樣性程度。3操作概率難以適應(yīng)種群狀態(tài)的變化遺傳算法的參數(shù)中交叉概率和變異概率對算法的性能起著非常的重要。進(jìn)化過程中,種群的狀態(tài)不是一成不變的,采用固定的操作概率難以適應(yīng)種群狀態(tài)的變化,往往導(dǎo)致進(jìn)化過程的停滯不前甚至倒退。本文根據(jù)種群中當(dāng)前較優(yōu)個體多樣性程度及不同適應(yīng)度個體在進(jìn)化中的作用從宏觀和微觀兩個方面對操作概率進(jìn)行動態(tài)調(diào)整,宏觀調(diào)整對當(dāng)前種群操作概率的范圍進(jìn)行調(diào)整,微觀調(diào)整則在宏觀調(diào)整確定的操作概率范圍內(nèi),對參與遺傳操作的個體進(jìn)行操作概率的確定,從而改善遺傳算法的搜索性能。3.1回復(fù)突變體的多樣性當(dāng)種群多樣性較高,即α*較大時,種群中個體包含的不同模式較多,搜索到更優(yōu)個體的潛力較大,應(yīng)適當(dāng)?shù)奶岣呓徊娓怕?減小變異概率,保證個體間進(jìn)行充分的模式重組,促進(jìn)有效模式在個體中的傳播,增加搜索的廣度;而當(dāng)種群多樣性較低,即α*較小時,種群中較優(yōu)個體逐漸趨于相同,應(yīng)提高變異概率,引入新的個體,打破較優(yōu)個體趨同的狀態(tài),避免陷入局部最優(yōu)。具體調(diào)整方法如(1)(2)式:{pc1(t)=pc1+(pc2?pc1)2?α?tpc2(t)=pc2(1)其中,pc1、pc2為初始交叉率范圍,且pc2>pc1;α*t為第t代種群的多樣性程度,α*t∈[0,1];pc1(t)、pc2(t)為第t代種群交叉率范圍。由(1)式可知,當(dāng)α*t=1時,pc1(t)=pc2+pc12,種群整體交叉率較大;當(dāng)α*t=0,pc1(t)=pc1,種群的整體交叉率較小。{pm1(t)=pm1pm2(t)=pm2?pm2?pm12?α?t(2)其中,pm1、pm2為初始變異概率范圍,pm1(t)、pm2(t)為第t代種群變異概率范圍,由(2)式可知,當(dāng)α*t減小時,變異概率的上限pm2(t)增大,種群的整體變異率增大。3.2第t代種群適應(yīng)度計算根據(jù)適應(yīng)度大小可將種群中個體大致分為三類:較優(yōu)個體、中等個體和較差個體。每類個體在種群進(jìn)化過程中的作用各不相同,對應(yīng)的操作概率應(yīng)視個體適應(yīng)度具體情況而定。較優(yōu)個體適應(yīng)度較高,擁有較優(yōu)模式,但較優(yōu)個體間一般差別不大,交叉率可適當(dāng)取小,而較優(yōu)個體與其他兩類個體的交叉率可適當(dāng)取大,有利于優(yōu)秀模式在種群中的傳遞;中等個體適應(yīng)度居中,包含豐富的模式信息,應(yīng)使其以較大概率參加交叉操作。不同適應(yīng)度個體具體交叉情況如表1。根據(jù)表1中的交叉情況,可得參加交叉的兩父個體平均適應(yīng)度與其交叉率的關(guān)系如圖1。由此可得,第t代種群中參加交叉操作的兩父代個體交叉概率如(3)式:pc=?????????pc2(t)?(pc2(t)?pc1(t))?f(t)avg?fˉf(t)avg?f(t)min,fˉ≤f(t)avgpc2(t)?(pc2(t)?pc1(t))?fˉ?f(t)avgf(t)max?f(t)avg,fˉ>f(t)avg(3)其中,fˉ為兩父代個體的平均適應(yīng)度,f(t)avg為第t代種群平均適應(yīng)度,f(t)min為第t代種群中個體最低適應(yīng)度,f(t)max為最高適應(yīng)度。pc2(t)、pc1(t)為經(jīng)宏觀調(diào)整后第t代種群交叉率的上限和下限。對于參加變異操作的個體,若其適應(yīng)度較高于平均適應(yīng)度的應(yīng)采用較小的變異率,以防止優(yōu)秀個體被破壞;若適應(yīng)度低于平均適應(yīng)度則應(yīng)對應(yīng)于較高的變異率。具體方法如(4)式:pm=?????pm1(t)+(pm2(t)?pm1(t))?f(t)max?ff(t)max?f(t)avg,f≥f(t)avgpm2(t),f<f(t)avg(4)其中,f為個體適應(yīng)度,pm1(t)、pm2(t)為經(jīng)宏觀調(diào)整后第t代種群交叉率的上限和下限。4模擬實驗4.1局部尋優(yōu)函數(shù)為了評價改進(jìn)算法的搜索性能,本文將改進(jìn)算法與自適應(yīng)遺傳算法(AGA)、標(biāo)準(zhǔn)遺傳算法進(jìn)行對比實驗,并選用3個難度較大的測試函數(shù):f1:Rosenbrock函數(shù)minf1(x,y)=100(x2-y)2+(1-x)2,-2.048≤x,y≤2.048f1是單極值的非二次函數(shù),但它是病態(tài)的,在y=x2處有一狹長深谷,很難極小化,尋優(yōu)中可能陷入局部解,其在(1,1)處有全局最小值0;f2:Shubert函數(shù)minf2(x,y)={∑i=15icos[(i+1)x+i]}×{∑i=15icos[(i+1)y+i]}+0.5[(x+1.42513)2+(y+0.80032)2],?10≤x,y≤10f2在(0,0)處有最大值為1,該函數(shù)最大值峰周圍有一圈脊,它們的取值均為0.990283,因此很容易陷入局部最大點;f3:Schaffer函數(shù)maxf3(x,y)=0.5?(sinx2+y2√)2?0.5[1+0.001(x2+y2)]2,?100≤x,y≤100f3有760個局部極小點,其中只有一個(-1.42513,-0.80032)為全局最小,最小值為-186.7309,此函數(shù)容易陷入局部極小值-186.3405。4.2改進(jìn)算法仿真實驗實驗中,三種算法均采用確定式采樣選擇和單點交叉,標(biāo)準(zhǔn)遺傳算法的交叉率為0.7、變異率為0.05;AGA和改進(jìn)算法的交叉率均為pc1=0.4,pc2=0.9,變異率為pm1=0.01,pm2=0.1;種群規(guī)模為100,最大運行代數(shù)為1000。將每種算法對不同的函數(shù)連續(xù)運行50次,記錄每次運行結(jié)束時的最優(yōu)解與理想值的平均誤差,搜尋到的最優(yōu)解及搜索到理想值的次數(shù),具體結(jié)果如下表。以上仿真實驗表明,SGA極易陷入局部最優(yōu),而且跳出局部最優(yōu)的幾率很小,并且尋優(yōu)結(jié)果較理想值的平均誤差較大。AGA和改進(jìn)算法在全局搜索性能上較SGA有較大提升,但相比之下,改進(jìn)算法尋優(yōu)結(jié)果較理想值的平均誤差很小,問題求解