針對KMC 局部最優問題的飛蛾捕焰優化方法*

郭 璐，許 哲，黃 鶴，張少帥，陳永安

（1.西北工業大學無人機系統國家工程研究中心，西安 710072；2.西安愛生技術集團公司，西安 710065；3.中國電子科技集團公司第二十研究所，西安 710068；4.長安大學電子與控制工程學院，西安 710064）

0 引言

聚類分析是統計學習領域的重要組成部分，可以針對不同的對象分析差異，并且能夠根據某種特定的規則進行模式分類。聚類的應用廣泛，擁有很好的發展前景。隨著社會發展對數據精度要求的不斷提高，如何提高算法的聚類精度是廣大學者一直以來的研究熱點［1］。經典K-means 聚類（K-means Clustering，KMC）算法存在易受初始聚類中心和異常數據影響的缺陷［2］，研究人員提出利用特征關聯度對傳統K-means 算法的初始聚類中心進行優化［3］和基于自適應權重的聚類算法［4］。

群智能優化算法作為新興的演化計算技術取得了高速發展。2015 年Mirjalili 根據飛蛾總是圍繞火焰做對數螺旋曲線軌跡的行為提出了一種飛蛾捕焰算法（Moth-flame Optimization，MFO）［5-6］。目前，MFO 算法已經在網絡［7］、電力［8］、以及加工制造［9］等方面有了具體的應用，并在此基礎上結合其他算法進行了設計。文獻［10］將粒子群優化算法的速度更新方式與MFO 算法的位置更新方式相結合，使飛蛾群向歷史最優解和全局最優解快速收斂，避免了陷入局部最優解的目的。文獻［11］將MFO 算法位置更新的方式和Lévy 飛行搜索策略結合，達到增強局部搜索能力的目的，使得收斂速度和求解精度大幅度提高。文獻［12］提出了一種縱橫交叉混沌捕焰優化算法，采用縱橫交叉機制，將火焰之間以及火焰不同維度之間相互結合，同時引入混沌算子，進一步提高了算法精確度和跳出局部最優能力［10］。目前，針對MFO 算法本身改進的文獻并不多，MFO算法的收斂速度和精度并沒有充分得到提升。同時，MFO 算法得自身特點非常適用于聚類，可以使求解的聚類中心更加精確，但目前并沒有研究者將MFO 算法設計在聚類的應用中。

因此，本文提出一種快速的飛蛾捕焰（Rapid Moth-flame Optimization，RMFO）算法，解決了經典MFO 算法求解復雜函數時收斂速度慢與精度較低等問題。同時，設計了一種基于改進飛蛾捕焰算法的K 均值交叉迭代聚類方法，提升MFO 算法的全局收斂能力和收斂速度，并且能夠改善聚類性能。

1 飛蛾捕焰優化算法

MFO 算法是根據飛蛾圍繞火焰做對數螺旋曲線運動的生物學原理構建數學模型，經過多次位置更新迭代之后求解得到最優火焰解。在飛蛾捕焰優化算法中，矩陣M 表示飛蛾（Moth）的集合，矩陣F表示火焰（Flame）的集合。與之對應的是，矩陣OM表示飛蛾集合M 的適應度值，矩陣OF 表示火焰集合F 的適應度值。飛蛾和火焰都是算法的解，不同的是飛蛾是在搜索空間中的實際搜索的主體，而火焰則是用來存儲飛蛾搜索的最優解［13］。

1.1 初始化種群

設飛蛾種群集合M 的大小為n×d，如式（1）所示，n 表示飛蛾總數，d 表示一個樣本的特征數或是待尋優變量的個數（維度）。

其中，Mi=［mi1，mi2，…，mid］代表的是第i 只（i=1，2，…，n）飛蛾的狀態，Mij代表的是第i 只飛蛾在第j（j=1，2，…，d）維變量空間中所處的位置。

飛蛾的適應度值OM 的大小為n×1，如式（2）所示。

其中，OMi=［omi］表示第i 只（i=1，2，…，n）飛蛾的適應度值，是由Mi通過相應的適應度函數（尋優目標函數）得到的。

設火焰集合F 的大小與飛蛾M 的大小相同，為n×d。如式（3）所示。

其中，Fi=［fi1，fi2，…，fid］表示第i 個（i=1，2，…，n）火焰的狀態，Fij表示第i 個火焰在第j（j=1，2，…，d）維變量空間中所處的位置。

火焰的適應度值OF 的大小同樣為n×1，如式（4）所示。

其中，OFi=［ofi］表示第i（i=1，2，…，n）個火焰的適應度值。OF 矩陣是OM 矩陣中每個量排序之后的結果，所以F 矩陣是M 矩陣根據OF 矩陣的排序得到的結果，這說明火焰F 是飛蛾M 在當前迭代搜索中的最優解。

1.2 捕焰過程

飛蛾在圍繞火焰做對數螺旋曲線運動時的位置更新機制可以分為兩個過程：飛蛾捕焰、飛蛾棄焰。

