基于自適應步長果蠅優(yōu)化算法圖像分割

宋 杰，許 冰，楊淼中

安徽大學 計算機科學與技術學院，合肥230601

1 引言

果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）是一種尋求全局優(yōu)化的新方法[1]，它是根據(jù)果蠅尋食行為推理出來的。該算法因為可調(diào)參數(shù)較少，所以簡單容易實現(xiàn)。而且果蠅在嗅覺與視覺等感官知覺上比其他物種敏銳，因此能夠很好地搜尋到空氣里漂浮的氣味，甚至能嗅到40 km以外的食物源?？拷澄镂恢煤竽軕{借視覺的敏銳度找到食物和同伴聚集的位置，然后朝目標源飛去。至今為止，已經(jīng)有很多改進的果蠅優(yōu)化算法，例如多樣性種群果蠅優(yōu)化算法[2]，利用強嗅覺果蠅，由正常果蠅突變?yōu)槲兜罎舛扰卸ㄖ刀鄻踊姆椒??；谀M退火的果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm based on Simulated Annealing，SA-FOA）[3]，增大了接收概率，且利用非均勻變異因子改進步長。參數(shù)修正與收斂策略融合的果蠅優(yōu)化算法[4]，為了解決味道濃度判定值不能是負數(shù)的問題，對味道濃度公式進行了修正；為了避免高維函數(shù)維間互擾問題，迭代優(yōu)化的過程中對果蠅個體在最優(yōu)值附近尋優(yōu)采取逐維擾動的方法。果蠅算法不僅僅限于優(yōu)化，也有很多用于解決實際問題，例如基于MFOA-SVM（Multi Fruit Fly Optimization Algorithm Support Vector Machine）算法的乳腺腫瘤識別[5]、果蠅算法對多峰值光伏最大功率跟蹤仿真研究[6]、基于果蠅算法優(yōu)化的BP神經(jīng)網(wǎng)絡[7]等。雖然改進算法相比傳統(tǒng)算法而言有提高，但是還存在不足，例如SA-FOA算法雖然步長減小，精度提高，但全局搜索能力下降，容易錯過最優(yōu)值。因此對于FOA的研究還是有必要的。對于那些較早的遺傳算法、煙花算法、蟻群算法（基于遺傳算法的蛋白質(zhì)復合物識別算法[8]、改進的煙花算法優(yōu)化粒子濾波研究[9]、基于混合遺傳-蟻群算法的（Maintenance，Repair&Overhaul，MRO）服務調(diào)度研究[10]）等而言，傳統(tǒng)果蠅算法還不夠成熟，整體尋優(yōu)速度慢，收斂精度不高，容易陷入局部最佳值等。傳統(tǒng)果蠅算法的步長是固定不變的，從而會導致陷入局部最優(yōu)值和收斂速率慢等一系列問題。

本文提出了升半柯西函數(shù)，混合正切函數(shù)與柯西算子的果蠅優(yōu)化算法（Tangent Cauchy Operator Fruit Fly Optimization Algorithm，TCO-FOA）根據(jù)迭代次數(shù)的變化對步長進行相應的增加或者減少。正切函數(shù)的變量采用當前迭代中最優(yōu)的濃度值與最差的濃度值的和平均值與前一次迭代果蠅群中最優(yōu)的濃度值與最差的濃度值的和平均值的比值。濃度平均值變化比率ARate＞1，利用升半柯西函數(shù)特點，步長在前期先均勻后呈S型增長。當濃度平均值變化比率ARate≤1，這時進入迭代后階段，果蠅十分靠近目標源，隨著濃度平均值比值減小，這時需要減少步長進行局部搜索。通過濃度平均值變化改變步長，收斂速率和尋優(yōu)精度在原有的基礎上都得到了有效的提高。本文將新型算法TCOFOA與傳統(tǒng)FOA、加權(quán)果蠅算法（Weight Fruit Fly Optimization Algorithm，WFOA）、線性生成機制改進果蠅算法（Linear Generation Mechanism Fruit Fly Optimization Algorithm，LGMS-FOA）這三種算法進行了實驗對比。

2 算法原理

2.1 基本果蠅優(yōu)化算法

定義1果蠅有著敏感的嗅覺和視覺，它能夠通過嗅覺搜尋空中各種氣味，然后通過視覺找到氣味的位置和同伴的位置，算法的主要過程如下：

（1）對種群規(guī)模Sizepop、迭代次數(shù)Maxgen的最大值賦值。

（2）隨機化種群開始的位置，隨機果蠅開始方向與距離：

