摘  要： 針對(duì)傳統(tǒng)優(yōu)化算法在圖像聚類分析中存在的復(fù)雜度高、容易陷入局部最優(yōu)解的問(wèn)題，提出了使用貓群算法求解圖像聚類問(wèn)題。該算法通過(guò)分組和混合策略的機(jī)制進(jìn)行信息傳遞，用貓記憶當(dāng)前群體中的全局最優(yōu)解來(lái)更新自身，提高了算法的搜索能力；闡述了貓群算法的搜尋模式和跟蹤模式，討論了兩種模式下貓群的速度、位置更新公式；并說(shuō)明了利用該算法求解圖像聚類分析問(wèn)題的具體步驟。通過(guò)實(shí)驗(yàn)驗(yàn)證了貓群算法在圖像聚類分析中的有效性和準(zhǔn)確性。

　　關(guān)鍵詞： 貓群算法；群體智能；組合優(yōu)化；圖像聚類

0 引言

　　圖像的聚類分析就是在錯(cuò)誤率最小的情況下，把特征相近或者相同的圖像歸為一類，是模式識(shí)別研究方向的一個(gè)重要環(huán)節(jié)。人們已經(jīng)找到了許多用于圖像聚類分析的群體仿生智能優(yōu)化算法，其中比較典型的算法包括粒子群算法、遺傳算法以及蟻群算法等。粒子群算法在后期不能很好地跳出局部最優(yōu)；遺傳算法搜索速度比較緩慢，不能較好地進(jìn)行局部搜索；蟻群算法需要強(qiáng)調(diào)信息素的作用，增加了算法的時(shí)間復(fù)雜度，降低了分類效率。為了解決上述問(wèn)題，本文提出了解決圖像聚類分析的一種智能仿生算法——貓群算法，并以圖像中不同物體聚類分析為例，介紹該算法解決聚類問(wèn)題的實(shí)現(xiàn)方法并驗(yàn)證算法的正確性和有效性。

1 貓群算法的基本原理

　　貓群算法是通過(guò)觀察貓?jiān)谌粘Ｉ钪械男袨閯?dòng)作提出的群體智能仿生算法，貓即為待求優(yōu)化問(wèn)題的可行解[1]。該算法將貓的行為分為搜尋模式和跟蹤模式，在搜尋模式中貓?zhí)幱谛菹?、張望的狀態(tài)；而在跟蹤模式中貓?jiān)诟檮?dòng)態(tài)目標(biāo)。在整個(gè)貓群中，絕大多數(shù)貓執(zhí)行搜尋模式，而只有少量的貓?zhí)幱诟櫮Ｊ絒2]。在搜尋模式下，記憶池記錄了貓所搜尋的鄰域位置點(diǎn)，記憶池的大小代表貓能夠搜索的地點(diǎn)數(shù)量，通過(guò)變異算子，改變?cè)?，使記憶池存?chǔ)了貓?jiān)谧陨淼泥徲騼?nèi)能夠搜索的新地點(diǎn)，貓根據(jù)保存在記憶池中適應(yīng)度值的大小選擇一個(gè)最好的位置點(diǎn)。在跟蹤模式下，每一次迭代中，貓將跟蹤一個(gè)“極值”來(lái)更新自己，這個(gè)“極值”是目前整個(gè)種群找到的最優(yōu)解[3]，使得貓的移動(dòng)方向向著全局最優(yōu)解逼近，利用全局最優(yōu)的位置來(lái)更新貓的位置，具有向“他人”學(xué)習(xí)的機(jī)制。然后混合成為一個(gè)群體，根據(jù)分組率，隨機(jī)地將貓群分為搜尋模式和跟蹤模式兩種模式，直到算法執(zhí)行完預(yù)定的種群進(jìn)化次數(shù)結(jié)束。

　　1.1 搜尋模式

　　在搜尋模式中，定義了3個(gè)基本要素：記憶池、個(gè)體上每個(gè)基因改變范圍、個(gè)體上需要改變的基因的個(gè)數(shù)。記憶池中記錄了貓所搜尋的鄰域位置點(diǎn)，貓從中選擇一個(gè)適應(yīng)度最好的位置點(diǎn)；在算法開始之前設(shè)定個(gè)體上每個(gè)基因改變范圍的值，一般取值為0.2；在基因總長(zhǎng)度的范圍內(nèi)隨機(jī)挑選一個(gè)值作為個(gè)體上需要改變的基因個(gè)數(shù)。搜尋模式可分為如下3個(gè)步驟：

