联系方式:860122112@qq.com

和声搜索算法(Harmony search, HS)是一种新兴的智能优化算法,通过反复调整记忆库中的解变量,使函数值随着迭代次数的增加不断收敛,从而来完成优化。算法概念简单、可调参数少、容易实现。

类似于模拟退火算法对物理退火的模拟、遗传算法对生物进化的模仿、以及粒子群优化算法对鸟群的模仿等,和声算法模拟了音乐演奏的原理,它是 2001 年韩国学者 Geem Z W 等人提出的一种新颖的智能优化算法。算法模拟了音乐创作中乐师们凭借自己的记忆,通过反复调整乐队中各乐器的音调, 最终达到一个美妙的和声状态的过程。
举个例子:
假设一个需要优化的函数 f(X) <script type="math/tex" id="MathJax-Element-61">f(X)</script>,且 X={x1,x2,,xn}Rn <script type="math/tex" id="MathJax-Element-62">X=\{x_1,x_2,\cdots,x_n\}\in R^n</script>。那么,可以把 X <script type="math/tex" id="MathJax-Element-63">X</script>看成一个由n<script type="math/tex" id="MathJax-Element-64">n</script>个成员组成的乐队,他们用不同的乐器演奏出来音乐 xi <script type="math/tex" id="MathJax-Element-65">x_i</script>的和声对应 X={x1,x2,,xn} <script type="math/tex" id="MathJax-Element-66">X=\{x_1,x_2,\cdots,x_n\}</script>, f(X) <script type="math/tex" id="MathJax-Element-67">f(X)</script>可以看成是对这组和声的评价,成员们根据评价不断调整自己演奏的 xi <script type="math/tex" id="MathJax-Element-68">x_i</script>(搜索过程),直到评价达到要求。

一. 一般HS算法步骤

(1)定义问题和参数值
a. 假设一个最小化问题,即:
minf(X)X={x1,x2,,xn}Rn <script type="math/tex" id="MathJax-Element-9">minf(X),X=\{x_1,x_2,\cdots,x_n\}\in R^n</script>

b. 确定参数值

  • 和声记忆库的大小HMS:理解成和声种群的大小
  • 和声记忆库取值概率HMCR:从现有种群(HM和声库)中拿出一个和声的概率
  • 音调微调概率 PAR:对拿出的和声进行微调的概率
  • 音调微调带宽 BW:微调的幅度
  • 创作的次数 Tmax:调整(迭代)的次数

(2)初始化和声记忆库HMS
X <script type="math/tex" id="MathJax-Element-10">X</script>的解空间里随机生成 HMS 个和声(理解成种群)X1,X2,,XHMS<script type="math/tex" id="MathJax-Element-11">X^1,X^2,\cdots,X^{HMS}</script>放入和声记忆库,并记录对应的 f(X) <script type="math/tex" id="MathJax-Element-12">f(X)</script>,和声库的形式为:

HM=X1X2XHMS=x11x21xHMS1x12x22xHMS2x1nx2nxHMSn|f(X1)|f(X2)|f(XHMS)
<script type="math/tex; mode=display" id="MathJax-Element-13">\begin{equation} HM=\left[ \begin{matrix} X^1\\ X^2\\ \vdots\\ X^{HMS} \end{matrix} \right]= \left[ \begin{matrix} x_1^1&x_2^1&\cdots&x_n^1&|f(X^1)&\\ x_1^2&x_2^2&\cdots&x_n^2&|f(X^2)&\\ \vdots&\vdots&\vdots&\vdots&\vdots&\\ x_1^{HMS}&x_2^{HMS}&\cdots&x_n^{HMS}&|f(X^{HMS})& \end{matrix} \right] \end{equation}</script>

(3) 生成一个新的和声
[0,1] <script type="math/tex" id="MathJax-Element-14">[0,1]</script>之间产生一个随机数 r1 <script type="math/tex" id="MathJax-Element-15">r_1</script>,与HMCR进行比较

  • r1<HMCR <script type="math/tex" id="MathJax-Element-16">r_1
  • 否则,从解空间随机生成一个和声变量
  • 由上得到一个和声变量,若这个和声变量是从和声库中得到的,就需要对这个和声变量进行微调,在[0,1]之间产生一个随机数 r2 <script type="math/tex" id="MathJax-Element-17">r_2</script>
  • r2<PAR <script type="math/tex" id="MathJax-Element-18">r_2 BW <script type="math/tex" id="MathJax-Element-19">BW</script>来对得到的和声变量进行调整,得到一个新的和声变量
  • 否则,不做任何调整

最后得到新的和声 Xnew <script type="math/tex" id="MathJax-Element-20">X^{new}</script>

(4)更新和声记忆库
Xnew <script type="math/tex" id="MathJax-Element-21">X^{new}</script>进行评估,即 f(Xnew) <script type="math/tex" id="MathJax-Element-22">f(X^{new})</script>,若优于 HM 中的函数值最差的一个,即 f(Xnew)<f(Xworst) <script type="math/tex" id="MathJax-Element-23">f(X^{new}) Xnew <script type="math/tex" id="MathJax-Element-24">X^{new}</script>代替HM中函数值最差的和声 Xworst <script type="math/tex" id="MathJax-Element-25">X^{worst}</script>;否则,不做修改。

(5)检查算法是否终止
重复步骤 (3)和 (4),直到创作(迭代)次数达到 Tmax 为止。

HS流程图:
这里写图片描述

算法
这里写图片描述

