·308· 智能系统学报 第10卷 路径优化]、电力系统经济负荷分配问题13]和 BW)。各参数含义如下： PD控制器优化]等领域。然而，研究发现，在有 D为问题的维数，HMS为和声记忆库大小，Tm 限的时间内，和声搜索算法具有很强的全局探索能 为算法迭代次数：HMCR为和声记忆库选择概率， 力，但是，在实数优化问题中，求解精度较低[51。 PAR为局部微调概率，BW为局部微调步长值。 为此，很多改进的和声搜索算法被提出，潘全科 2)随机初始化和声记忆库HM 等[15]采用动态子种群策略提出了局部最好和声搜 =xL:+rand·(xU:-xL:) 索算法，利用自适应动态策略提出一种全局最优和 i=1,2,…,D:j=1,2,…,HMS 声搜索算法[i6]。M.Mahdavi等设计出一种参数动 式中：rand是(0,1)中的随机数。 态调整策略，有效改进了HS算法的性能(IHS)〔18]： 树 7 M.G.H.Omran提出全局最优和声搜索算法 x好 好 . 品 (GHS)【1];Zou[20]采用一种很简单的差分学习策 2 HM 略，有效屏蔽了参数HMCR(harmony memory con-- XHMS sidering rate)和PAR(pitch-adjusting rate),降低了 算法的复杂性21-]。P.Yadav给出一种智能调整和 3)利用3种和声调节规则创作新和声 声搜索算法(THS)[)]:S.Das通过理论分析与证 通过如下3个规则产生新和声xw= 明，给出了一种新的和声步长(pitch bandwidth,BW) [xxw…x8]。 调整算法(EHS)【);本文作者在文献[24]和[25] ①和声记忆库选择。新和声向量x"的决策变 中分别提出了“混沌和声搜索算法”与“基于教与学 量x"(i=1,2,…,D)以概率HMCR从和声记忆库 策略的和声搜索算法”：另外，在一些具体应用中， 的第i维[xx…xs]中随机选取。 对和声搜索算法进行了有效改进[263]。尽管上述 ②局部微调。局部微调是将①中产生的x 改进算法从某些方面对和声搜索算法进行了改进， (i=1,2,…,D)以概率PAR进行再次微调。微调 但并没有从算法的运行代价考虑，比如EHS算法， 方法如下： 虽然搜索能力有了明显的改进，但是，由于每次迭代 xew=xew±rand·BW(i) 都需要计算和声记忆库(harmony memory,HM)的方 ③搜索空间内随机产生。新和声向量x"的决 差，其计算量甚至超过了和声搜索算法本身的计算 策变量x(i=1,2,…,D)以概率1-HMCR在搜索 量，使得算法的运行代价是标准和声算法HS的好 空间内随机产生。产生方法如下： 几倍。特别是在求解高维复杂优化问题时，目前的 xM=xL rand.(xU:-xL) 和声算法运行速度普遍较慢。为此，本文通过引入 4)更新操作 一种动态和声调整策略，使其能够有效提高和声算 如果新和声向量x"优于HM中最差的和声 法的性能，并且，能使算法运行代价降低，提高其搜 x,则用x将其替换，否则，转至(3)重新产生新 索速度。 和声。重复3)、4)，直到满足终止条件。 1 标准和声搜索算法 2动态降维和声调整策略 考虑如下优化问题： 2.12种和声调整策略分析与比较 minf八x),x=[x1x2xp] 目前的和声搜索算法和一些改进算法是在整个 s.t.x;E [xLi,xU:],i=1,2,....D 种群的基础上通过组合策略（规则①）产生新的候 式中：f(x)是目标函数，x是由D个决策变量x 选解，这样实现了组合算子的多样性，因此具有较好 (i=1,2,…,D)构成的解向量，[xL:,xU】表示决 的全局搜索性能。但是，在进化后期，即使发现了全 策变量x:的可行搜索区域.将该优化问题对应于和 局最优解所在的区域，由于其较低的更新成功率 声算法，x表示一个和声向量，f(x)表示和声x的 (更新成功率是指每次产生的新解好于和声记忆库 旋律优美程度（在该问题中，(x)越小，表示其和声 中最差解的概率)，使得算法往往很难获得高精度 旋律越优美)。 的最优解。 1.1标准和声搜索算法 对于一个高维优化问题，必然要从大范围的扰 标准和声搜索算法的基本步骤如下： 动开始逐步到小范围（部分维度）的微调，最终使其 1)设置参数值(D,HMS,T,HMCR,PAR, 在所有维上都能够达到最优，然而，和声优化算法在路径优化［ １２ ］ 、电力系统经济负荷分配问题［ １３ ］ 和 ＰＩＤ 控制器优化［１４］ 等领域。 然而，研究发现，在有 限的时间内，和声搜索算法具有很强的全局探索能 力，但是，在实数优化问题中，求解精度较低［ １５⁃１７］ 。 为此，很多改进的和声搜索算法被提出， 潘全科 等［ １５ ］采用动态子种群策略提出了局部最好和声搜 索算法，利用自适应动态策略提出一种全局最优和 声搜索算法［ １６ ］ 。 Ｍ． Ｍａｈｄａｖｉ 等设计出一种参数动 态调整策略，有效改进了 ＨＳ 算法的性能（ＩＨＳ） ［ １８ ］ ； Ｍ． Ｇ． Ｈ． Ｏｍｒａｎ 提 出 全 局 最 优 和 声 搜 索 算 法 （ＧＨＳ） ［ １９ ］ ； Ｚｏｕ ［２０］采用一种很简单的差分学习策 略，有效屏蔽了参数 ＨＭＣＲ （ ｈａｒｍｏｎｙ ｍｅｍｏｒｙ ｃｏｎ⁃ ｓｉｄｅｒｉｎｇ ｒａｔｅ ）和 ＰＡＲ（ ｐｉｔｃｈ⁃ａｄｊｕｓｔｉｎｇ ｒａｔｅ），降低了 算法的复杂性［ ２１⁃２２ ］ 。 Ｐ．Ｙａｄａｖ 给出一种智能调整和 声搜索算法（ ＩＴＨＳ） ［１７］ ； Ｓ．Ｄａｓ 通过理论分析与证 明，给出了一种新的和声步长（ｐｉｔｃｈ ｂａｎｄｗｉｄｔｈ，ＢＷ） 调整算法（ＥＨＳ） ［ ２３ ］ ；本文作者在文献［２４］和［２５］ 中分别提出了“混沌和声搜索算法”与“基于教与学 策略的和声搜索算法”；另外，在一些具体应用中， 对和声搜索算法进行了有效改进［２６⁃３４］ 。 尽管上述 改进算法从某些方面对和声搜索算法进行了改进， 但并没有从算法的运行代价考虑，比如 ＥＨＳ 算法， 虽然搜索能力有了明显的改进，但是，由于每次迭代 都需要计算和声记忆库（ｈａｒｍｏｎｙ ｍｅｍｏｒｙ，ＨＭ）的方 差，其计算量甚至超过了和声搜索算法本身的计算 量，使得算法的运行代价是标准和声算法 ＨＳ 的好 几倍。 特别是在求解高维复杂优化问题时，目前的 和声算法运行速度普遍较慢。 为此，本文通过引入 一种动态和声调整策略，使其能够有效提高和声算 法的性能，并且，能使算法运行代价降低，提高其搜 索速度。 １ 标准和声搜索算法 考虑如下优化问题： ｍｉｎ ｆ（ｘ），ｘ ＝ ［ｘ１ ｘ２ … ｘＤ］ ｓ．ｔ．ｘｉ ∈ ｘＬｉ，ｘＵｉ [ ] ，ｉ ＝ １，２，…，Ｄ 式中： ｆ（ｘ） 是目标函数， ｘ 是由 Ｄ 个决策变量 ｘｉ （ｉ ＝１，２，…，Ｄ ）构成的解向量， ｘＬｉ，ｘＵｉ [ ] 表示决 策变量 ｘｉ 的可行搜索区域． 将该优化问题对应于和 声算法， ｘ 表示一个和声向量， ｆ（ｘ） 表示和声 ｘ 的 旋律优美程度（在该问题中， ｆ（ｘ） 越小，表示其和声 旋律越优美）。 １．１ 标准和声搜索算法 标准和声搜索算法的基本步骤如下： １）设置参数值（ Ｄ， ＨＭＳ， Ｔｍａｘ， ＨＭＣＲ，ＰＡＲ， ＢＷ）。 各参数含义如下： Ｄ 为问题的维数，ＨＭＳ 为和声记忆库大小， Ｔｍａｘ 为算法迭代次数；ＨＭＣＲ 为和声记忆库选择概率， ＰＡＲ 为局部微调概率，ＢＷ 为局部微调步长值。 ２）随机初始化和声记忆库 ＨＭ ｘ ｊ ｉ ＝ ｘＬｉ ＋ ｒａｎｄ·（ｘＵｉ － ｘＬｉ） ｉ ＝ １，２，…，Ｄ；ｊ ＝ １，２，…，ＨＭＳ 式中：ｒａｎｄ 是（０，１）中的随机数。 ＨＭ ＝ ｘ １ ｘ ２ ．．． ｘ ＨＭＳ é ë ê ê ê ê ê ù û ú ú ú ú ú ＝ ｘ １ １ ｘ １ ２ … ｘ １ Ｄ ｘ ２ １ ｘ ２ ２ … ｘ ２ Ｄ ︙ ︙ ︙ ｘ ＨＭＳ １ ｘ ＨＭＳ ２ … ｘ ＨＭＳ Ｄ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú ３）利用 ３ 种和声调节规则创作新和声 通 过 如 下 ３ 个 规 则 产 生 新 和 声 ｘ ｎｅｗ ＝ ［ｘ ｎｅｗ １ ｘ ｎｅｗ ２ … ｘ ｎｅｗ Ｄ ］ 。 ①和声记忆库选择。 新和声向量 ｘ ｎｅｗ 的决策变 量 ｘ ｎｅｗ ｉ （ｉ ＝ １，２，…，Ｄ） 以概率 ＨＭＣＲ 从和声记忆库 的第 ｉ 维 ［ｘ １ ｉ ｘ ２ ｉ … ｘ ＨＭＳ ｉ ］ Ｔ 中随机选取。 ②局部微调。 局部微调是将①中产生的 ｘ ｎｅｗ ｉ （ｉ ＝１，２，…，Ｄ） 以概率 ＰＡＲ 进行再次微调。 微调 方法如下： ｘ ｎｅｗ ｉ ＝ ｘ ｎｅｗ ｉ ± ｒａｎｄ·ＢＷ（ｉ） ③搜索空间内随机产生。 新和声向量 ｘ ｎｅｗ 的决 策变量 ｘ ｎｅｗ ｉ （ｉ ＝ １，２，…，Ｄ） 以概率 １⁃ＨＭＣＲ 在搜索 空间内随机产生。 产生方法如下： ｘ ｎｅｗ ｉ ＝ ｘＬｉ ＋ ｒａｎｄ·（ｘＵｉ － ｘＬｉ） ４）更新操作 如果新和声向量 ｘ ｎｅｗ 优于 ＨＭ 中最差的和声 ｘ ｗｏｒｓｔ ，则用 ｘ ｎｅｗ 将其替换，否则，转至（３）重新产生新 和声。 重复 ３）、４），直到满足终止条件。 ２ 动态降维和声调整策略 ２．１ ２ 种和声调整策略分析与比较 目前的和声搜索算法和一些改进算法是在整个 种群的基础上通过组合策略（规则①）产生新的候 选解，这样实现了组合算子的多样性，因此具有较好 的全局搜索性能。 但是，在进化后期，即使发现了全 局最优解所在的区域，由于其较低的更新成功率 （更新成功率是指每次产生的新解好于和声记忆库 中最差解的概率），使得算法往往很难获得高精度 的最优解。 对于一个高维优化问题，必然要从大范围的扰 动开始逐步到小范围（部分维度）的微调，最终使其 在所有维上都能够达到最优，然而，和声优化算法在 ·３０８· 智 能 系 统 学 报 第 １０ 卷