基于細菌覓食優(yōu)化算法的圖像聚類方法研究

馮 帆，王博凱，楊淑瑩

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

基于細菌覓食優(yōu)化算法的圖像聚類方法研究

馮 帆，王博凱，楊淑瑩

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

利用細菌覓食優(yōu)化算法研究圖像聚類問題，采用群體智能模式實現(xiàn)問題解的搜索.首先提取圖像特征以確定解的編碼形式，初始化種群，在此基礎(chǔ)上利用細菌覓食優(yōu)化算法的細菌遷徙算子、繁殖算子和趨化算子實現(xiàn)群體內(nèi)個體之間的相互合作和競爭，提高了算法的搜索能力，實驗證明該算法具有較強的適應(yīng)性和魯棒性.

細菌覓食優(yōu)化算法；群體智能；優(yōu)化算法

細菌覓食優(yōu)化算法（Bacterial Foraging Optimization，BFO）是Passino在2002年基于大腸桿菌在人體腸道內(nèi)的覓食行為提出的一種新型仿生類群體智能算法［1］.與其他進化算法相比，細菌覓食優(yōu)化算法具有較強的適應(yīng)性和魯棒性［2］，其良好的并行性提高了算法的性能和效率，算法簡單、靈活，可與其他各種算法相結(jié)合產(chǎn)生新的進化優(yōu)化算法.由于具有群體智能算法的特點以及較強的搜索能力和易跳出局部極小值等優(yōu)點，細菌覓食優(yōu)化算法被廣泛應(yīng)用于各種群智能識別方面的問題［3］.本研究將細菌覓食優(yōu)化算法應(yīng)用于圖像聚類問題，并通過仿真實驗檢驗算法性能.

1 細菌覓食優(yōu)化算法

大腸桿菌的覓食行為可分為以下幾個過程［4］：

（1）尋找可能存在食物源的區(qū)域.

（2）通過先驗知識判斷是否進入該覓食區(qū)域.

（3）消耗掉一定量的食物或覓食區(qū)域環(huán)境變惡劣等不適合生存的條件出現(xiàn)后，細菌死亡或遷移到另一個適合的覓食區(qū)域.

細菌覓食優(yōu)化算法是根據(jù)以上3個過程提出的一種仿生隨機搜索算法，與其他的群智能算法相同，細菌覓食優(yōu)化算法在搜索最優(yōu)解時，首先要對所求問題的解進行編碼，然后根據(jù)算法中細菌的行為進行信息交流和更新，最終得到最優(yōu)解.

2 算法的行為算子

在BFO模型中，優(yōu)化問題的解對應(yīng)搜索空間中細菌的狀態(tài)，即優(yōu)化函數(shù)適應(yīng)值.BFO算法主要依靠自身特有的趨化（Chemo taxis）、復(fù)制（Repro－duction）和遷徙（Elimination－dispersal）3種基礎(chǔ)算子［5］進行細菌個體位置的更新和群體最優(yōu)位置的搜索，進而實現(xiàn)種群的進化.

2.1 趨化算子

細菌向有利于自身的環(huán)境（食物源）靠近，在算法中表現(xiàn)為細菌位置的改善.設(shè)qi（j，k，l）為細菌個體i當(dāng)前的位置，其中j表示細菌的第j代趨化算子，k表示細菌的第k代復(fù)制算子，l表示細菌的第l代遷徙算子，細菌覓食優(yōu)化算法中細菌的位置按照θi（j＋1，k，l）＝θi（j，k，l）＋C（i）φ（j）進行調(diào)整，其中，C（i）表示細菌每次前進的步長，φ（j）表示細菌隨機翻滾的方向.

細菌位置更新過程中，每個細菌首先向一個隨機的方向前進一個步長，判斷其適應(yīng)度是否得到改善.如果適應(yīng)度得到改善，就按此方向繼續(xù)前進，直到適應(yīng)度不再改善或達到最大的前進次數(shù)；如果按此方向前進一個步長后適應(yīng)度值沒有得到改善，就隨機向另一個方向前進一個步長，直到每只細菌都完成預(yù)定的趨化算子次數(shù)后執(zhí)行復(fù)制算子.

