基于罰函數的小生境遺傳算法在MATLAB中的實現

蔣昀昕

(福建衛生職業技術學院公共基礎部，福建 福州 350101)

1.引言

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

2.罰函數法

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

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

式中，F(X)為原適應度，f(x)為考慮了罰函數后的新適應度，G(X)為罰函數。

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

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

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

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

(2)依據各個個體的適應度對其進行降序排序，記憶前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之間的適應度大小，并對其中適應度較低的個體處以罰函數：

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

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

4.算法實現

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

4.1 編碼運算

本文中的編碼方案采用的是最常用的二進制編碼，即用二進制數構成的符號串來表示一個個體。使用randint函數實現編碼并產生初始群體：

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

4.2 解碼運算

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

4.3 選擇運算

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

4.4 交叉運算

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

4.5 變異運算

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

4.6 小生境淘汰運算

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

4.7 降序排序運算

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

5.數值實驗

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

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

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

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

6.結論

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

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

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