　　（1）復(fù)制自身位置。貓把自身的位置復(fù)制J份并且存放在記憶池中，J為記憶池的大小[4]。

　?。?）執(zhí)行變異算子。變異算子是一種局部搜索操作，每只貓經(jīng)過(guò)復(fù)制、變異產(chǎn)生鄰域候選解，在鄰域里找出最優(yōu)解，即完成了變異算子。對(duì)記憶池中的每個(gè)個(gè)體，個(gè)體上每個(gè)基因改變的范圍是一個(gè)隨機(jī)值，它的大小取值范圍是從零至個(gè)體上基因總長(zhǎng)度之間，并且是在算法開始之前設(shè)定的。根據(jù)個(gè)體上需要改變的基因的個(gè)數(shù)和改變的范圍，在原來(lái)的位置上隨機(jī)加上一個(gè)擾動(dòng)，然后使用新的位置來(lái)替代原來(lái)的位置[1]。

　　（3）執(zhí)行選擇算子。復(fù)制貓的自身位置，把新的位置副本保存在記憶池中，從中選擇適應(yīng)度值最高的新位置來(lái)代替當(dāng)前貓的位置。

　　1.2 跟蹤模式

　　貓進(jìn)入跟蹤模式后，貓群算法即類似于粒子群算法，采用速度-位移模式來(lái)移動(dòng)每一位基因的值。貓的跟蹤模式可以通過(guò)以下兩步來(lái)描述。

　?。?）速度-位移模型操作算子

　　整個(gè)貓群經(jīng)歷的最好位置，即為目前得到的最優(yōu)解[1]，記做。每個(gè)貓都有一個(gè)速度，記做Vi={vi1，vi2，…，viL}，定義式（1）：

　　其中，表示更新后第k只貓的第d位基因的速度值，L為個(gè)體上基因的總長(zhǎng)度[1]；代表的是第k只貓Xk（t）所處位置的第d個(gè)分量；c是一個(gè)常量，其值需要根據(jù)不同的問(wèn)題而定；rand是一個(gè)隨機(jī)數(shù)，它的取值范圍是0~1。

　?。?）根據(jù)式（2）更新第k只貓的位置：

　　其中，代表位置更新后第k只貓Xk（t+1）的第d個(gè)位置分量。

2 控制參數(shù)選擇

　　2.1 群體規(guī)模

　　較大的群體規(guī)?？梢栽龃笏阉鞯目臻g，使所求的解更逼近于最優(yōu)解，但增加了算法的時(shí)間和空間的復(fù)雜度，較小的群體規(guī)模容易陷入局部最優(yōu)。

　　2.2 分組率

　　分組率就是為了使貓群算法更加逼近真實(shí)世界貓的行為而設(shè)定的一個(gè)參數(shù)，該參數(shù)一般取一個(gè)很小的值，使少量的貓?zhí)幱诟櫮Ｊ剑ＷC大部分貓?zhí)幱谒褜つＪ健?/p>

　　2.3 個(gè)體上每個(gè)基因改變范圍

　　進(jìn)行基因的改變主要是為了增加解的多樣性。個(gè)體上基因的改變范圍太小很難產(chǎn)生新解，太大則會(huì)使得算法變成隨機(jī)搜索。

　　2.4 最大進(jìn)化次數(shù)

　　進(jìn)化次數(shù)過(guò)少，使算法還沒(méi)有取得最優(yōu)解提前結(jié)束，出現(xiàn)“早熟”現(xiàn)象；進(jìn)化次數(shù)過(guò)多，算法早已收斂到了最優(yōu)解，增加了算法的運(yùn)算時(shí)間。

3 基于貓群算法圖像聚類分析設(shè)計(jì)

　　一幅圖像中含有多個(gè)物體，在圖像中進(jìn)行聚類分析需要對(duì)不同的物體分割標(biāo)識(shí)[6]，如圖1所示。有A、B、C、D、B、C、D、A、C、D、A、B共12個(gè)待分類樣品，如何將這12個(gè)物體分成4類呢？本文介紹用貓群算法解決圖像中不同聚類問(wèn)題的實(shí)現(xiàn)方法。

　　3.1 構(gòu)造個(gè)體

