进化计算

进化计算是遗传算法、进化策略、进化规划的统称。进化计算起源于20世纪50年代末,成熟于20世纪80年代,目前主要被应用于工程控制、机器学习、函数优化等领域。

来源:维基百科
简介

在计算机科学中,进化计算是一系列受生物进化启发的全局优化算法,以及研究这些算法的人工智能和软计算的子领域。在技术方面,这是一系列基于群体演变的算法,具有元启发式或随机优化特征。

在进化计算中,程序生成并迭代更新初始候选解决方案集。通过随机删除不太理想的解决方案并引入小的随机变化来生成每个新一代。这种演化一般体现为适应度的增加,即解决方案越来越理想。

进化计算技术可以在广泛的问题设置中生成高度优化的解决方案,使其在计算机科学中广受欢迎。它存在许多变体和扩展,包含遗传算法(GA,  Genetic Algorithm )、进化策略 (ES, Evolutionary Strategy)、遗传编程 (GP,Genetic Programming) 等等。这里简单地进行介绍。

  1. 遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题,一定数量的候选解(称为个体)可抽象表示为染色体,使种群向更好的解进化。传统上,解用二进制表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个体的种群开始,之后一代一代发生。在每一代中评价整个种群的适应度,从当前种群中随机地选择多个个体(基于它们的适应度),通过自然选择和突变产生新的生命种群,该种群在算法的下一次迭代中成为当前种群。遗传算法通过与不同种类的竞争方案保持联系的方法生成下一代,从而保证了多样性。然而,在实际过程中,大部分留存下来的精英方案倾向于逐渐收敛到局部最优。遗传算法有许多复杂的变形,比如 CoSyNe、ESP 和 NEAT,它们的想法主要是将类似的解决方案集聚到不同的种类中,从而更好地在过程中更好地保持多样性。
  2. 在我们探讨进化策略(ES)之前,有必要强调一下尽管这种方法名字中有「进化」这个词,但进化策略和生物进化关系不大。也许这项技术的早期版本从生物进化上获得了一些启发——在一定的抽象程度上,这种方法可被视为这样一个过程:从个体构成的群体中采样并让其中成功的个体引导未来后代的分布。但是,其数学细节在生物进化方法的基础上实现了很大的抽象,我们最好将进化策略看作是一类黑箱的随机优化技术。直观上来讲,这种优化就是一种「猜测然后检测」的过程,即我们从一些随机参数开始,然后重复执行以下过程:1)随机对该猜测进行一点调整,2)让我们的猜测向效果更好的方向移动一点。具体而言,就是在每个步骤输入一个参数向量 w,然后通过高斯噪声对 w 进行抖动来生成一群(比如 100 个)有稍微改变的参数向量 w1, w2……w100。然后我们在环境中分别运行这 100 个候选项所对应的策略网络,从而独立地对这 100 候选项分别进行评估,然后将每个案例中的奖励加起来。然后其更新后的参数就变成了这 100 个向量的加权和,其中每个权重都正比于其总奖励。(即,我们想让更成功的候选项有更高的权重。)在数学上,你也会注意到这就相当于使用有限差分法(finite difference)来估计参数空间中预期奖励的梯度,只是我们是沿着 100 个随机方向来做的。
  3. 遗传编程是一种特殊的利用进化算法的机器学习技术,它开始于一群由随机生成的千百万个计算机程序组成的“人群”,然后根据一个程序完成给定的任务的能力来确定某个程序的适合度,应用达尔文的自然选择(适者生存)确定胜出的程序,计算机程序间也模拟两性组合,变异,基因复制,基因删除等代代进化,直到达到预先确定的某个中止条件为止。

[描述来源:OpenAI详解进化策略方法:可替代强化学习|机器之心]

