劉 樂

濟南大學 管理學院，濟南 250002

結合群體協(xié)同與和聲搜索策略的果蠅優(yōu)化算法*

劉 樂+

濟南大學 管理學院，濟南 250002

LIU Le.Fruit fly optimization algorithm by combining strategies of swarm collaboration and harmony search.Journal of Frontiers of Computer Science and Technology,2016,10(11):1587-1600.

為了改善標準果蠅優(yōu)化（fruit fly optimization，F(xiàn)FO）算法易陷入局部極優(yōu)，收斂精度不高的不足，提出了一種結合群體協(xié)同（swarm collaboration，SC）與和聲搜索（harmony search，HS）策略的新型果蠅優(yōu)化算法FFO-SC+HS。該算法基于隨機確定的單一維度和動態(tài)搜索半徑得到果蠅個體的食物源位置，并在種群中心位置的逐代更新環(huán)節(jié)新增了兩個可供選擇的備選位置。兩備選位置均出自按群體協(xié)同策略重構后的位置集合，其一為重構后位置向量集合中的最佳位置，另一則為借助和聲搜索策略得到的新位置向量。為驗證所設計算法的有效性，在10種測試函數(shù)上進行了大量的計算實驗與性能對比分析，結果表明FFO-SC+HS在求解質(zhì)量、收斂能力上優(yōu)于其他4種已報道的FFO算法，并發(fā)現(xiàn)3個主要參數(shù)的不同取值組合對其優(yōu)化性能具有顯著影響，所采取的SC與HS策略缺一不可。

果蠅優(yōu)化；群體協(xié)同；和聲搜索；函數(shù)優(yōu)化

1 引言

果蠅優(yōu)化（fruit fly optimization，F(xiàn)FO）算法由Pan于2011年最早提出[1]，是一種受果蠅覓食行為啟發(fā)的新型群體智能優(yōu)化技術。自然界中的果蠅通常具備出眾的嗅覺與視覺能力，能在所處群體中心位置的基礎上自如地確定下一步的覓食步長與方向，從而逐漸向遠處的食物源靠近。果蠅優(yōu)化算法源于對果蠅覓食習性的模仿；面向待優(yōu)化問題的解空間，它分嗅覺覓食（osphresis foraging）和視覺覓食（vision foraging）兩個階段進行迭代式隨機搜索，不考慮求解空間是否連續(xù)、可微，無需目標函數(shù)的梯度信息。自問世以來，果蠅優(yōu)化算法憑借流程簡單，易于實現(xiàn)，控制參數(shù)少（僅2個），易跟其他啟發(fā)式優(yōu)化技術相混合等優(yōu)勢，已在財務危機數(shù)據(jù)分析[2]、參數(shù)辨識[3-4]、電子節(jié)流閥控制[5]、年度電力負荷預測[6]、雙級供應鏈網(wǎng)絡優(yōu)化[7]、煉鋼重調(diào)度優(yōu)化[8]等領域得到成功應用，并為多維度背包[9]、置換流水線調(diào)度[10]、隨機資源約束項目調(diào)度[11]、多產(chǎn)品聯(lián)合補貨[12]等典型NP-Hard問題提供了新穎、高效的求解手段。

標準果蠅優(yōu)化算法在實際應用中具備不易跳出局部極優(yōu)，收斂精度不高等缺陷。為此，近年來相繼涌現(xiàn)出了若干成功的果蠅優(yōu)化改進算法。這些算法的改進思路大致分為3類：一是在嗅覺覓食階段改進果蠅個體獲得食物源位置的方式，并引入新的參數(shù)及其設置方式，例如基于新解線性生成機制的果蠅優(yōu)化算法（linear generation mechanism of candidate solution-based fruit fly optimization algorithm，LGMSFOA）[13]、基于“歷史認知”的果蠅優(yōu)化算法（FOA based on history cognition，F(xiàn)OABHC）[14]以及基于隨機確定的單維分量與動態(tài)搜索半徑的改進果蠅優(yōu)化算法（improved FFO，IFFO）[15]。二是在視覺覓食階段通過融合先進的啟發(fā)式優(yōu)化機理以求不斷改善果蠅種群的中心位置，例如基于細菌趨化的果蠅優(yōu)化算法（bacterial chemotaxis-based FOA，BCFOA）[16]、自適應混沌果蠅優(yōu)化算法（adaptive chaos FOA，ACFOA）[17]以及基于最優(yōu)最差個體協(xié)同學習的果蠅優(yōu)化算法（best-worst FOA，BWFOA）[18]等。三是在標準果蠅優(yōu)化算法框架基礎上融合多種群協(xié)同進化機制，提出了改進的果蠅優(yōu)化算法，包括動態(tài)雙子群協(xié)同進化果蠅優(yōu)化算法（dynamic double subgroups cooperative FOA，DDSCFOA）[19]和新型多種群果蠅優(yōu)化算法（multi-swarm FOA，MFOA）[3]。相比而言，運用第三類改進思路的果蠅優(yōu)化算法目前還較少；第一、二類改進思路吸引了更多人的研究興趣。最近，由Wang等人提出的改良型果蠅優(yōu)化算法（improved FOA，IFOA）[12]中，前兩類改進思路同時得以實施，并取得了令人滿意的改進效果。

為了進一步挖掘果蠅優(yōu)化算法的優(yōu)化潛力，本文設計了一種新的混合果蠅優(yōu)化算法，稱為“結合群體協(xié)同與和聲搜索策略的果蠅優(yōu)化算法”（FFO with swarm collaboration and harmony search strategies，F(xiàn)FO-SC+HS）。該算法在每次迭代過程中面向單維分量生成食物源位置，并通過融合群體協(xié)同機制（swarm collaboration，SC）以及和聲搜索（harmony search，HS）策略來改進果蠅種群中心位置的逐代更新方式。在現(xiàn)有的諸多改進果蠅優(yōu)化算法中，IFFO算法[15]、MFOA算法[3]和IFOA算法[12]無論在優(yōu)化機理上，還是在優(yōu)化性能上均較標準果蠅優(yōu)化算法有明顯改進。為此，本文以上述3種算法為主要比較對象，在選定的10種測試函數(shù)上進行一系列計算實驗。實驗結果顯示，F(xiàn)FO-SC+HS算法在函數(shù)優(yōu)化質(zhì)量、收斂能力上均具備相對優(yōu)越性。此外，還基于實驗設計方法分析了不同參數(shù)取值組合以及兩種融合策略對于所提出算法優(yōu)化性能的影響。

