改進混合蛙跳算法優(yōu)化的產(chǎn)品族模糊C均值聚類設(shè)計方法

崔文華， 劉曉冰， 王 偉， 王介生

（1.大連理工大學(xué)控制科學(xué)與工程學(xué)院，遼寧大連 116024；2.遼寧科技大學(xué)電子與信息工程學(xué)院，遼寧鞍山 114044）

改進混合蛙跳算法優(yōu)化的產(chǎn)品族模糊C均值聚類設(shè)計方法

崔文華＊1，2， 劉曉冰1， 王 偉1， 王介生2

（1.大連理工大學(xué)控制科學(xué)與工程學(xué)院，遼寧大連 116024；2.遼寧科技大學(xué)電子與信息工程學(xué)院，遼寧鞍山 114044）

研究了基于改進混合蛙跳算法優(yōu)化的模糊C均值聚類解決模塊化產(chǎn)品族設(shè)計中產(chǎn)品平臺的確定問題.建立了該產(chǎn)品開發(fā)過程中的部件關(guān)聯(lián)矩陣，采用變個體長度的混合蛙跳算法同時優(yōu)化模糊聚類數(shù)和聚類中心，求得產(chǎn)品構(gòu)成部件的最優(yōu)模糊劃分.切斷算子和拼接算子用來對個體進行重新組合而形成新個體，采用ISODATA迭代算法進行局部尋優(yōu).通過對紙幣清分機進行的產(chǎn)品族設(shè)計的仿真研究，表明所提方法為產(chǎn)品族模塊化設(shè)計提供了定量數(shù)學(xué)分析和快速配置的理論依據(jù).

紙幣清分機；產(chǎn)品族；產(chǎn)品平臺；混合蛙跳算法；模糊C均值聚類

0 引 言

在國內(nèi)外競爭日益激烈的市場環(huán)境當中，針對不同層次和規(guī)模的客戶群體設(shè)計提供合適的金融機具產(chǎn)品，是金融機具企業(yè)面臨的一個嚴重挑戰(zhàn).基于產(chǎn)品平臺（product platform）的面向產(chǎn)品族（product family）的設(shè)計方法在產(chǎn)品設(shè)計中得到了廣泛應(yīng)用［1］，該方法擴展了面向變形的設(shè)計方法（design for variety，DFV），以提高企業(yè)的敏捷定制水平.

模糊C均值（FCM）聚類算法［2］是非監(jiān)督模式識別中的一種基本方法，目前在圖像處理、模式識別、模糊控制等眾多領(lǐng)域被廣泛采用.判定聚類算法是否高效需要考慮如下問題：能否自動確定聚類的數(shù)目（聚類有效性問題［3］）；是否對初始參數(shù)和噪聲敏感；是否具有全局優(yōu)化能力和較快的收斂速度.諸如粒子群算法［4］、微分進化算法［5］等智能優(yōu)化算法被應(yīng)用在模糊聚類算法中的優(yōu)化領(lǐng)域.這些算法在某種程度上有效地克服了傳統(tǒng)模糊聚類算法易陷入局部極小值的缺點，而且有效避免了對初始化選值敏感性的問題.另一方面，眾多聚類有效性函數(shù)被提出，如Xie－Beni的Fukuyama－Sugeno的、Kwon的和 Chen－Linkens的，但基于聚類有效性函數(shù)的FCM聚類算法易陷入局部極小值和對初始化選值敏感的弱點沒有得到有效解決.文獻［10］則采用神經(jīng)網(wǎng)絡(luò)算法對獲取最優(yōu)聚類數(shù)進行了有效嘗試.在面向產(chǎn)品族的產(chǎn)品開發(fā)設(shè)計領(lǐng)域，國內(nèi)外學(xué)者采用聚類算法也進行了有效探索［1，11］.文獻［1］采用模糊聚類分析方法解決飲水機的模塊化產(chǎn)品族設(shè)計中模塊和核心平臺的確定問題.文獻［11］采用聚類分析方法對電子產(chǎn)品功能模塊進行提取，為產(chǎn)品族設(shè)計提供了一定思路.

混合蛙跳算法（SFLA）就是一種基于群體的進化搜索智能算法［12］.2009年，Amiri等［13］采用SFLA對K均值聚類問題進行了求解；杜長海等［14］提出SFLA－FCM優(yōu)化交通時段劃分問題，但沒有考慮聚類有效性問題.

