基于聚類劃分子種群的多種群遺傳算法

丁若冰，鄒書蓉

(成都信息工程學(xué)院計算機(jī)學(xué)院，成都 610000)

引 言

美國的Holland教授在20世紀(jì)七十年代首次提出了一種模擬達(dá)爾文進(jìn)化論的自然選擇機(jī)制的優(yōu)化算法，是最早的遺傳算法起源。遺傳算法［1］同其它優(yōu)化算法相比較擁有隱含的并行性、尋優(yōu)過程快速、本身的自適應(yīng)性及其魯棒性等優(yōu)點(diǎn)，此外還具有搜索不依賴于問題的梯度信息、模型特征的優(yōu)點(diǎn)，使其在傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題上有很好的效果，近年越來越多的國內(nèi)外學(xué)者致力于遺傳算法的研究，特別是多種群遺傳算法的研究。多種群遺傳算法(Multi-Population Genetic Algorithm，MPGA)是在遺傳算法并行運(yùn)算的基礎(chǔ)上，通過多種群并行進(jìn)化的思想，將遺傳算法中單種群進(jìn)化過程分解為多個子種群并行進(jìn)行的過程，每個子種群單獨(dú)完成選擇、交叉、變異操作，這樣不僅可以加快算法的收斂速度，而且避免了單個種群進(jìn)化過程中出現(xiàn)的過早收斂現(xiàn)象［2-6］。

但是，由于傳統(tǒng)的多種群遺傳算法只是簡單地將主種群沒有任何規(guī)律地劃分成多個子種群，所以算法仍存在許多不足之處，如進(jìn)化后期種群同質(zhì)化現(xiàn)象嚴(yán)重、種群陷入局部最優(yōu)等問題。本文提出了一種基于聚類劃分子種群的多種群遺傳算法(Multiple Population Genetic Algorithm Based on Clustering Dividing Populations，MPGA_BC)，使得子種群劃分不再是一種隨機(jī)行為，而是將滿足約束條件的個體根據(jù)其特征劃分到不同子種群中，從而解決種群同質(zhì)化問題，避免所有子種群陷入局部最優(yōu)，從而提高算法性能和算法搜尋全局最優(yōu)解的能力。

多種群遺傳算法后期子種群同質(zhì)化嚴(yán)重一直是一個重要缺陷，因為同質(zhì)化會導(dǎo)致種群陷入局部最優(yōu)，從而不能獲得全局最優(yōu)，盡管變異算子能在一定程度上打破這種狀況，但其幾率比變異操作的概率還要小得多，本文提出的基于聚類劃分的多種群遺傳算法從根本上解決種群同質(zhì)化問題，從而使得算法能最大程度地獲得全局最優(yōu)解。實(shí)驗結(jié)果表明改進(jìn)的算法有較好的尋優(yōu)能力和收斂能力。

1 聚類的定義和數(shù)學(xué)模型

1.1 聚類的定義

聚類［7］就是按照一定的要求和規(guī)律對事物進(jìn)行區(qū)分和分類的過程，在這一過程中沒有任何關(guān)于分類的先驗知識，僅靠事物間的相似性作為類屬劃分的準(zhǔn)則，因此屬于無監(jiān)督分類的范疇?！叭艘匀悍郑镆灶惥邸?，聚類是一個古老的問題，它伴隨著人類社會的產(chǎn)生和發(fā)展而不斷深化，人類要認(rèn)識世界就必須區(qū)別不同的事物并認(rèn)識事物間的相似性。

1.2 聚類的數(shù)學(xué)模型

