基于余弦相似度改进蝴蝶优化算法-附代码_余弦相似测度的改进

基于余弦相似度改进蝴蝶优化算法

摘要：针对蝴蝶优化算法（BOA）容易陷入局部最优和寻优精度低等问题，本文提出一种多策略改进的蝴蝶优化算法（MSBOA）。该算法首先引入余弦相似度位置调整策略，通过旋转变化算子和伸缩变换算子进行位置更新，有效的保持算法的种群多样性。其次引入动态切换概率，平衡算法局部阶段和全局阶段的转换。最后增加混合惯性权重策略，提高算法的收敛速度。

1.蝴蝶优化算法

基础蝴蝶优化算法的具体原理参考，我的博客：https://blog.csdn.net/u011835903/article/details/107855860

2. 改进蝴蝶优化算法

2.1 基于余弦相似度位置更新策略

余弦相似度反应两个向量方向一致性关系。取值范围为［ -1 ，1］，其中 1表示两个向量之间的夹角为 0度，有重合部分，-1表示两个向量方向相反。由于蝴蝶算法的特点，在迭代中后期，蝴蝶飞行围绕当前最优蝴蝶位置，甚至于飞行过程中出现重叠的现象，很难保持种群的多样性，引入余弦相似度衡量最优蝴蝶位置与周围蝴蝶的分布情况，通过构造当前蝴蝶个体位置和最优个体之间的向量，余弦相似度为分布情况的
指标，更新余弦相似度较高且适应度较差的蝴蝶个体位置，既加快算法收敛的速度，也保持了种群的多样性。策略具体细节如下：
首先构建 $a,b$ 向量:
a = x i t − g ∗ b = x j t − g ∗ (5)

