1 群体智能优化算法

SI(swarm intelligence)系统的特点是 个体间的相互作用 促进了智能行为的出现。

SI优化过程的实现主要包括以下两个步骤：

• 在 搜索空间范围 内创建一组 随机个体
• 在迭代过程中 组合、移动或进化 这些随机个体。

每种优化算法的 区别在于如何在优化过程中设计新的策略 (特别是组合、移动或进化)，如：

• 粒子群优化算法：在进化过程中，每个个体的位置可以逐渐收敛到全局最优解，主要取决于以下两个重要位置：1)一个是每个个体的最优位置，2)另一个是整个种群的全局最优位置。
• 蚁群优化(ant colony optimization, ACO)算法：在算法中，每只蚂蚁的路径表示一个可行解，所有蚂蚁的路径构成解空间。信息素的选择对于蚁群在整个优化问题空间中搜索全局最优路径至关重要。在这种情况下，在信息素水平较强的方向上获得最短路径。

除了研究群体与个体之间的关系，新的 SI还研究了生物的习性。如：

• 灰狼优化(GWO)算法：该算法模拟了灰狼的领导等级(包括alpha、beta、delta和omega)和狩猎行为。GWO算法的狩猎机制主要包括搜索、包围和攻击猎物。
• 鲸鱼优化算法(WOA)：首次提出了模仿座头鲸社会行为的气泡网捕猎策略。

除了以上介绍的算法，还有很多算法，且都应用到了实践中，但根据 No Free Lunch (NFL)定理，我们知道没有一个算法可以处理所有的优化问题。

换句话说，一个算法的优化性能可能在一组问题中表现良好，而在另一组问题中表现不佳。

因此，NFL定理鼓励寻找和开发更多性能令人满意的优化器。在上述讨论的基础上，作者提出了一种新的基于 SI的优化技术-蜣螂算法(Dung beetle optimizer,DBO)，旨在为复杂的优化问题提供一种更高效的优化器。

2 蜣螂的生活习性

蜣螂 以动物的粪便为食 。研究表明，屎壳郎有一个有趣的习惯，就是 把粪便打成球状 ，然后 滚出来 ，如图所示。

滚球

向后滚

其会尽可能 快速 有效地 移动 它们的粪球，这可以防止它们与其他屎壳螂 竞争(偷窃) 。

偷窃/竞争

另一方面，屎壳郎是 利用天体线索 (特别是太阳、月亮和偏振光)来 导航 ，使粪球沿 直线滚动 。

如果完全 没有光源 (即完全黑暗)，屎壳郎的路径就不再是直线，而是 弯曲 的，有时甚至 略圆 。

一些 自然因素 (如风和不平整的地面)也会导致屎壳郎偏离原来的方向。

此外，屎壳郎在滚动过程中很可能会遇到 障碍物 ，无法前进。在这方面，蜣螂通常 爬到粪球上跳舞 (包括一系列的 旋转和停顿 )，这决定了它们的 运动方向 。

跳舞(旋转和停顿)

蜣螂另一个有趣的行为是， 获得的粪球 有以下两个主要 目的 ：

• 一些粪球用来 产卵和养育 下一代
• 其余的用作 食物 。

具体来说，蜣螂把 粪球埋起来 ， 雌性 蜣螂在这些 粪球里产卵 。

埋球

繁殖(产卵)

繁殖(养育)

粪球不仅是幼虫的发育场所，还为幼虫提供了生活所必需的食物。因此，粪球对屎壳郎的生存起着不可替代的作用。

基于屎壳郎的 滚球、跳舞、觅食、偷窃和繁殖行为 提出了DBO算法。

3 数学模型

1) 模拟滚球行为

根据上面的讨论，我们知道蜣螂在 滚动过程 中需要 通过天体线索来导航 ，以保持粪球在 直线上滚动 。

为了模拟滚动球的行为，蜣螂需要在整个搜索空间中 朝着给定的方向移动 。

屎壳郎的 运动轨迹 如图所示。在这张图中，可以看到屎壳郎利用 太阳导航 ， 红色箭头 表示 滚动方向 。

运动轨迹

在本文中， 假设光源的强度也会影响屎壳郎的路径 。在滚球过程中，滚球屎壳郎的 位置被更新 ，可表示为：

式中：

• t 表示 当前迭代次数
• 表示第 i 只蜣螂在第 t 次迭代时的 位置信息
• k∈(0,0.2) 表示一个 常值 ，表示缺陷系数
• b 表示属于 (0,1) 的 常值
• 是赋值为 -1或1的 自然系数
• 表示 全局最差位置
• 用来模拟 光强 的 变化

选择两个参数 (k和b)的合适值是至关重要的，本文中k和b分别设为0.1和0.3。

意味着许多 自然因素 (如风和不平整的地面)可以使屎壳郎偏离原来的方向。其中，= 1表示 无偏差 ，=−1表示 偏离原方向 。

为了模拟现实世界中的复杂环境，本文通过 概率法 将设为1或-1。

同样， 值 越高 ， 光源越弱 。其具有以下两个优点：

• 在优化过程中尽可能彻底地 探索整个问题空间
• 追求更强的搜索性能， 减少陷入局部最优 的可能性。

因此， 更适合控制 的值来扩大搜索范围。

当屎壳郎遇到 障碍无法前进 时，它需要通过 舞蹈来重新定位 ，以获得新的路线。

2) 模拟跳舞行为

