多策略混合的花朵授粉算法

姚光磊,熊菊霞,楊國(guó)武,鄭宏宇

1(廣西民族大學(xué) 數(shù)理與物理學(xué)院,南寧 530006)

2(電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,成都 611731)

0 引 言

工業(yè)、信息、管理、交通等領(lǐng)域中的大量科學(xué)應(yīng)用難題都能歸類(lèi)為優(yōu)化問(wèn)題,或能使用處理優(yōu)化問(wèn)題的方法論來(lái)處理.優(yōu)化領(lǐng)域難題歷來(lái)都是研究者們公認(rèn)的重點(diǎn)研究課題.雖然成熟的優(yōu)化理論與方法已在優(yōu)化問(wèn)題中得到了廣泛的應(yīng)用,但隨著人類(lèi)生產(chǎn)力的提升以及科學(xué)技術(shù)的高速發(fā)展,現(xiàn)實(shí)世界中所面臨的優(yōu)化問(wèn)題逐漸增多,并且呈現(xiàn)出規(guī)模大、高維、非線性、多目標(biāo)、多約束、不連續(xù)、不可微等一系列復(fù)雜特征,這使得專(zhuān)家學(xué)者們很難從分析問(wèn)題的數(shù)學(xué)特性角度運(yùn)用傳統(tǒng)的優(yōu)化方法來(lái)求解問(wèn)題.即使能用傳統(tǒng)的優(yōu)化方法求解大規(guī)模復(fù)雜優(yōu)化問(wèn)題,也會(huì)存在求解效率低等缺陷.于是,探索出高效率、高并行、自適應(yīng)性、強(qiáng)健的新型智能優(yōu)化方法來(lái)求解大規(guī)模高復(fù)雜性優(yōu)化問(wèn)題,已成為工程應(yīng)用領(lǐng)域中一項(xiàng)緊迫且長(zhǎng)期的研究課題,不僅在理論方向有深層次意義,而且在實(shí)際應(yīng)用具有廣泛的前景.

受人類(lèi)智能、生物群體社會(huì)性或自然現(xiàn)象規(guī)律的啟發(fā),學(xué)者們創(chuàng)造了大量智能優(yōu)化算法,主要囊括5大類(lèi):進(jìn)化類(lèi)算法、群智能算法、模擬退火算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)算法.在過(guò)去的幾十年中,在智能優(yōu)化研究中陸續(xù)出現(xiàn)了很多新型優(yōu)化算法,但是沒(méi)有一種算法是能夠滿足所有的優(yōu)化問(wèn)題,所以一直有大量新的優(yōu)化算法不斷地被提出或者改進(jìn).針對(duì)復(fù)雜問(wèn)題和工程優(yōu)化問(wèn)題,利用群智能的元啟發(fā)算法解決優(yōu)化問(wèn)題有著滿意的效果,從經(jīng)典的遺傳算法(GA)、禁忌搜索算法(TS)、免疫算法(IA)、蝙蝠算法(BA)、蟻群優(yōu)化算法(ACO)等到近些年來(lái)提出和拓展的人工電場(chǎng)算法(AEFA)、蝗蟲(chóng)優(yōu)化算法(GOA)、哈里斯鷹優(yōu)化算法(HHO)、正余弦優(yōu)化算法(SCA)等.這些算法可以歸結(jié)為兩大類(lèi):基于個(gè)體和基于群體的.第1類(lèi)只生成一種優(yōu)化解決方案,而第2類(lèi)會(huì)生成多個(gè)解決方案并優(yōu)化.

眾所周知,花朵是地球上最普遍、最吸引人的植物之一.通過(guò)風(fēng)、鳥(niǎo)、雨水等介質(zhì),花朵能將花粉帶到適合生長(zhǎng)的地方,這是大自然中無(wú)比奇妙的繁衍過(guò)程.2012年Yang提出花朵授粉算法(Flower Pollination Algorithm,簡(jiǎn)記為FPA)[1],用來(lái)模仿花朵授粉過(guò)程.FPA借鑒了花粉授粉系統(tǒng)的運(yùn)行過(guò)程,是元啟發(fā)類(lèi)型算法的一種.此算法效仿了花朵授粉系統(tǒng)的兩種機(jī)制:異花授粉和自花授粉.FPA具有算法簡(jiǎn)單、參數(shù)少、包容性強(qiáng)、容易實(shí)現(xiàn)等優(yōu)點(diǎn).因此,FPA已經(jīng)被應(yīng)用于諸多現(xiàn)實(shí)問(wèn)題并取得較好的效果,比如:結(jié)構(gòu)優(yōu)化[2]、 經(jīng)濟(jì)分配[3]、背包問(wèn)題[4]、旅行商問(wèn)題[5]等.