$$\begin{aligned} a &=x_{i}^{t}-g^{*} \\ b &=x_{j}^{t}-g^{*} \end{aligned}$$ \tag{5} ab​=xit​−g∗=xjt​−g∗​(5)
其中第 $t$ 次迭代的当前蝴蝶位置, 即第 $i$ 个位置, 记为 $x_i^t\circ x_j^t$ 表 示第 $t$ 次迭代其他蝴蝶位置中的一个, $g^{\ast }$ 属于第 $t$ 代中的最优 蝴蝶的位置。
定义 ${\cos }_j(\mathbf{a},\mathbf{b})$ 为两个向量之间的相似度, 取值范围为 $[-$ $1,1]$, 个体位置之间相似度计算公式为:
$$\cos j(a,b)=\frac{a\cdot b}{|a||b|}\text{\hspace{1em}(6)}$$
其中分子为向量 $a,b$ 的内积, 分母分别为向量 $a,b$ 的模。余弦 相似度越高, 代表蝴蝶个体 $x_i^{\prime }$ 和 $x_j^{\prime }$ 越容易在方向上的重合。 将当前蝴蝶位置 $i$ 与其他蝴蝶位置 $j$ 依次计算余弦相似度, 并 设置阈值 $C$ 将与当前蝴蝶位置余弦相似度较高的个体进行监 选, 通过比较当前个体与笑选后个体的适应度, 将适应度较 差的个体位置引人状态转移算法中的旋转变换算子或伸缩变 换算子 ${}^{[14]}$ 进行位置更新, 并保留适应度较高的个体位置, 更新 公式如下：
$$\{\begin{array}{ll}{x}_j^t=g^{\ast }+\alpha \frac{1}{n{\Vert x_j^t\Vert }_2}{\mathbf{R}}_r{g}^{\ast }& f\left(x_j^t\right)⩾f\left(x_i^t\right)\\ x_i^t=x_i^t+\delta {\mathbf{R}}_e{\mathbf{x}}_i^t& \text{ otherwise }\end{array}\text{\hspace{1em}(7)}$$
其中 $f\left(x_i{}^t\right)$ 和 $f(x_j{}^t$ ) 分别为蝴蝶个体 ${\mathbf{x}}_i^{\prime }$ 和 ${\mathbf{x}}_j{}^{\prime }$ 适应度值, $\alpha$ 为旋转 因子; $R_r\in {\mathbf{R}}^{n^{\ast \ast }}$ 是一个其元素取值在 $[-1,1]$ 之间均匀分布的 随机矩阵, $\Vert \cdot \Vert$ 为向量 2-范数, 理论上能将位置旋转到以半径 为 $\alpha$ 的任何位置。 $R_e\in {\mathbf{R}}^{n^{\ast }n}$ 是一个其非零元素取值服从高斯 分布随机对角矩阵, 从理论上看, 能将位置伸缩到服从 $\delta$ 的范 围内。

2.2 根据适应度动态调整转换概率策略

基本的蝴蝶算法中, 切换概率 $P$ 值, 使用固定的常量来调 整局部搜索和全局搜索。本文采用文献 $[15]$ 所提出的自适应 机制来描述切换概率,并且做了改进。如公式(8)所示。
$$P_i^t=P_{\min }+\left(\frac{\log \left(\left|f_{\min }^t\right|\right)+\left|f_{\min }^t\right|}{\log \left(\left|f_i^t\right|\right)+\left|f_i^t\right|}\right)\times \left(P_{\max }-P_{\min }\right)\text{\hspace{1em}(8)}$$
$P_i^{\prime }$ 是在第 $t$ 次迭代中第 $i$ 只蝴蝶位置的切换概率, 其中 $P_{\text{min }}$, 中的最好适应度, 而 $f_i^{\prime }$ 是第 $t$ 次迭代中的第 $i$ 只蝴蝶的适应度。 蝴蝶位置对应的适应度接近最优的适应度时, 其切换的概率 接近大值, 更容易进人全局的引导; 反之当前个体的适应度与 最好的适应度相差较大时, 其转换概率接近最小值, 更容易进 人局部的引导。这样有利于将好的个体引导全局, 较差的个 体得到更多的机会引导。

2.3 自适应混和惯性权重

本文还在全局搜索阶段当前个体的位置更新公式 (3) 中 引人动态惯性权重 $w$ 来影响更新蝴蝶的位置, 惯性权重较大 或者较小都有可能引起算法陷人局部最优, 从而影响算法得 效率。为了协调算法的全局和局部搜索能力引人了自适应惯 性权重(9)。
$$w=\beta \times \left(1-\frac{\exp \left(\left|f_{\min }^t\right|\right)+\left|f_{\min }^t\right|}{\exp \left(\left|f_i^t\right|\right)+\left|f_i^t\right|}\right)+K\text{\hspace{1em}(9)}$$
其中 $K$ 为调整过的 sigmoid函数 (10):
$$K=1-1/(1+\exp (-(15t-7\text{ Niter })/\text{ Niter }))\text{\hspace{1em}(10)}$$
$K$ 值是调整过的 sigmoid函数, 该函数是神经网络中最常 用的激活函数之一。该函数在线性和非线性之间展现出极好 的平衡性, 拥有平滑的上界域和下边界域。在迭代前期参数 $K$ 能保持较大值, 延长初期阶段的全局搜索能力和强度。伸 缩的范围较大, 保留个体的多样性。中期 $K$ 值随着迭代次数 的增加而减少, 从而加快算法的收敛速度。在迭代后期的一 段保持一个较小的权重, 延长了迭代后期的局部搜索时间, 更 有利于进行局部搜索, 更新后的全局阶段搜索过程为公式 (11)表示。
$${\mathbf{x}}_i^{t+1}=w{\mathbf{x}}_i^t+\left(r^2\times g^{\ast }-{\mathbf{x}}_i^t\right)\times f\text{\hspace{1em}(11)}$$
权重引人了式 (9)的一部分, 其目的在于在控制最优蝴蝶 位置对新的蝴蝶位置的影响程度, 参数 $\beta$ 为影响程度因子, 蝴 蝶个体适应度接近当前最好的适应度时, 其权重接近最小值, 较小的权重有利于进行局部开发; 反之当前个体的适应度与 最好的适应度相差较大时, 其权重接近最大值, 保留当前个体 的更多信息, 下一次迭代保持较强的全局搜索能力。

多策略改进蝴蝶优化算法 (MSBOA)的基本流程如下:
Step 1: 初始化。初始化算法参数, 随机生成种群位置, 计 算适应度并择优保存。

Step2: 蝴蝶位置更新阶段。根据公式 (5)构建向量, 并根 据式 (6) 计算蝴蝶个体位置的余弦相似度, 设置阈值 C将相似 度高于阈值的蝴蝶位置通过公式(7)进行位置更新。

Step3: 计算当前个体适应度, 并根据公式 (8) 计算 $P$ 值判 断当前迭代当前个体是进行全局搜索还是局部搜索, 并通过 式 (10)计算当前个体的自适应惯性权重, 对应更新蝴蝶位置 的更新公式 (12)或(4)。

Step4: 计算位置更新后每只蝴蝶所在位置适应度, 并且 更新最优位置。

Step 5 : 重复 Step 2, Step 3 和 Step 4 的更新迭代过程, 若达到 设置收玫精度要求或规定的最大迭代次数, 终止算法并输出 最优解。

3.实验结果

4.参考文献

[1]陈俊,何庆.基于余弦相似度改进蝴蝶优化算法[J/OL].计算机应用:1-10[2021-04-28].http://kns.cnki.net/kcms/detail/51.1307.TP.20210305.0941.002.html.

5.Matlab代码

6.Python代码