ABSTRACT

Harmony search algorithm is a new heuristic global search algorithm, which has been successfully applied in many combinatorial optimization problems. The better performance of genetic algorithm, simulated annealing algorithm and tabu search is demonstrated on the problem. However, the harmony search algorithm is easy to fall into local search. This paper makes an improvement on the generation of the initial solution vector and the harmony bank so as to improve the efficiency of the algorithm.

Keywords:Harmony Search Algorithm, Initial Solution Vector, Harmony Bank

和声搜索算法的改进

张康丽，陈寿元，邵增珍

山东师范大学信息科学与工程学院，山东 济南

收稿日期：2015年10月24日；录用日期：2015年11月7日；发布日期：2015年11月11日

摘 要

和声搜索算法是新近问世的一种启发式全局搜索算法，在许多组合优化问题中得到了成功应用。在有关问题上展示了较遗传算法、模拟退火算法和禁忌搜索更好的性能。但是，和声搜索算法在迭代时容易陷入局部搜索的状态，本文针对这一问题，对生成初始解向量进行了改进，对更新和声记忆库进行了改进。从而提高了算法的执行效率，避免算法陷入局部最优。

关键词 :和声搜索算法，初始解向量，和声记忆库

1. 引言

2001年，韩国学者Geem Z W提出了和声搜索算法HS (Harmony Search)，该算法是一种新的启发式智能搜索算法，HS灵感来源于音乐创作中和声的调节，音乐家们在原有和声的基础上对各个乐器的音调进行调节，逐步实现一个自己满意的新和声。

HS算法通用好，依赖于问题程度低，一直受到广大研究人员的关注。它被应用到各种优化问题中，例如水网设计优化、土木工程结构优化、公交线路车辆调度优化等众多领域。文献[1] 提出了一种求解数值优化问题的轮盘赌自适应和声搜索算法；文献 [2] 阐述了和声搜索算法的起源、思想、基本步骤，并分析了参数HMS、HMCR、PAR对该算法的影响；文献 [3] 首先描述了原始和声搜索算法的特点和流程，然后对和声搜索算法繁多的变种及其应用领域进行梳理和分类，最后指出和声搜索算法的未来研究方向；文献 [4] 在和声算法中引入自适应的参数调节方式及遗传算子，使和声算法能够解决离散型数学问题；文献 [5] 提出了一种提取种群中优良个体的算法。总的来说，和声搜索算法容易陷入局部最优的问题并没有引起足够的重视。本文中提出一种ALHS算法对此进行了部分改进，该算法首先采用区间分割法生成初始解向量，避免了收敛于局部最优解的可能性；然后利用了遗传算法的基于排序的概率分配方法和轮盘赌选择方法，提高和声记忆库的多样性，避免算法陷入局部最优，提高了算法的效率。实验结果表明改进的算法效率高于HS算法 [2] 。

2. 和声搜索算法

和声搜索算法原理

和声搜索算法的基本思想：首先对和声记忆库大小HMS (Harmony Memory Size)和各种参数进行初始化，然后按照一定的概率生成新的和声并且对新和声进行微调，如果新和声优于原和声记忆库中最差的和声则进行替换，按照上述步骤进行迭代直到找到最优解或满足停止条件为止 [6] 。HS算法基本步骤为：

Step 1：确定需要优化问题的目标函数和HS的基本参数。

其中是需要进行优化的目标函数，是由个决策向量组成的解向量，是决策向量，的下界和上界分别是和。初始化的参数主要包含：

，决策变量的个数(I ≥ 1)

，决策变量的范围

HMS，和声记忆库的解向量个数

HMCR，和声记忆库的保留概率

PAR，新生成的解向量的微调概率

bw，(band width)微调时使用的干扰带宽

iter，迭代次数计数器(初始值为0)

Itermax，算法的最大迭代次数(停止条件)

Step 2：根据Step 1的约束对和声记忆库进行随机初始化。

根据下式可得到解向量的各个决策变量，从而得到和声记忆库中各个初始化解向量。

Step 3：构建新的解向量

新的解向量，其中每个决策变量可通过三中方式产生。

1) 选择原解向量中的对应决策变量；

2) 在决策变量的取值范围内随机选择；

3) 对于前两种方式中某些决策变量新型概率微调。具体构建流程如下：

For i=1 to n do

If r

xinew∈U{xi1,xi2,…,xiHMS}

If r

xinew=xinew±r×bw

End if

Else //随机选择产生新的决策向量

xinew=ximin+(ximax-ximin) ×r

End if

End for

Step 4： 更新和声记忆库。Xworst是和声记忆库中最差的解向量。

Xworst =Xnew,g(Xnew)优于g(Xworst)

=Xworst,g(Xnew)差于g(Xworst)

Step 5：判断算法是否满足停止条件。i_ter = i_ter + 1，若i_ter < I_termax则跳转到Step 3继续迭代，否则输出最优解，算法结束。