本文應(yīng)用基于改進混合蛙跳算法優(yōu)化的模糊C均值聚類解決模塊化產(chǎn)品族設(shè)計中產(chǎn)品平臺的確定問題，以期為產(chǎn)品族模塊化設(shè)計提供定量數(shù)學(xué)分析和快速配置的理論依據(jù).

1 FCM聚類算法

FCM聚類算法將特征空間X＝（x1，x2，…，xn）中的特征點分為c類（2≤c≤n），第i類的聚類中心用vi表示，其中任意特征點xj屬于第i類隸屬度uij（0≤uij≤1），且uij滿足如下條件：

FCM聚類算法的目標函數(shù)［15］為

其中m＞1.FCM聚類算法的目的就是獲取最小化目標函數(shù)（3）的U＝（uij）c×n和V＝（v1v2…vc）.

ISODATA算法流程如下（算法流程1）：

Step 2對于c＝2，3，…，cmax，初始化V0＝（v10v20…vc0）；

Step 3針對迭代次數(shù)t＝1，2，…，T，根據(jù)以下公式計算隸屬度和聚類中心：

2 基于變個體長度的SFLA優(yōu)化FCM參數(shù)

2.1 SFLA算法

SFLA算法的基本思想是［12］：隨機生成S維解空間中由N只蛙組成的初始種群P＝｛X1，X2，…，XN｝，第i只蛙表示為Xi＝（xi1xi2…xiS）；然后將種群內(nèi)個體按適應(yīng)度值進行降序排列，種群中最優(yōu)個體記為Xg；接下來將蛙群個體均分為m個模因組，每組有n只蛙，即N＝m×n.設(shè)蛙的集合Mk為第k個模因組，則蛙的分配過程可用下式進行描述：

記錄每個模因組中最優(yōu)個體和最差個體適應(yīng)度為Xb和Xw，而種群中最優(yōu)個體記為Xg.然后對Xw進行局部搜索，采用如下蛙跳規(guī)則進行更新：

式中：r∈［0，1］，Dmax為蛙所跳最大距離.如X′w優(yōu)于Xw，則進行個體替換，如無改進，則用Xg取代Xb，根據(jù)式（7）和（8）重新進行局部搜索；如個體依然沒有得到優(yōu)化，則隨機產(chǎn)生新個體替代Xw.重復(fù)上述優(yōu)化過程Lmax次，進行蛙群的混洗、排序、模因組劃分和局部搜索，如此反復(fù)直到定義的收斂條件結(jié)束為止，例如達到混合迭代次數(shù)Gmax.

2.2 編碼和適應(yīng)度函數(shù)

本文對聚類中心向量V進行編碼，設(shè)n個樣本要分成c類，為了合理有效地縮小SFLA的搜索空間，本文中c的取值范圍為［2，cmax］（cmax≤）.根據(jù)各自的取值范圍，采用浮點數(shù)編碼，則一個個體I可表示為［16］

在本文中，采用SFLA對聚類中心向量V進行優(yōu)化，式（9）中的聚類數(shù)c是變化的，所以個體I的長度不是固定的.本文借助Jm（U，V）定義SFLA的適應(yīng)度函數(shù)：

適應(yīng)度函數(shù)采用如下步驟進行求解（算法流程2）：

Step 1從個體I中提取vi（i＝1，2，…，c）；

Step 2依據(jù)式（4）求取uij；

Step 3根據(jù)式（5）重新計算聚類中心參數(shù)；

Step 4根據(jù)式（3）和（10）計算ff（U，V）.確定了編碼方式和ff（U，V）后，就可用混合蛙跳算法對模糊聚類數(shù)和聚類中心同時優(yōu)化.

2.3 切斷算子和拼接算子

由于編碼方式的特殊性，由式（7）、（8）所定義的蛙跳規(guī)則不適用于變個體長度的SFLA，所以切斷算子（cut operator）和拼接算子（splice operator）［16］被用來將群體中各個個體進行重組（如圖1所示）.

2.4 算法流程

基于變個體長度的SFLA同時優(yōu)化模糊聚類數(shù)和聚類中心的算法步驟如下（算法流程3）.

Step 1選定如下算法初始參數(shù)：N、cmax、S、m、n（N＝m×n）、Lmax和Gmax.

圖1 基于切斷算子和拼接算子的新蛙跳規(guī)則Fig.1 New frog－leaping rule based on cut operator and splice operator

Step 2隨機生成包含N只蛙的P＝｛X1（t），…，Xk（t），…，XN（t）｝；迭代計數(shù)值t＝0；將每只蛙Xk（t）作為聚類中心參數(shù)，并根據(jù)算法流程2求出每個個體的適應(yīng)度值Fk（t）＝F（Xk（t））；對蛙群按照適應(yīng)度值從大到小進行排列，令Uk（t）＝｛Xk（t），F(xiàn)k（t）｝和Xg（t）＝U1（t）.