自FPA被提出以來(lái),國(guó)內(nèi)外諸多學(xué)者對(duì)其進(jìn)行了一系列的改進(jìn).Chakraborty等人[6]提出了一種混合差分進(jìn)化的花朵授粉算法(A Hybrid Differential Evolution-Flower Pollination Algorithm,DE-FPA),將差分進(jìn)化算法與花朵授粉算法相結(jié)合,利用差分進(jìn)化算法增強(qiáng)了全局搜索的能力,實(shí)驗(yàn)結(jié)果表明改進(jìn)后的新算法在尋找足夠優(yōu)的解和擺脫局部最優(yōu)解方面具有更好的能力.Ouadfel S等人[7]將Social spiders optimization與花朵授粉相結(jié)合,提升算法尋優(yōu)能力.Zhou Y等人[8]提出了 基于精英反向?qū)W習(xí)的花朵授粉算法(Elite Opposition-Based Flower Pollination Algorithm,EOBLFPA),利用種群精英的信息提升算法尋優(yōu)能力.賀智明等人[9]提出了一種基于動(dòng)態(tài)全局搜索和柯西變異的花授粉算法(Flower Pollination Algorithm Based on Dynamic Global Search and Cauchy Mutation,DCFPA),實(shí)驗(yàn)證明該算法有著較好的收斂速度以及收斂精度.肖輝輝等人[10]提出一種基于引力搜索機(jī)制的花朵授粉算法,個(gè)體在通過(guò)優(yōu)化信息的共享向質(zhì)量大(最優(yōu)位置)的個(gè)體靠近,且個(gè)體間的萬(wàn)有引力牽制萊維飛行的隨機(jī)游走.李克文等人[11]提出了一種基于混合策略改進(jìn)的花朵授粉算法(Flower Pollination Algorithm Based on Hybrid Strategy,HSFPA),使用一種自適應(yīng)的轉(zhuǎn)換概率策略,以動(dòng)態(tài)的方式切換全局搜索與局部搜索,以提升算法各方面性能.

雖然花朵授粉算法(FPA)在解決較為簡(jiǎn)單的問(wèn)題時(shí)能夠取得不錯(cuò)的結(jié)果,但在求解一些較復(fù)雜的問(wèn)題時(shí)卻表現(xiàn)得不盡人意.因此,本文在FPA算法的基礎(chǔ)上,從多個(gè)角度添加不同的改進(jìn)策略,提出多策略混合的花朵授粉算法(MFPA),使其在解決多特征、復(fù)雜問(wèn)題上具有收斂速度快、收斂精度高等優(yōu)點(diǎn),為處理復(fù)雜問(wèn)題提供一種新思路.多策略主要包括自適應(yīng)的控制策略、改進(jìn)的全局搜索策略、改進(jìn)的局部搜索策略、基于梯度信息的精英擾動(dòng)策略、特征選擇策略.自適應(yīng)控制策略能夠很好地把控兩種花朵授粉過(guò)程,使其達(dá)到平衡.特征選擇策略能夠?qū)?fù)雜問(wèn)題分成一系列較簡(jiǎn)單的問(wèn)題,先求解簡(jiǎn)單問(wèn)題,最后再將簡(jiǎn)單問(wèn)題的解融合在一起,以此提升算法各方面的性能.

1 花朵授粉算法(FPA)

FPA借鑒了花粉授粉系統(tǒng)的運(yùn)行過(guò)程,是元啟發(fā)類(lèi)型算法的一種.自然界中的有花(被子)植物約為地球上植物物種的百分之八十.授粉過(guò)程是地球最自然、最有意義的活動(dòng)之一.授粉過(guò)程需要將花粉從某個(gè)花卉轉(zhuǎn)移到另一個(gè)花卉上,從而能夠進(jìn)行繁殖,遷移過(guò)程一般有以下方式:非生物因素(花粉由風(fēng)進(jìn)行轉(zhuǎn)移)和生物因素(花粉由昆蟲(chóng)等動(dòng)物轉(zhuǎn)移).前者類(lèi)型花粉來(lái)源具有隨機(jī)性強(qiáng)、距離遠(yuǎn)的特點(diǎn),稱為全局授粉(異花授粉)過(guò)程.后者類(lèi)型的花粉通常來(lái)自自身所屬的花卉或者自身所屬植株的花卉,屬于局部授粉(自花授粉)過(guò)程.

