基于扇形趨利果蠅優(yōu)化算法改進的FS-K聚類算法*

曹珍貫, 楊 遜, 呂旻姝, 朱靖雯

(安徽理工大學 電氣與信息工程學院， 安徽 淮南 232001)

0 引 言

果蠅算法(FOA)是由潘文超[1]在2012年提出的，是基于仿生果蠅群體覓食行為的尋優(yōu)算法；文獻[2]對果蠅算法和其他算法進行了對比，結(jié)果表明果蠅算法簡單、參數(shù)少、運行效率高，并且在進化次數(shù)低時[2]，果蠅算法比混合跳蛙算法[3]、和聲算法、人工蜂群算法的收斂精度和收斂速度都高，適合于實際應(yīng)用或與其他算法結(jié)合進行分階段優(yōu)化。但是，F(xiàn)OA和其他全局優(yōu)化算法一樣，標準果蠅優(yōu)化算法也容易陷入局部最優(yōu)，特別對于高維多極值復(fù)雜優(yōu)化問題，在搜索計算后期收斂速度變慢，收斂精度降低。FOA算法目前的優(yōu)化途徑大致分為兩種：對算法自身的改進；將FOA算法與其他算法結(jié)合，產(chǎn)生新算法。其中文獻[4-5]將果蠅算法的固定步長改進為自適應(yīng)步長；文獻[6]將果蠅群分為搜索果蠅和跟隨果蠅，分別進行全局和局部搜索；文獻[7]將FOA算法與差分算法相結(jié)合，提高果蠅種群多樣性；文獻[8-9]也都是通過與其他算法相結(jié)合，彌補果蠅算法缺陷。智能群算法的改進應(yīng)該遵循“內(nèi)部完善-外部提升”[10]，但是目前少有學者對果蠅算法自身的搜索特性進行改進。

針對上述問題，提出了一種基于扇區(qū)搜索機制的果蠅優(yōu)化算法，并將該方法應(yīng)用于K-means算法優(yōu)化。本文首先介紹了果蠅算法工作原理和扇區(qū)搜索機制搜索原理，然后將改進的果蠅算法用于K-means聚類算法的優(yōu)化，最后通過對比實驗驗證改進的FS-K算法具有更好的聚類效果。

1 果蠅算法

果蠅優(yōu)化算法是一種仿生果蠅群覓食行為的算法，模擬了果蠅群的兩種覓食搜索方式：嗅覺搜索(果蠅群捕捉空氣中的氣味逼近氣味源)和視覺搜索(果蠅個體在靠近氣味源的同時，使用視覺發(fā)現(xiàn)食物與種群位置，并靠近)[1]。

果蠅算法模擬果蠅覓食行為可以總結(jié)為以下7步:

Step1 初始化參數(shù)：群體規(guī)模S，最大迭代數(shù)M_G，隨機初始化群體坐標X_axis，Y_axis。

Step2 在群體坐標周圍，隨機生成S個果蠅個體，L為搜索半徑：

Xi=X_axis+L*(2*rand()-1)

Yi=Y_axis+L*(2*rand()-1)

Step3 由于無法得知食物位置，先計算果蠅個體與原點的距離Di，并將其倒數(shù)作為果蠅個體的味道濃度判定值Si:

Step4 將果蠅個體的味道濃度判定值Si帶入味道判定函數(shù)(即目標函數(shù))，計算果蠅個體味道濃度值Smli:

Smli=Function(Si)

Step5 找出該果蠅群體中味道濃度最佳的果蠅(最小值或最大值):

[b_Smlb_index]=min (Smli)

Step6 將果蠅的最佳味道濃度值b_Sml保存下來，并且記錄最優(yōu)個體的坐標值作為群體坐標：

X_axis=X(b_index)Y_axis=Y(b_index)

Step7 通過迭代運算，進行尋優(yōu)，重復(fù)執(zhí)行上面的 step 2—step 5，并判斷最佳味道濃度是否優(yōu)于前一迭代最佳味道濃度，并且判斷當前迭代次數(shù)是否小于最大迭代次數(shù)M_G，若是，則執(zhí)行Step 6。

