董袁泉（沙洲職業(yè)工學(xué)院，江蘇 張家港 215600）

貓群算法仿生計(jì)算在圖像聚類分析中的應(yīng)用*

董袁泉
（沙洲職業(yè)工學(xué)院，江蘇 張家港 215600）

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

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

0 引言

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

1 貓群算法的基本原理

貓群算法是通過觀察貓?jiān)谌粘Ｉ钪械男袨閯?dòng)作提出的群體智能仿生算法，貓即為待求優(yōu)化問題的可行解［1］。該算法將貓的行為分為搜尋模式和跟蹤模式，在搜尋模式中貓?zhí)幱谛菹?、張望的狀態(tài)；而在跟蹤模式中貓?jiān)诟檮?dòng)態(tài)目標(biāo)。在整個(gè)貓群中，絕大多數(shù)貓執(zhí)行搜尋模式，而只有少量的貓?zhí)幱诟櫮Ｊ剑?］。在搜尋模式下，記憶池記錄了貓所搜尋的鄰域位置點(diǎn)，記憶池的大小代表貓能夠搜索的地點(diǎn)數(shù)量，通過變異算子，改變原值，使記憶池存儲了貓?jiān)谧陨淼泥徲騼?nèi)能夠搜索的新地點(diǎn)，貓根據(jù)保存在記憶池中適應(yīng)度值的大小選擇一個(gè)最好的位置點(diǎn)。在跟蹤模式下，每一次迭代中，貓將跟蹤一個(gè)“極值”來更新自己，這個(gè)“極值”是目前整個(gè)種群找到的最優(yōu)解［3］，使得貓的移動(dòng)方向向著全局最優(yōu)解逼近，利用全局最優(yōu)的位置來更新貓的位置，具有向“他人”學(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；在基因總長度的范圍內(nèi)隨機(jī)挑選一個(gè)值作為個(gè)體上需要改變的基因個(gè)數(shù)。搜尋模式可分為如下3個(gè)步驟：

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

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

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

1.2 跟蹤模式

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

（1）速度-位移模型操作算子

整個(gè)貓群經(jīng)歷的最好位置，即為目前得到的最優(yōu)解［1］，記做。每個(gè)貓都有一個(gè)速度，記做…，｝，定義式（1）：

t）代表的是第 k只貓Xk（t）所處位置的第d個(gè)分量；c是一個(gè)常量，其值需要根據(jù)不同的問題而定；rand是一個(gè)隨機(jī)數(shù)，它的取值范圍是0～1。

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

2 控制參數(shù)選擇

2.1 群體規(guī)模

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

2.2 分組率

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

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

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

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

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

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

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

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

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

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

圖1待分類的樣品

圖2待測樣品的編號

為了算法求解方便，設(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表示第1、4、12號樣品被歸類到第1類；第2、6、9號樣品被歸類到第3類；第 3、7、10號樣品被歸類到第2類；第5、8、11號樣品被歸類到第4類。

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

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

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

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

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

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

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

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

Cat（i）=｛location［］，velocity［］，fitness｝

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

（2）計(jì)算適應(yīng)度

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

①按照最鄰近法則式（4），確定該貓的聚類劃分。

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

③使用公式 Cat.fitness=1/Jc表示貓的適應(yīng)度，Jc是總的類內(nèi)離散度和。貓所代表的聚類劃分的總類間離散度越小，貓的適應(yīng)度越大。

3.3 位置更新

（1）跟蹤模式

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

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

（2）搜尋模式

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

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

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

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

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

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

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

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

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

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

（8）如果達(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所示。通過樣品值與基因值對照比較，發(fā)現(xiàn)相同的數(shù)據(jù)被歸為同一類，而且全部正確，最優(yōu)解出現(xiàn)在第4代。

表2 最優(yōu)解

4.2 算法性能分析

在同樣的實(shí)驗(yàn)條件下，使用貓群算法、蟻群算法、遺傳算法分別對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種算法對50組圖像進(jìn)行10次實(shí)驗(yàn)，統(tǒng)計(jì)平均最優(yōu)解出現(xiàn)代數(shù)（如圖3所示）和平均準(zhǔn)確率（如圖4所示）。

圖3 最優(yōu)解出現(xiàn)的代數(shù)

圖4 分類出現(xiàn)的準(zhǔn)確率

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

5 結(jié)論

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

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

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

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

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

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

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

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

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

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

圖6 連續(xù)航路識別效果圖

4 結(jié)論

本文提出了利用卷積神經(jīng)網(wǎng)絡(luò)直接對坐標(biāo)數(shù)據(jù)進(jìn)行特征提取從而進(jìn)行機(jī)動(dòng)模式分類的算法。針對航跡機(jī)動(dòng)模式難以分割的實(shí)際情況，提出了滑動(dòng)固定時(shí)間窗口的模式識別方法，并通過仿真實(shí)驗(yàn)確定了機(jī)動(dòng)模式識別的卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)。實(shí)驗(yàn)結(jié)果表明，構(gòu)造好的卷積網(wǎng)絡(luò)對航跡類型識別率達(dá)98.4％，并且在結(jié)合機(jī)動(dòng)觸發(fā)點(diǎn)后，對連續(xù)航跡識別取得了良好效果，為空中目標(biāo)戰(zhàn)術(shù)機(jī)動(dòng)模式識別提供了一個(gè)可行的方法。

參考文獻(xiàn)

［1］丁全心.現(xiàn)代空戰(zhàn)中的戰(zhàn)術(shù)輔助決策技術(shù)［J］.電光與控制，2009，16（12）：1-4.

［2］李國芳，王力.基于改進(jìn) Gamma和改進(jìn) BP算法的人臉識別研究［J］.微型機(jī)與應(yīng)用，2015，34（4）：49-51.

［3］蘇春梅，馮朝陽，王力軍.通用飛機(jī)航跡生成技術(shù)［J］.兵工自動(dòng)化，2010，29（12）：20-25.

［4］杜永翔，林新.態(tài)勢推演系統(tǒng)在飛機(jī)過渡段航跡規(guī)劃算法研究［J］.系統(tǒng)仿真學(xué)報(bào)，2013，25（8）：1721-1725.

［5］張宏.巡航導(dǎo)彈的作戰(zhàn)使用特點(diǎn)及對抗途徑［J］.艦船電子對抗，2009，32（4）：19-24.

［6］LECUN Y，BENGIO Y.Convolutional networks for images，speech，and time-series［C］.The Handbook of Brain Theory and Neural Networks，1995：255-258

［7］BOUVRIE J.Notes on convolutional neural networks［R］.Technical Report，2006

［8］KRIZHEVSKY A，SUTSKEVER I，HINTON G E.Imagenet classification with deep convolutional neural networks［C］.Advances in Neural Information Processing Systems，2012：1097-1105.

（收稿日期：2015-08-21）

作者簡介：

鄭昌艷（1990-），通信作者，女，碩士研究生，主要研究方向：目標(biāo)跟蹤、機(jī)器學(xué)習(xí)。E-mail：echoaimaomao@163.com。

梅衛(wèi)（1971-），男，博士，副教授，主要研究方向：目標(biāo)跟蹤、不確定性理論、機(jī)器學(xué)習(xí)。

Application of cat sw arm algorithm in image clustering analysis

Dong Yuanquan
（Shazhou Professional Institute of Technology，Zhangjiagang 215600，China）

Traditional optimization algorithm in image clustering analysis has high complexity，so it′s easy to fall into the problem of local optimal solution.We put forward the cat swarm algorithm solving image clustering problem.This algorithm transfers information by grouping and hybrid strategy mechanism，updates itself using the cat in the memory of global optimal solution and improves the search ability.It has searching mode and tracking mode.We discuss cat group velocity and position updating formulas，and explain the concrete steps of solving the image clustering analysis problems.Through experiments，the validity and accuracy are verified.

cat swarm algorithm；swarm intelligence；combination optimization；image clustering

TP311

A

1674-7720（2015）22-0053-04

董袁泉.貓群算法仿生計(jì)算在圖像聚類分析中的應(yīng)用［J］.微型機(jī)與應(yīng)用，2015，34（22）：53-56，60.

2015-07-26）

董袁泉（1974-），男，工程碩士，講師，主要研究方向：數(shù)據(jù)庫及分布式網(wǎng)絡(luò)應(yīng)用開發(fā)。

國家自然科學(xué)基金項(xiàng)目（41501461）