在FPA算法中,將花卉、花粉、植株視為等價(jià)的概念,將花粉看成一個(gè)可行解,將自花和異花授粉過(guò)程視作為尋找最優(yōu)解的過(guò)程.該過(guò)程主要由以下面3個(gè)部分組成:

1)全局搜索利用萊維飛行效仿異花授粉;

2)局部搜索效仿自花授粉;

3)轉(zhuǎn)化概率p控制異花授粉過(guò)程和自花授粉過(guò)程轉(zhuǎn)換.

異花授粉過(guò)程能夠進(jìn)行大范圍的傳播,更新公式為:

(1)

(2)

(3)

σv=1

(4)

自花授粉過(guò)程主要以風(fēng)等因素進(jìn)行傳播,傳播范圍小,更新公式為:

(5)

2 多策略混合的花朵授粉策略

2.1 自適應(yīng)控制策略

FPA算法通過(guò)控制因子p選擇全局搜索與局部搜索.FPA為每一個(gè)個(gè)體賦予控制因子,能提高每一個(gè)個(gè)體的自主性,但是FPA采用固定的控制因子p,讓種群不能有效地朝著首要目標(biāo)前進(jìn),不符合動(dòng)物群體的社會(huì)屬性.受到文獻(xiàn)[11]的啟發(fā),可以比較當(dāng)前個(gè)體與種群最優(yōu)個(gè)體信息,自適應(yīng)地調(diào)整控制因子.控制因子p過(guò)大或者過(guò)小,會(huì)導(dǎo)致算法陷入全局搜索或者局部搜索策略,導(dǎo)致算法穩(wěn)定性變差.本文提出的控制概率模型如下:

(6)

由公式(6)易知:當(dāng)R>0.5時(shí),p(t)由1～0隨迭代線性遞減.隨著迭代,算法探索主體由全局搜索向局部搜索轉(zhuǎn)變.由函數(shù)cos(x)在[0,π/2]的變化曲線得知,p(t)中期變化速率快,使種群探索方式能夠快速完成從全局到局部方式的切換.當(dāng)R<0.5時(shí),p(t)受到自身到最優(yōu)個(gè)體的距離影響,距離越小p(t)越大,以全局搜索為主,在算法后期可以緩解種群堆積、陷入局部最優(yōu)的現(xiàn)象.

2.2 改進(jìn)的全局搜索策略

全局搜索的目的是提高算法的收斂速度,維護(hù)種群多態(tài)性.分析FPA算法得知:萊維飛行和最優(yōu)個(gè)體信息為種群迭代在全局授粉過(guò)程提供動(dòng)力與方向.利用萊維飛行的隨機(jī)性,能夠很大程度保持種群多樣性,增強(qiáng)問(wèn)題空間的挖掘能力,最優(yōu)個(gè)體能夠?yàn)榉N群更新提供方向.FPA算法始終以當(dāng)前個(gè)體為基準(zhǔn)最優(yōu)個(gè)體提供方向進(jìn)行更新.本文提出的改進(jìn)的全局搜索策略添加反向過(guò)程:以最優(yōu)個(gè)體為基準(zhǔn),當(dāng)前個(gè)體為其提供方向,使用自適應(yīng)控制策略給出的控制因子來(lái)控制選擇全局更新策略,具體公式為:

(7)

A=2a·r1-a

(8)

a隨迭代公式從2～0線性遞減,r1滿足正態(tài)分布N(0,1)的隨機(jī)數(shù).

從公式(7)可以看出:在算法前期p(t)較大時(shí),種群更新以第1個(gè)式子為主,使得種群能夠較快地探索最優(yōu)個(gè)體的鄰域,加速了算法收斂速度.到算法后期p(t)較小時(shí),則會(huì)增加以第2個(gè)公式更新的個(gè)體,在萊維隨機(jī)數(shù)的控制下,能夠很大程度地保持種群的多樣性.r1∈N(0,1)理論上可以取到任何實(shí)數(shù),使得eA∈(0,+∞),從而全局搜索能夠布滿整個(gè)問(wèn)題空間.

