姚志敏

(廣東培正學(xué)院 計(jì)算機(jī)科學(xué)與工程系，廣州 510830)

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

從遺傳算法產(chǎn)生新個(gè)體的能力來(lái)看，交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法，它決定了算法的全局搜索能力，而變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，但它決定了遺傳算法尋找新的搜索方向能力，應(yīng)當(dāng)是解決遺傳算法早熟收斂重點(diǎn)研究對(duì)象。

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

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

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

1 BDGA 算法描述［2］

通過定義等位異值變異算子進(jìn)行有向?qū)У淖儺愑?jì)算，將每一位基因值的差異性在不同代遺傳中加以保留，其實(shí)質(zhì)是對(duì)某代遺傳群體，若某同位基因值全部相同，則主動(dòng)強(qiáng)制變異使其產(chǎn)生修正，以避免在進(jìn)化中，有某位基因值缺少差異而導(dǎo)致不能繼續(xù)進(jìn)化，從而較好的解決GA 早熟問題。

1.1 編碼方式

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

1.2 概念定義

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

定義1 等位同值群體。

定義2 等位異值群體。

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

定義3 簡(jiǎn)單群體［1－3］。

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

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

定義4 等位異值變異。

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

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

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

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

1.3 BDGA 算法設(shè)計(jì)［4－5］

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

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

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

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

(1)將m 個(gè)長(zhǎng)度為L(zhǎng) 的二進(jìn)制串按照個(gè)體適應(yīng)度值由大到小進(jìn)行排序;

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

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

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

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

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

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

步驟3——結(jié)果輸出:輸出第k 代種群。

2 實(shí)證分析［6 －7］

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

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

1)多個(gè)極值點(diǎn)、等距、等高f1。

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

圖1 f1 曲線

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

表1 BDGA 算法計(jì)算參數(shù)及結(jié)果

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

圖2 各代適應(yīng)度均值的變化曲線

由于篇幅有限，在此選取第7 次計(jì)算結(jié)果文件部分內(nèi)容顯示如圖3 所示。

圖3 第7 次計(jì)算結(jié)果文件片段

2)多個(gè)極大值點(diǎn)，等距、非等高f2。

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

圖4 f2 曲線

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

表2 BDGA 算法計(jì)算參數(shù)及結(jié)果

3)多個(gè)極大值點(diǎn)，等高，非等距f3。

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

圖5 f3 曲線

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

4)多個(gè)極大值點(diǎn)，非等高，非等距f4

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

表3 BDGA 算法計(jì)算參數(shù)及結(jié)果

圖6 f4 曲線

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

表4 BDGA 算法計(jì)算參數(shù)及結(jié)果

3 結(jié)語(yǔ)

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

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

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

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

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

［2］李敏強(qiáng)，寇紀(jì)淞，林丹，等.遺傳算法的基本理論與應(yīng)用［M］.北京:科學(xué)出版社，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)化中的應(yīng)用［J］. 廣西工學(xué)院學(xué)報(bào)，2013，24(2):25－31.

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

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