Corresponding author: OUYANG Hai-bin, E-mail: oyhb1987@163.com
和声搜索算法(HS)是一种简单有效的启发式智能算法，由Geem等[1]于2001年提出.HS算法模拟即兴创作过程，具有机制简单、随机性强、全局优化效果好的特点.通过近十几年的研究，HS算法及其改进算法已被成功地应用到许多实际优化问题中.至今，学者们对HS算法的研究主要通过参数的有效调整，优化机制策略的改进以及与其他智能算法的融合这三种途径.一些改进的和声搜索算法逐渐被提出，例如改进和声搜索算法(IHS)[2]，探索和声搜索算法(EHS)[3]，新颖全局和声搜索算法(NGHS)[4]，全局动态和声搜索算法(GDHS)[5]等.虽然这些算法提高了HS算法的优化性能，但仍存在着搜索盲目、易陷入局部最优、多样性差的缺陷.
子种群的思想在粒子群算法和差分进化算法中都得到了很好的应用，其突出的特点是能够有效增强种群的多样性，提高算法逃逸局部最优的能力.为了克服HS算法的不足，进一步增强HS算法的寻优能力，本文提出了一种多子群混合和声搜索(MHHS)算法.该算法引入子种群的思想，利用和声之间的距离划分子种群，并结合相应的进化策略，改善算法的优化性能.数值仿真验证了本文算法的有效性.
1 相关知识和声搜索算法[1]的基本步骤如下.
步骤 1 算法参数初始化,给定和声记忆库大小(HMS)、最大迭代次数(G)、和声记忆库的考虑概率(HMCR)、基音调整概率(PAR)、基音调整步长(BW).
步骤2 给定范围[ｘｉＬ ，ｘｉU]，ｘｉＬ和ｘｉU分别为第i维变量的下限和上限.根据式(1)随机初始化，产生HMS个和声向量存入和声记忆库HM.
步骤3 基于HMCR,PAR和BW进行即兴创作，产生一个新的和声向量.在进行基音调整时，当随机数大于0.5时，取“+”号，小于0.5时，取“-”号.其具体伪代码如图 1所示.
|
图1 算法即兴创作过程的伪代码 Fig. 1 Pseudo codes of HS improvisation |
步骤4 更新和声记忆库.判断新和声 x new是否优于当前HM内最差和声 x worst,若是，则用新和声代替当前HM内最差和声.
步骤5 核查终止准则.如果当前迭代次数g等于最大迭代次数 G ，则终止运行HS算法，否则重复执行步骤3和步骤4.
2 多子群混合和声搜索算法为进一步增强和声搜索算法的优化性能，本节提出一种多子群混合和声搜索算法.下面将具体介绍多子群划分、差分调整和通信机制.
2.1 多子群划分对于多子群划分，传统方法主要有三种：一是按照种群数目进行等量随机划分，例如种群数目为100，划分为4个子种群，每个子种群随机选择25个不同的个体，这种方法随机性强，有一定的盲目性，容易导致各个子种群的差别性低，划分子群或者不划分子群效果相差不大；二是按照个体的适应值排序进行划分，即把所有个体按照适应值的大小排序，然后从排序的第一个开始每25个划分为一个子种群，虽然这样能够有效显示各个子群间的差异，但是每个子群内部的差异性变差，容易导致算法全局搜索能力下降；三是依照整个种群的具体信息设定平衡标准来进行划分，例如将整个种群划分为优于平均适应值和劣于平均适应值的两个子种群.这种方式在迭代前期有利于算法的搜索，使算法的局部搜索和全局搜索相结合，但是到了迭代后期，平均适应值变化范围非常狭小，个体之间已很难用平均适应值加以区分，这样会导致划分的两个子种群非常相似，使算法难以跳出局部最优.本文提出一种多子群划分策略.具体操作如下.
步骤1 计算每一个和声到最好和声的空间距离，表达式如下:
步骤 2 根据所计算的距离di,best，从小到大进行排序.
步骤 3 根据距离的排序进行分层，为简单起见，分为顶层、中间层、底层，基于文献[1, 2, 5]的研究，和声记忆库大小最好取5，因此，在本文算法中保证每一层的和声数目等于5，如果存在某一层和声数目小于5，则随机初始化和声，并将其加入这一层直至数目为5.
2.2 差分调整在HS算法中，原始的基音调整操作受步长BW大小的影响:BW大时有利于广泛搜索，BW小时有利于精细搜索;可BW往往难确定，导致算法难以有效平衡广泛搜索和精细搜索.因此，本文借助个体的差异性，利用差分调整取代基音调整，并针对不同子群的具体信息，设计不同的差分调整策略.
对于处于顶层的子群，每个和声离当前最优和声的空间距离比较小，基于算法聚集和发散思想的考虑，所有和声应逐渐向当前最优和声聚集，同时也进行局部的发散搜索，因此，提出一种最优差分调整操作，具体表达式如下：
处于中间层的子群是整个种群空间分布的核心区域，既需要扩大搜索范围，又需要有效的邻域搜索，因此，设计一种多选择差分调整策略，如下式所示：
对处于底层的子群进行广泛的随机搜索，因此，采用一种随机差分调整策略，如下式所示：
在本文算法中，3个子群处在不同的层次，顶层子群处于群体优化方向的指导阶段，中间层子群处于群体发展阶段，底层子群处于群体培育阶段，为了协调各个子群的进化，提出一种简单通信机制.
通信过程如下：
步骤1 顶层、中间层和底层子群分别产生3个和声向量 x t,i, x m,i,和 x b,i.每个子群的最差和声向量为 x t,w,x m,w,x b,w,每个子群中距离当前最优和声向量最远的和声向量分别为 x t,f,x m,f, x b,f,对应的距离为 dt,f,dm,f,db,f ,每个子群距离当前最优和声向量最近的和声向量为 x t,n, x m,n, x b,n,对应的距离为dt,n,dm,n,db,n.
步骤2 独立的子群进行选择操作：
If f( x t,i) ＜f( x t,w)， x t,w= x t,i，End If
同理 x m,i和 x b,i 分别与 x m,w和 x b,w比较.
步骤3 分别计算3个和声向量 x t,i, x m,i和 x b,i 到当前最优和声向量的距离，得到dt,d,dm,d和db,d.
步骤4 以距离为标准进行通信.
步骤4.1 顶层子群的新和声向量与中间层的距离最优和声向量比较：
If dt,d<dm,n, x m,n= x t,i,End If
步骤4.2 中间层的新和声向量与顶层的距离最差和声向量比较：
If dm,d<dt,f, x t,f= x m,i,End If
步骤4.3 中间层的新和声向量与底层的距离最优和声向量比较：
If dm,d<db,n， x b,n= x m,i,End If
步骤4.4 底层的新和声向量与中间层的距离最差和声向量比较：
If db,d<dm,f, x m,f= x b,i,End If
步骤 5 通信结束.
2.4 算法步骤多子群混合和声搜索算法的具体步骤如下.
步骤1 初始化算法参数.给定和声记忆库大小HMS，最大迭代次数G，和声记忆库考虑概率HMCR，基音调整概率PAR，α0为初始权重，β0为差分缩放初始值，距离调整系数μ.
步骤2 初始化和声记忆库HM.
步骤3 进行子群的划分.计算每个和声到当前最优和声的距离di,best并进行排序划分出顶层子群、中层子群和底层子群.对于不同的子群采用不同的标记号，顶、中、底层子群采用数字1，0，-1标记.
步骤4 针对所划分的子群分别进行即兴创作.
步骤5 基于通信机制的要求，各个子群进行信息交流，并更新子群.
步骤6 验证终止条件.如果迭代次数达到最大值G，则终止算法运行，否则重新执行步骤4和步骤5.
3 实验仿真与结果 3.1 函数优化实验准备为了验证本文算法的有效性，与EHS算法[3]，NGHS算法[4]，MPSO算法[6],CLPSO算法[7],DE算法[8],ODE算法[9],IABC算法[10]及HS算法[1]进行了比较.所有算法的参数均参照文献中给定的最优参数设置，在本文算法中，HMS=15,每个子群的和声记忆库大小为5，HMCR=0.99,PAR=0.45,差分缩放初始值β0=0.5，距离调整系数μ=g/2，对5个经典测试函数进行优化.5个经典函数的表达式如下：
其中-100≤xi≤100,在xi=0时达到极小值0.
以平均最优值作为指标，利用5个经典函数来测试PAR和β0对本文算法优化性能的影响，维数N=30，HMS=5，最大迭代次数G=50000，独立运行算法程序30次，分别得到优化结果如表 1~2所示.
|
表1 PAR变化对MHHS算法的影响 Table 1 Effect of PAR on MHHS |
|
|
表2 β0变化对MHHS算法的影响 Table 2 Effect of β0 on MHHS |
由表 1可知，不同的PAR值，所优化的结果偏差比较大，针对不同的函数，需要适当地调整PAR值.整体上，PAR的值在范围[0.25,0.5]之间，优化的效果较好，因此，针对具体的优化问题，合理的PAR需要具体的调试.
由表 2可知，β0 的值影响MHHS算法最终解的质量，虽然每一个确定的β0 适合于所有的优化问题，但在整体上，β0 的值在范围[0.25,0.5]之间，优化的效果较好.
3.2.2 各种算法的优化结果比较与分析本文所进行的数值测试，均采用MATLAB 7.04实验仿真软件，Pentium(R)4，CPU为2.93GHz的电脑运行算法程序.对f1~f5进行30次独立优化仿真，所得的结果如表 3所示，其中函数维数分别为10，30，50.当优化结果的数量级小于-330时，计算机显示结果为0.
|
|
表3 9种算法所获得的f1~f5(N=10,30,50)的优化结果 Table 3 Optimization results of nine algorithms for f1-f5 (N=10，30，50) |
由表 3可以看出，对于f1函数，虽然EHS算法、NGHS算法、CLPSO算法、ODE算法和IABC算法能搜索到靠近全局最优值的值，并且MPSO算法和IABC算法在维数为10时能够搜索到最优值，但本文算在维数为10和30 时能找到全局最优值，并比其他8种和声搜索算法所优化的结果要好.MPSO算法和ODE算法求解出f2函数的平均最优值和方差都达到了较高的数量级，EHS算法、CLPSO算法和IABC算法也取得了较好的优化效果，但本文算法在整体上所搜索到结果相对这些算法来说有进一步的提高.对于f3函数，除了HS算法优化的精度稍微低一些外，其他8种算法优化的精度都较高，所找到的最优值靠近全局最优值.本文算法优化的结果虽没有较大的提高，但仍显示出了良好的优化性能.对于函数f4，EHS算法、NGHS算法、CLPSO算法、ODE算法、IABC算法和本文算法所取得的结果相差不多，表明本文算法具有很好的优化竞争能力.函数f5是一个典型的高维复杂优化测试问题，求解过程比较困难.本文算法搜索到靠近全局最优值的值，相对于其他算法的优化结果有很大的进步.通过这5个函数的实验仿真，从整体上看，本文算法优于其他算法，其原因在于本文算法针对不同的和声采用了不同的优化措施，有效平衡算法的搜索和探测过程，提高算法逃逸局部最优的能力.
4 结 语本文提出一种多子群混合和声搜索(MHHS)算法，该算法对HS算法进行了三点改进：一是根据每个和声到最好和声的距离进行子种群的划分，以更好地增加算法的搜索范围；二是基于子种群的划分，融合了不同的差分调整策略，提高算法的寻优能力，增加和声记忆库的多样性；三是建立通信机制，使各子群以一定规格进行信息交流，提高算法的搜索空间.仿真结果表明，本文算法在寻优精度、收敛性和鲁棒性方面整体上优于文献中报道的算法，具有良好的优化潜力.
| [1] | Geem Z W,Kim J H,Loganathan G V.A new heuristic optimization algorithm:harmony search[J].Simulation,2001,76(2):60-68.( 4) |
| [2] | Mahdavi M,Fesanghary M,Damangir E.An improve harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation,2007,188(2):1567-1579.(2) |
| [3] | Das S,Mukhopadhyay A,Roy A,et al.Exploratory power of the harmony search algorithm:analysis and improvements for global numerical optimization[J].IEEE Transactions on Systems,Man,and Cybernetics.Part B:Cybernetics,2011,41(1):89-106.(2) |
| [4] | Zou D X, Gao L Q, Wu J H, et al.Novel global harmony search algorithm for unconstrained problems[J].Neurocomputing,2010,73(16):3308-3318.(2) |
| [5] | Khalili M,Kharrat R,Salahshoor K,et al.Global dynamic harmony search algorithm:GDHS[J].Applied Mathematics and Computation,2014,228:195-219.(2) |
| [6] | 吴沛锋, 高立群, 邹德旋, 等.一种改进粒子群优化算法[J].东北大学学报:自然科学版, 2010, 31(11):1530-1533. (Wu Pei-feng,Gao Li-qun,Zou De-xuan,et al.An improved particle swarm optimization algorithm[J].Journal of Northeastern University:Natural Science,2010,31(11):1530-1533.)(1) |
| [7] | Liang J J,Qin A K,Suganthan P N,et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation 2006,10(3):281-295.(1) |
| [8] | Storn R,Price K.Differential evolution:a simple and efficient adaptive scheme for global optimization over continuous spaces.Technical Report TR-95-012[R].Berkeley:International Computer Science Institute,1995.(1) |
| [9] | Rahnamayan S,Tizhoosh H R,Salama M M A.Opposition-based differential evolution[J].IEEE Transactions on Evolutionary Computation,2008,12(1):64-79.(1) |
| [10] | Gao W,Liu S.Improved artificial bee colony algorithm for global optimization[J].Information Processing Letters,2011,111(17):871-882. (1) |