核模糊聚類劃分子種群的雙種群遺傳算法

孫雨萌，柏麗娜，張旭秀

(大連交通大學 電氣信息工程學院，遼寧 大連 116028)

0 引 言

傳統(tǒng)單種群遺傳算法[1]在其尋優(yōu)進化過程中易出現(xiàn)個體多樣性下降過快，在進行種間交配時，易出現(xiàn)高適應度種群交配池，造成種群中部分基因信息丟失，產(chǎn)生遺傳算法早熟現(xiàn)象。2005年Martikainen等[2]將單一機制的種群進化過程演變成雙種群并行進化，選取合適時機進行種間交流。雙種群遺傳算法正不斷應用于工程實踐中，例如：時間軌跡優(yōu)化[3]、配電網(wǎng)參數(shù)辨識[4]、作業(yè)車間調(diào)度[5]和控制器參數(shù)優(yōu)化[6]等。

標準雙種群遺傳算法在其進化初期采用隨機分配的方式對子種群進行劃分，變異后以遷移的方式進行種間交流，但其在進化后期仍存在雙種群種間同質(zhì)化的嚴重缺陷，造成雙種群陷入相同的局部最優(yōu)解。文獻[7-9]引入蜂群繁殖結構，在迭代過程中以不斷引進新種群的方式來構造雙種群，并進行種內(nèi)斗爭獲取最優(yōu)個體作為蜂王與其他個體進行交配，采用個體融合的方式進行種間交流；文獻[10-12]引入小種群探測結構，即依據(jù)迭代經(jīng)驗，在進化達到一定程度時，取適應度值最高的個體集合，隨機對其進行劃分成i個并行遺傳的小種群，以進化所得最優(yōu)解替換原集合的方式進行種間交流；文獻[13-14]引入戰(zhàn)爭淘汰結構，采用初始單種群取反的方式構造雙種群，迭代過程中以個體斗爭淘汰的方式進行種間交流。

蜂群繁殖結構屬于嵌套循環(huán)結構，小種群探測結構屬于經(jīng)驗劃分，戰(zhàn)爭淘汰結構需在個體轉化為二進制條件下進行，因此，算法計算過程較為復雜，且嚴格限制了缺乏經(jīng)驗的工程人員的應用。吸取上述雙種群遺傳算法改進思路，為解決種群同質(zhì)化的嚴重缺陷，同時加快迭代進化所需時間，本研究給出一種核模糊聚類劃分子種群的雙種群遺傳算法(KFC-2PMGA)，使子種群劃分不再是一種隨機行為，而是以個體適應度值為依據(jù)，利用核模糊聚類算法將滿足不同約束條件的個體劃分到子種群中，并對個體中基因位分別采取改進的自適應交叉及變異策略，使得改進后的雙種群遺傳算法更易保留基因多樣性，同時具備局部及全局搜索能力。

1 標準雙種群遺傳算法

標準雙種群遺傳算法[2]在單種群遺傳算法的基礎上，對初始群體進行隨機劃分，得到個體數(shù)目相等的兩個子種群，分別按照不同的交叉及變異概率進行遺傳操作。其中子種群1交叉及變異概率均較小，稱為開發(fā)種群，用于發(fā)掘個體中局部最優(yōu)值，提高收斂速度；子種群2交叉及變異概率均較大，稱為探測種群，用于擴大搜索面積，提供新的可行解，克服過早收斂。在進化過程中，兩個子種群均獨立進化，并引入遷移算子進行種群間基因交換，算法具體步驟為：

步驟1初始化染色體個數(shù)2N個，隨機劃分雙種群，確定交叉概率Pc1、Pc2及變異概率Pm1、Pm2；

步驟2計算群體中染色體適應度值；

步驟3判斷適應度值是否滿足收斂條件，若滿足收斂條件則輸出其全局最優(yōu)解，若未滿足則轉步驟4；

步驟4并行子種群按照交叉概率Pc1、Pc2進行交叉操作；

步驟5并行子種群按照交叉概率Pm1、Pm2進行變異操作；

步驟6進行中間遷移，產(chǎn)生新一代種群，轉步驟2。

2 基于核模糊聚類算法的雙種群遺傳算法

2.1 雙種群劃分方式的改進

傳統(tǒng)雙種群遺傳算法在進行種群間劃分時，往往將初始種群隨機分割為兩個子種群，雖在一定程度上對傳統(tǒng)單種群遺傳算法做出優(yōu)化，但未能避免迭代后期出現(xiàn)子種群同化的現(xiàn)象[15]。

