改進(jìn)人工蜂群優(yōu)化的K均值圖像分割算法

李海洋 何紅洲

文章編號： 2095-2163（2018）03-0045-05中圖分類號： 文獻(xiàn)標(biāo)志碼： A

摘要： 關(guān)鍵詞： （School of Information Engineering， Mianyang Normal University， Mianyang Sichuan 621000， China）

Abstract： In the image segmentation， K-means clustering algorithm has the disadvantage of low accuracy and poor stability. The hybrid algorithm based on artificial bee colony and K-mean tend to be too inefficient to meet the application requirements. To cure the above problems， a new image segmentation algorithm called IABC-K is proposed in this study. The artificial bee colony algorithm is improved according to its different characteristics in honey source renewal and mining. An adaptive neighborhood search mechanism associated with optimal fitness is adopted to improve the speed of honey source renewal. A linear decreasing neighborhood search strategy associated with optimal fitness is adopted to improve the quality of honey source mining. Experimental results show that IABC-K algorithm is superior to other similar algorithms in terms of quality， efficiency and stability. IABC-K algorithm has better image segmentation quality and higher image segmentation efficiency. It can be applied in image processing field with high quality and performance requirements.

Key words：

基金項目：

作者簡介：

收稿日期： 引言

K均值聚類算法是聚類問題研究的經(jīng)典算法，常應(yīng)用于圖像分割[1]。但K均值聚類算法的聚類結(jié)果往往依賴于初始值的選取，圖像分割質(zhì)量較低[2]。針對K均值聚類算法的缺點，很多研究人員采用進(jìn)化技術(shù)對K均值聚類算法進(jìn)行優(yōu)化。進(jìn)化技術(shù)中，主要包括有：遺傳算法[3]、粒子群優(yōu)化[4-5]、人工蜂群優(yōu)化[6]（artificial bee colony， ABC）等。其中，ABC算法性能優(yōu)異，全局尋優(yōu)能力強(qiáng)，能比遺傳算法、粒子群優(yōu)化算法更快收斂于最優(yōu)解[7]。

在ABC算法優(yōu)化K均值聚類的研究中，梁冰等[8]將與當(dāng)前維度最優(yōu)解差值的變化率作為權(quán)值，對蜜源的搜索公式進(jìn)行了改進(jìn)，提高了算法的魯棒性和聚類精度。宋錦等[9]修改了ABC算法對蜜源的更新方法，獲得了較好的圖像分割質(zhì)量。Shokouhifar等[10]利用ABC算法來調(diào)整模糊規(guī)則，使算法具有自適應(yīng)特性。Cong等[11]通過變異操作增強(qiáng)了ABC算法的搜索能力，提高了算法的聚類質(zhì)量。Bose等[12] 使用一種模糊隸屬函數(shù)來搜索ABC算法最優(yōu)解，用以初始化K均值聚類中心，使算法在收斂性、時間復(fù)雜度、魯棒性和圖像分割精度方面表現(xiàn)較好。趙文昌等[13]利用距離最大最小乘積方法對ABC種群進(jìn)行初始化，并采用自適應(yīng)搜索參數(shù)調(diào)整鄰域搜索范圍，得到了較好的圖像分割效果。但是，上述混合聚類算法大都針對特定條件，并存在穩(wěn)定性欠佳的問題，不能達(dá)到聚類質(zhì)量和聚類效率同時提高的目的，因而難以應(yīng)用在分割質(zhì)量和分割效率要求較高的圖像處理領(lǐng)域。

基于此，本研究提出一種新的ABC和K均值聚類的圖像分割算法IABC-K。IABC-K算法分別改進(jìn)了ABC算法的蜜源更新和蜜源開采公式，使其鄰域搜索策略更符合不同進(jìn)化階段的要求，從而使算法獲得了穩(wěn)定性強(qiáng)、分割質(zhì)量好、分割效率高的出色性能表現(xiàn)。

1相關(guān)算法

1.1K均值聚類算法

K均值聚類算法是從聚類樣本X=xi∈Rd，i=1，2，…，n中隨機(jī)選取k個聚類中心a1，a2，…，ak，將xi按最小距離分配到k個簇，其目標(biāo)函數(shù)如式（1）所示：J=∑kj=1∑x∈Cjx-aj2（1）其中，x是每個簇內(nèi)的樣本。