2 標準的果蠅優(yōu)化算法

果蠅優(yōu)化算法實質(zhì)上是一種模擬果蠅嗅覺覓食與視覺覓食行為的迭代式全局搜索方法。數(shù)學優(yōu)化問題的n維求解空間決定著果蠅種群的允許飛行空間；各果蠅個體在n維空間中的所處位置代表已搜索到的解向量。在每次迭代搜索過程中，都要先后經(jīng)歷“嗅覺覓食”與“視覺覓食”兩個階段。敏銳的嗅覺能力使每個果蠅都能從當前種群的中心聚集位置出發(fā)，借助一定的覓食步長接近食物源位置。果蠅個體的當前所處位置對應于由優(yōu)化目標函數(shù)所決定的味道濃度（smell concentration）?！耙曈X覓食”的過程即為從當前果蠅群體中確定味道濃度最佳的果蠅所處位置，如果該位置的味道濃度優(yōu)于當前群體中心位置，則其他果蠅個體憑借視覺追蹤能力向該位置聚集。

對于數(shù)學優(yōu)化問題的界定以及標準果蠅優(yōu)化算法對其求解的一般步驟可描述如下。

對于待最小化的數(shù)學優(yōu)化問題：其中，n為解空間的維數(shù)；X=(x1,x2,…,xn)為解向量；f(?)為待優(yōu)化的目標函數(shù)；LBi和UBi分別為決策變量xi取值范圍的下界與上界值(i∈{1,2,…,n})。

步驟1初始化控制參數(shù)和果蠅群體的中心位置。首先對種群規(guī)模Popsize和最大迭代次數(shù)Itermax進行初始化。然后，在待搜索的n維空間中按下式隨機生成初始的果蠅種群中心位置Δ=(δ1,δ2,…,δn)。

其中，函數(shù)rand(S)隨機返回集合S的任一元素。

步驟2各個果蠅從當前的種群中心位置Δ出發(fā)進行嗅覺覓食搜索，隨機得到Popsize個食物源位置。假設Pop={X(1),X(2),…,X(Popsize)}為所生成的食物源位置集合。第p個果蠅飛往的食物源位置；分量可由下式得出：

其中，Li=di+rand([-1,1]),i=1,2,…,n。

步驟3根據(jù)目標函數(shù)式 f(?)計算各個食物源位置X(p)的味道濃度(p=1,2,…,Popsize)，并展開視覺覓食搜索，即將最佳味道濃度所對應的食物源位置作為種群的新中心位置。具體地，首先從當前位置集合Pop中找出具備最小目標值的食物源位置Xbest，即；若 Xbest優(yōu)于當前種群的中心位置Δ，則Xbest為新的種群中心位置，即Δ←Xbest當且僅當 f(Xbest)

步驟4判斷迭代終止條件是否已滿足。如果迭代終止準則尚未滿足（如未達到最大迭代次數(shù)Itermax），則轉回步驟2；否則，輸出搜索到的最佳食物源位置X*及其味道濃度 f(X*)，結束。

3 新型的果蠅優(yōu)化改進算法

相互均衡的集約化（intensification）與分散化（diversification）搜索策略是成功開發(fā)出元啟發(fā)式算法的重要保證。集約化尋優(yōu)旨在迄今最佳解的鄰近區(qū)域?qū)嵤┚植克阉鳎欢ǔ潭壬蠒黾忧蟮酶媒獾母怕?；但過分追求集約化，易使算法陷入局部極優(yōu)，弱化全局優(yōu)化搜索的能力。分散化尋優(yōu)往往要借助當前種群信息或啟發(fā)式信息執(zhí)行覆蓋全局的隨機化搜索，這樣有助于算法擺脫局部極優(yōu)；但一味注重搜索的分散化，會徒勞地評價許多非最優(yōu)解，進而影響整體的優(yōu)化搜索效率。為此，成功的果蠅優(yōu)化改進算法應實現(xiàn)集約化與分散化搜索之間的有效協(xié)調(diào)，既要在嗅覺覓食階段強化集約化搜索的作用，又需在果蠅種群中心位置的更新環(huán)節(jié)實施專門的分散化尋優(yōu)機制。

3.1 基于單維分量生成食物源位置

為進一步增強解搜索的集約化程度，算法FFOSC+HS擬在嗅覺覓食階段采取文獻[15]中的相關做法，即基于隨機確定的單維分量和動態(tài)搜索半徑生成果蠅個體的食物源位置。其中，每個新生成的食物源位置跟當前種群的中心位置Δ相比，僅在唯一的分量值上有差別；至于哪一維分量，則由相應的果蠅個體在嗅覺覓食前隨機確定；該分量值上的變動幅度將受動態(tài)搜索半徑的影響。假設為第p個果蠅嗅覺覓食所得食物源位置X(p)的第i維分量(p= 1,2,…,Popsize,i=1,2,…,n)，則有：

其中，搜索半徑Ri的值適宜隨著迭代次數(shù)的增加而變小[3,15]。在此擬運用文獻[3]中對搜索半徑的設置方法，即在第iter次迭代中，Ri(iter)的計算公式為：

結合前期實驗結果發(fā)現(xiàn)，算法FFO-SC+HS中指數(shù)參數(shù)?的取值應大于5。

3.2 基于群體協(xié)同與和聲搜索的分散化尋優(yōu)

