1、收稿日期: xxxx-xx-xx。教育部高等學校博士學科點專項科研基金聯合資助項目(20132121110009)；遼寧省教育廳基金項目(l2015208)。高雷阜，教授，博士生導師，主研領域：最優化理論與應用。趙世杰，博士研究生。徒君，講師，博士。于冬梅，博士研究生。動態搜索半徑的果蠅優化算法高雷阜 趙世杰* 徒君 于冬梅(遼寧工程技術大學優化與決策研究所，阜新123000)摘要 針對傳統果蠅優化算法固定搜索半徑導致后期局部尋優性能弱、收斂緩慢的問題，提出了一種動態搜索半徑的果蠅優化算法，該算法前期以較大搜索半徑保證全局尋優性能，而后期搜索半徑隨迭代次數動態遞減以保證局部尋優性能，有效地實現

2、算法全局與和局部尋優性能的均衡；其次，針對傳統果蠅優化算法不適于優化變量的區間設定問題，通過初始搜索半徑設定和平移變換等技術提出了一種有效的區間限定方法。數值實驗結果表明：改進算法具有較好的尋優精度和預測標準差等指標，驗證了算法的有效性和可行性。關鍵詞 果蠅優化算法 搜索半徑 平移變換 基準測試函數中圖分類號 tp18文獻標識碼 a doi: 10.3969/j.issn.1000-386x.2013.01.001fruit fly optimization algorithm with dynamic search radiusgao leifu zhao shijie tu jun yu

3、dongmei(institute of optimization and decision, liaoning technical university, fuxin 123000, liaoning, china)abstract considering the fixed-scale search radius of the classical fruit fly optimization algorithm (foa) results in several problems in algorithms later-stage, i.e. the weak local optimizat

4、ion performance and the slowing constringency, the fruit fly optimization algorithm with dynamic search radius (dsr-foa) is proposed. the search radius of dsr-foa algorithm is larger to ensure the global optimization performance in the early-stage, while its radius declines dynamically with the iter

5、ations increasing for having better local optimization performance in the later-stage. this improvement achieves the equilibrium between the global and local optimization. secondly, facing that foa algorithm is unfit for the interval setting of the optimized variables, an effectual interval-set meth

6、od is present which based on techniques including the setting of the initial search radius and the translation transformation. the experimental results show that dsr-foa algorithm has better precision and smaller standard deviation, which validates the effectiveness and feasibility of improved algor

7、ithm.keywords fruit fly optimization algorithm search radius translation transformation benchmark testing function0 引言果蠅優化算法1-2(fruit fly optimization algorithm, foa)是學者潘文超受果蠅覓食行為啟發于 2011 年提出的一種新的仿生智能優化算法，其模仿果蠅通過優越的嗅覺和視覺來找尋發現食物，主要利用嗅覺搜索實現果蠅個體多樣性的提高和較大的搜索范圍，利用視覺搜索實現果蠅個體的快速收斂；該算法具有調節參數少、尋優速度快和易于實現等優點而

8、在一些科學和工程領域3-5得到有效應用。目前foa算法的研究方向主要有搜索半徑的改進6-7、味道判定函數的改進8-9和種群多樣性的設置10等方面11。傳統foa算法中搜索半徑是保持固定不變的，雖能保證算法前期較大的搜索空間以實現較好的全局搜索性能，但卻嚴重影響了算法后期的局部搜索性能，而造成后期尋優性能弱、收斂緩慢的不足，對此本文改進了傳統foa算法的迭代搜索半徑，提出了一種動態搜索半徑的果蠅優化算法，以實現果蠅群體在全局與局部均能保持較好的搜索性能；同時由于果蠅代表的解只能為正值與優化問題可能存在負值區間的矛盾性，基于初始搜索半徑的設定和平移變換等技術提出了一種區間限定方法，最后，將改進算法