Step 3根據(jù)式（1）對U進行m個模因組M1（t），…，Mj（t），…，Mm（t）的形成，令最優(yōu)個體和最差個體分別為和.

Step 4對Mj（t）中的與做切斷和拼接運算，產(chǎn)生新蛙，并采用算法流程1進行局部搜索；然后根據(jù)算法流程2，計算其適應(yīng)度值，采用上文所述的蛙跳規(guī)則進行局部尋優(yōu)，得到進化后的模因組M1（t）′，M2（t）′，…，Mm（t）′.

Step 5將更新后的模因組M1（t）′，M2（t）′，…，Mm（t）′內(nèi)的蛙重新混合，記U（t＋1）＝（M1（t）′M2（t）′…Mm（t）′），對U（t＋1）中的蛙按照適應(yīng)度值從大到小進行排列，記錄Xg（t＋1）＝U1（t＋1）.

Step 6t＝t＋1，如t＜Gmax，轉(zhuǎn)Step 3，否則輸出最優(yōu)蛙.

3 基于聚類有效性函數(shù)的模糊聚類數(shù)優(yōu)化

3.1 聚類有效性函數(shù)

（1）Bezdek提出的VPC和VPE

Bezdek提出的VPC和VPE如下：

VPC在1／c和1之間有效.如果期待一個良好的劃分，目標就是選取使Vpc最大的模糊劃分.它最主要的優(yōu)勢是分配系數(shù)簡便，缺點是它的單調(diào)下降，缺乏直接連接到數(shù)據(jù)本身的性能.

VPE在0和logac之間有效.對所有的概率群C，事實證明它有如下關(guān)系：0≤1－PC（C）≤PE（C）.它基本上是一個衡量模糊聚類劃分的函數(shù)，與VPC類似.

（2）Xie－Beni提出的VXB

VXB是基于Jm的客觀功能，通過確定平均數(shù)據(jù)和最小距離來確定聚類中心的.

3.2 算法流程

結(jié)合FCM聚類算法和聚類有效性函數(shù)可得到最優(yōu)模糊劃分，其算法描述如下（算法流程4）：

Step 1指定最大聚類中心個數(shù)cmax（cmax≤），聚類有效性函數(shù)VW（U，V，c）（如式（11）～（16）），初始化T、m和ε＞0；

Step 2對于c＝2，3，…，cmax，進行V0＝（v10v20…vc0）的初始化；

Step 3針對迭代次數(shù)t＝1，2，…，T，根據(jù)式（4）和（5）計算uij，t和vj，t.如果＜ε，轉(zhuǎn)下一步，否則重復(fù)Step 3；

Step 4計算VW（U，V，c）；如果c＜cmax，轉(zhuǎn)步驟2；否則停止迭代，最優(yōu)聚類數(shù)c＝cb，cb滿足下式：

4 仿真實驗

4.1 聚類有效性實驗

聚類有效性準則要求模糊劃分必須在緊密性和分離性間達到一定的平衡.為與基于聚類有效性函數(shù)的模糊聚類優(yōu)化算法進行比較，本文采用類中距和類間距兩個性能指標進行對比實驗：

為了與基于聚類有效性函數(shù)對FCM算法的聚類中心個數(shù)尋優(yōu)進行比較，本文采用圖2中的數(shù)據(jù)集合開展研究.

表1為聚類數(shù)為2～6時，6個有效性指標在m＝2下的驗證結(jié)果.從表1可以看出針對圖2這個空間分布極為簡單的數(shù)據(jù)集只有指標VXB、VFS和VK找到正確的模糊數(shù)4.這就說明并不是所有的有效性函數(shù)對給定的數(shù)據(jù)集均為有效.采用本文所提的基于變個體長度的SFLA－FCM算法，在10次隨機運行中均得到正確聚類中心數(shù)4，并且類中距和類間距平均值分別為5.118 2和1.737 4，較好地在模糊劃分的緊密性和分離性之間取得折中.

圖2 具有4個聚類中心的含噪聲測試數(shù)據(jù)集Fig.2 Test data set with noises having four cluster centers

4.2 基于改進的SFLA－FCM的產(chǎn)品族設(shè)計產(chǎn)品平臺的選擇和設(shè)計是產(chǎn)品族設(shè)計的核