果蠅群體中心位置Δ的更新頻次是影響果蠅優(yōu)化算法求解精度與效率的關鍵因素。為了促進種群中心位置在逐次迭代中的頻繁更新，需要通過引入分散化尋優(yōu)機制來擴展種群中心位置的擇優(yōu)選取范圍。食物源位置集合的結構性變化會引起種群中心位置的不同。為此，在果蠅優(yōu)化算法的每次迭代中，可考慮對嗅覺覓食階段形成的位置集合Pop進行自適應重構。重構后的新位置集合既要發(fā)揮現(xiàn)有種群中心位置的引導作用，也要體現(xiàn)位置向量的多樣性。受文獻[12]中成功做法的啟發(fā)，算法FFO-SC+ HS中擬基于群體協(xié)同策略，對由若干食物源位置組成的集合執(zhí)行重構過程。

重構后的食物源位置集合負責產(chǎn)生若干新的候選中心位置。除了其中具有最小目標值的食物源位置外，還可面向重構后的位置集合，按特定的啟發(fā)式策略隨機生成候選的中心位置。每次迭代中候選的種群中心位置增多，有助于提高中心位置的更新頻次，但由于候選中心位置的產(chǎn)生與解質(zhì)量評價過程均會耗用一定的計算時間開銷，擴充的數(shù)目不宜過多，否則會影響算法的整體搜索效率。為了確保候選的中心位置少而精，面向重構后位置集合隨機生成的候選中心位置應在體現(xiàn)一定隨機性的基礎上，注重保留重構后位置集合中的歷史搜索信息。由此，對于所采取的啟發(fā)式候選中心位置生成策略，提出了面向群體，對歷史搜索信息記憶能力強，易實現(xiàn)，易跟其他元啟發(fā)式算法相混合的要求。事實上，和聲搜索算法就是一種具備上述特征的元啟發(fā)式優(yōu)化技術。該技術由Geem等人于2001年最早提出[20]，根源于現(xiàn)實中的樂隊即興創(chuàng)作過程。目前，它已在特征選擇、鋼架結構設計、儲能系統(tǒng)研發(fā)、單元式制造系統(tǒng)調(diào)度等領域得到廣泛應用[21-24]。由此，在算法FFO-SC+HS中擬基于重構后的位置集合，運用和聲搜索策略隨機生成一個候選中心位置，以助于提升種群中心位置的更新幅度與頻次。

需要指出的是，在算子Pop_SC_HS_X3中，果蠅種群規(guī)模Popsize的值即為參數(shù)HMS的取值；和聲記憶思考率HMCR∈(0,1)，在多數(shù)HS算法中建議它選取接近于1的較大值；微調(diào)幅度BW由當前搜索半徑Ri(iter)所決定。此外，結合先期實驗結果，擬沿用文獻[25]中的方式動態(tài)設置參數(shù)PAR的值，即以PARmax和PARmin為上、下限，以(PARmax-PARmin)/Itermax為步長而逐代線性遞增。

3.3 算法步驟

步驟1對待優(yōu)化問題、控制參數(shù)進行初始化，并置迭代計數(shù)變量iter←1。其中，需初始化的參數(shù)包括Popsize、?、HMCR、PARmin、PARmax、Itermax。

步驟2按式（2）對果蠅種群的中心位置進行初始化，得到位置向量Δ(0)。

步驟3各個果蠅從種群中心位置Δ(iter-1)出發(fā)，基于隨機確定的單維分量和動態(tài)搜索半徑按式（4）和式（5）進行嗅覺覓食搜索，得到位置集合Popiter。其中，搜索半徑Ri(iter)的值按式（6）確定。

步驟4從位置集合Popiter中找出具備最佳味道濃度（目標函數(shù)值）的食物源位置，并將其作為備選的新種群中心位置，即。

步驟5運用算子Pop_SC對集合Popiter進行群體協(xié)同式重構，得到新位置集合。

步驟9置iter←iter+1。若iter≤Itermax，則轉回步驟3；否則，將Δ(Itermax)作為最終解輸出，結束。

對于算法FFO-SC+HS的計算復雜性分析如下。步驟1對優(yōu)化問題和控制參數(shù)進行初始化，消耗常數(shù)時間O(1)。步驟2對種群中心位置進行初始化，消耗O(n)時間。步驟3～9重復執(zhí)行Itermax次。在每次迭代中，步驟3負責實施嗅覺覓食搜索，需耗用O(Popsize×n)時間；步驟4從集合Popiter中確定備選中心位置，需消耗O(Popsize)時間；步驟5、6和7的計算時間分別由算子Pop_SC、Pop_SC_X2和Pop_SC_HS_X3所決定；步驟8和9均耗用常數(shù)時間O(1)。算子Pop_SC的計算時間為O(Popsize×n)，如算法1所示；算子Pop_SC_X2的計算時間為O(Popsize)，如算法2所示；算子Pop_SC_HS_X3的計算時間為O(n)，如算法3所示。綜上，算法FFO-SC+HS的總體時間復雜度可歸結為O(Itermax×Popsize×n)。

4 實驗結果與分析

4.1 計算實驗準備與相關描述

為了考察、評估FFO-SC+HS算法在函數(shù)優(yōu)化問題求解上的有效性，本文選取10種無約束的最小化函數(shù)進行測試。這10種測試函數(shù)可區(qū)分為3類：單模態(tài)基準函數(shù) f1～f3；存在多個極值的多模態(tài)基準函數(shù) f4和 f5；對常見基準函數(shù)的決策變量進行偏移后而得到的變換型（Shifted）函數(shù) f6～f10。后5種函數(shù)出自“商務與企業(yè)計算（commerce and enterprise computing，CEC）”2010標準測試函數(shù)集[26]。經(jīng)變量偏移后，這些函數(shù)的最優(yōu)值點不再處于搜索空間的中央位置，而出現(xiàn)在邊界或若干狹小區(qū)域中，從而增加了最優(yōu)解的搜索難度。經(jīng)變換后的測試函數(shù)又有可分離（separable）與不可分離（non-separable）函數(shù)之分;通常，可分離函數(shù)優(yōu)化問題求解起來相對容易，完全不可分離函數(shù)最難優(yōu)化。測試函數(shù) f6～f10中，f6～f8為可分離函數(shù)，而 f9和 f10為完全不可分離函數(shù)。對上述10種測試函數(shù)按模態(tài)類型劃分，f1～f3，f6～f7為單模態(tài)（unimodal）函數(shù)；f4～f5，f8～f10屬于多模態(tài)（multimodal）函數(shù)。表1給出了10種測試函數(shù)的表達式、解搜索空間和各自的理論最優(yōu)值。

整個計算實驗在處理器為Intel?CoreTMi3，主頻為2.53 GHz，內(nèi)存為2.0 GB，操作系統(tǒng)為Windows 7 SP1的PC機上進行。實驗中所涉及的各種果蠅優(yōu)化算法均采用Java語言編程實現(xiàn)。

4.2 算法優(yōu)化性能比較與分析

為驗證FFO-SC+HS算法在函數(shù)優(yōu)化質(zhì)量、收斂能力上的優(yōu)越性，擬在表1中的10種測試函數(shù)上對其進行性能對比分析。除了算法FFO-SC+HS外，參與優(yōu)化性能對比的果蠅優(yōu)化算法有標準FOA算法[2]、IFFO算法[15]、MFOA算法[3]和最近問世的IFOA算法[12]。5種果蠅優(yōu)化算法的迭代搜索過程都涉及最大迭代次數(shù)Itermax的設置。考慮到實驗比較條件的公平性和對于解搜索空間維度的依賴性，結合先期計算實驗結果，規(guī)定各果蠅優(yōu)化算法的最大迭代次數(shù)統(tǒng)一取Itermax=2n×103。此外，參考現(xiàn)有文獻中的相關做法，5種果蠅優(yōu)化算法在該性能對比實驗中的其他參數(shù)設置詳情如下：（1）對于果蠅種群規(guī)模，在算法FOA、IFFO和FFO-SC+HS中均取Popsize=10，在算法MFOA中取Popsize=30，而在算法IFOA中取Popsize=50；（2）算法IFFO中搜索半徑最小值λmin= 10-5，搜索半徑最大值λmax=(UB-LB)/2，其中UB和LB分別為算法搜索范圍中各維度上的上限、下限值；（3）在算法MFOA中，子群體的數(shù)目M=5，指數(shù)參數(shù)?=6；（4）算法IFOA中，對擾動放大因子取w=0.3，定位區(qū)間LR=[LB,UB]，隨機飛行的方向與距離區(qū)域FR=[(LB-UB)/1 000,(UB-LB)/1 000]；（5）在算法FFOSC+HS中，取和聲記憶思考率HMCR=0.95，音調(diào)微調(diào)率最小值PARmin=0.01，音調(diào)微調(diào)率最大值PARmax= 0.99，指數(shù)參數(shù)?=6。

Table 1 10 test functions and their searching spaces and theoretical optima表1 10種測試函數(shù)及其搜索空間、理論最優(yōu)值

該優(yōu)化性能對比實驗中，參與對比的果蠅優(yōu)化算法candiFOA∈{FOA,IFFO,MFOA,IFOA,FFO-SC+HS}跟測試函數(shù) fk(k∈{1,2,…,10})聯(lián)合確定一個實驗單元。統(tǒng)一取110種測試函數(shù)的維數(shù)n=50，由此，Itermax=105。在實驗單元(candiFOA,fk)中，算法candi-FOA對測試函數(shù) fk獨立優(yōu)化25次，每次獨立優(yōu)化后，記下當前所得解向量的目標函數(shù)值和優(yōu)化過程所耗用的時間。表2給出了各實驗單元中對于所得目標函數(shù)值的統(tǒng)計結果。其中，mean、±SD與best分別表示25次解搜索過程所得目標值數(shù)據(jù)的平均值、標準差和最好值；對于各測試函數(shù)上每項統(tǒng)計指標的最佳結果，均以粗體標示。

Table 2 Computational results of 5 fruit fly optimization algorithms over test functionsf1～f10表2 5種果蠅優(yōu)化算法對測試函數(shù) f1～f10的優(yōu)化統(tǒng)計結果

由表2可以看出，針對所統(tǒng)計的10×3=30項指標結果，F(xiàn)FO-SC+HS算法在27項指標上的統(tǒng)計結果優(yōu)于其他4種果蠅優(yōu)化算法；與之相比，標準FOA、IFFO、MFOA和IFOA算法分別僅在0、2、1、0項指標上的統(tǒng)計結果采用加粗標示，由此顯示出算法FFOSC+HS對不同類型的無約束連續(xù)函數(shù)在求解精度、求解魯棒性上的相對優(yōu)越性。對于單模態(tài)函數(shù) f1、f7和 f3，F(xiàn)FO-SC+HS算法在求解質(zhì)量上的比較優(yōu)勢尤為顯著。具體地，在指標mean上，次好果蠅優(yōu)化算法的統(tǒng)計結果分別為FFO-SC+HS算法對應結果的1.429E+15、4.744E+14和9.804E+08倍。對于變換型函數(shù) f6和 f8，算法FFO-SC+HS能穩(wěn)健地搜索到理論最優(yōu)值0，展現(xiàn)出了能有效優(yōu)化更高維度函數(shù) f6或 f8的潛力。雖然在函數(shù) f10的指標mean上，算法FFOSC+HS遜色于IFFO算法，但二者相差不大（數(shù)量級一致），且在指標min上它們也有相近的結果。

Fig.1 Convergence curves of 5 FOAs on functionf1圖1 5種果蠅優(yōu)化算法在函數(shù) f1上的收斂曲線

Fig.2 Convergence curves of 5 FOAs on functionf3圖2 5種果蠅優(yōu)化算法在函數(shù) f3上的收斂曲線

Fig.3 Convergence curves of 5 FOAs on functionf4圖3 5種果蠅優(yōu)化算法在函數(shù) f4上的收斂曲線

Fig.4 Convergence curves of 5 FOAs on functionf5圖4 5種果蠅優(yōu)化算法在函數(shù) f5上的收斂曲線

Fig.5 Convergence curves of 5 FOAs on function f7圖5 5種果蠅優(yōu)化算法在函數(shù)f7上的收斂曲線

Fig.6 Convergence curves of 5 FOAs on function f8圖6 5種果蠅優(yōu)化算法在函數(shù)f8上的收斂曲線

為對比分析FFO-SC+HS算法在迭代收斂性上的表現(xiàn)，根據(jù)5種果蠅優(yōu)化算法對部分測試函數(shù)（D= 50）獨立優(yōu)化25次的平均目標值變化趨勢繪制了收斂曲線對比圖，如圖1～圖6所示。對于函數(shù) f1、f3和f4，算法FFO-SC+HS在優(yōu)化搜索的前期、中期未表現(xiàn)出相對更快的收斂速度；然而，迭代次數(shù)超過90 000次以后，它開始加速收斂，收斂速度明顯超過之前快于它的IFFO算法，并最終實現(xiàn)了更佳的收斂精度，詳見圖1～圖3?！跋嚷罂臁钡氖諗口厔菀渤霈F(xiàn)在算法FFO-SC+HS對函數(shù) f7和 f8的迭代優(yōu)化過程中。如圖5所示，算法FFO-SC+HS的收斂速度在優(yōu)化搜索早期不及標準FOA算法，到搜索中期又遜于IFFO算法，直到迭代次數(shù)達到80 000次后才表現(xiàn)出顯著更快的收斂速度。對于函數(shù) f8，F(xiàn)FO-SC+HS算法能通過95 000次迭代穩(wěn)定地搜索到理論最優(yōu)解。這一突出表現(xiàn)完全要歸功于75 000次迭代后的“瀑布式”快速收斂階段，詳見圖6。對于FFO-SC+HS算法在函數(shù)優(yōu)化中的“慢熱”收斂趨勢，究其原因，可歸于它在迭代搜索的后期表現(xiàn)出了相對更強的擺脫局部極優(yōu)的能力。Pop_SC_HS_X3算子中逐代線性遞增的參數(shù)PAR取值是導致迭代后期脫離局部極優(yōu)能力增強的主要原因。事實上，在和聲搜索算法中，當參數(shù)HMCR取接近于1的較大值時，音調(diào)微調(diào)率PAR就成了調(diào)節(jié)全局搜索能力的重要參數(shù)；PAR的值越接近于1，對于即興生成的新和聲解而言，它擺脫局部極優(yōu)的概率就越大。此外，對于函數(shù) f5，算法FFO-SC+ HS表現(xiàn)出比其他4種果蠅優(yōu)化算法更好的收斂能力；當?shù)螖?shù)達到約32 000次時，它沒繼續(xù)保持平穩(wěn)趨勢，而是從局部極值中有效脫離，顯示出相對更好的全局搜索能力和收斂精度，詳見圖4。

相比于標準的果蠅優(yōu)化算法，F(xiàn)FO-SC+HS算法在其視覺覓食搜索階段額外增加了對于算子Pop_ SC、Pop_SC_X2和Pop_SC_HS_X3的計算時間開銷。這3個算子的計算時間復雜度分別為O(Popsize×n)、O(Popsize)和O(n)。不難看出，算法FFO-SC+HS相對于標準果蠅優(yōu)化算法的額外時間開銷跟果蠅種群規(guī)模Popsize和待優(yōu)化問題的求解空間維數(shù)n成正比；當果蠅種群規(guī)模較大或者待優(yōu)化問題的求解空間維數(shù)較高時，算法FFO-SC+HS在計算時間開銷上會明顯超過標準的果蠅優(yōu)化算法。通過對性能對比實驗中每次函數(shù)優(yōu)化所耗用的計算時間數(shù)據(jù)進行統(tǒng)計分析，可以發(fā)現(xiàn)算法FFO-SC+HS在10種測試函數(shù)上的總體平均計算時間約為標準果蠅優(yōu)化算法的1.83倍（兩算法中均取Popsize=10），甚至在函數(shù) f6上FFOSC+HS算法與標準果蠅優(yōu)化算法之間的計算耗時比竟高達7.60。然而，算法FFO-SC+HS的額外計算時間開銷并非徒勞，隨之換來的是比標準果蠅優(yōu)化算法顯著更優(yōu)的優(yōu)化精度和收斂穩(wěn)定性，詳見表2中的相關統(tǒng)計結果。

跟其他果蠅優(yōu)化改進算法相比，算法FFO-SC+ HS在計算時間開銷上雖未表現(xiàn)出全方位的比較優(yōu)勢，但也具備一定的競爭性。表3給出了算法IFOA和FFO-SC+HS在相應實驗單元中針對平均、最少耗用時間的統(tǒng)計結果。表中結果顯示，F(xiàn)FO-SC+HS算法在10種測試函數(shù)上的總體平均計算時間僅為標準果蠅優(yōu)化算法的0.563倍，并且在9種測試函數(shù)上的平均計算時間都少于標準果蠅優(yōu)化算法，在8種測試函數(shù)上的最小計算時間比較中均占優(yōu)。由此，另鑒于它在函數(shù)優(yōu)化質(zhì)量上的相對優(yōu)越性（詳見表2），可認定FFO-SC+HS算法具備比IFOA算法更高的函數(shù)優(yōu)化效率。

4.3 參數(shù)對優(yōu)化性能的影響分析

