高雷阜 趙世杰 徒 君 于冬梅

(遼寧工程技術大學優(yōu)化與決策研究所 遼寧 阜新 123000)

?

動態(tài)搜索半徑的果蠅優(yōu)化算法

高雷阜 趙世杰*徒 君 于冬梅

(遼寧工程技術大學優(yōu)化與決策研究所 遼寧 阜新 123000)

針對傳統(tǒng)果蠅優(yōu)化算法FOA(Fruit Fly Optimization Algorithm)固定搜索半徑導致后期局部尋優(yōu)性能弱、收斂緩慢的問題，提出一種動態(tài)搜索半徑的果蠅優(yōu)化算法DSR-FOA(Fruit Fly Optimization Algorithm With Dynamic Search Radius)。該算法前期以較大搜索半徑保證全局尋優(yōu)性能，而后期搜索半徑隨迭代次數(shù)動態(tài)遞減以保證局部尋優(yōu)性能，有效地實現(xiàn)算法全局與局部尋優(yōu)性能的均衡。其次，針對傳統(tǒng)果蠅優(yōu)化算法不適于優(yōu)化變量的區(qū)間設定問題，通過初始搜索半徑設定和平移變換等技術提出一種有效的區(qū)間限定方法。數(shù)值實驗結果表明：改進算法具有較好的尋優(yōu)精度和預測標準差等指標，驗證了算法的有效性和可行性。

果蠅優(yōu)化算法 搜索半徑 平移變換 基準測試函數(shù)

0 引 言

果蠅優(yōu)化算法[1，2]FOA是學者潘文超受果蠅覓食行為啟發(fā)，于 2011 年提出的一種新的仿生智能優(yōu)化算法。其模仿果蠅通過優(yōu)越的嗅覺和視覺來找尋、發(fā)現(xiàn)食物，主要利用嗅覺搜索實現(xiàn)果蠅個體多樣性的提高和較大的搜索范圍，利用視覺搜索實現(xiàn)果蠅個體的快速收斂。該算法具有調節(jié)參數(shù)少、尋優(yōu)速度快和易于實現(xiàn)等優(yōu)點而在一些科學和工程領域[3-5]得到有效應用。目前FOA算法的研究方向主要有搜索半徑的改進[6，7]、味道判定函數(shù)的改進[8，9]和種群多樣性的設置[10，11]等方面。

傳統(tǒng)FOA算法中搜索半徑是保持固定不變的，雖能保證算法前期較大的搜索空間以實現(xiàn)較好的全局搜索性能，但卻嚴重影響了算法后期的局部搜索性能，而造成后期尋優(yōu)性能弱、收斂緩慢的不足。對此本文改進了傳統(tǒng)FOA算法的迭代搜索半徑，提出了一種動態(tài)搜索半徑的果蠅優(yōu)化算法，以實現(xiàn)果蠅群體在全局與局部均能保持較好的搜索性能。同時由于果蠅代表的解只能為正值與優(yōu)化問題可能存在負值區(qū)間的矛盾性，基于初始搜索半徑的設定和平移變換等技術提出了一種區(qū)間限定方法，最后，將改進算法用于基準測試函數(shù)的優(yōu)化求解。

1 果蠅優(yōu)化算法

果蠅優(yōu)化算法是受果蠅覓食行為啟發(fā)而提出的一種仿生智能優(yōu)化算法，是一種全局優(yōu)化方法。果蠅是飛行昆蟲，通過自身嗅覺和視覺對外部環(huán)境極為敏感的特性，先利用嗅覺器官很好地獲取漂浮在空氣中的各種氣味，確定出食物源的大體位置；在飛近食物后再利用視覺發(fā)現(xiàn)食物與同伴聚集的位置，同時往該方向飛去。在嗅覺記憶與視覺記憶的協(xié)同作用下，模擬果蠅群體搜尋食物的過程。FOA算法迭代尋優(yōu)過程可歸納為以下幾步：

Step1 果蠅種群規(guī)模Sizepop和最大迭代次數(shù)Genmax的設置；果蠅群體位置的隨機初始化axisX和axisY：

(1)

其中，x0和y0為常數(shù)。

Step2 賦予果蠅飛行的搜索半徑R與隨機方向D，確定出第k代果蠅群體第i個個體利用嗅覺搜尋食物所得的新位置坐標：

(2)

其中，R(·)為果蠅個體利用嗅覺覓食的固定搜索半徑；D(·)=2rand()-1為[-1,1]間的一個隨機數(shù)，表示果蠅個體的隨機覓食方向(正值表示正方向；負值表示負方向)。

