一種保持種群多樣性的單變量邊緣分布算法

黃情操

(湖南鐵道職院鐵道牽引與動(dòng)力學(xué)院,湖南株洲 412001)

一種保持種群多樣性的單變量邊緣分布算法

黃情操

(湖南鐵道職院鐵道牽引與動(dòng)力學(xué)院,湖南株洲 412001)

針對(duì)單變量邊緣分布算法(UMDA)求解復(fù)雜優(yōu)化問(wèn)題時(shí)的局限性,本文將均勻變異機(jī)制引入分布估計(jì)算法 (EDAs)領(lǐng)域,提出了一種基于均勻變異的單變量邊緣分布算法。該算法利用均勻變異操作保持種群的多樣性,提高混合算法的全局搜索能力。通過(guò)對(duì)算法的分析和仿真實(shí)驗(yàn)表明與單變量邊緣分布算法(UMDA)相比,改進(jìn)后的保持種群多樣性的單變量邊緣分布算法具有更高的優(yōu)化性能。

分布估計(jì)算法 單變量邊緣分布算法 種群 收斂性 均勻變異算子 多樣性

1 引言

單變量邊緣分布估計(jì)算法(univariate marginal distribution algorithm，UMDA) 是一種基于概率模型的進(jìn)化算法。在該算法中，種群中各變量是相互獨(dú)立的，因而是一種基礎(chǔ)的分布估計(jì)算法(estimation of distri—bution algorithms，EDA)[1，2]。該算法首先利用被選擇的優(yōu)良解集的邊緣分布來(lái)構(gòu)建基因變量的概率分布模型，隨后通過(guò)采樣算子來(lái)產(chǎn)生新一代種群。由于該算法是在宏觀(guān)層次上對(duì)種群進(jìn)行建模，因此算法有時(shí)會(huì)出現(xiàn)過(guò)早收斂的情況，全局最優(yōu)搜索的能力較差。此外，在進(jìn)化種群中，由于個(gè)體趨同往往會(huì)導(dǎo)致種群多樣性的迅速降低，使算法陷入早熟。因此，解決UMDA早熟收斂問(wèn)題的思路之一就是重構(gòu)種群的多樣性。

近年來(lái)，國(guó)內(nèi)外很多學(xué)者從重構(gòu)種群多樣性的角度出發(fā)，提出了很多種改進(jìn)的UMDA算法，歸納起來(lái)，主要有(1)Koumoutsakos等人提出的高斯分布模型的方差制;(2)小生境技術(shù);(3)nadera等提出的多種群并行進(jìn)化[8]等3個(gè)方面。

在各種具體的遺傳操作算子中，變異算子用新的基因值來(lái)替換原有的基因值，從而改變了個(gè)體編碼串的結(jié)構(gòu)，是維持算法的種群多樣性的重要手段一。但是，傳統(tǒng)UMDA算法僅僅通過(guò)選擇算子和基因的重組算子來(lái)實(shí)施進(jìn)化，缺少維持種群多樣性的變異算子。為解決UMDA算法的早熟收斂問(wèn)題，提出一種基于均勻變異的單變量邊緣分布算法(univariate marginal distribution algorithm with uniform mutation，UMDA—UM)。

表1

表2

表3

圖1 變異率為0.01時(shí)兩種算法的比較

圖2 變異率為0.02時(shí)兩種算法的比較

圖3 變異率為0.005時(shí)兩種算法的比較

2 單變量邊緣分布算法

單變量邊緣分布算法是一種分布估計(jì)算法。在該算法中，種群由 M個(gè)個(gè)體組成。在進(jìn)化的每一代，從 M個(gè)個(gè)體中選擇 N個(gè)優(yōu)良解，之后計(jì)算優(yōu)良解集中每一位取1的概率，并由此產(chǎn)生概率分布模型，接著由該模型來(lái)產(chǎn)生新一代的種群。在二進(jìn)制的搜索空間，UMDA算法由一個(gè)概率向量開(kāi)始，其表示個(gè)體中的每個(gè)變量的取值為1或0的概率是相等的，以此概率產(chǎn)生的初始群體可以盡量均勻地分布二進(jìn)制搜索空間。算法通過(guò)提取當(dāng)前群體的一些優(yōu)良解提供的信息來(lái)計(jì)算概率向量，并利用此概率向量來(lái)指導(dǎo)種群進(jìn)化。隨著迭代的進(jìn)行，概率向量的值逐漸收斂于0或1。