[描述来源:维基百科 URL:https://en.wikipedia.org/wiki/Evolutionary_computation]

发展历史

进化算法下的几个算法起初是各自独立的发展的。1965年,Larry Fogel 离开通用动力公司,在圣地亚哥组建了一家名为Decision Science的新公司,专门用于进化编程(Evolutionary programming)的应用。他曾担任信息科学,计算机模拟,预测和系统控制领域的总裁并负责研究和实际应用。 Decision Science也是第一家专门应用进化计算来解决实际问题的公司。这些方法通过Alvin Owens和George Burgin的努力得到进一步发展,并形成了新一代飞行模拟器的基础,该模拟器首先部署在兰利研究中心,用于空对空作战训练。

1971年, Ingo Rechenberg在他的PhD论文中介绍了ES。John Holland 阅读了 Ronald Fisher 的经典论文「自然选择的遗传理论」,然后他阐述了其核心思想并设计了遗传算法。1975年,John Holland的著作《自然系统和人工系统中的自适应(Adaptation  in Natural and Artificial Systems)》普及了他所提出的遗传算法 ——这一算法用于是解决最优化问题的搜索算法,是进化算法的一种——其在随后几十年变得越来越流行。由于理论上讲遗传算法能够跳出局部最优而找到全局最优点,而且遗传算法允许使用非常复杂的适应度函数,并对变量的变化范围可以加以限制。

1994年,John R. Koza出版了《Genetic programming as a means for programming computers by natural selection》对遗传编程进行了介绍。尽管他不是GP的发明者,但通过他的研究GP才真正开始受到了大量的关注,并成为了一个独立的研究领域。

从九十年代初开始,这一系列算法被统一为一种技术的不同代表(“方言”),称为进化算法。

进化算法的应用范围很广。2002年,Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T应用遗传算法来解决多目标优化问题。优化问题也是进化算法最擅长解的问题之一。2009年,Liang等学者针对PSO算法应用在多模态问题(multimodal problem)时容易陷入局部最优解的问题,提出了CLPSO(comprehensive learning particle swarm optimizer)算法来防止算法过早收敛(pre-convergence)。

具体到目前人们关心的深度学习领域,2017年有许多将深度学习与进化算法结合的研究涌现。对于具有上百万个连接的多层深度神经网络(DNN),现在往往通过随机梯度下降(SGD)算法进行常规训练。许多人认为,SGD 算法有效计算梯度的能力对于这种训练能力而言至关重要。但是,来自Uber的Joel Lehman和Kenneth O. Stanley发表的论文展示了如何将神经进化和梯度相结合,以提高循环神经网络和深度神经网络的进化能力。这种方法可以使上百层的深度神经网络成功进化,远远超过了以前的神经进化方法所展示的可能性。他们通过计算网络输出关于权重的梯度(即,和在传统深度学习中使用误差梯度不同)来实现这一点,使得在随机突变的校准过程中,对最敏感的变量(相比其他变量而言)进行更加精细的处理,从而解决大型网络中随机变量的一个主要问题。

Edoardo Conti和Jeff Clune等人则通过引入新的算法将 ES 的优化能力和可扩展性与神经进化所独有的、通过群体激励将不同智能体区别开的促进强化学习领域的探索结合起来。这种基于群体的探索有别于强化学习中单一智能体传统,包括最近在深度强化学习领域的探究工作。该实验表明,通过增加这种新的探索方式,能够提高 ES 在许多需要探索的领域(包括一些 Atari 游戏和 Mujoco 模拟器中的类人动作任务)的性能,从而避免欺骗性的局部最优。

OpenAI 发表了论文《用作强化学习的可扩展替代的进化策略(Evolution Strategies as a Scalable Alternative to Reinforcement Learning)》研究表明神经进化方法在现在的代理-环境基准上,可与强化学习的方法相媲美,同时在代码复杂性上也有重大收益、易于延展到大规模分布式环境。同年,Google发布了研究利用进化算法设计神经网络的架构。他们以空前的规模采用了简单的进化技术,并从平凡的初始条件出发,来发现可用于 CIFAR-10 和 CIFAR-100 数据集的模型。为此,他们使用了直观的新型变异算子(mutation operators)来导航大型搜索空间。演化一旦开始,其输出就应当是一个经过完整训练的模型,不需任何人进行参与。这项研究尤其重要的是结果的可重复性、可变性以及计算要求。

主要事件

年份事件相关论文/Reference
1966Larry Fogel介绍了Evolutionary programmingFogel, L.J., Owens, A.J., Walsh, M.J. (1966), Artificial Intelligence through Simulated Evolution, John Wiley.
1971Ingo Rechenberg在他的PhD论文中介绍了ESRechenberg, I. (1971). Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
1975John Holland的著作《自然系统和人工系统中的自适应(Adaptation  in Natural and Artificial Systems)》普及了遗传算法 Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press.
1994John R. Koza出版了《Genetic programming as a means for programming computers by natural selection》对遗传编程进行了介绍,通过他的研究GP才真正开始受到大量的关注,并成为了一个独立的研究领域Koza, J. R. (1994). Genetic programming as a means for programming computers by natural selection. Statistics and Computing. 4(2): 87–112.
2002Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T应用遗传算法来解决多目标优化问题Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
2009Liang等学者提出了CLPSO(comprehensive learning particle swarm optimizer)算法Liang J.J.; Qin A.K.; Suganthan P.N.; Baskar S. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation. 10(3): 281 - 295.
2017OpenAI 发表了论文《用作强化学习的可扩展替代的进化策略(Evolution Strategies as a Scalable Alternative to Reinforcement Learning)》Salimans, T. et al. (2017). Evolution Strategies as a Scalable Alternative to Reinforcement Learning. arXiv:1703.03864.
2017Google发布了研究利用进化算法设计神经网络的架构Real, E. (2017). Large-Scale Evolution of Image Classifiers. arXiv:1703.01041v2.
2017Joel Lehman和Kenneth O. Stanley发表的论文展示了如何将神经进化和梯度相结合,以提高循环神经网络和深度神经网络的进化能力Lehman, J. et al. (2017). Safe Mutations for Deep and Recurrent Neural Networks through Output Gradients. arXiv:1712.06563.
2017Edoardo Conti和Jeff Clune等人通过引入新的算法将 ES 的优化能力和可扩展性与神经进化所独有的、通过群体激励将不同智能体区别开的促进强化学习领域的探索结合起来Conti, E. et al. (2017). Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents. arXiv:1712.06560.

发展分析

瓶颈

这类算法大部分的收敛性很难从数学上证明,算法有可能陷入局部最优。而数学基础比较好的算法(如协方差矩阵自适应进化策略,CMA-ES),计算速度较慢。此外,进化算法尽管在单一问题上表现很优秀,但它的泛化能力还没有被系统性的验证过。

未来发展方向

如上文已经提到的,利用进化计算取代传统的SGD过程来训练神经网络,或将其与强化学习结合等进化算法+深度学习的研究正在逐渐受到关注。

Contributor: Yuanyuan Li

相关人物
Ingo Rechenberg
Ingo Rechenberg
约翰·科萨
约翰·科萨
斯坦福大学计算机科学家,最著名的是他在开拓遗传编程以优化复杂问题方面所做的工作。
约翰·霍兰德
约翰·霍兰德
密歇根大学博士,美国科学家,复杂理论和非线性科学领域的开拓者,遗传算法之父。主要研究领域为复杂自适应系统、认知过程的计算机模型等。他是心理学、电气工程和计算机科学教授,致力于用数学模型和计算机模拟研究认知过程和复杂的适应性系统。
简介
相关人物