9、用于基準測試函數的優化求解。1 果蠅優化算法果蠅優化算法1-2是受果蠅覓食行為啟發而提出的一種仿生智能優化算法，是一種全局優化方法。果蠅是飛行昆蟲，通過自身嗅覺和視覺對外部環境極為敏感的特性，先利用嗅覺器官很好地獲取漂浮在空氣中的各種氣味，確定出食物源的大體位置；在飛近食物后再利用視覺發現食物與同伴聚集的位置，同時往該方向飛去。在嗅覺記憶與視覺記憶的協同作用下，模擬果蠅群體搜尋食物的過程，foa算法迭代尋優過程可歸納為以下幾步：step1:果蠅種群規模和最大迭代次數的設置；果蠅群體位置的隨機初始化和： (1)其中，和為常數。step2:賦予果蠅飛行的搜索半徑與隨機方向，確定出第代果蠅群體第個個

10、體利用嗅覺搜尋食物所得的新位置坐標： (2)其中，為果蠅個體利用嗅覺覓食的固定搜索半徑；為間的一個隨機數表示果蠅個體的隨機覓食方向(正值表示正方向；負值表示負方向)；step3:由于無法事先得知食物的位置所在，不失一般性，以原點坐標為食物的默認位置，計算第代果蠅群體中第個個體的位置與原點的距離，并以其倒數作為味道濃度判定值： (3)step4:將味道濃度判定值代入到味道濃度判定函數中，確定出該果蠅個體的味道濃度： (4)step5:第代果蠅群體最優味道濃度的確定和對應味道濃度判定值的保存： (5)step6:果蠅群體通過視覺飛到(5)所保存的位置，生成新的果蠅群聚位置： (6)step7:判斷

11、是否滿足終止條件，即判斷迭代次數是否達到最大迭代次數，若是則輸出最優味道濃度和判定值，反之加1，并跳轉執行step2。果蠅群體中每個個體的味道濃度判定值代表所研究問題的可行解，對應味道濃度值代表目標值，并以群體中味道濃度的大小來衡量果蠅個體的優劣。2 動態搜索半徑的果蠅優化算法2.1 改進思想傳統foa算法在step2中，搜索半徑是保持固定不變的，即每代果蠅群體的果蠅個體在利用嗅覺覓尋食物時都是以固定半徑向周圍隨機搜索的。為保證foa算法具有較好的全局尋優性能，同時避免陷入局部極值等問題，一般搜索半徑設置為一個相對較大的值。這樣做，雖然保證了foa算法前期的較好全局尋優性能，但同時導致了另外一

12、個問題：在算法迭代尋優后期，由于果蠅群體仍在較大的搜索空間中繼續尋優，從而導致局部尋優性能較弱、尋優效率相對較低和收斂緩慢等問題。由傳統foa中搜索半徑存在的問題分析可以發現：搜索半徑的設置直接影響著foa算法的優化性能。為保證算法既具有較好的全局尋優性能，又具有較強的局部尋優性能。因此，搜索半徑的設定應遵循如下原則：前期搜索半徑為一個相對較大的值以保證全局尋優性能，后期搜索半徑則應為相對較小的值以保證局部搜索性能。文獻6改進提出的ds-foa算法中搜索半徑滿足的函數關系式為： (7)其中，變量為果蠅群體的當前迭代次數，常量為最大迭代次數，常量為搜索半徑的初始最大值。文獻7改進提出的iffo算

13、法中搜索半徑滿足的函數關系式為： (8)其中，常量為搜索半徑的最小值。圖1 foa算法的搜索半徑對比圖在ds-foa算法和iffo算法中搜索半徑前期下降較為迅速(見圖1)，并不能較好地保證算法的全局優化性能，在一定程度上降低了foa算法的全局優化性能，綜合考慮傳統foa算法、ds-foa算法和iffo算法中存在的問題，本文對果蠅群體搜索半徑進行改進提出了動態搜索半徑的果蠅優化算法(fruit fly optimization algorithm with dynamic search radius，dsr-foa)，搜索半徑定義式為： (9)其中，跳轉因子和指數因子均為間的一個常量。跳轉因子控