本節(jié)擬以函數(shù) f1、f4、f6和 f9為實驗對象，力求通過探析參數(shù)組合(Popsize,HMCR,?)的不同取值下FFO-SC+HS算法的優(yōu)化表現(xiàn)，進而得到有價值的參數(shù)取值建議。在該參數(shù)影響分析實驗中，測試函數(shù) fk(k∈{1,4,6,9})以及參數(shù)Popsize、HMCR和?的特定取值聯(lián)合確定一個實驗單元。對于各測試函數(shù)的維度，統(tǒng)一取n=100。對于果蠅種群規(guī)模參數(shù)Popsize，所考慮的水平值分別為10，20，30，40和50。鑒于多數(shù)HS算法都推薦參數(shù)HMCR取接近于1的較大值，在此設置HMCR∈{0.85,0.90,0.95,0.99}。結合前期實驗中對指數(shù)參數(shù)?的取值建議，取?∈{10,15,20}。綜上，該參數(shù)影響分析實驗總共由4×5×4×3=240個實驗單元組成。在每個實驗單元(fk,Popsize,HMCR,?)中，F(xiàn)FO-SC+HS算法對測試函數(shù) fk獨立優(yōu)化30次，以最大函數(shù)評價數(shù)目Max_FEs=3.0×106為每次獨立優(yōu)化的迭代終止條件。每次獨立優(yōu)化過程中，一旦當前所得解向量的目標值達到指定閾值VTR=10-10，則記下已完成的解向量函數(shù)評價數(shù)目FEs。根據(jù)文獻[26]中的建議，若函數(shù)評價次數(shù)未超過3.0×106，則認為該次獨立優(yōu)化是“成功”的，并據(jù)此算出該實驗單元所對應的優(yōu)化成功率（success rate，SR），即：

Table 3 Comparison in computational time of IFOA and FFO-SC+HS over functions f1～f10表3 IFOA和FFO-SC+HS在函數(shù)f1～f10上的計算時間對比

其中，對于第i次獨立優(yōu)化過程，如果FEsi≤3.0×106，則isSuccessi=1；否則，isSuccessi=0。假設為當前實驗單元中全部成功獨立優(yōu)化對于函數(shù)評價數(shù)目FEs的算術平均值。由此，取期望函數(shù)評價比（expected function evaluations ratio，EFER）為該參數(shù)影響分析實驗的響應指標，計算方式如下：

實驗單元(fk,Popsize,HMCR,?)對應的EFER值越小，說明FFO-SC+HS算法在該參數(shù)組合下對函數(shù)fk的優(yōu)化性能越佳。圖7給出了4種測試函數(shù)各自所對應60個實驗單元在指標EFER上的統(tǒng)計結果。

通過觀察圖7可看出，參數(shù)組合(Popsize,HMCR, ?)的不同取值對FFO-SC+HS算法的函數(shù)優(yōu)化表現(xiàn)具有顯著影響，并且?是最主要的影響參數(shù)。當指數(shù)參數(shù)?=15時，無論另兩個參數(shù)取何值，F(xiàn)FO-SC+HS算法在指標EFER的表現(xiàn)上都比?=10，?=20下的FFO-SC+HS算法明顯更優(yōu)。若不考慮參數(shù)?，隨著20種參數(shù)組合(Popsize,HMCR)的變化，算法FFO-SC+ HS在指標EFER上的表現(xiàn)相對穩(wěn)定，并無大幅波動；只是在組合（30，0.90）和（40，0.95）下表現(xiàn)出一定的下降趨勢。相比而言，組合（30，0.90）下的FFO-SC+ HS算法在整體優(yōu)化性能上略優(yōu)于組合（40，0.95）。綜上，算法FFO-SC+HS在函數(shù)優(yōu)化中對參數(shù)組合(Popsize,HMCR,?)的建議取值為（30，0.90，15）。

4.4 兩種融合策略對優(yōu)化性能的影響分析

為了考察算法FFO-SC+HS中群體協(xié)同與和聲搜索策略分別對優(yōu)化性能提高的貢獻，本節(jié)擬以函數(shù)f1、f4、f6、f8和 f9為實驗對象，針對單一混合群體協(xié)同策略的FFO-SC算法、單一混合和聲搜索策略的FFO-HS算法以及FFO-SC+HS算法進行優(yōu)化性能對比實驗與分析。需要注意的是，相比于FFO-SC+HS算法，算法FFO-SC中缺少算子Pop_SC_HS_X3；而算法FFO-HS中則不含算子Pop_SC和Pop_SC_X2，在算子Pop_SC_HS_X3運行時，不再用重構后的食物源位置集合PopSC作為和聲記憶庫，取而代之的是在嗅覺覓食搜索階段形成的位置集合Pop。在該策略影響分析實驗中，算法candiFOA∈{FFO-SC,FFOHS,FFO-SC+HS}與測試函數(shù) fk(k∈{1,4,6,8,9})聯(lián)合確定一個實驗單元。具體地，對于各測試函數(shù)的維度，統(tǒng)一取n=150；算法FFO-SC中不含Pop_SC_ HS_X3算子，無需考慮參數(shù)HMCR的取值；參數(shù)HMCR在算法FFO-HS和算法FFO-SC+HS中均取建議值0.90；此外，在3種對比算法中，參數(shù)Popsize和?均取建議值30和15。在實驗單元(candiFOA,fk)中，算法candiFOA對函數(shù)fk獨立優(yōu)化30次；以最大函數(shù)評價數(shù)目Max_FEs=4×106為每次獨立優(yōu)化的迭代終止條件；每次獨立優(yōu)化過程中一旦發(fā)現(xiàn)搜索到的解向量目標值已達到指定閾值VTR=10-6，則記下已完成的解向量函數(shù)評價數(shù)目FEs；若函數(shù)評價次數(shù)已達到4×106次，而搜索到的解向量目標值仍大于指定閾值10-6，則認定本次獨立優(yōu)化“不成功”。整個策略影響分析實驗由3×5=15個實驗單元組成；對于每個實驗單元，按式（8）統(tǒng)計出它所對應的EFER指標值。圖8給出了FFO-SC、FFO-HS和FFO-SC+HS算法在指標EFER上各自對5種測試函數(shù)的統(tǒng)計結果。

