和声搜索算法调优

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

（以下描述，均不是学术用语，仅供大家快乐的阅读）
和声搜索算法（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,仅供参考

目录
上一篇 优化算法笔记（二十五）飞蛾扑火算法
下一篇 优化算法笔记（二十七）蜉蝣算法

❷ 优化算法笔记（二十七）蜉蝣算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
蜉蝣算法（mayfly optimization algorithm）是根据蜉蝣的飞行和繁衍行为提出的优化算法。该算法提出与2020年（论文接收在2019年），算是一个新算法。算法的流程和结构其实与蜉蝣的关系不大，可以看作是对粒子群的一个修改。
蜉蝣算法中群体分为雄性和雌性，雄性的行为与粒子群相似，通过全局最优和自身历史最优移动，而雌性则是向优于自己的配偶移动，若配偶弱于自己则自行局部搜索。然后这对雌性和雄磨搭孝性会产生两个后代，并保留群体中的较优个体。
算法的流程结构都有些许复杂，不过有粒子群基础的小伙伴应该能很好的理解。

这次我们的主角就是蜉蝣了（虽然关系不太大）。
蜉蝣算法中有两种角色，雄性蜉蝣和雌性蜉蝣，其数量均为N/2,N为群体总数, 其位置为 ,速度 为了方便描述，下面使用XM表示雄性蜉蝣的位置，XF表示雌性蜉蝣的位置。

整个算法的每次迭代流程大致可以分为四步：
1. 将蜉蝣群体均分为雄性组和雌性组，每组内按优劣顺序排列。
2. 雄性个瞎稿体移动
3. 雌性个体移动
4. 雄性雌性交配产生两个后代
5. 在这2N个个体中选出N个作为下一代
可以看出每次迭代算法产生了2N个新个体，所以说蜉蝣算法的计算速度会比其他算法更慢，因为蜉蝣算法多计算了N个个体的适应度值。（其他大多数算法每次迭代只计算N个值）。
由于1.分组和5.选择比较简单，不需要再详细描述，下面只介绍2,3,4这三个步骤。

雄性蜉蝣的移动方式与粒子群中的粒子相似枝携，新位置当前位置和速度决定：

其中 表示第n代群体中的第i个个体的第j维的位置。
其速度则有以下公式决定：

其中如果该个体使群体中的最优个体则使用公式（3）进行移动，其他个体则使用公式（2）进行移动。 表示第n代群体中的第i个个体的第j维的速度，pbest为该个体所到过的最好位置，gbest为全局最好位置，a1,a2,beta为常数，一般取值为2，rp为当前位置与pbest的欧式距离，rg为当前位置与gbest的欧式距离，e为自然常数，d为常数，一般取值为0.1，r为[-1,1]内的随机数。
公式2是不是和粒子群的速度更新公式很像？下面是粒子群的速度更新公式

与粒子群相比雄性蜉蝣的速度更新公式将两个随机数r1与r2替换成了与距离相关的值，个人认为这不是一个好的修改，不过后面可以看出，该改动为算法提供了强大的局部搜索能力。
下面做一个试验：现在将蜉蝣算法中所有个体全部划分为雄性，即没有雌性的搜索行为和交配产生后代的行为。也可以认为是在粒子群算法中将公式（3）替换为公式（2），我们看看效果。（唯一不同的是蜉蝣算法中雄性中的全局最优个体使用公式（3）进行移动）。

可以看出，只有最优个体在缓慢的移动，并且在略过最优解附近后仍在移动。问题出在哪呢？

有两个原因：
1 .如下公式的值

我们上述的实验中取值范围（-100,100），初始化时两个个体之间的欧式距离r的取值范围在10以下的都比较少，此时自身的历史最优就是自己本身，也不会产生速度。
当r=10时，其分母为e^200,其值约等于0，此时公式（2）如下

即速度不会发生任何变化。
下面，我们把解空间缩小100倍看看效果。

