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

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

0 引言

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

1 貓群算法的基本原理

　　貓群算法是通過觀察貓在日常生活中的行為動作提出的群體智能仿生算法，貓即為待求優(yōu)化問題的可行解[1]。該算法將貓的行為分為搜尋模式和跟蹤模式，在搜尋模式中貓?zhí)幱谛菹?、張望的狀態(tài)；而在跟蹤模式中貓在跟蹤動態(tài)目標。在整個貓群中，絕大多數(shù)貓執(zhí)行搜尋模式，而只有少量的貓?zhí)幱诟櫮Ｊ絒2]。在搜尋模式下，記憶池記錄了貓所搜尋的鄰域位置點，記憶池的大小代表貓能夠搜索的地點數(shù)量，通過變異算子，改變原值，使記憶池存儲了貓在自身的鄰域內(nèi)能夠搜索的新地點，貓根據(jù)保存在記憶池中適應度值的大小選擇一個最好的位置點。在跟蹤模式下，每一次迭代中，貓將跟蹤一個“極值”來更新自己，這個“極值”是目前整個種群找到的最優(yōu)解[3]，使得貓的移動方向向著全局最優(yōu)解逼近，利用全局最優(yōu)的位置來更新貓的位置，具有向“他人”學習的機制。然后混合成為一個群體，根據(jù)分組率，隨機地將貓群分為搜尋模式和跟蹤模式兩種模式，直到算法執(zhí)行完預定的種群進化次數(shù)結束。

　　1.1 搜尋模式

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

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

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

　?。?）執(zhí)行選擇算子。復制貓的自身位置，把新的位置副本保存在記憶池中，從中選擇適應度值最高的新位置來代替當前貓的位置。

　　1.2 跟蹤模式

　　貓進入跟蹤模式后，貓群算法即類似于粒子群算法，采用速度-位移模式來移動每一位基因的值。貓的跟蹤模式可以通過以下兩步來描述。

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

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

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

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

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

2 控制參數(shù)選擇

　　2.1 群體規(guī)模

　　較大的群體規(guī)模可以增大搜索的空間，使所求的解更逼近于最優(yōu)解，但增加了算法的時間和空間的復雜度，較小的群體規(guī)模容易陷入局部最優(yōu)。

　　2.2 分組率

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

　　2.3 個體上每個基因改變范圍

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

　　2.4 最大進化次數(shù)

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

3 基于貓群算法圖像聚類分析設計

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

　　3.1 構造個體

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

　　貓群使用符號編碼，位串長度L=12，樣品所屬的類號取值范圍為1~4。因為樣品的編號是固定的，所以某個樣品在每個解的位置是固定的，而樣品所屬的類別隨時保持編號變化。如果編號為n，則代表第n個樣品，而第n個位所指向的值代表第n個樣品的歸屬類號[7]。

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

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

　　3.2 計算適應度

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

　?。?）將貓的編碼表示法轉化為類中心表示法

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

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

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

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

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

　　在一個具有k個聚類中心、樣品向量維數(shù)為D的聚類問題中，貓的結構可以由位置、速度和適應值[1]來表示：

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

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

　?。?）計算適應度

　　貓的適應度值使用Cat.fitness來表示并且采用以下方法計算。

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

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

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

　　3.3 位置更新

　　（1）跟蹤模式

　　在迭代過程中，用C_gd表示貓群經(jīng)歷的最優(yōu)位置和適應度，記憶貓群的全局最優(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為一個定值，根據(jù)經(jīng)驗一般取c=2會有比較好的效果。

　?。?）搜尋模式

　　貓復制自身副本，在自身鄰域內(nèi)加一個隨機擾動到達新的位置，再根據(jù)適應度函數(shù)求取適應度最高的點作為貓所要移動到的位置點。其副本的位置更新函數(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，即每個貓個體上的基因值變化范圍控制在0.2之內(nèi)，相當于在自身鄰域內(nèi)搜索。

　　3.4 實現(xiàn)步驟

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

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

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

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

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

　　（6）對于每一個樣品來說，按照如下步驟來更新適應度值：首先確定貓的聚類中心編碼，然后根據(jù)最鄰近法則確定樣品的聚類劃分，最后根據(jù)相應的聚類劃分重新計算新的聚類中心，更新每一只貓的適應度值。

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

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

4 圖像聚類分析實驗及性能分析

　　4.1 圖像聚類分析實驗

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

　　4.2 算法性能分析

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

　　貓群算法：初始化50只貓，分組率為0.1，變化域為0.2，記憶池大小為5。

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

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

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

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

5 結論

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

　　參考文獻

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

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

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

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

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

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

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

　　[8] 陳建成，屠昂燕.基于粒子群算法的織物組織結構識別[J].湖北第二師范學院學報，2010，27（2）：15-16.

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