和声搜索算法

改进和声搜索算法生成组合测试用例策略研究组合测试方法能够在确保检错能力的前提下,使用较小规模的测试用例集对系统中由于复杂因素间的相互作用而导致的软件故障进行检测。

但是,测试用例集的构造是个NP完全问题。

现有的方法多基于贪心算法或者启发式算法生成组合测试用例,并通过对这些算法的改进以改善测试用例的生成效率和测试用例集的规模。

在实际项目中,待测的软件系统通常由多个复杂的因素相互交集和约束组合而成,因此,常规的组合测试方法也面临着挑战。

为了使用较少规模的测试用例集对系统参数间的交互作用进行全面地测试,研究者提出了可变强度的t-way组合测试方法。

作为一种科学、有效的测试方法,可变强度的t-way组合测试技术成为了学者研究的关键问题之一。

本文系统回顾和总结了现有的组合测试用例生成技术,针对组合测试模型中参数的约束和可变力度的交互问题进行了深入研究,提出了两种基于和声搜索算法(Harmony Search Algorithm,HSA)改进的组合测试用例集构造策略。

具体贡献可以概括为以下三个方面:(1)通过对和声搜索算法中初始和声库的生成方式进行改进,提出了多和声库竞争的和声搜索算法(Multi-HM Competitive Harmony Search Algorithm,MHCHS)生成组合测试用例策略。

在标准的HSA中新解的生成直接受初始和声库(Harmony Memory,HM)的影响。

本文采用多个小规模HM代替一个大规模的HM进行独立更新,并受自然界中种群间相互合作与竞争达到共同发展的思想启发,将较优的新解更新到多个小规模和声库中进一步改善HM中解的质量来增强算法的寻优能力。

最后详细分析了算法中参数初始值设定对生成组合测试用例集规模的影响,得出该配置下最好的参数值选择。

(2)通过对和声搜索算法中参数的自适应调整,提出了带灾变的蝙蝠-和声搜索算法(Catastrophe Strategy Bat-Harmony Search Algorithm,CSBHS)生成组合测试用例策略。

量来 源于 ＨＭ 中的解 的分 量 的概率 大小 ， 而新解 分量 来源 于可行 域 的概率 为 １ 一ＨＭＣ Ｒ。ｂ ｗ是 带宽值 ， Ｐ Ｒ是音 节调 节率 （ ｉｈＡ ｊｓｎ ａｅ ， Ａ Ｐｔ ｄｕｔ ｇＲ ｔ）即对来 源 于 ＨＭ 中的解 的分量 进行微 调 的概 率 大小 。 ｃ ｉ
基金项 目： 国家 自然科学基金资助项 目（０７ １８ ６ ５４ ７ ） ６ ６ ４ ０ ， ０ ７ ０ ５ 作者简介 ： 军（９ ９ ， ， 赵鹏 １ ７ 一）男 陕西渭南人 ， 洛学 院数学 与计算科学 系 ， 师 ， 安电子科技 大学理学 院硕士研 商 讲 西
究生。
赵鹏军： 和声搜索算法参数的均匀设计
一 ，
，
其 中Ｘ 是优化问
）
题的第 ｉ 个解 ， （ 是其对应 的函数值 ， ＭＳ为和声记忆库大Ａ （ ａ ｎ ｍ ｒ Ｓｚ） 即保存在 ｆ ｘ） Ｈ ￣Ｈ ｒ ｙＭｅ ｏ ｉ ， ｍｏ ｙ ｅ
ｆ ∈｛ ，；…， ｆ ，
【 Ｘ ￡ ｌ ｂｊ ∈ ａ ，
中图分类号 ：］３ １ ６ １Ｐ ０ ． 文献标识码 ： Ａ
１ 引 言
２０ 年 ，ｅｍ等人通过类 比音乐创作和优化问题的相似性而提出了一种新 的智能优化算法—— ０１ Ｇ ｅ 和声搜索（ ａｍ ｎ ｅｒ ， Ｓ 算法［ 。与其他进化算法相 比， Ｓ算法机理简单， Ｈ ｒ ｏｙＳａｃ Ｈ ） ｈ 川 Ｈ 易于理解 ， 解的构
ｒ ＜Ｈ Ｃ ｌ ＭＲ
ｌ ＨＭＣ ≥ Ｒ
…
② 对选 自 ＨＭ 中的解 的分量 进 行微 调 ： ， ｆ ± ｂ ・ ２ ｒ ｚ ｗ ｒ ＜
， ’ 。
一１ ｚ ，
ｒ≥ＰＲ ３ Ａ
Ｌ ｚ

