一種求解多模態復雜問題的混合和聲差分算法

黎延海，拓守恒

隨著社會的進步和科技的快速發展，大量的復雜優化問題相繼出現，為此，許多群體智能優化算法[1-5]被提出并成功應用于解決科學計算和工程技術中的大規模復雜問題。差分進化算法(differential evolution，DE)[2]與和聲搜索算法(harmony search，HS)[5]是兩種優秀的群體智能優化算法，已經吸引了眾多研究者的關注。雖然兩種算法具有較好的搜索能力，但仍然存在一些固有的缺陷：HS算法局部開發能力較弱，求解精度低；DE算法容易陷入局部最優而導致停滯。為克服兩種算法的不足，近年來涌現了許多改進算法。一方面，許多HS和DE算法的變體被提出，如改進和聲搜索算法(improved harmony search algorithm，IHS)[5]、全局和聲搜索算法(novel global harmony search algorithm，NGHS)[6]、多子群混合和聲搜索算法(multiple-subgroups hybrid harmony search algorithm，MHHS)[7]、動態降維和聲算法(dyna-mic adjustment atrategy in IHS, DIHS)[8]、全局競爭和聲搜索算法(global competitive harmony search algorithm, GCHS)[9]、復合實驗向量生成策略的差分進化算法(DE with composite trial vector Generation Strategies, CoDE)[10]、全局自適應差分優化算法(DE with strategy adaptation,SaDE)[11]、雙變異差分進化算法(DE with double mutation strategies, DaDE)[12]等；另一方面，也出現了一些HS和DE的融合算法，主要有：采用雙種群進化的協同差分和聲算法(coevolutionary DE with HS,CDEHS)[13]、使用各種差分變異算子來代替HS算法中原有的音調調節方法的混沌自適應差分和聲搜索算法(chaotic self-adaptive differential harmony search algorithm，CSADHS)[14]、基于差分算子的和聲搜索算法[15-16]、改進的和聲差分算法(improved harmony search with differential operator, IHSDE)[17]等。這些改進算法從一定程度上提高了算法的性能，但是在解決部分多模態復雜優化問題時，收斂速度慢，求解精度和魯棒性仍不夠理想。

HS算法在搜索過程中能很好地維持種群的多樣性，具有很強的全局搜索能力，以致它能快速發現最優解所在的區域，但其步長調整策略在進化后期盲目搜索，不能有效調整解的結構，使得和聲記憶庫的多樣性逐漸消失，無法獲得高精度的全局最優解；DE算法由于采用“貪婪”的選擇機制，具有很強的收斂能力，可以獲得較高精度的解，但在處理多模態復雜優化問題時，由于極值點個數隨著維度的增加而急劇增多，種群容易快速聚集，從而導致最優解丟失。針對HS算法和DE算法在處理多模態復雜優化問題時的特點，本文提出了一種混合和聲差分算法(hybrid algorithm based on HS and DE,HHSDE)。不同于已有的兩種算法的融合方式，HHSDE算法設計了一種混合自適應調整機制，在同一種群中采用累積加權更新成功率來自適應地選擇用HS算法或DE算法作為下一代種群的更新方式。為驗證HHSDE算法的性能，通過求解10個多模態Benchmark測試函數[18-19]，并與6種優化算法(SaDE、CoDE、DE、IHS、DIHS、NGHS)進行了對比，驗證了所提算法的有效性和可靠性。

1 和聲搜索算法

1.1 標準和聲搜索算法

標準和聲算法的基本步驟[5]如下:

1)設置參數

2)隨機初始化和聲記憶庫HM ( harmony memory)

3)使用3種調節規則創作新的和聲

每次迭代可通過如下3種規則產生新和聲：

4)更新和聲記憶庫

1.2 改進的和聲算法

為改善HS算法的性能，文獻[5]提出了改進的和聲算法(IHS)，算法動態地對參數PAR和bw進行調整。參數PAR隨迭代的增加而線性增大，bw呈指數地遞減，迭代初期用較大的值來增加多樣性，迭代后期使用較小的值來提高解的精度。

2 差分進化算法

2.1 標準的差分進化算法

標準差分算法包括變異、交叉和選擇3種基本操作，其基本步驟[2]如下：

1)參數設置及初始化

2)變異操作

3)交叉操作

4)選擇操作

通過不斷進化，直到滿足終止條件停止。

2.2 改進的差分進化算法

