基于進(jìn)化規(guī)劃算法的圖像聚類研究

王兆珍，劉旭鵬，楊淑瑩

（1.天津現(xiàn)代職業(yè)技術(shù)學(xué)院電子工程系，天津 300350；2.天津理工大學(xué)智能計(jì)算及軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津 300384）

圖像聚類是指將圖像中若干樣品分成不同類，并將相同形狀的物體歸為一類的算法[1]，它在模式識(shí)別領(lǐng)域中占有重要地位，主要用于數(shù)據(jù)壓縮、數(shù)據(jù)挖掘和圖像檢索等.圖像聚類涉及特征提取和識(shí)別算法，它們直接影響聚類速度和識(shí)別精度.在圖像聚類識(shí)別方法當(dāng)中，常用的有遺傳算法、k-means算法和粒子群算法等.其中遺傳算法[2-3]在局部搜索過(guò)程中表現(xiàn)能力差，搜索速度相對(duì)較慢，容易出現(xiàn)早熟現(xiàn)象；k-means算法[4]對(duì)初始值的聚類中心較為敏感，容易陷入局部最優(yōu)；粒子群優(yōu)化算法[5]是一種基于群體的智能算法，但是后期具有收斂慢、搜索精度低和容易陷入局部極小等缺點(diǎn).在圖像聚類過(guò)程中，上述算法都不可避免地出現(xiàn)重復(fù)搜索的現(xiàn)象，如果樣品的數(shù)目過(guò)多，則上述算法進(jìn)行搜索的時(shí)間消耗將更為突出[6].

進(jìn)化規(guī)劃（evolutionary programming，EP）是為了求解預(yù)測(cè)問(wèn)題而提出的一種有限機(jī)進(jìn)化模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程得到的一種隨機(jī)搜索方法，屬于進(jìn)化計(jì)算的分支.該算法在變異運(yùn)算中引入正態(tài)分布技術(shù)，從而使進(jìn)化規(guī)劃成為一種優(yōu)化搜索算法，可作為進(jìn)化計(jì)算的一個(gè)分支在實(shí)際領(lǐng)域中得到廣泛應(yīng)用.進(jìn)化規(guī)劃可應(yīng)用于求解組合優(yōu)化問(wèn)題和復(fù)雜的非線性優(yōu)化問(wèn)題，它只要求所求問(wèn)題是可計(jì)算的，且使用范圍較廣，目前已應(yīng)用于人工智能和機(jī)器人智能控制等諸多領(lǐng)域[9-10].與遺傳算法相比，在模擬生物進(jìn)化的過(guò)程中，進(jìn)化規(guī)劃主要著眼于物種的進(jìn)化過(guò)程，不使用個(gè)體交叉算子和重組算子來(lái)操作[11].進(jìn)化規(guī)劃中的選擇算子著重于群體中各個(gè)體之間的競(jìng)爭(zhēng)選擇，但是當(dāng)競(jìng)爭(zhēng)個(gè)體數(shù)目較大時(shí)，也就類似于進(jìn)化策略中的選擇過(guò)程.進(jìn)化規(guī)劃直接把問(wèn)題的可行解作為個(gè)體的編碼，無(wú)需再對(duì)個(gè)體進(jìn)行編碼處理，也無(wú)需考慮隨機(jī)擾動(dòng)因素對(duì)個(gè)體的影響，更便于應(yīng)用.本研究將進(jìn)化規(guī)劃優(yōu)化算法應(yīng)用于圖像聚類問(wèn)題，并通過(guò)仿真實(shí)驗(yàn)檢驗(yàn)算法的性能．

1 進(jìn)化規(guī)劃基本原理

進(jìn)化規(guī)劃的基本原理為：

（1）種群初始化(隨機(jī)分布個(gè)體).

（2）變異(更新個(gè)體).進(jìn)化規(guī)劃中不使用平均變異方法，而使用高斯變異算子，以實(shí)現(xiàn)種群內(nèi)個(gè)體的變異，保持種群中豐富的多樣性.高斯變異算子可以根據(jù)個(gè)體適應(yīng)度獲得高斯變異的標(biāo)準(zhǔn)差，對(duì)于適應(yīng)度低的個(gè)體，其變異范圍大，高斯變異算子可擴(kuò)大搜索的范圍；對(duì)于適應(yīng)度高的個(gè)體，其變異范圍小.高斯變異算子可以在當(dāng)前位置局部小范圍的搜索，以實(shí)現(xiàn)變異操作.