1）飛蛾捕焰：飛蛾Mi在搜索空間中尋找火焰的位置時，飛蛾會根據自己的趨光生物特性來尋找與它距離最近的火焰Fi，然后在每一次的位置更新迭代中圍繞火焰做對數螺旋曲線運動，如圖1 所示，螺旋線的起點為飛蛾初始化位置，螺旋線的終點即為最優解。

圖1 飛蛾運動軌跡圖

定義對數螺旋曲線如式（5）所示：

2）飛蛾棄焰：為了提高算法尋優的收斂速度并且使得所有的飛蛾盡可能收斂于一個最優火焰解中，所以應該使火焰的數目自適應地減少，讓飛蛾舍棄適應度值差的火焰。這樣也可以避免飛蛾丟失最優解的情況?；鹧孀赃m應減少如式（6）所示：

其中，flameno 為當前火焰的數量，N 為飛蛾種群的總數量，l 為當前的迭代次數，T 為規定的最大迭代次數。

2 K 均值聚類算法

K 均值聚類的目的是將給定的數據集X={X1，X2，…，Xn}劃分成K 個類的子集{C1，C2，…，Ck}，執行過程中初始聚類中心的選取很重要，直接影響聚類的結果，導致結果陷入局部最優解。聚類中心Cj的計算式如式（7）所示：

3 改進的飛蛾捕焰算法

本文針對經典MFO 算法的不足，提出了一種RMFO 算法，分別將飛蛾種群的初始化和飛蛾的適應度函數進行改進，通過設計最大最小距離積法初始化飛蛾種群，可以克服原始飛蛾捕焰算法初始化的隨機性，避免算法陷入局部最優解。同時，結合飛蛾捕焰迭代搜索過程以及KMC 算法思想，提出一種新的適應度函數。

3.1 最大最小距離積法初始化

飛蛾捕焰算法的搜索起點是飛蛾群的初始位置，所以選取尤為重要。經典飛蛾捕焰算法的初始飛蛾群采用隨機初始化易導致算法陷入局部最優解。同時，飛蛾種群的個體解往往會遠離最優解，使得算法收斂速度變慢，收斂效率變低，增加了算法的時間復雜度。針對這一問題，本文設計了最大最小距離積法對飛蛾群進行初始化，不僅可以解決飛蛾群初始化的隨機性，而且也可以在K 均值聚類中降低對初始點的敏感性。通過最大最小距離積法得到k 個初始飛蛾的步驟描述如下：

1）從飛蛾種群集合M 中隨機選取一只飛蛾作為第一個初始點Z1，將其加入集合Z 并從集合M 中刪除；

2）計算更新后M 中所有元素到Z1的距離，選取距離Z1最大的元素為Z2；

3）將Z2加入集合Z 并從集合M 中刪除；

4）分別計算更新后M 中元素到Z 中各個元素的距離并存入Temp 中；

5）計算M 中每個元素對應的Temp 的最大值與最小值的乘積，取該值最大對應的元素存入集合Z 中并從集合M 中刪除。若Z 中元素個數小于k，則轉到步驟3；若Z 中元素個數大于k，則初始點選取結束，輸出包含k 個初始點的集合Z，即為得到的初始點。

其中，k 是規定的聚類個數或是給定的初始點個數，Z 初始時是空集，存儲等待加入的k 個初始點的集合，Temp 是存儲Z 中各個元素到M 中各個元素距離的數組。

從以上步驟可以看出，最大最小距離積法將M中每個元素對應的Temp 最大值與最小值乘積中的最大值為初始點，不但能夠使初始點的分布比較稀疏，而且可以選取到點密度比較大的點。

3.2 新的適應度函數

適應度函數將引導群體進化的方向，直接決定了群體的進化行為、迭代的次數和解的質量，不同的適應度函數會得出不同優劣程度的解［14］。本文提出一種新的適應度函數，如式（9）所示。

從式（8）可以看出適應度越小，所解出的聚類中心點與該類中其他點的歐式距離的差值之和越小，也就是求解出的聚類中心越精確。

4 RMFO 優化KMC 算法

本文提出了基于RMFO 優化的KMC 算法，主要過程是：通過RMFO 算法先進行一次迭代，得到新的聚類中心作為KMC 算法的初始聚類中心，再將KMC 運行的結果作為改進MFO 算法的初始點。兩種算法交叉迭代進行，最終找到最優聚類中心以及最優解。

算法的具體步驟描述如下：

1）輸入標準數據集即飛蛾種群集合M，根據數據集類別的個數確定該數據集中類的個數k；

2）根據最大最小距離積法確定每個類的初始聚類中心點；

3）計算飛蛾群中的某個點到每個初始聚類中心的距離，當該點與某一初始聚類中心的距離最小時，則把該點與這個初始聚類歸并為一類，依此將所有的點歸并到相應的初始聚類中；

4）使用MFO 算法確定步驟3）中歸并之后的每個類的新聚類中心；

