和声搜索算法（HS）及其MATLAB实现

mypro334 · 发表于 2023-1-5 20:36

1 概述

在工程领域，解决函数优化问题的算法很多，常见的有遗传算法、微粒群算法和模拟退火算法等。近年来，一种新出现的现代启发式全局搜索算法——和声搜索(Harmony Search, HS)算法在函数优化问题中得到了成功应用。
基本和声搜索算法是对音乐演奏中乐师们凭借自己的记忆，通过反复调整乐队中各乐器的音调，最终达到一个美妙和声状态过程的模拟。
HS算法将乐器 i（i=1,2，...，m）类比于优化问题中的第 i 个决策变量，各乐器声调的和声H_{j}（j=1,2，...，M）相当于优化问题的第 j 个解向量，评比类比于目标函数。算法首先随机产生 M 个初始解（和声）放入和声记忆库（Harmony Memory, HM）内，根据记忆考虑、微调扰动、随机选择3个规则产生新解，然后判断新解是否优于 HM 内的最差解，若是，则替换之；否则保持当前 HM 不变。上述过程不断重复，直至达到预定的迭代次数为止。
2 算法步骤

1.定义问题与参数值

（1）假设问题
如求解最小值问题，目标函数为 minf（X）.X=\left\{ x_{1} ，x_{2} ，x_{3} ，...，x_{n} \right\} 。
（2）定义算法中的参数值

和声记忆库大小HMS（Harmony Memory）：和声种群的大小
和声记忆库取值概率HMCR(Harmony Memony Size)：从现有种群（HM和声库）中拿出一个和声的概率
音调微调概率 PAR(Ptich Adjusting Rate)：对和声进行微调的概率
音调微调带宽 BW：微调的幅度
创作的次数 NI：迭代的次数

2. 初始化和声记忆库HM

在 X 的解空间随机生成HMS个和声向量放入和声记忆库HM，并记录对应向量下的 f（X） ,生成的初始HM形式如下
HM=\begin{bmatrix} X^{1} \\ X^{2} \\ .\\ .\\ .\\ X^{HMS} \end{bmatrix}=\begin{bmatrix} x_{1}^{1}&x_{2}^{1}&...&x_{m}^{1} &f(X^{1})\\ x_{1}^{2}&x_{2}^{2}&...&x_{m}^{2} &f(X^{2}) \\ &&.&&.\\ &&.&&.\\ &&.&&.\\ x_{1}^{HMS}&x_{2}^{HMS}&...&x_{m}^{HMS} &f(X^{HMS}) \end{bmatrix}
3. 生成新和声向量

依据如下三个准则生成新和声向量 x^{,}=\left( x_{1}^{,} ,x_{2}^{,} ,...,x_{m}^{,} \right) ：记忆库取值、音调微调、随机选择
新和声中每个变量 x_{k}^{,}(k=1,2,...,m) 都有HMCR的概率取自HM中（ x_{k}^{1}，x_{k}^{2}，...，x_{k}^{HMS} ）中的任意一个值；相应地 x_{k}^{,} 有1-HMCR的概率在整个解空间内任意随机取值。
即新和声 x_{i}^{,}=\left\{ \begin{aligned} x_{i}^{,}& \in\left\{ x_{i}^{1},x_{i}^{2}...,x_{i}^{HMS} \right\},rand<HMCR\\ x_{i}^{,}& \in X_{i},else \end{aligned} \right.
式中，rand为[0,1]区间内均匀分布的随机数， X_{i} 为变量的定义域。
若新变量取自HM，为增加解的多样性以扩大搜索范围，变量有PAR的概率需要音调微调，
即 x_{i}^{,}=\left\{ \begin{aligned} &x_{i}^{,}+\left( 2\cdot rand^{,,}-1 \right)\cdot BW,rand^{,}<HMCR\\ &x_{i}^{,},else \end{aligned} \right.
式中，BW为音调微调带宽， rand^{,} 与 rand^{,,} 均为[0,1]区间内均匀分布的随机数。
由此可以的到新的和声向量 X^{,} 。
4.更新和声记忆库

评估新生成的和声向量 X^{,} 的性能（计算该向量下的 f（X^{,}）），若强于HM中适应性最差的和声，则将其替换，否则淘汰该新和声，以此更新和声记忆库HM。
5.确定是否满足迭代停止条件

重复步骤3.4.直到迭代次数达到NI为止，并输出HM中最优的一组和声。

基本HS算法流程

3 优化示例与MATLAB实现

3.1 多基地声纳探测系统的阵位优化

利用和声搜索算法，对多基地声纳探测系统的阵位进行寻优，待优化变量为 m 个发射平台和 n 个接收平台的坐标，适应度函数为多基地声纳系统的探测性能评估模型，适应度值为声纳系统的覆盖率。
在算法中，设 HMS=5,HMCR=0.9,PAR=0.3,BW=0.01,NI=500 .
优化结果如下所示：

HS算法优化前后对比

HS算法迭代过程曲线

在阵位优化前后对比图中，“*”表示发射平台位置，“o”表示接收平台位置，迭代初始时，阵位位置严重靠近区域边缘，声纳系统效能受束缚，经过和声搜索寻优后，阵位得到改善，声纳系统的区域覆盖率由29.81%提升到51.03%。
4 总结

和声搜索算法在结构上与遗传算法（Genetic Algorithm, GA）具有相似性。两者在产生新成员的过程中都具有相似的重组与突变机制；都以随机的方式产生初始解，并依据“优胜劣汰、适者生存”的法则进行优化。在编码方式上，和声搜索算法利用十进制编码，省去了遗传算法中从十进制到二进制的编码步骤，应用更为简便；在依据旧解邻域搜索生成新解的过程中，和声搜索算法采用多点交配模式，遗传算法采用单点或双点交配模式，由此产生的新和声解会更具多样性，但对旧解的依赖程度降低，会导致和声搜索算法收敛较缓慢；和声搜索算法中的解有的概率能够逃离和声记忆库，并在解空间内随机生成新解，这提高了和声搜索算法跳出局部最优解的可能性，这种机制也是遗传算法中所没有的。
与粒子群算法（Particle Swarm Optimization, PSO）比较，和声搜索算法的优点可以概括为：算法结构简单，运算量低；有概率逃离历史解影响，易跳出局部最优解。
5 参考文献

[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]韩红燕,潘全科,梁静.改进的和声搜索算法在函数优化中的应用[J].计算机工程,2010,36(13):245-247.
[3]雍龙泉.和声搜索算法研究进展[J].计算机系统应用,2011,20(07):244-248.
[4]李士勇,李研,林永茂.智能优化算法与涌现计算[M].清华大学出版社.2019:604.
[5]邹佳运. 多声纳协同探测性能分析及参数优化研究[D].哈尔滨工程大学,2019.

——初稿于2022.12.11 河北
<hr/>
算法及MATLAB代码问题欢迎评论区或私信交流。
本文仅作为个人学习笔记，部分理论引用网络文献，若有侵权请联系博主删除。

		自动登录	找回密码
密码			立即注册

和声搜索算法（HS）及其MATLAB实现

本帖子中包含更多资源