14、制dsr-foa算法的全局優化與局部優化的進程跳轉，通過適當設置以實現全局與局部優化性能的均衡；指數因子控制搜索半徑的遞減速率，實現算法后期較好的局部搜索性能。由算法定義式的分析可知：當，且時，dsr-foa算法便退化為傳統foa算法，都是以搜索半徑進行次搜索；當，且時，式(8)和式(9)是相一致的，表明式(8)可看作是式(9)的一個特例，但文獻7每次只修正一個變量，從而影響了種群的進化進程。由于前幾代果蠅群體(即小于)離食物源相對較遠，故設定果蠅優化算法具有較大的搜索半徑，以保證算法的全局尋優性能；隨著果蠅群體越趨近于食物源，較大搜索半徑不利于算法的局部優化性能，故定義搜索半徑隨迭代次數而逐

15、漸減小，直到最大迭代次數時減為。dsr-foa算法與foa算法、ds-foa算法和iffo算法的搜索半徑對比圖見圖1。2.2 dsr-foa算法優化連續函數由圖1可知：dsr-foa算法在迭代前期具有較大的搜索半徑，保證了較好的全局尋優性能；后期搜索半徑相對減小有利于保證算法的局部尋優性能，從而使算法實現全局與局部尋優性能的較好均衡。dsr-foa算法可用于連續函數的優化求解，設連續函數的定義式為： (10)其中，表示函數中的變量數目。由于傳統foa算法的味道濃度判定值(即問題的解)是通過搜索半徑所定位置以距離的形式來表示的，且只能取正值，這與測試函數中變量取值區間可能存在負區間是相矛盾的。為

16、解決這種矛盾，利用搜索半徑的初始設定和平移變換等技術提出了一種適應于foa算法的變量區間設定方法。該方法首先對初始搜索半徑根據變量取值區間進行設定，再利用區間平移變換實現味道濃度判定值落入變量取值區間內，具體操作方法為：當優化函數變量取值區間(默認測試函數中和均大于1)的界值和同號時，同時利用循環保證生成個介于(和均正時)，則即表示函數變量(若和均負時，需保證介于，此時表示函數變量)；當變量取值區間界值和異號時，同時保證生成個小于等于，則表示函數變量。利用dsr-foa算法對優化函數的執行偽碼(以變量取值區間為為例)為：表1 基準測試函數信息函數名稱函數形式變量區間schaffergriewa

17、nkrosenbrockrastriginquadricackley3 實驗仿真3.1 實驗設計為驗證dsr-foa算法的優越性，以foa算法、ds-foa算法和iffo算法作為對比算法，通過6個基準測試函數的仿真實驗結果來說明dsr-foa算法的有效性和可行性。6個基準測試函數的函數名稱、函數形式和變量區間等信息見表1(其中schaffer函數為2維，其余為30維)。果蠅的搜索半徑按2.2中的方法進行設置，最大迭代次數，種群規模，跳轉因子和指數因子。最大搜索半徑，為保證與iffo算法的對比性能，根據二者間的關系式，設置iffo的最小搜索半徑為。各實驗均獨立進行30次實驗，并以30次實驗的平均

18、值作為最終結果。3.2 實驗結果與分析根據3.1中6個測試函數的變量取值區間和參數設置情況，利用4種算法對6個測試函數進行數值實驗，各算法性能的評價指標選用最優值(best)、最差值(worst)、平均值(mean)和標準差(std)共4個統計指標，各測試函數的30次實驗的統計平均結果見表2。表2 四種算法對測試函數的結果alg.bestworstmeanstd.f1foa-1-0.9997-0.999965.91e-5iffo-1-0.9218-0.98471.65e-2dsfoa-1-0.99999-12.58e-6dsrfoa-1-10f2foa1.51e-46.51e-31.41e-3

19、1.75e-3iffo1.20e-48.25e-32.78e-32.02e-3dsfoa1.14e-48.32e-42.59e-41.56e-4dsrfoa1.06e-43.71e-42.20e-46.86e-5f3foa1.03e-51.65e-22.69e-33.84e-3iffo2.3e-11.15e+21.27e+05.03e+1dsfoa9.44e-61.11e-31.88e-42.74e-4dsrfoa8.27e-61.59e-44.33e-54.28e-5f4foa3.80e-91.29e-31.85e-42.91e-4iffo1.03e-72.99e-39.98e-45.43e

