動態搜索半徑的果蠅優化算法

高雷阜 趙世杰 徒 君 于冬梅

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

?

動態搜索半徑的果蠅優化算法

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

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

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

果蠅優化算法 搜索半徑 平移變換 基準測試函數

0 引 言

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

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

1 果蠅優化算法

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

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

(1)

其中，x0和y0為常數。

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

(2)

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

(3)

(4)

(5)

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

(6)

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

2 動態搜索半徑的果蠅優化算法

2.1 改進思想

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

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

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

(7)

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

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

(8)

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

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

(9)

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

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

2.2 DSR-FOA算法優化連續函數

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

DSR-FOA算法可用于連續函數的優化求解。設連續函數的定義式為：

(minf(x)

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

(10)

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

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

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

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

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

break;

END

END

Iter=1

Repeat

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

∥嗅覺覓食階段

While 1

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

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

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

break；

END

END

∥視覺覓食階段

END

Iter=Iter+1

Until Iter==Itermax

3 實驗仿真

3.1 實驗設計

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

表1 基準測試函數信息

3.2 實驗結果與分析

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

表2 四種算法對測試函數的結果

續表2

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

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

圖2 測試函數Schaffer的對比曲線

圖3 測試函數Griewank的對比曲線

圖4 測試函數Rosenbrock的對比曲線

圖5 測試函數Rastrigin的對比曲線

圖6 測試函數Quadric的對比曲線

圖7 測試函數Ackley的對比曲線

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

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

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

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

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

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

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

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

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

4 結 語

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

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

本文所提出的動態搜索半徑果蠅優化算法是以搜索半徑分段變化的方式來實現算法全局尋優性能和局部尋優性能的均衡。如何尋求一種符合“起始變化率較小而后期變化率較大”的特性函數，有效地實現全局與局部尋優的均衡，這也將是下一步研究的一個重點；同時將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] 寧劍平,王冰,李洪儒,等.遞減步長果蠅優化算法及應用[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] 張勇,夏樹發,唐冬生.果蠅優化算法對多峰函數求解性能的仿真研究[J].暨南大學學報：自然科學與醫學版,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] 賀智明,宋建國,梅宏標.結合元胞自動機的果蠅優化算法[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。教育部高等學校博士學科點專項科研基金聯合項目(20132121110009);遼寧省教育廳基金項目(L2015208)。高雷阜，教授，主研領域：最優化理論與應用。趙世杰，博士生。徒君，講師。于冬梅，博士生。

TP18

A

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