（3）Dist(i)表示果蠅與初始位置的距離值，S(i)表示味道濃度判定值，S(i)為距離的倒數(shù)：

（4）判定函數(shù)中的變量為S(i)，從而得出果蠅味道的濃度Smell(i)：

（5）在所有群體里面找到濃度最佳的個體：

（6）所有的個體朝著最佳的個體飛去：

（7）迭代尋優(yōu)：

將重復（2）、（3）、（4）、（5）；

判斷：SmellBesti＜SmellBesti-1

如上式成立，則執(zhí)行（6），如不成立則繼續(xù)迭代尋優(yōu)。

2.2 WFOA

WFO是根據(jù)FOA進行改進，加入了擾動因子。主要如下：

（1）C1與C2為干擾常數(shù)，C1＞C2＞0,T為當前算法所運行的迭代次數(shù)，Maximun是算法所設置的最大迭代次數(shù)。

（2）隨著迭代次數(shù)的增加，步長值從C1漸漸變到C2，變化趨勢不斷減小，步長所能達到的最大值與最小值對應為C1與C2。

（3）WFOA的缺點是算法的表現(xiàn)優(yōu)劣與C1和C2相關，取值不同時，產(chǎn)生的效果也有較大差異，而且在迭代過程中，步長的變化趨勢和速率保持不變，容易錯過最優(yōu)解和陷入局部最優(yōu)值。

2.3 LGMS-FOA

LGMS-FOA是以FOA為基礎，增加了權(quán)重因子W，將原有的固定步長，更改為由權(quán)重因子影響的動態(tài)步長，W變化趨勢為遞減的。

果蠅所處位置：

權(quán)重參數(shù)：

其中，W0為初始權(quán)重因子，a為調(diào)節(jié)常數(shù)，gen為當前算法所處的迭代次數(shù)。該算法使用了動態(tài)調(diào)節(jié)步長，增強了局部探索能力，但是到迭代后期容易陷入局部最優(yōu)值的問題沒有得到有效的改善。

3 TCO-FOA

3.1 升半柯西分布

“年老”模糊集合的隸屬函數(shù)為升半柯西分布，其中a=1/5,b=50,c=2。本文算法迭代前期將升半柯西分布特點運用到設置的迭代步長中，使步長在前期先均勻后呈S型增長。

升半柯西分布函數(shù)：

圖1是升半柯西分布函數(shù)圖像，0到a之間函數(shù)值為0，大于a時呈曲線增長，相比于指數(shù)自身的變量而言，升半柯西分布具有靈活性。小于a時均勻變化使得迭代過程不易錯過最優(yōu)值，大于a曲線增長擴大搜索范圍，最后曲線漸漸平緩趨近于1，加快收斂速度，使得步長自適應變化。

圖1 升半柯西分布

3.2 柯西分布

本文改進算法利用柯西分布的特性來設置果蠅迭代步長，使步長具有隨機性，在果蠅尋優(yōu)過程中能夠更好地平衡全局的勘探能力和局部的尋優(yōu)能力[11]。

柯西分布的分布函數(shù)：

柯西分布的密度函數(shù)：

圖2是柯西分布和正態(tài)分布的比較圖像，相比于正態(tài)分布而言，柯西分布的整體分布更加均勻，對稱軸的至高點相對于高斯分布較為平緩，而兩邊曲線所對應的拖尾概率較大。這樣的分布特點，使柯西分布具有較大的散布特性。

圖2 柯西分布和正態(tài)分布

根據(jù)柯西分布的特征，本文提出了柯西變異因子?？挛髯儺愐蜃邮抢每挛髯儺惔嬷笖?shù)函數(shù)的變量，指數(shù)函數(shù)exp(x)與x的變化趨勢相同，相對于高斯分布，柯西分布有較大的拖尾概率，整體變化平緩，根據(jù)其散布特性，柯西分布比指數(shù)原來的自變量更容易產(chǎn)生一個遠離原點的隨機數(shù)，有利于果蠅在迭代過程中脫離局部最優(yōu)值。函數(shù)方程如下：

3.3 改進算法的思想

