东北大学学报:自然科学版   2015, Vol. 36 Issue (10): 1403-1407   PDF (236 KB)    
引用本文
翟军昌, 高立群, 欧阳海滨, 刘宏志. 改进的新颖全局和声搜索算法[J]. 东北大学学报:自然科学版 , 2015, 36(10): 1403-1407.  
ZHAI Jun-chang, GAO Li-qun, OUYANG Hai-bin, LIU Hong-zhi. Improved Novel Global Harmony Search Algorithm[J]. Journal Of Northeastern University Nature Science, 2015, 36(10): 1403-1407.  
改进的新颖全局和声搜索算法
翟军昌, 高立群, 欧阳海滨, 刘宏志     
(东北大学 信息科学与工程学院, 辽宁 沈阳 110819)
收稿日期：2014-09-12
基金项目：国家自然科学基金资助项目(61273155).
作者简介：高立群(1949-),男,辽宁沈阳人,东北大学教授,博士生导师.
通讯作者：翟军昌(1978-), 男, 辽宁东港人,东北大学博士研究生
摘要：为了提高和声搜索算法的寻优性能,提出了改进的新颖全局和声搜索(INGHS)算法.通过差分向量范数定义和声记忆库多样性,以和声记忆库的多样性信息为指导实现位置动态更新,并结合变异操作更新和声记忆库.算法采用动态位置更新策略产生新和声,在寻优早期具有较好的全局搜索性能，在寻优后期具有较好的局部搜索性能,提高了算法跳出局部最优的能力.利用7个标准测试函数对所提算法与目前已知文献中优秀的改进HS算法进行性能测试,测试结果表明所提算法具有较好的寻优性能.
关键词： 和声搜索     范数     多样性     自适应     变异    
Improved Novel Global Harmony Search Algorithm
ZHAI Jun-chang, GAO Li-qun， OUYANG Hai-bin， LIU Hong-zhi    
School of Information Science ＆ Engineering, Northeastern University, Shenyang 110819, China.
Corresponding author: ZHAI Jun-chang, E-mail: zhaijunchang@163.com
Abstract: To improve the optimization performance of harmony search algorithm, an improved novel global harmony search (INGHS) algorithm was proposed. The harmony memory diversity was defined by the difference vector norm to implement dynamically position updating, and the mutation operation was employed to update harmony memory. A new harmony generated with dynamically updating strategy made the algorithm having excellent global search performance in the early states and local search capability during the final stages of the optimization process, which avoided the algorithm trapped in local optimal. Finally, the simulation for 7 benchmark functions were carried out using the proposed algorithm and other state-of-the-art HS variants that reported in the recent literature. The simulation results demonstrated that the proposed algorithm has a higher precision.
Key words: harmony search     norm     diversity     adaptive     mutation    

和声搜索(HS)算法是由Geem等[1]提出的一种启发式优化算法.该算法操作简单，收敛速度和收敛性与问题变量的初始值无关.迄今为止,涌现出了许多改进HS算法变体[2, 3, 4, 5, 6, 7, 8, 9, 10].如改进和声搜索(IHS)算法[2]、动态自适应和声搜索(DSHS)算法[3]、全局最好和声搜索(GHS)算法[4]、智能调整和声搜索(ITHS)算法[5]等.受GHS算法启发,自适应全局最好和声搜索(SGHS)算法[6]、新颖全局和声搜索(NGHS)算法[7]、改进全局最好和声搜索(IGHS_E)算法[8]和结合反向学习的改进全局和声搜索(IGHS_X) 算法[9]相继出现.最近Valian等[10]针对NGHS算法过早收敛的问题,提出了智能全局和声搜索(IGHS_V)算法,提高其优化性能.然而HS及其改进算法仍然存在收敛速度慢,易陷入局部最优等问题.

为了提高NGHS算法的优化性能,本文提出了改进的新颖全局和声搜索(INGHS)算法.在新算法中引入和声记忆库多样性作为指导信息,给出了动态位置更新策略,提高了算法全局搜索和局部搜索的能力,从而避免算法陷入局部最优.最后仿真结果验证了所提方法的有效性.

1 HS和NGHS算法 1.1 HS算法