　　圖1中有12個(gè)物體需要進(jìn)行聚類，假設(shè)得到的一種結(jié)果如圖2所示，樣品的分類號(hào)位于每個(gè)樣品的下方；樣品的編號(hào)在右上角且固定不變[7]，并且編號(hào)不同。

　　貓群使用符號(hào)編碼，位串長(zhǎng)度L=12，樣品所屬的類號(hào)取值范圍為1~4。因?yàn)闃悠返木幪?hào)是固定的，所以某個(gè)樣品在每個(gè)解的位置是固定的，而樣品所屬的類別隨時(shí)保持編號(hào)變化。如果編號(hào)為n，則代表第n個(gè)樣品，而第n個(gè)位所指向的值代表第n個(gè)樣品的歸屬類號(hào)[7]。

　　為了算法求解方便，設(shè)定A用數(shù)字1表示，B用數(shù)字2表示，C用數(shù)字3表示，D用數(shù)字4表示。設(shè)初始解的編碼為（1，3，2，1，4，3，2，4，3，2，4，1），如表1所示。這個(gè)解并不是最優(yōu)解，而是一種假設(shè)分類情況。

　　表1表示第1、4、12號(hào)樣品被歸類到第1類；第2、6、9號(hào)樣品被歸類到第3類；第3、7、10號(hào)樣品被歸類到第2類；第5、8、11號(hào)樣品被歸類到第4類。

　　3.2 計(jì)算適應(yīng)度

　　系統(tǒng)初始化了N只貓，算法中取分組率為0.02，根據(jù)分組率將貓分為搜尋模式和跟蹤模式下的貓，每一只貓的位置就是所求問(wèn)題的解但不一定是最優(yōu)解。

　?。?）將貓的編碼表示法轉(zhuǎn)化為類中心表示法

　　設(shè)模式樣品集為X={Xi，i=1，2，…，n}，其中Xi為D維模式向量，聚類問(wèn)題就是要找到一個(gè)劃分C={C1，C2，…，Ck}，使得總的類內(nèi)離散度之和達(dá)到最小[5]。定義式（3）：

　　其中，Cj為第j個(gè)聚類的中心，d（Xi，Cj）為樣品到對(duì)應(yīng)聚類中心的距離，聚類準(zhǔn)則函數(shù)Jc即為各類樣品到對(duì)應(yīng)聚類中心距離的總和[8]。

　　確定聚類中心后，可由最鄰近法則確定聚類的劃分。即對(duì)樣品Xi，若第j類的聚類中心Cj滿足式（4）時(shí)，則Xi屬于類j。

　　d（Xi，Cj）=mind（Xi，Cl），l=1，2，…，k（4）

　　利用貓群算法求解聚類問(wèn)題中，解集（即貓群）由每一個(gè)可行解（貓）組成。本文采用基于聚類中心集合作為貓的對(duì)應(yīng)解[9]，每一只貓的位置由k個(gè)聚類中心組成（k為已知的聚類數(shù)目）。

　　在一個(gè)具有k個(gè)聚類中心、樣品向量維數(shù)為D的聚類問(wèn)題中，貓的結(jié)構(gòu)可以由位置、速度和適應(yīng)值[1]來(lái)表示：

　　Cat（i）={location[]，velocity[]，fitness}

　　其中貓的位置通過(guò)Cat（i）.location[]=[C1，…，Cj，…，Ck]表示，Cj表示第j類的聚類中心，是一個(gè)D維矢量。貓的速度可以表示為：Cat（i）.velocity[]=[V1，…，Vj，…，Vk]；Vj表示第j個(gè)聚類中心的速度值，Vj也是一個(gè)D維矢量。

　?。?）計(jì)算適應(yīng)度

　　貓的適應(yīng)度值使用Cat.fitness來(lái)表示并且采用以下方法計(jì)算。

　?、侔凑兆钹徑▌t式（4），確定該貓的聚類劃分。

　　②重新計(jì)算聚類中心，按照式（3）計(jì)算總的類內(nèi)離散度Jc。

　?、凼褂霉紺at.fitness=1/Jc表示貓的適應(yīng)度，Jc是總的類內(nèi)離散度和。貓所代表的聚類劃分的總類間離散度越小，貓的適應(yīng)度越大。

　　3.3 位置更新

　　（1）跟蹤模式