圖4 變異率為0.01時(shí)兩種算法的比較

圖5 變異率為0.02時(shí)兩種算法的比較

圖6 變異率為0.005時(shí)兩種算法的比較

3 均勻變異算子

均勻變異[6](uniform mutation)操作指的是用符合某一參數(shù)范圍內(nèi)，均勻分布的隨機(jī)數(shù)，在某個(gè)位置以某一較小的概率來(lái)代替原個(gè)體編碼串中的基因位上的基因值的過(guò)程。具體操作過(guò)程如下：(1)首先依次指定個(gè)體的編碼串中的某個(gè)基因位為變異點(diǎn);(2)隨后對(duì)每一個(gè)變異點(diǎn)，以概率 pm從其對(duì)應(yīng)基因的參數(shù)取值范圍內(nèi)取一個(gè)隨機(jī)數(shù)來(lái)替換原有的基因值。若有一個(gè)體的值為：，其中若 xk為變異點(diǎn)，其取值的范圍為，則在該點(diǎn)對(duì)該個(gè)體 xk進(jìn)行均勻變異后，可得到一新個(gè)體。其中個(gè)體變異點(diǎn)的新基因值，式中 r為參數(shù)范圍內(nèi)符合均勻分布的一個(gè)隨機(jī)數(shù)。

4 基于均勻變異的單變量邊緣分布算法

在算法中，將均勻變異算子引入U(xiǎn)MDA算法，其具體描述如下：

(1)隨機(jī)產(chǎn)生 M 個(gè)個(gè)體作為初始群體lD， l=0;(2)計(jì)算 M個(gè)個(gè)體的適應(yīng)值，若符合終止條件，算法結(jié)束，否則繼續(xù)進(jìn)行;(3)進(jìn)行選擇操作，選擇 N＜M個(gè)個(gè)體作為優(yōu)勢(shì)群體;(4)對(duì)優(yōu)勢(shì)群體進(jìn)行均勻變異;(5)由均勻變異的新優(yōu)勢(shì)群體構(gòu)建概率模型，估計(jì)聯(lián)合概概率分布

5 算法的多樣性分析及實(shí)驗(yàn)仿真分析

算法中個(gè)體是采用二進(jìn)制編碼方式構(gòu)成染色體，個(gè)體之間的距離是采用漢明距離。個(gè)體之間的差異用公式

表示。對(duì)于其種群的多樣性測(cè)度，設(shè)： X為個(gè)體 x的種群集， xij為個(gè)體 xi在第 j位的取值，種群的集合G表示為：

該種群全部個(gè)體的多樣性測(cè)度表示為：

其中 N為種群規(guī)模大小， m為染色體的長(zhǎng)度。其的時(shí)間復(fù)雜度為

為檢驗(yàn)所提出的算法的性能以及算子變異率的大小對(duì)算法性能的影響， 把所提出的改進(jìn)算法UMDA-UM以及簡(jiǎn)單的邊緣分布估計(jì)算法UMDA對(duì)測(cè)試函數(shù)[10]進(jìn)行了對(duì)比測(cè)試。

測(cè)試函數(shù)集2

在UMDA算法和改進(jìn)算法UMDA-UM中，選取的群體規(guī)模為500，變量的數(shù)目為30，截?cái)鄥?shù)為0.5，變異概率為0.01。為了減小隨機(jī)誤差的影響，取30次結(jié)果的平均值，結(jié)果如表1所示。

在保持算法其他參數(shù)不變，而變異概率增大為0.02的情況下，結(jié)果如圖2所示。

