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

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

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

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

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

1 GCFOA算法

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

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

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

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

(1)

其中Xij和Yij表示第i代的第j個(gè)果蠅的橫坐標(biāo)和縱坐標(biāo).

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

(2)

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

Smelli=function(Si).

(3)

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

(4)

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

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

(5)

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

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

(6)

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

(7)

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

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

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

(8)

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

(9)

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

2 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證GCFOA算法，設(shè)置一組對(duì)比實(shí)驗(yàn)，將GCFOA算法與改進(jìn)的果蠅算法(IFOA)、加權(quán)果蠅算法(WFOA)、經(jīng)典果蠅算法(FOA)、粒子群算法(PSO)、蝙蝠算法(BA)進(jìn)行比較.

選取8個(gè)經(jīng)典的函數(shù)，分別是Sphere、Schwefel2.22、Schwefel1.2、Schwefel2.21、Griweank、Quadric、Rastrigin、Ackley.采用GCFOA、IFOA、WFOA、FOA、PSO、BA算法求以上函數(shù)的最小值，并比較其平均誤差和標(biāo)準(zhǔn)差.表1給出了函數(shù)的編號(hào)、名稱、代數(shù)式、維度、搜索區(qū)間和最小值.為便于觀察函數(shù)的最小值，本實(shí)驗(yàn)以維度為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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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