基于罰函數(shù)的小生境遺傳算法在MATLAB中的實(shí)現(xiàn)

蔣昀昕

(福建衛(wèi)生職業(yè)技術(shù)學(xué)院公共基礎(chǔ)部，福建 福州 350101)

1.引言

生物學(xué)上，小生境(niche)是指在特定環(huán)境中一種組織(organism)的功能，把有共同特性的組織稱作物種(species)。小生境技術(shù)就是將每一代個(gè)體劃分為若干類，每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)群，再在種群中以及不同種群中之間雜交、變異產(chǎn)生新一代個(gè)體群。同時(shí)采用預(yù)選擇機(jī)制和排擠機(jī)制或分享機(jī)制完成任務(wù)?；谶@種小生境的遺傳算法 (Niching Genetic Algorithms，NGAs)，可以更好地保持解的多樣性，同時(shí)具有很高的全局尋優(yōu)能力和收斂速度，特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問(wèn)題。常見(jiàn)的小生境遺傳算法主要有適應(yīng)值共享遺傳算法、擁擠遺傳算法、隔離小生境遺傳算法等。在小生境遺傳算法中，為了使個(gè)體能夠在整個(gè)約束空間分散開(kāi)來(lái)，更好地維護(hù)種群的多樣性，有學(xué)者提出在傳統(tǒng)的小生境遺傳算法中引入罰函數(shù)的思想。本文從編程角度出發(fā)，詳細(xì)闡述如何使用MATLAB語(yǔ)言實(shí)現(xiàn)該算法并給出數(shù)值實(shí)驗(yàn)測(cè)試。

2.罰函數(shù)法

實(shí)際應(yīng)用中的優(yōu)化問(wèn)題一般都含有一定的約束條件，它們的描述形式多種多樣[1]。在構(gòu)造遺傳算法時(shí)，罰函數(shù)法是處理約束條件的常用方法之一。

這種處理方法的基本思想是：對(duì)在解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體，計(jì)算其適應(yīng)度時(shí)，處以一個(gè)罰函數(shù)，從而降低該個(gè)體的適應(yīng)度，使該個(gè)體被遺傳到下一代群體中的機(jī)會(huì)減少。即用下式來(lái)對(duì)個(gè)體的適應(yīng)度進(jìn)行調(diào)整：

式中，F(xiàn)(X)為原適應(yīng)度，f(x)為考慮了罰函數(shù)后的新適應(yīng)度，G(X)為罰函數(shù)。

在確定合理的罰函數(shù)時(shí)既要考慮到度量解對(duì)約束條件不滿足的程度，又要考慮遺傳算法在計(jì)算效率上的要求。如果罰函數(shù)的強(qiáng)度太小，部分個(gè)體仍有可能破壞約束條件，所以保證不了遺傳運(yùn)算所得到的個(gè)體一定是滿足約束條件的一個(gè)可行解；反之，如果罰函數(shù)的強(qiáng)度太大，又有可能使個(gè)體的適應(yīng)度差異不大，降低了個(gè)體之間的競(jìng)爭(zhēng)力，從而影響遺傳算法的運(yùn)行效率。

3.基于罰函數(shù)的小生境遺傳算法思想

在小生境遺傳算法中引入罰函數(shù)的目的是為了使個(gè)體能夠在整個(gè)約束空間分散開(kāi)來(lái)，更好地維護(hù)種群的多樣性。該算法的思想是：首先兩兩比較群體中各個(gè)個(gè)體之間的距離，若這個(gè)距離在預(yù)先指定的距離L之內(nèi)的話，再比較兩者之間的適應(yīng)度大小，并對(duì)其中適應(yīng)度較低的個(gè)體施加一個(gè)較強(qiáng)的罰函數(shù)，極大地降低其適應(yīng)度。這樣，對(duì)于在預(yù)先指定的某一個(gè)距離L之內(nèi)的兩個(gè)個(gè)體，其中較差的個(gè)體經(jīng)處理后其適應(yīng)度變得更差，它在后面的進(jìn)化過(guò)程中被淘汰掉的概率就極大。也就是說(shuō)，在距離L之內(nèi)將只存在一個(gè)優(yōu)良的個(gè)體，從而維護(hù)了群體的多樣性，又使得各個(gè)個(gè)體之間保持一定的距離，并使得個(gè)體能夠在整個(gè)約束空間分散開(kāi)來(lái)。算法的步驟可描述如下：

(1)設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=1；隨即生成M個(gè)初始個(gè)體組成初始群體P(t)，并求出各個(gè)個(gè)體的適應(yīng)度Fi（i=1,2,…，M）。

(2)依據(jù)各個(gè)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排序，記憶前N個(gè)個(gè)體（N

(3)選擇運(yùn)算。對(duì)群體P(t)進(jìn)行比例選擇運(yùn)算，得到P1(t)。

(4)交叉運(yùn)算。對(duì)選擇出的個(gè)體集合P1(t)作單點(diǎn)交叉運(yùn)算，得到 P2(t)。

(5)變異運(yùn)算。對(duì)P2(t)作均勻變異運(yùn)算，得到P3(t)。

