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

真的好久好久好久没更新了！

读研后平日较忙，很少有时间能够再次投入自己喜欢的算法领域进行创作。自开始创作这些算法小科普以来，有幸认识了很多朋友，大家相互交流，分享自己对科研、生活的见解，这让我感到十分温暖（平台中很多朋友的评论没及时回复，见谅见谅~）。期间，有许多友人与我交流近两年涌现出的新型算法，大多思路新奇，性能优异，但很可惜由于时间原因没能及时在这个平台与大家分享。

近日有幸受友人之邀，在此与大家分享去年由东华大学Xue Jiankai等人（即2020年提出麻雀搜索算法的优秀科研团队）提出的一种新型群智能优化算法——蜣螂优化算法（Dung beetle optimizer，DBO）。与此同时，也有两位知乎好友向我私信该算法，看来大家都很关注它呀~ 这足以表明DBO算法拥有在未来掀起一股热度的潜力！

原始的遗传算法，粒子群算法，模拟退火算法等的出现，为群智能优化算法的发展开辟了先河。经过多年的发展，这一领域已绽放出炫丽的光彩。新出炉的DBO算法，其灵感来自于蜣螂的滚球、跳舞、觅食、偷窃和繁殖行为。总的来说该算法兼顾了全局探索和局部开发，具有收敛速度快、求解精度高的特点。另外在Wilcoxon秩和检验和Friedman检验方面，相比于当前其他流行的群智能优化算法，DBO算法也具有相当的优越性。实验结果表明对于实际应用问题，如压力管设计、三杆桁架等，DBO算法同样保持着优秀的优化性能。（PS：原文作者在代码注释中给出了qq群供大家交流，869592172 或者439115722）

蜣螂，也就是我们常说的“屎壳郎”，是自然界中常见的昆虫，以动物粪便为食。这类昆虫在自然界中充当分解者，在生态系统中至关重要。

蜣螂把粪球滚回洞穴的过程中存在许多技巧。首先，它可以利用天体线索（尤其是太阳、月亮和偏振光）来导航，使粪球沿着直线滚动。然而到了很黑的晚上，它的路径就不再是笔直的，而是弯曲的，有时甚至略微偏圆形。

许多自然因素（如风和不平的地面）会对它的回城之路产生巨大的影响，此时，蜣螂通常会爬到粪球顶部跳舞（包括一系列旋转和暂停行为），从而决定它们的运动方向（有可能是在绕圈圈，头晕了然后随机停到一个方向？？）。

当它好不容易把粪球推回家，这些粪球会有两个作用：一些粪球用于产卵和饲养下一代，其余的用作食物。具体来说，蜣螂把粪球埋起来，雌虫在粪球里产卵。需要注意的是，粪球不仅是幼虫的发育场所，还为幼虫提供生命所必需的食物。因此，粪球对蜣螂的生存发挥着不可替代的作用。

下面开始介绍算法的数学模型。由上述可知，在滚动过程中，蜣螂需要通过天体线索导航，以保持粪球在直线上滚动，毕竟，两点之间直线最短，可见它数学学的还不错。为了模拟滚动球的行为，需要在整个搜索空间中以给定的方向移动蜣螂。蜣螂的轨迹如图2所示。

在上图中，我们可以看到太阳宝宝正为蜣螂进行导航。在算法中，假设太阳宝宝的强度也会影响蜣螂的路径。在滚动过程中，蜣螂位置的更新方式为：

