段艷明,肖輝輝,譚黔林,趙翠芹

(河池學(xué)院 大數(shù)據(jù)與計算機學(xué)院,河池 546300)

1 引言

學(xué)者Yang 受顯花植物繁殖機理的啟發(fā),提出了一種名為花授粉算法(flower pollination algorithm,FPA)[1]的智能優(yōu)化算法.該算法仿生原理簡單、參數(shù)較少、易調(diào)節(jié),運用轉(zhuǎn)換概率參數(shù)p好地解決了探測和開采之間的平衡問題.當(dāng)前,FPA 算法主要在函數(shù)(包括無約束函數(shù)和約束函數(shù))優(yōu)化、能源、通信等應(yīng)用領(lǐng)域得到了廣泛運用,其具體應(yīng)用如下:

(1)函數(shù)優(yōu)化領(lǐng)域

函數(shù)優(yōu)化是屬于連續(xù)優(yōu)化問題,可分為無約束函數(shù)優(yōu)化和帶約束的函數(shù)優(yōu)化.郭慶等[2]分析了FPA 算法在求解多模態(tài)優(yōu)化問題時存在的不足,分別利用模擬退火和單純形法思想對FPA 算法的全局搜索和局部搜索進行了改進了,設(shè)計出一種新的FPA 算法框架;最后,利用改進算法對多種類型的測試函數(shù)進行求解,并與對比算法進行了對比分析,實驗結(jié)果說明改進算法是一種具有良好競爭力的新算法.

(2)能源領(lǐng)域

能源是一個國家的經(jīng)濟命脈,如何提高能源的利用率是一個熱點的研究話題.為此,眾多學(xué)者運用元啟發(fā)式算法來解決該問題,并取得不錯的效果.如用FPA算法對能量流管理[3]、能源交易市場單價預(yù)測[4]、電力調(diào)度[5]等問題進行優(yōu)化求解,并獲得較好的結(jié)果.

(3)通信領(lǐng)域

Rajeswari 等[6]把鮑威爾法引入到花授粉算法中,并用改進的花授粉算法解決傳感網(wǎng)最小能量傳播問題,實驗結(jié)果表明新算法與對比算法相比,更適合解決此類優(yōu)化問題.

雖然該算法在眾多領(lǐng)域中得到了廣泛應(yīng)用,但該算法與其他智能算法一樣,也存在一些不足,如算法演化后期計算速度慢、容易早熟,尋優(yōu)精度不高,魯棒性差等缺陷,導(dǎo)致其在解決大量復(fù)雜優(yōu)化問題時獲得的結(jié)果不盡人意.為了克服這些算法存在上述的不足,提高其收斂能力,當(dāng)前眾多學(xué)者依據(jù)各種智能算法的特征和優(yōu)缺點,運用了諸多的策略和方法對其進行了改進,構(gòu)建了許多優(yōu)化能力更強的新算法模型,使得大量的工程優(yōu)化問題得到更好的解決.

Zhou 等[7]在FPA 算法的勘探部分融入精英反向?qū)W習(xí)策略的組合探測搜索機制,以增加個體之間的差異性,擴展算法的探索領(lǐng)域; 在算法的開發(fā)部分加入貪婪搜索機制構(gòu)造新的局部搜索策略,以提高算法的開采能力; 同時對參數(shù)p運用了動態(tài)調(diào)整策略.實驗結(jié)果表明改進算法的尋優(yōu)能力得到了一定提升.一方面,該算法利用精英所具有的豐富信息,可有效提升算法的性能; 另一方面,在該算法演化過程中,由于精英起著重要作用,將引導(dǎo)種群快速向最優(yōu)解靠近,因此,若精英一旦陷入局部極值,則導(dǎo)致整個種群停滯進化,易造成算法陷入“早熟”問題.

Abdel-Raouf 等[8]把particle swarm optimization(PSO)算法融合到FPA 算法中,即把PSO 算法優(yōu)化后的種群作為FPA 算法的初始解,同時通過混沌映射對算法的參數(shù)進行調(diào)節(jié),這使算法解的質(zhì)量得到了改善,但該算法由于缺乏增加種群多樣性機制,使其在演化中種群的多樣性不能得到較好的保持,易陷入局部最優(yōu).Lenin 等[9]先對和聲算法增加混沌策略進行改進,再把其優(yōu)化后的種群作為花授粉算法的初始解,提高算法初始解的質(zhì)量,提升了算法的尋優(yōu)性能,但其同樣存在文獻(xiàn)[8]的不足.

Tawhid 等[10]利用鯨魚優(yōu)化算法的搜索獵物策略和攻擊獵物方法替換了FPA 算法的全局搜索策略,構(gòu)建了一種新的混合算法whale optimization algorithm and flower pollination algorithm (WOFPA),其性能與對比算法相比,得到了一定程度的提升,但該算法增加了較多的參數(shù),降低了算法的靈活性,同時新算法只在低維上驗證了其性能的優(yōu)越性,沒有在高維得到驗證,使其缺少了說服力.

