AI界的集邮学？回眸ES，粒子群PSO，遗传(进化)算法，GA等无梯度优化方法

实验物理学家卢瑟福说过：“ 所有科学要么是物理，要么是集邮” 。相较其他学科，物理学也许对宇宙大一统的解释有一定的优越性。如在研究半衰期过程中就会被一种大自然的神奇所折服（ 弱核力 ）。

然而 “集邮” 并不是没有意义。苏格拉底说过， “盾从防御看是美的，矛则从射击的敏捷和力量看是美的” 。不能因为深度学习理论薄弱，就去否认深度网络的实际效用。收集大自然的“邮票”加以利用也许成就感不那么高，但它可能非常有效 ，甚至在某些角度不乏美感。

比如在我们AI机器学习领域就有这样一种“集邮”学：其囊括 遗传算法 ， 进化策略算法（ES） ， 粒子群算法（PSO） ，多数都是以模仿自然为依据，还有一个流行好听的称呼： 无梯度优化算法（gradient-free，derivative-free） （ facebook开源的Nevergrad库 也是来自这种优化方法）

这些“离经叛道”的优化算法，不像SVM极具数学根基，但在某些场合非常适用：

拿粒子群算法（PSO）来讲，如上图，是粒子群在平面上找到极小值的过程，其本质是模拟了群鸟飞行或群鱼相互协作的搜索过程：

其核心公式也是贯彻了 相互协作 的原则：

其中 vi(t+1) 是下一个时刻的粒子速度，它由三个因素决定：

1. vi(t) 即当前速度，

2. 该粒子历史最佳位置 \({pi}^{best}\) 与该粒子当前位置 pi(t) 的差,

3. 群体历史最佳位置 \(p_{gbest}\) 与该粒子当前位置 pi(t) 的差 。值得注意的是， 这里说的速度和差都是矢量 。

用人话来说就是每个粒子的方向是由群体最佳方向和自己搜索的最佳方向共同决定的。

是的，也许这种算法看不出坚实的理论基础，但是在所有的搜索算法中，David 9认为这何尝不是一类最有美感的算法？ 加之如果融合之前提到的量子计算优势 ，不排除 无梯度优化算法 今后还会有长足的进步。

回望无梯度优化， 进化策略（ES） 是不可忽视的一大类。

而ES算法框架大体都是一样的：

如上图，圆圈是 群体集合 ，矩形框是操作， 实线 是所有ES算法都有的过程， 虚线 是一些特别ES算法需要的过程。即，一般算法流程为：

1. 从 Xbase 基础群体集合 中选择出 Xparent 父代群体集合
2. 从 Xparent 父代群体集合 估算出目前的整体概率分布
3. 从2中的分布抽样出 Xoffspring 子代群体集合
4. 用 Xoffspring 子代群体 集合替代 Xbase 基础群体集合

之所以有虚线，是因为替代 基础集合 的过程也可以由父代群体参与（(1+1)-ES算法和IDEA算法），因父代也有较好的个体不需要淘汰。

论文[8] 很好地比较了5个ES算法（ (1+1)-ES，CSA-ES，CMA-ES，IDEA，MBOA ）之间的微妙区别:

1.对于 概率分布 和 分布参数 ：

所有ES算法都是借助 高斯模型 N(m, C) 做底层搜索的。不一样的是 (1+1)-ES和CSA-ES算法用的是 各方向等距的高斯 （ C= \(σ^2I\) ），而CMA-ES和IDEA算法用的是更 随意方向的高斯 （如CMA-ES用协方差矩阵来控制步长）

另外IDEA算法和MBOA算法的 分布参数 在每次迭代时都会改变， 如IDEA在每次迭代时都构造新的 条件分解图 。 MBOA算法也会不断更新自己的高斯核。

2. 在训练过程中使用的 统计度量 ：

ES算法的分布都是被群体 个体的位置 和每个 个体各自的表现（适应度） 左右的。不同的是 (1+1)-ES只关注了父代到子代的 遗传率 ；而 CSA-ES 和CMA-ES都维护了 整个种群的进化路线 ，从而引导下一次子代父代更替；IDEA在构图时还考虑了父代的度量。

3. 学习策略 和 历史信息 的使用：

更新有两种完全不同的策略：一种是 完全根据进化来出的子代群体 的分布更新概率分布；另一种是每次都根据群体的情况重新构造全新的概率分布（ 就好像每次都是诺亚方舟创世 ）。

对于 历史信息 的保留方式也有两种：

一种是每一代都保留优秀的子代，用于后续的迭代，

另一种是一直维护自身的内部参数来更新每一次的代际更替。

参考文献：

1. https://github.com/facebookresearch/nevergrad
2. https://github.com/DEAP/deap
3. http://www.jmlr.org/papers/volume13/fortin12a/fortin12a.pdf
4. http://vision.gel.ulaval.ca/~cgagne/pubs/sigevolution2014.pdf
5. https://cloud.tencent.com/developer/article/1379395
6. https://zh.wikipedia.org/wiki/欧内斯特·卢瑟福
7. https://en.wikipedia.org/wiki/Particle_swarm_optimization
8. Learning Probability Distributions in ContinuousEvolutionary Algorithms – A Comparative Review
9. http://www.cleveralgorithms.com/nature-inspired/swarm/pso.html

本文采用 署名 – 非商业性使用 – 禁止演绎 3.0 中国大陆许可协议 进行许可。著作权属于“David 9的博客”原创，如需转载，请联系微信: david9ml，或邮箱：yanchao727@gmail.com

或直接扫二维码: