随着社会的进步和科技的快速发展，大量的复杂优化问题相继出现，为此，许多群体智能优化算法^[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-sub-groups 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)设置参数

$D$ 表示问题的维数，HMS (harmony memory size)为和声记忆库的大小， ${T_{\max }}$ 为算法迭代的最大次数，HMCR (harmony memory considering rate) 为和声记忆库选择概率，PAR (pitch-adjusting rate)为局部微调概率，bw为局部微调步长 。

2)随机初始化和声记忆库HM ( harmony memory)

$x_i^j = x{L_i} + {{rand}} \cdot (x{U_i} - x{L_i})$

(1)

式中： $i = 1,2, \cdots, D$ ； $j = 1,2, \cdots, $ HMS；rand为 $(0,1)$ 的随机数。

$\bf{HMS} = \left[ {\begin{array}{*{20}{c}} {{x^1}} \\ [3pt] {{x^2}} \\ [3pt] \vdots \\ [3pt] {{x^{{HMS}}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {x_1^1}&{x_2^1}& \cdots &{x_1^1} \\ [3pt] {x_1^2}&{x_2^2}& \cdots &{x_D^2} \\ [3pt] \vdots & \vdots &{}& \vdots \\ [3pt] {x_1^{{HMS}}}&{x_2^{{HMS}}}& \cdots &{x_D^{{HMS}}} \end{array}} \right]$

3)使用3种调节规则创作新的和声

每次迭代可通过如下3种规则产生新和声：

${{{x}}^{{new}}} = [x_1^{{new}} \,\, x_2^{{new}} \,\, \cdots \,\, x_D^{{new}}]$

①从和声记忆库HM中选择。新和声 ${x^{{new}}}$ 的第 $i$ 维变量 $x_i^{{new}}(i = 1,2, \cdots \!, D)$ 以概率HMCR从和声记忆库的第i维 $\{ x_i^1,x_i^2, \cdots \!, x_i^{{HMS}}\} $ 中选择。

②局部微调。将②中产生的 $x_i^{{new}}(i = 1,2, \cdots, D)$ 以概率PAR进行微调，如式(2)：

$x_i^{{new}} = x_i^{{new}} \pm {{rand}} \cdot {{bw}}(i)$

(2)

③在搜索空间内随机生成。新和声 ${x^{{new}}}$ 的第 $i$ 维变量 $x_i^{{new}}(i = 1,2, \cdots \!, D)$ 以概率1 – HMCR在搜索空间内随机生成。具体方法如下：

$x_i^{{new}} = x{L_i} + {{rand}} \cdot (x{U_i} - x{L_i})$

(3)

4)更新和声记忆库

对3)中产生的新和声 ${x^{{new}}}$ 进行评估，如果优于记忆库中的最差和声 ${x^{{worst}}}$ ，则用 ${x^{{new}}}$ 替换 ${x^{{worst}}}$ ，否则转3)。重复3)、4)，直到满足终止条件为止。

1.2 改进的和声算法

为改善HS算法的性能，文献[5]提出了改进的和声算法(IHS)，算法动态地对参数PAR和bw进行调整。参数PAR随迭代的增加而线性增大，bw呈指数地递减，迭代初期用较大的值来增加多样性，迭代后期使用较小的值来提高解的精度。

${{PAR}}(t) = {{PA}}{{{R}}_{\min }} + \frac{{{{PA}}{{{R}}_{\max }} - {{PA}}{{{R}}_{\min }}}}{{{T_{\max }}}} \times t$

(4)

${{bw}}(t) = {{{bw}}_{\max }}\exp (t \times \ln (\frac{{{{{bw}}_{\min }}}}{{{{{bw}}_{\max }}}})/{T_{\max }})$

(5)

式中： ${T_{\max }}$ 为最大迭代次数， $t$ 为当前迭代次数， ${{PA}}{{{R}}_{\max }}$ 为最大微调概率， ${{PA}}{{{R}}_{\min }}$ 为最小微调概率， ${{{bw}}_{\max }}$ 为最大微调步长， ${{{bw}}_{\min }}$ 是最小微调步长。