（3）適應(yīng)度計(jì)算(評(píng)價(jià)個(gè)體).

（4）選擇(群體更新).在選擇操作上，進(jìn)化規(guī)劃算法采用父代與子代一同競(jìng)爭(zhēng)的方式，利用錦標(biāo)賽選擇算子，最終選擇適應(yīng)度較高的個(gè)體.

雖然進(jìn)化規(guī)劃算法同樣是對(duì)生物進(jìn)化過(guò)程進(jìn)行模擬，且具有進(jìn)化計(jì)算的一般流程，但進(jìn)化規(guī)劃算法具有其自身特點(diǎn).與其他進(jìn)化計(jì)算相比[12]，進(jìn)化規(guī)劃算法不使用遺傳算法的交叉，也不使用進(jìn)化策略算法的基因重組算子，而使用變異算子操作來(lái)體現(xiàn)個(gè)體之間相互作用[13].

2 聚類算法的實(shí)現(xiàn)

基于進(jìn)化規(guī)劃算法的聚類算法實(shí)現(xiàn)步驟如下：

（1）設(shè)置相關(guān)參數(shù)：初始化初始種群中的個(gè)體數(shù)Sizepop、最大迭代次數(shù)Itermax、聚類中心數(shù)目Numcenter以及進(jìn)行錦標(biāo)賽競(jìng)爭(zhēng)時(shí)用于比較的個(gè)體數(shù)q.

（2）獲得所有待聚類樣品個(gè)數(shù)和特征.

（3）群體初始化，即隨機(jī)分配每個(gè)個(gè)體基因位的值.

（4）計(jì)算每個(gè)個(gè)體的適應(yīng)度值fitness.

（5）通過(guò)高斯變異算子，生成Sizepop個(gè)新個(gè)體：對(duì)所有個(gè)體循環(huán)每個(gè)基因位，對(duì)該位基因運(yùn)用變異算子操作，按照高斯變異產(chǎn)生1個(gè)1～-Numcenter之間的數(shù)賦值給該位，生成子代群體.

（6）計(jì)算新生成的Sizepop個(gè)子代個(gè)體適應(yīng)度值.

（7）令父代與子代個(gè)體（共2×Sizepop個(gè)）組成新群體totalpop，對(duì)新群體進(jìn)行選擇算子操作：隨機(jī)從totalpop中選擇q個(gè)個(gè)體，循環(huán)每個(gè)體，讓每個(gè)個(gè)體與這q個(gè)個(gè)體逐個(gè)進(jìn)行適應(yīng)度值的比較，以q個(gè)個(gè)體中適應(yīng)度值高于當(dāng)前個(gè)體適應(yīng)度值的個(gè)體個(gè)數(shù)作為當(dāng)前個(gè)體的得分，最終選擇評(píng)分最高的Sizepop個(gè)個(gè)體，作為下一代父代.

（8）記錄種群中的最優(yōu)解：若新生成的子代群體中，最優(yōu)個(gè)體適應(yīng)度值低于全體種群的最優(yōu)個(gè)體的適應(yīng)度值（相互之間距離越近，適應(yīng)度值越小），則用當(dāng)前最好的個(gè)體替換總的最好的個(gè)體.

（9）判斷是否滿足停止條件，即判斷是否達(dá)到總的迭代次數(shù).如果是，則輸出最優(yōu)解，即輸出各個(gè)樣品的類別號(hào)，并退出；反之，則跳轉(zhuǎn)到步驟（4）繼續(xù)迭代.

3 基于差分進(jìn)化算法的圖像聚類設(shè)計(jì)

3.1 特征提取