5）利用步驟4）得到的新的聚類中心對飛蛾群進行K 均值迭代聚類，根據其他點與聚類中心點的歐式距離再次進行聚類劃分，用每一類的新的聚類中心再次更新當前的飛蛾群，當迭代次數沒有達到設定的迭代次數時，轉向步驟3），直到達到設定的迭代次數，結束。

主程序流程圖如圖2 所示。

圖2 主程序流程圖

5 實驗結果分析

實驗平臺采用CPU 為Intel Core i5 2.60 GHz、內存為4 GB 的計算機，操作系統為Windows 7，編譯軟件為Matlab R2014a。選擇的數據集為UCI 國際通用測試數據庫，是專門用來聚類算法的國際的通用的數據庫。實驗采用Iris、Wine 和Glass 3 種數據集，主要特征如表1 所示。

表1 標準數據集特征

5.1 RMFO 算法性能測試

對RMFO 算法進行性能測試比較，分別在3 種數據集上使用MFO 算法和RMFO 算法進行聚類，對比聚類效果并進行數據分析。兩種算法的參數設置如下：在Glass、Iris 最大迭代次數為200 次，在Wine 數據集上最大迭代次數為100 次，飛蛾種群的規模為30，數據集中的聚類數目如表1 所示。采用適應度來評價改進算法的性能，則兩種算法在3 種數據集上聚類的實驗結果圖如下頁圖3 所示?？梢钥闯?，改進的RMFO 算法的適應度值比經典MFO算法的適應度值要小，收斂速度更快。RMFO 算法在初始值的選取上使用最大最小距離積法，避免了初始值的隨機性，不易使算法陷入局部最優解，得到的最優解更加精確。RMFO 算法確實比MFO 算法在求解的最優解方面更有優勢。但從圖3（c）中看出，兩種算法很有可能陷入局部最優解，所以需要將RMFO 算法和K 均值算法進行混合迭代。

圖3 RMFO 實驗結果

5.2 基于RMFO 優化的KMC 算法性能評價

將KMC 算法、基于RMFO 優化的KMC 算法和文獻［15］算法分別對3 種數據集進行聚類分析。其中基于RMFO 優化的KMC 算法參數設置為：飛蛾種群的規模為30，算法在3 種數據集上聚類的最大迭代次數都為100 次。圖3 和圖4 是基于RMFO 優化的KMC 算法在3 種數據集的運行結果，可以看出，算法能夠很快迭代到最優解的位置，適應度值變化幅度不大。圖3 還可以看出算法能夠很好地避免局部最優解，這與MFO 算法本身的飛蛾棄焰行為和基于RMFO 優化的KMC 算法混合迭代每一次聚類的重新劃分有很大關系。對比實驗表明，本文算法迭代次數更少，聚類過程中的收斂速度快，能夠很好地跳出局部最優解尋找出全局最優解，適應度變化幅度不大，穩定性更強。

圖4 在Iris 和Glass 數據集上的結果

圖5 在Wine 數據集上的運行結果

采用KMC 算法、基于RMFO 優化的KMC 算法、文獻［15］算法，分別對3 種數據集進行聚類分析，實驗結果如表2～表4 所示?？梢钥闯鯧MC 需要的迭代次數過多，算法達到穩定狀態耗時過長。同時，由于KMC 算法依賴初始點的選取，所以很容易陷入局部最優解，使所得適應度值并不是最優解，全局搜索能力較差。文獻［15］在聚類算法中引入模糊控制的概念，使用模糊聚類算法，使得迭代曲線趨于平滑，相比KMC 算法，文獻［15］的迭代次數較少，但由于初始點選取的隨機性，仍未達到全局最優解，使所得聚類中心點不夠準確。本文算法改進了MFO 算法的初始化和適應度公式構造方法，并通過與KMC 算法混合迭代使收斂速度加快，迭代次數減少，適應度值最小，具有跳出局部最優解的能力，全局搜索能力較佳，解得的聚類中心更加精準。

表2 不同算法在Glass 數據集上的對比結果

表3 不同算法在Iris 數據集上的對比結果

表4 不同算法在Wine 數據集上的對比結果

6 結論

1）本文從飛蛾群的初始化以及適應度函數兩個方面對MFO 算法進行了改進，提出了RMFO 算法，克服了原始飛蛾捕焰算法初始化的隨機性，解決了飛蛾的個別解較差和容易陷入局部最優解等問題。

2）將RMFO 算法和KMC 算法進行交叉迭代，構建新的基于RMFO 優化的KMC 算法，克服了KMC 算法由于初始化的隨機性使得初始點敏感，使KMC 算法的迭代次數大大減少，避免了陷入局部最優解。

3）對比結果表明了本文算法的有效性，通過引入改進的飛蛾捕焰算法，提升K 均值聚類算法全局搜索能力，提高了算法的魯棒性，并且解決了KMC算法由于初始化的隨機性使得初始點敏感的問題。

4）保證聚類效果的條件下，效率當然是越高越好。如何進一步降低基于RMFO 優化的KMC 算法復雜度將是本文下一步研究方向。