2.3 改進(jìn)的局部搜索策略

FPA算法的局部搜索策略是以當(dāng)前個(gè)體為基礎(chǔ),以兩個(gè)隨機(jī)個(gè)體向量差值為方向及隨機(jī)權(quán)重為步長(zhǎng)進(jìn)行更新.該策略具有一定的盲目性和隨機(jī)性.為了降低該策略的隨機(jī)性,本文利用梯度信息與種群最優(yōu)個(gè)體信息為種群提供探索方向.但是,梯度信息存在兩個(gè)主要缺點(diǎn):1)在平坦區(qū)域,梯度過(guò)小導(dǎo)致個(gè)體陷入停滯;2)在較為陡峭的位置,梯度較大,從而導(dǎo)致個(gè)體跳出局部最優(yōu)解的探索區(qū)域,降低算法精度.

為了緩解梯度更新帶來(lái)的兩種不利情況,將梯度向量歸一化并使用群體最優(yōu)個(gè)體為個(gè)體更新提供信息.具體公式如下:

(9)

其中eαlcos(2πl(wèi))為旋轉(zhuǎn)因子使得種群以螺旋路徑靠近最優(yōu)個(gè)體,α為對(duì)數(shù)螺旋形狀的常量系數(shù),l為[-1,1]中均勻分布隨機(jī)數(shù),Grad為當(dāng)前個(gè)體的梯度信息.采用權(quán)重系數(shù)ω來(lái)平衡兩種信息的影響程度.

梯度下降法在機(jī)器學(xué)習(xí)中廣泛使用,通過(guò)文獻(xiàn)[12-14]以及函數(shù)始終沿著梯度方向變化最快的原理,不難得出運(yùn)用梯度下降法的合理性.對(duì)于局部搜索策略的第2部分進(jìn)行簡(jiǎn)要的證明:

(10)

命題1.給定一元非常數(shù)連續(xù)函數(shù)f(x),定義域?yàn)镈,x0是f(x)一個(gè)極小值點(diǎn),則必存在一個(gè)x0鄰域U(x0)使得函數(shù)有唯一極小值且x∈U(x0)時(shí)f(x)的函數(shù)值隨著|x-x0|的增大而增大,即:

對(duì)于極小值點(diǎn)y0=f(x0),?U(x0,δ0)∈D,對(duì)于?x1,x2∈U(x0,δ0),滿足x1≠x2≠x0且(x1-x)(x2-x)>0當(dāng)|x1-x0|>|x2-x0|時(shí),有f(x1)≥f(x2).

證明:(反證法)設(shè)任意x0的鄰域U(x0,δ),有不同于極值y0=f(x0)的極值y1=f(x1),存在ε>0有|x0-x1|<δ使得|y0-y1|>ε,根據(jù)δ的任意性知,與f(x)連續(xù)性矛盾.所以存在x0的鄰域U(x0,δ0)使得存在唯一的極小值.

又根據(jù)極小值定義,易知在鄰域U(x0,δ0)上使得f(x)的函數(shù)值隨著|x-x0|的增大而非嚴(yán)格增大.

命題2.f(x0)為f(x)極小值,U(x0,δ)為x0的一個(gè)鄰域且滿足命題1,設(shè)xn,xbest∈U(x0,δ),存在一數(shù)列{an}an=xn,an+1=xn+1,其中xn+1由公式(10)得出,則數(shù)列{an}為收斂數(shù)列并且收斂于x0.

證明:eαlcos(2πl(wèi))levy的定義區(qū)間為[-c,c],c足夠大.xn,xbest∈U(x0,δ)有兩種情況:1)(xn-x0)(xbest-x0)>0;2)(xn-x0)(xbest-x0)<0.

第1種情況為xn,xbest均在x0的左側(cè)(右側(cè)),根據(jù)命題1有|xn-x0|>|xbest-x0|,令xn+1=xn+k(xbest-xn),其中k=eαlcos(2πl(wèi))·levy,則當(dāng)0f(xn+1)>f(x0),又因?yàn)?0,x0-xn/xbest-xn)∈[-c,c].所以公式(10)能夠產(chǎn)生一單調(diào)遞減數(shù)列有界數(shù)列{f(xn)}收斂于f(x0),又由f(x)連續(xù)性得xn收斂于x0.