2 差分进化算法 2.1 标准的差分进化算法

标准差分算法包括变异、交叉和选择3种基本操作，其基本步骤^[2]如下：

1)参数设置及初始化

$D$ 表示问题的维数，NP表示种群的规模，CR为交叉概率， $F$ 为缩放因子， ${T_{\max }}$ 为最大迭代次数。随机初始化种群 ${{X}^0} = [x_1^0 \,\, x_2^0 \,\, \cdots \,\, x_{{NP}}^0]$ ， $x_i^t$ 表示第 $t$ 代种群的第 $i$ 个个体。

2)变异操作

对 $t$ 代种群中的每个个体 $x_i^t$ 按式(6)进行变异操作，得到个体：

$v_i^t = x_{r1}^t + F \cdot (x_{r2}^t - x_{r3}^t)$

(6)

式中 ${r_1},{r_2},{r_3} \in \left\{ {1,2, \cdots, {{NP}}} \right\}$ 互不相同且不同于 $i$ 。

3)交叉操作

对个体 $x_i^t$ 和 $v_i^{t}$ 进行交叉操作，生成实验个体：

$u_{i,j}^{t + 1} = \left\{ {\begin{array}{*{20}{l}}{v_{i,j}^t}, &{({{rand}}(j) \leqslant {{CR}})\,{{or}}\,(j = {j_{{rand}}})}\\{x_{i,j}^t}, &\text{其他}\end{array}} \right.$

(7)

4)选择操作

对个体 $x_i^t$ 和 $u_i^{t + 1}$ 的适应值进行比较，选择更优个体作为新种群的个体：

$x_i^{t + 1} = \left\{ {\begin{array}{*{20}{l}} {u_i^{t + 1}},&{f(u_i^{t + 1}) < f(x_i^t)} \\ {x_i^t},&{\text{其他}} \end{array}} \right.$

(8)

式中 $f( \cdot )$ 为适应值函数。

通过不断进化，直到满足终止条件停止。

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)：

$v_i^t = x_{r1}^t + F \cdot [\lambda x_{{best}}^t + (1 - \lambda )x_{r2}^t - x_{r3}^t]$

(9)

当 $t \leqslant {T_{\max }}/2$ ， $\lambda = 0$ ，式(9)即为DE/rand/1，表示在迭代的前半阶段，算法主要进行全局搜索；当 ${T_{\max }}/2 \leqslant $ $ t \leqslant {T_{\max }}$ ， $\lambda = 1$ ，即在迭代的后半阶段，算法主要进行局部开发，提高收敛速度和求解精度。

3 混合和声差分算法

对于不同的优化问题甚至同一问题的不同进化阶段，最适合的进化策略都不同。针对多模态复杂优化问题，为充分发挥HS算法和DE算法的各自优势，本文设计了一种混合机制，自适应地选择使用HS算法或DE算法来更新新一代种群。

3.1 算法混合机制

算法使用自适应选择因子(selected factor，SF)来决定在一个选择周期( $T$ )内选择HS算法或DE算法作为种群更新方式的比例，而自适应选择因子是依据一个选择周期内两种算法的加权累积成功率(success rate，SR)动态得到的。在第 $k$ 个选择周期，首先生成一个随机数 ${r^{(k)}} \in (0,1)$ ，如果 ${r^{(k)}} < {{S}}{{{F}}^{(k)}}$ ，选择使用HS算法来更新种群；否则，使用DE算法来更新种群。

具体如下：令 ${{SR}}_{{H}}^{{{(0)}}} = 1$ ， ${{SR}}_{{D}}^{{{(0)}}} = 1$ ， ${{S}}{{{F}}^{(0)}} = 0.5$ 。对 $k = 1,2, \cdots \!, \left[ {{T_{\max }}/T} \right]$ ，

