优化算法笔记（二十六）和声搜索算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）

和声搜索算法（Harmony Search）是受音乐中的和声启发而提出的启发式算法，其提出（发表）年份为2001年，算是一个比较老的算法了。和声搜索算法放在现在，其性能非常一般，不过它提出了一种领域搜索的具体实现方式，可以和不同的算法融合，提高其他算法的性能。

单独看一个和声意义不大，一个和声的一个维度会根据群体中该维度的所以取值来确定其领域范围，然后再进行领域搜索。

原算法受音乐启发，所以它所解决的目标问题也是离散的问题。

和声搜索算法中的一个个体被称为和声记忆（Harmony Memory,HM），群体中和声记忆的数量为N,每个和声记忆中的音数（维度）为D。每一维的取值范围为 。

原算法中每个维度的取值范围L是一组有序的离散的值，即在指定的变量值中选取一个作为和声记忆的值。

每个和声记忆每次迭代只能变为其领域的值。

和声算法中有两种 *** 作：1.移动到领域，2.变异到领域

其概率分别为Harmony Memory Considering Rate(HMCR)和Pitch Adjusting Rate(PAR)。

其中HMCR取值约为0.95，PAR取值约为0.10。

可以看出该算法的步骤和数值参考了遗传算法，而且两者都是为了处理离散问题。

例子如下：

和声记忆的数量为3，维度为2，其中第1维的取值范围为{A,B,C,D,E,F,G},第2维的取值为{3,4,5,6}。

第1代，三个个体的取值如下

在计算第2代时，每个个体的每一维只能去到该维度的邻域的值。

个体1_2能取到的值为(A,3) (A,4) (B,3) (B,4)

个体2_2能取到的值为(F,4)(F,5)(F,6)(G,4)(G,5)(G,6)

个体3_2能取到的值为(C,3)(C,4)(C,5)(D,3)(D,4)(D,5)(E,3)(E,4)(E,5),

图中标出了这三个个体能够到达的邻域。

变异到邻域到 *** 作也很简单，该 *** 作是对标了遗传算法中的变异 *** 作。

变异到邻域 *** 作时，该维度不会变异到当前已有的值。

如个体1_1变异第1维，由于群体中第1维的取值为{A,D,G}故该维度只能取到{B,C,E,F}。

下图中标有颜色的块出了变异 *** 作无法到达的位置，空白位置为变异 *** 作能够到达的位置。（如果没有空白位置呢？概率非常小，毕竟个体位置远少于解空间位置，如果出现了，不变异或者随机一个位置都行）

迭代过后，如果新的位置更好，则保留该和声记忆，并去除最差的和声记忆。

最后文章给出了判断找到的解是否是最优解的判断函数

其中Hr=HMCR,Hi会在该维度找到更好值时随着迭代次数递增。该公式的作用主要是为了判断何时去结束算法程序，不过在之前我们都是使用的最大迭代次数来结束算法程序，所有好像没多大用处。

算法的流程也挺简单的：

和声搜索的原算法是根据音乐中和声概念提出的，音符是离散的，所有算法也是离散的，对标遗传算法用于处理离散解空间问题，那么如何修改和声搜索算法使其能处理连续数值问题呢？

最关键的点是如何处理“邻域”，在连续解空间上，很难定义出一个点的领域，而且每个维度上的取值数量也是无穷的。

为和声搜索算法定义邻域也有几种思路：

1 .将所有的个体定义为该个体的邻域，即每次随机从群体中选择一个个体，该维度移动到所选中的个体处。

其中D,E,F分别为AB,AC,BC的中点，A,B,C三个和声记忆的邻域将由DEF这三个点及解空间边界决定，此时的邻域比思路2中的更小，也不会出现重叠部分。

当某一维度的两个领域值相等时，上述（二维）的邻域（面）将会退化成邻域（线），可能会导致该维度快速收敛到该值，故此时需要忽略重复值，将邻域重新展开（成为面）。

在连续算法中，当满足HCMR条件时，算法将根据上面的色块在邻域中随机选择一个值；当满足PAR条件时，由于无法剔除指定值，简单起见，直接移动到随机的和声记忆的该维度。

后续的实验由于是求解连续函数最值，故会选择上述连续算法中的三种思路来进行。

适应度函数 。

实验一 ： 思路一

从图像可以看出，思路一的策略与遗传算法非常的相似，移动路线类似于十字架，最终也收敛到了正解附近。前期搜索主要靠邻域移动，后期移动则是靠变异。

从结果也可以看出与遗传算法的差距不大，算法不是很稳定，其策略是飞到相邻的和声记忆上，所以跨越度比较大，精度全靠变异。

实验二 ： 思路二

从图像中可以看出，种群的搜索路径不在像实验一中那样直来直去的十字路径，收敛的速度也慢了不少，但是仍能在正解附近收敛。

从结果中可以看出，思路二的结果好了不少，同时也更加稳定（误，运气好，之前实验出现过不好的结果，没能重现）。该思路的邻域搜索面积会更大，且个体之间的邻域存在重叠部分，故会有可能收敛于不好的位置，不过概率也较小。

实验三 ： 思路三

图像逐渐贪吃蛇化！前期的图像与思路一相似，后期的图像有点类似遗传算法，可能是邻域的面积逐渐缩小成了长条状所致，不过最终“贪吃蛇”还是吃到了食物。