2.2 復(fù)制算子

適應(yīng)環(huán)境的細菌復(fù)制自身在算法中表現(xiàn)為依據(jù)適應(yīng)度值對執(zhí)行完趨化算子后的種群進行排序，適應(yīng)度值較低的半數(shù)細菌個體死亡，適應(yīng)度值高的半數(shù)細菌個體復(fù)制自身，生成新的群體.然后新產(chǎn)生的群體再次循環(huán)執(zhí)行趨化算子和復(fù)制算子，直至群體執(zhí)行完預(yù)定的復(fù)制算子次數(shù)后執(zhí)行遷徙算子.

2.3 遷徙算子

在環(huán)境惡化的情況下，細菌死亡或者移動到另一個有利環(huán)境在算法中表現(xiàn)為某些細菌一定概率的死亡并隨機產(chǎn)生新位置的細菌.如果種群中的某個個體滿足遷徙算子發(fā)生的概率，則這個細菌個體死亡，并隨機在解空間的任意位置生成一個新的個體.整個種群執(zhí)行完一次遷徙算子后，細菌再次循環(huán)執(zhí)行趨化算子、復(fù)制算子和遷徙算子，直到執(zhí)行完預(yù)定的遷徙算子次數(shù)，種群更新并輸出最優(yōu)解，算法結(jié)束.

在細菌覓食優(yōu)化算法的3種行為算子中，趨化算子是BFO算法的核心部分，決定了搜尋食物源時細菌位置的改變方式以及細菌能否找到食物源，對算法的收斂性和優(yōu)劣具有極其重要的影響.復(fù)制算子保證了細菌種群總體優(yōu)良性能的提高，使群體向最優(yōu)的方向移動，有利于達到全局最優(yōu)［6］.遷徙算子產(chǎn)生的新個體與滅亡的個體一般具有不同的位置，即不同的覓食能力，它可對趨化算子產(chǎn)生一定促進作用，因為遷徙操作隨機生成的新個體可能更靠近食物源區(qū)域，這樣更有利于趨化算子跳出局部最優(yōu)解并尋找到全局最優(yōu)解.

3 基于細菌覓食優(yōu)化算法的圖像聚類設(shè)計

3.1 特征提取

以含有9個手寫字母的圖像樣品為例對基于細菌覓食優(yōu)化算法的圖像聚類方法進行驗證，待測樣品如圖1所示.圖1中，字母右上角的數(shù)字為每個樣品的編號.

圖1 待測樣品圖Fig.1 Samples for clustering

對于模式識別的聚類問題，特征提取是十分關(guān)鍵的重要環(huán)節(jié).采用圖像處理方法［7］將含有9個樣本的待測樣品圖像進行分割，分別將9個樣品所在的外切矩形區(qū)域平均分成7×7個矩形子區(qū)域，并以每個子區(qū)域中黑像素占子區(qū)域總像素個數(shù)的百分比作為特征值.

3.2 確定解的編碼形式

每種聚類方案都對應(yīng)一個解，所有解均采用十進制編碼，向量總長度為9位.首先，隨機生成初始解，如（2，3，1，1，2，1，3，3，2，2，1，3），即第3、4、6和11個樣品被分到第1類，第1、5、9和10個樣品被分到第2類，第2、7、8和12個樣品被分到第3類.

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

設(shè)樣品集為X＝｛Xi，i＝1，2，…，n｝，其中Xi為d維（d＝49）特征向量，需要算法求解的問題是找到一個可使類內(nèi)距離總和達到最小的聚類方案.

式（1）中：Cj表示第j個聚類中心；d（Xi，Cj）為樣品到對應(yīng)聚類中心的距離；Jc為各類樣品到對應(yīng)聚類中心的距離之和.

個體的適應(yīng)度值為實數(shù)，可表示為

由式（2）可知，個體所代表的劃分方案的類間距離之和Jc越小，個體的適應(yīng)度fitness越大，聚類結(jié)果越準(zhǔn)確.

