一種求解多模態(tài)復(fù)雜問題的混合和聲差分算法

黎延海，拓守恒

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

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

1 和聲搜索算法

1.1 標(biāo)準(zhǔn)和聲搜索算法

標(biāo)準(zhǔn)和聲算法的基本步驟[5]如下:

1)設(shè)置參數(shù)

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

3)使用3種調(diào)節(jié)規(guī)則創(chuàng)作新的和聲

每次迭代可通過如下3種規(guī)則產(chǎn)生新和聲：

4)更新和聲記憶庫

1.2 改進(jìn)的和聲算法

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

2 差分進(jìn)化算法

2.1 標(biāo)準(zhǔn)的差分進(jìn)化算法

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

1)參數(shù)設(shè)置及初始化

2)變異操作

3)交叉操作

4)選擇操作

通過不斷進(jìn)化，直到滿足終止條件停止。

2.2 改進(jìn)的差分進(jìn)化算法

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

3 混合和聲差分算法

對于不同的優(yōu)化問題甚至同一問題的不同進(jìn)化階段，最適合的進(jìn)化策略都不同。針對多模態(tài)復(fù)雜優(yōu)化問題，為充分發(fā)揮HS算法和DE算法的各自優(yōu)勢，本文設(shè)計(jì)了一種混合機(jī)制，自適應(yīng)地選擇使用HS算法或DE算法來更新新一代種群。

3.1 算法混合機(jī)制

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

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

3.2 算法流程

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

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

4 實(shí)驗(yàn)仿真測試

為評估本文所提算法的性能，將其與另外6種優(yōu)秀算法 (SaDE、CoDE、DE、HIS、DIHS、NGHS)在10個(gè)多模態(tài)的benchmark函數(shù)[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是非常復(fù)雜的多模態(tài)函數(shù)，當(dāng)維數(shù)大于50時(shí)，很多優(yōu)秀的群智能優(yōu)化算法都不能得到滿意的解；F8～F10是對3個(gè)經(jīng)典的測試函數(shù)進(jìn)行了Shift操作，使其計(jì)算難度大幅增加，能夠更好地測試算法的通用性(許多優(yōu)秀的智能優(yōu)化算法往往對這類問題存在偏好型，比如當(dāng)最優(yōu)解在(0,0， · ··,0)時(shí)，求解性能非常好，反之性能變得很差)。

4.1 運(yùn)行環(huán)境與參數(shù)設(shè)置

本文進(jìn)行的所有測試，硬件環(huán)境為戴爾PC機(jī)：Intel Xeon(TM)i7-4790 3.6 GHz CPU,8 GB 內(nèi)存; 軟件環(huán)境Window7操作系統(tǒng)，MATLAB 2014b軟件。為公平起見，本文采用相同的最大適應(yīng)度函數(shù)評價(jià)次數(shù)(MaxFEs=5 000×D), D為維數(shù)。6種比較算法的參數(shù)設(shè)置參照于原文獻(xiàn)，本文算法參數(shù)具體設(shè)置為：Cr=0.4，F(xiàn)=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 實(shí)驗(yàn)結(jié)果與分析

表1～2分別展示了D=30和D=100時(shí)，10個(gè)測試函數(shù)的30次獨(dú)立實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果，對每一個(gè)函數(shù)都記錄了最優(yōu)解和最差解，并統(tǒng)計(jì)了30次實(shí)驗(yàn)的最優(yōu)平均值和運(yùn)行時(shí)間。從表1～2可以看出，這10個(gè)測試函數(shù)中，HHSDE算法除了在函數(shù)F4(Schwefel 2.22 Function)上僅弱于SaDE外，對其他問題，HHSDE 算法的評價(jià)指標(biāo)均優(yōu)于或不弱于其他6種算法。在運(yùn)行時(shí)間方面，當(dāng)D=30時(shí)，本文算法僅比DE算法用時(shí)稍長，在某些問題上與NGHS算法相當(dāng)，但遠(yuǎn)少于其他幾種算法；當(dāng)D=100時(shí)，算法用時(shí)就僅少于DE算法?？傮w來說，對這10個(gè)多模態(tài)復(fù)雜優(yōu)化問題，用時(shí)短的算法在解的精度方面弱于本文算法，而相較于獲得相同最優(yōu)解的算法，本文算法的用時(shí)卻最短。

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

從表3可以看出，其他6種算法在10個(gè)問題上的成績沒有優(yōu)于本文算法的，DIHS，IHS 和CoDE分別在6個(gè)、4個(gè)和2個(gè)問題上與本文算法的成績相當(dāng)。由此可見，本文算法相較于其他算法在統(tǒng)計(jì)意義上有著更好的表現(xiàn)。

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

表1 算法30次獨(dú)立運(yùn)行結(jié)果比較(D=30)Table 1 Thirty times optimization results of the algorithm (D=30)

表2 算法30次獨(dú)立運(yùn)行結(jié)果比較(D=100)Table 2 Thirty times optimization results of the algorithm (D=100)

表3 標(biāo)準(zhǔn)測試函數(shù)30次Wilcoxon符號秩檢驗(yàn)的P-value(D=100)Table 3 Thirty times P-values of Wilcoxon signed rank test (D=100)

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

圖4 F7函數(shù)的統(tǒng)計(jì)盒圖Fig. 4 Boxplot of F7

4.3 HHSDE算法的混合機(jī)制分析

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

圖5 F10函數(shù)的統(tǒng)計(jì)盒圖Fig. 5 Boxplot of F10

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

圖6 兩種更新策略的累積更新個(gè)體數(shù)目變化曲線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

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

5 結(jié)束語

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

[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].東北大學(xué)學(xué)報(bào): 自然科學(xué)版, 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]拓守恒, 雍龍泉, 鄧方安. 動態(tài)調(diào)整策略改進(jìn)的和聲搜索算法[J]. 智能系統(tǒng)學(xué)報(bào), 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ìn)種群多樣性的雙變異差分進(jìn)化算法[J]. 運(yùn)籌學(xué)學(xué)報(bào), 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]. 蘭州大學(xué)學(xué)報(bào): 自然科學(xué)版, 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.