为了模拟舞蹈行为，我们使用 切线函数 来得到 新的滚动方向 。

我们只需要考虑在区间，上定义的正切函数的值，如图所示。

一旦蜣螂成功地 确定 了一个 新的方向 ，它应该继续 向后滚动 球。因此，对滚球屎壳郎的位置进行更新和定义如下:

• ，：偏转角。
• ：第 i 只蜣螂在第 t 次迭代时的位置与第 t - 1次迭代时的 位置之差 。因此，滚球屎壳郎的位置更新与当前和历史信息密切相关。

如果 等于0，或，屎壳郎的位置不会更新。

蜣螂会将粪球滚到 安全 的地方，并将粪球 藏起来 (见下图)。为了给后代提供一个安全的环境， 选择合适的产卵地点 对蜣螂来说至关重要。

3) 模拟产卵行为

在上述讨论的启发下，提出了一种边界选择策略来模拟 雌性蜣螂产卵的区域 ，其定义为：

• 表示 当前局部最佳位置
• 和 分别表示 产卵区下限和上限
• ， 表示 最大迭代次数
• 和 分别表示优化问题的 下限和上限

如图所示，当前局部最佳位置 用一个 大棕色圆圈 表示，而 周围的 小黑圆圈 表示 卵球 。每个卵球包含一个屎壳螂卵。 红色小圆圈 代表边界的 上下边界 。

产卵区

一旦确定了产卵区域，雌性蜣螂就会选择这个区域的卵球产卵。对于DBO算法， 每只雌性蜣螂在每次迭代中只产一个卵 。

由 (3) 可以清楚地看到， 产卵区边界范围是动态变化的 ，主要由R值决定。

因此，在迭代过程中 巢球的位置也是动态的 ：

• 为第 i 个球在第 t 次迭代时的 位置信息
• 和 为两个大小为 1 × D 的 独立随机向量
• D 为优化问题的 维数

注意窝球的位置被严格限制在 一定范围 内，即产卵区域。

4) 模拟觅食行为

一些 成年屎壳郎 从地下钻出来觅食。本文称其为 小屎壳郎 。此外，需要建立 最佳觅食区域 来引导甲虫觅食，如下图所示。

最优觅食区域的边界 定义如下：

• 为 全局最佳位置
• 和 分别为最佳觅食区域的 下界和上界 ，其他参数在 (3) 中定义。

因此， 小蜣螂的位置更新 如下：

• 为第 i 只小蜣螂在第 t 次迭代时的 位置信息
• 为 服从正态分布的随机数
• 为属于 (0,1)的 随机向量

5) 模拟偷窃行为

一些屎壳郎，被称为 小偷 ，从其他屎壳郎那里 偷粪球 (见下图)，需要指出的是，这是自然界中很常见的现象。

此外，由 (5) 可以看出， 是 最佳食物来源 。因此，可以假设 附近是最适合竞争食物 的地方。在迭代过程中， 小偷的位置信息被更新 ：

• 为第 i 个 小偷 在第 t 次迭代时的
• g 为服从正态分布的大小为1 × D的 随机向量 ，
• S 为 常数值

4 算法框架

基于以上讨论，本文提出的DBO算法的 伪代码 如下所示。

• 首先，设 为 最大迭代次数 ，为 总体大小 。
• 然后对DBO算法的所有代理进行 随机初始化 ，其分布设置如下图所示。

在这个图形中，小矩形的数量表示 总体大小 。假设总体规模为 30 ：蓝色、黄色、绿色和红色的长方形分别代表滚球的屎壳郎、窝球、小屎壳郎和小偷。

• 之后，根据 步骤2-27 ，知道了滚球屎壳郎、窝球、小屎壳郎和小偷在优化过程中不断更新。
• 最后输出最佳位置 及其适应度值。

综上所述，对于任意优化问题，DBO算法作为一种新型的基于 SI的优化技术，主要有 六个步骤 ，可以概括为：

1. 初始化 屎壳郎群和DBO算法 参数
2. 根据目标函数 计算 各agent的 适应度值
3. 更新 所有屎壳郎的 位置
4. 判断各agent 是否出界
5. 更新 当前最优解及其适应度值
6. 重复 上述步骤，直到 t 满足 终止准则 ，输出全局最优解及其适应度值

5 总结

DBO算法在 收敛速度、求解精度和稳定性 方面与其他7种优化技术进行了比较，显示出具有竞争力的搜索性能。

从理论上讲，DBO算法在探索或开发方面比其他算法更 具竞争力的原因 有以下几个特点：

1. 提出了一种新型的滚球蜣螂 搜索机制 ，不同的搜索模式使我们可以：A) 利用 不同时间段的信息 对搜索空间进行彻底的探索；b) 追求 更强的搜索能力 ，以避免陷入局部最优。
2. R参数 具有 动态变化的 特点，可以进一步激发DBO算法的探索和开发状态。
3. 不同的区域搜索策略 (包括产卵区域和最佳觅食区域)可以促进DBO算法的利用行为。
4. 不同的更新规则 可以保证所开发的DBO算法在局部和全局搜索能力之间保持足够的平衡。

matlab code：

https://www.mathworks.com/matlabcentral/fileexchange/121278-dung-beetle-optimizer-dbo

文献*载下** ( 蜣螂)

参考：

Xue, J., Shen, B. Dung beetle optimizer: a new meta-heuristic algorithm for global optimization. J Supercomput (2022). https://doi.org/10.1007/s11227-022-04959-6.