基于差分進(jìn)化算法的圖像聚類研究

賈紫娟，楊淑瑩，王光彪

基于差分進(jìn)化算法的圖像聚類研究

賈紫娟，楊淑瑩，王光彪

（天津理工大學(xué)智能計算及軟件新技術(shù)重點實驗室，天津300384）

將差分進(jìn)化算法應(yīng)用于圖像聚類問題，對問題進(jìn)行實數(shù)編碼，采用群體智能模式實現(xiàn)問題解的搜索．利用差分進(jìn)化算法的差分變異操作和群體分布特性有效提高算法的搜索能力，采用貪婪選擇操作和競爭生存策略實現(xiàn)群體內(nèi)個體之間的相互合作與競爭，降低了進(jìn)化操作的復(fù)雜性，并通過仿真實驗證明了該算法的有效性．

差分進(jìn)化算法；群體智能；圖像聚類；優(yōu)化問題

差分進(jìn)化算法是Storn和Price于1995年提出的一種隨機(jī)并行搜索算法［1］，它與遺傳算法和粒子群算法等算法一樣是基于群體智能理論的優(yōu)化算法，利用由群體內(nèi)個體之間的相互合作與競爭產(chǎn)生的群體智能模式來指導(dǎo)優(yōu)化搜索的進(jìn)行．與其他進(jìn)化算法不同，差分進(jìn)化算法保留了基于種群的全局搜索策略，采用實數(shù)編碼、基于差分的簡單變異操作和一對一的競爭生存策略，降低了進(jìn)化操作的復(fù)雜性［2－3］．差分進(jìn)化算法特有的進(jìn)化操作使其具有較強(qiáng)的全局收斂能力和魯棒性，非常適于求解一些復(fù)雜環(huán)境中的優(yōu)化問題．

1 差分進(jìn)化算法的基本原理

差分進(jìn)化算法（Differential Evolution，DE）采用實數(shù)編碼方式，其算法原理和進(jìn)化流程與遺傳算法十分相似，如父代生成子代的操作均包括變異、交叉和選擇［4－5］．

與遺傳算法相比，差分進(jìn)化算法具有如下特點：首先，差分進(jìn)化算法的變異操作采用差分變異操作，即將種群中任意2個個體的差分向量加權(quán)后，根據(jù)一定的規(guī)則加到第3個個體上，再通過交叉系數(shù)控制下的交叉操作產(chǎn)生新個體，差分進(jìn)化算法的這種變異方式有效利用了群體分布特性，提高了算法的搜索能力，避免了遺傳算法中變異方式的不足；同時，差分進(jìn)化算法的選擇操作采用貪婪選擇操作，即如果新生成個體的適應(yīng)度值比父代個體的適應(yīng)度值大，則用新生成個體替代原種群中對應(yīng)的父代個體，否則原個體保存到下一代．差分進(jìn)化算法通過變異、交叉和選擇3個操作進(jìn)行迭代尋優(yōu)．

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

基于差分進(jìn)化算法的聚類算法的實現(xiàn)步驟如下：

（1）設(shè)置相關(guān)參數(shù)．

設(shè)置種群大小N、最大迭代次數(shù)Maxlter、交叉概率系數(shù)Pc和放大系數(shù)F．

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

（3）對群體進(jìn)行初始化，即隨機(jī)分配每個個體基因位的值．

（4）計算群體中每個個體的適應(yīng)度（適應(yīng)度值越大代表分類情況越準(zhǔn)確）．

（5）采用差分變異算子，生成下一代群體．

目前，較為常見的差分算子有4種，分別為隨機(jī)向量差分法（DE／rand／1）、最優(yōu)解加隨機(jī)向量差分法（DE／best／1）、最優(yōu)解加多個隨機(jī)向量差分法（DE／best／2）和最優(yōu)解與隨機(jī)向量差分法（DE／rand－to－best／1）。本研究采用最優(yōu)解與隨機(jī)向量差分法．

（6）進(jìn)行進(jìn)化算子的交叉操作．