Draa[11]對FPA 算法進行了定性、定量分析及其改進.首先,從改進的FPA 算法文獻(xiàn)中所利用的測試函數(shù)、實驗驗證方式及傳統(tǒng)FPA 算法參數(shù)值的設(shè)置3 個方面進行了詳細(xì)的定性分析; 其次,依據(jù)定性分析的結(jié)果,作者對參數(shù)p的值設(shè)置進行了較全面的實驗對比分析,分析結(jié)果表明當(dāng)p的值取0.2 時,該算法的尋優(yōu)能力獲得最佳; 最后,根據(jù)上述的定性分析和定量分析實驗,作者把反向?qū)W習(xí)方法引入到該算法中以達(dá)到提高其尋優(yōu)能力,優(yōu)化結(jié)果說明該改進策略是行之有效的.但是,反向?qū)W習(xí)機制對算法的改善還是很有限的,其原因在于學(xué)習(xí)機制過于簡單,不能很好地提取和利用較劣粒子所隱含的有益信息[12]; 同時在進化后期,大部分反向點及原點都集中到小范圍區(qū)域,使反向點的適應(yīng)度值并不比原值較優(yōu),所以在演化后期試圖通過反向的方式很難跳出當(dāng)前的極值區(qū)域[13],其依然不能解決算法陷入局部最優(yōu)、收斂精度低的問題.另外,在該算法中是以一定概率采用反向?qū)W習(xí)策略,擴大了算法的隨機性,從而減緩了其收斂速度.

綜上所述,目前的一些改進方法對FPA 算法的優(yōu)化能力起到了一定的提升作用,但這些方法沒有對種群個體之間的信息進行有效利用,造成種群的多樣性在演化過程中不能較好地保持,使算法易“早熟”,影響了其全局優(yōu)化能力; 同時,當(dāng)前改進的FPA 算法在對多模態(tài)等復(fù)雜問題進行求解時,其求解精度、穩(wěn)定性及求解速度等方面還有較大的提升空間,且有些改進措施增加了算法的時間復(fù)雜度,降低了算法的靈活性,另外一些改進策略對基本的FPA 算法原有的仿生原理做了相應(yīng)的修改.

為了解決在提高算法的收斂速度、解的質(zhì)量的同時防止算法“早熟”的問題,本文構(gòu)建了一種把改進的教與學(xué)優(yōu)化算法[14]中的教與學(xué)思想及動態(tài)高斯變異融入到花授粉算法中的改進算法(teaching learning Gauss flower pollination algorithm,TLGFPA).

TLGFPA 算法的基本思想: 首先,根據(jù)總迭代次數(shù)與當(dāng)前迭代次數(shù)的關(guān)系對教與學(xué)優(yōu)化算法中的教學(xué)因子進行改進,并把改進的教機制作用于花授粉算法中的全局尋優(yōu)部分,充分利用最優(yōu)個體(教師)與其他個體(學(xué)生或?qū)W員)間的促進作用來提高算法的收斂速度;其次,把教與學(xué)優(yōu)化算法中的學(xué)機制作用于花授粉算法中的局部尋優(yōu)部分,通過個體(學(xué)生或?qū)W員)之間的相互學(xué)習(xí)來保持種群的多樣性,提高其求解精度; 最后,在教與學(xué)優(yōu)化算法的教階段的進化過程中,由于超級個體(教師)不斷吸引其他普通個體(學(xué)生),使得種群個體之間的差異性不能到較好的保持,從而易造成算法“早熟”,因此,在進化過程中需要判斷算法是否陷入“早熟”進行處理,若“早熟”,則利用動態(tài)高斯變異策略對種群的中間個體進行擾動,增加種群個體之間的差異性,防止算法過早收斂.

首先,通過對16 個經(jīng)典的優(yōu)化問題進行求解,求解結(jié)果顯示新算法與FPA 算法相比,其優(yōu)化能力得到了較顯著提升; 其次,選擇了3 種FPA 改進算法進行了對比實驗,對比分析結(jié)果顯示新算法的性能總體上要好于對比算法,顯示出較好的競爭力.最后,運用TLGFPA 算法對伸縮繩應(yīng)用問題進行求解,同樣也得到了較好的優(yōu)化結(jié)果,進一步驗證了TLGFPA 算法的有效性和可行性.

本文的創(chuàng)新工作主要包括:

(1)為了解決教學(xué)機制容易導(dǎo)致教與學(xué)算法“早熟”問題,本文對該算法的教學(xué)因子進行改進,使其隨著迭代的進行而動態(tài)調(diào)整,能夠較好地解決其的勘探和開采能力平衡問題.

(2)把改進的教機制作用于花授粉算法中的全局尋優(yōu)部分,充分運用最優(yōu)個體(教師)與其他個體(學(xué)生或?qū)W員)間的促進作用來提升算法的搜索速度; 同時把教與學(xué)優(yōu)化算法中的學(xué)機制作用于花授粉算法中的局部尋優(yōu)部分,通過種群個體之間的相互交流學(xué)習(xí)來維持種群的多樣性,改進其求解精度.

(3)在算法中融入了動態(tài)高斯變異策略來提高種群個體之間的差異性,防止算法“早熟”而導(dǎo)致整個種群進化陷入停滯狀態(tài).

本文第2 節(jié)對FPA 算法進行了簡單描述; 第3 節(jié)對教與學(xué)優(yōu)化算法、改進的教與學(xué)優(yōu)化算法、動態(tài)高斯變異機制、TLGFPA 算法以及該算法的時間復(fù)雜度進行了闡述; 第4 節(jié)進行實驗評測; 第5 節(jié)對本文的研究工作進行歸納,并對今后的研究方向進行展望.

2 FPA 算法