當(dāng)目標(biāo)函數(shù)最小時，可根據(jù)式（2）更新k個聚類中心。數(shù)學(xué)公式具體如下：Cj=1N∑x∈Cjx（2）其中，N是第j個簇包含的樣本數(shù)。

通過不斷迭代，當(dāng)k個簇的中心都不再變化或滿足迭代條件時，可得到聚類結(jié)果。

1.2ABC算法

ABC算法通過模擬蜂群分工合作尋找最優(yōu)蜜源的過程來求解優(yōu)化問題，是一種基于蜜蜂群體智能的優(yōu)化算法[14]。ABC算法求解優(yōu)化問題的步驟如下：

步驟1種群的初始化。樣本集X={xi∈Rd，i=1，2，…，n}表示待求解的優(yōu)化問題，xi為d維向量；設(shè)算法最大迭代次數(shù)為MCN；每個蜜源的最大開采次數(shù)為limit。

步驟2隨機(jī)選擇蜜源，用來表示初始可行解，公式表述可見如下：Xji=Xjmin+rand0，1（Xjmax-Xjmin）（3）其中，j∈1，2，…，d；xji表示第i個可行解的第j維分量；rand0，1是區(qū)間0，1內(nèi)均勻分布的隨機(jī)數(shù)。

步驟3引領(lǐng)蜂在其對應(yīng)的蜜源當(dāng)前位置附近鄰域內(nèi)對蜜源進(jìn)行更新，研究推得數(shù)學(xué)公式如下：Vji=Xji+φjiVji-Vjk （4）其中，k∈1，2，…，n，且k≠i；φji為區(qū)間-1，1內(nèi)均勻分布的隨機(jī)數(shù)，用來控制鄰域搜索范圍。

步驟4如果蜜源Vji=v1i，v2i，…，vdi的適應(yīng)度優(yōu)于蜜源Xji，則采用貪婪選擇法用Vji代替Xji；如果蜜源Xji經(jīng)過limit次開采后都沒有更新，說明該蜜源質(zhì)量較差，則蜜源Xji應(yīng)被放棄，其對應(yīng)的引領(lǐng)蜂轉(zhuǎn)化為偵察蜂，并根據(jù)式（3）隨機(jī)選擇新蜜源。

步驟5在每個引領(lǐng)蜂更新蜜源后，跟隨蜂在引領(lǐng)蜂種群內(nèi)選擇一只引領(lǐng)蜂，跟隨其前往蜜源采蜜。跟隨蜂選擇引領(lǐng)蜂的概率計算如式（5）所示：pi=fi/∑ni=1fi（5）其中，fi為第i個蜜源適應(yīng)度值。

然后，跟隨蜂在被選蜜源位置附近采用式（4）開采蜜源。

步驟6若算法當(dāng)前迭代次數(shù)t

2ABC算法改進(jìn)

在ABC算法中，引領(lǐng)蜂和跟隨蜂共用式（4） 實現(xiàn)蜜源的更新和開采，而式（4）中的鄰域搜索范圍控制系數(shù)φji是一個在區(qū)間[-1，1]內(nèi)均勻分布的隨機(jī)數(shù)，會對ABC算法性能產(chǎn)生影響，使算法收斂速度過慢或求解精度不高[15]。當(dāng)ABC算法與K均值聚類算法相混合后，ABC算法的這種影響會被放大并傳導(dǎo)至混合算法，造成混合算法整體性能下降。本研究根據(jù)ABC算法不同階段特點，對ABC算法的蜜源更新及開采策略進(jìn)行了改進(jìn)，并設(shè)計給出了改進(jìn)ABC算法與K均值混合算法步驟。

2.1蜜源更新策略