2 扇形搜索果蠅算法

2.1 扇形搜索原理

FOA算法在進行隨機搜索時，其果蠅群產(chǎn)生機制是圍繞群體坐標進行隨機搜索:

Stacking算法既能集成各基分類器的訓練結(jié)果，也能組合各種可能決定分類的相關(guān)信息，因此普遍認為其性能優(yōu)于貝葉斯投票方法[41]。

Xi=X_axis+R,Yi=Y_axis+R

其中R為[-L,L]的隨機數(shù)。這種搜索機制在二維空間上表現(xiàn)為中點為種群坐標，邊長為2L的正方形，果蠅的搜索范圍如圖1所示。這樣的搜索機制使果蠅群在搜索時總是趨向于沿著單一方向移動，限制了果蠅群搜索方向的多樣性。

圖1 FOA果蠅群搜索范圍

針對果蠅群搜索范圍的不平衡性，本文提出一種扇形搜索機制，該機制在果蠅隨機搜索時，以果蠅群坐標為中心，把搜索區(qū)域劃分為n個扇區(qū)，每個扇區(qū)均生成果蠅個體。具體實現(xiàn)方法如下:

① 劃分扇區(qū)，其中t為扇區(qū)角度;

② 在群坐標周圍產(chǎn)生果蠅群，其中L為果蠅群搜索半徑，rand()為[0,1]的隨機值;

Xi=Xaxis+L*sin(t)*rand()Yi=Yaxis+L*cos(t)*rand()

對FOA和FS-FOA算法進行單獨5次的運行，對比了果蠅群的迭代路徑，如圖2。由圖2可以看出：FS-FOA果蠅群在搜索食物時，有4次向上方飛行，有1次向右方飛行，而FOA果蠅群的迭代方向較為單一，總是趨向于沿著Y=X的方向飛行。說明基于扇形搜索機制的果蠅群在尋找食物源時，在種群前進方向上的選擇性增加了，相較于FOA算法，F(xiàn)S-FOA算法的果蠅群總是朝著味道濃度最大的方向前進，而FOA算法在迭代中受到搜索范圍的影響，方向單一，無法朝著味道值最優(yōu)的方向前進，使得FOA算法的收斂較慢，在高維度函數(shù)優(yōu)化問題中，還會陷入局部最優(yōu)。

圖2 FS-FOA果蠅群搜索范圍

2.2 果蠅趨利特性

在自然界，果蠅在覓食過程中，其并不是隨機在一個范圍搜索，而是多數(shù)果蠅朝著食物源的方向飛行，少數(shù)果蠅向著其他方向搜索。受此啟發(fā)，F(xiàn)S-FOA對果蠅個體賦予了不同的性質(zhì)：趨利性和盲從性。盲從果蠅在果蠅群坐標周圍隨機搜索，趨利果蠅則更有方向性，總是朝著食物源一側(cè)快速飛行，在食物源單一的情況下，趨利果蠅能夠幫助算法減少無效迭代并快速收斂，在相同的迭代次數(shù)下，F(xiàn)S-FOA算法總能達到更高的收斂精度。

趨利果蠅的個數(shù)由趨利因子R決定，趨利果蠅個數(shù)q=S*R，其中R∈[0，1]，R取值越大，果蠅的趨利性越強，但是R的取值不應(yīng)超過0.5，超過0.5會導(dǎo)致果蠅群忽略對味道源方向的判別。趨利果蠅的方向由趨利果蠅的個數(shù)決定，其生成方法如下：

(1)

趨利果蠅的搜索步長采用自適應(yīng)步長，其步長值計算如式(2)所示：

Lq=L*ln(gen+3)

(2)