該算法的仿生原理是對花朵植物繁殖過程(異花和自花授粉)的模擬,花朵植物的異花授粉過程是通過昆蟲等方式來實現(xiàn)授粉繁殖,具有萊維飛行的特征,FPA 算法的全局搜索策略模擬了該過程,這使其具有良好的全局優(yōu)化能力,花朵植物的自花授粉是通過同株上的花朵自行傳粉繁殖,傳播距離非常小,這個過程對應(yīng)于FPA 算法的局部搜索過程.同時,該算法運用參數(shù)p來解決其的勘探和開采能力平衡問題,這使其具有較好的全局尋優(yōu)能力.為了利用該算法更好地解決一系列實踐中復(fù)雜的優(yōu)化問題,還必須對其設(shè)定4 條約定,其詳情見文獻(xiàn)[1].依據(jù)上述思路,學(xué)者Yang[1]利用以下公式對其實現(xiàn)了數(shù)學(xué)模型化.

FPA 算法的探索機制(全局搜索策略)是采用式(1)進行模型化:

其中,,表示算法進化中第t、t+1 代對應(yīng)的解,g*表示種群中的最優(yōu)個體,γ是對步長進行控制的伸縮因子,L(λ)表示種群個體的Lévy 步長,其值運用式(2)計算:

其中,λ取值1.5,G(λ)表示Gamma 函數(shù),s的值通過式(3)計算得到:

其中,μ～N(0,σ2),V～N(0,1),σ2的值采用式(4)計算:

FPA 算法的種群個體采用式(5)實現(xiàn)開發(fā)搜索(局部搜索):

其中,ε∈[0,1]上產(chǎn)生的隨機數(shù),xtj,xtk是隨機選擇的不同于xti的兩個不同的種群個體.

3 教與學(xué)優(yōu)化策略的動態(tài)變異花授粉算法

3.1 教與學(xué)優(yōu)化算法

受教與學(xué)的啟發(fā),Rao 等[14]設(shè)計了一種名為教與學(xué)優(yōu)化算法(TLBO),該算法模擬了教師的教學(xué)過程及學(xué)生之間的相互學(xué)習(xí)和交流的過程.該算法的種群個體分為教師和學(xué)生兩類,教師是超級個體,學(xué)生是普通個體,其所學(xué)科目數(shù)對應(yīng)問題的維數(shù).TLBO 算法把進化過程分為“教學(xué)”與“學(xué)習(xí)”兩個時段,在“教學(xué)時段”是普通個體(學(xué)生)向最優(yōu)個體(教師)不斷學(xué)習(xí)的過程,從而達(dá)到提升學(xué)生的成績,同時結(jié)合了種群均值的作用,能有效地融合最優(yōu)個體與普通個體的相互促進作用; 在“學(xué)習(xí)時段”,隨機選取兩個種群個體,并比較其優(yōu)劣,劣者向優(yōu)者學(xué)習(xí).

教與學(xué)優(yōu)化算法的具體實施過程如下.

Step 1.對算法種群(班級)個體的位置利用式(6)進行隨機初始化:

其中,和分別為解空間自變量xi的上界和下界,D為解空間的維數(shù),rand(0,1)∈(0,1)之間的任意數(shù).

Step 2.教學(xué)時段.每個普通個體(學(xué)生)通過最優(yōu)個體(教師)和學(xué)生平均值之間的差異來向教師(最優(yōu)個體)學(xué)習(xí),首先求解當(dāng)前種群每一維的平均值xmean,再利用式(7)計算教師與學(xué)生的差異,最后利用式(8)實現(xiàn)位置更新,即完成教的過程:

其中,xteacher是種群中的超級個體,s=rand(0,1)為學(xué)習(xí)步長,tf=round(1+rand(0,1))為教學(xué)因子.

Step 3.對普通個體(學(xué)生)位置進行更新.每個學(xué)生依據(jù)學(xué)習(xí)的效果決定對當(dāng)前的位置是否更新,若優(yōu)對其當(dāng)前位置進行更新,否則保留其原有位置.

Step 4.學(xué)習(xí)時段.對種群中每個普通個體(學(xué)生)xi,隨機選取其學(xué)習(xí)對象xj(i≠j)進行學(xué)習(xí),通過計算兩者間的目標(biāo)函數(shù)適應(yīng)度值來進行調(diào)整位置,即利用式(9)來進行學(xué)生間的學(xué)習(xí):

其中,f(xi)和f(xj)分別表示個體xi和xj的目標(biāo)函數(shù)適應(yīng)度值,s=rand(0,1)為學(xué)習(xí)步長.

Step 5.對普通個體(學(xué)生)位置進行更新.每個學(xué)生依據(jù)學(xué)習(xí)的效果決定對當(dāng)前的位置是否替換,若優(yōu),替換,反之保留原有位置.

Step 6.對算法的演化條件進行判斷,如條件成立,則優(yōu)化結(jié)束,并輸出算法的最優(yōu)值和其對應(yīng)的最優(yōu)解,否則進化繼續(xù)并轉(zhuǎn)Step 2.

3.2 動態(tài)高斯變異

高斯分布是一類重要的概率分布函數(shù),在眾多領(lǐng)域得到廣泛應(yīng)用,其計算公式如式(10):

其中,σ、μ為分別表示為方差為1 和均值為0.

動態(tài)高斯變異的思想是給原有個體增加一個擾動項,其具體形式如下:

其中,m=(Max_iter-t)/Max_iter,即m∈(1,0]為遞減變量;xi表示為算法在進化代數(shù)為t時個體i所對應(yīng)的狀態(tài);N(0,1)是服從高斯分布的一個任意向量;Max_iter表示算法的最大進化代數(shù),t表示為算法當(dāng)前進化的代數(shù).

動態(tài)高斯變異機制能在一定程度上增加了種群個體之間的差異性,能使個體有效跳出局部極值進行全局搜索,同時提高收斂速度.

3.3 改進的教與學(xué)優(yōu)化機制

3.3.1 TLBO 算法存在的問題