在ABC算法中，蜜源更新目的是通過適應(yīng)度函數(shù)值判斷可行解的優(yōu)劣， 保持每個可行解優(yōu)良性質(zhì)。這一階段，算法應(yīng)盡量避免陷入局部最優(yōu)，實現(xiàn)蜜源快速更新，才能獲得算法高效性。但式（4）中φji是隨機(jī)產(chǎn)生的。如果引領(lǐng)蜂所對應(yīng)蜜源為優(yōu)質(zhì)蜜源而隨機(jī)產(chǎn)生的φji較小，就會使該引領(lǐng)蜂尋優(yōu)能力下降，并不斷放棄優(yōu)質(zhì)蜜源；如果引領(lǐng)蜂所對應(yīng)蜜源為劣質(zhì)蜜源而隨機(jī)產(chǎn)生的φji較大，就會擴(kuò)大該引領(lǐng)蜂的鄰域搜索范圍，使算法遲遲不能收斂。本研究對原算法的蜜源搜索公式做出了改進(jìn)，采用與最優(yōu)適應(yīng)度關(guān)聯(lián)策略，在蜜源更新過程中加入搜索鄰域優(yōu)良個體信息，能使算法快速收斂于最優(yōu)解。研究得到這一過程公式可表示為：Vji=Xji+φjifibest（Vji-Vjk）（6）其中，fibest是第i個蜜源的第j維分量的最優(yōu)適應(yīng)度值。

同時，為避免算法陷入局部最優(yōu)，本研究采用了自適應(yīng)策略，對φji的取值也提供了一定了改進(jìn)，研究中將使用如下數(shù)學(xué)公式：

φji=φmin+φmax-φminfi-fminfavg-fminfi≤fmin

φmaxfi>fmin （7）

其中，φmin和φmax為常數(shù)，用以控制鄰域搜索的最小、最大范圍；favg和fmin為當(dāng)前所有蜜源的平均適應(yīng)度和最小適應(yīng)度。

采用以上最優(yōu)適應(yīng)度關(guān)聯(lián)的自適應(yīng)搜索策略后，當(dāng)fi與fibest相差較大時，可通過式（7）自動增大φji，避免算法陷入局部最優(yōu)，使算法快速逼近最優(yōu)解；當(dāng)fi與fibest相差較小時，可通過式（7）自動減小φji，提高算法局部尋優(yōu)能力，實現(xiàn)精細(xì)搜索。

2.2線性遞減的蜜源開采策略

在ABC算法中，蜜源開采的目的是在每個可行解中繼續(xù)尋優(yōu)，找到最優(yōu)解。在蜜源開采初期，算法應(yīng)采用較大的開采系數(shù)，從而保持較強(qiáng)的全局尋優(yōu)能力，快速逼近最優(yōu)解；在蜜源開采后期，算法應(yīng)采用較小的開采系數(shù)，實現(xiàn)細(xì)致的局部尋優(yōu)。但式（4）中開采系數(shù)φji是隨機(jī)變化的，與對蜜源開采階段的要求不相適應(yīng)。如果在蜜源開采初期，隨機(jī)產(chǎn)生的φji比較小，就會降低算法的全局尋優(yōu)能力，使算法遲遲不能逼近最優(yōu)解；如果在蜜源開采后期，隨機(jī)產(chǎn)生的φji比較大，則會造成對蜜源的過度開采，降低算法效率。針對這一問題，本研究對式（4）進(jìn)行了改進(jìn)。在數(shù)學(xué)理論上，即如式（8）所示：Vji=Xji+γ fibest（Vji-Xji）（8）其中，γ為鄰域搜索范圍調(diào)整系數(shù)，對應(yīng)計算則如式（9）所示：γ=γmax-t×（γmax-γmin）tmax（9）其中，γmax和γmin為常數(shù)，用以控制鄰域搜索最大最小范圍，這里取γmax=0.9， γmin=0.3；t和tmax分別為當(dāng)前迭代步數(shù)和最大迭代步數(shù)。

式（8）采用了最優(yōu)適應(yīng)度關(guān)聯(lián)的搜索范圍線性遞減的策略，能使開采系數(shù)隨進(jìn)化步數(shù)逐漸降低。其優(yōu)點是：在蜜源開采初期，γ相對較大，利于大范圍搜索，能使算法快速逼近全局最優(yōu)，提高算法效率；在蜜源開采后期，γ相對較小，利于算法實現(xiàn)局部精細(xì)搜索，提高算法尋優(yōu)質(zhì)量。

3IABC-K算法

經(jīng)過對ABC算法的改進(jìn)，結(jié)合K均值聚類，本研究提出了一種新的人工蜂群優(yōu)化與K均值聚類混合算法IABC-K。

3.1算法思想