　　在迭代過(guò)程中，用C_gd表示貓群經(jīng)歷的最優(yōu)位置和適應(yīng)度，記憶貓群的全局最優(yōu)解。C_gd={location[]，fitness}，根據(jù)式（1）和式（2）可以得到貓的速度公式如式（5）所示，位置更新公式如式（6）所示。

　　Cat（i）.velocity（j）.feature=Cat（i）.velocity（j）.feature+c*rand（Nwidth，Nwidth）*（C_gd.location（j）.feature-Cat（i）.location（j）.feature）（5）

　　Cat（i）.location（j）.feature=Cat（i）.locaiton（j）.feature+Cat（i）.velocity（j）.feature（6）

　　其中，C為一個(gè)定值，根據(jù)經(jīng)驗(yàn)一般取c=2會(huì)有比較好的效果。

　?。?）搜尋模式

　　貓復(fù)制自身副本，在自身鄰域內(nèi)加一個(gè)隨機(jī)擾動(dòng)到達(dá)新的位置，再根據(jù)適應(yīng)度函數(shù)求取適應(yīng)度最高的點(diǎn)作為貓所要移動(dòng)到的位置點(diǎn)。其副本的位置更新函數(shù)如下：

　　current_Cat（n）.location（k）.feature=current_Cat（n）.location（k）.feature+current_Cat（n）.location（k）.feature*（SRD*（rand*2-1））（6）

　　其中，SRD=0.2，即每個(gè)貓個(gè)體上的基因值變化范圍控制在0.2之內(nèi)，相當(dāng)于在自身鄰域內(nèi)搜索。

　　3.4 實(shí)現(xiàn)步驟

　?。?）設(shè)置相關(guān)參數(shù)。設(shè)定算法參數(shù)（分組率為0.02，基因變化范圍為[-0.2，0.2]，記憶池大小SMP=5），輸入最大迭代次數(shù)（MaxIter）和類中心數(shù)（centerNum）。

　?。?）貓群的初始化。對(duì)于第i只貓Cat（i），為每一個(gè)樣品隨機(jī)指派某一類作為最初的聚類劃分，并計(jì)算各個(gè)類的聚類中心，把它作為貓i的位置編碼Cat（i）.location[][1]，計(jì)算貓的適應(yīng)度Cat（i）.fitness，反復(fù)進(jìn)行，生成CatNum個(gè)貓。

　?。?）根據(jù)分組率隨機(jī)設(shè)定貓群中執(zhí)行搜尋模式的貓和跟蹤模式的貓，即將貓的模式標(biāo)識(shí)位作出相應(yīng)的改變，在搜尋模式下貓的模式標(biāo)識(shí)位為0，在跟蹤模式下貓的模式標(biāo)識(shí)位為1。

　　（4）在跟蹤模式下，貓需要記住一個(gè)貓群的全局最優(yōu)位置C_gd.location（j），對(duì)于每一只貓，根據(jù)式（5）和式（6）更新貓的速度和位置，這樣在執(zhí)行跟蹤模式下的貓總是向著最優(yōu)解的方向趨近。

　?。?）在搜尋模式下，對(duì)于每一只貓復(fù)制5份，并對(duì)這5份副本應(yīng)用變異算子，根據(jù)式（6）對(duì)它們進(jìn)行位置改變。將每個(gè)聚類中心位置進(jìn)行變異，計(jì)算位置更新后的副本的適應(yīng)度值，選取適應(yīng)度最高的點(diǎn)來(lái)代替當(dāng)前位置。

　?。?）對(duì)于每一個(gè)樣品來(lái)說(shuō)，按照如下步驟來(lái)更新適應(yīng)度值：首先確定貓的聚類中心編碼，然后根據(jù)最鄰近法則確定樣品的聚類劃分，最后根據(jù)相應(yīng)的聚類劃分重新計(jì)算新的聚類中心，更新每一只貓的適應(yīng)度值。

　?。?）計(jì)算所有貓的適應(yīng)度值，找到當(dāng)前的最優(yōu)解。

　?。?）如果達(dá)到結(jié)束條件，則算法結(jié)束，輸出全局最優(yōu)解；否則回到步驟（3）繼續(xù)執(zhí)行。

4 圖像聚類分析實(shí)驗(yàn)及性能分析

　　4.1 圖像聚類分析實(shí)驗(yàn)

