飛蛾撲火優化算法在聚類分析中的應用

李志明

(廣西科技師范學院 數學與計算機科學學院，廣西 來賓 546199)

0 引 言

聚類[1]是一種流行的數據分析和數據挖掘技術。聚類分析是一種無監督的學習過程，它的任務是將類似的對象分組成多個類組。簡單的說，聚類分析問題的任務就是把一些對象按照某種規則分成不同的組，分組完成之后，每個組里面的對象具有較高的相似度，而不同組之間的對象具有較高的相異性。聚類算法是基于樣本之間距離或相似性的自動分類，且聚類技術已經成功應用于諸多實際的問題當中，如數據挖掘[2]、模式識別[3]、圖像分割[4-5]等。分組聚類方法是指通過優化某些標準將數據劃分成預定數量的簇。K-means是最流行的分組聚類方法[6-7]，不過K-means高度依賴于初始狀態，并且容易陷入局部最優。

為了有效地解決聚類分析問題，國內外一些學者嘗試用新興的群智能算法來求解這類問題。2011年，Hatamlou等采用了一個大爆炸算法進行數據聚類[8]；2014年，陳信等提出一種改進型猴群算法，并將其應用到聚類分析中，取得了比K-means等更好的性能[9]；2015年，張森等將新型灰狼優化算法應用于聚類分析中，取得了良好的成績[10]；2016年，王睿將基于蜜蜂傳粉策略的花授粉算法用于求解聚類分析問題，均取得了很好的成績[11]；2019年，凌靜等提出結合模擬退火算法的K-means聚類方法，其聚類準確性比一般K-means方法和遺傳K-means方法都要高[12]。

1 飛蛾撲火優化算法

飛蛾撲火優化算法(moth-flame optimization，MFO)是由學者Mirjalili于2015年提出的一種新型群智能優化算法，其靈感來源于一種特殊的導航機制——橫向定位導航機制[13-14]。飛蛾在晚上飛行時，因其與月亮相距較遠，所以飛蛾與月亮保持固定的角度即可保證自己沿直線飛行。

然而在現實中，飛蛾與火焰相距很近，當飛蛾看到火焰發出的光時，便會試圖與其保持固定的角度飛行，而由于這些人造光相比月亮光距離很近，所以，飛蛾仍然保持與人造光的固定角度不變飛行時，飛蛾便會最終向人造光處收斂。

在MFO算法中飛蛾是候選解，飛蛾的集合用矩陣M表示，OM存儲相對應的適應度值。算法中另外一個核心組件火焰用F表示，OF存儲相對應的適應度值，并且矩陣M和F具有相同的維數。在MFO算法中，飛蛾或火焰都是解，它們的不同就在于每一次迭代過程中更新方式的不同。飛蛾在搜索空間里是實際的搜索主體，而火焰為當前獲取的最佳位置。因此，每個飛蛾都會搜索一個火焰，在找到更好的解的情況下進行標記并更新，通過這種機制，飛蛾永遠不會失去它的最優解。

MFO算法用全局最佳的三元組表示如下：

MFO=(I,P,T)

(1)

通過函數I隨機產生一個飛蛾種群及相應的適應度值，其模型如下：

I:φ→{M,OM}

(2)

P是使飛蛾在搜索空間里移動的主函數，它接受矩陣M，并返回更新后的值。

P:M→M

(3)

當滿足終止準則時，T函數為真；如果不滿足，則T函數為假。

T:M→{true,false}

(4)

I函數初始化之后，P函數迭代運行直到T函數返回真。為了精確地模擬飛蛾的行為，可使用下式對飛蛾相對于火焰的位置進行更新。

Mi=S(Mi,Fj)

(5)

其中，Mi為第i只飛蛾，Fj為第j個火焰，S為螺旋形函數。

選取對數螺旋線作為飛蛾的主要更新機制，其對數螺線描述如下：

S(Mi,Fj)=Di·ebt·cos(2πt)+Fj

(6)