(3)

(4)

(5)

Step6 果蠅群體通過視覺飛到式(5)所保存的位置，生成新的果蠅群聚位置：

(6)

Step7 判斷是否滿足終止條件，即判斷迭代次數(shù)k是否達到最大迭代次數(shù)Genmax。若是則輸出最優(yōu)味道濃度和判定值，反之k加1，并跳轉執(zhí)行Step2。

2 動態(tài)搜索半徑的果蠅優(yōu)化算法

2.1 改進思想

傳統(tǒng)FOA算法在Step2中，搜索半徑R是保持固定不變的，即每代果蠅群體的果蠅個體在利用嗅覺覓尋食物時都是以固定半徑R向周圍隨機搜索的。為保證FOA算法具有較好的全局尋優(yōu)性能，同時避免陷入局部極值等問題，一般搜索半徑R設置為一個相對較大的值。這樣做，雖然保證了FOA算法前期的較好全局尋優(yōu)性能，但同時導致了另外一個問題：在算法迭代尋優(yōu)后期，由于果蠅群體仍在較大的搜索空間中繼續(xù)尋優(yōu)，從而導致局部尋優(yōu)性能較弱、尋優(yōu)效率相對較低和收斂緩慢等問題。

由傳統(tǒng)FOA中搜索半徑R存在的問題分析可以發(fā)現(xiàn)：搜索半徑R的設置直接影響著FOA算法的優(yōu)化性能。為保證算法既具有較好的全局尋優(yōu)性能，又具有較強的局部尋優(yōu)性能，搜索半徑R的設定應遵循如下原則：前期搜索半徑R為一個相對較大的值以保證全局尋優(yōu)性能，后期搜索半徑R則應為相對較小的值以保證局部搜索性能。

文獻[6]改進提出的DS-FOA算法中，搜索半徑R滿足的函數(shù)關系式為：

(7)

其中，變量Iter為果蠅群體的當前迭代次數(shù)，常量Itermax為最大迭代次數(shù)，常量Rmax為搜索半徑的初始最大值。

文獻[7]改進提出的IFFO算法中搜索半徑R滿足的函數(shù)關系式為：

(8)

其中，常量Rmin為搜索半徑的最小值。

在DS-FOA算法和IFFO算法中，搜索半徑R前期下降較為迅速(如圖1所示)，并不能較好地保證算法的全局優(yōu)化性能，在一定程度上降低了FOA算法的全局優(yōu)化性能。綜合考慮傳統(tǒng)FOA算法、DS-FOA算法和IFFO算法中存在的問題，本文對果蠅群體搜索半徑R進行改進，提出了動態(tài)搜索半徑的果蠅優(yōu)化算法DSR-FOA。搜索半徑定義式為：

(9)

其中，跳轉因子μ和指數(shù)因子α均為(0,1)間的一個常量。

圖1 FOA算法的搜索半徑對比圖

2.2 DSR-FOA算法優(yōu)化連續(xù)函數(shù)

由圖1可知：DSR-FOA算法在迭代前期具有較大的搜索半徑，保證了較好的全局尋優(yōu)性能；后期搜索半徑相對減小有利于保證算法的局部尋優(yōu)性能，從而使算法實現(xiàn)全局與局部尋優(yōu)性能的較好均衡。

DSR-FOA算法可用于連續(xù)函數(shù)的優(yōu)化求解。設連續(xù)函數(shù)的定義式為：

(minf(x)

s.t. xi∈[m,n] i=1,2,…,N)

(10)

其中，N表示函數(shù)f(·)中的變量數(shù)目。

傳統(tǒng)FOA算法的味道濃度判定值(即問題的解)是通過搜索半徑R所定位置以距離的形式來表示的，且只能取正值，這與測試函數(shù)中變量取值區(qū)間可能存在負區(qū)間是相矛盾的。為解決這種矛盾，利用搜索半徑的初始設定和平移變換等技術提出了一種適應于FOA算法的變量區(qū)間設定方法。該方法首先對初始搜索半徑Rmax根據(jù)變量取值區(qū)間進行設定，再利用區(qū)間平移變換實現(xiàn)味道濃度判定值落入變量取值區(qū)間內。具體操作方法為：當優(yōu)化函數(shù)變量取值區(qū)間[m,n](默認測試函數(shù)中|m|和|n|均大于1)的界值m和n同號時，Rmax=1/max{|m|,|n|}，同時利用循環(huán)保證生成Sizepop個Si介于[m,n](m和n均正時)，則Si即表示函數(shù)變量(若m和n均負時，需保證(-Si)介于[m,n]，此時(-Si)表示函數(shù)變量)；當變量取值區(qū)間界值m和n異號時，Rmax=1/|n-m|，同時保證生成Sizepop個Si小于等于|n-m|，則(Si-|m|)表示函數(shù)變量。利用DSR-FOA算法對優(yōu)化函數(shù)的執(zhí)行偽碼(變量取值區(qū)間為[-m,m],m>1)為：

