多维度改进的蜣螂优化算法及其应用

The Multi-Dimensional Improved Dung Beetle Optimization Algorithm and Its Applications

摘要: 蜣螂优化算法(DBO)作为一种新兴的智能优化算法，在求解复杂优化问题中显示出巨大潜力。然而，其在收敛精度和易陷入局部最优方面的局限性限制了其应用范围。本文提出了一种多策略改进的蜣螂优化算法(ODBO)，通过佳点集群初始化和周期突变机制增强种群多样性，引入Beta分布动态生成反射解决方案以探索更广的搜索空间，并采用莱维飞行处理边界违规问题。进一步融合鲸鱼优化算法的螺旋搜索更新机制，结合随机策略更新位置，显著提升了算法的收敛精度和鲁棒性。当算法陷入停滞时，引入t分布扰动变异策略，有效提高了算法跳出局部最优解的能力。通过在17个基准测试函数验证了改进策略的有效性。此外，本文还将ODBO应用于车间排产调度问题，进一步证实了其在解决实际工程问题中的有效性和可靠性。

Abstract: The Dung Beetle Optimization algorithm (DBO), as an emerging intelligent optimization algorithm, shows great potential in solving complex optimization problems. However, its limitations in convergence precision and susceptibility to local optima hinder its broader application. This paper proposes an improved multi-strategy Dung Beetle Optimization algorithm (ODBO), which enhances population diversity through good point set initialization and periodic mutation mechanisms. A Beta distribution is introduced to dynamically generate reflected solutions to explore a wider search space, and Lévy flight is applied to handle boundary violation issues. Additionally, the spiral search update mechanism from the Whale Optimization Algorithm is integrated, along with random strategy updates for position, significantly improving the algorithm’s convergence accuracy and robustness. When the algorithm stagnates, a t-distribution mutation perturbation strategy is introduced, effectively enhancing its ability to escape local optima. Simulations on 17 benchmark functions test functions validate the effectiveness of the improved strategies. Moreover, the application of ODBO to the job-shop scheduling problem confirms its effectiveness and reliability in solving real-world engineering problems.

1. 引言

在生产调度领域，面对日益复杂的问题，传统的精确求解策略如整数规划和网络流算法，虽然能确保找到最优解，但其计算成本却随着问题规模的扩大而迅速攀升。为了解决这一问题，研究者们开始转向启发式算法[1]，这些算法在迭代过程中通过避免陷入局部最优解来提高效率。蜣螂优化算法(DBO) [2]，由Xue等人在2022年提出，是一种新兴的群体智能优化技术。该算法已经在多个实际问题中得到应用，例如生物医学和能源系统规划。与传统的群体智能算法相比，DBO算法的位置更新是并行进行的，它模拟了蜣螂的四种行为：滚球、繁育、觅食和偷窃。这种并行更新机制使得DBO算法在处理大规模问题时具有潜在的优势。然而，DBO算法也面临着一些挑战，如算法稳定性、可解释性以及高纬度问题处理困难。

为了克服这些挑战，本文提出了以下改进措施：首先，通过使用佳点集群初始化[3]方法来增强种群的多样性，并引入周期性突变机制[4]来帮助算法跳出局部最优。其次，采用Beta分布来动态生成反射解[5]，以更有效地探索解空间，并利用莱维飞行策略[6]来处理边界违规问题[7]。最后，结合鲸鱼优化算法中的螺旋搜索机制[8]，通过随机策略来更新位置，从而提高算法的收敛精度。当算法遇到停滞状态时，采用t分布扰动变异策略[9]来进一步增强算法跳出局部最优解的能力。这些改进在基准函数测试和车间排产优化问题中的应用中得到了验证，证明了其在工程领域的实用性。

2. 蜣螂优化算法

受自然界中蜣螂独特生活习性的启发，科研人员开发了一种创新的优化策略。在自然界里，蜣螂展现出滚动粪球、精心挑选繁殖地、积极觅食以及巧妙偷窃等多种行为。在算法设计中，这些复杂行为被巧妙地提炼为四种各具特色的搜索策略，它们分别对应于算法中的四种蜣螂角色：滚动者、繁殖者、觅食者和偷窃者。它们遵循各自独特的位置更新机制，协同合作，共同在广阔的解空间中探索，旨在发现全局最优解。

(1) 滚球蜣螂

在滚动的过程中，蜣螂必须通过天体的线索来导航，以保持粪球在直线上滚动。因此，滚球蜣螂的位置被更新，并且可以表示为

$x_i\left(t+1\right)=x_i\left(t\right)+\alpha \times k\times x_i\left(t-1\right)+b\times \Delta x$ (1)

$\Delta x=\left|x_i\left(t\right)-X^w\right|$ (2)

