启发式优化算法的一些调研

启发式优化算法的背景

1. 首先，我们需要有一个目标函数 其中的 ， 是一个正整数。然后，目标函数 不一定需要是显式的（所谓显式指的是能够精确写出 的表达式，例如逻辑回归的目标函数，神经网络的目标函数，XGBoost 的目标函数等），隐式的目标函数使用启发式优化算法也是可以研究的（即无法写出 表达式）。

2. 其次，需要计算目标函数 的最大值 或者最小值 。

3. 再次，如果存在多个函数 并且每一个 的值域都在 内。如果目标函数是

希望求该目标函数的最小值，那么意思就是使得每一个 在 的定义域内都相差得不多，也就是这 条曲线几乎重合。

4. 拥有目标函数的目的是寻找最优的 使得它满足 或者 。

5. 在这里的 一般都是连续的特征，而不是那种类别特征。如果是类别的特征，并不是所有的启发式优化算法都适用，但是遗传算法之类的算法在这种情况下有着一定的用武之地。

启发式优化算法的实验方法

1. 论文中的方法：找到一些形状怪异的函数作为目标函数，需要寻找这些函数的全局最大值或者全局最小值。除了全局的最大最小值点之外，这些函数也有很多局部极值点。例如 Rastrigin 函数（Chapter 6，Example 6.1，Search and Optimization by Metaheuristics）

其中， 或者 Easom 函数（Chapter 2，Example 2.1，Search and Optimization by Metaheuristics）

其中，

2. 最朴素的算法：随机搜索法（Random Search）。也就是把 的定义域切分成 份，其中 计算每一个交点的函数取值，然后统计出其最大值或者最小值就可以了。实际中不适用，因为当 的时候，这个是指数级别的计算复杂度。

3. 启发式优化算法：针对某一个目标函数，使用某种启发式优化算法，然后与随机搜索法做对比，或者与其余的启发式优化算法做对比。

4. 在线调优：启发式优化算法大部分都可以做成实时调优的算法，调优的速度除了算法本身的收敛速度之外，还有给定一个 之后，获取到 的时间。

注：可以尝试使用启发式优化算法在线调优推荐系统中的 AUC 或者 CTR。不过 CTR 一般具有波动性，需要几个小时甚至一天的数据才能够统计出一个相对靠谱的取值。同时，如果用户量不够多的话，如果切流量的话，可能会造成一些流量的 CTR 偏高，另外一些流量的 CTR 偏低。并且流量的条数会有上限，一般来说不会超过 100 左右，甚至只有 10 个不同的流量。因此，在其余场景下使用这类方法的时候，一定要注意获取目标函数 value 的时间长度。时间长度越短，能够进行的尝试（探索次数）就会越多，收敛的希望就会越大；反之，时间长度越长，能够进行的尝试（探索次数）就会受到限制，收敛的时间长度就会变长。

启发式优化算法的一些常见算法

以下的内容暂时只涉及最基本的算法，有很多算法的变种暂时不做过多的描述。

粒子群算法（Particle Swarm Optimization）

PSO 算法是有一个粒子群，根据群体粒子和单个粒子的最优效果，来调整每一个粒子的下一步行动方向。假设粒子的个数是 ，每一个粒子 都是 维欧几里德空间里面的点，同时需要假设粒子的速度 。在每一轮迭代中，需要更新两个最值，分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值，分别记为 （）和 。在第 次迭代的时候，

在这里，，并且 是 中间的随机数。

注：需要解决的问题是如何设置这 个粒子，也就是构造粒子群的问题。在每次只能够设置调整一次 的时候，可以把时间窗口按照连续的 段来进行切分，在一个时间段内的这 个时间点可以当成 个粒子，然后进行下一轮的迭代即可。

模拟退火（Simulated Annealing）

其核心思想是构造了温度 这个维度，当温度 高的时候，分子运动速度快，能够探索更多的区域；温度 低的时候，分子运动速度慢，能够探索的区域有限。随着时间的迁移，温度 会从一个较大的值逐渐降低到 0。

模拟退火的大体思路是这样的：先设置一个较大的温度值 ，随机初始化 。假设目标函数是 ，需要寻找 ，然后执行以下的程序：

Repeat：

a. Repeat:

i. 进行一个随机扰动 ；

ii. 计算 ，

如果 ，也就是 ，选择 ；

否则，按照 的概率来接受 。

b. 令 。

直到 足够小。

遗传算法的个人理解：

1. 如何选择合适的 ，可以选择 Gaussian 正态分布，并且可以同时修改 的 个维度，也可以每次只修改一个维度或者部分维度的值；
2. 一开始在温度 很大的时候，即使 的时候，都会以极大概率接受 ，因为此时 。然后一开始都在四处游荡；
3. 当温度 逐渐降低的时候，当时 不一定在一个合适的位置，因此，需要记录历史上探索过的满足 最小的值，从历史上的值中选择出一个合适的值继续迭代。因此，在温度下降的时候，如何选择一个合适的值继续迭代可能是一个关键问题。
4. 从遗传算法和 PSO 的对比效果来看，因为 PSO 算法会随时记录当前粒子和所有粒子的最优状态，然后在整个种群中，总会有少数粒子处于当前的最优状态，所以 PSO 的效果从实验效果上来看貌似比不记录状态的遗传算法会好一些。

进化策略（Evolutionary Strategies）

ES 和 GA 有一些方法论上面的不同，这个在书上有论述，等撰写了 GA 在一起看这一块的内容。

进化策略（Evolutionary Strategies）的大体流程与遗传算法（Genetic Algorithm） 相似，不同的是 ES 的步骤是交叉/变异（Crossover/Mutation）在前，选择（Selection）在后。

对于经典的进化策略而言，交叉算子（Crossover Operator）可以按照如下定义：两个父代（parents） 和 ，那么子代（children）的交叉可以定义为：

这里的相加就是向量之间的相加。

对于经典的进化策略而言，变异算子（Mutation Operator）可以按照如下定义：对于一个向量 ，使用 Gaussian 正态分布可以构造出一个后代如下：

这里的 是基于具体问题的，很难给出一个通用的值。

就经验而谈，ES 算法一般来说比 GA 更加 Robust。在交叉（Crossover）或者变异（Mutation）之后，ES 算法就需要进行选择，通常来说，ES 算法有两种方式，分别是 和 两种策略。这里的 表示人口数量（population size）， 表示从人口中产生的后代的数量。

（1）在 策略中，从 人口中通过变异或者交叉得到 个人，然后从这 个人中选择出 个最优的人。 是精英策略，每一次迭代都比上一次要好。

（2）在 策略中， 个最优的人是从 中选择出来的。

传统的梯度搜索法，例如 Newton-Raphson 方法，需要能够计算目标函数 的导数，也就是说目标函数必须可导。但是在 Evolutionary Gradient Search 中，不需要 是可导的，而是使用导数的近似值来计算。

如果是 的方案，它整体来说其实只有一个人口。从当前的点 开始，通过 Gaussian Mutation 的方法可以生成 个后代，记为 。计算它们的函数取值 。那么估算的梯度就可以计算出来：

归一化之后得到

Evolutionary gradient search 生成了两个点，分别是：

这里的 新的个体定义为: 如果 那么 如果 那么

进化策略（ES）包括 gradient search 和 gradient evolution，并且 covariance matrix adaptation（CMA）ES 在一定的限制条件下加速了搜索的效率。

参考资料：

1. Search and Optimization by Metaheuristics，Kelin DU, M.N.S. SWAMY，2016年