李海洋 何紅洲

文章編號： 2095-2163（2018）03-0045-05中圖分類號： 文獻標志碼： A

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

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

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

1相關算法

1.1K均值聚類算法

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

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

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

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維向量；設算法最大迭代次數為MCN；每個蜜源的最大開采次數為limit。

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

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

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

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

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

步驟6若算法當前迭代次數t

2ABC算法改進

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

2.1蜜源更新策略

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

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

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

φmaxfi>fmin （7）

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

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

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

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

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

3IABC-K算法

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

3.1算法思想

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

3.2蜜源適應度計算

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

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

IABC-K算法步驟如下：

步驟1初始化樣本集X并設置引領蜂、跟隨蜂和偵察蜂數量；設置MCN和limit初始值。

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

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

步驟4根據式（5）所得概率使跟隨蜂選擇引領蜂或蜜源。

步驟5根據當前進化步數t按式（9）計算γ。再根據式（8）進行蜜源開采。

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

步驟7若算法當前迭代次數t

4實驗結果和分析

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

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

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

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

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

5結束語

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

參考文獻

[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]. 中國公路學報， 2016， 29（4）： 130-137，152.

[4] 李海洋， 文永革， 何紅洲， 等. 基于隨機權重粒子群和 K-均值聚類的圖像分割[J]. 圖學學報， 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] 柯鋼. 基于增強蜂群優(yōu)化與 K-means 的文本聚類算法[J]. 計算機應用研究， 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]. 計算機應用， 2017，37（9）：2600-2604.

[9] 宋錦， 高浩， 王保云. 改進人工蜂群算法在圖像分割中的應用[J]. 電視技術， 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]趙文昌， 李忠木. 融合改進人工蜂群和K均值聚類的圖像分割[J]. 液晶與顯示， 2017，32（9）：726-735.

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

[15]周新宇， 吳志健， 鄧長壽， 等. 一種鄰域搜索的人工蜂群算法[J]. 中南大學學報（自然科學版）， 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] 陳昌領，馮曉東，邵惠鶴. 單生產線序貫多目的批處理過程短期調度的MILP建模[J]. 系統(tǒng)仿真學報，2001，13（S1）：69-71.

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

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

[8] 莫豐勇. 印染企業(yè)浸染生產排產優(yōu)化問題研究及系統(tǒng)設計[D]. 杭州：浙江工業(yè)大學，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.