第8章　和声搜索算法

8.1　和声搜索算法的提出

和声搜索（Harmony Search，HS）算法是2001年由韩国学者Zong Woo Geem等人提出的一种基于音乐演奏和声原理的仿人智能优化算法^[32-34]。

在音乐演奏中，乐师们凭借自己的记忆，通过反复调整乐队中各乐器的音调，最终达到一种美妙的和声状态。音乐和声是一种来源于审美观的、令人欢愉的美妙的声音组合。在自然界中，和声是一些有不同频率的声波之间的特殊关系。音乐演奏是要寻找一个由美学评价所决定的最佳状态（极好的和声），同样优化算法也是寻找由目标函数值所决定的最优状态（全局最优——最低花费、最大利益或效率）。美学评价是由参与演奏的乐器发出的声音集合所决定的，正如目标函数值是由设计变量值所组成的集合决定的。表8.1给出了优化过程与音乐演奏和声过程的对比情况。

和声搜索算法已用于求解旅行商、多目标水坝调度、水资源网络优化、公交车路径优化、网络优化等问题。

8.2　和声搜索算法的原理及结构

和声搜索算法首先初始化和声记忆库，其次在和声记忆库中随机产生新的和声，如果新的和声比记忆库中最差的和声好，则把新的和声放进记忆库，把最差的和声换出记忆库。如此循环直至满足停止准则。和声记忆库（HM）的结构图如图8.1所示。

考虑由小提琴、萨克斯、钢琴组成的爵士三重奏乐曲。最初，记忆库被随机的和声（C，E，G）、（C，F，A）和（B，D，G）充满，它们被美学评价所分类。在演奏调试的过程中，3个乐器产生了新的和声，如（C，D，A），小提琴的音调｛C｝来自｛C，C，B｝；萨克斯的音调｛D｝来自｛E，F，D｝；钢琴的音调｛A｝来自｛G，A，G｝。在和声记忆库中每一个音调有同样的机会被选中，如在和声记忆库中萨克斯的每一个音调E、F和D都有33.3%的概率被选中。如果新生成的和声（C，D，A）比和声记忆库中现存的任何一个和声都好，那么新的和声就被换进和声记忆库，而最差的和声（在例子中为（B，D，G））就被换出和声记忆库。一直重复这个过程直到得到令人满意的结果（最优解）。

为了更深地理解和声搜索算法的原理，考虑如下的最优化问题。

f（x）=（x₁-2）²+（x₂-3）⁴+（x₃-1）²+3（8.1）

式（8.1）为一个最小化问题，当全局最小时可以很容易地找到解向量为（2，3，1），和声搜索寻找解向量是用另一种方法。如图8.2所示的和声记忆库是由随机生成的值所构成的，这些随机生成的值被目标函数值所分类。接下来，新的和声（1，2，3）是在和声记忆库中随机搜索产生的：x₁的值是从｛2，1，5｝中搜索到的｛1｝；x₂的值是从｛2，3，3｝中搜索到的｛2｝；x₃的值是从｛1，4，3｝中搜索到的｛3｝。因为新的和声函数值是9，所以新的和声（1，2，3）被放入和声记忆库，最差的和声（5，3，3）被换出和声记忆库，如图8.3所示。最后，和声搜索随机地找到函数值是3的和声（2，3，1），此时问题达到全局最小。

当然，以上假设所有全局最优解起初就存在于和声记忆库中。但实际情况并不总是这样，为了找到全局最优，和声搜索提出了一个参数，和声记忆库保留概率（HMCR），它的范围为0～1。如果一个在0～1均匀分布的数超过了和声记忆库保留概率的值，那么和声搜索就在允许的范围内随机地寻找乐器音调（变量值）而不用考虑和声记忆库。和声记忆库的保留概率为0.95，也就是在下一步，算法在和声记忆库中选择乐器音调（变量值）的概率为95%。

为了使目标函数值逃离局部最优，提出了另一个参数——音调调节率（PAR）。这种方案模拟了在音乐演奏中，为了调整合奏的效果而对每种乐器进行音调调整。音调调整办法是在可能存在的音调范围内转移到相邻的音调去。如果有5个可能存在的音调为｛1，3，4，6，7｝，则在音调调节的过程中｛6｝可以被移向临近的｛4｝、｛7｝。音调调节的概率为0.1，也就是说，算法以10%的概率选择相邻的音调。

