智能优化算法：堆优化算法

摘要：堆优化算法(Heap-based optimizer，HBO)是 Askari 等人在 2020 年提出的一种新型智能优化算法。它利用堆结构模拟了公司的层级结构，采用了堆的概念形成个体之间的交互，并且构建了三种构造新解的数学模型。具有收敛速度快，精度高的特点。

1.算法原理

HBO 模拟公司层次结构建立的树状结构，目前它选择的是三元堆或者说是一个三叉树，具体详见图 1。企业等级制度的最终目标是以最好的方式完成与业务相关的任务，主要包括三个数学模型:下属与直接领导的交互、与同事的交互和个体的自我贡献。

图1.三元堆

图1中$X_1$所在的层次为最高层第一层，仅有一个个体(其适应度值最高，为最优个体)，；$X_2\sim X_4$所在的层次为第二层，3 个个体(它们的适应度值低于第一层个体的适应度值，以下类似)；$X_5\sim X_{13}$ 所在的层次为第三层，9 个个体；如此，第四层应该有 27 个体；所有这些个体组成一个群体，其种群大小为 40。其中，第一层至第三层在本文中称为高层，第四层为低层(其中个体的适应度值低于高层个体的适应度值)。从 $X_2$开始所有的个体都是通过直接领导和同事的引导进行更新。以 $X_8$ 为例，由于堆独特的结构，与 $X_8$ 在同一层次的个体均为其同事，为 $X_5{X}_{13}$ ，且只有一个直接领导 $X_3$ 。然而对于最高领导$X_1$ ，它所在的层是最高层，没有直接领导，并且该层只有$X_1$ 一个个体，也不存在同事。

与直接领导交互的数学模型可以描述为:
$$X_i^j(t+1)=B^j+\gamma \lambda |B^j-X_i^j(t)|\text{\hspace{1em}(1)}$$

$$\gamma =|2-4\ast mod(t,25)/25|\text{\hspace{1em}(2)}$$

$$\lambda =2r-1\text{\hspace{1em}(3)}$$

其中，$t$ 是当前迭代次数，$T$ 是最大迭代次数，$j$ 是一个解向量的第 $j$ 个分量，$B$ 是当前个体的直接领导。$r$ 是均匀分布在[0,1]中的随机数。在迭代过程中，$\gamma$ 是一个三角波，它的值在 1 的左右波动，从 2 到 0，或从 0 到 2。

在堆中，位于同一层的个体都是其同事，每个个体$X_i$根据其随机选择的同事$ S_r$ 更新其位置，其数学模型见式(4)。
$$X_i^j(t+1)=\{\begin{array}{l}{S}_r^j+\gamma \lambda |S_r^j-X_i^j(t)|,f(S_r)<f(X_i(t))\\ X_i^j+\gamma \lambda |S_r^j-X_i^j(t)|,else\end{array}\text{\hspace{1em}(4)}$$
其中，$f$ 是个体的目标函数。对于最小极值问题，若 $f(S_r)<f(X_i)$，个体可以探索 $S_r$ 周围的区域；若 $f(S_r)\ge f(X_i)$，个体可以探索 $X_i$ 周围的区域，以保证搜索向好的方向发展。

在个体的自我贡献的模型中，个体在前一次迭代中的一些位置信息会一直保留到下一次迭代。即个体$X_i$ 在下一次迭代中不会改变其第$j$个分量的值。
$$X_i^j(t+1)=X_i^j(t)\text{\hspace{1em}(5)}$$
在 HBO 中，$p_1$ ，$p_2$ 和$p_3$决定了个体将会在这三个数学模型中选择哪个模型进行更新。选择概率的计算方法如下:
$$p_1=1-t/T\text{\hspace{1em}(6)}$$

$$p_2=p_1+(1-p_1)/2\text{\hspace{1em}(7)}$$

HBO 通过 $p_1$ 选择自我贡献模型更新个体，通过$p_2$ 选择与直接领导交互的数学模型更新个体，通过$p_3$ 选择与同事交互的数学模型更新个体，其中$p_3=1$

算法 1: 堆优化算法
Step1: 设置参数并随机初始化种群
Step2: 评估种群中个体的适应度值，获取全局最优解
Step3: 构建堆
Step4: for t=1 to T do
Step5: for i= N to 2 do
Step6: for j=1 to D do
Step7: p=rand
Step8: if p≤p 1
Step9: 通过公式（5）更新个体位置
Step10: else if p > p 1 & p ≤ p 2
Step11: 通过公式（1）更新个体位置
Step12: else
Step13: if p > p 2 & p ≤ p 3
Step14: 通过公式（4）更新个体位置
Step15: end if
Step16: end if

Step17: end for
Step18: 边界控制，计算个体的适应度值
Step19: 贪心选择更新种群
Step20: 更新堆，更新全局最优解
Step21: end for
Step22: end for
Step23: 输出全局最优解

2.算法结果

3.参考文献

[1]Qamar Askari,Mehreen Saeed,Irfan Younas. Heap-based optimizer inspired by corporate rank hierarchy for global optimization[J]. Expert Systems With Applications,2020,161:

[1]张新明,温少晨,刘尚旺.差分扰动的堆优化算法[J/OL].计算机应用:1-9[2021-12-11].http://kns.cnki.net/kcms/detail/51.1307.TP.20211014.1631.021.html.

4.Matlab代码