$\begin{array}{*{20}{c}}{{{SR}}_{H}^{(k)} = \displaystyle\frac{{{c_1}(k) - {c_1}(k - 1)}}{{T \times {{S}}{{{F}}^{{{(K - 1)}}}}}} + \rho \cdot {{SR}}_{{H}}^{{{(k - 1)}}}} = \\[10pt]{ {{SP}}_H^{(k)} + \rho \cdot {{SP}}_H^{(k - 1)} + \cdots + {\rho ^{k - 1}} \cdot {{SP}}_H^{(1)}} = \\[5pt]{\displaystyle\sum\limits_{i = 0}^k {{\rho ^i} \cdot } {{SP}}_H^{(k - i)}}\end{array}$

(10)

$\begin{array}{*{20}{c}}{{{SR}}_{{D}}^{{{(k)}}} = \displaystyle\frac{{{c_2}(k) - {c_2}(k - 1)}}{{T \times {{S}}{{{F}}^{{{(K - 1)}}}}}} + \mu \cdot {{SR}}_{{H}}^{{{(k - 1)}}}} = \\[10pt]{{{SP}}_D^{(k)} + \mu \cdot {{SP}}_D^{(k - 1)} + \cdots + {\mu ^{k - 1}} \cdot {{SP}}_D^{(1)}} = \\[5pt]{\displaystyle\sum\limits_{i = 0}^k {{\mu ^i} \cdot {{SP}}_D^{(k - i)}} }\end{array}$

(11)

${{S}}{{{F}}^{{{(k)}}}}{{ = }}\frac{{{{SR}}_{{H}}^{{{(k)}}}}}{{{{SR}}_{{H}}^{{{(k)}}}{{ + SR}}_{{D}}^{{{(k)}}}}}$

(12)

式中： ${T_{\max }}$ 为最大迭代次数； $T$ 为选择周期，即经过 $T$ 次迭代后重新计算选择因子，本文中 $T = 120$ ； $\rho $ 和 $\mu $ 是加权系数，表示考虑进化过程的历史信息，本文中 $\rho = 1.02$ ， $\mu = 1$ ； ${c_1}(k)$ 、 ${c_2}(k)$ 分别表示前 $k$ 个选择周期内使用HS算法和DE算法累计更新成功的个体数目； ${{SP}}_D^{(k)}$ 、 ${{SP}}_H^{(k)}$ 分别表示DE算法和HS算法在第 $k$ 个选择周期的实际更新成功率，即更新成功的个体数与实际产生的新个体数的比值； ${{SR}}_{{D}}^{{{(k)}}}$ 、 ${{SR}}_{{H}}^{{{(k)}}}$ 分别表示DE算法和HS算法在第 $k$ 个选择周期的实际更新成功率的加权和，即累积加权更新成功率； ${{S}}{{{F}}^{{{(k)}}}}$ 表示第 $k$ 个选择周期的选择因子。

分析上述过程，在第1个选择周期内，两种算法被选择的概率相同。以后的每个周期，兼顾考虑进化过程的当前信息和历史信息，根据累积加权更新成功率来动态选择更新种群的方式，哪种算法在进化过程中越活跃，被选择的概率就越大。使用累积成功率和设置选择周期也可以防止两种更新策略退化为单一策略现象的发生。迭代初期，HS算法因为具有优越的全局搜索能力而会获得较多的机会，有利于快速定位最优解所在的区域；迭代中后期，DE算法的更新成功率增大，主要进行精细搜索，获得精度较高的解。两种算法在同一种群中共享信息，相互协作，进化早期的DE算法可以加快收敛速度，后期的HS算法能够维持种群的多样性。

3.2 算法流程

HHSDE算法的具体流程如图1所示：

4 实验仿真测试

为评估本文所提算法的性能，将其与另外6种优秀算法(SaDE、CoDE、DE、HIS、DIHS、NGHS)在10个多模态的benchmark函数^[19]上比较测试。