20、-4dsfoa1.73e-89.75e-58.30e-61.91e-5dsrfoa3.78e-91.10e-51.88e-62.87e-6f5foa6.07e-53.71 e-25.85e-38.35e-3iffo1.06e-48.73e-28.82e-39.89e-3dsfoa2.77e-51.41e-32.99e-43.53e-4dsrfoa2.63e-53.04e-47.12e-55.65e-5f6foa8.97e-45.07 e-21.09e-21.29e-2iffo4.14e-37.37e-25.32e-28.80e-3dsfoa1.07e-34.17e-31.90e-37.79e-

21、4dsrfoa1.04e-34.85e-31.45e-36.84e-4由表2可知：對6個基準測試函數的實驗結果中，dsr-foa算法的4項評價指標均優于foa算法、iffo算法和ds-foa算法的，具有較好的平均函數值和較小的測試標準差，說明了dsr-foa算法具有較好的優化精度和較強的魯棒性；并具有最優的best指標(除f6)，表明改進算法保證了較好的最優預測性能；同時有最小的worst指標(除f6)，說明改進算法即使在最壞極端情況下也能保持較好的預測性能，在實際應用中有利于降低未知情形下的可能損失和資源浪費，從而在一定程度上驗證了改進算法的較好優越性能。為更直觀形象地展示4種算法對各測試函

22、數的迭代尋優性能，繪制了算法的迭代尋優對比曲線見圖2-圖7。圖2 測試函數schaffer的對比曲線圖3 測試函數griewank的對比曲線圖4 測試函數rosenbrock的對比曲線圖5 測試函數rastrigin的對比曲線圖6 測試函數quadric的對比曲線由圖2-圖7可以看出：在對各測試函數的迭代尋優過程中，dsr-foa算法與其他算法相比不僅保證了算法前期較好的全局尋優性能，即使在初始解離最優解相對較遠的情形下也能迅速地趨近于函數的近似最優解(近優解)，而且在算法后期有效地實現了對該近優解的進一步局部搜索，以較好的局部尋優性能來獲得一個更好的近優解；因此，在一定程度上說明了改進算法有

23、效地均衡全局尋優性能和局部尋優性能，具有較強的迭代尋優性能。同時改進算法不僅對單峰測試函數具有較好的尋優性能，而且對schaffer和ackley等多峰函數也表現出較好的尋優性能和收斂精度，進一步驗證了dsr-foa算法的優良尋優性能。圖7 測試函數ackley的對比曲線3.3 2個因子對dsr-foa算法的性能影響dsr-foa算法的優化性能是受跳轉因子和指數因子的共同影響，因此需要研究2個因子對算法的影響性能。本節以quadric函數為測試函數，參數設置情況同3.2，跳轉因子和指數因子分別屬于和，且自增步長為0.02共得到組的參數組合，對各參數組合均進行30次實驗，以30次實驗平均值為最終

24、實驗結果，并繪制2個因子對dsp-foa算法性能影響圖見圖8。圖8 2個因子對drpfoa算法性能的影響由圖8可知，不同因子組合對dsr-foa算法性能的影響是不同的：越趨近于組合，改進算法的預測精度越弱，原因是改進算法越趨退化為傳統foa算法而導致后期局部尋優性能減弱；指數因子越趨近于0，改進算法的預測精度越高，表明算法后期對近優解的局部尋優性能越強；跳轉因子在一定區間內對改進算法性能的影響差異是不明顯的，即表明跳轉因子在一定區間內對改進算法而言均具有較好的全局尋優性能，在算法前期都可迅速獲得所研究問題的一個近優解，因此，在實際應用中可通過跳轉因子和指數因子的合理設置有效地實現算法全局尋優性

25、能和局部尋優性能的良好均衡，以提高算法的尋優效率和優化精度。圖8中星形表示最優解，其坐標為。為更直觀地分析究因子和對改進算法性能的影響，繪制圖9以研究在固定某一因子條件下分析另一個因子對改進算法的獨立影響，其中圖9(a)是固定指數因子研究跳轉因子對dsrfoa算法性能的影響；圖9(b)是固定跳轉因子研究指數因子對dsrfoa算法性能的影響。在固定指數因子的前提下，由圖9(a)的分析可知：在固定值較小時，跳轉因子遞增變化的前半段對改進算法預測性能的影響是不明顯的，但在后半段(即時)，算法的預測性能越趨減弱(即min問題的預測值越趨增大)；在固定值超過一定范圍越趨近于1時，隨跳轉因子的遞增變化對改

