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

丁若冰，鄒書蓉

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

引 言

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

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

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

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

1.1 聚類的定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法步驟

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

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

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

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

(1)評(píng)價(jià)所有個(gè)體;

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

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

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

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

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

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

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

3.1 典型測(cè)試函數(shù)

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

Sphere Model函數(shù):

Rastrigrin函數(shù):

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

3.2 測(cè)試結(jié)果分析

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

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

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

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

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

表2 實(shí)驗(yàn)數(shù)據(jù)對(duì)比表

4 結(jié)束語(yǔ)

本文將聚類劃分引入多種群遺傳算法，提出了一種使用聚類方式劃分子種群的多種群遺傳算法，用個(gè)體特性來(lái)為其歸類的思想初始化總?cè)?，并將其合理劃分為有各自特性的子種群。通過(guò)對(duì)典型測(cè)試函數(shù)的實(shí)驗(yàn)測(cè)試，其結(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ì)算機(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é)報(bào)，2009，20(2):271-289.

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

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

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

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