F₁：Ackley Function；

F₂：Griewank Function；

F₃：Levy Function；

F₄：Schwefel 2.22 Function；

F₅：Schwefel 2.26 Function；

F₆：Rastrigin Function；

F₇：FastFractal‘DoubleDip’ Function；

F₈：Ackley Shift Function；

F₉：Griewank Shift Function；

F₁₀：Rastrigin Shift Function。

其中F₁~F₇是非常复杂的多模态函数，当维数大于50时，很多优秀的群智能优化算法都不能得到满意的解；F₈~F₁₀是对3个经典的测试函数进行了Shift操作，使其计算难度大幅增加，能够更好地测试算法的通用性(许多优秀的智能优化算法往往对这类问题存在偏好型，比如当最优解在(0,0， $ \cdots $ ,0)时，求解性能非常好，反之性能变得很差)。

4.1 运行环境与参数设置

本文进行的所有测试，硬件环境为戴尔PC机：Intel Xeon(TM)i7-4790 3.6 GHz CPU,8 GB内存; 软件环境Window7操作系统，MATLAB 2014b软件。为公平起见，本文采用相同的最大适应度函数评价次数(MaxFEs=5 000×D), D为维数。6种比较算法的参数设置参照于原文献，本文算法参数具体设置为：C_r=0.4，F=0.5，PARmax=0.99，PARmax=0.1，bw_max=((x^U–x^L)/100，bw_min=(x^U–x^L)/10¹⁰，T=120 HMCR=0.98，ρ=1.02，μ=1。

4.2 实验结果与分析

表1～2分别展示了D=30和D=100时，10个测试函数的30次独立实验统计结果，对每一个函数都记录了最优解和最差解，并统计了30次实验的最优平均值和运行时间。从表1～2可以看出，这10个测试函数中，HHSDE算法除了在函数F₄(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次最优解的分布很集中，说明了本文算法具有很强的稳定性。

4.3 HHSDE算法的混合机制分析

为分析本文算法的自适应混合机制，跟踪记录了HHSDE算法中的IHS和DE两种策略的更新成功率。图6和图7分别绘制了D=100维时两种策略的累积更新个体数目图和更新成功率曲线。从图6可以看出，在迭代初期，IHS算法累积成功更新的个体数量较多，可以快速定位最优解的区域，但随着迭代的进行，DE算法累积更新的个体数目迅速增多，主要进行深度开发，提高解的精度。从图7以看出，IHS算法的概率随着进化的进行逐渐减小，而DE算法被选择的概率逐渐增大。

所提算法能根据寻优问题的特点，针对不同难易程度的优化对象，依据进化过程的历史经验自适应地选择合适的更新策略来满足不同进化阶段的要求，动态调节两种进化策略的选择比例。对Griewank shif，IHS算法能快速定位最优解所在区域，然后主要使用DE算法进行局部搜索，所以两种算法在整个进化过程中的选择概率差异较大；Rastrigin Shift比Griewank shif更复杂，存在更多的局部极小值，进化过程中需要不断地跳出局部极值，从而IHS算法的选择概率下降得较慢，整个进化过程中两种算法的选择概率差异较小。

5 结束语

针对多模态复杂优化问题，提出了一种混合和声差分算法——HHSDE算法。算法通过在不同进化阶段依据累积加权更新成功率来自适应地选择IHS算法和DE算法作为更新种群的方式，能够有效地平衡进化过程的全局搜索与局部搜索。利用10个复杂多模态Benchmark函数对HHSDE算法和其他6种优秀算法进行仿真比较，实验结果和统计分析表明，在100维以内，HHSDE算法收敛速度快，求解精度高，算法稳定性好，能有效求解多模态复杂优化问题。但由于混合算法采用了两种进化机制，参数较多，同时对超过200维的复杂问题，优化效果也不尽理想，在后续的研究过程中，可以设计更好的混合机制来解决更高维的复杂优化问题。