為更好地實(shí)現(xiàn)待測(cè)圖像有效聚類，首先須對(duì)每個(gè)待測(cè)圖像提取特征參數(shù)[14].本研究特征參數(shù)的提取方法為：在每個(gè)數(shù)字的外邊緣劃定1個(gè)矩形框，將矩形框的長(zhǎng)和寬進(jìn)行N×M分割，分割后的每個(gè)數(shù)字稱為N×M模板[7]；然后計(jì)算每個(gè)小方格的黑像素個(gè)數(shù)在本方格內(nèi)的比例，以此作為樣品特征值.以圖1為例.

將樣品分割成7×5個(gè)小方格，在每1小方格中統(tǒng)計(jì)黑像素所占方格總面積的比例，即得特征值，根據(jù)實(shí)際問(wèn)題的需要可適當(dāng)修改N和M的值，其值越大，樣品特征越多，聚類精度越高，算法收斂時(shí)間則會(huì)相應(yīng)延長(zhǎng)；其值越小，算法收斂速度加快，但聚類精度會(huì)有所下降.

3.2 解的編碼

在進(jìn)化規(guī)劃中，采用符號(hào)編碼，位串長(zhǎng)度為L(zhǎng)，搜索空間為1個(gè)L維空間，與其相對(duì)應(yīng)，搜索點(diǎn)為1個(gè)L維向量.算法中，組成進(jìn)化群體的每個(gè)染色體X可直接用這個(gè)L維向量表示.

圖2為待聚類樣品圖.

圖2中每個(gè)個(gè)體均包含1種分類方案.L取12位，基因代表樣品所屬的類號(hào)（1～4），基因位的序號(hào)代表樣品的編號(hào)，基因位的序號(hào)是固定的，即某個(gè)樣品在染色體中的位置是固定的，而每個(gè)樣品所屬的類別在隨時(shí)變化.若基因位為n，則其對(duì)應(yīng)第n個(gè)樣品，而第n個(gè)基因位所指向的基因值代表第n個(gè)樣品的歸屬類號(hào).

每個(gè)解包含1種分類方案，某個(gè)個(gè)體的初始染色體編碼為（1，3，4，1，2，4，2，3，1，3，2，1），其含義為：第1、4、9和12個(gè)樣品被分到第1類；第5、7和11個(gè)樣品被分到第2類；第2、8和10個(gè)樣品被分到第3類；第3、6個(gè)樣品屬于第4類，此時(shí)還處于假設(shè)分類情況，不是最優(yōu)解，如表1所示.

表1 初始染色體編碼Tab.1 Code of initial chromosome

3.3 設(shè)置適應(yīng)度函數(shù)

適應(yīng)度函數(shù)代表每個(gè)個(gè)體優(yōu)劣的程度，對(duì)初始群體中的每個(gè)染色體計(jì)算其適應(yīng)度值fitnessm_pop（i），其實(shí)現(xiàn)步驟如下：

（1）通過(guò)人工干預(yù)獲得聚類類別總數(shù)Numcenter.

（2）找出染色體中相同類別號(hào)的樣品，X(i)表示第i個(gè)類的樣品.

（3）統(tǒng)計(jì)每個(gè)類的樣品個(gè)數(shù)n，ni為第i個(gè)類別的個(gè)數(shù)，樣品總數(shù)為

（5）同一類內(nèi)計(jì)算每個(gè)樣品到相應(yīng)的聚類中心的距離，并將其累加求和

（6）將不同類的Di求和，賦值給

將fitnessm_pop(i)作為最適應(yīng)度函數(shù)，其值越小，說(shuō)明這種分類方法的誤差越小，即其適應(yīng)度值越小.

3.4 變異算子

變異操作是進(jìn)化規(guī)劃算法中最重要的操作，也是唯一的搜索方法，這是進(jìn)化規(guī)劃的獨(dú)特之處.在標(biāo)準(zhǔn)的進(jìn)化規(guī)劃中，變異操作應(yīng)使用高斯變異（Gauss mutation）算子[8].變異過(guò)程中，計(jì)算每個(gè)個(gè)體適應(yīng)度函數(shù)值線性變換的平方根，從而獲得該個(gè)體變異的標(biāo)準(zhǔn)差si，將每個(gè)分量加上1個(gè)服從正態(tài)分布的隨機(jī)數(shù).