可以看出仅仅是修改了取值范围，雄性蜉蝣们的行为就发生了巨大的改变。因为距离参数会受到解空间范围的影响，当距离足够小时，公式（2）中的距离参数所算出的速度不在是0，所以雄性蜉蝣们便活跃了起来。
当然这是一个不好的现象，算子不应该受解空间范围改变有如此大的影响。

2 .初始速度
每个蜉蝣都有初始速度呀，就像粒子群一样，所以一开始应该也会移动。
蜉蝣确实有初始速度，不过速度的每一维都是0。为什么呢？不能是一个不是0的值吗？可以但又不完全可以，因为蜉蝣算法没有给出速度的上下限范围，没有范围就无法初始化到该范围内的值。作者将速度的上下限作为了一个改进点放到了文章的后部！
结合上述1,2两点，雄性个体中除最优个体外，其他个体的速度几乎都是0，可以说是以肉眼不可见的方式在缓慢移动。或者也可以理解为该步骤的主要作用是局部搜索，当个体之间距离较远时则不会移动，将雄性单独拿出来实验是没有意义的。如果必须单独拿出来用则需要设置速度上下限，并在初始化中为个体设置随机速度。
其实论文中的速度上下限，以及惯性系数递减等粒子群中已有的步骤，完全可以直接沿用到原始的蜉蝣算法中，而不应作为改进单独拎出来说明。此处也可以直接沿用粒子群算的速度更新公式。

每只雌性个体会有自己对应的雄性个体作为配偶，雌雄两组顺序配对，即最优的雌性配对最优的雄性，次优的雌性配对次优的雄性。
雌性的移动方式为向由于自己的配偶移动，若配偶弱于自己则自行搜索。
其位置的计算公式与雄性相同均为公式（1），速度的更新公式如下：

其中xm为该雌性个体配对的雄性个体的位置，xf为该雌性个体的位置，rmf为这两只蜉蝣之间的位置，fl为常量一般取值为0.1，r为[-1,1]内的随机数。
当该雌性个体差于雄性个体时，使用公式(7)中的上式，当雌性个体优于该雄性个体时，使用公式(7)中的下式。
与雄性的速度更新公式相似的问题，因为距离参数rmf的值可能非常大，会导致公式(7)中的上式做小范围的局部搜索，速度更新幅度较小。可以试着用随机数去代替距离参数：

其中r2为[0,1]内的随机数。

交配行为中一对雌性和雄性会产生两个后代，其产生公式如下：

其中L为随机数，取值范围应该是(0,1),xm为雄性蜉蝣，xf为雌性蜉蝣，可以看出产生的两个个体关于这对雌性的中心对称。该步骤为蜉蝣算法提供了全局搜索能力，并结合选择操作加快了算法的收敛速度。

整个蜉蝣算法的流程如下：

其流程看上去还是挺简单的，不过由于分了雌性和雄性两种，导致所需操作的步骤细节很多，同时由于父辈母辈更新自身位置后还产生了后代，其实每次迭代计算了2N个个体的适应度值，导致其速度慢。

适应度函数 。
实验一 ： 原算法

从图像可以看出，蜉蝣算法的收敛速度非常的快，在解附近聚集后群体仍然能够移动并向着正解运动，并最终收敛在正解附近。和之前的全是雄性蜉蝣的实验大相径庭，应该是因为交配产生的后代优于了父辈母辈，父辈母辈被替代了，所以看上去移动了。当距离变小后，雌性雄性蜉蝣的速度更新公式则开始生效了。

不过，结果并不太好，但是在预期内，可以看出，其精度是非常高的，但是算法不太稳定，会出现非常差的结果。
因为距离较远时全靠着交配产生的后代更新位置，此时会快速收敛到当前的最优个体附近。当距离变小后，雌性和雄性的速度更新公式开始生效，此时的群体较为集中，其运动轨迹就像贪吃蛇一样。
综上，可以看出算法的前期收敛很快，算法的局部搜索精度很高，同时全局搜索能力较弱，依靠局部搜索花上跟多时间也能找到最优解。由于全局搜索能力不强，且收敛过快，算法应该比较容易陷入局部最优。
实验二 ： 去除距离操作，还原成类似粒子群的速度更新方式，使用公式（4）（8）