ｏ ａ ｍｏ ｙ ｓ ａ ｃ ｇｏ ｔｍ ｄ ｔ ｅ ｂ ｓｃ ｉ ｅ ｅｇ ｖ ｎ Ｗ ｅ ｇ ｖ ｅ ｂ ｉ ｔｐ ｎ ｒ ｃ ｓｅ ｆｈ ｒ ｏ ｙ ｓ ａｃ ｆｈ ｒ ｎ ｅ ｒ ｈ ａ ｒ ｈ ａ ａ ｉ ｄ ａ ａ ｉ ｅ ． ｌ ｉ ｎ ｈ ｒ ｉ ｅ ｔ ａ ｃ ｓ ｓ ａ ｄ ｐ ｏ ｅ ｓ ｓｏ ａｍ ｎ ｅ ｒ ｈ ｈ ｓ ｅ
计 算 机 系 统 应 用
ｈ ｐ／ ｗ ＣＳ ．ｒ． ｔ ：ｗ ｗ． － ｏｇ ａ ７ 期
和声搜索算法研究进．① 屣
雍龙泉
（ 陕西理工学院 数学系，汉中 ７３０） ２０ １
摘
要：和 声搜索算法是一种新兴 的智能优化算法 ，通 过反复调整记 忆库中的解变量 ，使 函数值 随着迭代次数
（ ａ ｎ ｍｏ ｏ ｓ ｅ ｎ ｔ Ｈ Ｈ ｒ ｙｍｅ ｒ ｃ ｎｉ ｒ ｇｒ ｅ ＭＣ ）和微调概 ｍｏ ｙ ｄｉ ａ， Ｒ
ｒｎ，如果 ｒｎ ＜ ＭＣ ， ａｄ ａｄ Ｈ Ｒ则新解在 ＨＭ 内随机搜索得 到：否则在和 声记忆库外 ， 变量 可能 的值域 内搜索取 值 。 以微调概率 Ｐ Ｒ对取 自Ｈ 内的新解进行局部 再 Ａ Ｍ
ｄ ｆｅ ｅ ｃ ｅｗｅ ｎ ｈ ｒ ｎ ｅ ｒｈ ａｇ ｒｔ ｍ ｄ ｇ ｎ ｔｃ ａｇ ｒｔ ｍ ｓｃ ｍｐ ｅ ｉ ｒ ｎ ｅ ｂ ｔ ｅ ａｍｏ ｙ ｓ ａ ｃ ｏ ｉｈ ａ ｅ ｅ ｏ ｉｈ ｉ ｏ ａ ｄ．Ｆ ｒｈ ｒ ｒ ，ｔｅ ａ ｐｉ ａｉ ｎ ｎ ｌ ｎ ｉ ｌ ｒ ｕ ｔ ｅ ｍｏ ｅ ｈ ｐ ｌｃ ｔｏ ｓ ａ ｄ
Ａｄ ａ ｅ ｎ Ｈａ ｍ ｏ ｙ Ｓｅ ｒ ｈ Ａｌ ｏ ｉｈｍ ｖ ｎｃ ｓｉ ｒ ｎ ａ ｃ ｇ ｒｔ
Ｙ ＮＧＬ ｎ — ｕ ｎ Ｏ ｏ ｇＱ ａ

和声搜索算法参数研究摘要：合适的参数能够提高和声搜索算法的性能和收敛速度。

详细介绍了和声搜索算法的流程，并总结了每个参数对算法的作用及参数变化对算法的影响。

针对如何选取参数才能达到提高算法性能的目的，通过参数调整的方法，利用4个基准函数对算法进行仿真实验，实验结果表明，较高的HMCR、PAR和HMS取较小的值能使函数得到较优值。

关键词：和声搜索算法；基准函数；参数调整；仿真实验0引言在音乐创作过程中，乐师们凭借自己的记忆，通过反复调整乐队中各乐器的音调，最终达到一个美妙和声的过程。

Geem[1]等人受这一现象启发，提出一种新型的群智能优化算法——和声搜索算法，已经在函数优化[2，3]和调度[4-6]等问题中表现出了优势。

此算法结构简单，参数少，通过对参数的分析及调整，利用多维函数进行仿真实验，最终找出最优参数组合。

1 和声搜索算法（Harmony Search，HS）HS是Geem等通过类比音乐和最优化问题的相似性而提出的一种现代启发式群智能算法。

将乐器的和声Ri（i=1，2，…n）类比于函数第i分量的解向量Xi（i=1，2，…，n），评价对应解的函数值。

HMS为和声记忆库的大小，即和声库中解向量的个数。

和声库HM=[X1，X2…，XHMS]，其中，每个解向量由n分量组成Xi=[xi1，xi2，…，xin]，i=1，2，…HMSHMCR是产生新解时从和声库中保留解分量的概率；PAR则为记忆扰动概率。

1.1初始化和声库为了保证初始解的质量和多样性，并保证优化结果具有一定的代表性，初始种群在函数定义域内应均匀分布，产生方式如下：1.2新解产生（1）和声库的学习。

（2）候选解分量微调。

与其它算法不同，和声搜索算法候选解产生原理是多个个体合作完成，并通过微调机制增加算法局部寻优能力。

2参数设计2.1HMS设计HMS是影响算法执行性能和优化效率的重要因素之一，决定了算法的全局搜索能力。

若值太小则不能提供足够的采样点从而导致算法优化性能较差；反之，取值越大，搜索全局最优解的能力越强，但是其值也不能过大，太大值反而会增加计算量而导致收敛时间较长。