從數(shù)學(xué)的角度來刻畫聚類劃分可以得出以下模型:設(shè) X={x1，x2，...，xm}是待聚類分析的對象的全體，X中的每個對象(稱為樣本)xi(i=1，2，...，m)常用有限個參數(shù)值來刻畫，每個參數(shù)值刻畫xi的某個特征。于是對象 xi就伴隨著一個向量 P(xi)=(xi1，xi2，...，xis)，其中 s是維度，xij(j=1，2，...，s)是 xi在第 j個屬性上的賦值，P(xi)稱為xi的特征向量或模式矢量。聚類分析就是分析論域X中的m個樣本所對應(yīng)的模式矢量間的相似性，按照樣本間的親疏關(guān)系把 x1，x2，...，xm劃分成多個不想交的子集 X1，X2，...，Xc，并要求滿足下列條件:

式(2)中，隸屬函數(shù)必須滿足條件μki∈Eh。也就是說，要求每一個樣本能且只能隸屬于某一類，同時要求每個子集(類)都是非空的。

本文使用K均值聚類算，算法詳細(xì)法描述如下:

(1)隨機(jī)地生成K個聚類中心;

(2)計算所有樣本點(diǎn)到各聚類中心的距離，并將其歸入與其距離最近的聚類中心所代表的的那一類;

(3)對每一類，計算其樣本均值，將其作為該類新的聚類中心;

(4)如果在第(2)步某一樣本的類別發(fā)生改變，則轉(zhuǎn)第(2)步;

(5)返回聚類核心和各個樣本類別，聚類終止。

2 聚類劃分子種群的多種群遺傳算法

2.1 引入聚類方式劃分子種群優(yōu)勢

傳統(tǒng)的多種群遺傳算法雖然能夠?qū)⒎N群分割，從而加快種群收斂速度，但是傳統(tǒng)的劃分子種群的方法只是如圖1所示，簡單隨機(jī)的將種群初始化為A、B和C幾個子種群，并沒有按個體本身特性分配到不同種群中去。這樣會導(dǎo)致種群同質(zhì)化嚴(yán)重，最終收斂向同一個最優(yōu)解。

本文提出引入聚類的思想如圖2所示，將特性相似的個體劃分到相同的子種群里，這樣可以克服基本多種群遺傳算法的缺陷，避免種群間出現(xiàn)同質(zhì)化的現(xiàn)象，而子種群劃分能使單個種群更快的收斂到最優(yōu)解，最后通過子種群間比較取得全局最優(yōu)，將遺傳算法本身的并行性發(fā)揮出來，實(shí)現(xiàn)并行搜索最優(yōu)，匯總?cè)∪肿顑?yōu)的方式來尋找全局最優(yōu)的解。此外，使用聚類的方式劃分子種群更加符合自然規(guī)律［7-8］。

圖1 非聚類方式劃分樣本子種群

2.2 算法步驟

Step0:初始化種群規(guī)模P，子種群個數(shù)K，以及終止迭代代數(shù)T;

Step1:隨機(jī)生成規(guī)模為P的種群;

Step2:將所有個體進(jìn)行聚類，生成K個子種群;

Step3:對每個子種群進(jìn)行如下進(jìn)化迭代:

(1)評價所有個體;

(2)利用最優(yōu)保留策略的比例完成該子種群父代個體的選擇，并對其執(zhí)行交叉操作;

圖2 聚類方式劃分樣本子種群

(3)根據(jù)變異概率對種群內(nèi)個體進(jìn)行變異操作，得到新一代種群;

(4)如果沒有達(dá)到給定迭代代數(shù)，轉(zhuǎn)Step3，否則，轉(zhuǎn)Step4;

Step4:如果不滿足終止條件，將所有子種群合并，轉(zhuǎn)Step2，否則，轉(zhuǎn)Step5;

Step5:從每個子種群中選出最好個體作為最優(yōu)解，進(jìn)化過程結(jié)束。

3 實(shí)驗仿真及結(jié)果分析

3.1 典型測試函數(shù)

為了驗證文章中提出的改進(jìn)的多種群遺傳算法的可行性與有效性，選擇了兩個典型函數(shù)Sphere Model與Rastrigrin進(jìn)行測試，這個兩個函數(shù)分別表示如下:

Sphere Model函數(shù):

