具有逃脱机制的蚁狮算法及其应用

The Antlion Algorithm with Escape Mechanism and Its Applications

摘要: 本文介绍了一种受蚂蚁逃脱蚁狮陷阱方式启发而设计的具有逃逸机制的蚁狮算法。该算法的特点是在蚂蚁的随机游走中引入了曲线位移，增强了它们逃离陷阱的能力。我们将本算法与其他三种蚁狮算法进行了比较，并进行了大量测试，结果显示新构建的蚁狮算法具有更优越的性能。此外，我们将该算法与K-Means聚类算法的质心选择过程相结合，以提高其聚类性能。进一步，我们将这种新算法应用于玻璃产品的分类，并取得了良好的结果。本研究展示了将自然机制融入算法设计的有效性，并在现实问题中得到了实际的应用。

Abstract: In this paper, we present an antlion algorithm with an escape mechanism inspired by the way ants avoid antlions’ traps. Our algorithm features a curved displacement in the random walk path of ants, which allows them to escape more efficiently. We compared our algorithm with three other antlion algorithms and conducted extensive testing, which showed that our modified antlion algorithm has superior performance. Furthermore, we integrated our algorithm with the centroid selection process of the K-Means clustering algorithm to improve its clustering performance. We applied this new algorithm to the classification of glass products and achieved good results. Our research demonstrates the effectiveness of incorporating natural mechanisms into algorithm design and how it can lead to practical applications in real-world problems.

1. 引言

群智能优化算法 [1] 是一种仿生优化算法，它模拟自然种群的行为和规则，利用合作和进化机制，通过简单个体之间的相互作用来完成给定任务。随着时间的推移，群智能优化算法经历了一系列的发展和演变。遗传算法(Genetic Algorithm, GA) [2] 于1975年问世，是最早提出的一种群智能算法。GA通过模拟遗传演化和自然选择过程来实现全局搜索，然而，在收敛速度和解的质量方面存在局限性。随后，蚁群优化算法(Ant Colony Optimization, ACO) [3] 于1992年提出，模拟了蚂蚁的觅食和通信行为，具有良好的全局搜索能力，特别适用于离散优化问题，但在连续优化问题上可能性能受限。粒子群优化算法(Particle Swarm Optimization, PSO) [4] 于1995年提出，通过模拟群体中粒子的移动来寻找最优解，虽然收敛快速并具有鲁棒性，但容易陷入局部最优。人工鱼群算法(Artificial Fish Swarm Algorithm, AFSA) [5] 于2002年出现，模拟了鱼类的觅食和集群行为，并在解决连续优化问题上表现出一定的优势。然而，在高维问题中，AFSA的性能可能受到影响。人工蜂群算法(Artificial Bee Colony, ABC) [6] 于2005年提出，模拟了蜜蜂的觅食行为。ABC具有鲁棒性和多样性，但对初始条件敏感。有关群体智能优化算法的更多文章可参考 [7] [8] 。

蚁狮优化算法(ALO) [9] 是一种新型的群智能算法，最初由Seyedali Mirjalili提出，模拟了蚁狮在沙坑中捕捉蚂蚁的特殊狩猎方法。ALO具有参数少、收敛速度快等优点，并广泛应用于工程领域。然而，在ALO算法中，随机游走的蚂蚁根据轮盘赌策略选择蚁狮，其中选择概率由每个蚁狮的适应度确定。这种选择策略可能导致更多的蚂蚁随机在适应度较高的蚁狮周围徘徊。随着蚁狮适应度逐渐增加，蚂蚁大概率会被限制在一些精英蚁狮附近，导致搜索范围减少，算法陷入局部最优解。为了解决这些问题，对ALO算法提出了几项改进。例如，Kilic、Yüzgeç和Karakuzu [10] 通过将轮盘赌选择方法替换为锦标赛选择方法，提高了蚂蚁随机漫步模型的效率，显著减少了算法的运行时间。此外，Emary和Zawbaa [11] 将Levy飞行随机游动方法应用于ALO算法，取代了蚂蚁使用的正态分布随机游走，极大地提高了算法的优化效率。