差分算法區別于其他優化算法之處在于差分變異算子的引用，具有代表性的變異策略主要包括5 種：DE/rand/1、DE/best/1、DE/c–t–b/1、DE/best/2、DE/rand/2。以上常用變異策略中，DE/rand/1的全局搜索能力強，但收斂速度慢，DE/best/1的局部搜索能力強，收斂速度快，但容易陷入局部最優。綜合考慮兩種變異方式的特點，為平衡算子的全局探索和局部開能力，提出了改進的變異策略，具體操如式(9)：

3 混合和聲差分算法

對于不同的優化問題甚至同一問題的不同進化階段，最適合的進化策略都不同。針對多模態復雜優化問題，為充分發揮HS算法和DE算法的各自優勢，本文設計了一種混合機制，自適應地選擇使用HS算法或DE算法來更新新一代種群。

3.1 算法混合機制

算法使用自適應選擇因子(selected factor，SF)來決定在一個選擇周期()內選擇HS算法或DE算法作為種群更新方式的比例，而自適應選擇因子是依據一個選擇周期內兩種算法的加權累積成功率(success rate，SR)動態得到的。在第個選擇周期，首先生成一個隨機數，如果，選擇使用HS算法來更新種群；否則，使用DE算法來更新種群。

分析上述過程，在第1個選擇周期內，兩種算法被選擇的概率相同。以后的每個周期，兼顧考慮進化過程的當前信息和歷史信息，根據累積加權更新成功率來動態選擇更新種群的方式，哪種算法在進化過程中越活躍，被選擇的概率就越大。使用累積成功率和設置選擇周期也可以防止兩種更新策略退化為單一策略現象的發生。迭代初期，HS算法因為具有優越的全局搜索能力而會獲得較多的機會，有利于快速定位最優解所在的區域；迭代中后期，DE算法的更新成功率增大，主要進行精細搜索，獲得精度較高的解。兩種算法在同一種群中共享信息，相互協作，進化早期的DE算法可以加快收斂速度，后期的HS算法能夠維持種群的多樣性。

3.2 算法流程

HHSDE算法的具體流程如圖1所示：

圖1 HHSDE算法流程圖Fig. 1 The flow chart of HHSDE algorithm

4 實驗仿真測試

為評估本文所提算法的性能，將其與另外6種優秀算法 (SaDE、CoDE、DE、HIS、DIHS、NGHS)在10個多模態的benchmark函數[19]上比較測試。

F1：Ackley Function；

F2：Griewank Function；

F3：Levy Function；

F4：Schwefel 2.22 Function；

F5：Schwefel 2.26 Function；

F6：Rastrigin Function；

F7：FastFractal‘DoubleDip’ Function；

F8：Ackley Shift Function；

F9：Griewank Shift Function；

F10：Rastrigin Shift Function。

其中F1～F7是非常復雜的多模態函數，當維數大于50時，很多優秀的群智能優化算法都不能得到滿意的解；F8～F10是對3個經典的測試函數進行了Shift操作，使其計算難度大幅增加，能夠更好地測試算法的通用性(許多優秀的智能優化算法往往對這類問題存在偏好型，比如當最優解在(0,0， · ··,0)時，求解性能非常好，反之性能變得很差)。

4.1 運行環境與參數設置