其中，Di為第i個飛蛾與第j個火焰的距離，b為定義對數螺旋線形狀的常數，t為區間[-1，1]上的隨機數。其中D由式(7)計算求得。

Di=|Fj-Mi|

(7)

式(6)模擬了飛蛾的移動路徑，并可以確定飛蛾的下一個位置。參數t定義為飛蛾在下一個位置應當接近火焰的程度(t=-1是最接近火焰的位置，t=1為距離火焰最遠的位置)。在式(6)中僅僅需要飛蛾朝向火焰移動，卻也容易使MFO算法陷入局部最優。為了避免這種情況，每個飛蛾必須使用式(6)中的火焰來更新它們的位置。每次更新火焰列表后，火焰便會根據它們的適應度值來排序，然后飛蛾更新它們相對于相應火焰的位置。第一只飛蛾總是更新相對于最優火焰的位置，而最后一只飛蛾更新列表中相對于最差火焰的位置。

針對在搜索空間中相對于n個不同位置飛蛾的位置更新，有可能降低了最有希望解的開采，提出一種適合于火焰數量的自適應機制。使用式(8)使火焰數量在迭代過程中自適應減少：

(8)

其中，l為當前迭代次數，N為火焰數量的最大值，T為最大迭代次數。

2 基于單純形法的飛蛾撲火優化算法流程

單純形法又稱為可變多面體搜索法，它具有計算量小、搜索速度快等優點，是一種傳統的處理無約束最優化問題的方法。在標準飛蛾撲火優化算法的基礎上使用單純形法搜索策略，可以增強算法的種群多樣性，使算法尋找到更好的位置。SMMFO算法的簡易流程如下：

Initialize the position of moths

While(Iteration<=Max_iteration)

Update flame no using Eq.(8)

OM=FitnessFunction(M);

if iteration==1

F=sort(M);

OF=sort(OM);

else

F=sort(Mt-1,Mt);

OF=sort(Mt-1,Mt);

end

for i = 1:n

for j=1:d

Update r and t

Calculate D using Eq.(7) with respect to the corresponding moth

Update M(i,j) using Eqs.(5) and (6) with respect to the corresponding moth

end

for each search agent

Update the position of the current search agent using Simplex Method

end

end

3 仿真實驗

3.1 仿真環境

為了驗證SMMFO在解決聚類分析問題上的有效性，選取了8個常見的數據集，其中包括2個人工數據集和6個現實數據集[11]。

8個數據集描述如下(數據集中數據項個數為N，每條數據的屬性數為d，數據集要分類的數目為K)。人工數據集1(N=250，d=3，K=5)中的每個屬性值都服從均勻分布，即分別服從(85,100)、(70,85)、(55,70)、(40,55)和(25,40)上的均勻分布。人工數據集2(N=600，d=2，K=4)，其中的600條數據項中的屬性值均服從二維隨機分布。Iris數據集(N=150，d=4，K=3)來自于150個隨機樣本，每條數據由四個屬性構成。Wine數據集(N=178，d=13，K=3)取自于對意大利相同地區的三種不同品種的酒進行化學分析，共有178條數據項，每個數據項有13個屬性。Seeds數據集(N=210，d=7，K=3)，共有210個數據項，每項數據包含7個屬性，并且可分為3類，每類各含有70條數據集。Heart數據集(N=270，d=13，K=2)包含270個數據項，每個數據項包含13個屬性，該Heart數據集來源于心臟病數據庫，不過采用了不同的表達形式。Balance Scale數據集(N=625，d=4，K=3)根據平衡性分為向左傾斜、向右傾斜和平衡居中3類，每條數據項有left weight，left distance，right weight，right distance等4個屬性，根據兩個比重left weight×left distance和right weight×right distance的大小對數據項進行分類，若前者大，則該數據項為向左傾斜，若后者大，數據項為向右傾斜，否則數據項被歸到平衡居中里。Contraceptive Method Choice (CMC)數據集(N=1 473，d=10，K=3)為避孕方法選擇集，該數據集源自于1987年印度尼西亞進行的全國避孕患病率調查的一個樣本，目的是預測當前的避孕方法是無效的、短期有效的還是長期有效的。