其中t表示当前迭代次数；$x_i\left(t\right)$ 表示第t次迭代期间，第i只蜣螂的位置信息；k ∈ (0, 0.2]是表示偏转系数的常数值；b是属于(0, 1)的常数值；α是分配给1或−1的自然系数；$X^w$ 是全局最差位置。当一只蜣螂遇到阻碍它前进的障碍物时，它会通过跳舞来改变自己的方向，以获得一条新的路线。正切函数模拟舞动行为以获得新的滚动方向。因此，滚球蜣螂的位置更新如下：

$x_i\left(t+1\right)=x_i\left(t\right)+\tan \theta \left|x_i\left(t\right)-x_i\left(t-1\right)\right|$ (3)

(2) 繁殖蜣螂

选择一个合适的产卵地点对蜣螂为后代提供一个安全的环境至关重要。因此，在DBO中，提出了一种边界选择策略来模拟雌性蜣螂的产卵区，其定义如下：

$L{b}^{\text{*}}=\max \left(X^{\text{*}}\times \left(1-R\right),Lb\right)$

$U{b}^{\text{*}}=\min \left(X^{\text{*}}\times \left(1-R\right),Ub\right)$ (4)

其中，X表示当前的局部最优位置；Lb和Ub表示产卵区域的上下界；R = 1 − t/Tmax；Tmax表示最大迭代次数；$Lb$ 和$Ub$ 分别是可行区域的上下界S。$U{b}^{\text{*}}$ 、$L{b}^{\text{*}}$ 为安全区域的上界和下界。假设每只雌性蜣螂在每次迭代中只产一个卵。产卵区域的边界范围随值动态变化，因此在迭代过程中，蛋球的位置也动态变化，表示如下：

$B_i\left(t+1\right)=X^{\text{*}}+b_1\times \left(B_i\left(t\right)-L{b}^{\text{*}}\right)+b_2\times \left(B_i\left(t\right)-U{b}^{\text{*}}\right)$ (5)

其中B_i (t)是第t次迭代时第i个球体的位置；b₁和b₂是两个独立的随机向量，大小为1 × D；D是维数。

(3) 小蜣螂

一些成年的蜣螂会从地下钻出来寻找食物，这种蜣螂被称为小蜣螂。小蜣螂最佳觅食区的边界定义如下：

$L{b}^b=\max \left(X^b\times \left(1-R\right),Lb\right)$

$U{b}^b=\min \left(X^b\times \left(1-R\right),Ub\right)$ (6)

其中$X^b$ 表示全局最优位置；$L{b}^b$ 和$U{b}^b$ 分别是最优觅食区域的下限和上限。因此，小蜣螂的位置更新如下：

$x_i\left(t+1\right)=x_i\left(t\right)+C_1\times \left(x_i\left(t\right)-L{b}^b\right)+C_2\times \left(x_i\left(t\right)-U{b}^b\right)$ (7)

其中$x_i\left(t\right)$ 表示第t次迭代时第i只蜣螂的位置；$C_1$ 为服从正态分布的随机数；$C_2$ 为(0, 1)范围内的随机向量。

(4) 偷窃蜣螂

有些被称为小偷的蜣螂会从其他蜣螂那里偷粪球。从等式(5)可以观察到，$X^b$ 是最佳食物源。假设$X^b$ 周围的区域是竞争食物的最佳位置。在迭代过程中，小偷的位置信息更新如下：

$x_i\left(t+1\right)=X^b+S\times g\times \left(\left|x_i\left(t\right)-X^{\text{*}}\right|+\left|x_i\left(t\right)-X^b\right|\right)$ (8)

其中，$x_i\left(t\right)$ 表示第t次迭代时第i个小偷的位置信息；g为正态分布的随机向量，大小为1 × D；S为常数值。

3. 多策略改进的蜣螂优化算法

本章节介绍的改进型蜣螂优化算法(ODBO)融合了三项关键策略：首先是优势点集群的初始化方法和周期性突变机制；其次是动态生成反向解的策略，以及莱维飞行在处理边界冲突时的应用；最后是结合了鲸鱼搜索算法的螺旋搜索技术，并引入了基于t分布的扰动变异策略。

3.1. 佳点集群初始化策略和周期突变机制

为了增强算法种群的遗传多样性，本研究采取了一种周期性突变策略，这一策略使得优化算法能够周期性地在解空间内进行大幅度跳跃，有效地扩展了搜索范围。这种周期性跳跃有助于算法在广阔的解空间中进行深入探索，从而提高找到全局最优解的几率。蜣螂的四种种群更新方式为：

