首页 > 编程学习 > 智能优化算法(源码)—蜣螂优化算法(Dung beetle optimizer,DBO)

在这里插入图片描述

获取更多资讯,赶快关注上面的公众号吧!

文章目录

  • 启发
  • 数学模型
    • 滚球
    • 跳舞
    • 繁殖
    • 觅食
    • 偷窃
    • 伪代码

2022年11月27日,东华大学沈波教授团队,继麻雀搜索算法之后,又提出了一种全新的群体智能优化算法——蜣螂优化(Dung beetle optimizer,DBO),主要模拟了蜣螂的的滚球、跳舞、觅食、偷窃和繁殖行为。关注公众号后回复“蜣螂”获取MATLAB源码

启发

  蜣螂,又称屎壳郎,以动物的粪便为食(口味很独特啊)。众所周知,屎壳郎有一个有趣的习惯,就是把粪便揉成球,滚动到可靠的地方藏起来(挺护食),然后再慢慢吃掉。

  蜣螂可以滚一个比自身大得多的粪球,并且可以利用天体的线索(特别是太阳、月亮和偏振光)来导航,使粪球沿直线滚动;然而,如果完全没有光源(也就是说,完全黑暗),蜣螂的路径就不再是直线,而是弯曲的,有时甚至略圆。许多自然因素(如风和不平坦的地面)会导致蜣螂偏离原来的方向。此外,蜣螂在滚动过程中很可能会遇到障碍物,无法前进。为此,蜣螂通常会爬到粪球上面跳舞(包括一系列的旋转和停顿),这决定了它们的运动方向。

  从蜣螂的生活方式中可以观察到获得粪球有以下两个主要目的:(1)有些粪球是用来产卵和养育下一代的;(2)其余的则用作食物。具体来说,蜣螂把粪球埋起来,雌性蜣螂在粪球里产卵。需要注意的是,粪球不仅是幼虫的生长场所,而且为幼虫提供了生存所必需的食物。因此,粪球对蜣螂的生存起着不可替代的作用。

  研究学者主要就是基于蜣螂以上生活习性,受其滚球、跳舞、觅食、偷窃和繁殖行为的启发,而提出了蜣螂优化算法,进行全局搜索和局部利用。

数学模型

滚球

  根据上面的描述,我们知道蜣螂在滚动过程中需要通过天体线索来导航,以保持粪球在直线上滚动。为了模拟滚动球的行为,需要蜣螂在整个搜索空间中沿着给定的方向移动。如下图所示,可以看出,蜣螂利用太阳导航,红色箭头表示滚动方向。

  文章中,作者假定光源强度也会影响蜣螂路径。在滚动过程中,按照如下对滚球屎壳郎的位置进行更新:

x i ( t + 1 ) = x i ( t ) + α × k × x i ( t − 1 ) + b × Δ x , Δ x = ∣ x i ( t ) − X w ∣ (1) \begin{aligned} x_i(t+1) & =x_i(t)+\alpha \times k \times x_i(t-1)+b \times \Delta x, \\ \Delta x & =\left|x_i(t)-X^w\right| \end{aligned} \tag{1} xi(t+1)Δx=xi(t)+α×k×xi(t1)+b×Δx,=xi(t)Xw(1)

其中 t t t表示当前迭代次数, x i ( t ) x_i(t) xi(t)表示第 t t t次迭代时第 i i i只蜣螂的位置信息, k ∈ ( 0 , 0.2 ] k\in(0,0.2] k(0,0.2]是一个常量表示偏转系数, b ∈ ( 0 , 1 ) b\in(0,1) b0,1 α \alpha α是自然系数取1或-1, X w X^w Xw是全局最差位置, Δ x \Delta x Δx模拟光强的变化。

在式(1)中,为参数 k k k b b b选择合适的值是至关重要的。 α \alpha α模拟了自然因素(如风和不平坦的地面)可以使蜣螂偏离它们原来的方向,具体来说, α = 1 \alpha=1 α=1代表没有偏离, α = − 1 \alpha=-1 α=1代表偏离原来方向。 α \alpha α的取值根据概率方法确定的以模拟复杂的环境,见下面的算法。类似的, Δ x \Delta x Δx越大表示光源越弱,其能带来两个好处:1)在优化过程中,尽可能彻底地探索整个问题空间;2)执行更强的搜索性能,降低陷入局部最优的可能性。

跳舞

  当蜣螂遇到障碍物而无法前进时,它会通过跳舞来重新定向自己,以获得新的路线。

  为了模拟舞蹈行为,作者使用正切函数(只考虑 [ 0 , π ] 区 间 内 的 值 [0,\pi]区间内的值 [0,π])得到新的滚动方向。 一旦蜣螂成功地确定了一个新的方向,它应该继续向后滚动球。因此,蜣螂的位置按如下更新:

x i ( t + 1 ) = x i ( t ) + tan ⁡ ( θ ) ∣ x i ( t ) − x i ( t − 1 ) ∣ (2) x_i(t+1)=x_i(t)+\tan (\theta)\left|x_i(t)-x_i(t-1)\right|\tag{2} xi(t+1)=xi(t)+tan(θ)xi(t)xi(t1)(2)
其中 θ \theta θ是偏转角 ∈ [ 0 , π ] \in[0,\pi] [0,π]

在式(2)中, ∣ x i ( t ) − x i ( t − 1 ) ∣ |x_i(t)-x_i(t-1)| xi(t)xi(t1)是第 i i i只蜣螂第 t t t t − 1 t-1 t1次迭代之间的差异,因此蜣螂位置的更新与当前和历史信息密切相关。