该算法的灵感源于观察到蚂蚁在被蚁狮捕捉时的逃逸行为。在捕猎时，蚁狮会向坑穴附近抛掷沙子，以阻止蚂蚁逃跑。而蚂蚁为了躲避蚁狮的捕捉，除了会向坑穴外进行垂直方向的移动，还会本能地进行横向游走，如此通过垂直和横向移动的组合形成的曲线逃逸路线可以有效地帮助蚂蚁避免被捕捉。这种行为启发了我们将曲线位移纳入蚂蚁随机行走路径的设计中，从而设计了一个具有逃逸机制的蚁狮算法。

本文结构如下：第1节介绍了本文的研究背景和动机；第2节详细介绍了经典蚁狮算法的关键步骤；第3节解释了如何实现蚂蚁的逃逸机制并将其嵌入到经典蚁狮算法中。我们还使用CEC2005和CEC2017测试函数将新设计的算法与三种现有蚁狮算法进行了比较。第4节将新设计的算法与K-Means聚类算法结合，以提高质心选择的效率。我们使用标准UCI数据集将此算法与类似的聚类算法进行了比较。第5节提供了一个具体的应用示例，我们使用新设计的聚类算法解决了古玻璃产品分类问题，并取得了令人满意的结果。最后，我们对文章进行了总结，并对之后的研究方向提出设想。

2. 经典蚁狮算法

蚁狮一般生活在干燥、多沙的地区，主要的猎物是蚂蚁。它们会挖出类似于漩涡状的锥形沙坑，当作自己的巢穴和狩猎用的陷阱。这些沙坑的边缘十分陡峭，使猎物很容易掉进去。故蚁狮大多时间会在坑底等待猎物接近，当猎物掉进去时，它们会立即试图抓住它。为了防止猎物逃跑，蚁狮会向陷阱边缘投掷沙子，使猎物滑入坑底，最终被蚁狮食用。完成进食后，蚁狮会修缮陷阱，并准备下一次捕猎。

蚁狮算法是一种创新优化方法 [9] ，它模拟了蚂蚁的觅食过程和蚂蚁的狩猎行为。该算法设置了两组集群，蚂蚁和蚁狮。在每次迭代中，会通过轮盘赌策略选择出蚁狮，并将其作为临时最优解，蚂蚁会围绕着选中的蚁狮进行随机游走，寻找更优解。当搜索到优于选中蚁狮的解后，蚁狮会将蚂蚁吃掉并取代其位置，更新最优解。随着迭代次数的增加，蚂蚁随机游走的范围会逐渐缩小，并逐渐向全局最优解靠近，算法的精确度也会逐渐提高。

蚁狮算法主要包括两个关键策略：蚂蚁随机游走和轮盘赌选择精英策略。现在，让我们深入研究这两种策略的细节。

2.1. 蚂蚁的随机游走

蚁狮算法模拟了随机游走的蚂蚁在搜索过程中探索未知搜索空间的关键行为。在该算法中，每只蚂蚁在搜索空间内随机选择一个起点，并根据特定的概率规则确定下一步的移动方向。在随机游走过程中，蚂蚁会根据自己的经验和信息素不断调整自己的移动方向，直到找到最佳解决方案或达到搜索时间的上限。蚁狮算法利用蚂蚁的随机游走，有效避免了局域最优解的困点，提高了搜索效率，在各种优化问题中取得了较为理想的结果。

在蚁狮算法中，蚂蚁随机游走 [9] 是通过一个基本的统计函数实现的，该函数表示为：

$X\left(t\right)=\left[0,ssum\left(2\gamma \left(t_1\right)-1\right),\cdots ssum\left(2\gamma \left(t_n\right)-1\right)\right]$ ， (1)

其中， $X\left(t\right)$ 为随机游走的步数集合； $t$ 为随机游走的步数； $ssum$ 为计算累加和； $\gamma \left(t\right)$ 是定义的一个随机函数，公式如下：