Fig.7 Performances in terms of EFER changing with different combinations(Popsize,HMCR,?)on 4 test functions圖7 4種測試函數(shù)上指標EFER的表現(xiàn)隨不同參數(shù)組合(Popsize,HMCR,?)的變化情況

Fig.8 Results in terms of EFER for FFO-SC,FFO-HS and FFO-SC+HS algorithms on 5 test functions圖8 算法FFO-SC、FFO-HS和FFO-SC+HS在5種測試函數(shù)上對指標EFER的統(tǒng)計結果

由圖8不難看出，算法FFO-SC和FFO-HS在全部5種測試函數(shù)的EFER指標表現(xiàn)上均明顯遜色于本文提出的FFO-SC+HS算法。具體統(tǒng)計數(shù)字顯示，F(xiàn)FO-SC+HS算法在5種測試函數(shù)的總體EFER指標表現(xiàn)上分別比算法FFO-SC和FFO-HS提高了35.80%和32.25%?？梢姡瑹o論群體協(xié)同還是和聲搜索策略都是算法FFO-SC+HS實現(xiàn)其較高優(yōu)化性能的有效途徑，缺一不可。另外，在算法FFO-SC和FFO-HS之間作比較，可發(fā)現(xiàn)算法FFO-HS在5種測試函數(shù)上的EFER指標值都略優(yōu)于FFO-SC，由此反映出和聲搜索策略在算法FFO-SC+HS中的優(yōu)化性能改進貢獻相對更大。

5 結束語

通過在每輪迭代中對嗅覺覓食與視覺覓食環(huán)節(jié)進行同時改進，本文設計出一種融合群體協(xié)同與和聲搜索策略的FFO-SC+HS算法。本文算法的特點主要體現(xiàn)在三方面：一是在嗅覺覓食環(huán)節(jié)中基于隨機確定的單一維度和動態(tài)搜索半徑生成果蠅個體的食物源位置；二是為了擴展種群中心位置的擇優(yōu)選取范圍，運用群體協(xié)同機制對果蠅的位置集合進行自適應重構；三是面向重構后的位置集合，運用和聲搜索策略生成候選的種群中心位置。針對算法FFOSC+HS在10種測試函數(shù)上展開計算實驗；與4種已有的果蠅優(yōu)化算法進行對比，結果顯示FFO-SC+HS算法在整體優(yōu)化質(zhì)量、魯棒性、收斂能力上都具備相對優(yōu)越性。此外，還考察了60種參數(shù)組合(Popsize, HMCR,?)的不同取值以及兩種融合策略對于FFOSC+HS算法優(yōu)化性能的影響。通過分析相關實驗結果發(fā)現(xiàn)：在組合（30，0.90，15）下，算法FFO-SC+HS表現(xiàn)出相對更佳的優(yōu)化性能；無論群體協(xié)同還是和聲搜索策略均對FFO-SC+HS算法的改進具有顯著貢獻。在后續(xù)研究中，一方面應著力從理論上揭示FFO-SC+HS算法的收斂性與有效性，并分析參數(shù)選取對算法的收斂性影響；另一方面，F(xiàn)FO-SC+HS算法在高維有約束連續(xù)優(yōu)化、困難組合優(yōu)化、多目標優(yōu)化等問題中的應用研究需要受到重視。

[1]Pan W T.Fruit fly optimization algorithm[M].Taipei,China: Tsang Hai Book Publishing Co,2011:10-12.

[2]Pan W T.A new fruit fly optimization algorithm:taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26:69-74.

[3]Yuan Xiaofang,Dai Xiangshan，Zhao Jingyi,et al.On a novel multi-swarm fruit fly optimization algorithm and its application[J].Applied Mathematics and Computation，2014, 233:260-271.

[4]Yuan Xiaofang,Liu Yuanming,Xiang Yongzhong,et al.Parameter identification of BIPT system using chaotic-enhanced fruit fly optimization algorithm[J].Applied Mathematics and Computation,2015,268:1267-1281.

[5]Wang Sheng,Yan Bao.Fruit fly optimization algorithm based fractional order fuzzy-PID controller for electronic throttle[J]. Nonlinear Dynamics,2013,73(1):611-619.

[6]Li Hongze,Guo Sen,Li Chunjie,et al.A hybrid annual power load forecasting model based on generalized regression neural network with fruit fly optimization algorithm[J].Knowledge-Based Systems,2013,37:378-387.

[7]Mousavi S M,Alikar N,Niaki S TA,et al.Optimizing a location allocation-inventory problem in a two-echelon supply chain network:a modified fruit fly optimization algorithm[J]. Computers and Industrial Engineering,2015,87:543-560.

[8]Li Junqing,Pan Quanke,Mao Kun.A hybrid fruit fly optimization algorithm for the realistic hybrid flowshop rescheduling problem in steelmaking systems[J].IEEE Transactions on Automation Science and Engineering,2016,13(2): 932-949.

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

[10]Zheng Xiaolong,Wang Ling,Wang Shengyao.A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem[J].Control Theory and Applications,2014,31(2):159-164.

[11]Zheng Xiaolong,Wang Ling.An order-based fruit fly optimization algorithm for stochastic resource-constrained project scheduling[J].Control Theory and Applications,2015, 32(4):540-545.

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

[13]Shan Dan,Cao Guohua,Dong Hongjiang.LGMS-FOA:an improved fruit fly optimization algorithm for solving optimization problems[J].Mathematical Problems in Engineering, 2013,Article ID:108768.

[14]Han Junying,Liu Chengzhong.Fruit fly optimization algorithm based on history cognition[J].Journal of Frontiers of Computer Science and Technology,2014,8(3):368-375.

[15]Pan Quanke,Sang Hongyan,Duan Junhua,et al.An improved fruit fly optimization algorithm for continuous function optimization problems[J].Knowledge-Based Systems, 2014,62:69-83.

[16]Han Junying,Liu Chengzhong.Fruit fly optimization algorithm based on bacterial chemotaxis[J].Journal of Computer Applications,2013,33(4):964-966.

