第10卷第2期 智能系统学报 Vol.10 No.2 2015年4月 CAAI Transactions on Intelligent Systems Apr.2015 D0:10.3969/j.issn.1673-4785.201402019 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150326.1016.004.html 动态调整策略改进的和声搜索算法 拓守恒，雍龙泉，邓方安 (陕西理工学院数计学院，陕西汉中723001) 摘要：为了得到高维复杂问题的全局高精度最优解，提出一种动态调整策略，并用该策略改进和声搜索算法。算 法选取和声记忆库中最差和声向量作为优化调整目标，随着迭代的进行，逐步降低决策变量的调整概率，该方法能 够使得算法在全局探索能力和局部高精度开发能力之间实现平衡，有效提高了新和声更新最差和声的成功率。通 过6个高维Benchmark测试函数的仿真结果表明，提出的动态调整策略能够有效提高和声搜索算法求解高维复杂优 化问题的能力。 关键词：自适应调整策略：高维优化问题：和声搜索算法 中图分类号：TP391文献标志码：A文章编号：1673-4785(2015)02-0307-09 中文引用格式：拓守恒，雍龙泉，邓方安.动态调整策略改进的和声搜索算法[J].智能系统学报，2015,10(2)：307315. 英文引用格式：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. Dynamic adjustment strategy for improving the harmony search algorithm TUO Shouheng,YONG Longquan,DENG Fang'an (School of Mathematics and Computer Science,Shaanxi University of Technology,Hanzhong 723001,China) Abstract:A dynamic adjustment strategy is used to improve the harmony search algorithm for solving high-dimen- sional multimodal global optimization problems.It chooses the worst harmony vector from the harmony memory (HM)as an optimization objective vector.With the process of iteration,the adjustment probability of decision vari- ables is reduced step by step.It can achieve the balance effectively between the global exploration powers and local exploitation competence,and can increase the success rate of evolution.Finally,the experimental results of 16 high-dimension benchmark functions demonstrated that the proposed method can enhance the performance and ro- bustness of the harmony search algorithm obviously in solving large scale multimodal optimization problems. Keywords:adaptive adjustment strategy;high-dimensional optimization problems;harmony search algorithm 近年来，随着社会的发展和大数据时代的到来，年来，研究者将关注的焦点集中在模拟自然的启发 人们对科技产品的能耗和性能要求越来越高，使得 式(meta-heuristics)优化方法[1]等。 产品的设计遇到了极大的挑战。许多产品的设计需 和声搜索算法是Geem等[1]在2001年通过模 要考虑很多的设计要求，并要使其产品整体设计能 拟音乐家创作音乐和调节和声的过程，提出的一种 够达到最优，这些问题都可转化为大规模复杂优化 新的启发式优化算法。音乐家在音乐创作过程中， 问题(optimization problems,OP)。对于OP问题，近 需要不断调整各个音符，使其成为优美和声。由于 和声算法搜索能力强，并且结构简单，很容易在各种 收稿日期：2014-02-21.网络出版日期：2015-03-26. 基金项目：国家自然科学基金资助项目(11401357)，陕西省教育厅科研软件和硬件中实现，引起很多科学研究者和工程设 资助项目(14K1141):汉中市科技局科研资助项目 (2013hz-39);陕西理工学院科研资助项目(SLGKY13-27) 计人员的关注，近年来，已经广泛应用于实践中，例 通信作者：拓守恒.tu0_sh@126.com. 如，管网优化设计[1]、结构优化设计11)、交通运输
第 １０ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．２ ２０１５ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０２０１９ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０３２６．１０１６．００４．ｈｔｍｌ 动态调整策略改进的和声搜索算法 拓守恒，雍龙泉，邓方安 （陕西理工学院 数计学院，陕西 汉中 ７２３００１） 摘 要：为了得到高维复杂问题的全局高精度最优解，提出一种动态调整策略，并用该策略改进和声搜索算法。 算 法选取和声记忆库中最差和声向量作为优化调整目标，随着迭代的进行，逐步降低决策变量的调整概率，该方法能 够使得算法在全局探索能力和局部高精度开发能力之间实现平衡，有效提高了新和声更新最差和声的成功率。 通 过 ６ 个高维 Ｂｅｎｃｈｍａｒｋ 测试函数的仿真结果表明，提出的动态调整策略能够有效提高和声搜索算法求解高维复杂优 化问题的能力。 关键词：自适应调整策略；高维优化问题；和声搜索算法 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０２⁃０３０７⁃０９ 中文引用格式：拓守恒，雍龙泉，邓方安．动态调整策略改进的和声搜索算法［Ｊ］． 智能系统学报， ２０１５， １０（２）： ３０７⁃３１５． 英文引用格式：ＴＵＯ Ｓｈｏｕｈｅｎｇ， ＹＯＮＧ Ｌｏｎｇｑｕａｎ， ＤＥＮＧ Ｆａｎｇ’ ａｎ． Ｄｙｎａｍｉｃ ａｄｊｕｓｔｍｅｎｔ ｓｔｒａｔｅｇｙ ｆｏｒ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｈａｒｍｏｎｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（２）： ３０７⁃３１５． Ｄｙｎａｍｉｃ ａｄｊｕｓｔｍｅｎｔ ｓｔｒａｔｅｇｙ ｆｏｒ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｈａｒｍｏｎｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ＴＵＯ Ｓｈｏｕｈｅｎｇ， ＹＯＮＧ Ｌｏｎｇｑｕａｎ， ＤＥＮＧ Ｆａｎｇ’ａｎ （Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｓｈａａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｈａｎｚｈｏｎｇ ７２３００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｄｙｎａｍｉｃ ａｄｊｕｓｔｍｅｎｔ ｓｔｒａｔｅｇｙ ｉｓ ｕｓｅｄ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｈａｒｍｏｎｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｈｉｇｈ⁃ｄｉｍｅｎ⁃ ｓｉｏｎａｌ ｍｕｌｔｉｍｏｄａｌ ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ． Ｉｔ ｃｈｏｏｓｅｓ ｔｈｅ ｗｏｒｓｔ ｈａｒｍｏｎｙ ｖｅｃｔｏｒ ｆｒｏｍ ｔｈｅ ｈａｒｍｏｎｙ ｍｅｍｏｒｙ （ＨＭ） ａｓ ａｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｂｊｅｃｔｉｖｅ ｖｅｃｔｏｒ． Ｗｉｔｈ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｉｔｅｒａｔｉｏｎ， ｔｈｅ ａｄｊｕｓｔｍｅｎｔ ｐｒｏｂａｂｉｌｉｔｙ ｏｆ ｄｅｃｉｓｉｏｎ ｖａｒｉ⁃ ａｂｌｅｓ ｉｓ ｒｅｄｕｃｅｄ ｓｔｅｐ ｂｙ ｓｔｅｐ． Ｉｔ ｃａｎ ａｃｈｉｅｖｅ ｔｈｅ ｂａｌａｎｃｅ ｅｆｆｅｃｔｉｖｅｌｙ ｂｅｔｗｅｅｎ ｔｈｅ ｇｌｏｂａｌ ｅｘｐｌｏｒａｔｉｏｎ ｐｏｗｅｒｓ ａｎｄ ｌｏｃａｌ ｅｘｐｌｏｉｔａｔｉｏｎ ｃｏｍｐｅｔｅｎｃｅ， ａｎｄ ｃａｎ ｉｎｃｒｅａｓｅ ｔｈｅ ｓｕｃｃｅｓｓ ｒａｔｅ ｏｆ ｅｖｏｌｕｔｉｏｎ． Ｆｉｎａｌｌｙ， ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ １６ ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎ ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｃａｎ ｅｎｈａｎｃｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｒｏ⁃ ｂｕｓｔｎｅｓｓ ｏｆ ｔｈｅ ｈａｒｍｏｎｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｏｂｖｉｏｕｓｌｙ ｉｎ ｓｏｌｖｉｎｇ ｌａｒｇｅ ｓｃａｌｅ ｍｕｌｔｉｍｏｄａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ． Ｋｅｙｗｏｒｄｓ：ａｄａｐｔｉｖｅ ａｄｊｕｓｔｍｅｎｔ ｓｔｒａｔｅｇｙ； ｈｉｇｈ⁃ｄｉｍｅｎｓｉｏｎａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ； ｈａｒｍｏｎｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ 收稿日期：２０１４⁃０２⁃２１． 网络出版日期：２０１５⁃０３⁃２６． 基金项目：国家自然科学基金资助项目（１１４０１３５７），陕西省教育厅科研 资助 项 目 （ １４ＪＫ１１４１ ）； 汉 中 市 科 技 局 科 研 资 助 项 目 （２０１３ｈｚｚｘ⁃３９）；陕西理工学院科研资助项目（ＳＬＧＫＹ １３⁃２７）． 通信作者：拓守恒．ｔｕｏ＿ｓｈ＠ １２６．ｃｏｍ． 近年来，随着社会的发展和大数据时代的到来， 人们对科技产品的能耗和性能要求越来越高，使得 产品的设计遇到了极大的挑战。 许多产品的设计需 要考虑很多的设计要求，并要使其产品整体设计能 够达到最优，这些问题都可转化为大规模复杂优化 问题（ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ，ＯＰ）。 对于 ＯＰ 问题，近 年来，研究者将关注的焦点集中在模拟自然的启发 式（ｍｅｔａ⁃ｈｅｕｒｉｓｔｉｃｓ）优化方法［ １⁃９ ］等。 和声搜索算法是 Ｇｅｅｍ 等［ １ ］ 在 ２００１ 年通过模 拟音乐家创作音乐和调节和声的过程，提出的一种 新的启发式优化算法。 音乐家在音乐创作过程中， 需要不断调整各个音符，使其成为优美和声。 由于 和声算法搜索能力强，并且结构简单，很容易在各种 软件和硬件中实现，引起很多科学研究者和工程设 计人员的关注，近年来，已经广泛应用于实践中，例 如，管网优化设计［ １０ ］ 、结构优化设计［ １１ ］ 、交通运输
·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, 在所有维上都能够达到最优，然而，和声优化算法在
路径优化［ １２ ］ 、电力系统经济负荷分配问题［ １３ ］ 和 ＰＩＤ 控制器优化［１４］ 等领域。 然而，研究发现，在有 限的时间内，和声搜索算法具有很强的全局探索能 力，但是，在实数优化问题中，求解精度较低［ １５⁃１７］ 。 为此，很多改进的和声搜索算法被提出， 潘全科 等［ １５ ］采用动态子种群策略提出了局部最好和声搜 索算法，利用自适应动态策略提出一种全局最优和 声搜索算法［ １６ ］ 。 Ｍ． Ｍａｈｄａｖｉ 等设计出一种参数动 态调整策略，有效改进了 ＨＳ 算法的性能（ＩＨＳ） ［ １８ ］ ； Ｍ． Ｇ． Ｈ． Ｏｍｒａｎ 提 出 全 局 最 优 和 声 搜 索 算 法 （ＧＨＳ） ［ １９ ］ ； Ｚｏｕ ［２０］采用一种很简单的差分学习策 略，有效屏蔽了参数 ＨＭＣＲ （ ｈａｒｍｏｎｙ ｍｅｍｏｒｙ ｃｏｎ⁃ ｓｉｄｅｒｉｎｇ ｒａｔｅ ）和 ＰＡＲ（ ｐｉｔｃｈ⁃ａｄｊｕｓｔｉｎｇ ｒａｔｅ），降低了 算法的复杂性［ ２１⁃２２ ］ 。 Ｐ．Ｙａｄａｖ 给出一种智能调整和 声搜索算法（ ＩＴＨＳ） ［１７］ ； Ｓ．Ｄａｓ 通过理论分析与证 明，给出了一种新的和声步长（ｐｉｔｃｈ ｂａｎｄｗｉｄｔｈ，ＢＷ） 调整算法（ＥＨＳ） ［ ２３ ］ ；本文作者在文献［２４］和［２５］ 中分别提出了“混沌和声搜索算法”与“基于教与学 策略的和声搜索算法”；另外，在一些具体应用中， 对和声搜索算法进行了有效改进［２６⁃３４］ 。 尽管上述 改进算法从某些方面对和声搜索算法进行了改进， 但并没有从算法的运行代价考虑，比如 ＥＨＳ 算法， 虽然搜索能力有了明显的改进，但是，由于每次迭代 都需要计算和声记忆库（ｈａｒｍｏｎｙ ｍｅｍｏｒｙ，ＨＭ）的方 差，其计算量甚至超过了和声搜索算法本身的计算 量，使得算法的运行代价是标准和声算法 ＨＳ 的好 几倍。 特别是在求解高维复杂优化问题时，目前的 和声算法运行速度普遍较慢。 为此，本文通过引入 一种动态和声调整策略，使其能够有效提高和声算 法的性能，并且，能使算法运行代价降低，提高其搜 索速度。 １ 标准和声搜索算法 考虑如下优化问题： ｍｉｎ ｆ（ｘ），ｘ ＝ ［ｘ１ ｘ２ … ｘＤ］ ｓ．ｔ．ｘｉ ∈ ｘＬｉ，ｘＵｉ [ ] ，ｉ ＝ １，２，…，Ｄ 式中： ｆ（ｘ） 是目标函数， ｘ 是由 Ｄ 个决策变量 ｘｉ （ｉ ＝１，２，…，Ｄ ）构成的解向量， ｘＬｉ，ｘＵｉ [ ] 表示决 策变量 ｘｉ 的可行搜索区域． 将该优化问题对应于和 声算法， ｘ 表示一个和声向量， ｆ（ｘ） 表示和声 ｘ 的 旋律优美程度（在该问题中， ｆ（ｘ） 越小，表示其和声 旋律越优美）。 １．１ 标准和声搜索算法 标准和声搜索算法的基本步骤如下： １）设置参数值（ Ｄ， ＨＭＳ， Ｔｍａｘ， ＨＭＣＲ，ＰＡＲ， ＢＷ）。 各参数含义如下： Ｄ 为问题的维数，ＨＭＳ 为和声记忆库大小， Ｔｍａｘ 为算法迭代次数；ＨＭＣＲ 为和声记忆库选择概率， ＰＡＲ 为局部微调概率，ＢＷ 为局部微调步长值。 ２）随机初始化和声记忆库 ＨＭ ｘ ｊ ｉ ＝ ｘＬｉ ＋ ｒａｎｄ·（ｘＵｉ － ｘＬｉ） ｉ ＝ １，２，…，Ｄ；ｊ ＝ １，２，…，ＨＭＳ 式中：ｒａｎｄ 是（０，１）中的随机数。 ＨＭ ＝ ｘ １ ｘ ２ ．．． ｘ ＨＭＳ é ë ê ê ê ê ê ù û ú ú ú ú ú ＝ ｘ １ １ ｘ １ ２ … ｘ １ Ｄ ｘ ２ １ ｘ ２ ２ … ｘ ２ Ｄ ︙ ︙ ︙ ｘ ＨＭＳ １ ｘ ＨＭＳ ２ … ｘ ＨＭＳ Ｄ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú ３）利用 ３ 种和声调节规则创作新和声 通 过 如 下 ３ 个 规 则 产 生 新 和 声 ｘ ｎｅｗ ＝ ［ｘ ｎｅｗ １ ｘ ｎｅｗ ２ … ｘ ｎｅｗ Ｄ ］ 。 ①和声记忆库选择。 新和声向量 ｘ ｎｅｗ 的决策变 量 ｘ ｎｅｗ ｉ （ｉ ＝ １，２，…，Ｄ） 以概率 ＨＭＣＲ 从和声记忆库 的第 ｉ 维 ［ｘ １ ｉ ｘ ２ ｉ … ｘ ＨＭＳ ｉ ］ Ｔ 中随机选取。 ②局部微调。 局部微调是将①中产生的 ｘ ｎｅｗ ｉ （ｉ ＝１，２，…，Ｄ） 以概率 ＰＡＲ 进行再次微调。 微调 方法如下： ｘ ｎｅｗ ｉ ＝ ｘ ｎｅｗ ｉ ± ｒａｎｄ·ＢＷ（ｉ） ③搜索空间内随机产生。 新和声向量 ｘ ｎｅｗ 的决 策变量 ｘ ｎｅｗ ｉ （ｉ ＝ １，２，…，Ｄ） 以概率 １⁃ＨＭＣＲ 在搜索 空间内随机产生。 产生方法如下： ｘ ｎｅｗ ｉ ＝ ｘＬｉ ＋ ｒａｎｄ·（ｘＵｉ － ｘＬｉ） ４）更新操作 如果新和声向量 ｘ ｎｅｗ 优于 ＨＭ 中最差的和声 ｘ ｗｏｒｓｔ ，则用 ｘ ｎｅｗ 将其替换，否则，转至（３）重新产生新 和声。 重复 ３）、４），直到满足终止条件。 ２ 动态降维和声调整策略 ２．１ ２ 种和声调整策略分析与比较 目前的和声搜索算法和一些改进算法是在整个 种群的基础上通过组合策略（规则①）产生新的候 选解，这样实现了组合算子的多样性，因此具有较好 的全局搜索性能。 但是，在进化后期，即使发现了全 局最优解所在的区域，由于其较低的更新成功率 （更新成功率是指每次产生的新解好于和声记忆库 中最差解的概率），使得算法往往很难获得高精度 的最优解。 对于一个高维优化问题，必然要从大范围的扰 动开始逐步到小范围（部分维度）的微调，最终使其 在所有维上都能够达到最优，然而，和声优化算法在 ·３０８· 智 能 系 统 学 报 第 １０ 卷
第2期 拓守恒，等：动态调整策略改进的和声搜索算法 ·309· 进行优化时，总是通过组合算子产生一个全新的个 HMS =2.6561×10-5,利用方法2得到最优 体x",然后与和声记忆库HM中最差个体x比 HMS 较其优劣性，决定是替换还是丢弃。假设某一D维 解的概率为(1/D)·((HMS-1)/HMS)=0.009, 优化问题的最优解为[xx…x],利用和 显然，方法2具有更高的成功率。图1给出2种方 声搜索算法对其进行优化，开始时，随机初始化后的 法的成功率变化曲线。 和声记忆库HM如式(1)，经过一段时间优化后， 10 HM变为式(2)， ·嘉潮 ◆ x 对 10 x好 HM (1) 10 109 y 10 x HM= 9 (2) 10 020406080100120140160180200 维数D 此时，假设HM的每个和声中都仅有一个决策 图12种方法在维数不同时的更新成功率曲线图 变量没有达到最优。由于和声算法中规则①的调整 Fig.1 The update-success rate curve of two methods on 概率HMCR一般都大于O.9,也就是说规则①在和 different dimensioalities 声搜索算法中是非常重要的，这时，如果仅仅采用和 图1可以看出，在HMS相同的情况下，随着维 声搜索算法中的规则①进行优化。采用下列2种方 数D的增加，方法1的成功率急剧下降，而方法2下 法分别产生一个新和声x,分析2种方法的更新 降幅度很小。在问题的维数较低时，方法1的更新 成功率。 成功率高于方法2，但当维数D>40时，方法2的更 1)如果完全利用规则①产生一个新和声x"= 新成功率高于方法1。 [x…x0]。那么，x"(i=1,2,…,D) 由上例可知，对于一个高维优化问题，利用方法 取到x(i=1,2,…,D)的概率为 HMS 1 ,则 1难以驱动算法获得高精度的最优解。如果借鉴方 HMS 法2的思想进行优化，就有可能取得较好的优化效 x=[xx…x]的概率为 HMS -1 果。因此，本文提出一种基于动态减少调整维数的和 HMS 声优化策略。该策略首先选取和声记忆库中最差和 2)选取HM中一个和声作为调整目标，然后， 声向量作为优化目标，然后，通过对最差和声向量的 随机的将其中某一决策变量利用规则①重新生成。 不断调整，使其达到最优解。在优化刚开始时，对最 假设选取x作为优化调整目标x",则xew= 差和声向量进行较多维数的扰动，使得算法具有较强 [y1x2x;…x。],随机选取一个决策变量 的空间探索能力，随着优化的进行，逐步降低扰动概 进行调整，选取到y1的概率为1/D,并且利用规则 率，仅仅在较少维上进行优化调整，使得优化调整具 ①能够将其调整为x的概率为(HMS-1)/HMS, 有更高的成功率，从而获得高精度的全局最优解。 因此，优化调整后，x=[xx…x0]的概 2.2基于动态降维调整的和声搜索算法 率为(1/D)·((HMS-1)/HMS)。 本文提出的基于动态降维调整策略的和声搜索 假设HMS=10,D=10,则利用方法1得到最优 算法流程请见图2。本文算法中，调整概率 解x=[xx…x门的概率为 TP=TP-(TP-TP)·(t/T)2随着迭代次 HMS -1 数的增加逐步减小（如图3），其中，TP和TPn分 、HMS =0.348678,利用方法2得到最优解的 别为最大调整概率值和最小调整概率值。 概率为(1/D)·((HMS-1)/HMS)=0.09,显然此 在算法优化开始时，以较大的扰动调整概率 时，方法1更容易得到最优解。但是，当HMS=10, TPx进行优化，随着优化进行，调整概率TP逐渐减 维度D=100时，方法1得到最优解的概率为 小，开始进行局部微调。但是，为了防止优化调整概 率太小，可能导致所有维都得不到调整，因此，需要从
进行优化时，总是通过组合算子产生一个全新的个 体 ｘ ｎｅｗ ，然后与和声记忆库 ＨＭ 中最差个体 ｘ ｗｏｒｓｔ 比 较其优劣性，决定是替换还是丢弃。 假设某一 Ｄ 维 优化问题的最优解为 ［ｘ ∗ １ ｘ ∗ ２ … ｘ ∗ Ｄ ］ ，利用和 声搜索算法对其进行优化，开始时，随机初始化后的 和声记忆库 ＨＭ 如式（１），经过一段时间优化后， ＨＭ 变为式（２）， ＨＭ ＝ ｘ １ ｘ ２ ︙ ｘ ＨＭＳ é ë ê ê ê ê ê ù û ú ú ú ú ú ＝ ｘ １ １ ｘ １ ２ … ｘ １ Ｄ ｘ ２ １ ｘ ２ ２ … ｘ ２ Ｄ ︙ ︙ ︙ ｘ ＨＭＳ １ ｘ ＨＭＳ ２ … ｘ ＨＭＳ Ｄ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú （１） ＨＭ ＝ ｘ １′ ｘ ２′ ︙ ｘ ＨＭＳ′ é ë ê ê ê ê ê ù û ú ú ú ú ú ＝ ｙ１ ｘ ∗ ２ … ｘ ∗ Ｄ ｘ ∗ １ ｙ２ … ｘ ∗ Ｄ ︙ ︙ ︙ ｘ ∗ １ ｘ ∗ ２ … ｙＤ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú （２） 此时，假设 ＨＭ 的每个和声中都仅有一个决策 变量没有达到最优。 由于和声算法中规则①的调整 概率 ＨＭＣＲ 一般都大于 ０．９，也就是说规则①在和 声搜索算法中是非常重要的，这时，如果仅仅采用和 声搜索算法中的规则①进行优化。 采用下列 ２ 种方 法分别产生一个新和声 ｘ ｎｅｗ ，分析 ２ 种方法的更新 成功率。 １）如果完全利用规则①产生一个新和声 ｘ ｎｅｗ ＝ ［ ｘ ∗ １ ｘ ∗ ２ … ｘ ∗ Ｄ ］ 。 那 么， ｘ ｎｅｗ ｉ (ｉ ＝ １，２，…，Ｄ) 取到 ｘ ∗ ｉ (ｉ ＝ １，２，…，Ｄ) 的 概 率 为 ＨＭＳ － １ ＨＭＳ ， 则 ｘ ｎｅｗ ＝［ｘ ∗ １ ｘ ∗ ２ … ｘ ∗ Ｄ ］ 的概率为 ＨＭＳ － １ ＨＭＳ æ è ç ö ø ÷ Ｄ 。 ２）选取 ＨＭ 中一个和声作为调整目标，然后， 随机的将其中某一决策变量利用规则①重新生成。 假设选取 ｘ １ 作为优化 调 整 目 标 ｘ ｎｅｗ ， 则 ｘ ｎｅｗ ＝ ［ｙ１ ｘ ∗ ２ ｘ ∗ ３ … ｘ ∗ Ｄ ］ ，随机选取一个决策变量 进行调整，选取到 ｙ１ 的概率为 １ ／ Ｄ ，并且利用规则 ①能够将其调整为 ｘ ∗ １ 的概率为 （ＨＭＳ － １） ／ ＨＭＳ ， 因此，优化调整后， ｘ ｎｅｗ ＝ ［ ｘ ∗ １ ｘ ∗ ２ … ｘ ∗ Ｄ ］ 的概 率为 （１ ／ Ｄ）·（（ＨＭＳ － １） ／ ＨＭＳ） 。 假设 ＨＭＳ ＝ １０，Ｄ＝ １０，则利用方法 １ 得到最优 解 ｘ ｎｅｗ ＝ ［ ｘ ∗ １ ｘ ∗ ２ … ｘ ∗ Ｄ ］ 的 概 率 为 ＨＭＳ － １ ＨＭＳ æ è ç ö ø ÷ Ｄ ＝ ０．３４８ ６７８，利用方法 ２ 得到最优解的 概率为 （１ ／ Ｄ）·（（ＨＭＳ － １） ／ ＨＭＳ） ＝ ０．０９，显然此 时，方法 １ 更容易得到最优解。 但是，当 ＨＭＳ ＝ １０， 维度 Ｄ ＝ １００ 时， 方 法 １ 得 到 最 优 解 的 概 率 为 ＨＭＳ － １ ＨＭＳ æ è ç ö ø ÷ Ｄ ＝ ２．６５６ １×１０ －５ ，利用方法 ２ 得到最优 解的概率为 （１ ／ Ｄ）·（（ＨＭＳ － １） ／ ＨＭＳ） ＝ ０．００９， 显然，方法 ２ 具有更高的成功率。 图 １ 给出 ２ 种方 法的成功率变化曲线。 图 １ ２ 种方法在维数不同时的更新成功率曲线图 Ｆｉｇ．１ Ｔｈｅ ｕｐｄａｔｅ⁃ｓｕｃｃｅｓｓ ｒａｔｅ ｃｕｒｖｅ ｏｆ ｔｗｏ ｍｅｔｈｏｄｓ ｏｎ ｄｉｆｆｅｒｅｎｔ ｄｉｍｅｎｓｉｏａｌｉｔｉｅｓ 图 １ 可以看出，在 ＨＭＳ 相同的情况下，随着维 数 Ｄ 的增加，方法 １ 的成功率急剧下降，而方法 ２ 下 降幅度很小。 在问题的维数较低时，方法 １ 的更新 成功率高于方法 ２，但当维数 Ｄ＞４０ 时，方法 ２ 的更 新成功率高于方法 １。 由上例可知，对于一个高维优化问题，利用方法 １ 难以驱动算法获得高精度的最优解。 如果借鉴方 法 ２ 的思想进行优化，就有可能取得较好的优化效 果。 因此，本文提出一种基于动态减少调整维数的和 声优化策略。 该策略首先选取和声记忆库中最差和 声向量作为优化目标，然后，通过对最差和声向量的 不断调整，使其达到最优解。 在优化刚开始时，对最 差和声向量进行较多维数的扰动，使得算法具有较强 的空间探索能力，随着优化的进行，逐步降低扰动概 率，仅仅在较少维上进行优化调整，使得优化调整具 有更高的成功率，从而获得高精度的全局最优解。 ２．２ 基于动态降维调整的和声搜索算法 本文提出的基于动态降维调整策略的和声搜索 算 法 流 程 请 见 图 ２。 本 文 算 法 中， 调 整 概 率 ＴＰ ＝ ＴＰ ｍａｘ － （ＴＰ ｍａｘ － ＴＰ ｍｉｎ ）·（ｔ ／ Ｔｍａｘ） ２ 随着迭代次 数的增加逐步减小（如图 ３），其中， ＴＰ ｍａｘ 和 ＴＰ ｍｉｎ 分 别为最大调整概率值和最小调整概率值。 在算法优化开始时，以较大的扰动调整概率 ＴＰｍａｘ 进行优化，随着优化进行，调整概率 ＴＰ 逐渐减 小，开始进行局部微调。 但是，为了防止优化调整概 率太小，可能导致所有维都得不到调整，因此，需要从 第 ２ 期 拓守恒，等：动态调整策略改进的和声搜索算法 ·３０９·
310. 智能系统学报 第10卷 1~D中随机选取一维J=ceil(rand×D),使其必须得 0.50P 到调整，避免了算法“空转”。这样调整的好处是，迭 0.40 代初期，需要较强的全局扰动能力，此时，可以在优化 目标向量x"上加大扰动力度，增强种群多样性，使 要0叫 其具有较强的全局探索能力，随着优化的进行，到了 0.20 后期，多数个体可能已经聚集在了全局最优解附近， 0.1 10 此时，开始加强局部最优解的探索，为了保证较高的 012345678910 更新成功率，对优化目标向量x",选择较少的维数 迭代次数 进行优化调整，从而，增强算法的求解精度。 图3调整概率TP变化曲线 Fig.3 Adjustment curve of TP 开始○ TP=TPk一(TPat-TPm)×(t/T)2 3 仿真实验 从和声记忆库HM选择最差和声作为优化目标：x"=x© 为了评估本文算法提出的动态降维调整策略的 i=1 性能，选取了6个复杂的Benchmark测试函数进行仿 J=ceil(randxD) 真测试[6]（见表1），16个函数除了F,和F。是单峰 函数之外，其余函数都是复杂的高维多峰值函数。 rand<TP Y 分别将HS,IHS、ITHS、EHS和GHS利用本文算 利用和声搜索算法在第维上产生一个新值作为x 法思想进行改进，将其改进后分别称为HS2,HS2, ITHS2,EHS2和GHS2,并将其与改进前的算法进行 i≤D 比较。检验改进后的算法是否比改进前的算法能够 N 获得更高精度的解，同时，检验其运行成本（运行时 执行更新操作 间)是否降低。 1+I 3.1实验环境和算法参数设置 K-Tmax 本文实验采用戴尔工作站T7500 Inter(R)Xe N on(R)CPUE560@2.1GHz,8.0GB内存，Windows End Server20O3 Server操作系统，所有测试程序采用Mat- 图2基于动态降维调整的和声搜索算法流程图 labR2009a编写。10种算法参数设置如表2。 Fig.2 The flow chart of HS algorithm based on dy- namic dimensionality reduction strategy 表16个Benchmark函数(F,~F。) Table 1 Six Benchmark functions 函数名称 Benchmark函数表达式 搜索范围 参数值 F Ackley x"=(0.0,…,0) Function F(x)=-20e-2-+20-e [-15,30]0 F(x)=0 F2Griewank x°=(0,0，…，0) [-600,600]P Function F2(x'）=0 -1 F,(x)=sin2(my)+】 F;Levy 【-1)0+10im(,+)]+ x”=(1,1,…,1) (-1)2(1+10sin2(2myn) [-10,10]0 Function F(x)=0 y=1+(x-1)/4,i=1,2,…,D FMichalewics 乞ms)en(xya)产m:10 n=5 F(x)=- [-10,π]P Function F.(x)=-4.687658 F;Rastrigin x=(0,0,…,0) F,(x)=10D+ -10a(2》 [-5.12,5.12] Function F(x)=0 x·=(420.9687, F.Schwefel F(x）=418.9829D+ 2.26 Function 乞isin(V小国T) [-512,512]P420.9687,…,420.9687) F。(x)=0
１～Ｄ 中随机选取一维 Ｊ ＝ ｃｅｉｌ（ｒａｎｄ×Ｄ） ，使其必须得 到调整，避免了算法“空转”。 这样调整的好处是，迭 代初期，需要较强的全局扰动能力，此时，可以在优化 目标向量 ｘ ｎｅｗ 上加大扰动力度，增强种群多样性，使 其具有较强的全局探索能力，随着优化的进行，到了 后期，多数个体可能已经聚集在了全局最优解附近， 此时，开始加强局部最优解的探索，为了保证较高的 更新成功率，对优化目标向量 ｘ ｎｅｗ ，选择较少的维数 进行优化调整，从而，增强算法的求解精度。 图 ２ 基于动态降维调整的和声搜索算法流程图 Ｆｉｇ．２ Ｔｈｅ ｆｌｏｗ ｃｈａｒｔ ｏｆ ＨＳ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｙ⁃ ｎａｍｉｃ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ ｓｔｒａｔｅｇｙ 图 ３ 调整概率 ＴＰ 变化曲线 Ｆｉｇ．３ Ａｄｊｕｓｔｍｅｎｔ ｃｕｒｖｅ ｏｆ ＴＰ ３ 仿真实验 为了评估本文算法提出的动态降维调整策略的 性能，选取了 ６ 个复杂的 Ｂｅｎｃｈｍａｒｋ 测试函数进行仿 真测试［ ３５⁃３８ ］ （见表 １），１６ 个函数除了 Ｆ７ 和 Ｆ８ 是单峰 函数之外，其余函数都是复杂的高维多峰值函数。 分别将 ＨＳ、ＩＨＳ、ＩＴＨＳ、ＥＨＳ 和 ＧＨＳ 利用本文算 法思想进行改进，将其改进后分别称为 ＨＳ２ ，ＩＨＳ２ ， ＩＴＨＳ２ ，ＥＨＳ２ 和 ＧＨＳ２ ，并将其与改进前的算法进行 比较。 检验改进后的算法是否比改进前的算法能够 获得更高精度的解，同时，检验其运行成本（运行时 间）是否降低。 ３．１ 实验环境和算法参数设置 本文实验采用戴尔工作站 Ｔ７５００ Ｉｎｔｅｒ（Ｒ） Ｘｅ⁃ ｏｎ（Ｒ） ＣＰＵ Ｅ５６０＠ ２．１ ＧＨｚ， ８．０ ＧＢ 内存，Ｗｉｎｄｏｗｓ Ｓｅｒｖｅｒ２００３ Ｓｅｒｖｅｒ 操作系统，所有测试程序采用 Ｍａｔ⁃ ｌａｂ Ｒ２００９ａ 编写。 １０ 种算法参数设置如表 ２。 表 １ ６ 个 Ｂｅｎｃｈｍａｒｋ 函数（ Ｆ１ ～ Ｆ６ ） Ｔａｂｌｅ １ Ｓｉｘ Ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ 函数名称 Ｂｅｎｃｈｍａｒｋ 函数表达式 搜索范围 参数值 Ｆ １Ａｃｋｌｅｙ Ｆｕｎｃｔｉｏｎ Ｆ１（ｘ） ＝ － ２０ｅ １ ５ １ Ｄ ∑ Ｄ ｉ ＝ １ ｘ ２ ｉ － ｅ １ Ｄ ∑ Ｄ ｉ ＝ １ ｃｏｓ（２πｘ ｉ ） ＋ ２０ － ｅ ［ － １５，３０］ Ｄ ｘ ∗ ＝ （０，０，…，０） Ｆ１（ｘ ∗ ） ＝ ０ Ｆ ２ Ｇｒｉｅｗａｎｋ Ｆｕｎｃｔｉｏｎ Ｆ２ ＝ １ ４ ０００∑ Ｄ ｉ ＝ １ ｘ ２ ｉ － ∏ Ｄ ｉ ＝ １ （ｃｏｓ（ ｘｉ ｉ ）） ＋ １ ［ － ６００，６００］ Ｄ ｘ ∗ ＝ （０，０，…，０） Ｆ２（ｘ ∗ ） ＝ ０ Ｆ ３Ｌｅｖｙ Ｆｕｎｃｔｉｏｎ Ｆ３（ｘ） ＝ ｓｉｎ ２ （πｙ１ ） ＋ ∑ Ｄ－１ ｉ ＝ １ （ｙｉ － １） ２ １ ＋ １０ ｓｉｎ ２ （πｙｉ [ ( ＋ １） ) ] ＋ （ ｙ Ｄ － １）２ １ ＋ １０ ｓｉｎ ２ （２πｙ ( Ｄ ） ) ｙｉ ＝ １ ＋ （ｘｉ － １） ／ ４，ｉ ＝ １，２，…，Ｄ ［ － １０，１０］ Ｄ ｘ ∗ ＝ （１，１，…，１） Ｆ３（ｘ ∗ ） ＝ ０ Ｆ ４Ｍｉｃｈａｌｅｗｉｃｓ Ｆｕｎｃｔｉｏｎ Ｆ４（ｘ） ＝ － ∑ Ｄ ｉ ＝ １ ｓｉｎ（ｘｉ） ｓｉｎ（ｉｘｉ ２ ( ／ π） ) ２ｍ ；ｍ ＝ １０ ［ － １０，π］ Ｄ ｎ ＝ ５ Ｆ４（ｘ ∗ ） ＝ － ４．６８７ ６５８ Ｆ ５Ｒａｓｔｒｉｇｉｎ Ｆｕｎｃｔｉｏｎ Ｆ５（ｘ） ＝ １０Ｄ ＋ ∑ Ｄ ｉ ＝ １ ｘｉ ２ － １０ｃｏｓ（２πｘ ( ｉ） ) ［ － ５．１２，５．１２］ Ｄ ｘ ∗ ＝ （０，０，…，０） Ｆ５（ｘ ∗ ） ＝ ０ Ｆ ６ Ｓｃｈｗｅｆｅｌ ２．２６ Ｆｕｎｃｔｉｏｎ Ｆ６（ｘ） ＝ ４１８．９８２ ９Ｄ ＋ ∑ Ｄ ｉ ＝ １ ｘ ２ ｉ ｓｉｎ（ ｘｉ ） ［ － ５１２，５１２］ Ｄ ｘ ∗ ＝ （４２０．９６８ ７， ４２０．９６８ ７，…，４２０．９６８ ７） Ｆ６（ｘ ∗ ） ＝ ０ ·３１０· 智 能 系 统 学 报 第 １０ 卷
第2期 拓守恒，等：动态调整策略改进的和声搜索算法 .311. 表2参数设置 Table 2 Parameters setting 算法HMS HMCR PAR BW TP HS100.99 0.33 (xU-xL)/2000 HS2100.99 0.33 (xU-xL)/2000 TP=0.6,TP=5/D BWmax=(xU-xL)/20 IHS 10 0.99 PARmax=0.99,PARmin=0.1 1 BWmin=(xU-xL)/(le+8) BWmax=(xU-xL)/20 IHS, 100.99 PARmax=0.99.PARmin=0.1 TP=0.6.TPn=5/D BWmin=(xU-xL)/(1e+8) GHS 10 0.90 PARmax=0.99.PARmin=0.01 GHS, 100.90 PARmax=0.99,PARmin=0.01 / TP=0.6,TPn=5/D EHS 50 0.99 0.33 1 EHS,50 0.99 0.33 TP=0.6,TP=5/D THS100.99 PARmax=1,PARmin=0 THS2100.99 PARmax=1,PARmin=0 TPn=0.6,TP=5/D 表3在D=500时，5种和声算法及其利用本文算法改进的5种和声算法对6个测试函数的运行结果比较 Table 3 Results comparison between five HS algorithms and five improved HS algorithms F2 Fa 算法 Best Mean Std Runtime Best Mean Std Runtime Best Mean Std Runtime HS 2.34×10°2.50x1006.67×1022.52×1026.32×1016.75×1012.39x1023.06×1028.04×1029.70x1021.80×1021.61×103 HS21.39x1011.61×10-11.14×10-21.89×1024.20x10-15.31×1018.25×10-22.48×1021.09×10-41.24×1047.07E-061.53x103 GHs1.57×1031.64×1012.75×10-12.67×1021.88×1032.11×1031.49×1023.45×1027.11×1027.96×1024.40×109.03×102 GHS21.24×1024.29x1022.86×1022.42×1029.85×10-32.83×1012.72×1013.06×1021.30x1038.25x10-39.63×1038.86×102 Hs6.57×10-11.10x1001.74×10-13.79×1025.92×10-27.60x10-28.85×10-34.64x1025.27×10-21.05x10-14.09x10-21.24x103 IHS2 8.71×10-78.81×10-76.81×10-93.16×1022.69×10-13.70x10-41.65×10-34.00x1021.17×10121.19x10-22.75×10-49.71×102 THS7.90x1032.95×1021.18×10-23.17×1026.41×1031.92x10-19.97×10-23.87×1021.35×10°34.75×1032.16×10-31.70x103 THS21.50x10-33.49x10-.75×10-12.16×1026.66×10-167.72×10-165.67E-172.62x1021.50x10-321.50x10-20.00x10°1.62×103 EHS 4.55×1004.70x1008.66×10-25.02×1022.12×102.47×1011.58×1005.75×1021.11×1021.26×1027.58×10°2.04×103 EHS2 2.71×10~132.21×1056.85×1054.32×1027.77×10-61.26×1055.38×1055.17×1023.54E-151.25×1073.96×1071.24×103 F4 F6 算法 Best Mean Std Runtime Best Mean Std Runtime Best Mean Std Runtime HS -2.08×102-2.01×1024.92×1006.48×1021.10x1021.26×1021.07×1013.21×1024.57×1014.95×1012.42×10°2.98×102 HS2 -4.28×102-4.26×1022.03×1005.25×1021.13×1021.28×1028.39×1042.03×1026.99×1028.04×1026.73×1032.15×102 GHs-2.26×102-2.22×1022.90×1005.22×1021.61×1031.90×1031.19×1023.50x1023.35×1043.81×102.16x1033.47×102 GHS2-2.65x102-2.62×1021.55×1004.98x1028.81x10-41.10x10-11.69x10-13.14×1021.54×10-21.26x10°1.51×10°3.23x102 IHS -4.55x102-4.53×1022.43×1006.36×1021.02x1021.17×1025.45×10°4.99×1026.66×10°4.63×103.27×104.56×102 IHS2 -4.98×102-4.97×1021.33×10-15.83×1021.71×1021.20×10-11.05×1014.16×1021.37×1091.47×1096.97×10-113.83×102 THs-4.51×102-4.42×1023.69×1005.96×1024.35×10-35.94×10-25.25×10-24.38×1026.79×1021.39×1035.00×1025.66×102 THS2-4.98×102-4.98×1023.11×1014.89×1021.18×1014.27×1013.71×10112.97×1021.16×1091.39x1092.85×10103.98×102 EHS -1.63×102-1.58×1021.99×10°8.64×1024.43×1034.52×1034.70×106.68×1021.27×1031.32×1031.78×1036.48×102 EHS2-4.43×102-4.41×1021.38×10°8.10×1023.84×1024.52×1022.89x105.90×1022.36×1032.61×1031.33×1035.38×102 3.2实验结果与分析 次运行的最优目标函数适应值的平均值Mean,最优 为了保证算法测试的公平性，改进前的算法和值Bst,20次最优解的标准差(Std)和平均运行时 改进后的算法取相同的初始和声记忆库HM,每个算间(un time)。设置维数D=500,运行结果见表3。 法中随机数设置rand('twister',5489),每个算法程表中将HS、IHS、THS、EHs和GHS分别与HS2、 序独立运行20次，记录每次运行的过程，统计出20HS2、THS,、EHS2和GHS2进行比较，较好结果的用
表 ２ 参数设置 Ｔａｂｌｅ ２ Ｐａｒａｍｅｔｅｒｓ ｓｅｔｔｉｎｇ 算法 ＨＭＳ ＨＭＣＲ ＰＡＲ ＢＷ ＴＰ ＨＳ １０ ０．９９ ０．３３ （ｘＵ－ｘＬ） ／ ２ ０００ ／ ＨＳ２ １０ ０．９９ ０．３３ （ｘＵ－ｘＬ） ／ ２ ０００ ＴＰｍａｘ ＝ ０．６，ＴＰｍｉｎ ＝ ５ ／ Ｄ ＩＨＳ １０ ０．９９ ＰＡＲｍａｘ ＝ ０．９９， ＰＡＲｍｉｎ ＝ ０．１ ＢＷｍａｘ ＝ （ｘＵ－ｘＬ） ／ ２０ ＢＷｍｉｎ ＝ （ｘＵ－ｘＬ） ／ （１ｅ＋８） ／ ＩＨＳ２ １０ ０．９９ ＰＡＲｍａｘ ＝ ０．９９， ＰＡＲｍｉｎ ＝ ０．１ ＢＷｍａｘ ＝ （ｘＵ－ｘＬ） ／ ２０ ＢＷｍｉｎ ＝ （ｘＵ－ｘＬ） ／ （１ｅ＋８） ＴＰｍａｘ ＝ ０．６，ＴＰｍｉｎ ＝ ５ ／ Ｄ ＧＨＳ １０ ０．９０ ＰＡＲｍａｘ ＝ ０．９９， ＰＡＲｍｉｎ ＝ ０．０１ ／ ／ ＧＨＳ２ １０ ０．９０ ＰＡＲｍａｘ ＝ ０．９９， ＰＡＲｍｉｎ ＝ ０．０１ ／ ＴＰｍａｘ ＝ ０．６，ＴＰｍｉｎ ＝ ５ ／ Ｄ ＥＨＳ ５０ ０．９９ ０．３３ ／ ／ ＥＨＳ２ ５０ ０．９９ ０．３３ ／ ＴＰｍａｘ ＝ ０．６，ＴＰｍｉｎ ＝ ５ ／ Ｄ ＩＴＨＳ １０ ０．９９ ＰＡＲｍａｘ ＝ １， ＰＡＲｍｉｎ ＝ ０ ／ ／ ＩＴＨＳ２ １０ ０．９９ ＰＡＲｍａｘ ＝ １， ＰＡＲｍｉｎ ＝ ０ ／ ＴＰｍｉｎ ＝ ０．６，ＴＰｍｉｎ ＝ ５ ／ Ｄ 表 ３ 在 Ｄ ＝ ５００ 时， ５ 种和声算法及其利用本文算法改进的 ５ 种和声算法对 ６ 个测试函数的运行结果比较 Ｔａｂｌｅ ３ Ｒｅｓｕｌｔｓ ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ ｆｉｖｅ ＨＳ ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｆｉｖｅ ｉｍｐｒｏｖｅｄ ＨＳ ａｌｇｏｒｉｔｈｍｓ 算法 Ｆ １ Ｂｅｓｔ Ｍｅａｎ Ｓｔｄ Ｒｕｎｔｉｍｅ Ｆ ２ Ｂｅｓｔ Ｍｅａｎ Ｓｔｄ Ｒｕｎｔｉｍｅ Ｆ ３ Ｂｅｓｔ Ｍｅａｎ Ｓｔｄ Ｒｕｎｔｉｍｅ ＨＳ ２．３４×１０ ０ ２．５０×１０ ０ ６．６７×１０ －２ ２．５２×１０ ２ ６．３２×１０ －１ ６．７５×１０ －１ ２．３９×１０ －２ ３．０６×１０ ２ ８．０４×１０ －２ ９．７０×１０ －２ １．８０×１０ －２ １．６１×１０ ３ ＨＳ２ １．３９×１０ －１ １．６１×１０ －１ １．１４×１０ －２ １．８９×１０ ２ ４．２０×１０ －１ ５．３１×１０ －１ ８．２５×１０ －２ ２．４８×１０ ２ １．０９×１０ －４ １．２４×１０ －４ ７．０７Ｅ－０６ １．５３×１０ ３ ＧＨＳ １．５７×１０ １ １．６４×１０ １ ２．７５×１０ －１ ２．６７×１０ ２ １．８８×１０ ３ ２．１１×１０ ３ １．４９×１０ ２ ３．４５×１０ ２ ７．１１×１０ ２ ７．９６×１０ ２ ４．４０×１０ １ ９．０３×１０ ２ ＧＨＳ２ １．２４×１０ －２ ４．２９×１０ －２ ２．８６×１０ －２ ２．４２×１０ ２ ９．８５×１０ －３ ２．８３×１０ －１ ２．７２×１０ －１ ３．０６×１０ ２ １．３０×１０ －３ ８．２５×１０ －３ ９．６３×１０ －３ ８．８６×１０ ２ ＩＨＳ ６．５７×１０ －１ １．１０×１０ ０ １．７４×１０ －１ ３．７９×１０ ２ ５．９２×１０ －２ ７．６０×１０ －２ ８．８５×１０ －３ ４．６４×１０ ２ ５．２７×１０ －２ １．０５×１０ －１ ４．０９×１０ －２ １．２４×１０ ３ ＩＨＳ２ ８．７１×１０ －７ ８．８１×１０ －７ ６．８１×１０ －９ ３．１６×１０ ２ ２．６９×１０ －１１ ３．７０×１０ －４ １．６５×１０ －３ ４．００×１０ ２ １．１７×１０ －１２ １．１９×１０ －１２ ２．７５×１０ －１４ ９．７１×１０ ２ ＩＴＨＳ ７．９０×１０ －３ ２．９５×１０ －２ １．１８×１０ －２ ３．１７×１０ ２ ６．４１×１０ －３ １．９２×１０ －１ ９．９７×１０ －２ ３．８７×１０ ２ １．３５×１０ －３ ４．７５×１０ －３ ２．１６×１０ －３ １．７０×１０ ３ ＩＴＨＳ２ １．５０×１０ －１３ ３．４９×１０ －１３ １．７５×１０ －１３ ２．１６×１０ ２ ６．６６×１０ －１６ ７．７２×１０ －１６ ５．６７Ｅ－１７ ２．６２×１０ ２ １．５０×１０ －３２ １．５０×１０ －３２ ０．００×１０ ０ １．６２×１０ ３ ＥＨＳ ４．５５×１０ ０ ４．７０×１０ ０ ８．６６×１０ －２ ５．０２×１０ ２ ２．１２×１０ １ ２．４７×１０ １ １．５８×１０ ０ ５．７５×１０ ２ １．１１×１０ ２ １．２６×１０ ２ ７．５８×１０ ０ ２．０４×１０ ３ ＥＨＳ２ ２．７１×１０ －１３ ２．２１×１０ －５ ６．８５×１０ －５ ４．３２×１０ ２ ７．７７×１０ －１６ １．２６×１０ －５ ５．３８×１０ －５ ５．１７×１０ ２ ３．５４Ｅ－１５ １．２５×１０ －７ ３．９６×１０ －７ １．２４×１０ ３ 算法 Ｆ ４ Ｂｅｓｔ Ｍｅａｎ Ｓｔｄ Ｒｕｎｔｉｍｅ Ｆ ５ Ｂｅｓｔ Ｍｅａｎ Ｓｔｄ Ｒｕｎｔｉｍｅ Ｆ ６ Ｂｅｓｔ Ｍｅａｎ Ｓｔｄ Ｒｕｎｔｉｍｅ ＨＳ －２．０８×１０ ２ －２．０１×１０ ２ ４．９２×１０ ０ ６．４８×１０ ２ １．１０×１０ ２ １．２６×１０ ２ １．０７×１０ １ ３．２１×１０ ２ ４．５７×１０ １ ４．９５×１０ １ ２．４２×１０ ０ ２．９８×１０ ２ ＨＳ２ －４．２８×１０ ２ －４．２６×１０ ２ ２．０３×１０ ０ ５．２５×１０ ２ １．１３×１０ －２ １．２８×１０ －２ ８．３９×１０ －４ ２．０３×１０ ２ ６．９９×１０ －２ ８．０４×１０ －２ ６．７３×１０ －３ ２．１５×１０ ２ ＧＨＳ －２．２６×１０ ２ －２．２２×１０ ２ ２．９０×１０ ０ ５．２２×１０ ２ １．６１×１０ ３ １．９０×１０ ３ １．１９×１０ ２ ３．５０×１０ ２ ３．３５×１０ ４ ３．８１×１０ ４ ２．１６×１０ ３ ３．４７×１０ ２ ＧＨＳ２ －２．６５×１０ ２ －２．６２×１０ ２ １．５５×１０ ０ ４．９８×１０ ２ ８．８１×１０ －４ １．１０×１０ －１ １．６９×１０ －１ ３．１４×１０ ２ １．５４×１０ －２ １．２６×１０ ０ １．５１×１０ ０ ３．２３×１０ ２ ＩＨＳ －４．５５×１０ ２ －４．５３×１０ ２ ２．４３×１０ ０ ６．３６×１０ ２ １．０２×１０ ２ １．１７×１０ ２ ５．４５×１０ ０ ４．９９×１０ ２ ６．６６×１０ ０ ４．６３×１０ １ ３．２７×１０ １ ４．５６×１０ ２ ＩＨＳ２ －４．９８×１０ ２ －４．９７×１０ ２ １．３３×１０ －１ ５．８３×１０ ２ １．７１×１０ －２ １．２０×１０ －１ １．０５×１０ －１ ４．１６×１０ ２ １．３７×１０ －９ １．４７×１０ －９ ６．９７×１０ －１１ ３．８３×１０ ２ ＩＴＨＳ －４．５１×１０ ２ －４．４２×１０ ２ ３．６９×１０ ０ ５．９６×１０ ２ ４．３５×１０ －３ ５．９４×１０ －２ ５．２５×１０ －２ ４．３８×１０ ２ ６．７９×１０ ２ １．３９×１０ ３ ５．００×１０ ２ ５．６６×１０ ２ ＩＴＨＳ２ －４．９８×１０ ２ －４．９８×１０ ２ ３．１１×１０ －１ ４．８９×１０ ２ １．１８×１０ －１１ ４．２７×１０ －１１ ３．７１×１０ －１１ ２．９７×１０ ２ １．１６×１０ －９ １．３９×１０ －９ ２．８５×１０ －１０ ３．９８×１０ ２ ＥＨＳ －１．６３×１０ ２ －１．５８×１０ ２ １．９９×１０ ０ ８．６４×１０ ２ ４．４３×１０ ３ ４．５２×１０ ３ ４．７０×１０ １ ６．６８×１０ ２ １．２７×１０ ５ １．３２×１０ ５ １．７８×１０ ３ ６．４８×１０ ２ ＥＨＳ２ －４．４３×１０ ２ －４．４１×１０ ２ １．３８×１０ ０ ８．１０×１０ ２ ３．８４×１０ ２ ４．５２×１０ ２ ２．８９×１０ １ ５．９０×１０ ２ ２．３６×１０ ４ ２．６１×１０ ４ １．３３×１０ ３ ５．３８×１０ ２ ３．２ 实验结果与分析 为了保证算法测试的公平性，改进前的算法和 改进后的算法取相同的初始和声记忆库 ＨＭ，每个算 法中随机数设置 ｒａｎｄ（′ｔｗｉｓｔｅｒ′，５ ４８９），每个算法程 序独立运行 ２０ 次，记录每次运行的过程，统计出 ２０ 次运行的最优目标函数适应值的平均值 Ｍｅａｎ，最优 值 Ｂｅｓｔ， ２０ 次最优解的标准差（ Ｓｔｄ）和平均运行时 间（ｒｕｎ ｔｉｍｅ）。 设置维数 Ｄ ＝ ５００，运行结果见表 ３。 表中将 ＨＳ、 ＩＨＳ、 ＩＴＨＳ、 ＥＨＳ 和 ＧＨＳ 分别与 ＨＳ２ 、 ＩＨＳ２ 、ＩＴＨＳ２ 、ＥＨＳ２ 和 ＧＨＳ２ 进行比较，较好结果的用 第 ２ 期 拓守恒，等：动态调整策略改进的和声搜索算法 ·３１１·