第2種情況,不妨設(shè)xnf(xn+1)≥f(x0),因?yàn)?0,1)∈[-c,c],所以有{f(xn)}收斂與f(x0),又由f(x)連續(xù)性得xn收斂于x0,xn>x0,同理可證.

命題3.對(duì)于極小值點(diǎn)x0=(x1,x2,…xn),y0=f(x0),?鄰域U(x0,δ0)∈D,使得?xa=(x1,x2,…,xi+c1,…,xn),xb=(x1,x2,…,xi+c2,…,xn)∈U(x0,δ0),i=1,2…,n,滿足xa≠xb≠x0,且(xa-x)·(xb-x)>0,|xa-x0|>|xb-x0|時(shí),有f(xa)≥f(xb).存在這樣一個(gè)鄰域使得,任意其中一個(gè)分量在固定其他分量情況下滿足命題1.

命題4.存在滿足命題3的一個(gè)鄰域,能夠通過(guò)公式(10)產(chǎn)生一列收斂于x0的數(shù)列.

2.4 基于梯度信息的精英擾動(dòng)策略

由局部搜索公式(9)看出,種群最優(yōu)個(gè)體只能以梯度信息進(jìn)行更新.為了使最優(yōu)個(gè)體能夠充分利用自身信息引入柯西擾動(dòng)策略[15],這是一種以利用自身信息進(jìn)行探索的策略,更新公式如下:

X=Xbest+cauchy(0,1)Xbest

(11)

一維標(biāo)準(zhǔn)柯西概率函數(shù)定義如下:

(12)

柯西分布函數(shù)在越靠近原點(diǎn)處函數(shù)值越大,越遠(yuǎn)離原點(diǎn)處函數(shù)值值越小.使用柯西分布產(chǎn)生的隨機(jī)數(shù)cauchy(0,1)∈(-∞,∞)理論上X能夠使得可能值為問(wèn)題空間中的任意一點(diǎn).但是在計(jì)算機(jī)上通過(guò)有限次數(shù)模擬獲取到的隨機(jī)數(shù)|rand|>C(C為一個(gè)較大常數(shù))的情況極少,所以這種情況下的探索策略能夠探索的空間十分有限.所以探索空間的范圍主要根據(jù)‖Xbest‖的大小而定,當(dāng)‖Xbest‖取較小值時(shí),其本身引起的的探索范圍能夠達(dá)到較好的水平;當(dāng)‖Xbest‖較大時(shí),需要采取自適應(yīng)步長(zhǎng)來(lái)控制其探索空間.數(shù)學(xué)模型描述如下:

(13)

又由于柯西分布概率密度函數(shù)以軸x=0對(duì)稱,模擬得出的隨機(jī)數(shù)很可能導(dǎo)致X更新朝著真實(shí)解的反方向更新,為了充分利用柯西擾動(dòng)策略,使用梯度方向作為種群更新方向.修改后的數(shù)學(xué)模型描述如下:

(14)

其中:

2.5 特征選擇策略

在多特征問(wèn)題中,每個(gè)特征對(duì)問(wèn)題的影響可能大不相同,隨著問(wèn)題維數(shù)的增加,對(duì)于算法而言所需要探索的解空間也急劇增加,而且所有特征同時(shí)更新會(huì)存在很大的隨機(jī)性和不可控性.例如,假設(shè)X=(x1,x2,…,xn)為特征向量,并且特征分量相互獨(dú)立,則存在以下問(wèn)題:設(shè)每一個(gè)特征分量分別有(n1,n2,…,nn)個(gè)極值鄰域,最壞情況下通過(guò)整體更新需要獲取到n1n2,…,nn個(gè)空間信息最終找到最優(yōu)解,而依次找到單個(gè)特征的最優(yōu)解鄰域,最壞情況下只需要探索n1+n2,…,+nn個(gè)空間信息,極大的減少需要探索的空間,以此提高算法的性能.

控制變量法將多特征復(fù)雜問(wèn)題劃分為若干個(gè)單特征問(wèn)題,若只改變其中某一個(gè)因素,就研究這個(gè)因素對(duì)整體的影響,最后自底向上地將多個(gè)單特征問(wèn)題的解融合在一起得到整個(gè)問(wèn)題的解.