$\gamma \left(t\right)=\{\begin{array}{c}1,rand>0.5\\ 0,rand\le 0.5\end{array}$ ， (2)

其中， $rand$ 是在[0, 1]间取的随机数。

而在蚁狮优化算法中，由于蚁狮设置陷阱，限制了蚂蚁随机游走的范围，故对公式(1)进行了修改，以满足行走范围的局限性 [9] 。修改后的公式如下：

$X_i^t=\frac{\left(X_i^t-a_i\right)\left(d_i^t-c_i^t\right)}{\left(b_i-a_i\right)}+c_i^t$ ， (3)

其中， $X_i^t$ 为蚂蚁在第 $t$ 次迭代中第 $i$ 维的位置； $a_i$ 和 $b_i$ 分别指第 $i$ 维中随机游走的最小值和最大值； $c_i^t$ 和 $d_i^t$ 为第 $t$ 次迭代时在第 $i$ 维中随机游走的最小值和最大值。

因蚂蚁游走的路线会受到蚁狮位置和陷阱尺寸的影响，故参数 $c_i^t$ 和 $d_i^t$ 的值根据特定的规则确定 [9] 。

$c_i^t=Antlio{n}_j^t+c^t{\text{andd}}_i^t=Antlio{n}_j^t+d^t$ ， (4)

其中， $c^t$ 和 $d^t$ 分别是第 $t$ 次迭代中最小和最大的向量； $Antlio{n}_j^t$ 是在第 $t$ 次迭代中第 $j$ 只蚁狮的位置。

当蚂蚁掉进陷阱后，蚁狮会向沙坑边缘抛掷沙子，并把蚂蚁的向下拖拽，导致蚂蚁随机游走的范围会迅速缩小。我们采用如下方程模拟这种现象：

$c_i^t=\frac{c^t}{I},d_i^t=\frac{d^t}{I}\text{and}I={10}^{\omega }\frac{t}{T}$ ， (5)

其中，变量 $I$ 表示比例系数； $T$ 表示允许的最大迭代次数； $\omega$ 是一个参数，其值由 $t$ 的大小决定。 $\omega$ 和 $t$ 之间的关系如表1所示。

Table 1. The value of parameters

表1. 参数 $\omega$ 的值

当表1中的迭代次数增加时，蚂蚁随机游走的半径减小，保证了ALO算法的收敛性。

2.2. 精英策略和轮盘赌策略

每次迭代后，算法都会选择适应度最高的蚁狮作为精英蚁狮，之后蚂蚁会通过轮盘赌策略选择一只蚁狮，并围绕该蚁狮进行随机游走。蚂蚁的位置由下述公式确定 [9] 。

$An{t}_i^t=\frac{R_A^t\left(m\right)+R_E^t\left(m\right)}{2}$ ， (6)

其中， $An{t}_i^t$ 是指第 $i$ 个蚂蚁在第 $t$ 次迭代中的位置； $R_A^t\left(m\right)$ 表示在 $t$ 次迭代中，蚂蚁跟据轮盘赌策略选中蚁狮后，围绕其走 $m$ 步时得出的值；类似地， $R_E^t\left(m\right)$ 表示在第t次迭代中，蚂蚁围绕精英蚁狮走 $m$ 步得出的值；变量 $m$ 取自蚂蚁在随机游走期间所走步数范围内的任意值。

然而，由于轮盘赌策略是根据蚁狮的适应度为其分配概率，这可能会导致更多的蚂蚁围绕较高适应度的蚁狮进行游走，让算法有陷入局部最优的危险。

蚁狮优化算法将这两种策略相结合，对解空间进行更为有效地探索与开发，以求找到可能的最佳解。

2.3. ALO算法主要步骤

ALO算法的具体步骤如下：

1) 初始化数据：设置两个种群的参数，包括个体数、维度和迭代次数，并在指定范围内初始化蚁狮和蚂蚁的位置，计算它们各自的适应度。

2) 确定精英蚁狮：选择初始化后蚁狮种群中适应度最好的蚁狮作为精英蚁狮。

3) 轮盘选择：使用轮盘赌策略为每只蚂蚁选择一只蚁狮，根据选中蚁狮的位置更新蚂蚁的参数值，并让蚂蚁围绕所选蚁狮随机游走，更新蚂蚁位置。

4) 计算适应度：计算蚁狮和蚂蚁的适应度值，根据蚂蚁的位置和适应度更新蚁狮位置，两个种群中适应度最好的成为新精英蚁狮。

5) 判断是否终止：检查是否满足算法终止条件。如果满足，输出结果，返回精英蚁狮的位置及其适应度值，并结束迭代；否则，返回步骤3。