HS算法首先产生HMS个初始解,并放入和声记忆库中; 然后对解的各个分量分别以概率HMCR在和声记忆库内进行搜索,以1-HMCR 的概率在和声记忆库外搜索,期望获得新解的对应分量.在和声记忆库内进行搜索时,当随机搜索到某一分量后,则对该分量以概率PAR进行扰动.最后由搜索后得到的各分量构成新解,若新解优于和声记忆库中的最差解,则用新解替换最差解.如此循环,直到满足终止条件为止.HS算法操作包括:初始化优化问题和算法的参数;初始化和声记忆库;即兴创作产生一个新和声;更新和声记忆库;判断终止准则.关于HS算法的详细操作,请参见文献[1].

1.2 NGHS算法

基于粒子群优化算法的种群智能思想,Zou等[7]提出了新颖的全局和声搜索(NGHS)算法.NGHS算法排除了HS算法中HMCR,PAR和bw三个参数,通过引入位置更新和变异操作产生新和声,NGHS算法位置更新操作为

式中：xR为xjworst关于xjbest的对称位置；xjbest为最优和声向量的第j维分量;xjworst表示最差和声向量的第j维分量；x′j表示新生成和声向量的第j维分量.

由式(2)可知,x′j产生在xworstj关于xbestj对称的某个区域内.由于NGHS中的位置更新操作容易陷入局部最优,因此引入了变异操作,即

式中,xjL和xjU分别为第j维和声分量的下界和上界.

此外NGHS产生的新和声直接替换和声记忆库中的最差和声.

2 改进的新颖全局和声搜索(INGHS)算法

本文提出的INGHS算法,通过引入和声记忆库多样性定义自适应因子,实现位置动态更新,结合变异操作产生新和声.

2.1 和声记忆库多样性定义

在和声记忆库中,引入差分向量的范数定义和声记忆库的多样性Di,即

式中：Di表示第i代和声记忆库的多样性；HMbest和HMworst分别表示第i代和声记忆库中最优和最差和声向量；‖·‖表示向量的1范数.

若Di取值越大,表明当前和声记忆库中最优和声与最差和声差异越大,即和声记忆库中和声的多样性越好.若Di的取值越小,表明当前和声记忆库最优和声与最差和声差异越小,即多样性较差.

2.2 自适应因子(adaptive factor,AF)

自适应因子AF定义为

式中,Di和Di-1分别代表第i和i-1 代和声记忆库的多样性,设D0=1.

AF越小，表明和声记忆库的多样性越来越差,需要对最优和声的邻域信息进行精细搜索.反之则要提高算法的全局搜索性能.

2.3 位置更新策略

在INGHS算法中,通过自适应因子作为指导信息动态产生xjworst关于xjbest的对称点xR,即

在式(6)中,自适应因子AF反映了当前和声记忆库的多样性变化情况,而不是完全随机的过程,可以对对称点xR自适应调整.

引入新的对称点选择策略后,将其与NGHS算法中对称点选择策略通过位置更新概率PR进行决策,从而实现不同的位置更新策略.PR定义为

) 式中：N代表解空间维数；i代表当前迭代次数；J为进化代数.

由式(7)的定义可知,位置更新概率PR在算法迭代初期取值较大,随着算法迭代次数不断增加取值逐渐减小.

新的操作策略按照下面的决策规则执行：

1) 以概率PR保留原算法中对称点xR的选取操作,即式(1).

2) 以概率1－PR执行新的选取对称点xR操作,即式(6).

2.4 算法操作流程

INGHS算法的操作流程如下.

步骤1 初始化参数.设置和声记忆库大小HMS,最大迭代次数J和基因变异率pm.

步骤2 初始化和声记忆库确定范围[xjL,xjU],随机产生HMS个和声向量存入和声库HM中.

步骤3 即兴创作产生新和声，即兴创作产生新和声的伪代码如下：

步骤4 更新和声记忆库.新和声直接更新和声记忆库中的最差和声.

步骤5 判断终止准则.如果当前迭代次数等于最大迭代次数J,则终止运行INGHS算法,否则重复执行步骤3和步骤4.

3 仿真实验 3.1 仿真实验准备

为了验证INGHS 算法的性能,本文将其与HS[1]，SGHS[6]，NGHS[7]，IGHS_E[8]，IGHS_X[9]和IGHS_V[10]进行优化性能测试.实验中选取优化算法7个经典标准测试函数,具体表达如下.

其中,z=x-o+1,o=[o1,o2,…,oN]是平移的全局最优解.

其中,z=(x-o)×M,M为线性传输矩阵.