[17]Han Junying,Liu Chengzhong.Adaptive chaos fruit fly optimization algorithm[J].Journal of Computer Applications, 2013,33(5):1313-1316.

[18]Han Junying,Liu Chengzhong.Efficient fruit fly optimization algorithm with reverse cognition[J].Computer Engineering,2013,39(11):223-225.

[19]Han Junying,Liu Chengzhong,Wang Lianguo.Dynamic double subgroups cooperative fruit fly optimization algorithm[J].Pattern Recognition and Artificial Intelligence, 2013,26(11):1057-1067.

[20]Geem Z W,Kim J H,Loganathan G V.A new heuristic optimization algorithm:harmony search[J].Simulation,2001, 76(2):60-68.

[21]Diao Ren,Shen Qiang.Feature selection with harmony search[J].IEEE Transactions on Systems，Man,and Cybernetics:Part B,2012,42(6):1509-1523.

[22]Murren P,Khandelwal K.Design-driven harmony search (DDHS)in steel frame optimization[J].Engineering Structures,2014,59:798-808.

[23]Maleki A,Pourfayaz F.Sizing of stand-alone photovoltaic/ wind/diesel system with battery and fuel cell storage devices by harmony search algorithm[J].Journal of Energy Storage,2015,2:30-42.

[24]Li Yazhi,Li Xiaoping,Gupta J N D.Solving the multiobjective flowline manufacturing cell scheduling problem by hybrid harmony search[J].Expert Systems with Applications，2015,42(3):1409-1417.

[25]Yadav P,Rajesh K,Panda S K,et al.An intelligent tuned harmony search algorithm for optimization[J].Information Sciences,2012,196:42-72.

[26]Tang Ke，Li Xiaodong,Suganthan P N,et al.Benchmark functions for the CEC?2010 special session and competition on large-scale global optimization[R].Hefei:Nature Inspired Computation andApplications Laboratory,USTC,2009.

附中文參考文獻：

[1]潘文超.果蠅最佳化演算法[M].中國臺北:滄海書局, 2011:10-12.

[10]鄭曉龍,王凌,王圣堯.求解置換流水線調(diào)度問題的混合離散果蠅算法[J].控制理論與應用,2014,31(2):159-164.

[11]鄭曉龍,王凌.隨機資源約束項目調(diào)度問題基于序的果蠅算法[J].控制理論與應用,2015,32(4):540-545.

[14]韓俊英,劉成忠.基于歷史認知的果蠅優(yōu)化算法[J].計算機科學與探索,2014,8(3):368-375.

[16]韓俊英,劉成忠.基于細菌趨化的果蠅優(yōu)化算法[J].計算機應用,2013,33(4):964-966.

[17]韓俊英,劉成忠.自適應混沌果蠅優(yōu)化算法[J].計算機應用,2013,33(5):1313-1316.

[18]韓俊英,劉成忠.反向認知的高效果蠅優(yōu)化算法[J].計算機工程,2013,39(11):223-225.

[19]韓俊英,劉成忠,王聯(lián)國.動態(tài)雙子群協(xié)同進化果蠅優(yōu)化算法[J].模式識別與人工智能,2013,26(11):1057-1067.

LIU Le was born in 1984.He received the Ph.D.degree in management science and engineering from Beihang University in 2013.Now he is a lecturer at University of Jinan.His research interests include intelligent optimization algorithms,production scheduling and rescheduling，etc.

劉樂（1984—），男，山東濟南人，2013年于北京航空航天大學獲得管理學博士學位，現(xiàn)為濟南大學管理學院講師，主要研究領域為智能優(yōu)化算法，生產(chǎn)調(diào)度與重調(diào)度優(yōu)化等。已發(fā)表學術論文10余篇，目前主持國家自然科學青年基金項目、教育部人文社科研究青年基金項目以及山東省優(yōu)秀中青年科學家科研獎勵基金項目等。

Fruit Fly Optimization Algorithm by Combining Strategies of Swarm Collaboration and Harmony Search?

LIU Le+
School of Management,University of Jinan,Jinan 250002,China
+Corresponding author:E-mail:sm_liul@ujn.edu.cn

To deal with the drawbacks of trapping in local optimal solutions easily and low convergence accuracy of the standard fruit fly optimization(FFO)algorithm,this paper proposes a novel fruit fly optimization algorithm by combining the swarm collaboration(SC)and harmony search(HS)strategies,named as FFO-SC+HS.In each iteration of FFO-SC+HS,the food source location of each fruit fly is generated based on a single dimension that is randomly determined and dynamic search radius,and two candidate location vectors derived from the reconstructed location set by SC strategy are considered during the update process of fruit fly swarm location.Further,one candidate location is the best one of the reconstructed location set,and the other one is obtained by means of HS strategy.Extensive computational experiments and comparison analysis are conducted upon 10 benchmark functions to validate the effectiveness of FFO-SC+HS.As demonstrated in the results,FFO-SC+HS outperforms other 4 reported FFO algorithms in terms of solution quality and convergence efficiency.Moreover,it is found that different combinations of three main parametershave a significant impact on optimization performances of FFO-SC+HS,and both of the SC and HS strategies are indispensable.

fruit fly optimization;swarm collaboration;harmony search;function optimization

10.3778/j.issn.1673-9418.1510034

A

TP301.6

*The National Natural Science Foundation of China under Grant No.71501083(國家自然科學基金);the Youth Foundation of Humanities and Social Science Research of Ministry of Education of China under Grant No.14YJCZH098(教育部人文社會科學研究青年基金);the Promotive Research Foundation for Outstanding Young and Middle-Aged Scientists of Shandong Province under Grant No.BS2015ZZ002(山東省優(yōu)秀中青年科學家科研獎勵基金);the Research Foundation of University of Jinan under Grant No. XKY1322(濟南大學科研基金).

Received 2015-10,Accepted 2015-12.

CNKI網(wǎng)絡優(yōu)先出版:2015-12-16,http://www.cnki.net/kcms/detail/11.5602.TP.20151216.1021.004.html