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

黃情操

(湖南鐵道職院鐵道牽引與動力學院,湖南株洲 412001)

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

黃情操

(湖南鐵道職院鐵道牽引與動力學院,湖南株洲 412001)

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

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

1 引言

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

近年來，國內外很多學者從重構種群多樣性的角度出發，提出了很多種改進的UMDA算法，歸納起來，主要有(1)Koumoutsakos等人提出的高斯分布模型的方差制;(2)小生境技術;(3)nadera等提出的多種群并行進化[8]等3個方面。

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

表1

表2

表3

圖1 變異率為0.01時兩種算法的比較

圖2 變異率為0.02時兩種算法的比較

圖3 變異率為0.005時兩種算法的比較

2 單變量邊緣分布算法

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

圖4 變異率為0.01時兩種算法的比較

圖5 變異率為0.02時兩種算法的比較

圖6 變異率為0.005時兩種算法的比較

3 均勻變異算子

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

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

在算法中，將均勻變異算子引入UMDA算法，其具體描述如下：

(1)隨機產生 M 個個體作為初始群體lD， l=0;(2)計算 M個個體的適應值，若符合終止條件，算法結束，否則繼續進行;(3)進行選擇操作，選擇 N＜M個個體作為優勢群體;(4)對優勢群體進行均勻變異;(5)由均勻變異的新優勢群體構建概率模型，估計聯合概概率分布

5 算法的多樣性分析及實驗仿真分析

算法中個體是采用二進制編碼方式構成染色體，個體之間的距離是采用漢明距離。個體之間的差異用公式

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

該種群全部個體的多樣性測度表示為：

其中 N為種群規模大小， m為染色體的長度。其的時間復雜度為

為檢驗所提出的算法的性能以及算子變異率的大小對算法性能的影響， 把所提出的改進算法UMDA-UM以及簡單的邊緣分布估計算法UMDA對測試函數[10]進行了對比測試。

測試函數集2

在UMDA算法和改進算法UMDA-UM中，選取的群體規模為500，變量的數目為30，截斷參數為0.5，變異概率為0.01。為了減小隨機誤差的影響，取30次結果的平均值，結果如表1所示。

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

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

從實驗數據可以看出，在變異率為0.01的情況下，UMDA-UM算法在開始進化的階段的適應值離最優值的距離比UMDA計算出來的適應值離最優值的距離要大，這是由于加入了均勻變異因子以后，增加了種群的多樣性;隨著進化的進行，UMDA-UM算法跟UMDA算法的擬合度比較好，隨后，UMDA-UM算法超越了UMDA算法，較快較穩定的收斂到全局最優解。

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

在減小變異率為0.005的情況下，UMDA-UM算法在進化的過程中表現出來的收斂性要比UMDA算法的收斂性要差，這是因為增加了變異因子以后，相對于增加了群體的多樣性使群體的搜索空間加大了。隨著進化的進行，UMDA-UM算法慢慢的超越了UMDA算法，最后收斂到全局最優解。

在本算法中，變異率的取值大小對算法的性能有著重要影響。變異率取值過大，會導致算法或者迅速收斂，或者根本不收斂，從而影響算法的穩定性;變異率過小，會使算法的收斂速度變慢。因此，變異率的合適與否是算法性能的一個重要指標。

6 結語

本文提出一種維持種群多樣性的單變量分布估計算法UMDA—UM，通過在UMDA中增加均勻變異算子來保持種群的多樣性，進而克服傳統UMDA中存在的早熟收斂和后期收斂速度慢的問題。通過對測試函數來測試算法性能，并與傳統UMDA進行實驗比較，結果表明該方法能夠有效防止早熟收斂，在優化解的質量和收斂速度方面具有較好的性能。但是，該方法的缺點是變異率參數的設置對算法性能有著比較大的影響，需要靠經驗試湊對變異率參數進行設置。后續的研究工作包括參數的自適應調整以進一步提高算法的性能以及對算法實現的收斂性等給出嚴密的數學分析和證明。

[1]周樹德,孫增圻.分布估計算法綜述[J].自動化學報,2007,33(2)：113—121.

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

[3]程玉虎,王雪松,郝名林.一種多樣性保持的分布估計算法[J].電子學報,2010.3.

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