基于混合遺傳模擬退火的模糊C-均值聚類算法

殷旅江，楊立君，胡明茂，鄧義成

（1.湖北汽車工業(yè)學(xué)院經(jīng)濟(jì)管理學(xué)院，湖北十堰442002；2.湖北汽車工業(yè)學(xué)院機(jī)械工程學(xué)院，湖北十堰442002；3.上海海事大學(xué)經(jīng)濟(jì)管理學(xué)院，上海201306）

模糊聚類分析概念最早由Ruspini[1]提出，模糊聚類是基于模糊理論的聚類算法，可以將集中的數(shù)據(jù)根據(jù)其隸屬度進(jìn)行分類。模糊C-均值（Fuzzy C-means，F(xiàn)CM）是比較常用的聚類方法，目前已運(yùn)用于圖像分割[2]、腦電信號處理[3]、稅務(wù)決策支持系統(tǒng)[4]等。由于FCM算法本質(zhì)是用梯度下降的方法尋找最優(yōu)解，因此存在局部收斂的問題。許多學(xué)者為了彌補(bǔ)FCM算法的不足，將一些進(jìn)化算法引入模糊聚類中，從而形成了新的聚類方法：主要有基于粒子群算法[5]、基于改進(jìn)遺傳算法[6]和基于模擬退火算法[7]的方法等。

遺傳算法（Genetic Algorithm，GA）由J.H.Holland于1975年提出[8]，目前應(yīng)用于諸多領(lǐng)域[9-13]。遺傳算法具有較好的全局搜索性能，將其引入到聚類分析中可有效克服局部收斂問題。同時，遺傳算法也存在早熟缺陷，因此本文中又將模擬退火算法引入[14]，以避免早熟現(xiàn)象。通過將這2種算法結(jié)合用于聚類分析，可以使遺傳算法與模擬退火算法互相取長補(bǔ)短，獲得較好效果。

1 多類指派約束建模

1.1 模型變量定義

FCM的目標(biāo)函數(shù)定義為

FCM算法是通過將目標(biāo)函數(shù)最小化的迭代收斂來獲得最優(yōu)解。迭代過程中，U和A取值如下：

FCM算法迭代示意圖如圖1所示。

圖1 FCM算法示意圖

1.2 遺傳算法

遺傳算法是一種基于對自然界生物進(jìn)化的認(rèn)識而提出的算法，有非常廣泛的應(yīng)用，此處不做詳細(xì)介紹，只給出其算法示意圖，如圖2所示。

1.3 模擬退火算法

模擬退火算法（Simulated Annealing Algorithm，SA）由Metropolis等人[15-16]于1953年提出，其基本思想是通過模擬高溫物體退火過程來尋找最優(yōu)解或者近似最優(yōu)解。步驟如下：1）設(shè)置初始溫度、終止溫度、冷卻系數(shù)等，并隨機(jī)產(chǎn)生一個初始解；2）在當(dāng)前解領(lǐng)域中選擇一個最優(yōu)解，并計(jì)算該解與上一個最優(yōu)解的能量差，若小于0，則該解作為下一個當(dāng)前解，否則重新選擇；3）按照一定方式降溫，重復(fù)步驟2）；4）檢查終止條件，若滿足，結(jié)束迭代，輸出最優(yōu)解，否則轉(zhuǎn)到步驟2）。

圖2 遺傳算法示意圖

2 基于遺傳模擬退火的模糊聚類

2.1 遺傳模擬退火算法

遺傳模擬退火算法本質(zhì)是將遺傳算法和模擬退火算法結(jié)合起來，產(chǎn)生一種新的混合優(yōu)化算法。遺傳算法在把握搜索過程總體的能力比較強(qiáng)，但是局部搜索能力較差；模擬退火算法局部搜索能力較強(qiáng)，但對解的搜索空間了解較少，可能使得其運(yùn)算效率低。本文中將這2種算法有效結(jié)合，可以充分發(fā)揮兩者優(yōu)點(diǎn)，獲得較好的效果。

該算法與基本的遺傳算法基本是類似的，即先隨機(jī)產(chǎn)生初始解進(jìn)行全局搜索，然后通過交叉變異產(chǎn)生新個體，再獨(dú)立的對產(chǎn)生的個體進(jìn)行模擬退火操作，將結(jié)果作為下代種群個體。重復(fù)迭代過程，直至達(dá)到終止條件。步驟如下：1）設(shè)置初始參數(shù)、最大迭代次數(shù)、遺傳算法交叉率、模擬退火算法初始溫度等；2）產(chǎn)生初始種群；3）計(jì)算初始種群個體適應(yīng)度；4）進(jìn)行個體的交叉變異操作，產(chǎn)生新種群；5）對新種群個體進(jìn)行模擬退火操作，產(chǎn)生新個體；6）評價個體適應(yīng)度；7）判斷是否達(dá)到終止條件，是則輸出最優(yōu)解，否則轉(zhuǎn)到步驟4）。

2.2 基于遺傳模擬退火算法的模糊聚類算法

根據(jù)聚類問題的特征，采用操作較簡單、容易實(shí)現(xiàn)交叉變異操作的二進(jìn)制編碼方式，并采用隨機(jī)遍歷抽樣方式進(jìn)行選擇，以及使用單點(diǎn)變異方式進(jìn)行變異操作。在變異成功后，再對新個體進(jìn)行模擬退火操作，操作完畢，通過計(jì)算目標(biāo)函數(shù)值，記錄最佳值。最后，通過終止準(zhǔn)則判斷，結(jié)束迭代，輸出結(jié)果。該聚類算法程序偽代碼如下：