下面我们将介绍如何实现蚂蚁的随机游走。

3. 具有逃脱机制的蚁狮算法

为了避免过多蚂蚁在某些蚁狮周围进行无意义地游走，我们考虑修改它们的行走策略，以扩大搜索范围。

3.1. 逃脱机制

在现实捕猎的过程中，蚂蚁落入陷阱后会尽最大努力远离蚁狮并爬出陷阱。同许多其他动物相似，蚂蚁在垂直方向上移动的同时，本能地会在水平方向上进行游走，从而形成曲线状的运动轨迹。为了实现对这一现象的模拟，我们将蚂蚁的随机游走和曲线位移进行结合，使用正弦和余弦函数对其逃脱策略进行建模。

下面，我们将详细描述这个过程，并用数学公式来展现蚂蚁挣扎逃脱的过程。首先，由于蚂蚁具有二维视觉感知，故它们逃跑的方向是随机的。我们用 ${\gamma }_2\in \left(0,{360}^{\circ }\right)$ 来表示蚂蚁的逃跑方向。一般来说，当蚂蚁被陷阱困住后，会有两种挣扎逃脱的方式。一种方法是在逃跑时逐渐增加力量，直到达到极限，再慢慢耗尽；另一种方法则是在最初进行最有力的挣扎，然后逐渐削弱。我们可以分别用 $\sin \left(\gamma \right)$ 和 $\cos \left(\gamma \right)$ 来表示这两种方式。至于具体选择哪种方法，我们通过使用随机变量 ${\gamma }_3$ ，采用概率的形式来模拟蚂蚁选择方式的随机性。此外，由于蚂蚁在逐渐陷入困境的过程中，逃跑的力量会逐渐减弱，我们可以在逃避规则里乘上一个衰减系数，用 ${\gamma }_1=a-a\ast \left(t/T\right)$ 来表示，此处 $a$ 代表初始强度， $t$ 代表当前迭代次数， $T$ 代表迭代总数。考虑到不同的蚂蚁可能有着不同的斗争强度，我们在公式的末尾乘一个随机参数 $D=\left|{\gamma }_4\ast An{t}_i^t-An{t}_i^t\right|$ ， ${\gamma }_4$ 为一个随机数， $An{t}_i^t$ 表示蚂蚁 $i$ 在第 $t$ 次迭代中的状态。以上为蚂蚁挣扎逃避过程的描述，具体的参数设置和算法实现可能会根据实际的应用与问题而有所不同。

在下文中，我们将使用公式(7)至(10)来描述蚂蚁逃跑的过程。这种方法对蚂蚁的逃跑行为进行了更为真实的模拟，可以让蚂蚁的探索范围更广泛，从而降低陷入局部最优的风险。

$A{\text{nt}}_i^{t+1}=\{\begin{array}{c}An{t}_i^t+{\gamma }_1\ast \sin {\gamma }_2\ast D{\gamma }_3<0.5\\ An{t}_i^t+{\gamma }_1\ast \cos {\gamma }_2\ast D{\gamma }_3\ge 0.5\end{array}$ ， (7)

$D=\left\{\left|{\gamma }_4\ast An{t}_i^t-An{t}_i^t\right||i=1,2,\cdots ,n\right\}$ ， (8)

${\gamma }_1=a-a\ast \left(\frac{t}{T}\right)$ ， (9)

${\gamma }_2\in \left(0^{°},{360}^{°}\right)$ ， (10)

其中，γ₁~γ₄为参数， ${\gamma }_1$ 会随着迭代次数的变化而变化， ${\gamma }_3$ 和 ${\gamma }_4$ 为0到1之间均匀分布的随机数； $a$ 为常数，实验中取值为1。

值得注意的是，正弦余弦策略可以直接应用于算法设计 [12] [13] ，对此我们将其作为搜索方向来模拟蚂蚁的曲线运动。

3.2. 具有逃脱机制的ALO算法主要步骤

改进的算法包括以下步骤：

1) 初始化数据：在规定的范围内设置参数，如蚁狮和蚂蚁的数量、维度和迭代次数。随机为蚁狮和蚂蚁分配位置，并计算它们各自的适应度值。