3. 改进的和声搜索算法

3.1. 生成初始解向量的改进

初始解向量采用区间分割法生成，可以保证随机产生的各个解向量具有差别性，在解空间上的分布状况均匀，避免了收敛于局部最优解的可能性，加快了和声搜索算法的收敛速度，增强了全局搜索的能力 [8] 。

其中为分割得到的子解空间，是各个决策向量子区间大小。n个决策向量子区间构成一个子解空间。

3.2. 更新和声记忆库的改进

1) 基于排序的概率分配方法(Rank-Based Probability Assignment)

将和声记忆库中的解向量按照适应度值进行排序，概率与具体的适应度值无关，按照解向量在顺序表中的排名确定解向量的被选择概率。计算选择概率有两种方法本文采用第一种方法计算选择概率 [4] 。

方法一(由Baker提出，其中i是解向量在顺序表中的排名)：

方法二(由Michalewicz提出，θ是排名第一的解向量的概率)：

本文采用第一种方法计算选择概率，按照适应度值从小到大进行排序，则适应度值最小的解向量被选择的概率p(0) = 0，也就是说最优的解向量永远不会被替换[10] 。

2) 轮盘赌选择方法(Roulette Wheel Selection)

通过概率分配方法得到选择概率后，计算各个解向量的累计概率，每次迭代产生一个之间的随机数，通过与累计概率比较，判断是否选择进行更新。

若，则选择第1个解向量

若，则选择第i个解向量[11]

根据上述算法基本思想，算法部分代码(使用改进后的算法更新和声库)表示如下：

1) def refreshALHS():

2) global ALHS

3) newHM = createNew(ALHS)

4) for i in range(4):

for i in range(4 - i):

if calFxy(ALHS[i][0], ALHM[i][1]) > calFxy(ALHS[i + 1][0], ALHS[i + 1][1]):

temp = ALHS[i]

ALHS[i] = ALHS[i + 1]

ALHS[i + 1] = temp

Pi = []

lanmuda = round(random.uniform(1,2), 2)

r = random.random()

5) for i in range(5):

if i == 0:

Pi.append(0)

else:

temp = (1.0 / HMS) * (lanmuda - (lanmuda- (2 - lanmuda)) * (float(i - 1) / (HMS - 1)))

Pi.append(round(temp, 2))

if r < sum(Pi[:2]):

ALHS[1] = newHS

6) if sum(Pi[:2]) <= r and r < sum(Pi[:3]):

ALHS[2] = newHS

7) if sum(Pi[:3]) <= r and r < sum(Pi[:4]):

ALHS[3] = newHS

8) if sum(Pi[:4]) <= r and r < sum(Pi):

ALHS[4] = newHS

4. 实验结果分析

4.1. Rosenbrock测试函数

试验环境：Windows 64位操作系统；Python2.7.10语言；PyCharm 4.5平台。目标函数为Rosenbrock函数[12] ，该函数是一个用来测试最优化算法性能的非凸函数。Rosenbrock函数每个等高线大致呈抛物线形，其全域最小值也位于抛物线形山谷中。但山谷内的值变化不大，要找到全域最小值相当困难。其全域最小值位于(x, y) = (1,1)点，数值为f(x,y) = 0。实验参数：HMS = 5，HMCR = 0.9，PAR = 0.3，Bw = 0.01。

1) 稳定性测试

从图1，图2中可以看到：改进后的ALHS算法搜索到的目标函数的取值大部分在0附近，波动较小；未改进的HS算法搜索的目标函数的取值偏离最优值较多，波动较大。这就表明，ALHS算法在寻求最优值方面优于HS算法。通过实验可得(表1)，整体上，ALHS算法优于HS算法，但是随着迭代次数越来越多，效果明显度降低。

2) 性能测试

4.2. 其它测试函数(图4~7)

图1. Rosenbrock函数图

图2. 稳定性测试算法对比结果图

图3. 性能结果对比图

图4. Girewank函数

图5. 性能结果对比图

图6. Sphere函数

图7. Sphere函数下性能结果图

表1. HS算法与ALHS算法寻找最优值数据结果图

5. 结论

本文针对和声算法的搜索性能不足，提出了一种改进的和声算法ALHS。通过对生成初始解向量的改进，对和声记忆库的改进，改善了算法的性能。另外，本文详细说明了该算法的基本思想，通过实验对比分析具体证明了算法的有效性。在未来工作中，将重点在和声算法的新的应用领域进行研究[5] 。

文章引用

张康丽,陈寿元,邵增珍. 和声搜索算法的改进
The Improvement of Harmony Search Algorithm[J]. 人工智能与机器人研究, 2015, 04(04): 32-39. http://dx.doi.org/10.12677/AIRR.2015.44005

参考文献 (References)