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

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

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

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

1 多類指派約束建模

1.1 模型變量定義

FCM的目標函數定義為

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

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

圖1 FCM算法示意圖

1.2 遺傳算法

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

1.3 模擬退火算法

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

圖2 遺傳算法示意圖

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

2.1 遺傳模擬退火算法

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

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

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

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

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

3 仿真實驗

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

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

表1 實驗相關參數表

表2 Car數據集聚類結果表

表3 Iris數據集聚類結果表

表4 Wine數據集聚類結果表

圖3 各數據集對應的算法聚類

4 結論

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

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

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

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

[4]楊靜，稅務決策支持系統的FCM應用研究[J].四川理工學院學報：社會科學版，2009（S1）216-218.

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

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

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

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

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

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

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

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

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

[14]韓嘯，劉淑芬，徐天琦.基于遺傳模擬退火算法的改進K-medoids算法[J].吉林大學學報：工學版，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.