設(shè)X為染色體個(gè)體解的目標(biāo)變量，s為高斯變異的標(biāo)準(zhǔn)差.每部分都有L個(gè)分量，即染色體的L個(gè)基因位.染色體由目標(biāo)變量X和標(biāo)準(zhǔn)差s兩部分組成，即（X，s）=［（x1，x2，…，xL），s］.

個(gè)體變異的形式為 X（t+1）=X（t）+N（0，s）.X和標(biāo)準(zhǔn)差s之間的關(guān)系是

式（1）和式（2）中：F（X（t））是當(dāng)前個(gè)體的適應(yīng)度值，越靠近目標(biāo)解個(gè)體的適應(yīng)度值越小；N（0，s）是概率密度為的高斯隨機(jī)變量；b和g是待定參數(shù)，一般將b和g的值設(shè)為1和0；目標(biāo)變量X的每個(gè)分量通過(guò)式（1）可以達(dá)到不同的變異效果.

3.5 選擇算子

在進(jìn)化規(guī)劃中，選擇機(jī)制的作用是根據(jù)適應(yīng)度函數(shù)值從父代和子代集合的2×Sizepop個(gè)個(gè)體中選擇Sizepop個(gè)較好的個(gè)體組成下一代種群，其形式化表示為：s：I2×Sizepop→ISizepop.選擇操作按照一種隨機(jī)競(jìng)爭(zhēng)的方式進(jìn)行，進(jìn)化規(guī)劃中選擇算子主要通過(guò)概率選擇、錦標(biāo)賽選擇和精英選擇3種方式選取，其中錦標(biāo)賽選擇方法是進(jìn)化規(guī)劃中較為常用的方法.錦標(biāo)賽選擇操作的具體過(guò)程為：

（1）將由Sizepop個(gè)父代個(gè)體組成的種群P（t）和由種群P（t）經(jīng)過(guò)1次變異運(yùn)算后產(chǎn)生的由Sizepop個(gè)子代個(gè)體組成的種群P′（t）合并在一起，組成1個(gè)共含有2×Sizepop個(gè)個(gè)體的集合P（t）∪P′（t），記為I；

（2）每個(gè)個(gè)體xi∈I，從I中隨機(jī)選擇q個(gè)個(gè)體，并將q個(gè)個(gè)體的適應(yīng)度函數(shù)值Fj（j∈(1，2，…，q))與xi的適應(yīng)度函數(shù)值進(jìn)行比較，計(jì)算出q個(gè)個(gè)體中適應(yīng)度函數(shù)值比xi適應(yīng)度差的個(gè)體的數(shù)目wi，并把wi作為 xi的得分，其中 wi∈（0，1，…，q）.

（3）在所有2×Sizepop個(gè)個(gè)體都經(jīng)過(guò)比較后，按每個(gè)個(gè)體的得分wi進(jìn)行排序，選擇Sizepop個(gè)具有最高得分的個(gè)體作為下一代種群.

算法中，q≥1為選擇算法的參數(shù)，為使錦標(biāo)賽選擇算子發(fā)揮更好的作用，需要設(shè)定適當(dāng)?shù)挠糜诒容^的個(gè)體數(shù)q.q的取值較大時(shí)，偏向確定性選擇，當(dāng)q=2×Sizepop時(shí)，則從2×Sizepop個(gè)個(gè)體中將適應(yīng)度值較高的Sizepop個(gè)個(gè)體選出，容易帶來(lái)早熟等弊端；相反，q的取值較小時(shí)，偏向于隨機(jī)性選擇，適應(yīng)度的控制能力下降，導(dǎo)致大量低適應(yīng)度的個(gè)體被選出，造成種群退化.因此，為了既能夠保持種群的先進(jìn)性，又避免確定性選擇帶來(lái)的早熟弊端，需要依據(jù)具體問(wèn)題，合適地選取q值.

進(jìn)化過(guò)程中，每代種群中相對(duì)較好的個(gè)體被賦予了較大的得分，能夠被保留到下一代的群體中.

4 實(shí)驗(yàn)結(jié)果

