蔣昀昕

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

1.引言

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

2.罰函數(shù)法

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

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

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

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

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

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

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

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

(3)選擇運算。對群體P(t)進行比例選擇運算，得到P1(t)。

(4)交叉運算。對選擇出的個體集合P1(t)作單點交叉運算，得到 P2(t)。

(5)變異運算。對P2(t)作均勻變異運算，得到P3(t)。

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

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

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

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

4.算法實現(xiàn)

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

4.1 編碼運算

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

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

4.2 解碼運算

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

4.3 選擇運算

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

4.4 交叉運算

本文采用單點交叉的方法來實現(xiàn)交叉算子，具體代碼過程如下：

4.5 變異運算

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

4.6 小生境淘汰運算

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

4.7 降序排序運算

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

5.數(shù)值實驗

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

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

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

圖1 全部18個全局最小點示意圖

6.結(jié)論

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

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

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