核模糊聚類算法(KFCM)以模糊聚類算法(FCM)為主要依據(jù)，利用核函數(shù)替換傳統(tǒng)FCM算法中歐的距離，使聚類效果更加完善[16-17]。將核模糊函數(shù)引入遺傳算法子種群劃分中，將個體適應度值作為聚類劃分的約束條件，取{xi，i=1，2，…，n}表示種群內(nèi)個體適應度值集合，m為預設聚類子種群數(shù)目，{vj，j=1，2，…，m}為子種群聚類中心，φ為非線性映射函數(shù)，φ(x)為高維空間中x的原象，則向量的歐氏距離定義為

K(vj，vj)

(1)

其中K(x，v)=φ(x)Tφ(v)為核函數(shù)向量內(nèi)積，結合高斯核函數(shù)，可得式(2)，K(x，x)=1。

(2)

取zij函數(shù)表示第i個樣本點隸屬于第j個聚類程度，取c為模糊加權指數(shù)，決定本次聚類效果的模糊程度。c取值為常量，則KFCM目標函數(shù)定義為

(3)

將高斯核函數(shù)引入目標函數(shù)可得

(4)

(5)

更新后新種群聚類中心為

(6)

根據(jù)推導公式，利用核模糊C均值算法聚類劃分雙種群步驟為

步驟1設定參數(shù)n，m，c初始值，初始化聚類中心vj，初始隸屬度函數(shù)zji，使其滿足規(guī)定約束條件；

步驟2計算核矩陣K(x，y)；

步驟3利用式(5)更新后的隸屬度函數(shù)；

步驟4利用式(6)計算該隸屬度函數(shù)下的聚類中心；

步驟5利用式(3)計算KFCM目標函數(shù)，如果目標函數(shù)數(shù)值變化小于某一設定閾值，則算法停止，輸出聚類劃分后雙種群，適應度值較高的種群稱為精英種群，適應度值較低的種群稱為平民種群，否則跳轉至步驟2。

2.2 自適應基因位交叉策略

聚類劃分所得雙種群在進行種群內(nèi)部交叉時，基于單點交叉方式，應用一種簡單的單點橫向交叉方式[18]，交叉概率依據(jù)種內(nèi)個體基因相似度采取一種動態(tài)自適應的交叉算子。

為提高種群的局部搜索能力，在進行種內(nèi)交叉時，精英種群交叉概率與種內(nèi)個體相似性正相關，提高精英種群搜索最優(yōu)解的效率。平民種群交叉概率與種內(nèi)個體相似性負相關，擴大搜索范圍，以便尋求新的搜索空間，有關基因相似性的求解參考文獻[19]。

2.3 自適應多位變異策略

為確保種群內(nèi)樣本個體的多樣性，遺傳算法引入變異操作，將交叉后的部分個體基因進行按位取反。針對交叉操作所得的雙種群，采用一種改進的自適應多位變異算子。對于精英種群，在算法早期極少的基因位發(fā)生變異，充分發(fā)揮相似個體間高交叉概率的性質(zhì)，進行空間搜索，在算法迭代到一定次數(shù)，交叉作用不顯著時，增大變異位數(shù)，防止算法過早陷入局部最優(yōu)解。對于平民種群，算法早期引入大變異算子，增加樣本的多樣性，當算法趨于穩(wěn)定，減小變異位數(shù)，保留部分當前代數(shù)平民種群中產(chǎn)生的高適應度基因。在逐次迭代過程中，可依據(jù)新的核模糊聚類中心，進行精英種群與平民種群間的基因流動。同時依據(jù)個體的適應度情況決定變異位數(shù)，適應度值與變異位數(shù)呈反比，減少對優(yōu)秀基因的破壞。改進的自適應變異位數(shù)如式(8)所示，

(8)

其中bit1表示精英種群變異位數(shù)，bit2表示平民種群變異位數(shù)，Sn表示最終穩(wěn)定的變異位數(shù)，Sc表示交叉效果不顯著時的迭代次數(shù)，t表示當前迭代次數(shù)，f表示當前個體適應度情況，fmin與fmax分別表示適應度最小與最大值。

2.4 改進雙種群遺傳算法流程

基于核模糊聚類劃分子種群的動態(tài)自適應雙種群遺傳算(KFC-2PMGA)具體迭代步驟為

步驟1初始化種群規(guī)模P，子種群個數(shù)K，核模糊C均值聚類算法各初始參數(shù)，終止迭代次數(shù)T。

步驟2計算種群中所有個體適應度值。

步驟3求取滿足條件的KFCM目標函數(shù)，進行種群內(nèi)部所有個體核模糊聚類分析，劃分雙種群。

步驟4依據(jù)其個基因間相似度進行自適應交叉操作。

步驟5依據(jù)自適應多位變異算子進行自適應變異操作。

步驟6未收斂或未達到迭代次數(shù)，將雙種群進行合并，轉步驟2，否則轉步驟7；