结果可以看出，思路三的稳定性不太行，当全部个体收敛到了一点后会开始进行思路一的替换 *** 作，但无论如何替换都是相同的值，难以找到更优的位置，于是会出现一个较差的结果。这里也可以增加范围随机来跳出局部最优。

和声搜索算法是根据和声乐理知识提出的算法。由于音符是离散的值，算法也对标了遗传算法，故原算法也是针对离散问题提出的。在解决连续性问题时，需要对其邻域概念进行扩展和修改，最终的效果与遗传算法相差不大。

在现在看来，和声搜索算法的效果属实一般，对于其的针对性研究也不太多，该算法主要提出了其不同于遗传算法的遍历解空间的方式。所以在很多论文中都能看到用和声搜索算法与其他算法融合来进行改进的例子。

与遗传算法相比，和声搜索算法的邻域概念，将遗传算法的基因由线扩展到了面上。这一点有点类似于SVM和卷积神经网络的关系，不过，遗传算法和和声搜索算法的差别并没有那么大，只是搜索方式不同罢了。

参考文献

Geem Z W , Kim J H , Loganathan G V . A New Heuristic Optimization Algorithm: Harmony Search[J]. Simulation, 2001, 2(2):60-68. 提取码：4udl

Omran M , Mahdavi M . Global-best harmony search[J]. Applied Mathematics and Computation, 2008, 198(2):643-656. 提取码：pk3s

以下指标纯属个人yy,仅供参考

目录

上一篇优化算法笔记（二十五）飞蛾扑火算法

下一篇优化算法笔记（二十七）蜉蝣算法

一、确定调式调性，把握歌曲基本情绪

看看歌曲是什么调，是不是在你的音域范围之内，如果不是，将它调整到适合你自己的调，从而确定歌曲的调性。然后，看看歌曲是大调式的还是小调式的，全曲的情绪是温柔委婉的，还是高亢激烈的。

二、配好曲子和乐句的开始和中止处

接着来看歌曲的开始和终止，开始和终止处一般应配上主和弦，因为主和弦最稳定，可以起到明确的开始、结束作用。然后来看每个乐句的起始和终止处。一个乐句可以是完整的一句歌词，也可以是情绪的一个小段。

可以将其看成是一段微型面完整的歌曲，因此在它的开始和结束处要有较为明确的表示，但因其只是整首歌曲的一部分，这种表示应比整首歌曲的起、止处稍弱，所以可以配一些半终止式的和弦，即前面讲过的副和弦，当然配主和弦也是可以的。这样，歌曲的基本骨架就搭好了。

三、确定每小节主要音，配上相应和弦

从歌曲的第一小节开始，看看该小节里面哪几个音最多，哪几个音的时值最长，找出含有这几音最多的和弦作为该小节的和弦。比如对歌曲《九百九十九朵玫瑰》第一小节，该小节1和6就占了音数的一半，且加起来的时值最长，那么1和6是主要音，如果是C调的话，则可以配上Am和弦，即A小调的主和弦。

要说明的一点是，确定和弦时，时值的长度要优先于音数的多少，这个道理是显面易见的。比如这样一个小节1--75，7和5占了两个音，是否该配G和弦：呢?不是的，因为从时值上看仍然是1占得时间长，所以应配以含1的和弦，如C和弦：1、3、5等。按照这个基本原则可以初步为所有小节确定和弦。

四、用和弦的倾向性优化和弦进行

通过上面两步，歌曲和弦的大致面貌已经出来了。但还不够，我们还要用和弦的倾向性来优化和弦的进行。首先，可以在全曲和乐句的终止的前使用属七和弦，以达到更加明确的终止效果。

在歌曲的其它部位的主和弦前也可以用上属和弦和属七和弦。以C大调为例，在C前用上G或G7，可以达到完美的终止效果。

五、用副属和弦和离调和弦做修饰

以上几步的基础上我们还可以根据歌曲的具体情况，进一步用副副属和弦和离调和弦进一步美化和声。比如在A弦前可以尝试使用E或E7和弦，很可能会有非常美妙的音响效果。但并不是所有歌曲都可以用副属和弦和离调和弦来修饰的，要慎用。

扩展资料：

两个或两个以上不同的音按一定的法则同时发声而构成的音响组合。

1、和弦，是和声的基本素材，由3个或3个以上不同的音，根据三度叠置或其他方法同时结合构成，这是和声的纵向结构。

2、和声进行，指各和弦的先后连接，这是和声的横向运动。补充一句和声有明显的浓，淡，厚，薄的色彩作用；还有构成分句，分乐段和终止乐曲的作用。

参考资料：和声 百度百科

和声搜索算法是用来优化音乐创作的一种算法。和声搜索算法(Harmonysearch，HS)是一种新兴的智能优化算法，通过反复调整记忆库中的解变量，使函数值随着迭代次数的增加不断收敛，从而来完成优化。算法概念简单、可调参数少、容易实现。类似于模拟退火算法对物理退火的模拟、遗传算法对生物进化的模仿、以及粒子群优化算法对鸟群的模仿等，和声算法模拟了音乐演奏的原理，是2001年韩国学者GeemZW等人提出的一种新颖的智能优化算法。算法模拟了音乐创作中乐师们凭借自己的记忆，通过反复调整乐队中各乐器的音调，最终达到一个美妙的和声状态的过程。

---