2) 确定精英蚁狮：从初始种群中选择适应度最高的蚁狮作为精英蚁狮。

3) 轮盘选择：使用轮盘赌策略为每只蚂蚁选择一只蚁狮，并根据蚁狮的位置更新参数值。蚂蚁围绕所选蚁狮进行随机游走，更新位置。

4) 引入正弦余弦策略：跟据公式(7)更新蚂蚁位置。

5) 计算适应度：计算蚂蚁和蚁狮的适应度值，并依据蚂蚁的位置和适应度更新蚁狮位置，选择所有个体中适应度最好的成为新精英蚁狮。

6) 判断是否终止：判断是否满足算法的终止条件。如果满足，输出结果，返回精英蚁狮位置及其适应度值，并结束迭代；否则，返回步骤3。

3.3. 实验与分析

在本节中，我们比较了四种蚁狮优化算法在CEC2005和CEC2017部分测试函数上的性能。这四种算法分别为：新提出的具有逃跑机制的蚁狮优化算法(ALO-E)，结合柯西分布的蚁狮优化算法(CALO) [14] ，自适应蚁狮优化算法(PSALO) [15] 和经典蚁狮优化算法(ALO)。我们通过评估这些算法对测试函数的求解结果来分析它们的有效性。实验的运行平台为PyCharm Community Edition 2022.3.3，操作系统为Windows 10，内存大小为16 G，CPU为i5-1035G1。

两组测试函数如表2和表3所示。

Table 2. Some test functions from CEC2017

表2. 部分CEC2017测试函数

Table 3. Some test functions from CEC2005

表3. 部分CEC2005测试函数

在本节实验中，我们设置的参数如下：两个种群的大小均为20，最大迭代次数为10000。为了确保实验的准确性，我们对每个算法进行了20次独立运行，并计算每个基准函数的平均值和标准差。实验结果如表4所示。

Table 4. Comparison of results for solving test functions

表4. 求解测试函数结果对比

下面，我们对四种算法在求解上述23个函数时取得最佳均值和标准差的次数进行统计分析，如图1所示。其中，ALO-E算法的求解大部分最优且最为稳定，表明了具有逃跑机制的蚁狮算法的有效性。

Figure 1. The statistical analysis for the number of times with best results

图1. 最佳结果次数的统计分析

为了更好地展示ALO-E算法的优越性，我们给出了ALO-E、CALO、PSALO和ALO算法在1000次迭代下求解上述部分测试函数结果的收敛图，如图2所示。

Figure 2. Partial test function convergence result

图2. 部分测试函数收敛结果

4. 结合ALO-E的K-Means聚类算法

K-Means算法 [16] 是最常用的聚类算法之一，其核心为选择簇的数量并随机分配初始质心，再基于每个数据点和每个质心之间的欧式距离，将所有数据点分配到其对应的簇。通过一次次迭代，把各个簇的质心放在其他数据点的平均值处，并基于相同的原理对数据点进行重新分类，直到获得最佳聚类结果。值得注意的是，更新质心需要计算对应聚类中所有数据点的坐标平均值，这可能导致算法效率较低。

4.1. 改进K-Means聚类算法

为了提高K-Means聚类中质心更新的效率，我们将ALO-E算法应用到该过程中，即在初始化质心之后，采用ALO-E算法来获得新的质心。

以下是改进聚类算法的主要步骤：

1) 随机选取k个质心。

2) 计算每个数据点和每个质心之间的欧式距离，并根据该距离将样本分配到相应的聚类。

3) 运用改进的蚁狮算法更新质心。

4) 判断是否已达到最大迭代次数。如果达到，则结束迭代并输出聚类结果；否则，返回步骤3。

4.2. 实验与分析

为了证明改进聚类算法的有效性和优越性，我们将ALO-E算法结合K-Means (Kmeans-ALO-E)与传统的K-Means算法、粒子群优化算法结合K-Means (Kmeans-PSO) [17] 进行了比较分析。本次实验从UCI中选择了四个数据集：Iris、Wine、Seeds和Thyroid，具体信息如表5所示。

Table 5. The information for the four datasets

表5. 四个数据集的信息