隨機(jī)選擇一個基因位，并將該基因位設(shè)定為自變異后新生成的子代個體對應(yīng)的基因位上的基因；對于其他基因位，產(chǎn)生0～1之間的隨機(jī)數(shù)rand（i），i∈［1，patternNum］，通過與交叉概率系數(shù)Pc進(jìn)行比較控制父代子代基因的選擇，即當(dāng)rand（i）＜Pc時，選擇父代對應(yīng)的基因值，否則選擇子代（即通過差分變異后新產(chǎn)生的個體）對應(yīng)的基因值．

（7）計算新生成的子代群體的適應(yīng)度．

（8）執(zhí)行貪婪選擇．

比較對應(yīng)的父代和子代的適應(yīng)度值，選擇適應(yīng)度高的個體成為下一代的父代個體．

（9）保留精英個體，若在新生成的子代群體中，最優(yōu)個體適應(yīng)度值低于總的最優(yōu)個體的適應(yīng)度值，則用當(dāng)前最好的個體替換總的最好的個體．

（10）若已經(jīng)達(dá)到最大迭代次數(shù)，則退出循環(huán)，輸出結(jié)果，返回各個樣品的類別號；否則回到第（5）步，重新執(zhí)行操作直至達(dá)到最大迭代次數(shù)．

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

3．1 解的編碼設(shè)置

以含有10個數(shù)字的待聚類樣品為例，如圖1所示．采用實數(shù)編碼，在每個樣品的右上角編號，不同樣品采用不同編號，但樣品編號始終固定，即某個樣品在每個解中的位置是固定的．位串長度L取10位，分類號代表樣品所屬的類號（1～4），每個樣品的所屬類別隨時變化［6］．如果編號為n，則其對應(yīng)第n個樣品，而第n個位所指向的值代表第n個樣品的歸屬類號．

圖1 待聚類的樣品數(shù)字Fig．1 Number samples for clustering

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

表1 初始解Tab．1 Initial solution

3．2 差分變異算子

本研究所采用的最優(yōu)解與隨機(jī)向量差分法（DE／rand－to－best／1）將當(dāng)前種群的最優(yōu)個體置于差分向量中，種群中除當(dāng)前個體外，取最優(yōu)解與隨機(jī)選取的個體進(jìn)行向量相差，并乘以貪婪因子，同時任意選取互不相同的2個個體，將二者的向量差分結(jié)果乘以放大因子，加到當(dāng)前種群個體上．此種方法既利用了當(dāng)前種群最優(yōu)個體的信息，加快了搜索速度，又降低了優(yōu)化陷入局部最優(yōu)解的危險，即

式（1）中：λ為控制算法的“貪婪”程度，為了減少控制參數(shù)的數(shù)量，一般取λ＝F，則式（1）可改寫為

3．3 交叉算子

交叉算子操作依據(jù)交叉概率（Pc），使當(dāng)前父代個體m＿popt（i）和經(jīng)過差分變異生成的子代個體newpopt（i，j）的部分基因位進(jìn)行交換，從而生成新的子代個體．

為了保持種群的多樣性，父代個體m＿popt（i，j）經(jīng)過差分變異操作后，對新產(chǎn)生的個體newpopt（i，j）進(jìn)行交叉操作

式（3）中：randi，j表示在第i個個體的第j位基因上產(chǎn)生的符合均勻分布的隨機(jī)數(shù)，目的是為了與交叉概率Pc進(jìn)行比較，Pc∈（0，1）．如果randi，j≥Pc，則保留newpopt（i，j）的基因值，否則，用m＿popt（i，j）代替newpopt（i，j）相應(yīng)的基因值．這里引入一個隨機(jī)基因位Jrand，并強(qiáng)制使該位的基因取自變異后的新個體，這樣新個體newpopt（i，j）至少有一位基因由變異后產(chǎn)生的新個體提供，因此m＿popt（i，j）和newpopt（i，j）不會完全相同，從而更有效地提高種群的多樣性，保證個體的進(jìn)化．

3．4 貪婪選擇算子