其中，L為盲目果蠅的搜索步長，gen為迭代時所屬方向的累計代數(shù)，gen的取值范圍為gen∈[0,M_G]。趨利果蠅的自適應(yīng)步長會使其擁有較高的加速度，能夠較快確定食物源確切方向并向目標源飛行，同時在確定了食物源方位后也不會因為有太大的步長而忽略食物源。趨利果蠅的生成策略如式(3)所示:

Xq=X_axis+Lq*sin(θ)Yq=Y_axis+Lq*cos(θ)

(3)

3 FS-FOA算法優(yōu)化K-means聚類算法

聚類算法是數(shù)據(jù)分析經(jīng)典算法，屬于無監(jiān)督學習算法，K聚類算法的目的是將數(shù)據(jù)分為指定類，盡可能使類內(nèi)樣本相似度大，類間相似度小。由于算法較簡單且有極強的收斂性，K-means聚類算法在處理大數(shù)據(jù)的應(yīng)用背景下有廣泛的應(yīng)用。但是K-means聚類對初始聚類中心的選取依賴性很大，極易陷入局部解。目前比較流行的優(yōu)化方法是使用群優(yōu)化算法對K-means算法進行優(yōu)化，減少聚類算法對初始聚類中心的敏感度[11]。

針對K-means對初始聚類中心依賴性大的缺點，本文結(jié)合FS-FOA較強的全局搜索能力與K-means算法的快速收斂性，將FS-FOA與K-means相結(jié)合產(chǎn)生一種新型聚類算法FS-K。FS-K相較于FOA能夠較快收斂，并通過迭代尋找全局最優(yōu)值，避免陷入局部最優(yōu)。

算法流程如下：

Step1 對FS-K算法進行初始化:種群個數(shù)Sizepop;最大迭代次數(shù)maxgen;聚類中心數(shù)Knum。

Step2 初始化果蠅群，從樣本中隨機抽取Knum個數(shù)據(jù)作為一個果蠅個體，每個果蠅個體表示一種聚類中心。

Step3 將果蠅個體作為K-means的初始聚類中心，收斂得到的聚類中心作為果蠅個體的初始位置。

Step4 數(shù)據(jù)點距離所屬聚類中心的歐式距離之和作為味道濃度判定函數(shù)，計算果蠅個體適應(yīng)度，選擇最優(yōu)果蠅個體作為種群初始坐標。

Step5 在種群坐標周圍隨機生成果蠅群，計算果蠅個體的味道濃度，記錄最優(yōu)個體的味道濃度以及位置信息。

Step6 判斷果蠅最優(yōu)個體是否優(yōu)于當前最優(yōu)，如果是，將最優(yōu)個體作為下一代的果蠅群坐標。

Step7 進入迭代尋優(yōu)并重復(fù)執(zhí)行Step5—Step6，直到達到最大迭代次數(shù)Maxgen。

4 試驗與分析

4.1 優(yōu)化函數(shù)測試

為了驗證FS-FOA的聚類效果，采用了5種常用的測試函數(shù)進行仿真測試。為了更好對比算法的優(yōu)化性能，將測試分為固定迭代次數(shù)和固定精度兩種。其中固定迭代次數(shù)試驗中，F(xiàn)OA與FS-FOA算法的最大迭代次數(shù)均取M_G=100，種群大小S=30，為保持FOA與FS-FOA的種群大小一樣，把FS-FOA中盲從果蠅數(shù)量設(shè)置為20，趨利果蠅數(shù)量設(shè)置為10。固定精度試驗是為了測試算法在目標精度下的迭代次數(shù)和運行時間，通過對比不同精度的函數(shù)優(yōu)化來對比算法的收斂性。為了保證試驗的可靠性，在初始化時，將FOA的初始化果蠅坐標X_axis，Y_axis也作為FS-FOA的初始化坐標，并將FOA與FS-FOA算法各獨立運行30次，取其優(yōu)化結(jié)果的平均值、最優(yōu)值和方差作對比。固定迭代次數(shù)的試驗結(jié)果如表2所示，在目標精度下尋優(yōu)對比結(jié)果如表3所示。