心，其中模塊化的設(shè)計涉及實現(xiàn)產(chǎn)品各項功能結(jié)構(gòu)的最終整合，而在p個功能模塊之間大多具有如下關(guān)系［11］：（1）每個功能模塊對其余功能模塊提供支撐；（2）每個功能模塊從其余功能模塊接受支撐.這樣，任意兩個功能模塊之間的關(guān)系可采用p×p的模塊關(guān)聯(lián)矩陣進行描述.

表1 不同聚類有效性函數(shù)數(shù)據(jù)集結(jié)果（m＝2）Tab.1 Results of data set under different clustering valid function（m＝2）

本文所研究的紙幣清分機是銀行系統(tǒng)對回籠紙幣進行自動清分處理的高端設(shè)備.典型紙幣清分機主要功能模塊有電機模塊（a）、嵌入式模塊（b）、網(wǎng)絡(luò)模塊（c）、操作模塊（d）、直線－滾輪式走鈔模塊（e）、進鈔模塊（f）、輔助模塊（g）、UV傳感器（h）、磁性傳感器（i）、紅外光學(xué)傳感器（j）、熒光傳感器（k）、圖像傳感器（l）、測厚傳感器（m）和電解質(zhì)傳感器（n）.

本文采用文獻［11］所提的部件關(guān)聯(lián)矩陣標準化處理方法對部件關(guān)聯(lián)矩陣進行標準化：

式中：maxxij和minxij分別表示某一部件同其他部件的最大和最小關(guān)聯(lián)特征值；wi為功能模塊i的關(guān)聯(lián)權(quán)重變量.這樣，對紙幣清分機進行標準化處理后的模糊矩陣如表2所示.

表2 部件量化后關(guān)聯(lián)模糊矩陣表Tab.2 Coefficient fuzzy matrix table after component quantity

針對如表3所示的標準化后的部件關(guān)聯(lián)模糊矩陣表，采用本文所提出的基于變個體長度的SFLA來同時優(yōu)化FCM的聚類數(shù)和聚類中心，得到的最優(yōu)聚類數(shù)為3.同時得到最優(yōu)模糊矩陣U.狀態(tài)變量h以相應(yīng)的相對隸屬度值作為權(quán)重，基于式（21）求得各個功能模塊歸屬各個類別的特征值H（u）表，這樣就得出了最優(yōu)的功能模塊如表4所示分類結(jié)果.

分析c＝3時的功能模塊聚類結(jié)果，所研究金融機具紙幣清分機的功能模塊可歸為3類：｛（a，e，f）；（b，c，d，g）；（h，i，j，k，l，m，n）｝.這樣就可以根據(jù)金融機具生產(chǎn)企業(yè)的實際情況和特點，選取某些模塊作為產(chǎn)品族設(shè)計的核心平臺，例如將電機模塊、直線－滾輪式走鈔模塊以及進鈔模塊等作為構(gòu)成產(chǎn)品平臺的部件.

表3 標準化模糊矩陣表Tab.3 Standardized fuzzy matrix table

表4 c為3時最優(yōu)模糊矩陣和相對隸屬度表Tab.4 Optimum fuzzy matrix and relative membership table under c＝3

5 結(jié) 論

（1）提出用變個體長度的混合蛙跳算法對模糊C均值聚類算法的模糊聚類數(shù)和聚類中心同時進行優(yōu)化.針對FCM自身特點，采用切斷算子和拼接算子對個體進行重新組合而形成新個體，然后采用ISODATA迭代算法進行個體的局部尋優(yōu)以加快收斂速度.

（2）建立了紙幣清分機產(chǎn)品開發(fā)過程中的部件關(guān)聯(lián)矩陣，采用所提改進的SFLA－FCM算法來進行產(chǎn)品族的設(shè)計.仿真研究結(jié)果表明所提方法為產(chǎn)品族模塊化設(shè)計提供了定量數(shù)學(xué)分析和快速配置的理論依據(jù).

［1］Tseng M M，Jiao J X.A variant approach to product definition by recognizing functional requirement patterns［J］.Journal of Engineering Design，1997，8（4）：329－340.

［2］Arbelaitz O，Gurrutxag I，Muguerza J，etal.An extensive comparative study of cluster validity indices［J］.Pattern Recognition，2013，46（1）：243－256.

［3］Falasconi M，Gutierrez A，Pardo M，etal.A stability based validity method for fuzzy clustering［J］.Pattern Recognition，2010，43（4）：1292－1305.

