演化算法：乌鸦搜索算法 (Crow Search Algorithm)

前言

如果你对这篇文章感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

在机器学习中，我们所要优化的问题很多时候难以求导，因此通常会采用一些演化算法（又称零阶优化 / 黑盒优化）来近似求解。

这些演化算法通常是根据一些生物的行为置顶，有如下分类：

本文所要介绍的乌鸦搜索算法 (CSA) 就是其中的一种，属于演化算法。

---

乌鸦搜索算法

乌鸦搜索算法受乌鸦的行为所启发，即在乌鸦种群中，每只乌鸦都在干三件事：

• 寻找藏食物的地点；
• 想要发现其它乌鸦藏食物的地点；
• 不想被其它乌鸦发现自己藏食物的地点。

每只乌鸦 $i$ 在每一轮会选择一只乌鸦 $j$ 进行跟踪，此时有两种情况：

• 乌鸦 $j$ 未发现乌鸦 $i$，则乌鸦 $i$ 向乌鸦 $j$ 藏食物的地点前进；
• 乌鸦 $j$ 发现了乌鸦 $i$，决定进行误导，即乌鸦 $i$ 的位置变成随机位置。

为进一步说明上述过程，定义如下符号：

• 向量 $x_i^t$ 表示第 $i$ 只乌鸦第 $t$ 轮的位置；
• $me{m}_i^t$ 表示第 $i$ 只乌鸦第 $t$ 轮的历史最优解；
• $A{P}_i^t$ 表示第 $i$ 只乌鸦第 $t$ 轮的警觉概率；
• $f{l}_i^t$ 表示第 $i$ 只乌鸦第 $t$ 轮的跟随步长；
• $r_i$ 表示第 $i$ 只乌鸦的随机概率，范围在 $(0,1)$ 之间。

将 $x_i^t$ 理解为第 $t$ 轮搜索到的位置，$me{m}_i^t$ 即为到第 $t$ 轮时的历史最优解。具体迭代过程如下：

• 一共有 $t_{MAX}$ 轮迭代，$N$ 只乌鸦；
• 每一轮迭代，遍历每一只乌鸦；
• 当遍历到第 $i$ 只乌鸦时，随机选择第 $j$ 只乌鸦进行跟踪；
  • 如果 $r_j\ge A{P}_j^t$，即乌鸦 $j$ 未发现，则乌鸦 $i$ 进行如下更新：
    $$x_i^{t+1}=x_i^t+r_i\cdot f{l}_i^t\cdot (me{m}_j^t-x_i^t),$$
  • 如果 $r_j<A{P}_j^t$，则 $x_i^{t+1}$ 变为随机值；
• 每一轮迭代结束后，遍历每一只乌鸦，若 $f(x_i^{t+1})>f(me{m}_i^t)$，则更新 $me{m}_i^{t+1}=x_i^{t+1}$，否则不更新，即 $me{m}_i^{t+1}=me{m}_i^t$。

完整算法如下：

---

参考资料

• Learn Crow Search Algorithm Step-by-Step with Example
• [ESWA22 - Behrouz Samieiyan] Novel optimized crow search algorithm for feature selection