$x_i\left(t+1\right)=x_i\left(t\right)\times [1+A\times \left(0.5-rand\right)\times \sigma$ (9)

$\sigma =\left\{\begin{array}{c}1\cdots t=nT\\ 0\cdots t\ne nT\end{array}\right\}n=1,2,3,\cdots$ (10)

其中A为突变幅度；rand表示按照均分布N (0, 1)随机生成的实数；T为突变周期，其值小于迭代次数；$\sigma$ 是根据突变周期从一个区域搜索到另一个区域的冲量。

3.2. 动态反向学习策略

DBO算法中采用的动态区域选择策略，虽然在特定情况下有效，但可能会将搜索过程局限在较小的局部区域内，从而限制了对全局最优解的探索。为了克服这一局限，本研究提出了一种基于反向动态计算的策略，该策略通过扩展搜索边界，有助于算法跳出局部最优的局限，实现对更广阔解空间的探索。传统的初始化方法，如基于均匀分布的随机位置生成，虽然操作简便，但可能不足以形成对潜在最优解的有效“包围”。为了改善这一状况，本文引入了一种创新的方法，即利用Beta分布的特性来生成初始解，从而在解空间中形成对最优解的更紧密包围，类似Beta分布函数定义为：

$f\left(x\right)=\frac{1}{B\left(\alpha ,\beta \right)}{x}^{\alpha -1}{\left(1-x\right)}^{\beta -1},x\in \left[0,1\right]$ (11)

3.3. 边界违规处理

处理单个粒子位置超出预定边界的情况是一个关键问题。一种常见的简单处理方法是将超出的粒子位置直接设置为边界值，这种方法实现起来直截了当。然而，由于边界点往往不是全局最优解，这种直接的策略可能会限制优化过程的效果。这种方法的优点是易于实现。为了引入更多的随机性并提高搜索效率，Levy飞行作为一种数学方法被用来生成具有长尾分布的随机步长。Levy飞行能够模拟粒子在解空间中的随机游走，其步长遵循Levy分布。然而，Levy飞行可能产生的过长步长可能会导致粒子跳过潜在的最优解区域。为了平衡这一点，Levy飞行的步长会乘以一个适当的常数CC以降低其步长长度。本文采用一种新的基于Levy分布映射的新型边界处理方法。具体操作如下：

levy飞行机制结束后，采用贪婪策略，如果粒子的适应度小于前一代适应度，则对粒子进行替换。

$x_{ij}^{ı}=\left\{\begin{array}{c}\text{min}\left(U{b}^j\otimes Levy\left(\lambda \right),U{b}^j\right),x_{ij}>U{b}^j\\ \text{max}\left(L{b}^j,L{b}^j\otimes Levy\left(\lambda \right)\right),x_{ij}<L{b}^j\end{array}\right\}$ (12)

其中$x_{ij}$ 是边界处理后的粒子位置；λ是常数；Levy是随机搜索路径，其随机步长是Levy分布。符号是条目式乘法。图1直观地提供了一种直观的视角来展示粒子边界处理方法。当粒子$x_{ij}$ 跳出上边界和下边界时，通过Levy飞行调整其位置，确保有效搜索解空间。

Figure 1. Diagram for particle boundary processing

图1. 粒子边界处理方法图

3.4. 引入鲸鱼优化算法螺旋搜索策略和t分布扰动变异策略

3.4.1. 鲸鱼优化算法螺旋搜索更新机制

在蜣螂优化算法(DBO)中，如果按照当前的在产卵区域内繁殖雏球，这肯定会使种群在短时间内快速收敛，但也会导致种群的多样性降低，容易使算法陷入局部最优；因此对蜣螂算法繁殖阶段的这个公式进行改进，在蜣螂优化算法(DBO)中，盗窃蜣螂的行为对于种群多样性和算法的全局搜索能力有着重要影响。然而，传统的盗窃行为可能过于依赖当前搜索区域，导致种群多样性的降低，增加了算法陷入局部最优解的风险。为提升算法的全局探索性及种群的遗传多样性，本研究对蜣螂优化算法中的盗窃蜣螂行为引入了螺旋搜索策略。该策略仿照自然界中某些生物的螺旋形运动轨迹，使个体能够沿螺旋路径在解空间内进行探索，有效拓宽了搜索视野，增加了发现更优解的可能性。在经改进的DBO算法框架下，盗窃蜣螂在更新位置时，放弃了传统的简单复制或随机变异手段，转而依据其当前位置与历史搜索数据，采纳螺旋搜索策略来开辟新的探索路径。在每一轮迭代过程中，盗窃蜣螂依据自身的当前坐标和过往搜索经验，确定螺旋探索的起始点、半径及旋转角度，继而沿此螺旋轨迹进行搜索，并依据所获解的适应度来优化自身位置。这种更新机制使得盗窃蜣螂在维持与种群当前状态的联系的基础上，能够突破局部搜索局限，向更广阔的解空间扩展探索，从而为种群多样性的增加和算法全局搜索能力的提升做出了贡献。螺旋搜索策略的融入，不仅助力算法摆脱局部最优的困境，也为种群在持续搜索过程中的多样性维持提供了保障，显著增强了算法解决复杂优化问题的综合效能。

${\text{B}}_{\text{i}}\left(\text{t}+1\right)={\text{X}}^{\text{*}}+{\text{b}}_1\times \left({\text{B}}_{\text{i}}\left(\text{t}\right)-{\text{Lb}}^{\text{*}}\right)+{\text{b}}_2\times \left({\text{B}}_{\text{i}}\left(\text{t}\right)-{\text{Ub}}^{\text{*}}\right)$ (13)

鲸鱼优化算法(WOA)借鉴了鲸鱼的社会捕食模式，通过群体中的领导者引导，实现快速而多样的搜索。算法中，领导者通过发泡网攻击策略，指引其他成员，占群体的10%到20%。追随者根据以下公式更新位置：

受到鲸鱼算法中头鲸种群围捕猎物的启发，鲸鱼算法在迭代过程中，个体鲸鱼会使用螺旋搜索策略来更新与猎物的位置，这不仅保证了算法的收敛速度，而且可以增加个体的多样性。鲸鱼围捕猎物阶段公式如下：

$X\left(t+1\right)=D^t\cdot e^{cl}\cdot \cos \left(2\pi l\right)+X^{*}\left(t\right)$

$D^{\prime }=\left|X^{\ast }\left(t\right)-X\left(t\right)\right|$

$Po{s}_{new}=po{s}_b\left(t\right)+\left(po{s}_b\left(t\right)-po{s}_c\left(t\right)\right)\times C\times Levy$ (14)

但该策略很容易受到定义参数c的影响。较大的c会使算法衰减过快，导致算法局部最优，较小的c会导致算法收敛缓慢。为了解决这个问题，引入了动态螺旋搜索形状的参数r。

$r=e^{cgcos\left(\frac{\pi \cdot t}{Max\_iteration}\right)}$ (15)

式中：|X⃗ best(t) − X⃗ (t)|表示当前鲸鱼个体与最佳位置鲸鱼之间的距离向量；常量系数b决定了鲸鱼个体螺旋前进时的螺旋线形状，b取值为1时即为普通的对数螺旋线，l是[−1, 1]之间的随机数。WOA算法中鲸鱼个体位置向量X⃗ (t)的每一个分量在种群更新时均独立进行。

3.4.2. T分布扰动变异

在T分布中，随着自由度值的减小，曲线的形状越来越平，曲线的中部越低，曲线两侧的尾端翘起的幅度越大。使用T分布扰动蜣螂个体的位置，实现种群的变异，然后更新变异后的蜣螂个体位置的目标函数值，对比前一代最优函数值，如果结果更好，则改当前最优值。T分布扰动公式如下：

$x_i^t=x_i+x_i\cdot t\left(iter\right)$ (16)

式中：x，是变异后种群中第i个布谷鸟窝新的位置；x是变异前的个体位置；t (iter)为T分布值，以迭代次数为自由度。算法迭代前期，iter数值很小，由T分布函数生成的结果近似于柯西变异，全局搜索能力强，晚期iter数值偏大，类似高斯变异，拥有良好的局部搜索能力，进而使算法的搜索精度得以提高。

3.5. 算法复杂度分析

在深入探究DBO (Dung Beetle Optimizer，即蜣螂优化算法)的时间复杂度时，我们可以将其分解为三个核心组成部分：种群的初始化过程、适应度的评估环节，以及个体的位置更新机制。假设我们有一个最大迭代次数T、种群规模N，以及问题维度D的设定。对于种群的初始化，其时间复杂度为O (N × D)，这是因为每个个体都需要在D维空间中设定一个初始位置。接着，适应度评估的时间复杂度为O (N × T)，因为每个个体在每次迭代时都需要计算其适应度值。在个体的位置更新方面，DBO算法模拟了四种不同类型的蜣螂行为：滚球、繁育、觅食(此处可能原指“小蜣螂”的某种觅食行为，为简化表述而调整)、以及偷窃。每种蜣螂在种群中都有一定的数量N，且这些行为在每次迭代时都会对所有个体进行更新。尽管每种蜣螂的更新方式可能有所不同，但总体上，这些更新操作的时间复杂度最高可达到O (max (N_i) × T × D)。然而，由于所有N_i的总和等于种群规模N，因此我们可以将DBO算法的整体时间复杂度简化为O (max (N_i) × T × D)。

接下来，我们介绍ODBO算法(Omnifarious Dung Beetle Optimizer，即多维度蜣螂优化算法)，它是在DBO的基础上进行了扩展，并融入了三种新的策略。首先，佳点集群初始化策略和周期突变机制主要作用于初始化阶段，它们并没有增加额外的位置更新或适应度评估步骤，因此ODBO算法在这一阶段的时间复杂度保持不变。其次，ODBO算法还引入了动态反向学习和边界违规处理策略，并结合了鲸鱼优化算法和t分布扰动变异。尽管这些新策略增加了算法的复杂性，但它们在位置更新和适应度评估方面的最大时间复杂度仍然分别为O (N × D)和O (N × T)。因此，综合考虑所有因素，ODBO算法的整体时间复杂度仍然保持在O (N × T × D)，与DBO算法相同。

3.6. 算法复杂度分析

所提出的ODBO算法的复杂度分析如下图2。优化器的复杂度是衡量算法效率的关键指标之一。ODBO算法的复杂性主要包括以下几个过程，如下图3：初始化；通过Beta分布计算反射解；周期突变机制；螺旋搜索；t分布扰动变异；以及使用新的边界处理方法更新蜣螂的位置。假设在具有D个变量的问题中，涉及N个解和T次迭代。首先，算法的初始化复杂度为O (N)。然后，计算N个反射解的复杂度为O (T * N)。在ODBO中，每个周期需要评估N组解，总评估次数为4 ∗ T ∗ N。因此，蜣螂寻找最佳位置的时间复杂度约为O (4 ∗ T ∗ N)，简写为O (T ∗ N)。综上所述，ODBO的总体时间复杂度为O (ODBO) = O (N + T ∗ N ∗ (1 + D + N))。尽管相对于DBO算法增加了一些时间开销，但性能得到了显著提升。

Figure 2. Pseudocode diagram for algorithm

图2. 算法伪代码图

Figure 3. Flowchart of algorithm

图3. 算法流程图

4. 仿真实验及结果分析

4.1. 测试函数说明

为了全面评估ODBO算法的寻优性能，我们采用了表1中列出的17个经典测试函数。这些测试函数被分为三类：

1) 高维单峰值函数(F1至F7)：这些函数仅含有一个全局最优解，能够有效检验算法的开发(或称为局部搜索)能力。

