【智能优化算法】蜣螂优化算法（Dung beetle optimizer, DBO），2023

前言

蜣螂（俗称屎壳郎）优化算法( Dung beetle optimizer, DBO), 是由 Jiankai Xue 等于2022年提出的一种群体智能优化算法。其灵感来源于蜣螂的生物行为过程，具有寻优能力强，收敛速度快的特点。

1. 蜣螂的生物行为

蜣螂是自然界中一种常见的昆虫，以动物的粪便为食，在全世界内分布广泛，扮演着自然界中分解者的角色，对生态系统平衡起着至关重要的作用。蜣螂有一个有趣的习惯，它们会把粪便捏成球，然后把它滚出来，目的是能够尽可能快速、有效地移动粪球，防止被其他蜣螂抢夺。

蜣螂的可以利用天体线索(特别是太阳、月亮和偏振光)来导航，让粪球沿着直线滚动，如果完全没有光源(也就是在完全黑暗的环境中)，蜣螂的就不再走直线，而是弯曲的，有时甚至略圆，有很多因素(如风、地面不平)都会导致蜣螂偏离原来的方向，蜣螂在滚粪球的过程如遇到障碍物而无法前进时，通常会爬到粪球上面"跳舞"(包括一系列的旋转和停顿)，决定它们的运动方向。

从蜣螂的习性中观察发现，其获取粪球主要有以下两个目的：
①用来产卵和养育下一代；
②作为食物。蜣螂会把粪球埋起来，雌性蜣螂会在粪球里产卵，粪球不仅是蜣螂幼虫的发育场所，也是必需的食物。所以，粪球对蜣螂的生存起着不可替代的作用。

本位介绍了一种新的群体智能优化算法------DBO（Dung beetle optimizer）技术，其灵感主要来源于蜣螂的滚球、跳舞、觅食、偷窃、和繁殖等行为。

蜣螂在仿生算法设计中主要有四个角色：

1. 滚球蜣螂：移动粪球到某个场所
2. 卵球（繁殖蜣螂）：雌性蜣螂产生的子代
3. 小蜣螂：四处觅食
4. 偷窃蜣螂：偷取粪球

2. 算法优化原理

2.1 滚球蜣螂（ball-rolling dung beetle）

2.1.1 无障碍物：太阳定位及自然因素影响

概述： 蜣螂在滚动过程中可以利用天体的线索(特别是太阳、月亮和偏振光)来导航，使粪球沿直线滚动，太阳光等会影响运动轨迹，呈弯曲或椭圆等；自然因素(如风和不平坦的地面)会导致蜣螂偏离原来的方向。

为了模拟滚球行为，要求蜣螂在整个搜索空间中沿着给定的方向移动。蜣螂的运动轨迹如图1所示。在图1中，蜣螂利用太阳来导航，其中红色箭头表示的是滚动的方向,同时，假设光源的强度也会影响蜣螂的路径。在滚动过程中，滚球蜣螂的位置更新，可以表示为：

$t$ 表示迭代次数，$x_i(t)$ 表示第 $t$ 次迭代时第 $i$ 只蜣螂的位置信息，$k\in (0,0.2]$ 是一个常数，表示偏转系数，$b\in (0,1)$ 的一个定值， $\alpha$ 是自然系数取 1 或 -1，-1表示偏离原方向，1表示无偏差，$X^w$ 是全局最差位置，$\Delta x$ 模拟光强的变化。

在式(1)中，适当选择两个参数 $k$ 、 $b$ 的值至关重要, $\alpha$ 代表诸多自然因素(如风和不平坦的地面)可使蜣螂偏离原来的方向。为模拟现实世界中的复杂环境, 通过概率法设 $\alpha$ 为 $1$ 或 $-1$，如算法 1 所示，当 $\alpha =1$ 时, 表示无偏差, 当 $\alpha =-1$ 时, 表示偏离原方向。同样, $\Delta x$ 的值越高表示光源越弱, 同时, $k$ 和 $b$ 分别设为 $0.1$ 和 $0.3$ 。利用 $\Delta x$ 有以下两个优点：

• (1) 算法在优化过程中, 可尽可能地彻底地探索整个空间;
• (2) 使算法具有更强的搜索性能, 从而避免陷入局部最优。 $X^w$ 通过控制 $\Delta x$ 的值, 来扩大搜索范围。

2.1.2 有障碍物：跳舞

当蜣螂遇到障碍物无法前进时, 就需要通过跳舞来重新定位, 目的是获得新的路线。为了模拟舞蹈行为, 用切线函数得到新的滚动方向。需要指出的是, 只需要考虑定义在区间 $[0,\pi ]$, 如图 2 所示。一旦蜣螂成功确定了一个新的方向, 它继续把球向后移。因此, 蜣螂的位置更新定义如下：

其中, $\theta$ 为挠度角, 属于 $[0,\pi ]$ 。 $|x_i(t)-x_i(t+1)|$ 表示第 $i$ 只蜣螂在第 $t$ 次迭代时的位置与其在第 $t-1$ 次迭代时的位置之差，因此蜣螂的更新与当前和历史信息相关。如果 $\theta =0,\pi /2,\pi$, 蜣螂的位置不更新。

2.2 卵球（brood ball）繁殖

在自然界中, 粪球是被蜣螂滚到安全的地方藏起来。为了给它们的后代提供安全的环境, 选择合适的产卵地点对蜣螂来说至关重要。模拟䧳蜣螂产卵的区域边界选择策略, 其定义为：