本文進行的所有測試，硬件環境為戴爾PC機：Intel Xeon(TM)i7-4790 3.6 GHz CPU,8 GB 內存; 軟件環境Window7操作系統，MATLAB 2014b軟件。為公平起見，本文采用相同的最大適應度函數評價次數(MaxFEs=5 000×D), D為維數。6種比較算法的參數設置參照于原文獻，本文算法參數具體設置為：Cr=0.4，F=0.5，PARmax=0.99，PARmax=0.1，bwmax=((xU–xL)/100，bwmin=(xU–xL)/1010，T=120 HMCR=0.98，ρ=1.02，μ=1。

4.2 實驗結果與分析

表1～2分別展示了D=30和D=100時，10個測試函數的30次獨立實驗統計結果，對每一個函數都記錄了最優解和最差解，并統計了30次實驗的最優平均值和運行時間。從表1～2可以看出，這10個測試函數中，HHSDE算法除了在函數F4(Schwefel 2.22 Function)上僅弱于SaDE外，對其他問題，HHSDE 算法的評價指標均優于或不弱于其他6種算法。在運行時間方面，當D=30時，本文算法僅比DE算法用時稍長，在某些問題上與NGHS算法相當，但遠少于其他幾種算法；當D=100時，算法用時就僅少于DE算法。總體來說，對這10個多模態復雜優化問題，用時短的算法在解的精度方面弱于本文算法，而相較于獲得相同最優解的算法，本文算法的用時卻最短。

為檢驗本文算法與比較算法之間的差異，表3列出了30次獨立運算下本文算法與其他6種算法之間置信度為0.05的Wilcoxon符號秩檢驗而得到的 P-value 值，“–”，“+”，“≈”分別表示相應算法的成績與本文算法相比是差、好、相當。(NaN 表示算法成績類似)

從表3可以看出，其他6種算法在10個問題上的成績沒有優于本文算法的，DIHS，IHS 和CoDE分別在6個、4個和2個問題上與本文算法的成績相當。由此可見，本文算法相較于其他算法在統計意義上有著更好的表現。

為進一步分析實驗結果，圖2～5給出了7種算法在D=80維時30次獨立運行的平均收斂曲線圖和最優解分布盒圖。從收斂曲線圖不難看出，本文算法對兩個復雜優化函數(fastfractal“doubledip”function，rastrigin shift function)的收斂曲線呈下降趨勢，收斂精度高于其他算法，說明本文算法的全局搜索能力較強，不易陷入局部最優。從統計盒圖可以看出，本文算法的30次最優解的分布很集中，說明了本文算法具有很強的穩定性。

表1 算法30次獨立運行結果比較(D=30)Table 1 Thirty times optimization results of the algorithm (D=30)

表2 算法30次獨立運行結果比較(D=100)Table 2 Thirty times optimization results of the algorithm (D=100)

表3 標準測試函數30次Wilcoxon符號秩檢驗的P-value(D=100)Table 3 Thirty times P-values of Wilcoxon signed rank test (D=100)

圖2 F7函數的收斂曲線圖Fig. 2 Convergence curves’ comparison of F7

圖4 F7函數的統計盒圖Fig. 4 Boxplot of F7

4.3 HHSDE算法的混合機制分析

圖3 F10函數的收斂曲線圖Fig. 3 Convergence curves’ comparison of F10

圖5 F10函數的統計盒圖Fig. 5 Boxplot of F10

為分析本文算法的自適應混合機制，跟蹤記錄了HHSDE算法中的IHS和DE兩種策略的更新成功率。圖6和圖7分別繪制了D=100維時兩種策略的累積更新個體數目圖和更新成功率曲線。從圖6可以看出，在迭代初期，IHS算法累積成功更新的個體數量較多，可以快速定位最優解的區域，但隨著迭代的進行，DE算法累積更新的個體數目迅速增多，主要進行深度開發，提高解的精度。從圖7以看出，IHS算法的概率隨著進化的進行逐漸減小，而DE算法被選擇的概率逐漸增大。

圖6 兩種更新策略的累積更新個體數目變化曲線Fig. 6 The change curves of cumulative update individuals for the two kinds of update strategy

圖7 兩種更新策略選擇概率變化曲線Fig. 7 The change curves of select probability for the two kinds of update strategy

所提算法能根據尋優問題的特點，針對不同難易程度的優化對象，依據進化過程的歷史經驗自適應地選擇合適的更新策略來滿足不同進化階段的要求，動態調節兩種進化策略的選擇比例。對Griewank shif，IHS算法能快速定位最優解所在區域，然后主要使用DE算法進行局部搜索，所以兩種算法在整個進化過程中的選擇概率差異較大；Rastrigin Shift比Griewank shif更復雜，存在更多的局部極小值，進化過程中需要不斷地跳出局部極值，從而IHS算法的選擇概率下降得較慢，整個進化過程中兩種算法的選擇概率差異較小。

5 結束語

針對多模態復雜優化問題，提出了一種混合和聲差分算法——HHSDE算法。算法通過在不同進化階段依據累積加權更新成功率來自適應地選擇IHS算法和DE算法作為更新種群的方式，能夠有效地平衡進化過程的全局搜索與局部搜索。利用10個復雜多模態Benchmark函數對HHSDE算法和其他6種優秀算法進行仿真比較，實驗結果和統計分析表明，在100維以內，HHSDE算法收斂速度快，求解精度高，算法穩定性好，能有效求解多模態復雜優化問題。但由于混合算法采用了兩種進化機制，參數較多，同時對超過200維的復雜問題，優化效果也不盡理想，在后續的研究過程中，可以設計更好的混合機制來解決更高維的復雜優化問題。

[1]TRELEA I C. The particle swarm optimization algorithm:convergence analysis and parameter selection[J]. Information processing letters, 2003, 85(6): 317–325.

[2]DAS S, SUGANTHAN P N. Differential evolution: a survey of the state-of-the-art[J]. IEEE transactions on evolutionary computation, 2011, 15(1): 4–31.

[3]DASGUPTA K, MANDAL B, DUTTA P, et al. A genetic algorithm (GA) based load balancing strategy for cloud computing[J]. Procedia technology, 2013, 10: 340–347.

[4]DEEPA O, SENTHILKUMAR A. Swarm intelligence from natural to artificial systems: ant colony optimization[J]. International journal on applications of graph theory in wireless Ad hoc networks and sensor networks, 2016, 8(1):9–17.

[5]MAHDAVI M, FESANGHARY M, DAMANGIR E. An improved harmony search algorithm for solving optimization problems[J]. Applied mathematics and computation,2007, 188(2): 1567–1579.

[6]ZOU Dexuan, GAO Liqun, WU Jianhua, et al. Novel global harmony search algorithm for unconstrained problems[J].Neurocomputing, 2010, 73.

[7]夏紅剛, 歐陽海濱, 高立群. 多子群混合和聲搜索算法[J].東北大學學報: 自然科學版, 2015, 36(2): 171–175, 187.XIA Honggang, OUYANG Haibin, GAO Liqun. Multiplesub-groups hybrid harmony search algorithm[J]. Journal of Northeastern university: natural science, 2015, 36(2):171–175, 187.

[8]拓守恒, 雍龍泉, 鄧方安. 動態調整策略改進的和聲搜索算法[J]. 智能系統學報, 2015, 10(2): 307–315.TUO Shouheng, YONG Longquan, DENG Fang’an. Dynamic adjustment strategy for improving the harmony search algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(2): 307–315.

[9]夏紅剛, 歐陽海濱, 高立群, 等. 全局競爭和聲搜索算法[J].控制與決策, 2016, 31(2): 310–316.XIA Honggang, OUYANG Haibin, GAO Liqun, et al. Global competitive harmony search algorithm[J]. Control and decision, 2016, 31(2): 310–316.

[10]WANG Yong, CAI Zixing, ZHANG Qingfu. Differential evolution with composite trial vector generation strategies and control parameters[J]. IEEE transactions on evolutionary computation, 2011, 15(1): 55–66.

[11]QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE transactions on evolutionary computation, 2009, 13(2): 398–417.

[12]李榮雨, 陳慶倩, 陳菲爾. 改進種群多樣性的雙變異差分進化算法[J]. 運籌學學報, 2017, 21(1): 44–54.LI Rongyu, CHEN Qingqian, CHEN Feier. Differential evolution algorithm with double mutation strategies for improving population diversity[J]. Operations research transactions, 2017, 21(1): 44–54.

[13]WANG Ling, LI Lingpo. A coevolutionary differential evolution with harmony search for reliability-redundancy optimization[J]. Expert systems with applications, 2012,39(5): 5271–5278.

[14]ARUL R, RAVI G, VELUSAMI S. Chaotic self-adaptive differential harmony search algorithm based dynamic economic dispatch[J]. International journal of electrical power and energy systems, 2013, 50: 85–96.

[15]雍龍泉, 劉三陽, 張建科, 等. 基于差分算子的和聲搜索算法求解非線性l1模極小化問題[J]. 蘭州大學學報: 自然科學版, 2013, 49(4): 541–546.YONG Longquan, LIU Sanyang, ZHANG Jianke, et al.Improved harmony search algorithm with differential operator for nonlinear l1 norm minimization problems[J].Journal of Lanzhou university: natural sciences, 2013,49(4): 541–546.

[16]YONG Longquan, LIU Sanyang. An improved harmony search algorithm with differential operator for absolute value equation[J]. ICIC express letters, 2014, 8(4): 1151–1157.

[17]ABEDINPOURSHOTORBAN H, HASAN S, SHAMSUDDIN S M, et al. A differential-based harmony search algorithm for the optimization of continuous problems[J].Expert systems with applications, 2016, 62: 317–332.

[18]TANG K, YAO X, SUGANTHAN P N, et al. Benchmark functions for the CEC’2008 special session and competition on large scale global optimization[R]. Technical Report. China: Nature Inspired Computation and Applications Laboratory, USTC, 2007.

[19]TANG Ke, LI Xiaohong, SUGANTHAN P N, et al.Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization[R]. Technical Report. Nanyang: Nature Inspired Computation and Applications Laboratory, USTC, China and Nanyang Technological University, 2009.