2) 高维多峰值函数(F8至F13)：这些函数不仅包含一个全局最优解，还包含多个局部最优解，是检验算法全局搜索能力和局部逃逸能力的理想选择。

3) 固定维度多峰函数(F14至F17)：此类函数在特定维度下具有多个峰值，有助于验证算法在探索和开发能力之间的平衡。

Table 1. Test functions

表1. 测试函数

函数	名称	维度	范围	最优值	函数	名称	维度	范围	最优值
F1	Sphere	30/100	[−100, 100]	0	F11	Griewank	30/100	[−600, 600]	0
F2	Schwefel2.22	30/100	[−10, 10]	0	F12	Penalized	30/100	[−50, 50]	0
F3	Schwefel1.2	30/100	[−100, 100]	0	F13	Penalized2	30/100	[−50, 50]	0
F4	Schwefel2.21	30/100	[−100, 100]	0	F14	Foxholes	2	[−65, 65]	0.9980
F6	STEP	30/100	[−100, 100]	0	F15	Kowalik’s	4	[−5, 5]	0.0003
F7	Quartic	30/100	[−1.28, 1.28]	0	F21	Shekel5	4	[0, 10]	−10.153
F8	Schwefel	30/100	[−500, 500]	−12569	F22	Shekel7	4	[0, 10]	−10.402
F9	Rastrigin	30/100	[−5.12, 5.12]	0	F23	Shekel10	4	[0, 10]	−10.536
F10	Ackley	30/100	[−32, 32]	0

