丁若冰，鄒書蓉

(成都信息工程學院計算機學院，成都 610000)

引 言

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

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

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

1 聚類的定義和數學模型

1.1 聚類的定義

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

1.2 聚類的數學模型

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法步驟

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

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

Step2:將所有個體進行聚類，生成K個子種群;

Step3:對每個子種群進行如下進化迭代:

(1)評價所有個體;

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

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

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

(4)如果沒有達到給定迭代代數，轉Step3，否則，轉Step4;

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

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

3 實驗仿真及結果分析

3.1 典型測試函數

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

Sphere Model函數:

Rastrigrin函數:

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

3.2 測試結果分析

圖3 Sphere Model函數三維圖

圖4 Rastrigrin函數三維圖

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

表1 配置參數列表

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

表2 實驗數據對比表

4 結束語

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

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

［2］李軍華，黎 明，袁麗華.一種改進的雙種群遺傳算法［J］.小型微型計算機系統，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］公茂果，焦李成，楊咚咚.進化多目標優(yōu)化算法研究［J］.軟件學報，2009，20(2):271-289.

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

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

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

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