Algorithm:DSR-FOA AlgorithmParameters:Population size(sizepop),Maximum,iterations(Itermax),Search Radius(Rmax),Variable numbers(n),Constant μ and α

Output:Best Solution S*

Set sizepop,Itermax,Rmax,n,μ,α

While 1

∥根據(jù)式(1)和式(2)初始化種群位置(Xaxis,Yaxis)

∥計算S0并判定其中有效變量的數(shù)目

IF sum(S0<=2m)==n

break;

END

END

Iter=1

Repeat

∥根據(jù)式(9)更新搜索半徑RIter

∥嗅覺覓食階段

While 1

∥根據(jù)RIter利用式(2)更新種群位置(Xaxis,Yaxis)

∥計算SIter并判定其中有效變量的數(shù)目

IF sum(SIter<=2m)==n

break；

END

END

∥視覺覓食階段

END

Iter=Iter+1

Until Iter==Itermax

3 實驗仿真

3.1 實驗設計

為驗證DSR-FOA算法的優(yōu)越性，以FOA算法、DS-FOA算法和IFFO算法作為對比算法，通過6個基準測試函數(shù)的仿真實驗結果來說明DSR-FOA算法的有效性和可行性。6個基準測試函數(shù)的函數(shù)名稱、函數(shù)形式和變量區(qū)間等信息如表1所示(其中Schaffer函數(shù)為2維，其余為30維)。

表1 基準測試函數(shù)信息

3.2 實驗結果與分析

根據(jù)3.1節(jié)中6個測試函數(shù)的變量取值區(qū)間和參數(shù)設置情況，利用4種算法對6個測試函數(shù)進行數(shù)值實驗，各算法性能的評價指標選用最優(yōu)值(best)、最差值(worst)、平均值(mean)和標準差(std)共4個統(tǒng)計指標。各測試函數(shù)的30次實驗的統(tǒng)計平均結果如表2所示。

表2 四種算法對測試函數(shù)的結果

續(xù)表2

由表2可知：對6個基準測試函數(shù)的實驗結果中，DSR-FOA算法的4項評價指標均優(yōu)于FOA算法、IFFO算法和DS-FOA算法，具有較好的平均函數(shù)值和較小的測試標準差，說明了DSR-FOA算法具有較好的優(yōu)化精度和較強的魯棒性；并具有最優(yōu)的best指標(除F6)，表明改進算法保證了較好的最優(yōu)預測性能；同時有最小的worst指標(除F6)，說明改進算法即使在最壞極端情況下也能保持較好的預測性能，在實際應用中有利于降低未知情形下的可能損失和資源浪費，從而在一定程度上驗證了改進算法的較好優(yōu)越性能。

為更直觀形象地展示4種算法對各測試函數(shù)的迭代尋優(yōu)性能，繪制了算法的迭代尋優(yōu)對比曲線，如圖2-圖7所示。

圖2 測試函數(shù)Schaffer的對比曲線

圖3 測試函數(shù)Griewank的對比曲線

圖4 測試函數(shù)Rosenbrock的對比曲線

圖5 測試函數(shù)Rastrigin的對比曲線

圖6 測試函數(shù)Quadric的對比曲線

圖7 測試函數(shù)Ackley的對比曲線

由圖2-圖7可以看出：在對各測試函數(shù)的迭代尋優(yōu)過程中，DSR-FOA算法與其他算法相比不僅保證了算法前期較好的全局尋優(yōu)性能，即使在初始解離最優(yōu)解相對較遠的情形下也能迅速地趨近于函數(shù)的近似最優(yōu)解(近優(yōu)解)；而且在算法后期有效地實現(xiàn)了對該近優(yōu)解的進一步局部搜索，以較好的局部尋優(yōu)性能來獲得一個更好的近優(yōu)解。因此，在一定程度上說明了改進算法有效地均衡全局尋優(yōu)性能和局部尋優(yōu)性能，具有較強的迭代尋優(yōu)性能。同時，改進算法不僅對單峰測試函數(shù)具有較好的尋優(yōu)性能，而且對Schaffer和Ackley等多峰函數(shù)也表現(xiàn)出較好的尋優(yōu)性能和收斂精度，進一步驗證了DSR-FOA算法的優(yōu)良尋優(yōu)性能。