根據(jù)第3.1 節(jié)可知,TLBO 算法主要由“教學(xué)時段”和“學(xué)習(xí)時段”兩個核心部分構(gòu)成,但由于該算法的搜索機制存在以下問題,使其優(yōu)化能力受到一定的影響:

問題1.在TLBO 算法的教學(xué)時段,教學(xué)因子tf左右著學(xué)生個體與教師個體的差異,tf的大小決定著算法在該階段的搜索能力,tf越小,則搜索能力越強.但從基本TLBO 算法的教學(xué)因子的計算公式可知,其值隨機地在[1,2]中取值,沒有考慮到隨算法的進化而相應(yīng)地調(diào)整該值,從而使教學(xué)階段易陷入兩種極端的狀況,學(xué)生要么學(xué)得很好,要么學(xué)得很差,但在實際的教學(xué)過程中,學(xué)生個體是以任何概率從教師處學(xué)到知識.而且,在教學(xué)前期,學(xué)生個體與教師個體的差距是較大的,到教學(xué)后期,學(xué)生個體與教師個體的差距就會不斷縮小.

問題2: 從TLBO 算法的教學(xué)階段可知,通過普通個體(學(xué)生)之間小范圍的相互交流學(xué)習(xí)來提升各自的成績,這使種群個體之間的差異性能夠得到較好的保持,從而保證了算法的持續(xù)全局尋優(yōu)能力.但是,在TLBO 算法的教學(xué)階段,每個學(xué)生(個體)都向教師(最優(yōu)個體)學(xué)習(xí),雖然能快速提高搜索速度,但更易導(dǎo)致種群陷入局部最優(yōu).

3.3.2 對TLBO 算法進行改進

(1)對TLBO 算法的教學(xué)因子tf進行改進

針對第1 個問題,本文對教學(xué)因子tf做了改進,使其隨著迭代的進行而線性遞減,把教學(xué)因子tf的計算公式修改為:

其中,tfmin是tf取的最小值,tfmax是tf取的最大值,N_iter、t分別表示為算法的最大進化代數(shù)和當(dāng)前進化的代數(shù).

從式(12)中可以看出,tf的值在算法進化的前期取值較大,這有利于學(xué)生的學(xué)習(xí)速度和學(xué)習(xí)能力的提高,從而達(dá)到提升算法的勘探能力,提高算法的尋優(yōu)速度; 在算法進化的后期,學(xué)生的學(xué)習(xí)速度和學(xué)習(xí)能力顯著下降,教學(xué)因子tf的值變小,有利于提高算法的開采能力,促進種群個體向理論解靠近,提高解的精度.

(2)融入動態(tài)高斯變異機制

針對問題2,本文把高斯變異機制融入到TLGFPA算法中,從而進一步改善算法的優(yōu)化能力.這是因為TLGFPA 算法的全局授粉部分引入了TLBO 算法的教機制,而TLBO 算法的教階段在進化過程中,由于超級個體(教師)不斷吸引其他普通個體(學(xué)生),使得種群個體在進化過程容易同化,從而易造成算法陷入局部最優(yōu).為此,在進化過程中需要對算法是否陷入“早熟”進行判斷,若“早熟”,則利用動態(tài)高斯變異策略對種群的中間個體進行擾動,增加種群個體之間的差異性,防止算法過早收斂.

3.4 TLGFPA 算法

從式(1)可知,FPA 算法采用了Lévy 策略使其具有良好的勘探能力,但該策略也使其求解精度較低及收斂速度慢; 而其局部搜索部分利用了差分進化(DE)思想,這使其在解決高維復(fù)雜的優(yōu)化問題時,性能比較差; 同時,跟其他群智能算法類似,該算法在演化的后期,隨著種群多樣性的減少,算法容易早熟.然而該算法運用轉(zhuǎn)化概率參數(shù)p來平衡該算法的勘探和開采能力.“教與學(xué)”優(yōu)化算法(TLBO)是最近提出的一種新群智能算法,根據(jù)其仿生機理,其具有極強的收斂能力且求解速度快、精度高優(yōu)點,但該算法的教階段使算法易陷入早熟,且其“探索”與“開采”能力之間的平衡問題沒得到較好的處理.依據(jù)兩種算法的結(jié)構(gòu)及特性,把TLBO 算法引入到花授粉算法中,使其取長補短,提高算法的性能.鑒于此,本文提出了融合教與學(xué)優(yōu)化策略的動態(tài)變異花授粉算法TLGFPA,先根據(jù)總迭代次數(shù)與當(dāng)前迭代次數(shù)的關(guān)系對教與學(xué)優(yōu)化算法中的教學(xué)因子進行改進,接著把改進的教機制作用于花授粉算法中的全局尋優(yōu)部分,充分利用最優(yōu)個體與其他個體間的促進作用來提高算法的搜索速度; 同時把教與學(xué)優(yōu)化算法中的學(xué)機制作用于花授粉算法中的局部尋優(yōu)部分,通過種群個體之間的相互交流學(xué)習(xí)來維系種群的多樣性,提高其計算精度; 最后,如果適應(yīng)度值連續(xù)迭代3 次沒有改進或改進很小,則對進入下一代的中間種群個體進行動態(tài)高斯變異,增強種群的多樣性,避免過早收斂.通過融合多種策略,提高算法的尋優(yōu)性能.

TLGFPA 算法的偽代碼如算法1 所示,其中,n為種群規(guī)模,p是算法的全局搜索和局部搜索之間的轉(zhuǎn)換概率,N_iter是算法的最大進化代數(shù),ε∈[0,1]的任意數(shù),fmin為種群個體中的最優(yōu)值,g*為最優(yōu)解,fitness 為函數(shù)適應(yīng)度值,xi為種群的第i個體.