为确保实验的公平性和可比较性，所有算法的实验仿真均在相同的软硬件平台上进行，具体使用的是Matlab 2021a软件。实验参数统一设置如下：最大迭代次数T设为300，种群数量pop设为30。每种算法均独立运行30次，并以其30次寻优结果的最好值(Best)、平均值(Mean)和标准差(Std)作为评价指标。

通过这三类不同类型的测试函数，我们旨在全面而深入地评估ODBO算法的寻优性能。

4.2. 改进策略有效性分析

ODBO算法是在DBO算法的基础上进行了三项关键性改进，每项改进分别与DBO融合，形成了三种不同的变体算法：

1) ODBO1：通过将种群初始化策略和周期突变机制引入到DBO中，我们得到了ODBO1。这一改进旨在提升算法在初始阶段的多样性和在迭代过程中的突变能力。

2) ODBO2：在DBO的基础上，我们加入了生成反向解的动态学习反向策略以及莱维飞行边界违规处理机制，从而诞生了ODBO2。这一改进旨在增强算法在搜索空间中的探索能力和对边界条件的处理能力。

3) ODBO3：通过将螺旋搜索策略和t分布扰动变异融入DBO，我们得到了ODBO3。这一改进旨在提高算法在局部搜索中的精细度和在全局搜索中的随机性。

