遺傳算法的3種改進方法和分析

郭凱

（中北大學 電子測試技術國家重點實驗室，太原 030051）

0 引言

遺傳算法(Genetic algorithm,GA)是一種借鑒生物界自然選擇和進化機制發展起來的高度并行、隨機、自適應的全局優化概率搜索算法[1]。它模擬了自然選擇和遺傳中發生的復制、交叉和變異等現象[2]。先產生初始種群，通過選擇、交叉和變異操作，產生一群更適合環境的個體，經過一代一代的進化，使種群最后收斂到一群最適合環境的個體，求得問題的最優解。由于GA具有簡單、通用、魯棒性強和適應于并行分布處理等特點,已經成功應用到很多領域[3]。雖然遺傳算法有許多的優點，但是在處理復雜的非線性問題時，容易出現個體的早熟現象，使算法不能跳出局部極值，難以找到最優解。

針對遺傳算法的早熟現象，很多學者提出了改進方案。改進方法主要在3個方面,即改進遺傳操作、調整參數和采用多種群遺傳算法。本文具體的分析了3種改進遺傳算法，并通過一個實例來探索它們在實際問題中的應用。

1 3種改進遺傳算法

1.1 利用擬隨機Halton序列產生初始種群

遺傳算法中選擇初始種群的目的就是為了盡可能地獲取更多有關目標函數的信息[4]，這在算法操作中非常重要，經常對算法的最終優化結果有一定的影響。一般在種群初始化時，我們用產生偽隨機數的方法隨機地生成分布不均勻的初始種群，但是，初始種群中的個體均勻分布比隨機生成個體可以獲得更多的目標函數信息，在算法搜索中更有優勢。

使用擬隨機序列可以產生具有低差異度的個體，它以犧牲隨機性為代價，換取均勻性的提高。目前已提出的擬隨機序列主要有Van der Vorput序列、Faure序列、Sobol序列、Halton序列及Niederreiter的(t,s)序列[5]。Halton序列[6]是一個標準的低差異度序列。與其它低差異序列相比，Halton序列執行起來要簡單得多，因為它對每一維上利用基本的逆函數，而用逆函數產生小數比較容易實現[7]。本文利用擬隨機序列Halton序列產生初始種群。

1.2 自適應變異概率

遺傳算法的參數中變異概率Pm的選擇對遺傳算法行為和性能有較大影響。傳統的遺傳算法對個體隨機地進行變異操作,當變異概率過大時,容易使種群中適應度好的優秀個體遭到破壞,從而使算法陷入一種單純的隨機搜索當中,而變異率過低又難以引入新的基因[8]。而且對于不同的優化問題，如果經過反復實驗來確定Pm的值，比較繁瑣。為了有效地保留種群中的優良個體模式,又保證有效地產生一些較好的新個體模式，對傳統遺傳算法中的變異概率進行改進是有必要的。

本文采用自適應變異概率。對于高于群體平均適應度的個體，采用較低的Pm，而對于低于群體平均適應度的個體，采用較高的Pm。使用公式（1）。

其中：Pm1=0.1, Pm2=0.001,fmax為群體中最大的適應度值；favg為每代群體的平均適應度值；f為要變異個體的適應度值。

1.3 雙種群遺傳算法

本文采用的雙種群遺傳算法，其思路為：先產生一個種群，然后將其分為相同大小的兩個子種群，兩個子種群采用一樣的選擇策略、交叉算子和變異算子，分別進化一定代以后，將兩個子種群的最優個體進行交叉，再與各種群剩余的個體合并，在合并時，使兩個子種群的原有最優個體代替適應度最低的個體而保留下來。最后，新種群再進行遺傳算法操作。

通過這種操作，在逐漸單一的種群中注入了新的個體，而且這些新注入的個體是已經經過一定進化選擇得到的優秀個體交叉產生的，從而使新的種群更有效地向最優解收斂。

2 計算機仿真和結果分析

為了考察本文所述的3種改進遺傳算法的性能，選取了一個實例進行數值模擬。所選實例為：

該函數是一個一元多峰函數，在[-1,2]上存在多個極大值點，它在該范圍內的圖形如圖1所示。

圖1 實例函數在[-1,2]范圍上的圖形

我們把3種改進遺傳算法和傳統遺傳算法，各自運行10次，每次運行得到的函數值及其對應的變量值被記錄下來，如表1所示。

表1 應用3種改進遺傳算法和傳統遺傳算法得到的計算結果（10次運行的平均值）

由表1可以看出：3種改進遺傳算法都比傳統的遺傳算法能較好的接近最優解x=1.8505,f(x)=3.8503。采用實值的方法結果較一般，主要是在一元函數中，實值的單點交叉不起作用，種群進化時主要依賴生成的初始種群和變異操作。

3 結論

總的來說，改進方法對比傳統方法，在精確性上都有所提高。另外，3種改進也可以做進一步改善，通過對halton序列進行合理加擾可以得到分布更加均勻的初始種群；對于有的非線性方程組求解問題，可以嘗試尋找能取得更高精度的變異概率；也可以擴展種群到更多，以提高種群的多樣性。多數時候，還可以將幾種改進的方法有效地結合起來處理更復雜的優化問題。

[1] HOLLAND J H.Adaption in natural and artificial systems[M].Mass:MIT Press,1992:1.

[2] 雷英杰，張善文. MATLAB遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2005.

[3] 張頂學，關治洪，劉新芝.基于捕食搜索策略的遺傳算法研究[J].計算機應用研究，2008,25（4）：1006.

[4] H.MAARANEN,K. M I E T T I N E N,M. M.MAKELA.Quasi-Random Initial Population for Genetic Algorithms [J].Computers & Mathematics with Application，2004（47）:1887.

[5] 黃美發，景暉，鐘艷茹等，基于擬隨機序列的三維模型表面采樣方法[J].計算機工程，2008，34（14）：264.

[6] J.Halton.On the efficiency of certain quasirandom sequences of points in evaluating multidimensional integrals[J].Numersiche Mathematik，1960（2）:84-90.

[7] 李寧.擬蒙特卡羅中Halton序列的去隨機化[D].烏魯木齊：新疆大學,2008.

[8] 王小平，曹立明.遺傳算法—理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.