序列最小優(yōu)化算法(Sequential Minimal Optimization,SMO)[16]是一種用于解決支持向量機(jī)的優(yōu)化算法.SMO算法基本思路是每次先任意選取兩個(gè)變量ai和aj,然后固定ai和aj之外的所有參數(shù),隨后求f(x)在ai和aj上的極值,一次反復(fù)直至收斂.由此受到啟發(fā),本文首次提出特征選擇策略,基本思想為:將個(gè)體特征分為K個(gè)部分,采用本策略時(shí)每次會(huì)固定第ki部分之外特征,對(duì)第ki部分特征進(jìn)行搜索.特征選擇策略算法(FSA)流程如算法 1,其中被選中特征下標(biāo)向量(Dimselected)定義為被選中的特征位為1,其它特征位為0,I為被選中的特征集合.

根據(jù)評(píng)估最優(yōu)值變化情況來(lái)判斷是否需要使用特征選擇策略.當(dāng)長(zhǎng)時(shí)間出現(xiàn)最優(yōu)值變化過(guò)小時(shí),則采用特征選擇策略;當(dāng)特征選擇算法結(jié)束后,評(píng)估當(dāng)前最優(yōu)解向量的對(duì)稱性,對(duì)稱性高時(shí)不再采用特征選擇策略.

算法1.特征選擇算法

輸入:未被選擇過(guò)的特征集合S,需要選擇特征的個(gè)數(shù)k

輸出:被選中特征下標(biāo)(Dimselected).

Dimselected=zeros(dim)

N=min(k,size(S))

WhileN>0 do:

IfS==?:

Dimselected=ones(dim)

Else:

I=pop(S)

Indices=argIndices(I)

Dimselected(Indices)=1

2.6 MFPA算法流程

本文在花朵授粉算法(FPA)基礎(chǔ)上,為了提升FPA算法的性能,從多個(gè)角度對(duì)算法進(jìn)行改進(jìn)和修正,首次提出混合自適應(yīng)控制策略[10]、全局搜索策略[17]、局部搜索策略[18]、基于梯度信息的精英擾動(dòng)策略[19,20]、特征選擇策略的多策略混合的花朵授粉算法(MPFA),其算法流程如算法2,其中N、dim、itermax、population分別為種群數(shù)量、個(gè)體特征維度、最大迭代次數(shù)、種群.

算法2.多策略花朵授粉算法

輸入:N,dim,itermax.

輸出:最優(yōu)值(Xbest)

initialize:population

Repeatitermax:

If use FSA is ture:

Dimselected=FSA()

For 1 toN:

IfR>p(t) then:

UpdateXiby eq(7)

Else

UpdateXiby eq(9):

UpdateXbestby eq(14):

3 實(shí)驗(yàn)設(shè)計(jì)

3.1 實(shí)驗(yàn)條件設(shè)置

為了驗(yàn)證本文所提出的MFPA算法的優(yōu)化性能,將MFPA算法與原始花朵授粉算法(FPA)、融合正余弦和柯西變異算的麻雀搜索算法(Sparrow Search Algorithm Combining Sine-Cosine and Cauchy Mutation,SCSSA)[21]、 基于布朗運(yùn)動(dòng)與梯度信息的交替優(yōu)化算法(Alternately Optimizing Algorithm Based on Brownian Movement and Gradient Information,AOABG)[22]與基于混合策略改進(jìn)的花朵授粉算法(HSFPA)進(jìn)行對(duì)比分析.仿真實(shí)驗(yàn)的算法種群數(shù)量設(shè)置為50,最大迭代數(shù)為500,其中FPA算法轉(zhuǎn)換概率設(shè)為0.8,λ=1.5,其他算法的參數(shù)由對(duì)應(yīng)的文獻(xiàn)進(jìn)行相應(yīng)設(shè)置.采用9個(gè)常用測(cè)試函數(shù)驗(yàn)證算法效果.測(cè)試函數(shù)的基本信息如表 1所示,其中n=50.

實(shí)驗(yàn)硬件環(huán)境為:Inter i7 CPU 2.50GHz、RAM 8.0G、Windows10 操作系統(tǒng),Matlab R2016a.

各算法均在所有測(cè)試函數(shù)上獨(dú)立運(yùn)行15次,最后取每次測(cè)試中的最優(yōu)值并計(jì)算方差.公式(11)中ω=0.5,公式(13)中α1=10,β=mod(‖Xbest-0‖,10)其中mod為求余算法.

3.2 全局搜索性能對(duì)比

