改进的自适应和声搜索算法
- 格式：pdf
- 大小：281.22 KB
- 文档页数：4
第２ｓ卷第２期 ２０１１年３月 甘肃联合大学学报（自然科学版）
Ｊｏｕｒｎａｌ ｏｆ Ｇａｎｓｕ Ｌｉａｎｈｅ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅｓ） Ｖｏ１．２５ Ｎｏ．２
Ｍａｒ．２０１１
文章编号：１６７２－６９１Ｘ（２０１１】０２—００６３—０４ 改进的自适应和声搜索算法
陈莹珍，高岳林 （北方民族大学信息与系统科学研究所。宁夏银川７５００２１）
摘要：和声搜索算法是一种启发式优化算法，针对现有改进的和声搜索算法（ＩＨＳ）的不足，提出了一种改进 的自适应和声搜索算法（ＩＡＨＳ）．在该算法中，采用自适应的和声保留概率、音调调节概率和音调调节步长产生 新解，每次迭代产生多个新解，充分利用和声记忆库的信息．本文用了５个标准的测试函数对该算法进行测试， 结果表明该算法（ＩＡＨＳ）有较强的寻优能力和跳出局部最优解的能力． 关键词：和声搜索算法，自适应搜索 中图分类号：ＴＰ１８ 文献标识码：Ａ
Ｏ引言 ２００１年Ｇｅｅｍ Ｚ Ｗ等人提出了一种新的启 发式算法——和声搜索［１］（Ｈａｒｍｏｎｙ Ｓｅａｒｃｈ， ＨＳ）算法．类似于粒子群算法的思想来源于鸟群 捕食，和声搜索（ＨＳ）的基本思想来源于音乐创 作．在音乐创作中，乐师们反复调整乐队中各乐器 的音调，最终得到一个优美的和声． 研究者们已经提出了各种和声搜索的改进方 法．例如，２００７年Ｍａｈｄａｖｉ Ｍ等提出了ＩＨＳＬ２ 算 法．在基本的和声搜索算法中，音调调节概率 （ＰＡＲ）和调节步长（６ ）都是采用一个固定的值， 但是在实际中，在优化的前期，希望有较小的 ＰＡＲ和较大的ｂｚｖ，随着迭代次数的增加，则希望 有较大的ＰＡＲ和较小的ｂｗ，因此，Ｍａｈｄａｖｉ Ｍ 等提出了基于动态ＰＡＲ和ｂｗ的ＩＨＳ算法．文中 采用的动态的ＰＡＲ和ｂ－ｗ的表达式如下 ＰＡＲ（ｇｎ）一ＰＡＲ ＋（ 一一ＰＡＲ晡 ）×ｇｎ／Ｎ￣， ｂｗ（ｇｎ）一ｂｕａ￣．ｘｅｘｐ（１ｎ（ｂｗｍ×Ｍ）×ｇｎ），（１） 其中ＰＡＲ（ｇｎ）为每一代的音调调节概率， ＰＡＲ ，ＰＡＲ 分别是音调调节概率的最大值和 最小值，Ｎ 为最大迭代次数，ｇ，ｚ为当前迭代次 数，ｂｗ（ｇｎ）为每一代的音调调节步长，６ ， ６ 为音调调节步长的最大值和最小值． ２０１０年，高立群等提出了自适应和声粒子群 搜索（ＡＨＳＰＳＯ）算法［３］．将和声搜索算法与粒子 群搜索算法结合，首先用粒子群优化和声记忆库 中的变量，再利用动态的ＰＡＲ和ｂｗ产生新解， 更新记忆库．文中采用的自适应的音调调节概率 和调节步长如下 ＰＡＲ ：ｆ ，Ｅｆ／Ｅ卜 ≥ 。 ｏ （２） ‘ 【Ｅ ／Ｅ０１，Ｅ／Ｅｆ＿１＜１． 其中Ｅｉ为第ｉ代和声记忆库中解变量的目标函 数值的最大值与最小值之差，Ｅｏ一１； ｂｗ（ ）一ｄｌ （ＨＭ（ ，ｍａｘ）一ＨＭ（ｉ，ｍｉｎ））＋ ２ （ｚ 妒一ｚ乞 ）／ｇｎ， （３） 其中，ｇｎ是当前迭代次数， 坤ｉ妒， ｉ 是变量Ｘ 的上界和下界，ＨＭ（ ，ｍａｘ），ＨＭ（ｉ，ｍｉｎ）是记忆 库中五的最大值和最小值， １， ２是两个常数， 迭代次数较大时，左部分可以起一定的调节作用， 当算法陷入局部最优时，右部分可以起调节作用． 此外，和声搜索已经广泛的应用于工程实际 中［４ ］．例如，２００６年李亮等提出了改进和声搜 索算法及其在土坡稳定分析中的应用［４］．利用改 进的和声搜索算法寻求复杂土坡的临界滑动面及 其对应的安全系数，改进的和声搜索算法在每次 迭代中产生多个新解，而基本的和声搜索算法中 每次迭代只产生一个新解，对改进的和声算法与 基本的和声搜索算法的结果进行了比较，发现改 进的和声搜索算法比基本的和声搜索算法能搜索 到更危险的滑动面． ２００７年，金永强等提出了基于和声搜索的边
收稿日期：２０１０－ＩＩ－１５． 基金项目：国家自然科学基金项目资助（６０９６２００６）． 作者简介：陈莹珍（１９８７一），女，湖北襄樊人，北方民族大学在读硕士，主要从事最优化理论，智能计算等方面的应用 研究． ６４ 甘肃联合大学学报（自然科学版） 第２５卷 坡稳定性投影寻踪聚类分析［５］．传统的和声搜索 算法采用了固定的和声保留概率ＰＡＲ，不能同时 兼顾局部最优解和全局最优解的寻求，本文采用 动态的ＨＭＣＲ和ＰＡＲ对基本的和声搜索算法 进行了改进，针对边坡稳定问题的高维非线性、非 正态的特点，提出了一种基于和声搜索和投影寻 踪理论的边坡稳定性评价方法利用投影寻踪理论 将边坡稳定性评价多指标问题转换为单一投影指 标，采用改进的和声搜索算法优化投影方向．文 中，ＨＭＣＲ和ＰＡＲ的表达式如下 一一 ×ｅｘｐ［ ・ｎ［ 爱］］， ＰＡＲ 一茄ｇｎ（ＰＡＲ ｉ 一ＰＡＲ ）＋ＰＡＲ Ｉｎ． （４） 其中，ＮＩ为最大迭代次数；ｇｎ为当前迭代次数； ＨＭＣＲ ｜ｎ，ＨＭＣＲ ，ＰＡＲ Ｉｎ’ＰＡＲ 分别为迭 代起始时、迭代终止时第ｇｎ次迭代时的ＨＭＣＲ 和ＰＡＲ值． 本文结合了以上的改进方法，并对其中部分 参数做了改进．对和声保留概率（ＨＭＣＲ）、音调 调节概率（ＰＡＲ）都采用线性变换，对文献［３］中 提出的音调调节步长中参数ｄ ，ｄ 也采用了线性 变化，音调调节时增加或减少不再是随机的，而是 由记忆库中的变量的平均值决定的． １基本和声搜索算法 和声搜索（ＨＳ）是基于音乐演奏过程提出来 的．在音乐演奏中，每个演奏者发出一个音调，构 成一个和声向量，如果这个和声比较好，就把它记 录下来，以便下次产生更好的和声．乐器的音调类 比于优化问题中的决策变量 （ 一１，２，…， ），将 各乐器声调的和声类比于解向量 ＝（ ， ， …， ），美学评价类比于目标函数厂（Ｘｊ），音乐家 要找到由美学评价定义的优美的和声，研究人员 要找到由目标函数定义的全局最优解．和声搜索 算法包括一系列的优化因素，例如和声记忆库 （ＨＩＶＩ９，和声记忆库的大小（ＨＭＳ），和声保留概 率（ＨＭＣＲ），音调调节概率（ＰＡＲ）等．在和声搜 索算法中，和声记忆库储存可行解向量，和声记忆 库的大小决定着可行解的数量，和声保留概率就 是从记忆库中选择新产生的解的概率，音调调节 概率是对产生的新解进行扰动的概率． 基本和声搜索的步骤如下： Ｓｔｅｐｌ设定和声搜索的基本参数．（１）变量 的个数Ｎ Ｒ；（２）各变量的取值范围；（３）和声 记忆库可保存和声的个数ＨＭＳ；（４）和声记忆保 留概率ＨＭＣＲ；（５）音调调节概率ＰＡＲ；（６）最大 迭代次数ＮＩ． Ｓｔｅｐ２初始化和声记忆库． Ｓｔｅｐ３产生新解．每次可以通过三种机理产 生一个新解．（１）保留和声记忆库中的分量；（２）随 机选择产生；（３）对（１）、（２）中某些分量进行微调 扰动产生． Ｓｔｅｐ４更新记忆库．若新解优于记忆库中最 差解，则用新解替换最差解，得到新的记忆库． Ｓｔｅｐ５判断是否满足终止条件，若满足，停 止迭代，输出最优解；否则，重复Ｓｅｐ３，Ｓｔｅｐ４．
２改进的和声搜索算法 ２．１和声保留概率 和声保留概率ＨＭＣＲ的变化是由小变化到 大的，在优化的前期阶段，较大的值有利于找到局 部最优解，后期较小的值可以增加解的多样性［引． 根据文献［５］的思想，本文提出了新的和声保留概 率的表达式，定义ＨＭｃＲ的变化如下 ＨＭＣＲ—ＨＭＣＲ 。 一 （ＨＭＣＲ￣，， 一ＨＭＣｌＲ Ｉｎ） ｇｎ／ＮＩ． （５） 其中ｇ＂是当前迭代次数，ＮＩ是最大迭代次数， ＨＭＣＲｍ， ，ＨＭＣ尺 分别为和声保留概率的最大 值和最小值． ２．２音调调节概率 一般情况下，音调调节概率ＰＡＲ的变化是 由小到大的，在优化的前期阶段，较小的值有利于 找到局部最优解，后期较大的值可以增加解的多 样性．根据文献［２］的思想，本文提出了音调调节 概率的表达式，ＰＡＲ的变化定义如下 ＰＡＲ一（Ｏ．３８２。ｇｎ＋０．６１８ｇｎ）／ＮＩ． （６） 其中ｇｎ是当前迭代次数，ＮＩ是最大迭代次数． ２．３音调调节的步长 在最初的和声搜索中，每个变量的调节步长 ｂｗ是一样的，但是这个步长并不适合所有的变 量，根据文献［３］中音调调节步长的变化，对于 ｄ１，ｄ２两个参数，做了如下的改进 （ ）一ｄｌ （ＨＭ（ｆ，ｍａｘ）一ＨＭ（ｉ，ｒａｉｎ））＋ ｄ２。（ｚ 一ｚ乞一）／ ， ｄｌ一（ １ 一ｄｌ ｉ ）＊ｇｎ／Ｎ！＋ｄｌ ．ｎ； ｄ２一（ｄ２ Ｉｎ—ｄ２一） ｇｎ／ＮＩ＋ｄ２ ．（７） 第２期 陈莹珍等：改进的自适应和声搜索算法 ６５ 其中ｄｌ Ｉｎ， １ ，ｄ２ ｜ｎ，ｄ２ 分别为ｄ１，ｄ２的最 小值和最大值．实验表明，当 １是线性递增的， ２是线性递减时，算法的性能更好． ２．４调节的方向 如果产生的新解需要进行微调，在原来的算 法中都是随机的，本文中计算出记忆库中解的平 均值，如果产生的新解小于平均值，则 一ｚ ＋ＢＷ（ｉ）；若产生的新解大于平均值，则ｚ 一 ｎｃ 一Ｂｗ（ ），其中ｚｆｎ ，ｚ ？ 分别为调节前后解 的值，ａｖｅｒａｇｅ（ｘ ）是和声记忆库中变量墨的 平均值．
，－．～ ｆｚ ＋ＢＷ（ｉ），ｉｆｘ７ ＜一ａｖｅｒａｇｅ（ｘ ）； ｎｅｗ— 一Ｉｚ —ＢＷ（ｉ），ｏｔｈｅｒｓ．
（８） ２．５每代和声产生数目 在本文的迭代过程中，采用了文献［４］的思 想，基本的和声搜索算法在每次迭代中仅产生一 个新的解，没有尽可能大的利用和声记忆库的累 积信息，文献［４］中，每次迭代的过程中都产生Ｎ 个新解，与和声记忆库中ＨＭＳ个解放在一起，找 出ＨＭＳ个最优解作为新的和声记忆库． ２－６改进的和声搜索算法的步骤 Ｓｔｅｐｌ设定和声搜索的基本参数（１）变量的 个数ＮＶＡＲ；（２）各变量的取值范围；（３）和声记 忆库可保存和声的个数ＨＭＳ；（４）每次迭代产生 新解的个数Ｎ；（５）最大迭代次数；（６）和声记忆 保留概率ＨＭＣＲ的上下界；（７）ｄｌｌＩＩｉ ， １一， ｄ２ ．ｎ’ ２ ． Ｓｔｅｐ２初始化和声记忆库． Ｓｔｅｐ３产生新解．通过公式（５），（６），（７）， （８）产生新解，每次迭代得到Ｎ个新解． Ｓｔｅｐ４计算新解的目标函数值，从新产生的 Ｎ个解和记忆库中ＨＭＳ个解中选出ＨＭＳ个好 的解，作为新的和声记忆库． Ｓｔｅｐ５判断是否满足终止条件，如不满足则 返回ｓｔｅｐ３；否则算法结束．
３实验及结果分析 为了检验算法的有效性，下面用了五个经常 用到的测试函数对该算法进行测试．这些函数模 拟了在工程实际中经常碰到的各种特征问题，因 此可以比较准确的衡量算法的优化性能．其表达 式如下：
（１）Ｓｐｈｅｒｅ函数：厂１（ ）一∑ｚ ； （２）Ｒｏｎｓｅｎｂｒｏｃｋ函数：ｆ２（ｘ）一∑（１００ （置＋ｌ—ｚ ）。＋（ｚＩ一１）。）； （３）Ｓｅｈａｆｆｅｒ函数：