此处xi(t+1)为第i只蜣螂在第t次迭代时的位置，k∈(0, 0.2】表示偏转系数（在代码中被赋值0.1），b∈(0,1）为一个自然系数（在代码中被赋值0.3）； x用来表示光强度的变化程度，其中Xw为当前种群内的最差位置。

对于α，通过概率方法将其设置为1或-1，令α=1表示自然环境不影响原始方向，而α=-1表示偏离原始方向。类似地，作者将全局最差位置看做太阳宝宝，x的值越高表示光源越弱，促进蜣螂避开此位置，这样在优化过程中尽可能彻底地探索整个搜索空间，并减少陷入局部最优的可能性。这一部分的伪代码为：

当蜣螂遇到障碍物无法前进时，它需要通过跳舞来进行定位，以获得新的路线。为了模拟舞蹈行为，利用切线函数来获得新的滚动方向，其区间为[0，π], 如图3所示：

一旦蜣螂成功确定了新的方向，它应该继续向后滚动粪球。因此，滚动粪球时蜣螂的位置更新方式为：

此处θ∈[0，π]为偏转角，注意，当θ等于0，π/2，π时，蜣螂不会更改位置。这一部分的伪代码为：

当粪球被滚回家时，为了给后代提供一个安全的环境，选择合适的产卵地点对蜣螂来说至关重要。基于上述讨论，引出一种边界选择策略，以模拟雌虫产卵的区域，其定义如下：

其中Lb*，Ub*分别为产卵区域的下、上限，Lb，Ub分别为搜索空间的下、上限，X*为当前种群内最优位置，惯性权值R=1?t∕Tmax，这里Tmax为算法迭代时的最大迭代次数。

结合图4可以更好的理解上述模型。当前的种群内最优位置X*用一个大的橙色点表示，而X*周围的黑色点表示孵卵粪球。注意，每个孵卵粪球都含有一个蜣螂的卵（见图5）。此外，红色点表示边界的上下限。

一旦确定了产卵区域，雌虫就会选择该区域的孵卵粪球产卵。对于DBO算法，每只雌虫在每次迭代中肯定只产生一个卵，也就是一个解。从公式（3）可以清楚地看出，产卵区的边界范围是动态变化的，这样可以避免算法陷入局部最优值，而这主要由惯性权值R值决定。因此，孵卵粪球的位置在迭代过程中也是动态的，其定义如下：

其中Bi(t)是第t次迭代时第i个孵卵粪球的位置，b1和b2表示大小为1×D的两个独立随机向量，D表示优化问题的维数。注意，孵卵粪球的位置严格限制在一定范围内，即产卵区域，该区域的伪代码如下：

当小蜣螂孵化成功后（见图6），他们会跑出来成群觅食，因此需要建立最佳觅食区域来指导它们。

这一觅食过程也包含一个范围约束，即最佳觅食区域：

其中Xb为全局最优位置，Lbb、Ubb为最佳觅食区域的下、上限。确定好区域后，就可以定义小蜣螂的位置更新方式：

此处xi(t)表示第t次迭代时第i个小蜣螂的位置信息，C1表示遵循正态分布的随机数，C2表示属于（0，1）的随机向量。

当前人类社会固然和谐，但不乏也有鸡鸣狗盗之徒，蜣螂社会中也不例外。有些蜣螂不愿意本本分分滚粪球，非要白嫖别人的！

上文说过，Xb是全局最优位置，也就是最佳的食物位置。因此，可以假设Xb附近是争夺食物的最佳地点。在迭代过程中，小偷的位置更新方式如下：

其中xi(t)表示第t次迭代中第i个小偷的位置，g是大小为1×D的随机向量，服从正态分布，S表示一个常量，在代码中被赋值0.5。

前文提到了四种角色，在算法中就要对其数量进行分配。基于原文，假设种群规模为30，图8中蓝色、黄色、绿色和红色矩形分别代表滚球蜣螂、孵卵粪球、小蜣螂和小偷的配比。需要注意的是种群规模是可以自行设置的，并且四种角色的数量分配也可以根据实际问题进行调整。

至此，整个算法的流程就介绍完了~下面是DBO算法的完整伪代码：

此部分以三杆桁架设计、压力容器设计、焊接梁设计问题展开讨论。可能很多朋友没有看过我之前对三个问题的简要描述：

为了方便阅读，我在此重新对其进行介绍。

三杆桁架设计问题是土木工程领域中的另一个结构优化问题，在该问题中，为了使受应力、挠度和屈曲约束的重量最小，需要对两个杆长进行操作：

其约束条件为：

该问题的目标是使一个两端有盖，头部为半球形的圆柱形容器的材料、成型和焊接总成本最小化，该容器的模型如下：

同样，该问题也有四个待优化变量——壳体厚度(Ts )、顶部厚度(Th )、内半径(R )、忽略顶部的圆柱形截面长度(L ):

该问题的数学模型为：

该问题的目的是使焊接梁的制造成本最小化，焊接梁模型为：

其包含如下约束条件：

上述五者分别为：剪切应力、梁内部的弯曲应力、杆上的屈曲荷载、梁端挠度、侧面约束。该问题的优化变量为：焊缝厚度(h )、钢筋附着部分长度(l )、杆的高度(t )、杆的厚度(b )。基于此，可得该问题的数学模型：

对于上述三个问题的优化结果如下：

本文篇幅较长，在此对DBO算法的整个逻辑进行梳理：

1. 一种新型蜣螂行为机制，其中太阳导航和自然影响的搜索模式可以确保对搜索空间的充分探索。

2. 惯性权值R具有动态变化的特征，可以进一步平衡DBO算法的探索和开发状态。

3. 产卵区域和最佳觅食区域的动态更新可以促进算法对局部地区的开发。

4. 偷窃行为保证了算法能够即使跳出局部最优值。

总体来说，DBO算法对蜣螂的行为进行了充分的模拟，公式不是随便创造，有理有据，相比于其他算法，具有鲜明的特色。同时，惯性权值R能够更好平衡算法的全局搜索、局部开发行为，乃画龙点睛。

未来一段时间争取复更，希望我的点滴工作能让大家在欢乐之余了解到更多有关群智能优化算法的知识，你我皆是行路人~

原文链接：