3.4 細菌覓食優(yōu)化算法的實現(xiàn)步驟

（1）隨機初始化種群，包括種群大小N和聚類數(shù)目.對于第i只細菌，先將每個樣品隨機指派為某一類作為最初的聚類劃分，并計算各類的聚類中心作為細菌i的位置編碼，計算細菌的適應(yīng)度值，反復(fù)進行生成N只細菌，并記錄最優(yōu)細菌.

（2）外層循環(huán)細菌執(zhí)行遷徙算子.

（3）中層循環(huán)細菌執(zhí)行繁殖算子.

（4）內(nèi)層循環(huán)細菌執(zhí)行趨化算子，根據(jù)式（1）更新細菌個體.

（5）如果沒有達到預(yù)定的趨化算子次數(shù)，則重復(fù)執(zhí)行（4）.

（6）如果沒有達到預(yù)定的繁殖算子次數(shù)，重復(fù)執(zhí)行（3）.

（7）如果沒有達到預(yù)定的遷徙算子次數(shù)，重復(fù)執(zhí)行（2）；如果達到最大遷徙算子次數(shù)，則循環(huán)結(jié)束，更新并輸出最優(yōu)解.

4 仿真實驗

利用細菌覓食優(yōu)化算法得到的聚類方案如圖2所示，最優(yōu)解如表1所示，可以發(fā)現(xiàn)相同的數(shù)字被歸為一類，實現(xiàn)了聚類的預(yù)期效果.

圖2 最優(yōu)聚類結(jié)果Fig.2 Result of optimal clustering

表1 最優(yōu)解Tab.1 Optimal solution

5 結(jié)論

本研究分析了細菌覓食優(yōu)化算法的原理和仿生機制，并將其應(yīng)用于圖像聚類問題的求解，仿真實驗結(jié)果證明基于細菌覓食優(yōu)化算法的圖像聚類方法具有較強的可行性與準(zhǔn)確性，為進一步的算法優(yōu)化研究及其在其他領(lǐng)域的應(yīng)用奠定了基礎(chǔ).

［1］ MIILER S D，MARCHETTE J，AIRAGHIEL S.Optimization based on bacterial chemotaxis［J］.Transactions Evolutionary Computation，2002，6（1）：17－19.

［2］ 儲穎，邵子博，糜華，等.細菌覓食算法在圖像壓縮中的應(yīng)用［J］.深圳大學(xué)學(xué)報：理工版，2008，25（2）：153－157.

［3］ MISHRA S.Bacterial foraging technique－based optimized active power filter for Load Compensation［J］.IEEE Transactions on Power Delivery，2007，22（1）：457－465.

［4］ LI W W，WANG H，ZOU Z J，et al.Function optimization method based on bacterial colony chemotaxis［J］.Journal of Circuit's and System，2005，10（1）：58－63.

［5］ PASSINO K M.Biomimicry of bacterial for aging or distributed optimization and control［J］.Control System Magazine，2002，22（3）：52－67.

［6］ 麥雄發(fā)，李玲.混合PSO的快速細菌覓食算法［J］.廣西師范學(xué)院學(xué)報：自然科學(xué)版，2010（4）：91－94.

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

Research on image cluster based on bacterial foraging optimization algorithm

FENGFan，WANGBo－kai，YANGShu－ying

（Key Laboratory of Intelligence Computing and Novel Software Technology，Tianjin University of Technology，Tianjin 300384，China）

Bacterial foraging optimization algorithm is used for researching image clustering problem.Swarm intelligent model is used for achieving the search for the solution.Firstly，image characteristic is extracted to determine the coding solution form and the population is initialized.Then migrating operator，breeding operator and chemotaxis operator of the bacterial foraging optimization algorithm are employed to realize mutual cooperation and competition among individuals within the group，and the search capability of the algorithm is improved.Finally，the results of experiment show that the proposed algorithm is of strong adaptability and robustness.

bacterial foraging optimization algorithm；swarm intelligence；optimization algorithm

TP311

A

1671－1114（2012）02－0056－03

2012－01－10

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

馮 帆（1987－），男，碩士研究生.

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

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