为了全面评估ODBO及其变体算法的性能，我们将其与DBO、MSADBO (麻雀搜索算法) [10]等五种算法进行了对比实验。实验采用了表1中列出的17个测试函数，每种算法均独立运行30次，并记录其寻优结果的最好值(Best)、平均值(Mean)和标准差(Std)。其中，最好值反映了算法的精确性，即其能够找到的最优解的质量；平均值和标准差则共同反映了算法的稳定性，即其多次运行结果的一致性和可靠性。实验结果如表2所示。

表2中的加粗数据表明了相较于DBO算法，平均寻优精度有所降低的值。根据表2不同策略寻优结果表2的数据分析，我们可以得出以下结论：

与DBO相比，ODBO1、ODBO2和ODBO3分别在12个、9个和12个测试函数上实现了平均寻优精度的提升。而ODBO算法在13个函数上的平均寻优精度相较于DBO有明显提高，尽管在其余4个函数上的提升幅度不大，但在寻优结果的最好值和标准差方面却有所优化。具体来看，ODBO1在函数F1至F4上的最优收敛值达到了理论最优解，这充分证明了佳点集群初始化策略和周期突变机制对于提升算法收敛精度的有效性。ODBO2在F1至F11 (除F6外)的10个测试函数上，无论是最优收敛值还是平均收敛精度，都实现了大幅提升。特别是在多峰函数F11上，ODBO2的标准差相较于DBO更小，这表明在DBO中引入反向解策略能够显著提高算法的稳定性。而ODBO3在F9和F11两个函数上的平均值和最优收敛值都达到了理论最优解，要知道，F9的Rastrigin函数是一个高度多模态的函数，具有许多局部极小值，且这些极小值的位置规则分布，优化条件十分苛刻。ODBO3能够找到其全局最优解，说明将鲸鱼算法的螺旋搜索策略和t分布扰动变异融入DBO中，可以显著提升算法的寻优性能，并增大跳出局部最优解的概率。对于固定维度函数F14至F23，从F13、F15以及F21至F23的数据可以看出，融入了三种策略的ODBO在平均收敛精度上相较于DBO有了显著提升。而对于函数F14，虽然ODBO的平均收敛精度略低于DBO，但在最优精度值上却与DBO基本相当。这表明，融入三种策略的ODBO能够很好地平衡算法的探索与开发能力。与DBO相比，融合了三种改进策略的ODBO在F1至F23 (除4个函数外)上的最优收敛值、平均收敛精度以及标准差都有所提升。特别是在F1至F2上的最优收敛值，以及F9至F11上的平均收敛精度，都达到了理论最优解，且未出现负优化的现象。这充分证明了三种策略融合的有效性。

Table 2. Optimization results of different strategies

表2. 不同策略寻优结果

函数	指标	DBO	ODBO1	ODBO2	ODBO3	QHDBO	MSADBO	ODBO
F1	Best	6.62E−104	7.5E−214	2.3E−249	9.2E−192	4.8E−249	8.93E−298	0
	Std	2.866E−51	3.2E−138	7.81E−72	2.6E−139	0	0	0
	Mean	5.233E−52	5.9E−139	1.43E−72	4.7E−140	2E−212	4.01E−193	4.7E−283
F2	Best	8.206E−52	7.3E−105	1.1E−125	9.5E−107	1.6E−129	2.19E−148	1.6E−159
	Std	5.89E−32	3.68E−69	1.4E−124	5.13E−72	3E−106	1.78E−105	4.5E−138
	Mean	1.278E−32	6.81E−70	4.7E−125	1.08E−72	5.7E−107	3.27E−106	8.2E−139
F3	Best	3.588E−91	7.9E−242	6E−248	1.9E−183	4.8E−242	1.02E−218	0
	Std	1.427E−53	1.8E−127	0	1.9E−123	0	1.45E−138	0
	Mean	3.413E−54	3.2E−128	1E−245	3.5E−124	3.5E−211	2.64E−139	5.6E−281
F4	Best	4.253E−51	3.5E−111	3.2E−125	5.35E−96	2.7E−127	5.36E−157	6.6E−166
	Std	2.828E−33	8.47E−68	7.4E−126	2.9E−69	1.1E−103	8.875E−93	1.7E−140
	Mean	7.44E−34	1.69E−68	4.3E−125	5.37E−70	2E−104	1.809E−93	3.1E−141