繁殖

  在自然界中,粪球被蜣螂滚到安全的地方并藏起来(见图4)。

  为了给它们的后代提供一个安全的环境,选择合适的产卵地点对蜣螂来说至关重要。受上述讨论的启发,作者提出了一种边界选择策略来模拟雌性蜣螂产卵的区域,定义如下:
L b ∗ = max ⁡ ( X ∗ × ( 1 − R ) , L b ) , U b ∗ = min ⁡ ( X ∗ × ( 1 + R ) , U b ) (3) \begin{aligned} & L b^*=\max \left(X^* \times(1-R), L b\right), \\ & U b^*=\min \left(X^* \times(1+R), U b\right) \end{aligned}\tag{3} Lb=max(X×(1R),Lb),Ub=min(X×(1+R),Ub)(3)
其中 X ∗ X^* X表示当前局部最优位置, L b ∗ L b^* Lb U b ∗ U b^* Ub分别表示产卵区域的下界和上界, R = 1 − t / T max ⁡ R=1-t / T_{\max } R=1t/Tmax T max ⁡ T_{\max } Tmax表示最大迭代次数, L b L b Lb U b U b Ub分别表示优化问题的下界和上界。

  如下图所示,当前最优位置 X ∗ X^* X通过棕色圆表示,其周围的黑色小圆表示卵球,每个卵球里都包含蜣螂的卵。

  一旦确定了产卵区域,雌性蜣螂就会选择这个区域的卵球产卵,在算法中,假设每个雌蜣螂在每次迭代中只会下一个卵。并且从式(3中)可以清楚地看到,产卵区域的边界范围是随 R R R值动态变化的,因此卵球的位置在迭代过程中也是动态变化的,定义如下:

B i ( t + 1 ) = X ∗ + b 1 × ( B i ( t ) − L b ∗ ) + b 2 × ( B i ( t ) − U b ∗ ) (4) B_i(t+1)=X^*+b_1 \times\left(B_i(t)-L b^*\right)+b_2 \times\left(B_i(t)-U b^*\right)\tag{4} Bi(t+1)=X+b1×(Bi(t)Lb)+b2×(Bi(t)Ub)(4)
其中 B i ( t ) B_i(t) Bi(t)是第 i i i个卵球在第 t t t次迭代的位置信息, b 1 b_1 b1 b 2 b_2 b2是两个独立的大小为 1 × D 1 \times D 1×D的随机向量, D D D是优化问题的维度。注意,卵球是严格限制在产卵区域的。

觅食

  一些成年屎壳郎会从地下钻出来寻找食物,如下图。

  作者将其称为小蜣螂,并模拟了蜣螂的觅食过程,最优觅食区域的边界如下:

L b b = max ⁡ ( X b × ( 1 − R ) , L b ) U b b = min ⁡ ( X b × ( 1 + R ) , U b ) (5) \begin{aligned} & L b^b=\max \left(X^b \times(1-R), L b\right) \\ & U b^b=\min \left(X^b \times(1+R), U b\right) \end{aligned}\tag{5} Lbb=max(Xb×(1R),Lb)Ubb=min(Xb×(1+R),Ub)(5)

其中 X b X^b Xb表示全局最优位置, L b b L b^b Lbb和$ U b^b$分别表示最佳觅食区域的下界和上界。因此,小蜣螂的位置更新如下:
x i ( t + 1 ) = x i ( t ) + C 1 × ( x i ( t ) − L b b ) + C 2 × ( x i ( t ) − U b b ) (6) x_i(t+1)=x_i(t)+C_1 \times\left(x_i(t)-L b^b\right)+C_2 \times\left(x_i(t)-U b^b\right)\tag{6} xi(t+1)=xi(t)+C1×(xi(t)Lbb)+C2×(xi(t)Ubb)(6)

其中 x i ( t ) x_i(t) xi(t)表示第 i i i个小蜣螂第 t t t次迭代的位置信息, C 1 C_1 C1表示服从正态分布的随机数, C 2 C_2 C2 ( 0 , 1 ) (0,1) (0,1)范围内的随机向量。

偷窃

  有一些蜣螂,被称为小偷,会从其他蜣螂那里偷粪球,如下图。

  从式(5)中可以看出 X b X^b Xb是最优食物源,因此可以假设 X b X^b Xb周围是竞争食物的最优位置。迭代过程中,小偷的位置信息按如下更新:
x i ( t + 1 ) = X b + S × g × ( ∣ x i ( t ) − X ∗ ∣ + ∣ x i ( t ) − X b ∣ ) x_i(t+1)=X^b+S \times g \times\left(\left|x_i(t)-X^*\right|+\left|x_i(t)-X^b\right|\right) xi(t+1)=Xb+S×g×(xi(t)X+xi(t)Xb)
  其中 x i ( t ) x_i(t) xi(t)表示第 i i i个小偷第 t t t次迭代的位置信息, g g g是大小为 1 × D 1 \times D 1×D的服从正态分布的随机向量, S S S是常量。

伪代码

  基于以上讨论,蜣螂优化算法伪代码如下:

  首先,令 T m a x T_{max} Tmax为最大迭代次数, N N N为种群大小。

  然后,随机初始化所有代理,按照下图所示的方式分布设置。

  之后,根据不同类型的代理,选择合适的方式更新滚球蜣螂、卵球、小蜣螂和小偷的位置。

  最后,输出最优位置 X b X^b Xb及其适应度值。

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号