傳統(tǒng)的果蠅優(yōu)化算法中隨機搜索的長度是固定不變的，隨著迭代次數(shù)增加步長不會改變。迭代前期，步長過長有利于全局搜索尋優(yōu)，不易陷入局部最優(yōu)化。但在迭代后期，步長過長會導致局部尋優(yōu)性下降，有可能錯過最優(yōu)值，而且算法收斂性會減慢[12]。步長過短會提高算法的收斂速度，但尋優(yōu)速率會下降，而且后期極易陷入局部最優(yōu)解[13]。傳統(tǒng)算法在全局尋優(yōu)和局部尋優(yōu)中難以兩者兼得，本文提出了一種步長根據(jù)濃度平均值變化比率改變的果蠅優(yōu)化算法（TCO-FOA）。改進的算法可以很好地解決傳統(tǒng)算法中這種不足。

前期運用升半柯西函數(shù)是為了改變傳統(tǒng)果蠅算法中步長固定不變的問題。升半柯西函數(shù)在0到a時為0，大于a時呈S型增長，然后逐漸穩(wěn)定。將升半柯西函數(shù)作為指數(shù)變量，步長先均勻增加防止錯過最優(yōu)值，然后呈曲線增加，后期緩慢加快收斂速度，使步長自適應化。后期運用柯西函數(shù)是因為傳統(tǒng)果蠅算法容易陷入局部最優(yōu)解。柯西函數(shù)具有較大的散布特性，有較大的拖尾概率，能更容易產(chǎn)生遠離原點的隨機數(shù)，能在迭代過程中跳出局部最優(yōu)解。

本文算法通過濃度平均值變化比率對步長進行自適應動態(tài)變化。在改變步長的過程中引入了指數(shù)、升半柯西函數(shù)、正切函數(shù)和柯西算子。升半柯西函數(shù)靈活的變化使得步長變化力度自適應增長。正切函數(shù)和柯西分布本身都具有隨機性，結(jié)合兩種函數(shù)增大了隨機性。在指數(shù)函數(shù)的情況下，使步長增加或者減少具有非均勻性和隨機性。濃度平均值變化比率ARate＞1時，加快全局尋優(yōu)的速率，逐步增加步長，濃度平均值變化比率ARate≤1時，為了能進行精細搜索，自適應減小步長。

3.4 TCO-FOA算法改進的步驟

將當前迭代果蠅中最優(yōu)濃度值max(Smell(i))和最差濃度值min(Smell(i))的和取平均值Avg(i),與上一次迭代中最優(yōu)濃度值max(Smell(i-1))和最差濃度值min(Smell(i-1))的和取平均值Avg(i-1)進行對比，得出濃度變化比率，改進如下：

本文算法把濃度平均值變化比率ARate＞1作為前期，濃度平均值變化比率ARate＜1作為后期。前期步長隨機增大使全局尋優(yōu)加快。后期迭代，濃度比率會隨之減小，說明果蠅群體逐漸靠近目標源和自己的同伴，這時逐步減小步長，從而提高收斂速率。改進的步長如下：

Li和Li-1分別表示當前步長和前一次迭代時的步長，ARate表示當前迭代中最優(yōu)濃度和最差濃度和的平均值與前一次迭代中最優(yōu)濃度和最差濃度和的平均值的比值，m表示迭代次數(shù)，Maxgen是果蠅中迭代次數(shù)的最大值，Z表示柯西算子，是利用柯西變異代替指數(shù)函數(shù)的變量。K是動態(tài)補償因子，迭代前期加上動態(tài)補償因子，進入迭代后期減去動態(tài)補償因子達到平衡。通過實驗K=1.5時取得最佳結(jié)果。

3.5 全局尋優(yōu)和局部尋優(yōu)的平衡性

（1）全局尋優(yōu)

當濃度變化率大于1時，運用升半柯西函數(shù)。其中分為兩部分，參數(shù)a為控制步長變化的力度。迭代次數(shù)比率小于a時，步長均勻增加防止步長變化過大錯過最優(yōu)值。大于a時，升半柯西函數(shù)A(x)因變量呈S型增長且不斷趨近于1，步長逐漸穩(wěn)定。步長增加是為了加快全局勘探速率，加快全局尋優(yōu)，雖有利于全局尋優(yōu)，但局部尋優(yōu)性能下降，導致兩者不平衡。此時設置分隔點（濃度變化率）。

（2）局部尋優(yōu)

濃度變化率小于等于1時，趨近于目標值。減小步長，加快收斂速度?？挛骱瘮?shù)較大的散布特性，能更容易產(chǎn)生遠離原點的隨機數(shù)，使不會因步長過小而陷入局部最優(yōu)解[14]。算法在較小的區(qū)域進行細化搜索，保證算法的局部搜索能力[15]。從而使算法在全局尋優(yōu)和局部尋優(yōu)中達到平衡。

（3）算法步驟

