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

姚光磊,熊菊霞,楊國武,鄭宏宇

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

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

0 引 言

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

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

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

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

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

1 花朵授粉算法(FPA)

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

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

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

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

3)轉化概率p控制異花授粉過程和自花授粉過程轉換.

異花授粉過程能夠進行大范圍的傳播,更新公式為:

(1)

(2)

(3)

σv=1

(4)

自花授粉過程主要以風等因素進行傳播,傳播范圍小,更新公式為:

(5)

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

2.1 自適應控制策略

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

(6)

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

2.2 改進的全局搜索策略

全局搜索的目的是提高算法的收斂速度,維護種群多態性.分析FPA算法得知:萊維飛行和最優個體信息為種群迭代在全局授粉過程提供動力與方向.利用萊維飛行的隨機性,能夠很大程度保持種群多樣性,增強問題空間的挖掘能力,最優個體能夠為種群更新提供方向.FPA算法始終以當前個體為基準最優個體提供方向進行更新.本文提出的改進的全局搜索策略添加反向過程:以最優個體為基準,當前個體為其提供方向,使用自適應控制策略給出的控制因子來控制選擇全局更新策略,具體公式為:

(7)

A=2a·r1-a

(8)

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

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

2.3 改進的局部搜索策略

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

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

(9)

其中eαlcos(2πl)為旋轉因子使得種群以螺旋路徑靠近最優個體,α為對數螺旋形狀的常量系數,l為[-1,1]中均勻分布隨機數,Grad為當前個體的梯度信息.采用權重系數ω來平衡兩種信息的影響程度.

梯度下降法在機器學習中廣泛使用,通過文獻[12-14]以及函數始終沿著梯度方向變化最快的原理,不難得出運用梯度下降法的合理性.對于局部搜索策略的第2部分進行簡要的證明:

(10)

命題1.給定一元非常數連續函數f(x),定義域為D,x0是f(x)一個極小值點,則必存在一個x0鄰域U(x0)使得函數有唯一極小值且x∈U(x0)時f(x)的函數值隨著|x-x0|的增大而增大,即:

對于極小值點y0=f(x0),?U(x0,δ0)∈D,對于?x1,x2∈U(x0,δ0),滿足x1≠x2≠x0且(x1-x)(x2-x)>0當|x1-x0|>|x2-x0|時,有f(x1)≥f(x2).

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

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

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

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

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

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

命題3.對于極小值點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|時,有f(xa)≥f(xb).存在這樣一個鄰域使得,任意其中一個分量在固定其他分量情況下滿足命題1.

命題4.存在滿足命題3的一個鄰域,能夠通過公式(10)產生一列收斂于x0的數列.

2.4 基于梯度信息的精英擾動策略

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

X=Xbest+cauchy(0,1)Xbest

(11)

一維標準柯西概率函數定義如下:

(12)

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

(13)

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

(14)

其中:

2.5 特征選擇策略

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

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

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

根據評估最優值變化情況來判斷是否需要使用特征選擇策略.當長時間出現最優值變化過小時,則采用特征選擇策略;當特征選擇算法結束后,評估當前最優解向量的對稱性,對稱性高時不再采用特征選擇策略.

算法1.特征選擇算法

輸入:未被選擇過的特征集合S,需要選擇特征的個數k

輸出:被選中特征下標(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)基礎上,為了提升FPA算法的性能,從多個角度對算法進行改進和修正,首次提出混合自適應控制策略[10]、全局搜索策略[17]、局部搜索策略[18]、基于梯度信息的精英擾動策略[19,20]、特征選擇策略的多策略混合的花朵授粉算法(MPFA),其算法流程如算法2,其中N、dim、itermax、population分別為種群數量、個體特征維度、最大迭代次數、種群.

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

輸入:N,dim,itermax.

輸出:最優值(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 實驗設計

3.1 實驗條件設置

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

實驗硬件環境為:Inter i7 CPU 2.50GHz、RAM 8.0G、Windows10 操作系統,Matlab R2016a.

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

3.2 全局搜索性能對比

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

表1 測試函數Table 1 Test functions

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

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

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

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

3.3 搜索精度分析

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

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

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

表4 算法復雜度對比表Table 4 Table of algorithm complexity comparison

3.4 收斂速度分析

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

在BentCigar函數上,算法迭代初期所有算法收斂速度都較慢,MFPA經過一個轉折點后就開始快速的下降.在Michalewiz函數中,MFPA算法即使陷入局部最優也能在一定代數后跳出局部最優,下降速率也是最高的.對Sphere、Stybinski函數而言,MFPA收斂速度明顯優于其他算法.在Tablet函數中,MFPA算法的收斂速度要稍慢于SCSSA算法,但是最終達到一致的精度.在Schwefel函數中,在算法初期MFPA收斂速度要比HSFPA算法慢,但是到了算法迭代中期則實現了反超.

在Booth&Lee函數中,FPA算法收斂速度要明顯高于其他算法,而其他算法無明顯差異.在McCormick函數中,MFPA下降速度明顯快于其他函數.通過實驗結果對比,在低維測試函數上,初始種群的分布對于算法的收斂性能夠較大影響.MFPA有著良好的收斂速度,盡管在算法迭代前期在一些情況下收斂速度不足,但在算法迭代中期出現了收斂速度強勁的現象,這也反映出MFPA有著較為優秀的跳出停滯現象的能力.

3.5 算法復雜度分析

在算法執行過程中,時間主要消耗在計算目標函數值和梯度上.假設目標函數計算與梯度計算時間分別設為TF,TG,而其他步驟均為O(1).種群個體向量更新的復雜度為O(1),種群進行全局搜不需要進行梯度計算,則單個個體全局搜索時間復雜度為:O(TF+1).

局部搜索種群個體需要進行梯度計算,因此單個個體局部搜索的時間復雜度為:O(TF+TG+1).全局搜索與局部搜索個體比值為:1-p:p.種群最優個體只進行最優個體擾動策略,其需要計算梯度與目標函數值,算法單次迭代時間復雜度為: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

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

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

4 總 結

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