算法1.TLGFPA 算法偽代碼1.初始化所有參數(shù)2.for i=1: n 3.隨機產(chǎn)生 n 個個體 {xi | i=1,2,…,n};4.計算每個個體或每個解的適應(yīng)度值;5.end 6.計算當(dāng)前種群的最優(yōu)值7.找出當(dāng)前種群最優(yōu)值對應(yīng)的最優(yōu)解;8.% TLGFPA 算法開始迭代9.for t=1: N_iter (總的迭代次數(shù))do 10.for i=1: n do 11.if p＞rand(0,1)then 12./*全局尋優(yōu)*/13.根據(jù)式(10)計算 tf 的值;14.計算種群個體的平均值 Solmean;15.根據(jù)式(7)計算 dif 值;

16.根據(jù)式(1)和式(8)產(chǎn)生一個新的候選解;xt+1 i xt+1 i 17.對 進行越界判斷18.else 19./* 局部尋優(yōu)*/xtj xtk 20.隨機產(chǎn)生兩個個體 和 ;xt+1 i 21.根據(jù)式(9)產(chǎn)生一個新的候選解;xt+1 i 22.對 進行越界判斷23.end 24.找出當(dāng)前種群的最優(yōu)值和其對應(yīng)的最優(yōu)解fun(xt+1 i))25.if (t＞=3 && abs((-))＜δ)|| (t＞=3 && abs((-))=0)26.高斯變異xt+1 i fun(xti))fin(xti fun(xt+1 i 27.對 進行越界判斷28.找出當(dāng)前種群的最優(yōu)值和其對應(yīng)的最優(yōu)解29.end 30.end 31.end

TLGFPA 算法的實現(xiàn)過程如下.

步驟1.對TLGFPA 算法的種群規(guī)模n,全局和局部搜索轉(zhuǎn)換參數(shù)p,最大進化代數(shù)N_iter,問題規(guī)模D,教學(xué)因子的最大值tfmax,教學(xué)因子的最小值tfmin,分別進行賦值.

步驟2.對算法的種群進行初始化,求解每個解的值,并記錄所有值中的最小值或最大值和其相應(yīng)的解.

步驟3.若p＞rand(0,1),利用式(12)計算教學(xué)因子tf的值.

步驟4.計算種群的平均位置Solmean.

步驟5.運用式(7)計算最優(yōu)花朵與種群的差異dif.

步驟6.利用式(1)、式(8)對花朵個體的位置進行更新,并對新產(chǎn)生的解是否超出解的范圍進行處理.

步驟7.如果p＜rand(0,1),根據(jù)式(9)對花朵個體的位置進行更新,并對新產(chǎn)生的解是否超出解的范圍進行處理.

步驟8.對步驟6 或步驟7 產(chǎn)生的新個體進行求解,并更新fmin和g*.

步驟9.如果連續(xù)3 次,適應(yīng)度值沒變或變化很小,則執(zhí)行步驟10,否則跳到步驟11.

步驟10.對種群中間個體進行動態(tài)高斯變異.

步驟11.如進化代數(shù)大于閾值N_iter,則進化結(jié)束,并輸出所有解中的最優(yōu)解和其相應(yīng)的適應(yīng)度值,否則,轉(zhuǎn)步驟3 繼續(xù)進化.

3.5 TLGFPA 算法的時間復(fù)雜度分析

改進措施對算法性能的提升是否可行,主要從兩個方面來衡量: (1)改進策略能較好地改善算法的性能;(2)改進算法的靈活性要好,且算法的時間復(fù)雜度值要小.算法的時間復(fù)雜度與其進化代數(shù)成正比例.倘若f(x)為求解的問題,D為求解問題的規(guī)模,則依據(jù)算法時間復(fù)雜度的求解原則和FPA 算法的優(yōu)化機理,FPA算法的時間復(fù)雜度表示為:T(FPA)=O(D+f(D)).從TLGFPA 算法的具體實現(xiàn)過程可知,步驟3-步驟7 和步驟9 是新算法添加的步驟,即包括計算教學(xué)因子tf、計算種群的平均位置Solmean、計算最優(yōu)花朵與種群的差異dif、更新花朵個體的位置和動態(tài)高斯變異.依據(jù)上述公式的闡述和時間復(fù)雜度的求解規(guī)則,則可推導(dǎo)出TLGFPA 的時間復(fù)雜度表示為:T(TLGFPA)=T(FPA)+T(計算教學(xué)因子)+T(計算種群的平均位置)+T(計算最優(yōu)花朵與種群的差異)+T(更新花朵個體的位置)+T(高斯變異)=O(D+f(D))+T(1)+T(1)+O(D+f(D))+O(D+f(D))+O(D+f(D))=O(D+f(D)).從上述對改進算法的時間復(fù)雜度理論分析結(jié)果可知,改進算法與FPA 算法相比,其時間復(fù)雜度基本相同.

4 實驗仿真及分析

4.1 測試函數(shù)仿真及分析

為了驗證本文算法的可行性和有效性,本節(jié)選用4 類共16 個非常具有代表性的測試函數(shù)進行實驗,其具體詳情見表1.本節(jié)實驗除了與FPA 算法比較外,還與人工蜂群(artificial bee colony,ABC)算法[15]、動態(tài)領(lǐng)域?qū)W習(xí)粒子群(dynamic neighborhood learning particle swarm optimizer,DNLPSO)算法[16]、TLBO 算法、基于教與學(xué)的花授粉算法(teaching learning flower pollination algorithm,TLFPA)進行比較.實驗中所有參數(shù)的具體設(shè)定為: 種群規(guī)模n=30,最大進化代數(shù)MaxN_iter=5000,FPA、TLFPA 和TLGFPA 三種算法的p的值都取0.2; DNLPSO 算法的其他參數(shù)值來自文獻(xiàn)[16]; ABC 算法中,limit=100.

表1 本文使用的實驗測試函數(shù)

4.1.1 固定迭代次數(shù)的性能比較

為了驗證本文算法的有效性,佐證其收斂精度(解的質(zhì)量)的優(yōu)越性,且能較好地防止陷入局部最優(yōu),所有算法在每個求解問題上都獨自執(zhí)行30 次,求解出其對應(yīng)的Mean error (尋優(yōu)均值偏差)、St.dev (標(biāo)準(zhǔn)方差)值,并為了判定TLGFPA 算法與其余5 種對比算法尋優(yōu)性能是否存在顯著性差異,利用非參數(shù)統(tǒng)計檢驗(α=0.05 的Wilcoxon 檢驗)分別對16 個函數(shù)的實驗結(jié)果進行統(tǒng)計分析,其分析結(jié)果見表2,其中符號“?”,“≈”,“?”分別說明TLGFPA 算法的尋優(yōu)精度遜于、相當(dāng)于和高于其余算法,“w/t/l”符號分別說明TLGFPA算法與對比算法對比,在求解問題上,有w個的優(yōu)化結(jié)果好于比較算法,有t個的尋優(yōu)結(jié)果與比較算法相當(dāng),有l(wèi)個的優(yōu)化效果劣于比較算法.

表2 在固定進化代數(shù)下算法的尋優(yōu)能力對比(D=30,4,2)

對表2 分析獲得,TLGFPA 算法與ABC,DNLPSO,TLBO,FPA 及TLFPA 算法相比,有8 個函數(shù)能找到理論最優(yōu)值,3 個函數(shù)找的值接近理論值.與TLFPA 算法相比,只有在函數(shù)F07 上,尋優(yōu)均值偏差要劣于對比算法,說明加入“動態(tài)高斯變異”策略,能使算法避免陷入局部最優(yōu),提高了算法的收斂精度,同時也提升了算法的魯棒性.與ABC,DNLPSO,TLBO 及FPA 算法比較,在16 個函數(shù)上,分別有12、15、14、15 個函數(shù)的尋優(yōu)均值偏差要好于對比算法,這說明TLGFPA 算法的優(yōu)化精度明顯優(yōu)于對比的算法,驗證了本文提出的新算法是可行有效的,達(dá)到了改進的目的.

為了佐證新算法在高維函數(shù)上的優(yōu)化能力同樣表現(xiàn)出色,表3 列出了6 種算法在14 個函數(shù)上D=100 的優(yōu)化結(jié)果,并對實驗結(jié)果從數(shù)學(xué)角度進行統(tǒng)計分析.從表3 可以獲得,TLGFPA 算法有7 個函數(shù)能找到理論最優(yōu)值,2 個函數(shù)找的值無限接近理論值,與TLFPA 算法相比,只有函數(shù)F03 和F07 的尋優(yōu)均值偏差要遜于該算法,與其余4 種算法對比,本文算法的求解精度優(yōu)勢較顯著.

表3 6 種算法在固定迭代次數(shù)下的尋優(yōu)性能比較(D=100)

綜上所述,本文提出的新算法在4 類不同求解問題上的尋優(yōu)能力與對比算法相比,其優(yōu)化能力要優(yōu)于對比算法,也說明本文算法能較好地解決“早熟”問題.

4.1.2 固定尋優(yōu)精度的性能對比

為了比較TLGFPA 算法的穩(wěn)定性和尋優(yōu)速度,在尋優(yōu)精度固定下,檢驗其收斂速度和魯棒性的優(yōu)越性,其實驗結(jié)果如表4 所示.本節(jié)所有算法在每一個求解問題上都設(shè)置了一個固定的尋優(yōu)精度邊界值,若算法收斂到上述設(shè)定的閾值(邊界值)且進化代數(shù)已大于一定的代數(shù)(本文設(shè)置為3 000),則斷定該算法對該求解問題尋優(yōu)失敗; 其他參數(shù)設(shè)置同上,對比算法在每個求解問題上獨立執(zhí)行30 次; 計算出SR(執(zhí)行成功率,執(zhí)行成功率=算法找到求解精度邊界值所需要的代數(shù)/算法總的執(zhí)行代數(shù))值和mean_iter(平均進化代數(shù))值,對比算法的SR越大且mean_iter越小,其性能越優(yōu),表4 中符號“NA”表示對比算法尋優(yōu)受挫,最好結(jié)果用加粗突出顯示.從表4 中可獲得,FPA 算法只有在2 個求解問題上的尋優(yōu)成功率達(dá)到100%,其余都是0,對于函數(shù)F05,所有算法都尋優(yōu)失敗,這是由于該函數(shù)的特殊屬性,使得很多群智能算法很難找到其全局極小值.TLGFPA 算法和TLFPA 算法在16 個函數(shù)上,都有11 個函數(shù)的尋優(yōu)成功率是100%,但是TLGFPA 算法在這11 個函數(shù)上的平均收斂迭代次數(shù)都小于TLFPA算法,尤其在函數(shù)F01、F15、F16 上,TLGFPA 算法的平均收斂迭代次數(shù)比TLFPA 算法小1 個數(shù)量級,這說明加入“動態(tài)高斯變異”機制,能有效提高算法的收斂速度.與其余4 種算法相比,TLGFPA 算法的mean_iter和SR值明顯好于對比算法,說明TLGFPA 算法的求解速度和穩(wěn)定性要優(yōu)于比較算法.

由表4 可知,FPA 算法的總的平均尋優(yōu)成功率只有12.5%,通過在FPA 算法中引入新的策略,TLFPA和TLGFPA 算法的尋優(yōu)成功率得到大幅度提升,其中TLGFPA 算法的尋優(yōu)成功率為65%,是6 種算法中最高的,說明TLGFPA 算法的穩(wěn)定性最強.

表4 6 種算法的尋優(yōu)成功率、平均迭代次數(shù)比較

4.1.3 Friedman 與Wilcoxon 檢驗

為了更客觀評價對比算法的綜合優(yōu)化能力,本節(jié)從數(shù)學(xué)統(tǒng)計的角度(非參數(shù)Friedman 統(tǒng)計檢驗)進行對比實驗,其對比結(jié)果見表5 和表6 所示,分別是所有算法在16 個函數(shù)(維數(shù)D=30,函數(shù)F13、F14 的維數(shù)分別為4 和2)和14 個函數(shù)(維數(shù)D=100)上的Friedman的檢驗結(jié)果,從表5 和表6 可以看出,TLGFPA 算法不管在低維還是在高維上,總體性能最好,則進一步說明改進的算法是有效的.

表5 對比算法在16 個函數(shù)上的Friedman’s test (D=30,4,2)

表6 對比算法在14 個函數(shù)上的Friedman’s test (D=100)

為了更深入地對算法的優(yōu)化能力進行綜合評價比較,運用a=0.05 的Wilcoxon 檢驗分析,其對比分析結(jié)果見表7 和表8,從兩個表中獲得,TLGFPA 算法與ABC,DNLPSO,TLBO 和FPA 算法之間的優(yōu)化性能的差于性比較顯著,與TLFPA 顯著性差異要弱一些,但也小于0.05.這表明改進策略對提升FPA 算法的尋優(yōu)性能是可行有效的.

表7 對比算法在16 個函數(shù)上的Wilcoxon’s test (D=30,4,2)

表8 對比算法在14 個函數(shù)上的Wilcoxon’s test (D=100)

4.1.4 尋優(yōu)性能對比分析圖

為了更直觀地表明TLGFPA 算法的整體尋優(yōu)性能優(yōu)于其余對比算法,本文畫出了部分求解問題上的算法求解過程曲線圖,具體見圖1.從圖1 可知,TLGFPA算法與其他5 種對比算法相比,其優(yōu)化能力明顯好于其他算法,其經(jīng)過少量的進化代數(shù)就能找到理論最優(yōu)值或接近理論上的最優(yōu)值; 在F06 和F16 求解問題上,TLGFPA 算法和TLFPA 算法的優(yōu)化能力旗鼓相當(dāng),但明顯好于其余對比算法,在F05 和F11 函數(shù)上,TLGFPA算法的求解精度要劣于ABC 算法,但比其他對比算法好; 對于函數(shù)F07,TLGFPA 算法要劣于TLBO,FPA和TLFPA 算法,但略好于其他2 種對比算法.這說明TLGFPA 的優(yōu)化過程得到提速,尋優(yōu)精度得到提高.

圖1 6 種算法的適應(yīng)度值收斂曲線

同時,為了進一步深入地說明TLGFPA 算法在求解問題過程中的魯棒性和解的質(zhì)量優(yōu)于FPA 等對比算法,本文也畫出了對比算法在部分求解問題上執(zhí)行30 次的優(yōu)化結(jié)果變化對比圖和所有算法在求解問題上的方差對比分析圖,具體分別見圖2 和圖3.可見在這4 類函數(shù)上,TLGFPA 算法的求解精度、穩(wěn)定性要好于DNLPSO,ABC,TLBO 和FPA 對比算法,而略好于TLFPA 算法.這進一步顯示改進算法在求解精度、穩(wěn)定性上都得到了較好的提升.

圖2 6 種算法在部分函數(shù)上的最優(yōu)適應(yīng)度值比較圖

圖3 6 種算法的全局最優(yōu)值方差分析

綜上所述,TLGFPA 算法的優(yōu)化能力表現(xiàn)比較突出,驗證了本文改進算法的可行性和有效性,也證明了加入動態(tài)高斯變異的有效性.

4.2 與現(xiàn)有改進的FPA 算法比較

為了測試TLGFPA 算法與現(xiàn)有改進的FPA 算法在性能上是否具有不錯的競爭力,本節(jié)選用3 種改進的FPA 算法進行對比,分別是改進的花授粉算法(modified flower pollination algorithm,MFPA)[11]、基于廣義反向?qū)W習(xí)的改進花授粉算法(modified genera-lised oppsition-based flower pollination algorithm,MGOFPA)[11]及基于精英反向?qū)W習(xí)的花授粉算法(elite oppositionbased flower pollination algorithm,EOFPA)[7],為了更好突出本文算法的優(yōu)勢,在迭代次數(shù)較少(最大迭代次數(shù)為500)的情況下比較4 種算法的尋優(yōu)性能.其中,對于TLGFPA 算法除迭代次數(shù)外,其余實驗參數(shù)和求解問題同第4.1 節(jié); 對于MFPA、MGOFPA 和EOFPA 算法的參數(shù)p取相同的值0.8、種群規(guī)模n=30 和進化代數(shù)不同于相關(guān)文獻(xiàn)外,其他參數(shù)取自相關(guān)文獻(xiàn)中,為了避免實驗的偶然性誤差,每種對比算法在其每個求解問題上都單獨執(zhí)行30 次,各種對比算法的優(yōu)化結(jié)果如表9所示.