第11行的 UBj <script type="math/tex" id="MathJax-Element-26">UB_j</script>和 LBj <script type="math/tex" id="MathJax-Element-27">LB_j</script>是变量 xj <script type="math/tex" id="MathJax-Element-28">x_j</script>的上界和下界,即确定解空间范围;最后一行的 NI <script type="math/tex" id="MathJax-Element-29">NI</script>相当于前面提到的Tmax,即迭代次数。

二. 改进的HS算法(The improved harmony search (IHS) algorithm)

令PAR和BW能随迭代次数的变化而变化
这里写图片描述
初始化时先确定 PARmin,PARmax,BWmin,BWmax <script type="math/tex" id="MathJax-Element-30">PAR_{min},PAR_{max},BW_{min},BW_{max}</script>, t <script type="math/tex" id="MathJax-Element-31">t</script>为当前迭代次数,可以看出越往后PAR<script type="math/tex" id="MathJax-Element-32">PAR</script>和 BW <script type="math/tex" id="MathJax-Element-33">BW</script>越小。

二. 全局最优HS算法(Global best harmony search (GHS) algorithm)

先直接看算法
这里写图片描述

相比一般的HS,算法只改了一行(图中红框)。 xB <script type="math/tex" id="MathJax-Element-34">x_B</script>(对应上文是 XB <script type="math/tex" id="MathJax-Element-35">X_B</script>)表示的是和声库HM当前最好的和声,也就是从 xB <script type="math/tex" id="MathJax-Element-36">x_B</script>中随机挑选一个变量 k <script type="math/tex" id="MathJax-Element-37">k</script>作为新和声的第j<script type="math/tex" id="MathJax-Element-38">j</script>个变量。(注意 k <script type="math/tex" id="MathJax-Element-39">k</script>不一定等于j<script type="math/tex" id="MathJax-Element-40">j</script>)

二. 自适应全局最优HS算法(The self-adaptive GHS (SGHS) algorithm)
  • 变量生成规则修改:

    这里写图片描述

    相比GHS,SGHS的变量生成规则做了两处修改
    第一处修改意在增加变异,避免掉入局部最优解;第二处修改即把GHS对应行的 xB(k) <script type="math/tex" id="MathJax-Element-41">x_B(k)</script>改成 xB(j) <script type="math/tex" id="MathJax-Element-42">x_B(j)</script>,从HM中拿出的最好和声与当前要生成的变量在和声中的位置是相同的。因为如果像GHS那样,位置的不同有很大概率使新生成的和声 xnew <script type="math/tex" id="MathJax-Element-43">x_{new}</script>性能比 xB <script type="math/tex" id="MathJax-Element-44">x_B</script>糟糕。

  • 参数自适应
    在SGHS中,四个参数HMS, HMCR, PAR 和 BW,除了HMS是初始化后固定外,其他三个参数都是随迭代搜索而动态调整,其中HMCR和PAR为自适应调整。
    HMCR是从HM中选择一个和声的概率。 大的HMCR值有利于局部搜索,从而增加算法的收敛速度,而小的HMCR值增加了和声库的多样性。 通过广泛的模拟,Omran和Mahdavi提出,通常使用较大的HMCR值(即> = 0.9)更好。 PAR是从 xB <script type="math/tex" id="MathJax-Element-45">x_B</script>选择音调的调整率。 大的PAR值有利于将 xB <script type="math/tex" id="MathJax-Element-46">x_B</script>的信息传递到下一代,从而增强了算法在 xB <script type="math/tex" id="MathJax-Element-47">x_B</script>周围的局部开发能力,而小的PAR值使得新的和声向量能够通过扰乱和声库中相应维度的值, 从而扩大了搜索区域和增加和声库的多样性。 由于在搜索过程中局部利用和全局探索总是矛盾的,因此难以确定HMCR和PAR的值。
    在SGHS论文中,HCMR和PAR通过进入HM生成和声的历史记录而动态地调整适当的范围。假设HMCR(PAR)值服从均值HMCRm(PARm)为[0.9,1.0]([0.0,1.0])、标准差为0.01(0.05)的正态分布。最初,HMCRm(PARm)设定为0.98(0.9)。然后SGHS根据正态分布生成的HMCR(PAR)开始搜索。在迭代过程中,记录下 Xnew <script type="math/tex" id="MathJax-Element-48">X^{new}</script>成功替换HM中 Xworst <script type="math/tex" id="MathJax-Element-49">X^{worst}</script>时所对应的HMCR(PAR)的值。在经过指定迭代次数 LP <script type="math/tex" id="MathJax-Element-50">LP</script>(论文设为100)之后,通过求在此期间记录的所有HMCR(PAR)值的均值来重新生成HMCRm(PARm)。随着新的均值和固定的标准差0.01(0.05),产生新的HMCR(PAR)并用于随后的迭代。重复上述步骤。因此,可以逐渐学习适当的HMCR(PAR),以适应特定问题和特定阶段的搜索。

BW的调整
这里写图片描述
NI <script type="math/tex" id="MathJax-Element-51">NI</script>是需要迭代的总次数, t <script type="math/tex" id="MathJax-Element-52">t</script>是当前迭代次数。

SGHS算法:
这里写图片描述

博主之前做的是使用HS和SGHS优化FCMAC(模糊小脑神经网络),部分代码链接:
https://github.com/DajunZhou/SGHS-CMAC
参考文献
Pan Q K, Suganthan P N, Tasgetiren M F, et al. A self-adaptive global best harmony search algorithm for continuous optimization problems[J]. Applied Mathematics and Computation, 2010, 216(3): 830-848.

Logo

讨论HarmonyOS开发技术,专注于API与组件、DevEco Studio、测试、元服务和应用上架分发等。

更多推荐