基于分組協(xié)同進化策略的果蠅優(yōu)化算法研究

胡 天，戴寶賦，譚建軍，孫先波，黃 勇，朱 黎，易金橋

(湖北民族大學 信息工程學院，湖北 恩施 445000)

果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm,FOA)[1]是基于果蠅覓食行為提出的一種智能群體優(yōu)化算法.該算法具有低參量、快收斂、高效率等優(yōu)點，被廣泛應用于數(shù)據(jù)預測[2-3]、圖像處理[4]、路徑優(yōu)化[5-6]、故障診斷[7]、多維背包問題[8]等.針對FOA算法在尋優(yōu)過程中易于陷入局部最小值且迭代次數(shù)多的問題，張鑄等[9]提出了一種混沌步長果蠅優(yōu)化算法(A novel Fruit Fly Optimization Algorithm with Chaotic Step,HSFOA)，該算法將Hénon混沌映射引用為步長因子，提高了算法的全局搜索能力和收斂速度；王念等[10]提出了一種加權果蠅優(yōu)化算法(Weighting Fruit Fly Optimization Algorithm,WFOA)，該算法引入三維坐標和加權因子，克服了果蠅優(yōu)化算法只能在二維平面尋優(yōu)的局限性；張水平等[11]提出了一種基于動態(tài)調整搜索策略的果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm with Dynamic Adjustment of Search Strategy,FOAASS)，該算法利用混沌映射增強種群初始位置的均勻性和隨機性，通過轉換概率隨機選取搜索半徑并對其進行動態(tài)調整.以上研究成果提高了果蠅優(yōu)化算法的搜索能力和收斂速度.

分組協(xié)同進化是一種有效提高學習效率和學習能力的群體學習模式[12]，本文將這一模式與果蠅群體尋優(yōu)相結合，研究基于分組協(xié)同進化策略的果蠅優(yōu)化算法(Group coevolution Fruit fly optimization algorithm,GCFOA)，并選取8個經典函數(shù)[13]采用GCFOA算法計算函數(shù)最小值，最后與IFOA、WFOA、FOA、PSO(粒子群算法)、BA(蝙蝠算法)算法計算結果進行比較.

1 GCFOA算法

在經典FOA算法采用定步長方法進行動態(tài)尋優(yōu)的基礎上，先將果蠅群體分為兩組，分別進行動態(tài)尋優(yōu)和相互學習，擴大算法的搜索范圍，快速接近目標值，然后在目標值附近進行動態(tài)搜索，以免搜索結果陷入局部最小值.本文以代入適應度函數(shù)fitness所得函數(shù)值作為仿生學果蠅搜尋食物氣味濃度值Smell的大小，對果蠅算法得到的結果進行判定.GCFOA算法流程如圖1所示.

圖1 GCFOA算法流程圖Fig.1 GCFOA algorithm flow chart

步驟1 隨機定義果蠅的初始位置(Xaxis,Yaxis)、迭代次數(shù)iteration、種群大小sizepop.

步驟2 基于隨機方向(RandomValue)利用嗅覺搜尋食物，得到果蠅的新位置.

(1)

其中Xij和Yij表示第i代的第j個果蠅的橫坐標和縱坐標.

步驟3 先估計果蠅目前位置到原點的距離(Disti)，再計算味道濃度判定值(Si)，該值為距離的倒數(shù).

(2)

步驟4 將味道濃度判定值(Si)代入味道濃度判定函數(shù)(fitnessfunction)，求出該果蠅個體位置的味道濃度(Smelli).

Smelli=function(Si).

(3)

步驟5 記錄該果蠅通過嗅覺覓食過程，保留最佳濃度個體和最差濃度個體，記錄其濃度值(bestSmell、worstSmell).

(4)

其中bestIndex和worstIndex分別是判定函數(shù)最小值和最大值的索引值.

得到最佳個體的位置(Xaxis,Yaxis)和最差個體位置(Xworst,Yworst).

(5)

步驟6 進行迭代尋優(yōu)時，將果蠅分為兩組，A組向著最優(yōu)值進行擴散學習，記錄其迭代位置(Xa,Ya).其中rand為[0,1]的隨機數(shù).

Xa=Xaixs+2·rand-1,Ya=Yaixs+2·rand-1.

(6)

B組找出最差值和最優(yōu)值之間的距離(W)，然后以最優(yōu)值為目標，進行反思學習，記錄其迭代位置(Xb,Yb).

(7)

步驟7 分別選出A組和B組中的最佳濃度(AbestSmell,BbestSmell)和最差濃度(AworstSmell,BworstSmell)，并記錄其個體的位置信息.

步驟8 比較A、B兩組中最佳濃度的大小，將濃度大的團體中的最佳個體位置、最差個體位置、最佳濃度分別賦值給(Xaxis,Yaxis)、(Xworst,Yworst)、bestSmell.

若A組的最佳濃度大于B組的最佳濃度，則：

(8)

若B組的最佳濃度大于A組的最佳濃度，則：

(9)

步驟9 判斷是否到達最大迭代次數(shù)，若是則結束并輸出結果；否則重復步驟6～步驟8.

2 仿真實驗與結果分析

為了驗證GCFOA算法，設置一組對比實驗，將GCFOA算法與改進的果蠅算法(IFOA)、加權果蠅算法(WFOA)、經典果蠅算法(FOA)、粒子群算法(PSO)、蝙蝠算法(BA)進行比較.