從表9 可知,改進算法在所有求解問題上的優(yōu)化能力明顯好于MFPA 算法; 與MGOFPA算法相比,TLGFPA算法的尋優(yōu)能力在93.75%的求解問題上要優(yōu); EOFPA和TLGFPA 算法相比,TLGFPA算法在7 個求解問題上的優(yōu)化能力要比EOFPA 算法優(yōu),尤其是在F02 求解問題上,TLGFPA算法能找到理論上的最優(yōu)解,兩種算法在4 個求解問題(F06、F08、F14 及F15)上的優(yōu)化能力旗鼓相當(dāng),而TLGFPA 算法在剩余5 個求解問題上的尋優(yōu)能力要遜色于EOFPA算法.

為了更直觀地說明TLGFPA算法的優(yōu)化性能好于其余對比算法,本文畫出了對比算法在部分求解問題上的收斂過程曲線圖,具體見圖4.從圖4 可看出,本文算法的求解速度在7 個函數(shù)上是4 種算法中最快的.借助表9 中“?”的數(shù)學(xué)統(tǒng)計結(jié)果和圖4 的收斂曲線可以看出,TLGFPA 算法的性能總體上要優(yōu)于其他改進算法,顯示出較好的競爭力.

圖4 4 種改進的FPA 算法收斂曲線圖