代碼中，m 定義為樣本特征維數(shù)，cn 定義為類別數(shù)，q 定義為冷卻系數(shù)，T0 定義為初始溫度，Tend定義為終止溫度，MAXGEN 定義為最大遺傳代數(shù)，sizepop種群個體數(shù)目，PRECI 定義為變量的二進(jìn)制位數(shù)，NVAR 定義為變量的維數(shù)，pc 定義為交叉率，pm 定義為變異率。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證本文中提出的聚類算法的有效性，從UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫中選擇了Wine、Iris以及Car數(shù)據(jù)集做了仿真實(shí)驗(yàn)。這些數(shù)據(jù)集均來源于http∶//archive.ics.uci.edu/ml/網(wǎng)站，在本文中不一一列出。實(shí)驗(yàn)中的相關(guān)初始參數(shù)如表1所示。Car 數(shù)據(jù)集共1728個數(shù)據(jù)，將其分為4類，其聚類結(jié)果如表2所示。Iris 數(shù)據(jù)集共150個數(shù)據(jù)，將其分為3個類別，其聚類結(jié)果如表3所示。Wine 數(shù)據(jù)集共有178個數(shù)據(jù)，將其分為3類，其聚類結(jié)果如表4所示。各數(shù)據(jù)集和對應(yīng)算法的聚類過程如圖3所示。

由表2～4和圖3可知，對于Car 數(shù)據(jù)集聚類來說，本文中提出的算法聚類效果比原始FCM算法好些，并且其聚類過程圖有波動，即其在聚類過程中，目標(biāo)函數(shù)值會出現(xiàn)反復(fù)，這就說明了該算法在對樣本空間進(jìn)行聚類時陷入局部極小的可能性較小。對于Iris和Wine 數(shù)據(jù)集來說，2種算法取得的效果基本相同，但是本文中提出的算法陷入局部最小的可能性小，其全局搜索性能更好。

表1 實(shí)驗(yàn)相關(guān)參數(shù)表

表2 Car數(shù)據(jù)集聚類結(jié)果表

表3 Iris數(shù)據(jù)集聚類結(jié)果表

表4 Wine數(shù)據(jù)集聚類結(jié)果表

圖3 各數(shù)據(jù)集對應(yīng)的算法聚類

4 結(jié)論

本文中提出的算法較原始FCM算法來說，其全局搜索性能更好，較不易陷入局部極小值，聚類效果更好。本文中的算法有效避免了原始FCM算法易于陷入局部極小值的缺陷，對于聚類問題，可以獲得更好結(jié)果。

[1]Ruspini E H.A New Approach to Clustering[J].Information and Control，1969，19（15）：22-32.

[2]康家銀，紀(jì)志成，龔成龍.一種核模糊C 均值聚類算法及其應(yīng)用[J].儀器儀表學(xué)報，2010，31（7）：1657-1663.

[3]余煒，萬代立，楊喜敬，等.改進(jìn)的FCM算法及其在腦電信號處理中的應(yīng)用[J].重慶大學(xué)學(xué)報，2014，37（7）：83-89.

[4]楊靜，稅務(wù)決策支持系統(tǒng)的FCM應(yīng)用研究[J].四川理工學(xué)院學(xué)報：社會科學(xué)版，2009（S1）216-218.

[5]張利彪，周春光，馬銘，等.基于粒子群優(yōu)化算法的模糊C-均值聚類[J].吉林大學(xué)學(xué)報，2006，44（2）：217-222.

[6]董軍浪，王慶飛.基于改進(jìn)遺傳算法的模糊C均值聚類算法[J].西安工程大學(xué)學(xué)報，2008，22（5）：605-609.

[7]劉曉龍，張佑生，謝穎.模擬退火與模糊C-均值聚類相結(jié)合的圖像分割算法[J].工程圖學(xué)學(xué)報，2007，27（1）：89-93.

[8]J H Holland.Adaptation in Natural and artificial systems[M].Ann Arbor∶University of Michigan Press,1975.

[9]周明，孫樹棟.遺傳算法原理與應(yīng)用[M].長沙：國防工業(yè)出版社，1999.

[10]李金屏，何苗，楊波.遺傳算法平均截止代數(shù)和成功率與種群規(guī)模之間的關(guān)系[J].系統(tǒng)仿真學(xué)報，2001，13（8）：206-210.

[11]殷旅江，楊立君，何波.基于主成分分析與支持向量機(jī)的汽柴油需求預(yù)測[J].工業(yè)工程，2015（2）：20-27+50.

[12]史奎凡，陳月輝.提高遺傳算法收斂速度的方法[J].信息與控制，1998（8）：289-293.

[13]殷旅江，高亮，李登橋，胡明茂.改進(jìn)元胞遺傳算法的轉(zhuǎn)塔式貼片機(jī)貼裝優(yōu)化[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2015（3）：113-117+132.

[14]韓嘯，劉淑芬，徐天琦.基于遺傳模擬退火算法的改進(jìn)K-medoids算法[J].吉林大學(xué)學(xué)報：工學(xué)版，2015（2）：619-623.

[15]王華秋，曹長修.基于模擬退火的并行粒子群優(yōu)化研究[J].控制與決策，2005，20（5）：500-504.

[16]Mitsunori M K,Tomoyuki H,Toshihiko F.Parallel simulated annealing with adaptive neighborhood determined by GA[A].Proceeding IEEE International Conference System and Cybernetics[C].Washington∶Institute of Electrical and Electronics Engineers Inc,2003∶26-31.