郭凱

（中北大學(xué) 電子測(cè)試技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，太原 030051）

0 引言

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

針對(duì)遺傳算法的早熟現(xiàn)象，很多學(xué)者提出了改進(jìn)方案。改進(jìn)方法主要在3個(gè)方面,即改進(jìn)遺傳操作、調(diào)整參數(shù)和采用多種群遺傳算法。本文具體的分析了3種改進(jìn)遺傳算法，并通過一個(gè)實(shí)例來探索它們?cè)趯?shí)際問題中的應(yīng)用。

1 3種改進(jìn)遺傳算法

1.1 利用擬隨機(jī)Halton序列產(chǎn)生初始種群

遺傳算法中選擇初始種群的目的就是為了盡可能地獲取更多有關(guān)目標(biāo)函數(shù)的信息[4]，這在算法操作中非常重要，經(jīng)常對(duì)算法的最終優(yōu)化結(jié)果有一定的影響。一般在種群初始化時(shí)，我們用產(chǎn)生偽隨機(jī)數(shù)的方法隨機(jī)地生成分布不均勻的初始種群，但是，初始種群中的個(gè)體均勻分布比隨機(jī)生成個(gè)體可以獲得更多的目標(biāo)函數(shù)信息，在算法搜索中更有優(yōu)勢(shì)。

使用擬隨機(jī)序列可以產(chǎn)生具有低差異度的個(gè)體，它以犧牲隨機(jī)性為代價(jià)，換取均勻性的提高。目前已提出的擬隨機(jī)序列主要有Van der Vorput序列、Faure序列、Sobol序列、Halton序列及Niederreiter的(t,s)序列[5]。Halton序列[6]是一個(gè)標(biāo)準(zhǔn)的低差異度序列。與其它低差異序列相比，Halton序列執(zhí)行起來要簡(jiǎn)單得多，因?yàn)樗鼘?duì)每一維上利用基本的逆函數(shù)，而用逆函數(shù)產(chǎn)生小數(shù)比較容易實(shí)現(xiàn)[7]。本文利用擬隨機(jī)序列Halton序列產(chǎn)生初始種群。

1.2 自適應(yīng)變異概率

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

本文采用自適應(yīng)變異概率。對(duì)于高于群體平均適應(yīng)度的個(gè)體，采用較低的Pm，而對(duì)于低于群體平均適應(yīng)度的個(gè)體，采用較高的Pm。使用公式（1）。

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

1.3 雙種群遺傳算法

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

通過這種操作，在逐漸單一的種群中注入了新的個(gè)體，而且這些新注入的個(gè)體是已經(jīng)經(jīng)過一定進(jìn)化選擇得到的優(yōu)秀個(gè)體交叉產(chǎn)生的，從而使新的種群更有效地向最優(yōu)解收斂。

2 計(jì)算機(jī)仿真和結(jié)果分析

為了考察本文所述的3種改進(jìn)遺傳算法的性能，選取了一個(gè)實(shí)例進(jìn)行數(shù)值模擬。所選實(shí)例為：

該函數(shù)是一個(gè)一元多峰函數(shù)，在[-1,2]上存在多個(gè)極大值點(diǎn)，它在該范圍內(nèi)的圖形如圖1所示。

圖1 實(shí)例函數(shù)在[-1,2]范圍上的圖形

我們把3種改進(jìn)遺傳算法和傳統(tǒng)遺傳算法，各自運(yùn)行10次，每次運(yùn)行得到的函數(shù)值及其對(duì)應(yīng)的變量值被記錄下來，如表1所示。

表1 應(yīng)用3種改進(jìn)遺傳算法和傳統(tǒng)遺傳算法得到的計(jì)算結(jié)果（10次運(yùn)行的平均值）

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

3 結(jié)論

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

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

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

[3] 張頂學(xué)，關(guān)治洪，劉新芝.基于捕食搜索策略的遺傳算法研究[J].計(jì)算機(jī)應(yīng)用研究，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] 黃美發(fā)，景暉，鐘艷茹等，基于擬隨機(jī)序列的三維模型表面采樣方法[J].計(jì)算機(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序列的去隨機(jī)化[D].烏魯木齊：新疆大學(xué),2008.

[8] 王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.