如前所述，比較經(jīng)過變異和交叉操作后得到的子代個體newpopt和當(dāng)前父代個體m＿popt的適應(yīng)度，如果newpopt的適應(yīng)度大于m＿popt的適應(yīng)度，則選擇newpopt成為下一代的父代個體m＿popt＋1，否則m＿popt將直接進(jìn)入下一代．

4 實驗結(jié)果

在Inter（R）Core（TM）2Duo T7200處理器的計算機(jī)上和Matlab環(huán)境下，應(yīng)用差分進(jìn)化算法對圖像進(jìn)行聚類操作，結(jié)果如圖2所示．從圖2中可以看出，差分進(jìn)化算法實現(xiàn)了不同圖像的聚類，取得了較好的實驗效果．

圖2 聚類結(jié)果Fig．2 Result of clustering

差分進(jìn)化算法找到的最優(yōu)解編碼如表2所示．通過樣品值與基因值比較對照可以發(fā)現(xiàn)，相同的數(shù)據(jù)被歸為一類，分到相同的類號，而且全部正確．實驗結(jié)果表明：利用差分進(jìn)化算法有效地實現(xiàn)了不同圖像的聚類，并且取得了較好的實驗效果．

表2 差分進(jìn)化算法最終找到的最優(yōu)解Tab．2 Optimal Solution

5 結(jié)論

本研究在分析差分進(jìn)化算法原理的基礎(chǔ)上，詳細(xì)分析了差分進(jìn)化算法的3種操作算子，最后將差分進(jìn)化算法應(yīng)用到圖像聚類研究．差分進(jìn)化算法是基于群體智能理論的優(yōu)化算法，它保留了基于種群的全局搜索策略，利用群體內(nèi)個體之間的相互合作與競爭產(chǎn)生的群體智能模式來指導(dǎo)優(yōu)化搜索，降低了進(jìn)化操作的復(fù)雜性．

［1］ 王培崇，錢旭，王旭，等．差分進(jìn)化計算研究綜述［J］．計算機(jī)工程與應(yīng)用，2009，45（28）：13－16．

［2］ 黃天辰，韓國棟．進(jìn)化計算及應(yīng)用［J］．四川兵工學(xué)報，2009（3）：119－121．

［3］ 謝金星．進(jìn)化計算簡要綜述［J］．控制與決策，1997，12（1）：1－7．

［4］ 焦李成，保錚．進(jìn)化計算與遺傳算法—計算智能的新方向［J］．系統(tǒng)工程與電子技術(shù)，1995（6）：20－26．

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

［6］ 楊淑瑩．圖像模式識別—VC＋＋技術(shù)實現(xiàn)［M］．北京：清華大學(xué)出版社，北京交通大學(xué)出版社，2005：218－354．

（責(zé)任編校 亢原彬）

Research on image cluster based on differential evolutionary algorithm

JIA Zi－juan，YANG Shu－ying，WANG Guang－biao
（Key Laboratory of Intelligence Computing and Novel Software Technology，Tianjin University of Technology，Tianjin 300384，China）

Differential evolutionary algorithm is applied to image clustering problem．The problem is firstly encoded using real number，and swarm intelligent model is used for achieving the search for the solution．Through taking the best of features of the group distribution，the search capability of the algorithm is improved by using the operation of differential variation of the differential evolutionary algorithm．Mutual cooperation and competition among individuals within the group is achieved by adopting greed selection and survival strategies，and the complexity of the evolutionary operation is reduced．The simulation experiments show that the proposed algorithm for image cluster is correct and effective．

differential evolutionary algorithm；swarm intelligence；image cluster；optimization problem

book=2012,ebook=35

TP311

A

1671－1114（2012）02－0053－03

2012－01－10

國家自然基金資助項目（61001174）；天津市高校發(fā)展基金資助項目（20071308）

賈紫娟（1988－），女，碩士研究生．

楊淑瑩（1964－），女，教授，主要從事計算機(jī)仿真、模式識別與智能系統(tǒng)和動態(tài)目標(biāo)跟蹤方面的研究．