(6)小生境淘汰運(yùn)算。將第(5)步得到的M個(gè)個(gè)體和第(2)步所記憶的N個(gè)個(gè)體合并在一起，得到一個(gè)含有M+N個(gè)個(gè)體的新群體；對(duì)這M+N個(gè)個(gè)體，按照下式求出每?jī)蓚€(gè)個(gè)體Xi和Xj之間的海明距離：

當(dāng)時(shí)‖Xi-Xj‖＜L，比較個(gè)體個(gè)體Xi和Xj之間的適應(yīng)度大小，并對(duì)其中適應(yīng)度較低的個(gè)體處以罰函數(shù)：

(7)依據(jù)這M+N個(gè)個(gè)體的新適應(yīng)度對(duì)各個(gè)個(gè)體進(jìn)行降序排序，記憶前N個(gè)個(gè)體。

(8)終止條件判斷。若不滿足終止條件，則更新進(jìn)化代數(shù)計(jì)數(shù)器t=t+1，并將第(7)步排序中的前M個(gè)個(gè)體作為新的下一代群體P(t)，然后轉(zhuǎn)到第(3)步；若滿足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束。

4.算法實(shí)現(xiàn)

MATLAB是Matwork公司的產(chǎn)品，是一個(gè)功能強(qiáng)大的數(shù)學(xué)軟件，其優(yōu)秀的數(shù)值計(jì)算能力使其在工業(yè)界和學(xué)術(shù)界的使用率都非常高。MATLAB還十分便于使用，它以直觀、簡(jiǎn)潔并符合人們思維習(xí)慣的代碼給用戶提供了一個(gè)非常友好的開(kāi)發(fā)環(huán)境[2]。本算法的程序是在MATLAB環(huán)境下編寫(xiě)完成的，具體代碼如下：

4.1 編碼運(yùn)算

本文中的編碼方案采用的是最常用的二進(jìn)制編碼，即用二進(jìn)制數(shù)構(gòu)成的符號(hào)串來(lái)表示一個(gè)個(gè)體。使用randint函數(shù)實(shí)現(xiàn)編碼并產(chǎn)生初始群體：

在上述代碼中，PS是種群個(gè)數(shù)，GL是個(gè)體編碼長(zhǎng)度，VN是決策變量的個(gè)數(shù)。此代碼的含義是隨機(jī)產(chǎn)生一個(gè)種群大小為PS的初始化群體initpop，且每個(gè)個(gè)體的二進(jìn)制編碼長(zhǎng)度為GL*VN+VN+2。

4.2 解碼運(yùn)算

初始化的種群initpop必須通過(guò)解碼才能計(jì)算函數(shù)值與適應(yīng)度。代碼過(guò)程如下：

4.3 選擇運(yùn)算

選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。選擇操作的主要目的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。本文中的選擇算子是最常用的比例選擇算子。代碼過(guò)程如下：

4.4 交叉運(yùn)算

本文采用單點(diǎn)交叉的方法來(lái)實(shí)現(xiàn)交叉算子，具體代碼過(guò)程如下：

4.5 變異運(yùn)算

本文采用均勻變異的方法來(lái)實(shí)現(xiàn)變異算子，具體代碼過(guò)程如下：

4.6 小生境淘汰運(yùn)算

在小生境淘汰運(yùn)算中，正確地選擇罰函數(shù)是關(guān)鍵。具體代碼過(guò)程如下：

4.7 降序排序運(yùn)算

利用MATLAB中的Sort()函數(shù)對(duì)種群進(jìn)行排序，具體代碼如下：

5.數(shù)值實(shí)驗(yàn)

以Shubert函數(shù)為測(cè)試函數(shù)，測(cè)試參數(shù)為種群規(guī)模200，個(gè)體編碼長(zhǎng)度20，交叉概率0.9，變異概率0.01，罰函數(shù)Penalty=1.0e-030。

此函數(shù)共有760個(gè)局部極小點(diǎn)，其中18個(gè)為全局最小點(diǎn)，最小值為-186.7309。

圖1給出某一次計(jì)算出的18個(gè)全局最小點(diǎn)的具體數(shù)值，其中第1、2列為橫、縱坐標(biāo)，第3列為目標(biāo)函數(shù)值，第4列為適應(yīng)度。這個(gè)結(jié)果的精確度不僅超過(guò)了所有公開(kāi)報(bào)道的計(jì)算結(jié)果，而且比以往我們計(jì)算的結(jié)果更好。

圖1 全部18個(gè)全局最小點(diǎn)示意圖

6.結(jié)論

本文介紹了基于罰函數(shù)的小生境遺傳算法，給出了用MATLAB編寫(xiě)的完整代碼，并通過(guò)MTALAB測(cè)試。數(shù)值實(shí)驗(yàn)結(jié)果表明隨著進(jìn)化代數(shù)的增加，基于罰函數(shù)的小生境遺傳算法具有較好的多峰搜索能力。

[1]周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，1999.

[2]張宜華.精通MATLAB5[M].北京：清華大學(xué)出版社，1999.