結合群體協同與和聲搜索策略的果蠅優化算法*

劉 樂

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

結合群體協同與和聲搜索策略的果蠅優化算法*

劉 樂+

濟南大學 管理學院，濟南 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.

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

果蠅優化；群體協同；和聲搜索；函數優化

1 引言

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

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

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

2 標準的果蠅優化算法

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

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

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

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

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

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

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

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

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

3 新型的果蠅優化改進算法

相互均衡的集約化（intensification）與分散化（diversification）搜索策略是成功開發出元啟發式算法的重要保證。集約化尋優旨在迄今最佳解的鄰近區域實施局部搜索，一定程度上會增加求得更好解的概率；但過分追求集約化，易使算法陷入局部極優，弱化全局優化搜索的能力。分散化尋優往往要借助當前種群信息或啟發式信息執行覆蓋全局的隨機化搜索，這樣有助于算法擺脫局部極優；但一味注重搜索的分散化，會徒勞地評價許多非最優解，進而影響整體的優化搜索效率。為此，成功的果蠅優化改進算法應實現集約化與分散化搜索之間的有效協調，既要在嗅覺覓食階段強化集約化搜索的作用，又需在果蠅種群中心位置的更新環節實施專門的分散化尋優機制。

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

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

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

結合前期實驗結果發現，算法FFO-SC+HS中指數參數?的取值應大于5。

3.2 基于群體協同與和聲搜索的分散化尋優

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

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

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

3.3 算法步驟

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

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

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

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

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

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

對于算法FFO-SC+HS的計算復雜性分析如下。步驟1對優化問題和控制參數進行初始化，消耗常數時間O(1)。步驟2對種群中心位置進行初始化，消耗O(n)時間。步驟3～9重復執行Itermax次。在每次迭代中，步驟3負責實施嗅覺覓食搜索，需耗用O(Popsize×n)時間；步驟4從集合Popiter中確定備選中心位置，需消耗O(Popsize)時間；步驟5、6和7的計算時間分別由算子Pop_SC、Pop_SC_X2和Pop_SC_HS_X3所決定；步驟8和9均耗用常數時間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算法在函數優化問題求解上的有效性，本文選取10種無約束的最小化函數進行測試。這10種測試函數可區分為3類：單模態基準函數 f1～f3；存在多個極值的多模態基準函數 f4和 f5；對常見基準函數的決策變量進行偏移后而得到的變換型（Shifted）函數 f6～f10。后5種函數出自“商務與企業計算（commerce and enterprise computing，CEC）”2010標準測試函數集[26]。經變量偏移后，這些函數的最優值點不再處于搜索空間的中央位置，而出現在邊界或若干狹小區域中，從而增加了最優解的搜索難度。經變換后的測試函數又有可分離（separable）與不可分離（non-separable）函數之分;通常，可分離函數優化問題求解起來相對容易，完全不可分離函數最難優化。測試函數 f6～f10中，f6～f8為可分離函數，而 f9和 f10為完全不可分離函數。對上述10種測試函數按模態類型劃分，f1～f3，f6～f7為單模態（unimodal）函數；f4～f5，f8～f10屬于多模態（multimodal）函數。表1給出了10種測試函數的表達式、解搜索空間和各自的理論最優值。

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

4.2 算法優化性能比較與分析

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

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

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

Table 2 Computational results of 5 fruit fly optimization algorithms over test functionsf1～f10表2 5種果蠅優化算法對測試函數 f1～f10的優化統計結果

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

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

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

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

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

Fig.5 Convergence curves of 5 FOAs on function f7圖5 5種果蠅優化算法在函數f7上的收斂曲線

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

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

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

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

4.3 參數對優化性能的影響分析

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

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

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

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

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

4.4 兩種融合策略對優化性能的影響分析

為了考察算法FFO-SC+HS中群體協同與和聲搜索策略分別對優化性能提高的貢獻，本節擬以函數f1、f4、f6、f8和 f9為實驗對象，針對單一混合群體協同策略的FFO-SC算法、單一混合和聲搜索策略的FFO-HS算法以及FFO-SC+HS算法進行優化性能對比實驗與分析。需要注意的是，相比于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}與測試函數 fk(k∈{1,4,6,8,9})聯合確定一個實驗單元。具體地，對于各測試函數的維度，統一取n=150；算法FFO-SC中不含Pop_SC_ HS_X3算子，無需考慮參數HMCR的取值；參數HMCR在算法FFO-HS和算法FFO-SC+HS中均取建議值0.90；此外，在3種對比算法中，參數Popsize和?均取建議值30和15。在實驗單元(candiFOA,fk)中，算法candiFOA對函數fk獨立優化30次；以最大函數評價數目Max_FEs=4×106為每次獨立優化的迭代終止條件；每次獨立優化過程中一旦發現搜索到的解向量目標值已達到指定閾值VTR=10-6，則記下已完成的解向量函數評價數目FEs；若函數評價次數已達到4×106次，而搜索到的解向量目標值仍大于指定閾值10-6，則認定本次獨立優化“不成功”。整個策略影響分析實驗由3×5=15個實驗單元組成；對于每個實驗單元，按式（8）統計出它所對應的EFER指標值。圖8給出了FFO-SC、FFO-HS和FFO-SC+HS算法在指標EFER上各自對5種測試函數的統計結果。

Fig.7 Performances in terms of EFER changing with different combinations(Popsize,HMCR,?)on 4 test functions圖7 4種測試函數上指標EFER的表現隨不同參數組合(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種測試函數上對指標EFER的統計結果

由圖8不難看出，算法FFO-SC和FFO-HS在全部5種測試函數的EFER指標表現上均明顯遜色于本文提出的FFO-SC+HS算法。具體統計數字顯示，FFO-SC+HS算法在5種測試函數的總體EFER指標表現上分別比算法FFO-SC和FFO-HS提高了35.80%和32.25%。可見，無論群體協同還是和聲搜索策略都是算法FFO-SC+HS實現其較高優化性能的有效途徑，缺一不可。另外，在算法FFO-SC和FFO-HS之間作比較，可發現算法FFO-HS在5種測試函數上的EFER指標值都略優于FFO-SC，由此反映出和聲搜索策略在算法FFO-SC+HS中的優化性能改進貢獻相對更大。

5 結束語

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

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

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

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

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

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

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

[19]韓俊英,劉成忠,王聯國.動態雙子群協同進化果蠅優化算法[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年于北京航空航天大學獲得管理學博士學位，現為濟南大學管理學院講師，主要研究領域為智能優化算法，生產調度與重調度優化等。已發表學術論文10余篇，目前主持國家自然科學青年基金項目、教育部人文社科研究青年基金項目以及山東省優秀中青年科學家科研獎勵基金項目等。

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(山東省優秀中青年科學家科研獎勵基金);the Research Foundation of University of Jinan under Grant No. XKY1322(濟南大學科研基金).

Received 2015-10,Accepted 2015-12.

CNKI網絡優先出版:2015-12-16,http://www.cnki.net/kcms/detail/11.5602.TP.20151216.1021.004.html