全局搜索的主要目的是讓種群個(gè)體找到精確解所在鄰域.為了驗(yàn)證本文提出的MFPA算法具有高效的全局搜索性能,利用表 1給出的測(cè)試函數(shù)Michalewiz,Schwefel,Gramacy分別對(duì)MFPA、HSPFS、FPA、SCSSA、AOABG算法進(jìn)行全局搜索性能比較分析,驗(yàn)證MFPA算法在保持種群多樣性及搜索最優(yōu)解鄰域方面的效果.

表1 測(cè)試函數(shù)Table 1 Test functions

Gramacy函數(shù)是多峰對(duì)稱函數(shù),具有定義域小、真實(shí)解鄰域小、次要解相差小等特點(diǎn).Schwefel函數(shù)為多峰對(duì)稱函數(shù),具有定義域大、真實(shí)解鄰域范圍大、次要解相差大等特點(diǎn).Michalewiz函數(shù)為多峰非對(duì)稱函數(shù),定義域小、真實(shí)解鄰域小、次要解相差小,能夠基本滿足一般問(wèn)題的條件.

SCSSA與AOABG算法采取了分量更新步長(zhǎng)倍數(shù)不相等的模式,即:Incremental=(k1s1,k2s2,…,knsn),而其余算法采用了分量更新步長(zhǎng)倍數(shù)相等的模式,Incremental=(ks1,…,ksn),Incremental為解向量更新增量.由測(cè)試函數(shù)Sphere各算法全局搜索個(gè)體分布圖 1可以看出:倍數(shù)不相同模式下,種群分量幾乎充滿了整個(gè)取值范圍,其中AOABG算法混亂程度最高,而SCSSA在算法后期種群會(huì)向局部最優(yōu)解堆積,無(wú)法良好的保持種群多樣性.而選擇倍數(shù)相等模式下,測(cè)試函數(shù)為對(duì)稱函數(shù)時(shí),分量會(huì)逐步對(duì)稱縮小搜索圍.

圖1 全局搜索分布Fig.1 Global search distribution

由表 2可以看出,各個(gè)算法在問(wèn)題維度較小時(shí)都能有效并快速的到達(dá)最優(yōu)解鄰域.但是當(dāng)維度較高時(shí),SCSSA、AOABG、FPA算法幾乎不能找到解的鄰域,而MFPA、HSFPA算法卻能找到最優(yōu)解鄰域.HSFPA算法能夠進(jìn)入到最優(yōu)解鄰域的個(gè)體偏多,側(cè)面反映出該算法保持種群多樣性的能力不足.但在使用非對(duì)稱測(cè)試函數(shù)Michalewiz對(duì)5個(gè)算法進(jìn)行測(cè)試時(shí)都不能找到最優(yōu)解的鄰域.在利用Michalewiz測(cè)試時(shí),通過(guò)給全局搜索策略添加特征特征選擇策略后可以降低全局搜索所需要搜索的維度,各算法均能找到最優(yōu)解的鄰域,從而體現(xiàn)出特征選擇策略的有效性.

3.3 搜索精度分析

為了驗(yàn)證本文給出的算法MFPA在精度方面的效果,利用表 1中所給的前8個(gè)測(cè)試函數(shù),將其與HSPFS,FPA,SCSSA,AOABG進(jìn)行對(duì)比,計(jì)算不同算法在各測(cè)試函數(shù)得出的最優(yōu)值與標(biāo)準(zhǔn)差,測(cè)試結(jié)果如表3所示.雖然MFPA與HSFPA算法均為改進(jìn)的FPA算法,但相對(duì)于HSFPA算法而言,MFPA算法在Sphere、Stybinski、Tablet上精度都有一定程度的提高,在Tablet函數(shù)上方差小,而在Michalewiz上的探索和尋優(yōu)能力有大幅度提升.AOABG在所有函數(shù)上表現(xiàn)得中規(guī)中矩.由此可見(jiàn),本文提出的MFPA算法無(wú)論在探索能力與尋優(yōu)能力都要有一定程度的提升,并且保持著良好的魯棒性.

表2 全局搜索能力Table 2 Global search capability

表3 算法收斂精度Table 3 Convergence accuracy of algorithms

表4 算法復(fù)雜度對(duì)比表Table 4 Table of algorithm complexity comparison

3.4 收斂速度分析

為了直觀地展示出各算法在收斂速度方面的不同表現(xiàn),分別繪制出不同算法的收斂曲線,如圖 2所示.測(cè)試函數(shù)的值域較大時(shí)則采用對(duì)數(shù)顯示,有些函數(shù)值域與定義域均太大則縮小繪圖范圍.

