一種多種群多樣性保持的分布估計算法

一種多種群多樣性保持的分布估計算法

1eda算法改進分布估算算法是一種新的基于團隊搜索的進步計算方法。不通過傳統(tǒng)的橫向突變方法生成年輕一代的后代，而是使用統(tǒng)計分析方法對優(yōu)秀個體進行統(tǒng)計分析，建立概率模型，然后通過采樣生成后代的解。在重復(fù)統(tǒng)計建模和采樣過程中，我們可以得到問題的最佳解。這是統(tǒng)計學(xué)習(xí)和計算的結(jié)合。可以看出,與傳統(tǒng)進化算法不同,EDA是基于對整個群體建立數(shù)學(xué)模型,直接描述整個群體的進化趨勢,是對生物進化“宏觀”層面上的數(shù)學(xué)建模,具有良好的全局搜索能力,但局部優(yōu)化能力較差.因此,EDA能很好地解決低維單模態(tài)優(yōu)化問題,然而對于復(fù)雜的高維多模態(tài)優(yōu)化問題,常常陷入局部最優(yōu)解,出現(xiàn)早熟收斂現(xiàn)象.不同于EDA,遺傳算法(GeneticAlgorithm,GA)、粒子群優(yōu)化(ParticleSwarmOptimization,PSO)和差分進化(DifferentialEvolution,DE)算法是基于對種群中的各個個體進行遺傳操作(交叉、變異等)來實現(xiàn)群體的進化的,是對生物進化“微觀”層面上的數(shù)學(xué)建模,具有較好的局部優(yōu)化能力,但全局搜索能力較差.為此,可以將EDA與GA、PSO和DE等算法進行混雜,力求做到算法探索與利用的有效均衡,以解決EDA的早熟收斂問題.造成EDA早熟收斂的另一個原因是,進化種群中個體趨同、種群多樣性的迅速下降.因此,解決EDA早熟收斂問題的另一種思路是重構(gòu)種群的多樣性.近年來,國內(nèi)外學(xué)者從重構(gòu)種群多樣性的角度出發(fā),提出了各種改進EDA算法,歸納起來,主要有以下3個方面:(1)高斯分布模型的方差控制.Koumoutsakos等提出了一種用于保持EDA種群多樣性的自適應(yīng)方差尺度縮放技術(shù),具體方法是:在每次迭代過程中,檢查最優(yōu)適應(yīng)度值是否真正得到改進,若確實如此,則可將當(dāng)前估計得到的高斯分布模型的方差值適當(dāng)放大以增大EDA的搜索范圍;若不是這樣,則需將方差適當(dāng)縮小.(2)小生境技術(shù).同傳統(tǒng)遺傳算法中的小生境技術(shù),分布估計算法中的小生境技術(shù)主要是按小生境函數(shù)值在種群中的個體之間進行平衡,并對生成新種群的替換策略進行調(diào)整,使個體在特定生存環(huán)境中進化,這樣可形成有效的壓力以保證進化過程中種群的多樣性.(3)多種群并行進化.Madera等提出一種分布式孤島型EDA(distributedislandEDA,dEDA),具體方法是:在搜索空間中將初始種群劃分成多個子種群(對應(yīng)多個概率分布模型),各自獨立進化.每隔一定進化代數(shù),按完全網(wǎng)狀模型交換各種群最優(yōu)個體,從而生成新的種群,在此基礎(chǔ)上進行下一代種群進化周期的進化,直到滿足算法終止條件為止.在各種遺傳操作算子中,變異算子用新的基因值替換原有基因值,從而可以改變個體編碼串的結(jié)構(gòu),是維持種群多樣性,防止出現(xiàn)早熟收斂的重要手段.但是,傳統(tǒng)分布估計算法僅僅通過選擇算子和基因池重組算子來實施進化,缺少維持種群多樣性的變異算子.因此,為解決EDA的早熟收斂問題,提出一種多樣性保持的分布估計算法(EstimationofDistributionAlgorithmwithDiversityPreservation,EDA-DP),在傳統(tǒng)EDA中加入混沌變異操作,利用混沌運動具有的隨機性、遍歷性、初值敏感性和規(guī)律性等特點在解空間內(nèi)進行優(yōu)化搜索,使之跳出局部極值區(qū)、快速找到全局最優(yōu)解.12個基準(zhǔn)測試函數(shù)驗證了EDA-DP的可行性和有效性.2混沌變異算法混沌狀態(tài)廣泛存在于自然現(xiàn)象和社會現(xiàn)象中,是非線性系統(tǒng)中一種較為普遍的現(xiàn)象,其行為復(fù)雜且類似隨機.但看似一片混亂的混沌變化過程并不完全混亂,而是存在著精細的內(nèi)在規(guī)律性.混沌運動具有的隨機性、遍歷性和規(guī)律性等獨特的性質(zhì),使其介于確定性和隨機性之間,具有豐富的時空動態(tài).最重要的是,混沌運動能在一定范圍內(nèi)按其自身的“規(guī)律”不重復(fù)地遍歷所有狀態(tài).混沌變異優(yōu)化算法就是利用這些混沌變量的隨機性、遍歷性、規(guī)律性特點在解空間內(nèi)進行優(yōu)化搜索,能夠較好地使種群保持多樣性.對于一維變量,混沌變異模型一般采用一維Logistic映射模型:at+1=λat(1-at)(1)式中,λ為控制參數(shù),變化范圍為.當(dāng)a0取之間的一個隨機數(shù),在控制參數(shù)λ確定的情況下,可以得到一個混沌時間序列a1,a2,…,aNP.隨著λ值的不同,系統(tǒng)呈現(xiàn)不同特性:(1)0<λ≤1時,系統(tǒng)特性比較簡單,除了不動點0外,沒有其他周期點.(2)1<λ<3時,系統(tǒng)也比較簡單,只有兩個不動點,1和1-1/λ.(3)3≤λ≤4時,系統(tǒng)極為復(fù)雜,呈現(xiàn)非周期性,隨著λ值增大,系統(tǒng)遍歷范圍也增加.3類目標(biāo)值的計算多樣性保持分布估計算法的基本思想是:在傳統(tǒng)分布估計算法中引入混沌變異,變異半徑根據(jù)個體適應(yīng)度值和種群中各個體之間的距離信息自適應(yīng)變化.為進一步增強種群的多樣性,在選擇下一代種群時,利用個體在種群中的濃度調(diào)整其適應(yīng)度值,并根據(jù)調(diào)整后的適應(yīng)度值產(chǎn)生下一代種群.具體算法步驟如下:Step1初始化種群.將待優(yōu)化問題解在空間中的坐標(biāo)做為種群中各個獨立的個體,采用十進制編碼,如:Xj,G=(xj,1,G,…xj,i,G,…,xj,n,G)(2)式中,i=1,2,…,n,j=1,2,…,NP,G=1,2,…,Gmax,n為需要優(yōu)化的參數(shù)個數(shù),即為待優(yōu)化問題的維數(shù),NP為種群規(guī)模,Gmax為最大進化代數(shù).為使初始種群不重復(fù)地隨機遍歷整個解空間,采用一維Logistic模型,具體步驟如下:(1)隨機產(chǎn)生一組[0,1]之間的初始值,a0=rand(1,n);(2)將n維向量a0代入式(1),給定λ值,經(jīng)NP次迭代計算就可得到在范圍內(nèi)的混沌時間序列a1,a2,…,aNP.令A(yù)=[a1,a2,…,aNP]T,則A為NP×n維矩陣;(3)將混沌時間序列的取值范圍從擴展到待優(yōu)化問題的取值范圍,初始種群的第j個個體的第i個基因位可表示為:xj,i,1=low+(high-low)A(j,i)(3)式中,low為解空間的下限值,high為解空間的上限值.Step2評價初始種群.求種群中每個個體對待優(yōu)化問題的目標(biāo)值,設(shè)目標(biāo)函數(shù)為f(X),求函數(shù)的極小值;Step3適應(yīng)度分配,按線性分配,壓差為2的方式分配.首先對目標(biāo)函數(shù)值進行降序排列,目標(biāo)函數(shù)值最大,即最小適應(yīng)度個體放在列表的第一個位置,最大適應(yīng)度值個體放在位置NP上.那么,種群中第j個個體的適應(yīng)度值fit(j)可根據(jù)它在列表中排序的位置position(j)來確定,即:fit(j)=2-sp+2(sp-1)position(j)-1ΝΡ-1(4)(j)=2?sp+2(sp?1)position(j)?1NP?1(4)式中,position(j)為在區(qū)間[1,NP]內(nèi)取值的整數(shù),選擇壓差sp可在區(qū)間內(nèi)取值,此處sp=2.Step4執(zhí)行自適應(yīng)混沌變異,以概率1對每個個體進行自適應(yīng)混沌變異.為了變異后得到較好的解,在變異時考慮個體的適應(yīng)度值,對于較好的個體在較小的范圍內(nèi)變異,則第j個個體的第i個基因的變異半徑可表示為:r(j,i)=C(i)1-fit(j)maxj′=1,2,?ΝΡfit(j′)(5)r(j,i)=C(i)1?fit(j)maxj′=1,2,?NPfit(j′)(5)式中,C(i)為變異步長.變異步長對算法的性能影響較大,此處采用自適應(yīng)步長以加快算法的收斂.在進化的初期,需要一個較大的步長,以便在較大的空間內(nèi)搜索解,而在進化的后期要求以較小的步長變異進行精細搜索,使其在較好解的周圍進一步搜索最優(yōu)解.根據(jù)進化過程中種群本身的信息來確定步長,則步長可表示為:C(i)=maxj′=1,2,?ΝΡ(xj′,i,G)-minj′=1,2,?ΝΡ(xj′,i,G)DΙV(6)C(i)=maxj′=1,2,?NP(xj′,i,G)?minj′=1,2,?NP(xj′,i,G)DIV(6)式中,DIV為一常數(shù).由于保證一定的變異步長能使算法保持一定的隨機性,增大跳出局部最優(yōu)解的概率,因此,當(dāng)C(i)<Cmin(Cmin為事先給定的最小變異步長)時,令C(i)=Cmin.個體xj,i,G經(jīng)混沌變異后可表示為:x′j,i,G=xj,i,G+r(j,i)*2(1-2A(j,i))(7)式中,A(j,i)為本次進化過程中按Logistic混沌模型產(chǎn)生的Logistic序列構(gòu)成的矩陣A中的元素,具體實現(xiàn)方法同Step1中的步驟;2(1-2A(j,i))是為了將矩陣A中值的變化范圍從擴大到[-2,+2],以使混沌變異的變化范圍與傳統(tǒng)的高斯變異相當(dāng).Step5對個體進行倒序操作,以概率pdao<1對種群中的個體執(zhí)行倒序操作.首先,在[1,NP]之間隨機選取兩個整數(shù)p和q,設(shè)p<q,將個體的兩個整數(shù)之間的決策量倒序,則對個體X′j,G=(x′j,1,G,x′j,2,G,…,x′j,p,G,x′j,p+1,G,…,x′j,q-1,G,x′j,q,G,…,x′j,n,G)執(zhí)行倒序操作后,可得新個體X″j,G=(x′j,1,G,x′j,2,G,…,x′j,q,G,x′j,q-1,G,…,x′j,p+1,G,x′j,p,G,…,x′j,n,G).Step6評價經(jīng)混沌變異和倒序操作后的種群X″.對于個體X″j,G,如果f(X″j,G)<f(Xj,G),則用X″j,G代替Xj,G,得到新的種群X.Step7用分布估計算法產(chǎn)生下一代種群,算法步驟如下:(1)從種群X中選出M(M<NP)個較優(yōu)的個體,對所選樣本進行統(tǒng)計分析,建立單變量高斯模型;(2)按建立的單變量高斯統(tǒng)計模型產(chǎn)生K*NP(K>1)個新的個體;(3)評價新產(chǎn)生的所有個體,并從新產(chǎn)生的個體中選出NP個個體作為下一代種群.為保持種群的多樣性,不僅按個體適應(yīng)度值的大小選擇下一代種群,同時考慮個體的濃度.個體的濃度越大,說明種群中該個體或與該個體相近的個體數(shù)越多;個體濃度越小,則該個體或與該個體相近的個體數(shù)越少.因而,個體的選擇概率取決于個體的適應(yīng)度值和濃度,高適應(yīng)度值和低濃度個體的選擇概率大,該個體受到促進;反之,低適應(yīng)度值和高濃度個體選擇概率相對較小,該個體受到抑制.下一代種群產(chǎn)生策略如下:①計算種群中各個體與其他個體的距離之和,則第s個個體與其他個體的距離之和為:d(s)=∑k*ΝΡl=1k*NPl=1√(Xs,G-Xl,G)2(8)(Xs,G?Xl,G)2????????????√(8)②對求得的d(s)歸一化處理得d′(s)=d(s)maxs=1,2,?,Κ*ΝΡd(s);③求得個體的濃度ρ(s)=1d′(s);④根據(jù)個體的濃度調(diào)整個體的適應(yīng)度值fit′(s)=fit(s)ρ(s),按調(diào)整后的個體適應(yīng)度值從大到小對個體排序,并從中選擇NP個作為下一代種群.Step8檢查是否滿足終止進化條件,若滿足則停止迭代,否則轉(zhuǎn)Step3.常用的終止條件是設(shè)定最大進化代數(shù)或最大允許誤差.4算法的進化和性能分析為驗證EDA-DP的性能,并與傳統(tǒng)EDA和文中的dEDA進行比較,選擇了12個具有代表性的高維基準(zhǔn)測試函數(shù)進行測試,如表1所示.函數(shù)定義如下:函數(shù)f11和f12函數(shù)中的u和yi,按如下方式計算,當(dāng)x>a時,u(x,a,b,c)=b(x-a)c;當(dāng)x<-a時,u(x,a,b,c)=b(-x-a)c;當(dāng)-a<x<a時,u(x,a,b,c)=0?yi=1+14(xi+1).仿真過程中,各算法的參數(shù)設(shè)置情況為:傳統(tǒng)EDA的Gmax=1000,NP=200;dEDA中,Gmax=1000,采用4個并行的獨立種群,各種群NP=200,個體每隔20代按完全網(wǎng)狀模型遷移一次,遷移概率為0.2;EDA-DP中,Gmax=1000,NP=200,M=110,λ=3.9,K=1.5,Cmin=0.2,pdao=0.5,對函數(shù)f4,f7,f10有DIV=20,其他函數(shù)DIV=15.采用如下3種性能指標(biāo)測試算法性能:1)固定進化代數(shù)內(nèi)算法平均最優(yōu)結(jié)果.雖然此時所得結(jié)果可能不靠近最優(yōu)結(jié)果,僅僅是局部最優(yōu)點附近一個適應(yīng)度較小點,但此性能指標(biāo)能在一定程度上反映出算法的收斂速度.本文取此固定進化代數(shù)為500.2)到達確定閾值的平均進化代數(shù).此性能指標(biāo)也是算法進化速度測試指標(biāo),但不同于上述指標(biāo),此時可能意味著算法已經(jīng)靠近了全局最優(yōu)位置.本文中函數(shù)f1、f2、f4、f5、f8、f11和f12的閾值取為E-8,函數(shù)f3的閾值為0.05,函數(shù)f6的閾值為0.5,函數(shù)f7的閾值為-41898,函數(shù)f9的閾值為-78.3323,函數(shù)f10的閾值為0.002.當(dāng)運行代數(shù)達到2000代而仍未滿足學(xué)習(xí)誤差精度時,則認為算法已陷于局部最優(yōu)解,且其進化代數(shù)不計入平均進化代數(shù).3)達標(biāo)率.通過計算算法到達預(yù)設(shè)閾值的次數(shù)占規(guī)定進化總次數(shù)的比例,測試算法的可靠性.考慮性能指標(biāo)1,表2給出了500代內(nèi)3種算法優(yōu)化上述測試函數(shù)30次所得平均優(yōu)化結(jié)果.由表2可以看出,與EDA和dEDA相比,對于函數(shù)f1、f2、f4、f5、f6、f7、f8、f9、f10、f11和f12,EDA-DP能在500代之內(nèi)得到較優(yōu)結(jié)果;對于函數(shù)f3,EDA-DP所得結(jié)果略劣于dEDA,但是優(yōu)于EDA.因此,考慮全部優(yōu)化函數(shù),EDA-DP能在規(guī)定進化代數(shù)內(nèi)得到較為理想的優(yōu)化結(jié)果,甚至得到滿意解.表3給出了獨立運行30次3種優(yōu)化算法獲得的最優(yōu)解的平均值與方差.圖1至圖6描述了3種算法對于函數(shù)f4、f6、f7、f9、f11和f12,所得最優(yōu)結(jié)果與進化代數(shù)的曲線圖,其中橫坐標(biāo)為進化代數(shù),縱坐標(biāo)為優(yōu)化求解結(jié)果.由表2和3可知,對于函數(shù)f4、f6、f7、f9、f11和f12,EDA在進化500代和2000代所得優(yōu)化結(jié)果是一致的,這表明EDA在進化后期已經(jīng)陷入了早熟收斂,進化趨于停滯,這一點由圖1至圖6也能得到同樣的結(jié)果.另外,由表3出示的數(shù)據(jù)可以看出,EDA-DP所得結(jié)果要不同程度地優(yōu)于dEDA(函數(shù)f3和f10除外),并且明顯優(yōu)于EDA,EDA-DP甚至能夠得到函數(shù)f1、f2、f4、f5、f7、f8、f9、f11和f12的全局最優(yōu)解(此處E-15視為0).值得一提的是,對于函數(shù)f7,EDA和dEDA均無法找到全局最優(yōu)解,而由表2可知,EDA-DP卻能在500代內(nèi)即可進化到全局最優(yōu)解.這是由于在EDA中引入了混沌變異和個體濃度的思想,增強了EDA保持種群多樣性和避開局部最優(yōu)解的能力.表4給出了不同算法的達標(biāo)率及平均進化代數(shù).對于函數(shù)f1、f2、f3、f5、f8,3種算法的達標(biāo)率均為100%,但是考慮性能指標(biāo)2,EDA和dEDA所需進化代數(shù)要明顯多于EDA-DP(函數(shù)f3除外).另外,考慮函數(shù)f4、f6、f7、f9、f10、f12,EDA-DP同樣能以較高的達標(biāo)率得到滿意結(jié)果,而EDA的達標(biāo)率均為0.特別地,對于函數(shù)f6和f7,dEDA的達標(biāo)率也為0,表明