姚志敏

(廣東培正學院 計算機科學與工程系，廣州 510830)

遺傳算法是解決多峰優(yōu)化和多模態(tài)問題的重要工具，使用遺傳算法解決優(yōu)化問題既存在一定的不確定性，又具有一定的穩(wěn)定性［1］。但不足的是遺傳算法在多峰值函數(shù)優(yōu)化求解過程中往往出現(xiàn)早熟收斂，使群體過早的失去多樣性，收斂于局部最優(yōu)點。曾經出現(xiàn)過許多的改進方法，包括對群體的分類和參數(shù)設計，對選擇算子、交叉算子和變異算子的改進，試圖避免搜索方向收斂于局部最優(yōu)點，偏離全局最優(yōu)解的問題。

從遺傳算法產生新個體的能力來看，交叉運算是產生新個體的主要方法，它決定了算法的全局搜索能力，而變異運算是產生新個體的輔助方法，但它決定了遺傳算法尋找新的搜索方向能力，應當是解決遺傳算法早熟收斂重點研究對象。

筆者在遺傳算法研究中發(fā)現(xiàn)，在種群進化的某一代中，種群中所有位串的某一個等位基因產生相同值，是產生早熟收斂的重要原因。如群體 S:(1001111010101010，1010101001010011，0001010011101010，1010111010111001，… ，0010101010111001)中，第二列值全為0。任何交換算子都是等位交換基因值，群體中任意選擇兩個個體交換計算后，產生的兩個新個體第二列的值依然會保持為0。把具有這種性質的種群稱為等位同值群體，在進化中由于模板原理的作用很容易產生等位同值群體，這是造成遺傳算法早熟收斂的重要原因。

變異算子可以改變等位同值群體為等位異值群體，由于變異算子并不針對位串的某一位，變異概率pm取值很小，進化中要經過很多代才能確保某位的值發(fā)生變異，如上述群體中有位串第二位的值發(fā)生變異。若pm取值大，則會破壞已形成的模板規(guī)則，使算法不能穩(wěn)定收斂到結果。

基于以上分析，在算法中注意改變等位同值群體為等位異值群體，是避免遺傳算法早熟收斂有效方法。

1 BDGA 算法描述［2］

通過定義等位異值變異算子進行有向導的變異計算，將每一位基因值的差異性在不同代遺傳中加以保留，其實質是對某代遺傳群體，若某同位基因值全部相同，則主動強制變異使其產生修正，以避免在進化中，有某位基因值缺少差異而導致不能繼續(xù)進化，從而較好的解決GA 早熟問題。

1.1 編碼方式

由于二進制編碼方式編碼、解碼操作簡單，而且交叉、變異操作便于實現(xiàn)，故采用二進制編碼方式。

1.2 概念定義

令Xn(n 為串的長度)為樣板空間，S 表示進化群體，= 1，2，…，L，L，M 為正整數(shù)，L ≤2n且M ≤L;，其中

定義1 等位同值群體。

定義2 等位異值群體。

若群體S 不是等位同值群體，則稱S 為等位異值群體。

定義3 簡單群體［1－3］。

在每一代群體中，每個個體之間的位串結構互不相同。數(shù)學描述如下:

遺傳算法中的變異算子主要是在保持了群體多樣性的基礎之上，提高算法的局部搜索能力，但是簡單遺傳算法中提到的變異操作都是基于變異概率，針對單個個體的突變，這樣雖然可以產生新的個體，維持種群的多樣性，但是這種操作方式并沒有從整個種群(即所有個體)的角度來進行突變，進而維持種群的多樣性，基于此，提出等位異值變異算子。

定義4 等位異值變異。

在進化的任一代中，若群體S 是等位同值群體，k 為同值位，進行如下變異操作:以概率pm選擇S中的串，使群體S 變成等位異值群體，稱此變異為等位異值變異。

下面舉例說明，假定群體S1 規(guī)模為M=5;串長n =15，并進一步假定在第t 代，群體由下面的串組成。

從上面可以看出:位串在4 號基因位上的值都為1，故S1 為等位同值群體，4 是同值位。在這一代中，交叉算子的作用并不能夠使得4 號基因位的值產生變化，按照通常的變異操作，位串在基因位4 產生變異的概率很小，進化中S1 往往保持等位同值群體的性質，使進化陷入了局部最優(yōu)解而過早的收斂。

為了能夠使進化過程突破局部搜索，避免算法的提前收斂，按照給定的變異概率強制其中的某個位串，如X3在同值位4 上發(fā)生突變(1 變0)，使S1 成為等位異值群體。這樣的變異操作其實是從列的角度進行的變異操作，而通常的變異操作是從行的角度來考慮的。

1.3 BDGA 算法設計［4－5］

下文中提到的變量說明如下。

種群數(shù)量:m;迭代次數(shù):k;交叉概率:pc;變異概率:pm;自變量個數(shù):n ;第i 變量編碼長度:;第i 變量上下界:;種群中個體串長度L