其中, $X^{\ast }$ 为当前局部最佳位置, $L{b}^{\ast }$和 $U{b}^{\ast }$ 分别为产卵区下限和上界, $R=1-t/T_{\max }$, $T_{\max }$ 表 示最大迭代次数, $Lb$ 和 $Ub$ 分别代表优化问题的下界和上界。

如图 3 所示, 当前局部最佳位置 $X^{\ast }$ 用一个大的棕色圈表示, 而 $X^{\ast }$ 周围的小黑圈表示卵球。 每个卵球中都蕴含一枚蜣螂卵, 红色的小圆圈代表边界的上下界。

一旦确定了产卵区域, 雌性蜣螂就会选择这个区域的卵球产卵。对于 DBO 算法, 每只雌蜣螂在每次迭代中只产一个卵。此外, 从式(3)中可以清楚地看到, 产卵区域的边界范围是动态变化的, 这主要是由 $R$ 值决定的。由此可见, 卵球的位置在迭代过程中也是动态的, 表示为：

$B_i(t)$ 为第 $t$ 次迭代时第 $i$ 个卵球的位置信息, $b_1$ 和 $b_2$ 表示大小为 $1\times D$ 的两个独立随机向量, $D$ 表示优化问题的维数。卵球的位置被严格限制在一定范围内。

2.3 小蜣螂（small dung beetle）觅食

一些已经长成成虫的蜣螂会从地下钻出来觅食, 我们称它们为小蜣螂, 还需要建立最优蜣螂区域来引导蜣螂觅食，最佳蜣螂区域的边界定义如下：

$X^b$ 表示全局最佳受食位置, $L{b}^b$ 和 $U{b}^b$ 分别为最优受食区域的下界和上界, 其他参数在式(3)中定义, 因此小蜣螂的位置更新如下：

其中, $x_i(t)$ 表示第 $t$ 次迭代时第 $i$ 只小蜣螂的位置信息, $C_1$ 表示一个服从正态分布的随机数, $C_2$ 表示属于 $(0,1)$ 的随机向量。

2.4 偷窃蜣螂（thief）

还有一些蜣螂被称为偷窃蜣螂, 会从其他蜣螂那里偷粪球，这是自然界中非常常见的现象。 从式 (5) 可以看出， $X^b$ 即最优的食物来源位置。因此, 可以假设 $X^b$ 即表示争夺食物的最佳地点。在迭代过程中, 偷穷蜣螂的位置更新信息定义如下：

其中, $x_i(t)$ 表示第 $i$ 个偷窃蜣螂在第 $t$ 次迭代时的位置信息, $g$ 是一个大小为 $1\times D$ 维的随机向量, 服从于正态分布, $S$ 表示恒定值。

偷窃蜣螂在优化过程中位置不断更新, 最后输出最佳位置 $X^b$ 。根据此算法更具体地说, 在 DBO 算法中, 一个蜣螂种群包括 $N$ 种目标代理, 其中代理 $i$ 都代表一组候选解, 第 $i$ 个代理的位置向量用 $x_i(t)$ 表示, $x_i(t)=\left(x_{i1}(t),x_{i2}(t),\dots \dots ,x_{iD}(t)\right)$ , 其中, $D$ 为搜索空间的维数。它们的分布比例没有指定, 可以根据实际应用问题进行设置。

3. 算法流程

DBO 算法作为一种新颖的基于 SI 的优化技术, 主要有六个步骤:

• (1) 初始化蜣螂群和 DBO 算法的参数;
• (2) 根据目标函数计算出所有目标代理的适应度值;
• (3) 更新所有蛲螂的位置;
• (4) 判断每个目标代理是否超出边界;
• (5) 更新当前最优解及其适应度值;
• (6) 重复上述步骤, 直到 t 满足终止准则, 输出全局最优解及其适应度值。

种群按照 6:6:7:11 的比例，将蜣螂划分成不同的角色。也就是说，按照图中的种群规模，在30个个体中，有6个蜣螂用于滚球行为，6个蜣螂用于繁殖行为，7个蜣螂被定义为小蜣螂，执行觅食行为，剩下的11个蜣螂都被定义为小偷，用来执行偷窃行为。

4. 总结

蜣螂算法与粒子群优化算法相比的优缺点：

1. 收敛速度快：蜣螂优化算法采用局部搜索和全局搜索相结合的策略，可以避免陷入局部最优。

2. 参数设置较多

蜣螂算法可能改进的方面

1. 自适应参数：蜣螂算法中的参数需要手动设置，这可能会导致算法的性能受到参数设置的影响。可以通过自适应参数的方式来改进算法，即根据搜索过程中的结果来自适应地调整参数，以提高算法的鲁棒性和性能。

2. 并行化：蜣螂算法的搜索过程是串行的，这可能会导致搜索效率低下。可以通过并行化的方式来改进算法，例如使用分布式计算等技术，以提高算法的搜索效率和处理能力。

References

智能优化算法：蜣螂优化算法-附代码

蜣螂优化(DBO)算法(含MATLAB代码)

第五十九弹——蜣螂优化算法

Xue J, Shen B. Dung beetle optimizer: A new meta-heuristic algorithm for global optimization[J]. The Journal of Supercomputing, 2023, 79(7): 7305-7336.