函数维数、搜索空间及最优值见表 1.

表 1 函数维数、搜索空间和最优值 Table 1 Dimension, search space and optimum value of functions
3.2 仿真结果与分析

实验中,每种算法用到的参数均选择参考文献中的最优设置.每种算法参数的具体设置如下. HS：HMS=5,HMCR=0.95,PAR=0.33,bw=0.01. SGHS：HMS=5,HMCRm=0.98,PARm=0.9,bwmin=0.000 5,bwmax=(xiU-xiL)/10,LP=0. NGHS：HMS=5,pm=0.005. IGHS_E: HMS=5,HMCR=0.99,PARmin=0.01,PARmax=0.99,bwmin= 0.000 1,bwmax= (xiU-xiL)/10/20.IGHS_X： HMS=20,HMCRmin=0.9,HMCRmax=0.99,PARmin=0.9,PARmax=0.95,ξ=0.1,α=0.25,β=0.05.IGHS_V： HMS=5,HMCR=0.995 0,PAR=0.4. 本文INGHS算法用到的参数HMS=5，pm=0.005，与文献[7]中相同.

为了保证算法对比的公平性,将算法最大迭代次数J取80 000与文献[7, 10]中相同,每种算法独立运行30次.分别用Best代表最优值,Worst代表最差值,Mean代表平均值,Std代表方差,对5个函数的测试结果如表 2所示.

表 2 标准函数测试结果 Table 2 Optimization results of benchmark functions

由表 2知，IGHS_X，IGHS_V和INGHS三种算法的结果优于HS及其他种改进HS算法,其中INGHS算法除了对函数f5得到的最好值稍差于IGHS_V算法外,对其他几个函数优化的结果均优于IGHS_X和IGHS_V两种算法; 从平均值、最差值和方差看,INGHS算法的结果均优于HS及其他几种改进HS算法,由此可知INGHS算法在寻优时不仅比HS及其他几种改进HS算法的寻优精度高,而且更加稳定.对函数f6和f7的优化效果来看,几种和声算法的寻优效果较差,都陷入了局部最优.其中SGHS和NGHS算法的优化精度略优于其他几种算法,本文INGHS算法与IGHS_V算法的优化精度比较接近.

4 结论

本文提出了INGHS算法,新的位置更新策略使新和声根据和声记忆库多样性的变化动态调节产生,增强了算法开发解空间局部信息的能力.动态调整步长的方式产生新和声,使算法具有良好的收敛性,避免了算法因收敛过快而陷入局部最优的不足.最后仿真结果表明INGHS算法具有较高的寻优精度.

参考文献
[1] Geem Z W, Kim J H, Loganathan G V.A new heuristic optimization algorithm:harmony search[J].Simulation, 2001, 76(2):60-68.(2)
[2] Mahdavi M, Fesanghary M, Damangir E.An improved harmony search algorithm for solving optimization problems[J].Applied Mathematics and Computation, 2007, 188(2):1567-1579.(2)
[3] Kattan A, Abdullah R.A dynamic self-adaptive harmony search algorithm for continuous optimization problems[J].Applied Mathematics and Computation, 2013, 219(16):8542-8567.(2)
[4] Omran M G H, Mahdavi M.Global-best harmony search[J].Applied Mathematics and Computation, 2008, 198(2):643-656.(2)
[5] Yadav P, Rajesh K, Panda S K, et al.An intelligent tuned harmony search algorithm for optimization[J].Information Sciences, 2012, 196:47-72.(2)
[6] Pan Q K, Suganthan P N, Tasgetiren M F, et al.A self-adaptive global best harmony search algorithm for continuous optimization problems[J].Applied Mathematics and Computation, 2010, 216(3):830-848.(3)
[7] Zou D, Gao L, Wu J, et al.Novel global harmony search algorithm for unconstrained problems[J].Neurocomputing, 2010, 73(16):3308-3318.(5)
[8] EI-Abd M.An improved global-best harmony search algorithm[J].Applied Mathematics and Computation, 2013, 222(5):94-106.(3)
[9] Xiang W, An M, Li Y, et al.An improved global-best harmony search algorithm for faster optimization[J].Expert Systems with Applications, 2014, 41(13):5788-5803.(3)
[10] Valian E, Tavakoli S, Mohanna S.An intelligent global harmony search approach to continuous optimization problems[J].Applied Mathematics and Computation, 2014, 232(3):670-684.(4)