　　本文在Intel（R）Core（TM）i3-2330M處理器、內(nèi)存為2 GB的計(jì)算機(jī)上使用MATLAB軟件進(jìn)行了相應(yīng)的實(shí)驗(yàn)，采用歐式距離，設(shè)定類中心數(shù)為4，最大迭代數(shù)為8，最后得到的最優(yōu)解編碼如表2所示。通過(guò)樣品值與基因值對(duì)照比較，發(fā)現(xiàn)相同的數(shù)據(jù)被歸為同一類，而且全部正確，最優(yōu)解出現(xiàn)在第4代。

　　4.2 算法性能分析

　　在同樣的實(shí)驗(yàn)條件下，使用貓群算法、蟻群算法、遺傳算法分別對(duì)50個(gè)不同圖像進(jìn)行聚類分析。3種算法的初始的最大迭代次數(shù)都為30，初始候選解個(gè)數(shù)都為50。3種算法的相關(guān)參數(shù)選擇如下：

　　貓群算法：初始化50只貓，分組率為0.1，變化域?yàn)?.2，記憶池大小為5。

　　遺傳算法：染色體的初始值設(shè)為50，給定分類中心M，選擇算子采用賭輪選擇方法，當(dāng)交叉算子為0.6、變異算子為0.05時(shí)產(chǎn)生下一代。

　　蟻群算法：初始化50只螞蟻，信息素蒸發(fā)參數(shù)為0.9，轉(zhuǎn)換規(guī)則參數(shù)為0.5。

　　使用3種算法對(duì)50組圖像進(jìn)行10次實(shí)驗(yàn)，統(tǒng)計(jì)平均最優(yōu)解出現(xiàn)代數(shù)（如圖3所示）和平均準(zhǔn)確率（如圖4所示）。

　　從圖3和圖4可以看出，使用貓群算法在收斂速度和算法性能上要優(yōu)于后兩者，并且達(dá)到了預(yù)期分類效果。

5 結(jié)論

　　貓群算法具有良好的局部搜索和全局搜索能力，算法控制參數(shù)較少，通過(guò)搜索模式和追蹤模式的相互結(jié)合，大大提高了搜索優(yōu)良解的可能性和搜索效率，較其他算法容易實(shí)現(xiàn)，收斂速度快，具有較高的運(yùn)算速度，易于與其他算法結(jié)合。該算法主要通過(guò)迭代過(guò)程來(lái)不斷地尋找當(dāng)前最優(yōu)解，在每一次迭代過(guò)程中貓所執(zhí)行的模式是隨機(jī)的，在一定程度上提高了算法的全局搜索能力。實(shí)驗(yàn)表明，貓群算法在圖像聚類問(wèn)題中比蟻群算法和遺傳算法更有效、更加準(zhǔn)確。貓群算法目前主要應(yīng)用于函數(shù)優(yōu)化、圖像分類等領(lǐng)域中，具有很好的理論探討空間和廣闊的應(yīng)用前景。

　　參考文獻(xiàn)

　　[1] 王光彪，楊淑瑩，馮帆，等.基于貓群算法的圖像分類研究[J].天津理工大學(xué)學(xué)報(bào)，2011，27（5）：35-39.

　　[2] 范凱波.基于幾何特征的車輛目標(biāo)分類研究[D].天津：天津理工大學(xué)，2011.

　　[3] 王媛妮.順序形態(tài)邊緣檢測(cè)及分水嶺圖像分割研究[D].武漢：武漢大學(xué)，2010.

　　[4] 吳偉林，周永華.基于差分演化與貓群算法融合的群體智能算法[J].計(jì)算機(jī)技術(shù)與自動(dòng)化，2014，33（12）：78-83.

　　[5] 陳彬，駱魯秦，王巖.基于粒子群聚類算法的雷達(dá)信號(hào)分選[J].航天電子對(duì)抗，2009，24（5）：25-28.

　　[6] 張忠華，楊淑瑩.基于遺傳算法的聚類設(shè)計(jì)[R].南寧：中國(guó)高科技產(chǎn)業(yè)化研究會(huì)信號(hào)處理產(chǎn)業(yè)化分會(huì)，2008.

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

　　[8] 陳建成，屠昂燕.基于粒子群算法的織物組織結(jié)構(gòu)識(shí)別[J].湖北第二師范學(xué)院學(xué)報(bào)，2010，27（2）：15-16.

　　[9] 朱燕飛，胡夏云，唐雄民.基于群算法的過(guò)程參量聚類研究[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（26）：36-38.