表9 4 種改進算法的尋優(yōu)性能對比

4.3 利用改進算法對伸縮繩應(yīng)用問題進行求解

為了驗證新算法在應(yīng)用優(yōu)化問題上的尋優(yōu)性能,檢驗其可行性和有效性,本文選用伸縮繩應(yīng)用問題進行測試.

4.3.1 伸縮繩問題的描述

在滿足x1(d)、x2(D)和x3(P)三個約束條件下使設(shè)計的繩最輕,其中d、D及P分別表示為“線的直徑”“平均卷的直徑”及“卷數(shù)”.該問題利用式(13)對其進行數(shù)學(xué)模型化,其對應(yīng)的結(jié)構(gòu)如圖5 所示.

圖5 伸縮繩的結(jié)構(gòu)圖

4.3.2 實驗結(jié)果及對比分析

為了進一步佐證本文算法是否行之有效,本節(jié)利用TLGFPA 算法對上述伸縮繩設(shè)計問題進行求解,并與文獻(xiàn)協(xié)同進化差分進化算法(co-evolutionary differential evolution,CDE)[17],一種基于可行性規(guī)則的混合粒子群約束優(yōu)化(hybrid particle swarm optimization with a feasibility-based rule for constrained optimization,HPSO)[18],加速自適應(yīng)權(quán)重模型(accelerating adaptive trade-off model,AATM)[19],社會和文化算法(society and civilization algorithm,SCA)[20],精英教學(xué)優(yōu)化算法(elitist teaching-learning-based optimization,ETLBO)[21],