F6	Best	6.694E−19	0.009342	0.027981	0.010332	4.72E−11	2.709E−15	0.018906
	Std	7.375E−14	0.01537	0.195494	0.024425	0.065632	1.219E−12	0.030919
	Mean	4.167E−14	0.032816	0.233292	0.051217	0.073473	9.049E−13	0.063923
F7	Best	0.0001567	9.45E−06	5.07E−05	2.82E−06	8.71E−06	1.931E−05	4.18E−06
	Std	0.0011708	0.000312	0.000209	0.000245	0.000202	0.000144	0.000243
	Mean	0.00172	0.000291	0.000269	0.000287	0.000205	0.0002141	0.000203
F8	Best	−4189.829	−1.3E+53	−2.1E+31	−1.2E+59	−4189.83	−1.09E+37	−1706.04
	Std	532.17475	2.33E+52	3.78E+30	2.26E+58	797.5957	1.985E+36	184.1298
	Mean	−3249.935	−4.5E+51	−6.9E+29	−4.1E+57	−3183.34	−3.68E+35	−1305.42
F9	Best	0	0	0	0	0	0	0
	Std	8.5886184	0	0	0	0	0	0
	Mean	2.3126043	0	0	0	0	0	0
F10	Best	8.882E−16	8.88E−16	8.88E−16	8.88E−16	8.88E−16	8.882E−16	8.88E−16
	Std	0	0	0	0	0	0	0
	Mean	8.882E−16	8.88E−16	8.88E−16	8.88E−16	8.88E−16	8.882E−16	8.88E−16
F11	Best	0	0	0	0	0	0	0
	Std	0.0592216	0	0	0	0	0	0
	Mean	0.0318332	0	0	0	0	0	0
F12	Best	6.501E−19	0.006201	0.004179	0.003074	0.00148	2.901E−15	4.71E−32
	Std	4.567E−06	0.004989	0.021025	0.006014	0.029792	1.494E−12	1.13E−05
	Mean	8.339E−07	0.013597	0.027632	0.015356	0.034312	7.693E−13	3E−06
F13	Best	3.68E−16	0.001118	0.264409	0.009342	0.000259	1.551E−13	1.35E−32
	Std	0.0680511	0.008824	0.152237	0.081651	0.005239	0.0335791	1.26E−06
	Mean	0.052793	0.013238	0.640819	0.110192	0.006627	0.0133493	3.44E−07
F14	Best	0.9980038	12.67051	0.998078	0.998004	10.76318	0.9980038	0.998004
	Std	2.0316918	2.31E−13	1.110446	1.022965	0.953117	1.8283697	4.064419
	Mean	1.8846914	12.67051	2.304755	1.490099	11.68512	1.4557832	3.180025
F15	Best	0.0003076	0.000308	0.000435	0.000358	0.000307	0.0003075	0.000307
	Std	0.0003926	5.37E−05	0.003715	0.000339	4.07E−05	0.0003167	3.48E−05
	Mean	0.0007954	0.00035	0.003789	0.000779	0.000339	0.0005582	0.000336
F21	Best	−10.1532	−10.0398	−8.64979	−9.97054	−10.1532	−5.055198	−10.1532
	Std	2.8012857	1.496831	1.034111	1.880955	2.375941	2.0796472	0.00699
	Mean	−6.869318	−7.79054	−5.47573	−7.10676	−6.58434	−3.385713	−10.1472
F22	Best	−10.40294	−10.3271	−10.3265	−9.75886	−10.4029	−10.40294	−10.4029
	Std	2.9005639	1.653269	1.82438	1.698345	1.819441	2.7975311	0.026964
	Mean	−8.113965	−7.78766	−6.0879	−6.78902	−5.78918	−3.245011	−10.3929
F23	Best	−10.53641	−10.2633	−9.04942	−10.4956	−10.5364	−5.128481	−10.5363
	Std	2.8747407	1.501277	0.918715	1.865828	2.200108	2.1004129	0.01602
	Mean	−8.099543	−7.88544	−5.47779	−6.9271	−6.21004	−2.945935	−10.5277

5. 车间排产优化问题求解

为了进一步验证ODBO算法在实际工程应用中的可靠性，选取某制造企业车间生产排产调度设计问题进行验证。车间工单排产问题需要最小化成型炉占用位置，具体描述如下。

5.1. 模型描述

工单排产问题描述如下：

1) 在某一时间共有N个工单等待排产，每个工单包含以下关键信息：胎具号、组数(占用成型炉位置的个数)、圈数、产线信息、温度等。

2) 生产线有M个节点，每个节点只有一台加工机器，每台机器上有P个位置。

3) 吊炉有6个位置，每个位置的最大运转圈数和工艺路线相关略有不同；双层炉有5个位置。在这里它们统称成型炉

