前言
蜣螂（俗称屎壳郎）优化算法( Dung beetle optimizer, DBO), 是由 Jiankai Xue 等于2022年提出的一种群体智能优化算法。其灵感来源于蜣螂的生物行为过程，具有寻优能力强，收敛速度快的特点。
1. 蜣螂的生物行为
蜣螂是自然界中一种常见的昆虫，以动物的粪便为食，在全世界内分布广泛，扮演着自然界中分解者的角色，对生态系统平衡起着至关重要的作用。蜣螂有一个有趣的习惯，它们会把粪便捏成球，然后把它滚出来，目的是能够尽可能快速、有效地移动粪球，防止被其他蜣螂抢夺。
蜣螂的可以利用天体线索(特别是太阳、月亮和偏振光)来导航，让粪球沿着直线滚动，如果完全没有光源(也就是在完全黑暗的环境中)，蜣螂的就不再走直线，而是弯曲的，有时甚至略圆，有很多因素(如风、地面不平)都会导致蜣螂偏离原来的方向，蜣螂在滚粪球的过程如遇到障碍物而无法前进时，通常会爬到粪球上面"跳舞"(包括一系列的旋转和停顿)，决定它们的运动方向。
从蜣螂的习性中观察发现，其获取粪球主要有以下两个目的： ①用来产卵和养育下一代； ②作为食物。蜣螂会把粪球埋起来，雌性蜣螂会在粪球里产卵，粪球不仅是蜣螂幼虫的发育场所，也是必需的食物。所以，粪球对蜣螂的生存起着不可替代的作用。
本位介绍了一种新的群体智能优化算法------DBO（Dung beetle optimizer）技术，其灵感主要来源于蜣螂的滚球、跳舞、觅食、偷窃、和繁殖等行为。
蜣螂在仿生算法设计中主要有四个角色：
滚球蜣螂：移动粪球到某个场所卵球（繁殖蜣螂）：雌性蜣螂产生的子代小蜣螂：四处觅食偷窃蜣螂：偷取粪球
2. 算法优化原理
2.1 滚球蜣螂（ball-rolling dung beetle）
2.1.1 无障碍物：太阳定位及自然因素影响
概述： 蜣螂在滚动过程中可以利用天体的线索(特别是太阳、月亮和偏振光)来导航，使粪球沿直线滚动，太阳光等会影响运动轨迹，呈弯曲或椭圆等；自然因素(如风和不平坦的地面)会导致蜣螂偏离原来的方向。
为了模拟滚球行为，要求蜣螂在整个搜索空间中沿着给定的方向移动。蜣螂的运动轨迹如图1所示。在图1中，蜣螂利用太阳来导航，其中红色箭头表示的是滚动的方向,同时，假设光源的强度也会影响蜣螂的路径。在滚动过程中，滚球蜣螂的位置更新，可以表示为：
t
t
t 表示迭代次数，
x
i
(
t
)
x_i(t)
xi(t) 表示第
t
t
t 次迭代时第
i
i
i 只蜣螂的位置信息，
k
∈
(
0
,
0.2
]
k ∈(0, 0.2]
k∈(0,0.2] 是一个常数，表示偏转系数，
b
∈
(
0
,
1
)
b ∈(0, 1)
b∈(0,1) 的一个定值，
α
\alpha
α 是自然系数取 1 或 -1，-1表示偏离原方向，1表示无偏差，
X
w
X^w
Xw 是全局最差位置，
Δ
x
\Delta x
Δx 模拟光强的变化。
在式(1)中，适当选择两个参数
k
k
k 、
b
b
b 的值至关重要,
α
\alpha
α 代表诸多自然因素(如风和不平坦的地面)可使蜣螂偏离原来的方向。为模拟现实世界中的复杂环境, 通过概率法设
α
\alpha
α 为
1
1
1 或
−
1
-1
−1，如算法 1 所示，当
α
=
1
α = 1
α=1 时, 表示无偏差, 当
α
=
−
1
α = − 1
α=−1 时, 表示偏离原方向。同样,
Δ
x
\Delta x
Δx 的值越高表示光源越弱, 同时,
k
k
k 和
b
b
b 分别设为
0.1
0.1
0.1 和
0.3
0.3
0.3 。利用
Δ
x
\Delta x
Δx 有以下两个优点：
(1) 算法在优化过程中, 可尽可能地彻底地探索整个空间;(2) 使算法具有更强的搜索性能, 从而避免陷入局部最优。
X
w
X^w
Xw 通过控制
Δ
x
\Delta x
Δx 的值, 来扩大搜索范围。
2.1.2 有障碍物：跳舞
当蜣螂遇到障碍物无法前进时, 就需要通过跳舞来重新定位, 目的是获得新的路线。为了模拟舞蹈行为, 用切线函数得到新的滚动方向。需要指出的是, 只需要考虑定义在区间
[
0
,
π
]
[0 , π ]
[0,π], 如图 2 所示。一旦蜣螂成功确定了一个新的方向, 它继续把球向后移。因此, 蜣螂的位置更新定义如下：
其中,
θ
\theta
θ 为挠度角, 属于
[
0
,
π
]
[0, \pi]
[0,π] 。
∣
x
i
(
t
)
−
x
i
(
t
+
1
)
∣
|x_i (t) − x_i ( t + 1 )|
∣xi(t)−xi(t+1)∣ 表示第
i
i
i 只蜣螂在第
t
t
t 次迭代时的位置与其在第
t
−
1
t − 1
t−1 次迭代时的位置之差，因此蜣螂的更新与当前和历史信息相关。如果
θ
=
0
,
π
/
2
,
π
\theta=0, \pi / 2, \pi
θ=0,π/2,π, 蜣螂的位置不更新。
2.2 卵球（brood ball）繁殖
在自然界中, 粪球是被蜣螂滚到安全的地方藏起来。为了给它们的后代提供安全的环境, 选择合适的产卵地点对蜣螂来说至关重要。模拟䧳蜣螂产卵的区域边界选择策略, 其定义为：
其中,
X
∗
X^*
X∗ 为当前局部最佳位置,
L
b
∗
L b^*
Lb∗和
U
b
∗
U b^*
Ub∗ 分别为产卵区下限和上界,
R
=
1
−
t
/
T
max
R=1-t / T_{\max }
R=1−t/Tmax,
T
max
T_{\max }
Tmax 表 示最大迭代次数,
L
b
Lb
Lb 和
U
b
Ub
Ub 分别代表优化问题的下界和上界。
如图 3 所示, 当前局部最佳位置
X
∗
X^*
X∗ 用一个大的棕色圈表示, 而
X
∗
X^*
X∗ 周围的小黑圈表示卵球。 每个卵球中都蕴含一枚蜣螂卵, 红色的小圆圈代表边界的上下界。
一旦确定了产卵区域, 雌性蜣螂就会选择这个区域的卵球产卵。对于 DBO 算法, 每只雌蜣螂在每次迭代中只产一个卵。此外, 从式(3)中可以清楚地看到, 产卵区域的边界范围是动态变化的, 这主要是由
R
R
R 值决定的。由此可见, 卵球的位置在迭代过程中也是动态的, 表示为：
B
i
(
t
)
B_i (t)
Bi(t) 为第
t
t
t 次迭代时第
i
i
i 个卵球的位置信息,
b
1
b_1
b1 和
b
2
b_2
b2 表示大小为
1
×
D
1 × D
1×D 的两个独立随机向量,
D
D
D 表示优化问题的维数。卵球的位置被严格限制在一定范围内。
2.3 小蜣螂（small dung beetle）觅食
一些已经长成成虫的蜣螂会从地下钻出来觅食, 我们称它们为小蜣螂, 还需要建立最优蜣螂区域来引导蜣螂觅食，最佳蜣螂区域的边界定义如下：
X
b
X^b
Xb 表示全局最佳受食位置,
L
b
b
L b^b
Lbb 和
U
b
b
U b^b
Ubb 分别为最优受食区域的下界和上界, 其他参数在式(3)中定义, 因此小蜣螂的位置更新如下：
其中,
x
i
(
t
)
x_i(t)
xi(t) 表示第
t
t
t 次迭代时第
i
i
i 只小蜣螂的位置信息,
C
1
C_1
C1 表示一个服从正态分布的随机数,
C
2
C_2
C2 表示属于
(
0
,
1
)
(0 , 1)
(0,1) 的随机向量。
2.4 偷窃蜣螂（thief）
还有一些蜣螂被称为偷窃蜣螂, 会从其他蜣螂那里偷粪球，这是自然界中非常常见的现象。 从式 (5) 可以看出，
X
b
X^b
Xb 即最优的食物来源位置。因此, 可以假设
X
b
X^b
Xb 即表示争夺食物的最佳地点。在迭代过程中, 偷穷蜣螂的位置更新信息定义如下：
其中,
x
i
(
t
)
x_i(t)
xi(t) 表示第
i
i
i 个偷窃蜣螂在第
t
t
t 次迭代时的位置信息,
g
g
g 是一个大小为
1
×
D
1 × D
1×D 维的随机向量, 服从于正态分布,
S
S
S 表示恒定值。
偷窃蜣螂在优化过程中位置不断更新, 最后输出最佳位置
X
b
X^b
Xb 。根据此算法更具体地说, 在 DBO 算法中, 一个蜣螂种群包括
N
N
N 种目标代理, 其中代理
i
i
i 都代表一组候选解, 第
i
i
i 个代理的位置向量用
x
i
(
t
)
x_i(t)
xi(t) 表示,
x
i
(
t
)
=
(
x
i
1
(
t
)
,
x
i
2
(
t
)
,
…
…
,
x
i
D
(
t
)
)
x_i(t)=\left(x_{i 1}(t), x_{i 2}(t), \ldots \ldots, x_{i D}(t)\right)
xi(t)=(xi1(t),xi2(t),……,xiD(t)) , 其中,
D
D
D 为搜索空间的维数。它们的分布比例没有指定, 可以根据实际应用问题进行设置。
3. 算法流程
DBO 算法作为一种新颖的基于 SI 的优化技术, 主要有六个步骤:
(1) 初始化蜣螂群和 DBO 算法的参数;(2) 根据目标函数计算出所有目标代理的适应度值;(3) 更新所有蛲螂的位置;(4) 判断每个目标代理是否超出边界;(5) 更新当前最优解及其适应度值;(6) 重复上述步骤, 直到 t 满足终止准则, 输出全局最优解及其适应度值。
种群按照 6:6:7:11 的比例，将蜣螂划分成不同的角色。也就是说，按照图中的种群规模，在30个个体中，有6个蜣螂用于滚球行为，6个蜣螂用于繁殖行为，7个蜣螂被定义为小蜣螂，执行觅食行为，剩下的11个蜣螂都被定义为小偷，用来执行偷窃行为。
4. 总结
蜣螂算法与粒子群优化算法相比的优缺点：
收敛速度快：蜣螂优化算法采用局部搜索和全局搜索相结合的策略，可以避免陷入局部最优。
参数设置较多
蜣螂算法可能改进的方面
自适应参数：蜣螂算法中的参数需要手动设置，这可能会导致算法的性能受到参数设置的影响。可以通过自适应参数的方式来改进算法，即根据搜索过程中的结果来自适应地调整参数，以提高算法的鲁棒性和性能。
并行化：蜣螂算法的搜索过程是串行的，这可能会导致搜索效率低下。可以通过并行化的方式来改进算法，例如使用分布式计算等技术，以提高算法的搜索效率和处理能力。
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.