步驟7輸出最優(yōu)個體作為最優(yōu)解，進化過程結束。

3 實驗仿真及結果分析

3.1 測試函數(shù)及參數(shù)設置

為驗證所改進雙種群遺傳算法的可行性與有效性，分別選擇一元單峰、多峰測試函數(shù)及二元單峰、多峰測試函數(shù)進行仿真驗證，并對比標準雙種群遺傳算法[2](2PMGA)及自適應雙種群遺傳算法[20](A-2PMGA)，測試函數(shù)見表1。

表1 測試函數(shù)Tab.1 The test function

實驗算法中群體規(guī)模設置為200，維數(shù)設置為30維，函數(shù)f1、f4、f6最大迭代次數(shù)為200代，函數(shù)f5、f7最大迭代次數(shù)為100代，函數(shù)f2最大迭代次數(shù)為1 000代，函數(shù)f3最大迭代次數(shù)為400代。參數(shù)設置為：標準雙種群遺傳算法中，Pc1=0.1、Pc2=0.9、Pm1=0.01、Pm2=0.6。

3.2 仿真結果分析

對每種算法獨立運行100次，并對100次的運行結果進行統(tǒng)計，仿真結果見表2、圖1～7。

表1中，函數(shù)f1～f3為一元測試函數(shù)，其中Sphere函數(shù)為一元單峰函數(shù)，函數(shù)結構較為單一；Ackley函數(shù)為一元多峰函數(shù)，該測試函數(shù)存在大量的由余弦調(diào)制波構成的多峰或多孔，曲面起伏不平，函數(shù)搜索十分復雜，易落入局部最優(yōu)陷阱；Girewank函數(shù)為一元多峰函數(shù)，各變量之間影響嚴重、顯著相關。依據(jù)表2中f1、f2數(shù)據(jù)可得，3種優(yōu)化算法雖均未尋到其全局最優(yōu)解，但改進算法KFC-2PMGA平均收斂代數(shù)遠小于其余2種算法，且平均收斂值精度較高，依據(jù)圖1～2可得，KFC-2PMGA算法具有更快的搜索速度。依據(jù)表2f3可得，KFC-2PMGA在迭代過程中可跳出局部最優(yōu)點，搜索到全局最小值。

函數(shù)f4～f7為二元測試函數(shù)，其中Bohachevsky 函數(shù)為二元單峰函數(shù)，各變量之間相互獨立；Holder Table函數(shù)全局最優(yōu)解周圍存在很多局部極值點，因此難以找到全局最優(yōu)；Drop-Ware函數(shù)具有多模態(tài)，函數(shù)結構高度復雜；Shuber函數(shù)各變量之間的相關性較強，且存在誤導算法方向的梯度信息，全局共存在760個局部極值點。依據(jù)表2f4～f7數(shù)據(jù)可得，2PMGA在其收斂時產(chǎn)生“早熟”現(xiàn)象，A-2PMGA及KFC-2PMGA算法在求解多峰問題時有更好的收斂精度，KFC-2PMGA算法收斂精度最高；依據(jù)圖4～7可得，KFC-2PMGA算法具有較快的收斂速度。

表2 函數(shù)f的運行仿真結果Tab.2 Simulation result of function f

綜上可得核模糊聚類子種群的劃分方式降低了種群間同化的可能性，依據(jù)個體間相似度進行自適應交叉操作增加了算法的收斂速度，引入多基因位自適應變異算子使得種群內(nèi)個體多樣性得以提高，改進算法中后期性能。

(a) 函數(shù)Sphere三維圖

(a) 函數(shù)Ackley三維圖

(a) 函數(shù)Griewank三維圖

(a) 函數(shù)Bohachevsky三維圖

(a) 函數(shù)Holder三維圖

(a) 函數(shù)Drop-Wave三維圖

(a) 函數(shù)Shubert三維圖

4 結 論

提出了一種核模糊聚類劃分子種群的雙種群遺傳算法，將其個體適應度值設定為核模糊聚類算法的輸入，依據(jù)KFCM目標函數(shù)將初始種群進行劃分，分為精英種群與平民種群，子種群內(nèi)依據(jù)個體相似度進行自適應交叉操作，引入多基因位變異算子，擴大種群搜索范圍，將變異操作后子種群進行種間合并，重復上步驟，實現(xiàn)子種群間精英與平民個體的相互流動，將雙種群遺傳算法本身的并行性充分發(fā)揮出來。采取一元、二元、單峰及多峰測試函數(shù)進行驗證，結果表明改進的KFC-2PMGA算法能有效避免子種群陷入同質(zhì)化，在收斂速度及收斂精度上有了顯著提升，對比傳統(tǒng)2PMGA算法及A-2PMGA算法能更加高效地搜索到全局最優(yōu)解。