IABC-K算法首先將圖像分割問題轉(zhuǎn)化為ABC算法搜索最佳蜜源問題，然后采用改進(jìn)蜜源更新和開采策略的ABC算法進(jìn)行尋優(yōu)，利用改進(jìn)ABC算法全局尋優(yōu)能力強(qiáng)的優(yōu)點，使算法快速逼近全局最優(yōu)。當(dāng)算法逼近全局最優(yōu)或得到指定閾值時，使用當(dāng)前搜索到的全局最優(yōu)解作為K均值初始聚類中心，將算法切換到K均值聚類算法，利用K均值聚類局部尋優(yōu)精細(xì)的特點繼續(xù)尋優(yōu)，直至找到最優(yōu)解。

3.2蜜源適應(yīng)度計算

在進(jìn)行圖像分割時，首先將圖像轉(zhuǎn)化為d維數(shù)據(jù)點樣本集，并根據(jù)式（3）隨機(jī)選擇n個蜜源作為優(yōu)化問題解空間。其中，第i個蜜源的適應(yīng)度計算方法如式（10）所示：fi=∑dj=1∑xi∈Cjxi-cj2（10）3.3算法切換

ABC算法切換至K均值聚類的時機(jī)由蜜源群體適應(yīng)度方差σ2決定。在對蜜源的開采進(jìn)程中，fi與favg將逐漸趨同，并使σ2逐漸變小。當(dāng)跟隨蜂搜索到最優(yōu)蜜源附近時，σ2將小于某指定閾值。這時，可停止跟隨蜂的開采工作，輸出跟隨蜂搜索到的當(dāng)前最優(yōu)解作為K均值聚類中心，進(jìn)入K均值尋優(yōu)階段。σ2的計算如式（11）所示：σ2=∑ni=1fi-favg（11） 3.4算法步驟

IABC-K算法步驟如下：

步驟1初始化樣本集X并設(shè)置引領(lǐng)蜂、跟隨蜂和偵察蜂數(shù)量；設(shè)置MCN和limit初始值。

步驟2采用式（3）進(jìn)行蜜源初始化，并根據(jù)式（10）計算初始化后的每個蜜源的適應(yīng)度值fi，記錄最優(yōu)適應(yīng)度值fibest。

步驟3根據(jù)式（7）計算φji，然后根據(jù)式（6）進(jìn)行蜜源更新：若蜜源Vji優(yōu)于蜜源Xji，則用Vji代替Xji；若Xji經(jīng)limit次開采后無更新，則放棄Xji，其對應(yīng)引領(lǐng)蜂轉(zhuǎn)化為偵察蜂，根據(jù)式（3）隨機(jī)勘探新蜜源并替代Xji，再按式（10）重新計算fi，記錄fibest。

步驟4根據(jù)式（5）所得概率使跟隨蜂選擇引領(lǐng)蜂或蜜源。

步驟5根據(jù)當(dāng)前進(jìn)化步數(shù)t按式（9）計算γ。再根據(jù)式（8）進(jìn)行蜜源開采。

步驟6根據(jù)式（11）計算σ2。若σ2不小于指定閾值，則轉(zhuǎn)到步驟5，按式（8）繼續(xù)開采蜜源；若σ2小于指定閾值，則算法轉(zhuǎn)到K均值聚類，并以跟隨蜂搜索到的k個當(dāng)前最優(yōu)解作為K均值聚類的初始中心，同時按式（1）計算每個數(shù)據(jù)點到各聚類中心距離，再按式（2）繼續(xù)搜索更優(yōu)解。

步驟7若算法當(dāng)前迭代次數(shù)t

4實驗結(jié)果和分析

本研究將IABC-K算法（以下簡稱本文算法）與其它算法進(jìn)行了對比實驗。參與對比的算法為K均值聚類算法（以下簡稱算法1），ABC與K均值聚類混合算法（以下簡稱算法2）。算法2和本文算法參數(shù)設(shè)置相同：種群大小為20；個體維度為5；limit取20；MCN取500。實驗環(huán)境為Intel（R） Core（TM）i7 @2.67 GHz ＼＼RAM 4GB＼＼ Windows 7，仿真平臺為Matlab R2012a。實驗數(shù)據(jù)為伯克利圖像分割測試數(shù)據(jù)集。研究中選取了4幅圖像進(jìn)行分割實驗，結(jié)果如圖1所示。