反饋精英教學(xué)優(yōu)化算法(feedback elitist teachinglearning-based optimization,FETLBO)[22],基于精英反向?qū)W習(xí)的花授粉算法(elite opposition-based flower pollination algorithm,EOFPA)[7]求解結(jié)果進行比較.本節(jié)的實驗參數(shù)分別設(shè)置為: 種群規(guī)模都為25,進化代數(shù)為2 000,其余參數(shù)設(shè)置同第4.1 節(jié),實驗結(jié)果如表10 所示.從表10 可以看出TLGFPA 算法對伸縮繩問題的優(yōu)化效果要優(yōu)于其他5 種算法,這表明本文的改進策略是可行和有效的.

表10 8 種算法對伸縮繩優(yōu)化問題的求解結(jié)果

5 結(jié)論與展望

為了進一步解決花授粉算法的優(yōu)化能力還不太理想的問題,本文提出了先對教與學(xué)優(yōu)化算法中的教學(xué)因子進行改進,再把改進的教與學(xué)優(yōu)化機制和動態(tài)高斯變異融入到花授粉算法中的混合算法(TLGFPA).首先,通過對16 個無約束函數(shù)的仿真實驗顯示新算法能夠較好地解決“早熟”問題,有效地提升了FPA 算法的求解精度和求解速度等性能.其次,選擇了3 種FPA改進算法進行了對比實驗,對比分析結(jié)果顯示TLGFPA算法的性能總體上要優(yōu)于其他改進算法,顯示出較好的競爭力.最后,用TLGFPA 算法求解伸縮繩應(yīng)用優(yōu)化問題,實驗結(jié)果進一步驗證了本文算法在解決應(yīng)用問題時,也比FPA 算法和其他對比算法具有更好的優(yōu)化能力.

雖然本文算法性能還不錯,但在解決大規(guī)模優(yōu)化問題時,其優(yōu)化能力還有待提高,后續(xù)將針對此問題進一步研究.在今后的研究工作中,可以嘗試?yán)酶倪M差分進化算法的思路來對其局部搜索部分進行改進,增強其開發(fā)能力.因為其局部搜索部分是采用了傳統(tǒng)差分進化算法的思想,在優(yōu)化復(fù)雜多維的優(yōu)化問題時,性能較差.同時,將其應(yīng)用領(lǐng)域進一步地進行推廣,如解決動態(tài)組合優(yōu)化問題.其次,目前“二進制的花授粉算法”研究很少,如何將二進制的花授粉算法運用到軟件工程、大數(shù)據(jù)、量子計算等領(lǐng)域?qū)⑹侵档醚芯康膯栴}.