假设一种乐器可能存在的音调的集合为｛C，D，E，F，G｝，和声记忆库的保留概率为0.95，音调调节概率为0.1，乐器现有音调｛C，E，G｝在和声记忆库中，在和声搜索算法随机处理的过程中，算法以95%的概率从｛C，E，G｝中任意选取一个音调，或者以5%的概率从｛C，D，E，F，G｝中选取一个音调，且当｛E｝被选取时可以以10%的概率被｛D｝或｛F｝替换。

如上所述，和声搜索自然地包含了现有的启发式算法的结构。它保留了类似禁忌算法的初始向量元素（和声记忆库）的来历，并且从计算的开始到结束能够以类似模拟退火算法的方式改变适应率（和声记忆库保留概率），并且能够以类似遗传算法的方式同步地处理多个向量元素。但是遗传算法与和声搜索算法最主要的不同是和声搜索算法从所有现存的向量（在和声记忆库中所有的和声）中生成一个新的向量，而遗传算法仅从现存的两个向量（亲代）中生成新的向量。此外，当生成一个新的向量时和声搜索算法能够考虑到这个向量中的每一个组成变量，但是遗传算法却不能，因为它必须要保持遗传结构。

8.3　和声搜索算法的主要步骤及流程

将乐器i（i=1，2，…，m）类比于优化问题中的第i个变量，各乐器的音调相当于各变量的值，各乐器音调的和声X^j（j=1，2，…，N）相当于优化问题的第j组解向量，其中，音乐效果评价类比于目标函数f（X^j）（j=1，2，…，N）。于是，和声搜索的计算步骤可描述如下。

（1）确定优化问题的目标函数、约束条件及和声搜索基本参数。

①乐器（变量）个数m；

②各种乐器的音调范围（变量取值范围）；

③和声记忆库HM可保存的和声个数M，而M应远小于所有可行解数目；

④和声记忆库保留概率HMCR，即在产生新解时从和声记忆库中保留解分量的概率大小；

⑤记忆库扰动概率PAR，即每次对部分解分量进行微调扰动的概率大小；

⑥最大迭代次数，即循环的最大次数，为循环终止条件。

（2）和声记忆库初始化。将随机产生m优化问题的初始解放入和声记忆库HM中，可表示为

其中，X^j为第j个解向量；为第j个解向量的第i个分量；f（X^j）为第j个解向量的函数值。

（3）产生新的解。每次产生一个新解，其中新解分量可通过3种机理产生：

①保留和声记忆库中的某些解分量；

②随机选择产生；

③对①、②中某些分量进行微调扰动。

保留和声记忆库中某些解分量，以一定概率随机对和声记忆库的某些分量进行保留，即新产生的来源于记忆库中第i个解分量的集合的概率为HMCR。按机理②产生的新解分量是从第i个解分量的可行解空间（即变量i的取值范围）中以1-HMCR的概率随机产生的。对两种机理产生的解分量按概率PAR进行扰动，得到按机理③产生的新解分量。扰动原则为

x^new=x′^new+2×u×rand-u（8.3）

其中，x′^new ，x^new分别为扰动前后新解的第i个解分量；u为带宽；rand为0～1的随机数。

（4）更新记忆库。判断新解是否优于HM中的最差解，若是，则将新的解替换最差解，得到新的和声记忆库。

（5）重复步骤（3）和步骤（4），直到达到最大迭代次数或满足停止准则后结束循环输出最优解。

实现和声搜索算法的流程如图8.4所示。和声搜索算法的初始解可以随机给出，也可以事先使用其他启发式算法等构成一个较好的初始解。和声搜索算法主要是基于邻域搜索的，初始解的好坏对搜索的性能影响很大。尤其是一些带有很复杂约束的优化问题，随机给出的初始解很可能是不可行的，甚至通过多步搜索也很难找到可行解，这时应针对特定的复杂约束，采用启发式方法或其他方法找出一个可行解作为初始解。

和声记忆库HM的大小M是HS的一个重要参数，HS之所以具有更强的全局搜索能力，很大程度上依赖于HM的存在。一般来说，M越大，找到全局最优区域的能力越强。但由于HS是多点开始的，随M的增大，计算量将会变大，从而影响到最终搜索到最（近）优解的速度。HMCR是和声搜索算法的另一个重要参数，其取值范围为0～1，它决定每次迭代过程中新解产生的方式。在和声搜索算法中，因新解产生时每个变量都依赖于HMCR，故HMCR应取较大的值，通常HMCR的值为0.9～1.0。音调调节率PAR在和声搜索中起控制局部搜索的作用，它可使搜索逃离局部最优，其取值一般为0.1～0.5，局部扰动中u可取值为0.001～0.01。