以上8個數據集均有自己的特點，因此，對它們的實驗結果數據能充分反映算法的性能。另外，還選取了PSO[15]、ABC[16]、GGSA[17]、CS[18]等算法作為比較算法。

3.2 實驗結果與分析

各實驗結果如表1～表8所示，記錄了每個算法取得的最優值、最差值、平均值、標準差。從各表可以看出，在求解這8個測試集時，SMMFO均表現出了較好的性能。

表1 人工數據集1的20次獨立運行實驗結果

表2 人工數據集2的20次獨立運行實驗結果

表3 Iris數據集的20次獨立運行實驗結果

表4 Wine數據集的20次獨立運行實驗結果

表5 Seeds數據集的20次獨立運行實驗結果

表6 Heart數據集的20次獨立運行實驗結果

表7 Balance Scale數據集的20次獨立運行實驗結果

表8 CMC數據集的20次獨立運行實驗結果

由表1可知，對于人工數據集1，SMMFO所取得的平均值為1 985.13，僅次于CS的185.017，而且SMMFO的最優值是148.254，均優于其他算法。同樣在人工數據集2中，SMMFO與PSO，GGSA均取得了513.903 5的較好成績，而且其標準差也是比較小的。對于Iris測試集，由表3可知SMMFO在最優值、最差值和平均值方面都是96.655 48，而且標準差達到了9.392 8e-10，這表明改進型SMMFO具有較強的魯棒性，雖然PSO與GGSA給出的最優解也達到了和SMMFO一樣的成績，但是SMMFO在最差值、平均值和標準差方面均優于PSO與GGSA。表4給出了Wine測試集的結果，其中SMMFO取得的最優值、最差值、平均值和標準差分別是16 292.18，16 294.17，16 292.92和0.843 7，這比PSO、ABC、GGSA、CS、MFO和K-means得出的結果都要優秀。對于Seeds測試集，SMMFO的最優值、最差值、平均值均取得了311.121 1這個不錯的成績，而且其標準差為2.1e-11，這是比其他算法都要優秀的，雖然GGSA在最優值方面也取得了311.121 1，但是在其他方面卻要比SMMFO遜色很多。對于Heart測試集，SMMFO取得的最優值、最差值和平均值分別為10 622.98，10 623.18，10 623.00，這樣的結果比其他算法都要好，在標準差方面，SMMFO的標準差為0.061 56，在這些算法中也是最優秀的。對于Balance Scale測試集，SMMFO所得到的最優值和平均值分別是1 423.820和1 424.354，這兩個結果是要優于其他算法的，并且SMMFO取得的標準差也是小于其他算法的。對于測試集Contraceptive Method Choice (CMC)，SMMFO得到的最優值、最差值和平均值均為523.54，這一結果是優于其他算法的，而且其標準差達到了6.04e-12，這個結果更是比其他算法要優秀很多。通過以上數據分析可知，改進型SMMFO算法具有較強的搜索能力，并且在聚類分析方面是具有優勢的。

圖1是SMMFO算法對人工數據集2的聚類結果，從圖中可以看出，新算法取得了比較理想的成績。

圖1 人工數據集2聚類結果

4 結束語

針對飛蛾撲火優化算法容易陷入局部最優及由種群多樣性低導致的全局尋優能力不足等缺陷，提出了基于單純形法的飛蛾撲火優化算法，即在飛蛾撲火優化算法的基礎上，加入了一種經典的傳統優化方法——單純形法。改進后的SMMFO算法不僅了提高了種群多樣性，而且加強了算法的局部搜索能力，并使其收斂速度大大加快。通過與其他六個算法的對比實驗可知，SMMFO不僅在全局搜索方面表現不俗，更是在局部搜索方面表現出了良好的性能，所以，改進型SMMFO是一種非常有效和實用的方法。