在保持算法其他參數(shù)不變，而變異概率減小為0.005的情況下，結(jié)果如圖3所示。

從實(shí)驗(yàn)數(shù)據(jù)可以看出，在變異率為0.01的情況下，UMDA-UM算法在開(kāi)始進(jìn)化的階段的適應(yīng)值離最優(yōu)值的距離比UMDA計(jì)算出來(lái)的適應(yīng)值離最優(yōu)值的距離要大，這是由于加入了均勻變異因子以后，增加了種群的多樣性;隨著進(jìn)化的進(jìn)行，UMDA-UM算法跟UMDA算法的擬合度比較好，隨后，UMDA-UM算法超越了UMDA算法，較快較穩(wěn)定的收斂到全局最優(yōu)解。

增大變異率到0.02的情況下，UMDA-UM算法在開(kāi)始進(jìn)化的階段的適應(yīng)值離最優(yōu)值的距離比UMDA計(jì)算出來(lái)的適應(yīng)值離最優(yōu)值的距離要大很多，也比變異率為0.01的時(shí)候要大，這是由于增加變異因子的變異率后，進(jìn)一步增加了群體的多樣性;使群體的搜索空間加大。隨著進(jìn)化的進(jìn)行，UMDA-UM算法快速超越了UMDA算法，較快的收斂到全局最優(yōu)解。

在減小變異率為0.005的情況下，UMDA-UM算法在進(jìn)化的過(guò)程中表現(xiàn)出來(lái)的收斂性要比UMDA算法的收斂性要差，這是因?yàn)樵黾恿俗儺愐蜃右院?，相?duì)于增加了群體的多樣性使群體的搜索空間加大了。隨著進(jìn)化的進(jìn)行，UMDA-UM算法慢慢的超越了UMDA算法，最后收斂到全局最優(yōu)解。

在本算法中，變異率的取值大小對(duì)算法的性能有著重要影響。變異率取值過(guò)大，會(huì)導(dǎo)致算法或者迅速收斂，或者根本不收斂，從而影響算法的穩(wěn)定性;變異率過(guò)小，會(huì)使算法的收斂速度變慢。因此，變異率的合適與否是算法性能的一個(gè)重要指標(biāo)。

6 結(jié)語(yǔ)

本文提出一種維持種群多樣性的單變量分布估計(jì)算法UMDA—UM，通過(guò)在UMDA中增加均勻變異算子來(lái)保持種群的多樣性，進(jìn)而克服傳統(tǒng)UMDA中存在的早熟收斂和后期收斂速度慢的問(wèn)題。通過(guò)對(duì)測(cè)試函數(shù)來(lái)測(cè)試算法性能，并與傳統(tǒng)UMDA進(jìn)行實(shí)驗(yàn)比較，結(jié)果表明該方法能夠有效防止早熟收斂，在優(yōu)化解的質(zhì)量和收斂速度方面具有較好的性能。但是，該方法的缺點(diǎn)是變異率參數(shù)的設(shè)置對(duì)算法性能有著比較大的影響，需要靠經(jīng)驗(yàn)試湊對(duì)變異率參數(shù)進(jìn)行設(shè)置。后續(xù)的研究工作包括參數(shù)的自適應(yīng)調(diào)整以進(jìn)一步提高算法的性能以及對(duì)算法實(shí)現(xiàn)的收斂性等給出嚴(yán)密的數(shù)學(xué)分析和證明。

[1]周樹(shù)德,孫增圻.分布估計(jì)算法綜述[J].自動(dòng)化學(xué)報(bào),2007,33(2)：113—121.

[2]張慶彬,吳惕華,劉波.克隆選擇單變量邊緣分布算法[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),2007,10.

[3]程玉虎,王雪松,郝名林.一種多樣性保持的分布估計(jì)算法[J].電子學(xué)報(bào),2010.3.

[4]吳紅,許永平,石福麗,楊峰.基于改進(jìn)分布估計(jì)算法的二維航跡規(guī)劃[J].計(jì)算機(jī)工程,2010.8.