在BentCigar函數(shù)上,算法迭代初期所有算法收斂速度都較慢,MFPA經(jīng)過(guò)一個(gè)轉(zhuǎn)折點(diǎn)后就開(kāi)始快速的下降.在Michalewiz函數(shù)中,MFPA算法即使陷入局部最優(yōu)也能在一定代數(shù)后跳出局部最優(yōu),下降速率也是最高的.對(duì)Sphere、Stybinski函數(shù)而言,MFPA收斂速度明顯優(yōu)于其他算法.在Tablet函數(shù)中,MFPA算法的收斂速度要稍慢于SCSSA算法,但是最終達(dá)到一致的精度.在Schwefel函數(shù)中,在算法初期MFPA收斂速度要比HSFPA算法慢,但是到了算法迭代中期則實(shí)現(xiàn)了反超.

在Booth&Lee函數(shù)中,FPA算法收斂速度要明顯高于其他算法,而其他算法無(wú)明顯差異.在McCormick函數(shù)中,MFPA下降速度明顯快于其他函數(shù).通過(guò)實(shí)驗(yàn)結(jié)果對(duì)比,在低維測(cè)試函數(shù)上,初始種群的分布對(duì)于算法的收斂性能夠較大影響.MFPA有著良好的收斂速度,盡管在算法迭代前期在一些情況下收斂速度不足,但在算法迭代中期出現(xiàn)了收斂速度強(qiáng)勁的現(xiàn)象,這也反映出MFPA有著較為優(yōu)秀的跳出停滯現(xiàn)象的能力.

3.5 算法復(fù)雜度分析

在算法執(zhí)行過(guò)程中,時(shí)間主要消耗在計(jì)算目標(biāo)函數(shù)值和梯度上.假設(shè)目標(biāo)函數(shù)計(jì)算與梯度計(jì)算時(shí)間分別設(shè)為T(mén)F,TG,而其他步驟均為O(1).種群個(gè)體向量更新的復(fù)雜度為O(1),種群進(jìn)行全局搜不需要進(jìn)行梯度計(jì)算,則單個(gè)個(gè)體全局搜索時(shí)間復(fù)雜度為:O(TF+1).

局部搜索種群個(gè)體需要進(jìn)行梯度計(jì)算,因此單個(gè)個(gè)體局部搜索的時(shí)間復(fù)雜度為:O(TF+TG+1).全局搜索與局部搜索個(gè)體比值為:1-p:p.種群最優(yōu)個(gè)體只進(jìn)行最優(yōu)個(gè)體擾動(dòng)策略,其需要計(jì)算梯度與目標(biāo)函數(shù)值,算法單次迭代時(shí)間復(fù)雜度為:O((N-1)×(1-p)(TF+1)+(N+1)p(TF+TG+1)+1(TF+TG+1))=O((N-1)(TF+1)+((N-1)p+1)(TG)).

圖2 算法收斂速度Fig.2 Convergence rate of algorithms

所以算法總的時(shí)間復(fù)雜度為O(Maxiter(N(TF+1)+(N-1)(1-p)(TG))),其中Maxiter為算法最大迭代次數(shù),N為種群數(shù)量.其他算法時(shí)間復(fù)雜度如表 4.

由表 4可知,與其他算法相比,MFPA算法僅多出了求梯度的復(fù)雜度,但其總復(fù)雜度隨種群數(shù)量以及迭代次數(shù)呈線性增長(zhǎng).

4 總 結(jié)

本文提出了一種多策略混合的花朵授粉算法(MFPA),針對(duì)于FPA算法跳出局部最優(yōu)解能力不足提供了新思路.利用水往低處流的思想,為花粉添加了梯度信息,讓花粉朝著更好的方向傳播.根據(jù)自身與最優(yōu)個(gè)體的信息判斷下一步該如何更新,讓花粉表現(xiàn)出一種“智能”性.通過(guò)開(kāi)展大量仿真實(shí)驗(yàn)進(jìn)行算法性能分析對(duì)比,驗(yàn)證了MFPA算法的有效性以及優(yōu)越性.后續(xù)的研究工作將考慮把MFPA算法應(yīng)用到一些機(jī)器學(xué)習(xí)實(shí)際問(wèn)題中,實(shí)現(xiàn)算法的應(yīng)用示范.