表1 測試函數(shù)

表2 固定代數(shù)尋優(yōu)結(jié)果對比

由表2可以看出：FS-FOA算法在處理單峰函數(shù)F1(x)，F(xiàn)5(x)時，尋優(yōu)精度會比FOA算法高出一個數(shù)量級，在處理多峰函數(shù)F2(X)，f4(x)時，尋優(yōu)精度比FOA高出兩個數(shù)量級，說明FS-FOA在處理多峰函數(shù)時性能提升更明顯;此外，F(xiàn)S-FOA的方差在處理F1，F(xiàn)2，F(xiàn)3，F(xiàn)5時，要比FOA的方差高出4個數(shù)量級，在處理二維函數(shù)F4時，方差與FOA算法有相同數(shù)量級，說明FS-FOA算法在處理高維函數(shù)時，其尋優(yōu)能力更強，穩(wěn)定性更高。

表3 目標精度尋優(yōu)時間對比

對表3進行分析可知: FS-FOA算法在目標精度下的尋優(yōu)時間和代數(shù)更少，對于30維F1，F(xiàn)2函數(shù)；FS-FOA所用時間占比為44.44%和24.67%，其中時間占比η=t2/t1，F(xiàn)S-FOA在處理F4函數(shù)時，時間占比為96.4%，與FOA耗時差不多，這是由于處理低維函數(shù)時，所用迭代次數(shù)太少，在時間上差距不大。但是從F3和F5函數(shù)可以看出，F(xiàn)S-FOA在處理目標精度更高的尋優(yōu)時，其優(yōu)化性能更明顯，對F3函數(shù)30維在10-4和10-6精度下尋優(yōu)對比，發(fā)現(xiàn)時間占比縮小了15.9%，對比10-6精度下30維和50維，則縮小了0.9%，說明FS-FOA是精度更高的尋優(yōu)算法，其尋優(yōu)性更好。

4.2 聚類試驗及對比

實驗采用UCI標準數(shù)據(jù)集庫中的Iris，Wine，Glass，和CMC 4個數(shù)據(jù)集進行性能測試。仿真實驗參數(shù)設(shè)置：初始種群個數(shù)S為50，最大迭代數(shù)為100，每組數(shù)據(jù)獨立運行30次，取數(shù)據(jù)樣本距離所屬聚類中心的歐式距離和作為算法的適應(yīng)度函數(shù)，對K-means，F(xiàn)OA，SOM，F(xiàn)CM以及FS-K的聚類結(jié)果進行對比。表4為試驗得到的30次獨立試驗的最小值、最大值和均值。

表4 聚類結(jié)果對比

表4可以看出：FS-K的聚類結(jié)果在穩(wěn)定性上要比K-means和FOA高，并且總能跳出局部解，逼近最優(yōu)值，和另外兩個經(jīng)典算法SOM，F(xiàn)CM進行對比，具有更好的聚類效果。從圖3可以看出，在收斂性上，K-means的收斂速度最快，能夠在10代左右收斂；FS-K收斂較慢，在迭代50次左右趨于穩(wěn)定；FOA收斂速度要快于FS-K，但是容易陷入局部解，其跳出局部解的能力沒有FS-K強。

圖3 Iris數(shù)據(jù)集聚類曲線對比

5 結(jié) 論

提出了一種扇形搜索的果蠅優(yōu)化方法，彌補了果蠅算法在搜索中受限于搜索范圍的缺點，增加了果蠅算法跳出局部解的能力和收斂速度。在維度高的函數(shù)優(yōu)化問題中，F(xiàn)S-FOA算法的效果更加顯著。隨后，將FS-FOA算法與K-means算法相結(jié)合，提出一種優(yōu)化聚類方法FS-K，并使用UCI數(shù)據(jù)集進行測試，驗證了算法的可行性。但是，采用改進后的FS-K算法的聚類收斂的速度較慢，如何提高FS-K聚類的收斂速度是未來進一步的研究方向。