在圖1中，圖1（a）從左到右依次為實驗圖像原圖，包括：人物（481×321；115 KB）；鳥類（481×321；104 KB）；植物（321×481；93.5 KB）；建筑（481×321；113 KB）。圖1（b）～（d）分別為實驗圖像在算法1、算法2和本文算法下的分割結(jié)果。為了更好地比較3種算法的分割質(zhì)量，給出了實驗結(jié)果的局部放大圖，如圖2所示。

圖2（a）～（d）分別為實驗圖像原圖和算法1、算法2和本文算法分割實驗結(jié)果的局部放大圖。從圖2（a）～（d）第一列可以看出，在箭頭所指的人物左側(cè)臉頰處，原圖存在陰影，算法2和本文算法均較好地分割出了該陰影而算法1卻丟失了該陰影；對人物鼻梁處的頭發(fā)，算法1分割結(jié)果較為模糊，而算法2和本文算法較清晰。從圖2（a）～（d）第二列可以看出，在箭頭所指的鳥的翅膀處以及鳥的胸腹羽毛處，本文算法很好地保持了其輪廓的完整性，具有最好的分割效果；算法2也基本保持了輪廓的完整性但效果稍差，而算法1結(jié)果存在殘缺。圖2（a）～（d）第三列顯示的是3種算法對植物圖像的分割，可以看出，算法1和算法2結(jié)果中，樹與海水背景相互混雜，樹葉輪廓不完整；本文算法不但清楚地分開了樹與海水背景，而且樹葉輪廓較完整。圖2（a）～（d）第四列顯示的是3種算法對建筑圖像的分割。在原圖中，建筑樓層分為3層，但算法1已經(jīng)分辨不出來；算法2雖然可以分辨但不夠完整；本文算法的分割結(jié)果清晰完整，明顯優(yōu)于算法1和算法2。

本研究對4幅圖像各重復(fù)了20次分割實驗，并對比了3種算法的平均運行時間。實驗運行結(jié)果可見表1。

圖像名稱算法1算法2本文算法人物6 5449 8876 811鳥類6 2478 5246 465植物4 4056 7734 712建筑4 6087 4055 033從表1可以看出，在對4幅圖像進(jìn)行分割時，算法1平均運行時間最少，算法2平均運行時間多于本文算法，說明本文算法的圖像分割效率優(yōu)于算法2、但低于算法1。

實驗結(jié)果表明：本文算法圖像分割質(zhì)量優(yōu)于算法1和算法2，效率略低于算法1而高于算法2。究其原因即在于：本文算法在ABC算法蜜源更新階段引入了與最優(yōu)適應(yīng)度關(guān)聯(lián)的自適應(yīng)鄰域搜索機(jī)制，增強(qiáng)了算法綜合尋優(yōu)能力，使算法能快速逼近最優(yōu)解，提高了算法效率；本文算法在ABC算法蜜源開采階段采用與最優(yōu)適應(yīng)度關(guān)聯(lián)的線性遞減策略，可有效匹配蜜源開采階段的特點和要求，從而能提高算法尋優(yōu)質(zhì)量和效率；本文算法以ABC算法尋優(yōu)結(jié)果初始化K均值聚類中心，解決了K均值聚類對初始中心的依賴問題，提高了算法穩(wěn)定性。此外，本文算法效率略低于算法1，原因在于本文算法的復(fù)雜度要高于算法1。

5結(jié)束語

本文提出的IABC-K算法根據(jù)ABC算法在蜜源更新和蜜源開采階段的不同特點，分別采取了與最優(yōu)適應(yīng)度關(guān)聯(lián)的自適應(yīng)蜜源更新策略和線性遞減蜜源開采策略，取得了較好的圖像分割質(zhì)量和更高的圖像分割效率。但如何改進(jìn)ABC算法，有效解決圖像分割存在問題，還有待深入研究。

參考文獻(xiàn)

[1] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C] // Proc. of 5th Berkeley Symposium on Math. Stat. and Prob. Berkeley：University of California Press， 1967：281-297.

[2] SIDDIQUI F U， ISA N A M. Enhanced moving K-means （EMKM） algorithm for image segmentation[J]. IEEE Transactions on Consumer Electronics， 2011， 57（2）： 833-841.

