在机器学习中，我们所要优化的问题很多时候难以求导，因此通常会采用一些演化算法（又称零阶优化 / 黑盒优化）来近似求解。
这些演化算法通常是根据一些生物的行为置顶，有如下分类：
/d51ad9a8b3b8fbbea496d2d0756bae31.png)
本文所要介绍的乌鸦搜索算法 (CSA) 就是其中的一种，属于演化算法。
乌鸦搜索算法
乌鸦搜索算法受乌鸦的行为所启发，即在乌鸦种群中，每只乌鸦都在干三件事：
-
寻找藏食物的地点；
-
想要发现其它乌鸦藏食物的地点；
-
不想被其它乌鸦发现自己藏食物的地点。
每只乌鸦 $i$ 在每一轮会选择一只乌鸦 $j$ 进行跟踪，此时有两种情况：
-
乌鸦 $j$ 未发现乌鸦 $i$，则乌鸦 $i$ 向乌鸦 $j$ 藏食物的地点前进；
-
乌鸦 $j$ 发现了乌鸦 $i$，决定进行误导，即乌鸦 $i$ 的位置变成随机位置。
为进一步说明上述过程，定义如下符号：
-
向量 $x_i^{t}$ 表示第 $i$ 只乌鸦第 $t$ 轮的位置；
-
$mem_i^t$ 表示第 $i$ 只乌鸦第 $t$ 轮的历史最优解；
-
$AP_i^t$ 表示第 $i$ 只乌鸦第 $t$ 轮的警觉概率；
-
$fl_i^t$ 表示第 $i$ 只乌鸦第 $t$ 轮的跟随步长；
-
$r_i$ 表示第 $i$ 只乌鸦的随机概率，范围在 $(0,1)$ 之间。
将 $x_i^{t}$ 理解为第 $t$ 轮搜索到的位置，$mem_i^t$ 即为到第 $t$ 轮时的历史最优解。具体迭代过程如下：
-
一共有 $t_{MAX}$ 轮迭代，$N$ 只乌鸦；
-
每一轮迭代，遍历每一只乌鸦；
- 当遍历到第 $i$ 只乌鸦时，随机选择第 $j$ 只乌鸦进行跟踪；
- 如果 $r_j\geq AP_j^t$，即乌鸦 $j$ 未发现，则乌鸦 $i$ 进行如下更新：
$$ x_i^{t+1}=x_i^t+r_i\cdot fl_i^t \cdot (mem_j^t-x_i^t), $$- 如果 $r_j<AP_j^t$，则 $x_i^{t+1}$ 变为随机值；
- 每一轮迭代结束后，遍历每一只乌鸦，若 $f(x_i^{t+1})>f(mem_i^t)$，则更新 $mem_i^{t+1}=x_i^{t+1}$，否则不更新，即 $mem_i^{t+1}=mem_i^{t}$。
完整算法如下：
/b02b5cf532030bb94cc2afb60810a068.png)