4) 工单在排产时，应避免同一胎具的不同工单分配到相同班次，除非其运转圈数相加不大于最大运转圈数。(共用)，而胎具合并就是两种不同编号的胎具实际上是合并的关系。

5) 尽量减少胎具的搬运次数。

5.2. 变量定义

N：待排产的工单数量；

M：生产线节点数量；

P：每个节点的位置数量；

x：工单分配矩阵，元素为二元变量，表示工单是否分配到节点的位置；

T：工单的运转圈数矩阵；

C：节点在特定温度下的最大运转圈数矩阵；

S：胎具合并的工单集。

5.3. 目标函数

本文仅考虑单个目标函数，即成型炉位置占满度最大化：

$\text{max}{\displaystyle \sum }_{j=1}^M{\displaystyle \sum }_{k=1}^p{\displaystyle \sum }_{i=1}^N{x}_{ijk}$ (17)

该目标函数就是用最少的机器最少的位置来完成当天的生产需求。

5.4. 约束条件

1) 允许多个工单分配到同一个位置，只要它们的总运转圈数不超过位置的最大承载能力

引入符号：

$T_{ij}$ ：工单i在位置j上的运转圈数。

$C_j$ ：表示位置j的最大承载能力。

约束公式：

${\displaystyle \sum }_{i=1}^N{T}_{ij}{x}_{ijk}\le C_j$ (18)

2) 不同工艺路线的工单不能分到同一个成型炉上，因为成型炉一旦开工就不切换温度了。

引入符号：

$R_i$ ：工单i的工艺路线。

$x_{ijk}$ ：工单i是否分配到成型炉j的位置k上，二元变量，1表示分配，0表示不分配。

约束公式：

$x_{ijk}{R}_i=x_{ijk}{R}_j$ (19)

3) 每个成型炉上分配到的工单所实际占用的位置数须小于等于6。

${\displaystyle \sum }_{i=1}^N{x}_{ijk}\le 6$ (20)

5.5. 算例分析

本文以某汽车制造公司的实际生产排程为例，利用所设计的算法求解，算例中涉及22个成型炉，并从当天APS系统历史抽取出来70个某车间待排程工单。

其中前14个成型炉是吊炉，后8个是双层，这里展示白夜班认为是两个不同的成型炉编号，具体成型炉配置信息如表3。

Table 3. Configuration information of molding furnace

表3. 成型炉配置信息

成型炉	位置	圈数	工艺路线
吊炉	6	34	CW
吊炉	6	28	GW
吊炉	6	21	DW
双层炉	5	35	CW
双层炉	5	30	GW

然后这里的工单参数如下表，这里只展示部分工单数据因为量比较大，数据来源如下表4。

Table 4. Actual work order data

表4. 实际工单数据

工单编号	组数	圈数	工艺路线	胎具号	成型炉编号
1	2	28	GW	1	DL1
2	1	34	CW	2	DL2
3	3	25	GW	1	DL3
4	5	28	GW	2	DL3
5	6	34	CW	3	DL2
6	1	15	CW	4	DL1
7	2	30	CW	5	DL1
8	1	2	CW	6	DL1
9	1	5	CW	6	DL1
10	1	25	GW	10	DL4

如下图4是从企业APS系统获取到的原始数据，因实际生产需求，系统排产不满足现状。首先可以看出当天某车间成型排产若干个工单，但是实际上最后分配的实际情况却是很多机器的负载量要么过低要么过高，这里当天机器负载圈数204。

Figure 4. Raw data diagram of unplanned production in an enterprise’s internal system

图4. 某企业内部系统未排产原始数据图

如下图5是优化以后的最后结果。

Figure 5. Comparison chart before and after the production scheduling optimizer

图5. 排产优化器前后对比图

通过优化后的结果可以看出如图5，工单的分配均衡性得到了显著提升，各机器的负载更加均匀分布。所有工单的圈数都在限制范围内，且大部分机器的负载接近最大阈值204圈，表明资源利用率得到了有效提高。

6. 结束语

本文为提高蜣螂优化算法的优化性能，提出一种多策略改进的蜣螂优化算法(ODBO)，使用标准测试函数验证了改进策略的有效性，将ODBO与新型群智能优化算法在17个测试函数上的优化结果进行比对，结果表明ODBO比原始DBO和对比算法具有更高的收敛精度、更快的收敛速度和更强的鲁棒性；再将ODBO应用于车间排产优化问题实例，验证了ODBO在实际工程方面的适用性和可靠性；在后续的工作中，将继续提高算法的性能，提高算法的效率，减少算法耗时，并考虑把ODBO运用在其他实际问题中。通过上述研究与实验，改进的ODBO算法在车间生产排产调度问题上展现出了较高的实用性和可靠性。通过实际数据验证，ODBO算法能够有效减少成型炉的占用位置数，优化生产效率。