選取8個經典的函數(shù)，分別是Sphere、Schwefel2.22、Schwefel1.2、Schwefel2.21、Griweank、Quadric、Rastrigin、Ackley.采用GCFOA、IFOA、WFOA、FOA、PSO、BA算法求以上函數(shù)的最小值，并比較其平均誤差和標準差.表1給出了函數(shù)的編號、名稱、代數(shù)式、維度、搜索區(qū)間和最小值.為便于觀察函數(shù)的最小值，本實驗以維度為2的函數(shù)為例，畫出函數(shù)圖像如圖2所示.其中F1～F5為單峰函數(shù)，F(xiàn)6～F8為多峰函數(shù).

表1 函數(shù)及其特征表Tab.1 Functions and their characteristic tables

圖2 函數(shù)圖像Fig.2 Function images

擬解決文獻[14]提出的計算結果對于所設初值大小敏感的病態(tài)問題，應用不同的智能群優(yōu)化算法進行解決.將各算法種群大小sizepop設為30，最大迭代次數(shù)為1 000.其中IFOA算法權重初始值R為1，調節(jié)參數(shù)λ為0.95；WFOA算法中最大權重系數(shù)Wmax為0.9，最小權重系數(shù)Wmin為0.4；PSO算法最大速度Vmax為1，最小速度Wmin為-1，最大權重系數(shù)Wmax為0.9，最小權重系數(shù)Wmin為0.2，社會因子C1和個體因子C2均為2；BA算法中響度A為0.6，脈沖發(fā)射率r為0.7，最大頻率為1，最小頻率為0.

分別采用GCFOA、IFOA、WFOA、FOA、PSO和BA算法計算表1中8個函數(shù)的最小值，求得各函數(shù)應用不同算法計算20次的平均誤差和標準差，用于比較各算法的精度和緊密度.平均誤差值和標準誤差值如表2、表3所示.

表2 采用不同算法計算函數(shù)最小值的平均誤差Tab.2 The mean error of the minimum value of the function is calculated by different algorithms

表3 采用不同算法計算函數(shù)最小值的標準差Tab.3 The standard deviation of the minimum value of the function is calculated by different algorithms

由表2可以看出，對于函數(shù)F1、F2、F3和F5，采用GCFOA算法計算20次所得到的函數(shù)最小值平均誤差均小于10-13，比其他算法計算結果精度高10個數(shù)量級；對于函數(shù)F4、F6和F7，采用GCFOA算法計算函數(shù)最小值20次所得到的平均誤差比其他算法結果精度高1至2個數(shù)量級；對于函數(shù)F8，采用GCFOA算法計算20次所得函數(shù)最小值平均誤差值為1.18×10-8，比其他算法計算結果精度高3至10個數(shù)量級.由此可見，對于單峰函數(shù)和多峰函數(shù)而言，GCFOA算法的計算精度更高，具有良好的全局優(yōu)化能力.

由表3可以看出，對于函數(shù)F1、F2、F3和F5，采用GCFOA算法所得函數(shù)最小值的標準差比其他算法計算結果優(yōu)10個數(shù)量級以上；對于函數(shù)F4、F6和F7，采用GCFOA算法所得函數(shù)最小值的標準差略小于其他算法計算結果，優(yōu)于其他算法1至4個數(shù)量級；對于F8函數(shù)，采用GCFOA算法所得函數(shù)最小值的標準差優(yōu)于其他算法5至10個數(shù)量級.由此可見，相比于其他算法，GCOFA算法具有較強的魯棒性.

為了研究算法的收斂特征，觀察不同算法計算同一函數(shù)最小值的迭代過程如圖3所示.

由圖3可以看出，對于函數(shù)F1、F2、F3和F5，采用GCFOA算法分別迭代464、787、397、398次，函數(shù)最小值小于10-10，經過1 000次迭代后分別收斂至6.05×10-22、4.12×10-12、1.80×10-23和0；對于函數(shù)F4，采用GCFOA算法僅迭代261次就得到最小值0.009 91，領先于其他算法；對于函數(shù)F6，采用GCFOA算法迭代883次達到最小值0.002 44，也優(yōu)于其他算法；對于函數(shù)F7，采用GCFOA算法能夠持續(xù)尋找最小值，當?shù)? 000次時，求得最小值為0.042 45，該值也遠小于其他算法所求最小值；對于函數(shù)F8，采用GCFOA算法迭代988次則收斂于1.19×10-7.由此可見，相比于其他算法而言，采用GCFOA算法可以獲得更快迭代速度和更精確的解.

圖3 不同算法計算函數(shù)最小值的迭代過程Fig.3 The iterative process of the minimum value of the function calculated by different algorithms

3 結語

針對果蠅算法收斂速度慢、易陷入局部優(yōu)解的問題，將分組協(xié)同進化策略引入為群體尋優(yōu)方式，研究了一種基于分組協(xié)同進化策略的果蠅優(yōu)化算法.采用8個經典的單、多峰函數(shù)作為測試函數(shù)，將GCFOA算法與IFOA、WFOA、FOA、PSO、BA進行對比分析，結果表明，相比于IFOA、WFOA、FOA，PSO 和BA算法，GCFOA具有更強的全局尋優(yōu)能力和快速迭代能力.