26、進算法預測性能的影響差異是越趨不顯著的，原因正是由于改進算法越趨退化為傳統foa算法。在固定跳轉因子的前提下，由圖9(b)的分析可知：針對不同跳轉因子的固定值，dsr-foa算法的預測性能均隨著指數因子的增大越趨減弱，甚至在預測曲線后半段出現預測性能“差異性不顯著”的現象。鑒于上述分析：在實際應用中一般建議dsr-foa算法中因子的設置情況為：跳轉因子、指數因子。4 結 論(1) 鑒于傳統果蠅優化算法中搜索半徑固定不變而導致后期局部搜索性能較弱和收斂緩慢的問題，本文提出了一種動態搜索半徑的果蠅優化算法dsr-foa算法，該算法前期具有較大的搜索半徑保證了較好的全局搜索性能，同時后期搜索半徑隨迭

27、代次數動態較小有利于強化算法的局部搜索性能，該算法有效地實現了全局搜索性能和局部搜索性能的均衡，有利于迅速有效地獲得較為優異的問題解。(2) 由于果蠅優化算法所代表的解(濃度判定值)只能取正值，與所研究問題的解可能存在負取值區間是相矛盾的，因此，本文通過搜索半徑的初始設定和平移變換等技術提出了一種有效的優化變量取值區間的限定方法，以實現果蠅優化算法對變量取值區間的較好適用性；同時將dsr-foa算法用于基準測試函數的尋優中，數值實驗結果驗證了改進算法的有效性和可行性。(3) 本文所提出的動態搜索半徑果蠅優化算法是以搜索半徑分段變化的方式來實現算法全局尋優性能和局部尋優性能的均衡。如何尋求一種符

28、合“起始變化率較小而后期變化率較大”的特性函數也可以有效地實現全局與局部尋優的均衡，這也將是下一步研究的一個重點；同時將dsr-foa算法與其他方法結合(如svm等)用于解決某些科學工程問題也是一個較好的研究方向。圖9 不同影響因子值對dsrfoa算法的性能影響分析圖參 考 文 獻1 wen-tsao pan.a new fruit fly optimization algorithm: taking the financial distress model as an examplej. knowledge-based systems,2012,26:69-74.2 潘文超.果蠅最佳化演算法

29、-最新演化式計算技術m.臺灣:滄海書局,2011.3 lin wang,yuanlong shi, shan liu. an improved fruit fly optimization algorithm and its application to joint replenishment problemsj. expert systems with applications, 2015,42 (9): 43104323. 4 jun-qing li,quan-ke pan,kun mao,p.n. suganthan. solving the steelmaking casting pr

30、oblem using an effective fruit fly optimisation algorithmj. 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 seriesparallel redundancy allocation problem under discount strategiesj. soft computing

31、, 2015: 1-27.6 寧劍平,王冰,李洪儒,許葆華.遞減步長果蠅優化算法及應用j.深圳大學學報理工版,2014,31(4):367-373.7 quan-ke pan,hong-yan sang,jun-hua duan,liang gao. an improved fruit fly optimization algorithm for continuous function optimization problemsj. knowledge-based systems,2014,62:69-83.8 張勇,夏樹發,唐冬生.果蠅優化算法對多峰函數求解性能的仿真研究j.暨南大學學報(自

32、然科學與醫學版),2014,35(1):82-87. 9 wen-tsao pan.using modified fruit fly optimisation algorithm to perform the function test and case studiesj. connection science, 2013,25(2-3):151-160.10 賀智明,宋建國,梅宏標. 結合元胞自動機的果蠅優化算法j.計算機應用,2014,34(8):2295-2298,2321.11 ling wang,xiao-long zheng,sheng-yao wang. a novel bina