Rastrigrin函數(shù):

圖3和圖4分別描述了上述單峰值函數(shù)和多峰值函數(shù)定義域內(nèi)的三維圖。由圖3可知，單峰值函數(shù)在f(0，0)時取得全局最優(yōu)解［圖4顯示的是一個多峰值典型測試函數(shù)的曲面圖，有多個峰值陷阱，能夠?qū)е乱话銉?yōu)化算法陷入局部最優(yōu)，其全局最優(yōu)解在x，y∈(0，0)處取得，全局最優(yōu)解為0。

3.2 測試結(jié)果分析

圖3 Sphere Model函數(shù)三維圖

圖4 Rastrigrin函數(shù)三維圖

本實(shí)驗是在intel i3處理器、4 G內(nèi)存的個人筆記本上完成的，仿真環(huán)境為matlab2013b。實(shí)驗參數(shù)配置見表1。

表1 配置參數(shù)列表

表2是兩種算法測試對比數(shù)據(jù)，表明在單峰值函數(shù)中，兩種算法收斂到全局最優(yōu)解的次數(shù)和搜索到最優(yōu)解的平均值沒有太大差別，改進(jìn)的算法只是有略微的優(yōu)勢;但是在多峰值函數(shù)問題中改進(jìn)的算法仍然能保持算法收斂率，而傳統(tǒng)算法收斂率只有50%左右。在處理復(fù)雜的多峰值問題時傳統(tǒng)的多種群遺傳算法容易陷入局部解、不能收斂、尋找不到最優(yōu)解等問題。從數(shù)據(jù)對比可以看到文章提出的算法不僅能夠提高收斂率和收斂速度，而且能夠在面對復(fù)雜的多峰值尋優(yōu)問題的時候更加穩(wěn)定的搜索到全局最優(yōu)解。

表2 實(shí)驗數(shù)據(jù)對比表

4 結(jié)束語

本文將聚類劃分引入多種群遺傳算法，提出了一種使用聚類方式劃分子種群的多種群遺傳算法，用個體特性來為其歸類的思想初始化總?cè)?，并將其合理劃分為有各自特性的子種群。通過對典型測試函數(shù)的實(shí)驗測試，其結(jié)果表明基于聚類劃分種群的多種群遺傳算法與基本多種群算法相比能夠有效的避免子種群陷入同質(zhì)化現(xiàn)象，能夠提高算法收斂率和收斂速度，此外，基于聚類劃分子種群的多種群遺傳算法相比傳統(tǒng)的多種群遺傳算法能夠更好的搜索到全局最優(yōu)解，算法有很好的效果。

［1］ Holland J H.Adaptation in natural and artificial systems［M］.Ann Arbor:The University of Michigan Press，1975.

［2］李軍華，黎 明，袁麗華.一種改進(jìn)的雙種群遺傳算法［J］.小型微型計算機(jī)系統(tǒng)，2008，29(11):2099-2102.

［3］Borisovsky P，Dolgui A，Eremeev A.Genetic algorithms for a supply management problem:M IP-recombination VS greedy decoder［J］.Science Direct，2007，19(5):770-779.

［4］公茂果，焦李成，楊咚咚.進(jìn)化多目標(biāo)優(yōu)化算法研究［J］.軟件學(xué)報，2009，20(2):271-289.

［5］鞏敦衛(wèi)，孫曉燕.變搜索區(qū)域多種群遺傳算法［J］.控制理論與應(yīng)用，2006，23(2):256-260.

［6］王文義，秦廣軍，王若雨.自適應(yīng)的多種群并行遺傳算法研究［J］.計算機(jī)工程與應(yīng)用，2006，42(15):34-36.

［7］孫吉貴，劉 杰，趙連宇.聚類算法研究［J］.軟件學(xué)報，2008，19(1):48-61.

［8］賴玉霞，劉建平.基于遺傳算法的K均值聚類分析［J］.計算機(jī)工程，2008，34(20):200-202.