在MATLAB 2008環(huán)境下，編程實(shí)現(xiàn)了基于進(jìn)化規(guī)劃的手寫(xiě)數(shù)字的聚類問(wèn)題，并在Inter(R)Core(TM)i5 CPU處理器的計(jì)算機(jī)上對(duì)圖2所示的待聚類圖像進(jìn)行相應(yīng)的聚類實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3所示.由圖3可以看出，進(jìn)化規(guī)劃算法可以很好地實(shí)現(xiàn)不同手寫(xiě)數(shù)字的聚類，取得了較好的實(shí)現(xiàn)效果.

進(jìn)化規(guī)劃算法找到的最優(yōu)解編碼如表2所示.通過(guò)樣品值與基因值比較對(duì)照可以發(fā)現(xiàn)，相同的手寫(xiě)數(shù)字被歸為一類，分到相同的類號(hào)，而且全部正確.實(shí)驗(yàn)結(jié)果表明：進(jìn)化規(guī)劃算法可以有效實(shí)現(xiàn)不同圖像的聚類.

表2 進(jìn)化規(guī)劃算法獲得的最優(yōu)解編碼Tab.2 Optimal solution achieved by evolutionary programm ing

5 結(jié)論

本研究分析了進(jìn)化規(guī)劃算法的原理和仿生機(jī)制，并將其應(yīng)用于圖像聚類問(wèn)題的求解，仿真實(shí)驗(yàn)結(jié)果表明，基于進(jìn)化規(guī)劃算法的圖像聚類方法具有良好的可行性與準(zhǔn)確性.

[1]楊淑瑩．圖像模式識(shí)別—VC++技術(shù)實(shí)現(xiàn)[M]．北京∶清華大學(xué)出版社，北京交通大學(xué)出版社，2005．

[2]張講社，徐宗本，梁怡．整體退火遺傳算法及其收斂充要條件[J]．中國(guó)科學(xué)：E 輯，1997，27（2）：154—164．

[3]張忠華，楊淑瑩．基于遺傳算法的圖像聚類設(shè)計(jì)[J]．測(cè)控技術(shù)，2010，29（2）：4—46．

[4]郭慶銳，許建龍，孫樹(shù)森，等．基于顏色重心和k-means的彩色圖像聚類分割算法[J]．浙江理工大學(xué)學(xué)報(bào)，2010，27（4）：580—584．

[5]宋潔，董永峰，侯向丹，等．改進(jìn)的粒子群優(yōu)化算法[J]．河北工業(yè)大學(xué)學(xué)報(bào)，2008，37（4）：55—59．

[6]謝金星．進(jìn)化計(jì)算簡(jiǎn)要綜述[J]．控制與決策，1997，12（1）：1—7．

[7]LEECY，YAOX.Evolutionary programmingusingmutationsbased on the levy probability distribution[J].Transactions on Evolutionary Computation.2004，8（2）：1—13.

[8]IWAMATSU M.Generalized evolutionary programming with Levytypemutation[J].Computer Physics Communications，2002，147（8）：729—732.

[9]商允偉，裘隸皇．一種求解數(shù)值優(yōu)化問(wèn)題的快速進(jìn)化規(guī)劃算法[J]．系統(tǒng)仿真學(xué)報(bào)，2004，16（6）：1190—1192.

[10]王麗萍，董江輝．帶有一種新的算子的進(jìn)化規(guī)劃算法的收斂性分析[J]．科學(xué)技術(shù)與工程，2009，9（6）：1428—1431．

[11]高永超，李歧強(qiáng)．退火進(jìn)化規(guī)劃算法及其收斂性[J]．系統(tǒng)仿真學(xué)報(bào)，2006，18（3）：577—580．

[12]王向軍，嵇斗，張民．一種多群競(jìng)爭(zhēng)進(jìn)化規(guī)劃算法[J]．電子學(xué)報(bào)，2004，32（11）：1824—1828．

[13]高瑋．遺傳算法與進(jìn)化規(guī)劃的比較研究[J]．通訊和計(jì)算機(jī)，2005，2（8）：10—15．

[14]楊淑瑩．模式識(shí)別與智能計(jì)算-Matlab技術(shù)實(shí)現(xiàn)[M]．北京∶電子工業(yè)出版社，2011∶34—36．