33、ry fruit fly optimization algorithm for solving the multidimensional knapsack problemj. knowledge-based systems, 2013,48:17-23.提供聯系方式聯系人：趙世杰 電話郵箱：通信地址：遼寧省阜新市中華路47號遼寧工程技術大學328信箱（轉科技大廈806室），郵編：123000。作者簡介：高雷阜，教授，博士，博士生導師，主研領域：最優化理論與應用。趙世杰，博士研究生，主研領域：人工智能與數據挖掘，優化與管理決策。

34、徒君，講師，博士，主研領域：供應鏈管理，人工智能。于冬梅，博士研究生，主研領域：最優化理論與應用，應急管理。【預審意見】高雷阜您好！稿件a15080111：（1）圖中x,y坐標值或文字說明不清楚，請在顯示比例100%前提下放大原字體（若是彩圖請修改成黑白色）；其中：圖 2-8 請修改； 修改說明：對于圖中x和y坐標進行了重新說明，并適當放大了字體，望審閱。（2）請把基金名稱和編號、第一作者職稱、主研領域以及所有其他作者姓名和職稱放在首頁右下角。在論文最后必須附上所有作者簡介，內容為：姓名、職稱 / 學位、主研領域、身份證號、手機、單位、通信地址、郵編、e-mail； 修改說明：首頁右下角以放上

35、相應的信息，但框有些小，調整大小時會導致串位置，所以未敢對其修改。（3）本刊為雙欄格式排版，請將圖/表在保持清晰的前提下改成單欄大小（不要跨欄排版）； 修改說明：對于單欄排列的圖9，由于圖中線條較多，若再改為雙欄，將更不便于理解和展示。若必須要修改為單欄，將會在下一稿中予以修改。（4）圖或表插入論文相應位置； 修改說明：為便于論文板式，對論文中圖表的出現位置進行了適當的調整。（5）參考文獻（所列出參考文獻需在文中被引用）引用格式書寫有誤或不完整（若引用期刊需注明年、卷號、期、頁碼。如：2013，30（1）：1 - 5）或作者三人以下不能用等，其中參考文獻：1,4,5,7,11 請修改；。修改說

36、明： 1,4,7,11所引用文獻均是來自sci期刊” knowledge-based systems”中的論文，該期刊是只有卷號，沒有期號的；而sci期刊“soft computing”，卷號期號都沒有。 對于老師所提出的問題，已對其進行了適當的修改，期待專家的再次審閱。謝謝專家審稿意見（20150901）（1） 摘要不夠簡潔。 （2） 第1節中要說明果蠅個體代表問題的一個解是如何被表示和初始化的？ （3） 最大迭代次數是預先確定的嗎？如果是，針對具體問題是如何設定的？ （4） 為何改進算法中設置后期搜索半徑存在急劇變化？ （5） 實驗結果中，不要用局部對比曲線，不夠美觀。建議適當放大曲線比例

37、？ （6） 圖8中不易分辨兩個因子的影響和最優設置。 （7） 2.2節中算法敘述盡量使用中文。 其余詳見審改稿。2015-9-1審稿意見及逐條修改說明 （1） 摘要不夠簡潔。針對該問題，對摘要部分進行了重寫（包括英文摘要），并以“藍色”字體予以標注，望專家審閱。（2） 第1節中要說明果蠅個體代表問題的一個解是如何被表示和初始化的？ 針對該問題，首先對果蠅位置的隨機初始化以具體公式予以表示，見式（1）；其次，在第1節最后一段對foa算法中解的表示進行了進一步的解釋說明，也以“藍色”字體予以標注，望專家審閱。（3） 最大迭代次數是預先確定的嗎？如果是，針對具體問題是如何設定的？ 對于最大迭代次數的

38、設定問題，本文采用了仿生智能算法中國際上的一種設定方式，即種群30迭代500次，現舉幾篇sci論文以說明該設定方式： 1 mirjalili s, mirjalili s m, hatamlou a. multi-verse optimizer: a nature-inspired algorithm for global optimizationj. neural computing and applications, 2015: 1-19. 2 gonalves m s, lopez r h, miguel l f f. search group algorithm: a new metaheuristic method for the optimization of truss structuresj. computers & structures, 2015, 153: 165-184. 3 seyedali mirjalili, lewis a. adaptive gbest-guided gravitational search algorithmj.