[3] 詹森， 秦大同， 曾育平. 基于遺傳優(yōu)化K均值聚類算法工況識別的混合動力汽車能量管理策略[J]. 中國公路學(xué)報， 2016， 29（4）： 130-137，152.

[4] 李海洋， 文永革， 何紅洲， 等. 基于隨機(jī)權(quán)重粒子群和 K-均值聚類的圖像分割[J]. 圖學(xué)學(xué)報， 2014， 35（5）： 755-761.

[5] LI Haiyang， HE Hongzhou， WEN Yongge . Dynamic particle swarm optimization and K-means clustering algorithm for image segmentation[J]. International Journal for Light and Electron Optics， 2015， 126（24）： 4817-4822.

[6] 柯鋼. 基于增強(qiáng)蜂群優(yōu)化與 K-means 的文本聚類算法[J]. 計算機(jī)應(yīng)用研究， 2016， 33（8）： 2298-2302.

[7] KIRAN M S， HAKLI H， GUNDUZ M， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization[J]. Information Sciences， 2015， 300：140-157.

[8] 梁冰， 徐華. 基于改進(jìn)人工蜂群的核模糊聚類算法[J]. 計算機(jī)應(yīng)用， 2017，37（9）：2600-2604.

[9] 宋錦， 高浩， 王保云. 改進(jìn)人工蜂群算法在圖像分割中的應(yīng)用[J]. 電視技術(shù)， 2016， 40（8）： 8-14.

[10]SHOKOUHIFAR M，JALALI A. Optimized sugeno fuzzy clustering algorithm for wireless sensor networks[J]. Engineering Applications of Artificial Intelligence， 2017，60： 16-25.

[11]CONG T D， WU Zhijian， WANG Zelin， et al. A novel hybrid data clustering algorithm based on Artificial Bee Colony algorithm and K-Means[J]. Chinese Journal of Electronics， 2015， 24（4）：694-701.

[12]BOSE A， MALI K. Fuzzy-based artificial bee colony optimization for gray image segmentation[J]. Signal， Image and Video Processing， 2016，10（6）：1089-1096.

[13]趙文昌， 李忠木. 融合改進(jìn)人工蜂群和K均值聚類的圖像分割[J]. 液晶與顯示， 2017，32（9）：726-735.

[14]秦全德， 程適， 李麗， 等. 人工蜂群算法研究綜述[J]. 智能系統(tǒng)學(xué)報， 2014， 9（2）： 127-135.

[15]周新宇， 吳志健， 鄧長壽， 等. 一種鄰域搜索的人工蜂群算法[J]. 中南大學(xué)學(xué)報（自然科學(xué)版）， 2015， 46（2）： 534-546.

[16]YEH C C， YANG M S. Evaluation measures for cluster ensembles based on a fuzzy generalized rand index[J]. Applied Soft Computing， 2017， 57：225-234.（上接第44頁）

[5] 陳昌領(lǐng)，馮曉東，邵惠鶴. 單生產(chǎn)線序貫多目的批處理過程短期調(diào)度的MILP建模[J]. 系統(tǒng)仿真學(xué)報，2001，13（S1）：69-71.

[6] 戴智杰，宋執(zhí)環(huán)，宋春躍. 基于遺傳算法的浸染生產(chǎn)排缸策略[J]. 運籌與管理，2006，15（2）：149-153.

[7] 莫豐勇，郝平，楊馬英. 基于遺傳算法的拉動式浸染生產(chǎn)動態(tài)排產(chǎn)策略[J]. 計算機(jī)應(yīng)用，2008，28（S2）：97-99.

[8] 莫豐勇. 印染企業(yè)浸染生產(chǎn)排產(chǎn)優(yōu)化問題研究及系統(tǒng)設(shè)計[D]. 杭州：浙江工業(yè)大學(xué)，2008.

[9] LAOBOONLUR P ，HODGSON T J，THONEY K A. Production scheduling in a knitted fabric dyeing and finishing process[J]. The Journal of The Textile Institute，2006，97（5）：391-399.

[10]PINEDO M L. Scheduling： Theory， algorithms， and systems [M]. 2nd ed. New Jersey，USA： Prentice-Hall Inc， 2001.