3.3 2個因子對DSR-FOA算法的性能影響

DSR-FOA算法的優(yōu)化性能受跳轉因子μ和指數(shù)因子α的共同影響，因此需要研究2個因子對算法的性能影響。

本節(jié)以Quadric函數(shù)為測試函數(shù)，參數(shù)設置情況同3.2節(jié)，跳轉因子μ和指數(shù)因子α分別屬于[0，1]和(0，1]，且自增步長為0.02，共得到51×50組(μ,α)的參數(shù)組合。對各參數(shù)組合(μ,α)均進行30次實驗，以30次實驗平均值為最終實驗結果，并繪制2個因子對DSR-FOA算法性能影響，如圖8所示。

圖8 2個因子對DSR-FOA算法性能的影響

由圖8可知，不同因子組合(μ,α)對DSR-FOA算法性能的影響是不同的：越趨近于(1,1)組合，改進算法的預測精度越弱，原因是改進算法越趨退化為傳統(tǒng)FOA算法而導致后期局部尋優(yōu)性能減弱；指數(shù)因子α越趨近于0，改進算法的預測精度越高，表明算法后期對近優(yōu)解的局部尋優(yōu)性能越強；跳轉因子μ在一定區(qū)間內對改進算法性能的影響差異是不明顯的，即表明跳轉因子μ在一定區(qū)間內對改進算法而言均具有較好的全局尋優(yōu)性能，在算法前期都可迅速獲得所研究問題的一個近優(yōu)解。因此，在實際應用中可通過跳轉因子μ和指數(shù)因子α的合理設置有效地實現(xiàn)算法全局尋優(yōu)性能和局部尋優(yōu)性能的良好均衡，以提高算法的尋優(yōu)效率和優(yōu)化精度。圖8中星形表示最優(yōu)解，其坐標為(0.12,0.02)。

為更直觀地分析因子μ和α對改進算法性能的影響，繪制圖9以研究在固定某一因子條件下分析另一個因子對改進算法的獨立影響。其中(a)是固定指數(shù)因子α，研究跳轉因子μ對DSR-FOA算法性能的影響；(b)是固定跳轉因子μ，研究指數(shù)因子α對DSR-FOA算法性能的影響。

圖9 不同影響因子值對DSR-FOA算法的性能影響分析圖

在固定指數(shù)因子α的前提下，由圖9(a)的分析可知：在固定α值較小時，跳轉因子μ遞增變化的前半段對改進算法預測性能的影響是不明顯的，但在后半段(即μ→1時)，算法的預測性能越趨減弱(即min問題的預測值越趨增大)。在固定α值超過一定范圍越趨近于1時，跳轉因子μ的遞增變化對改進算法預測性能的影響差異是越趨不顯著的，原因正是由于改進算法越趨退化為傳統(tǒng)FOA算法。在固定跳轉因子μ的前提下，由圖9(b)的分析可知：針對不同跳轉因子μ的固定值，DSR-FOA算法的預測性能均隨著指數(shù)因子α的增大而越趨減弱，甚至在預測曲線后半段出現(xiàn)預測性能“差異性不顯著”的現(xiàn)象。鑒于上述分析，在實際應用中一般建議DSR-FOA算法中因子的設置情況為：跳轉因子μ∈[0.1,0.35]、指數(shù)因子α∈(0,0.15]。

4 結 語

鑒于傳統(tǒng)果蠅優(yōu)化算法中搜索半徑固定不變而導致后期局部搜索性能較弱和收斂緩慢的問題，本文提出了一種動態(tài)搜索半徑的果蠅優(yōu)化算法——DSR-FOA算法。該算法前期具有較大的搜索半徑，保證了較好的全局搜索性能；同時后期搜索半徑隨迭代次數(shù)動態(tài)減小，有利于強化算法的局部搜索性能。該算法有效地實現(xiàn)了全局搜索性能和局部搜索性能的均衡，有利于迅速有效地獲得較為優(yōu)異的問題解。