步驟1——初始化:讀取種群的參數(shù)信息(m，k，pc，pm，n，li，ai，bi)，初始化種群S，使種群以上述參數(shù)提供的信息隨機產生一系列二進制串。記S(其中:“xijk”代表0 或者

步驟2——迭代演化:在滿足迭代條件下(即迭代次數(shù)≤k)，重復執(zhí)行(1)～(6)。

(1)將m 個長度為L 的二進制串按照個體適應度值由大到小進行排序;

(2)檢查新群體是否符合簡單群體，若不符合，對種群進行簡單化處理，使得種群為簡單群體;

(3)查S 是否為等位異值群體，若不是，即對S 中的串Xi=存在某一位xijk或幾位，有或者m;那么以概率pm(pm可以取0.1 ～0.2)選擇S 中的串xij，使得:

這樣生成新串，使群體為等位異值群體;

(4)以交叉概率pc(實際操作中可取pc=0.8)執(zhí)行交叉操作;將S 中的m 個串隨機組成對，采用一點交叉法，隨機選擇交叉位，對其中的× pc對進行交叉操作;

(5)根據精英保留策略執(zhí)行選擇操作;

(6)返回到(1)繼續(xù)執(zhí)行，直到滿足最大迭代次數(shù)k。

步驟3——結果輸出:輸出第k 代種群。

2 實證分析［6 －7］

結合簡單群體策略和精英保留算法，對多峰連續(xù)函數(shù)優(yōu)化問題進行了大量實證研究(實證計算所選4 個函數(shù)是經典的GA 測試函數(shù)［2］)，獲得了很好的結果，對遺傳算法的應用具有重要參考價值。

一維(多峰)函數(shù)

1)多個極值點、等距、等高f1。

該函數(shù)圖像如圖1 所示。

圖1 f1 曲線

表1 給出了BDGA 算法對于此函數(shù)的計算參數(shù)及其結果。

表1 BDGA 算法計算參數(shù)及結果

圖2 顯示了第4 ～7 次計算過程中適應度均值變化情況，從圖中可以看出，該算法的收斂效率非常高。

圖2 各代適應度均值的變化曲線

由于篇幅有限，在此選取第7 次計算結果文件部分內容顯示如圖3 所示。

圖3 第7 次計算結果文件片段

2)多個極大值點，等距、非等高f2。

函數(shù)曲線如圖4 所示。

圖4 f2 曲線

表2 給出了BDGA 算法對于此函數(shù)的計算參數(shù)及其結果。

表2 BDGA 算法計算參數(shù)及結果

3)多個極大值點，等高，非等距f3。

此函數(shù)曲線如圖5 所示。

圖5 f3 曲線

表3 給出了BDGA 算法對于此函數(shù)的計算參數(shù)及其結果。

4)多個極大值點，非等高，非等距f4

此函數(shù)曲線如圖6 所示。

表3 BDGA 算法計算參數(shù)及結果

圖6 f4 曲線

表4 給出了BDGA 算法對于此函數(shù)的計算參數(shù)及其結果。

表4 BDGA 算法計算參數(shù)及結果

3 結語

研究遺傳算法的遺傳算子具體操作及其對多峰連續(xù)性函數(shù)的優(yōu)化求解，提出了等位同值群體和等位異值變異的概念，將每一位基因值的差異性在不同代遺傳中加以保留，其實質是對位串編碼的一種修正過程，目的是避免在進化中，有群體缺少差異而導致不能繼續(xù)進化。

運用等位異值變異遺傳算法求一維多峰函數(shù)優(yōu)化問題，數(shù)值試驗表明改進算法在求解這些問題中的高效與穩(wěn)定性。對于不同特性的復雜一維測試函數(shù)容易局部收斂問題，該算法能夠很好的突破局部收斂，從而獲得更好的解。

總之，該算法很好的防止了早熟收斂，顯示了良好的優(yōu)化性能，表明此改進算法是有效的，該思想對遺傳算法的進一步研究顯然有重要參考價值。

作為一種高效并行的全局搜索方法，遺傳算法雖有不足，但仍以其特有的算法特點使其在許多實際問題中越來越廣泛被應用，隨計算機速度的不斷增強，遺傳算法的研究進展將變得更大、更快。

［1］岳嵚，馮珊.遺傳算法的計算性能的統(tǒng)計分析［J］.計算機學報，2010，32(12):2389－2392.

［2］李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用［M］.北京:科學出版社，2002:179－206.

［3］Minqiang Li，Jisong Kou.Crowding with nearest neighbors replacement for multiple species niching and building blocks preservation in binary multimodal functions optimization［J］.Journal of Heuristics ，2008，14(3):243－270.

［4］Nedim Tutkun.Optimization of multimodal continuous functions using a new crossover for the real－coded genetic algorithms［J］.Expert Systems with Applications，2009(36):8172－8177.

［5］覃柏英. 非線性規(guī)劃的遺傳算法在多峰函數(shù)優(yōu)化中的應用［J］. 廣西工學院學報，2013，24(2):25－31.

［6］王利琴，董永峰，顧軍華. 改進的精英遺傳算法及其在特征選擇中的應用［J］. 計算機工程與設計，2014，35(5):1792－1796.

［7］趙婕. 基于VB 的遺傳算法在多峰函數(shù)全局優(yōu)化中的應用［J］. 太原大學學報，2014，15(1):128－131.