实验二的图像中蜉蝣的收敛速度比实验一中慢了一点，而且也没有那么集中，最终也聚集在了正解附近，这个图像其实和粒子群也有了几分相似。不过由于选择操作的作用，蜉蝣算法的总是会收敛的更快，即使设置了速度上限依然如此，因为即使该个体迭代数次可以飞到最优解，但后代可是可以直接降生与最优解附近的，如此一来该个体会被取代，剩下的个体则集中在了最优解附近。

从结果上看，实验二损失了不上精度有点不能接受，但是也稳定了不少，局部搜索能力也有所削弱。蜉蝣算法的收敛行为主要由交配繁衍后代和选择下一代来提供，如果要调整其搜索速度需要修改交配操作。原论文中也写出了相关的改进，如，父代母代产生一雌一雄两个子代，子代雄性优于父代则保留，子代雌性优于母代则保留。此处不再赘述，可以阅读原文。

蜉蝣算法受雌雄蜉蝣的运动和交配产生后代的行为启发而提出的优化算法，个人感觉该算法与蜉蝣关系不大，而是更像是对粒子群的一种改进。算法的流程较为复杂，不过有粒子群作为基础也很好理解。算法的性能比我想象的要好，其中雌性和雄性的移动为算法提供了局部搜索能力，而交配繁衍后代进行选择提供了全局搜索能力。算法的局部搜索能力很强但是稳定性较差，容易陷入局部最优。由于每次迭代产生了更多的新个体数，为了保证公平，它的迭代次数应为其他算法的1/2。
其实原文中还有许多的优化和改进步骤，这里也不一一实验了，还是推荐去看看原论文。
看到蜉蝣算法，想起了之前一个写着玩的算法，也是将种群分为了雌雄两类。不过没有蜉蝣算法这么复杂的操作，只是通过雌雄交配产生后代进行更新迭代，通过母辈生育有几率死亡以及近亲繁殖的后代有几率死亡来控制跳出局部最优，效果中规中矩，不提了。

参考文献
Zervoudakis, K., Tsafarakis, S., A mayfly optimization algorithm, Computers &
Instrial Engineering (2020) 提取码：ogl4
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（二十六）和声搜索算法
下一篇 优化算法笔记（二十八）蝗虫算法

❸ 元启发式算法和启发式算法有什么区别

启发式算法与元启发式算法对区别在于是否存在“随机因素”。 对一个同样的问题，启发式算法（heuristics）只要给定了一个输入，那么算法执行的步骤就固定下来了，输出也因此固定，多次运算结果保持一致。

而元启发式算法（meta－heuristics）里面包括了随机因素，如GA中的交叉因子，模拟退火中的metropolis准则，这些随机因素也使得算法有一定概率跳出局部最优解而去尝试全局最优解，因此元启发式算法在固定的输入下，而输出是不固定的。

启发式算法(Heuristic Algorigthm)是一种基于直观或经验构造的算法,在可接受的花费(指计算时间、计算空间等)给出待解决优化问题的每一实例的一个可行解，该可行解与与最优解的偏离程度一般不可以事先预计。

启发式算法是一种技术,这种算法可以在可接受的计算费用内找到最好的解,但不一定能保证所得到解的可行性及最优性，甚至大多数情况下无法阐述所得解与最优解之间的近似程度。

元启发式算法（MetaHeuristic Algorigthm）是启发式算法的改进，它是随机算法与局部搜索算法相结合的产物，常见的启发式算法包括遗传算法、模拟退火算法、禁忌搜索算法及神经网络算法等。

新兴的元启发式算法有、粒子群优化算法、差分进化算法，蚁群优化算法、萤火虫算法、布谷鸟算法、和声搜索算法、差分进化算法、随机蛙跳算法、细菌觅食算法、蝙蝠算法的算法等。