由于果蠅優(yōu)化算法所代表的解(濃度判定值)只能取正值，與所研究問題的解可能存在負取值區(qū)間是相矛盾的。因此，本文通過搜索半徑的初始設定和平移變換等技術提出了一種有效的優(yōu)化變量取值區(qū)間的限定方法，以實現(xiàn)果蠅優(yōu)化算法對變量取值區(qū)間的較好適用性。同時將DSR-FOA算法用于基準測試函數(shù)的尋優(yōu)中，數(shù)值實驗結果驗證了改進算法的有效性和可行性。

本文所提出的動態(tài)搜索半徑果蠅優(yōu)化算法是以搜索半徑分段變化的方式來實現(xiàn)算法全局尋優(yōu)性能和局部尋優(yōu)性能的均衡。如何尋求一種符合“起始變化率較小而后期變化率較大”的特性函數(shù)，有效地實現(xiàn)全局與局部尋優(yōu)的均衡，這也將是下一步研究的一個重點；同時將DSR-FOA算法與其他方法結合(如SVM等)用于解決某些科學工程問題也是一個較好的研究方向。

[1] WenTsao Pan.A new Fruit Fly Optimization Algorithm:Taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26:69-74.

[2] 潘文超.果蠅最佳化演算法-最新演化式計算技術[M].臺灣:滄海書局,2011.

[3] Lin Wang,Yuanlong Shi,Shan Liu.An improved fruit fly optimization algorithm and its application to joint replenishment problems[J].Expert Systems with Applications,2015,42 (9):4310-4323.

[4] Junqing Li,Quanke Pan,Kun Mao,et al.Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm[J].Knowledge-Based Systems,2014,72:28-36.

[5] Mousavi S M,Alikar N,Niaki S T A.An improved fruit fly optimization algorithm to solve the homogeneous fuzzy series-parallel redundancy allocation problem under discount strategies[J].Soft Computing,2016,20(6):2281-2307.

[6] 寧劍平,王冰,李洪儒,等.遞減步長果蠅優(yōu)化算法及應用[J].深圳大學學報:理工版,2014,31(4):367-373.

[7] QuanKe Pan,HongYan Sang,JunHua Duan,et al.An improved fruit fly optimization algorithm for continuous function optimization problems[J].Knowledge-Based Systems,2014,62:69-83.

[8] 張勇,夏樹發(fā),唐冬生.果蠅優(yōu)化算法對多峰函數(shù)求解性能的仿真研究[J].暨南大學學報：自然科學與醫(yī)學版,2014,35(1):82-87.

[9] WenTsao Pan.Using modified fruit fly optimisation algorithm to perform the function test and case studies[J].Connection Science,2013,25(2-3):151-160.

[10] 賀智明,宋建國,梅宏標.結合元胞自動機的果蠅優(yōu)化算法[J].計算機應用,2014,34(8):2295-2298,2321.

[11] Ling Wang,Xiaolong Zheng,Shengyao Wang.A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Knowledge-Based Systems,2013,48:17-23.

FRUIT FLY OPTIMIZATION ALGORITHM WITH DYNAMIC SEARCH RADIUS

Gao Leifu Zhao Shijie*Tu Jun Yu Dongmei

(Institute of Optimization and Decision,Liaoning Technical University,Fuxin 123000,Liaoning,China)

Considering the problems that the fixed-scale search radius in conventional fruit fly optimisation algorithm (FOA) causes weak local optimisation performance in algorithm’s later-stage and slow convergence,we propose a fruit fly optimisation algorithm with dynamic search radius (DSR-FOA).In its early-stage the algorithm ensures global optimisation performance by a greater search radius,while in later-stage its radius declines dynamically along with the iterations increasing for having better local optimisation performance.This improvement achieves the equilibrium between global and local optimisations effectively.Moreover,in light of the problem of conventional FOA that it is unsuitable for the interval setting of optimised variables,we present an effectual interval-set method which is based on the techniques including setting initial search radius and translation transformation.Numerical experimental results show that the DSR-FOA algorithm has better optimisation precision and smaller prediction standard deviation,which verifies the effectiveness and feasibility of the improved algorithm.

Fruit fly optimisation algorithm Search radius Translation transformation Benchmark testing function

2015-08-10。教育部高等學校博士學科點專項科研基金聯(lián)合項目(20132121110009);遼寧省教育廳基金項目(L2015208)。高雷阜，教授，主研領域：最優(yōu)化理論與應用。趙世杰，博士生。徒君，講師。于冬梅，博士生。

TP18

A

10.3969/j.issn.1000-386x.2016.11.052