［4］LI Chao－shun，ZHOU Jian－zhong，KOU Pan－gao，etal.A novel chaotic particle swarm optimization based fuzzy clustering algorithm ［J］.Neurocomputing，2012，83（15）：98－109.

［5］HE Yao－yao，ZHOU Jian－zhong，KOU Pan－gao，etal.A fuzzy clustering iterative model using chaotic differential evolution algorithm for evaluating flood disaster［J］.Expert Systems with Applications，2011，38（8）：10060－10065.

［6］XIE Xuan－li，Beni G.A validity measure for fuzzy clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（8）：841－847.

［7］Fukuyama Y，Sugeno M.A new method of choosing the number of clusters for the fuzzycmeans method［C］／／Proceedings of the International Conference of the Fifth Fuzzy System Symposium.Kobe：The Japan Society of Applied Physics，1989：247－250.

［8］Kwon S H.Cluster validity index for fuzzy clustering［J］.Electronics Letters，1998，34（22）：2176－2177.

［9］Chen M Y，Linkens D A.Rule－base self－generation and simplification for data－driven fuzzy models［J］.Fuzzy Sets and Systems，2004，142（2）：243－265.

［10］Alp Erilli N，Yolcu U，E，etal.Determining the most proper number of cluster in fuzzy clustering by using artificial neural networks［J］.Expert Systems with Applications，2011，38（3）：2248－2252.

［11］王愛民，孟明辰，黃靖遠.聚類分析法在產(chǎn)品族設(shè)計中的應(yīng)用研究［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2003，15（3）：343－347.

WANG Ai－min，MENG Ming－chen，HUANG Jingyuan.Research on clustering analysis for product family design［J］.Journal of Computer－Aided Design＆Computer Graphics，2003，15（3）：343－347.（in Chinese）

［12］Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm［J］.Journal of Water Resources Planning and Management，2003，129（3）：210－225.

［13］Amiri B，F(xiàn)athian M，Maroosi A.Application of shuffled frog－leaping algorithm on clustering［J］.The International Journal of Advanced Manufacturing Technology，2009，45（1－2）：199－209.

［14］杜長海，黃席樾，楊祖元，等.改進的FCM聚類在交通時段自動劃分中的應(yīng)用［J］.計算機工程與應(yīng)用，2009，45（24）：190－193.

DU Chang－h(huán)ai，HUANG Xi－yue，YANG Zu－yuan，etal.Application of improved fuzzyC－means clustering in automatic programming traffic intervals［J］.Computer Engineering and Applications，2009，45（24）：190－193.（in Chinese）

［15］Kannan S R，Devi R，Ramathilagam S，etal.Some robust objectives of FCM for data analyzing［J］.Applied Mathematical Modelling，2011，35（5）：2571－2583.

［16］WANG Jie－sheng，GAO Xian－wen.Optimization of fuzzyC－means clustering by genetic algorithms based on sizable chromosome［C］／／Proceedings of 2009Chinese Conference on Pattern Recognition.New York：IEEE Press，2009：1－5.

Product family design method based on fuzzyC－means clustering method optimized by improved shuffled frog leaping algorithm

CUI Wen－h(huán)ua＊1，2， LIU Xiao－bing1， WANG Wei1， WANG Jie－sheng2
（1.School of Control Science and Engineering，Dalian University of Technology，Dalian 116024，China；2.School of Electronic and Information Engineering，University of Science ＆Technology Liaoning，Anshan 114044，China）

The decision of product platform in the modularized product family design is proposed based on fuzzyC－means（FCM）clustering algorithm optimized by the improved shuffled frog leaping algorithm（ISFLA）.The component coefficient matrix based on the data collected in the product exploitation process is set up.The number of fuzzy clustering and cluster centers are optimized by sizable－individual SFLA to obtain the optimized fuzzy partition of the components of the product.Cut operator and splice operator are used to combine the individuals to form a new individual.ISODATA

iterative algorithm is adopted to carry through the local optimization.The simulation results of the product family design of the paper currency sorter show that the proposed method provides the theoretical basis of the quantitative mathematic analysis and fast configuration for the product modularized design.

paper currency sorter；product family；product platform；shuffled frog leaping algorithm；fuzzyC－means clustering

TP12

A

1000－8608（2013）05－0760－06

2012－05－09；

2013－07－20.

遼寧省教育廳創(chuàng)新團隊基金資助項目（2008T091）；遼寧省科技攻關(guān)計劃資助項目（2010220001）.

崔文華＊（1968－），女，教授，E－mail：cwh＠julong.cc；劉曉冰（1956－），男，教授，博士生導(dǎo)師.