ARate＞1：迭代次數(shù)比率小于a時，步長均勻變化。若濃度變化率不變ARate＞1，迭代次數(shù)比率大于a時，算法繼續(xù)迭代，步長呈S型遞增，保證全局尋優(yōu)能力。直至達到ARate≤1，步長在柯西函數(shù)下遞減，避免陷入局部極值。從而使算法在全局尋優(yōu)和局部尋優(yōu)中達到平衡。

ARate＞1：迭代次數(shù)比率小于a時，步長均勻變化。若迭代時濃度變化率改變ARate≤1，步長將停止呈S型遞增，步長在柯西函數(shù)下遞減，避免陷入局部極值。從而使算法在全局尋優(yōu)和局部尋優(yōu)中達到平衡。

3.6 大津法閾值分割

日本學者大津提出了一種確定圖像二值化分割閾值的算法，其對圖像的分割取得了良好的效果，原理是將圖像分為前景和背景兩部分。因為方差是對分布均勻性的一種度量，前景（目標）和背景的類間方差越大說明構(gòu)成圖像兩部分的差別越大，即說明前景與背景的分割越好，所以可以認為當前所取閾值使得類間方差最大時，分割結(jié)果最好。

圖像總平均灰度：

u=w0×u0+w1×u1

前景和背景圖像的方差：

g=w0×w1(u0-u1)2

類間方差越大，得到的閾值最佳。傳統(tǒng)的大津法需要對所有像素點進行灰度值計算，然后計算圖像的方差，所需要的計算量較大，并且隨著閾值數(shù)的增加，時間效率不斷增長。本文利用改進的果蠅優(yōu)化算法的快速收斂性和高精度性，對大津法閾值進行適應性求解。

4 TCO-FOA圖像分割步驟

（1）將種群規(guī)模、迭代次數(shù)Maxgen的最大值賦值。令閾值t為0，即t=0。

（2）隨機化果蠅開始的位置(Xaxis,Yaxis)，賦予果蠅個體隨機搜索食物的方向和距離：

其中L為本文算法中所改進的自適應變化步長。

（3）根據(jù)式（4）計算果蠅味道濃度判定值S(i) ，濃度判定值取整，判定S(i) 是否處于[0，255]，處于此區(qū)間時繼續(xù)迭代，若不在此區(qū)間內(nèi)，則S(i) 濃度值為0，繼續(xù)下一個循環(huán)。

（4）根據(jù)判定函數(shù)得出果蠅味道濃度，記錄最佳濃度值bestsmell。

（5）令t=t+1，返回步驟（2），直到t=maxgen。

（6）根據(jù)果蠅最佳濃度值求得最優(yōu)閾值。

（7）根據(jù)最優(yōu)閾值對圖像進行分割。

5 實驗結(jié)果分析

5.1 實驗設計

FOA、WFOA、LGMS-FOA、TCO-FOA四種算法采用6個適應度函數(shù)進行仿真實驗[16]。表1分別為6個函數(shù)的形式和類型、搜尋的范圍、達到函數(shù)目標的最優(yōu)值和目標收斂的精度。算法在實驗環(huán)境為Windows7下Matlab2014版本，運行內(nèi)存4 GB的電腦上測試。

5.2 算法性能測試

在二維情況下，將傳統(tǒng)FOA、WFOA、LGMS-FOA與本文算法TCO-FOA，在6個適應度函數(shù)中進行實驗測試，圖3表示四種算法在迭代200次尋優(yōu)過程中所達到的精度值。由圖可以看出，TCO-FOA算法自適應改變步長，通過運用正切函數(shù)和柯西算子在指數(shù)的情況下，收斂速率變快，易跳出局部最優(yōu)值，能夠達到適應度函數(shù)的目標精度值。而其他三種算法會出現(xiàn)收斂速度較慢或者陷入局部最優(yōu)解等問題。

5.3 實驗測試結(jié)果分析

5.3.1 四種算法在適應度函數(shù)下測試分析

圖3 測試函數(shù)適應度變化曲線

實驗采用6個適應度函數(shù)，在已知適應度函數(shù)的目標精度之下對FOA、WFOA、LGMS-FOA、TCO-FOA進行了20次獨立測試，測試結(jié)果如表2所示。表中的平均值表示進行20次獨立測試時算法在適應度函數(shù)中能夠達到的精度值和的平均值[17]。在測試中方差表示算法的穩(wěn)定性效果。從表2可以看出，F(xiàn)OA、WFOA、LGMSFOA在測試函數(shù)下多數(shù)沒有達到已知的精度值，而且極易陷入局部最優(yōu)解。TCO-FOA對比與另外三種算法而言達到了測試函數(shù)的目標精度值，而且測試過程中的穩(wěn)定性高于另外三種算法。實驗結(jié)果證明了混合動態(tài)改變步長的果蠅優(yōu)化算法的高效性。