为了对算法性能进行评估，我们使用了三个评估指标：召回率(recall)、准确度(precision)和F1精度，计算公式如下：

$recall=\frac{TP}{P}$ ， (11)

$precision=\frac{TP}{TP+FP}$ ， (12)

$F1=\frac{2\ast precision\ast recall}{precisiom+recall}$ 。 (13)

表6至表9为三个聚类算法应用在上述四个数据集的结果，展示了每种算法对数据点进行分组的准确性和有效性。我们可以看到，Kmeans-PSO在四个数据集上的三个评估指标绝大部分优于传统方法；而Kmeans-ALO-E算法的评估指标明显优于传统方法，且略优于Kmeans-PSO。由此我们可以得出，本文所提出的Kmeans-ALO-E算法为数据聚类提供了一种稳健有效的替代方案。

Table 6. Results of three clustering algorithms on the Iris dataset

表6. Iris数据集上三种聚类算法的结果

Table 7. Results of three clustering algorithms on the Wine dataset

表7. Wine数据集上三种聚类算法的结果

Table 8. Results of three clustering algorithms on the Seeds dataset

表8. Seeds数据集上三种聚类算法的结果

Table 9. Results of three clustering algorithms on the Thyroid dataset

表9. Thyroid数据集上三种聚类算法的结果

为了更直观地展现Kmeans-ALO-E算法的聚类性能，我们绘制了该算法在四个数据集上的聚类情况，如图3和图4所示。

Figure 3. Clustering of the Kmeans-ALO-E algorithm on the Iris and Wine datasets

图3. Kmeans-ALO-E算法在Iris和Wine数据集上的聚类

Figure 4. Clustering of the Kmeans-ALO-E algorithm on the Thyroid and Seeds datasets

图4. Kmeans-ALO-E算法在Thyroid和Seeds数据集上的聚类

5. Kmeans-ALO-E算法在古代玻璃制品分类中的应用

古代玻璃制品的分类源于“古代玻璃制品成分分析和鉴定”问题，关于这个问题的具体描述和数据可以在网站上找到：(www.mcm.edu.cn)。我们利用Kmeans-ALO-E算法通过选择合适的化学成分来对每个玻璃类进行亚类划分。

考虑到数据的复杂性，我们首先使用公式(14)对数据集进行归一化，为后续处理和分析数据提供便利。

$x^{\prime }=\frac{x-\min \left(x\right)}{\max \left(x\right)-\min \left(x\right)}$ 。 (14)

我们使用准确率(ACC)来评估实验结果，其定义公式为：

$ACC=\frac{TP+TN}{ALL}$ 。 (15)

图5展示了Kmeans-ALO-E算法在高钾玻璃数据集上的聚类结果。由图可得，高钾玻璃可分为两组：高钾低硅玻璃和高钾高硅玻璃。改进的算法在该数据集上实现了100%的准确率(ACC)。

Figure 5. Kmeans-ALO-E clustering in a high-potassium glass dataset

图5. Kmeans-ALO-E在高钾玻璃数据集上的聚类

同样，图6展示了Kmeans-ALO-E算法在铅钡玻璃数据集上的聚类结果。由图可得，铅钡玻璃根据铅含量可分为三个子类：低铅铅钡玻璃、中铅铅钡和高铅铅钡。改进算法在该数据集上的准确率(ACC)为91%。

Figure 6. Kmeans-ALO-E clustering in the lead-barium glass dataset

图6. Kmeans-ALO-E在铅钡玻璃数据集上的聚类

上述两个古老玻璃制品的分类问题证明了Kmeans-ALO-E算法在实际应用中的良好性能。

6. 总结

我们通过模拟蚂蚁被蚁狮追捕时的逃跑路线，将蚂蚁的逃跑策略融入蚁狮优化算法，对算法进行了改进。在进行了大量的数值实验后，我们观察到这种策略对算法的全局优化产生了积极影响。此外，我们将这种新设计的ALO算法引入到经典的K-Means聚类算法中，对质心更新的过程进行了优化，提高了算法的整体性能。随后，我们成功地将这种新的聚类算法应用于解决实际的问题。

我们的下一个研究目标是检验种群大小对算法性能的影响，并探索该改进算法在其他工程问题中的应用。

NOTES

^*通讯作者。