表3是四種算法在6個適應度函數(shù)中，分別將維度設置為2和30情況下，達到適應度函數(shù)的目標精度的平均迭代次數(shù)和成功率的比較。將算法中迭代次數(shù)賦值為2 000，獨立運行20次。從表中可以看到，無論在2維還是在30維中，本文算法都達到了目標精度值而且成功率是100%，算法在運行中所迭代的平均次數(shù)也比其他算法少。其他三種算法在2維和30維中都難以達到目標精度，而且穩(wěn)定性比較差，在迭代后期極易陷入局部最優(yōu)解。本文算法穩(wěn)定性強，達到目標精度的平均迭代次數(shù)小，不僅收斂速度優(yōu)于其他三種算法，而且能跳出局部最優(yōu)值。綜上所述，TCO-FOA無論是在低維還是在高維情況下，都能保持尋優(yōu)的穩(wěn)定性和比較高的成功率。

表1 測試函數(shù)

5.3.2 改進算法收斂性分析

從表2可以看出，本文算法在6個測試函數(shù)中都達到了目標精度值，其他三種算法在測試函數(shù)中達到目標精度的較少。表明在收斂精度上本文改進的算法優(yōu)于其他三種果蠅算法。而且從方差可以看出，本文算法在實驗中穩(wěn)定性高于其他三種算法。從表3的迭代次數(shù)可以看出，傳統(tǒng)果蠅算法平均迭代次數(shù)比較大，另外兩種改進算法相對于傳統(tǒng)算法而言迭代次數(shù)相對減少，增加了收斂速度。但本文改進的算法不僅迭代次數(shù)相對于其他三種算法少，收斂速度快，而且在6個適應度函數(shù)中，迭代成功率達到了100%。從兩個表中可以看出，本文算法無論在收斂精度還是在收斂速度上都優(yōu)于另外三種算法。

5.3.3 大津法閾值分割實驗分析

分別用傳統(tǒng)果蠅算法、TCO-FOA、LGMS-FOA、WFOA對大津法進行閾值優(yōu)化，各進行30次，并統(tǒng)計優(yōu)化大津法的平均閾值適應度函數(shù)值和方差，如表4所示。從優(yōu)化結(jié)果來看，TCO-FOA都取得了最大的最佳閾值適應值，這說明TCO-FOA在優(yōu)化大津法閾值方面能取得比其他算法更好的效果。從方差來看，TCO-FOA比其他算法表現(xiàn)得都較穩(wěn)定，這得利于TCO-FOA柯西分布容易產(chǎn)生遠離原點的隨機數(shù)作為指數(shù)的算子進行擾動，兼顧了全局和局部，從而提高了種群的多樣性。

從圖4可以看出傳統(tǒng)果蠅算法圖像分割模糊，且分割效果不明顯。LGMS-FOA、WFOA算法在圖像中能分割出大致輪廓，但是在細小部分的分割效果不佳，且存在噪點。本文改進的算法無論在去噪能力還是在分割效果上都優(yōu)于其他三種算法。

表2 四種算法測試結(jié)果

表3 目標精度下的平均迭代次數(shù)與成功率對比

表4 各算法取最佳閾值的適應值平均值和方差

圖4 測試圖像分割結(jié)果

6 結(jié)束語

傳統(tǒng)果蠅算法難以跳出局部最優(yōu)值，收斂速度慢，精度不高。本文改進的算法在步長中運用正切函數(shù)和柯西算子擴大了隨機性，使全局搜索能力得到優(yōu)化。運用指數(shù)，使步長變化具有隨機性和非均勻性，迭代前期利用升半柯西函數(shù)特點自適應增大步長，加快收斂速度，后期隨機性減小步長，提高精度。相比于其他三種算法而言，本文算法在精度值和收斂速度上都較高。將改進的果蠅算法應用到大津法閾值的優(yōu)化上，通過與其他算法進行仿真實驗對比，本文算法在閾值優(yōu)化的效果和穩(wěn)定性上都要優(yōu)于其他算法。隨著閾值數(shù)的增大，算法的穩(wěn)定性有所降低，這也是其他算法存在的問題，如何更好地提高算法的穩(wěn)定性，是未來研究的重點。