进化算法
序言
进化算法 (Evolutionary Algorithm, EA) 是一类通过模拟自然界生物自然选择和自然
进化的随机搜索算法。与传统搜索算法如二分法、斐波那契法、牛顿法、抛物线法等相
比,进化算法有着高鲁棒性和求解高度复杂的非线性问题 (如 NP 完全问题) 的能力。
在过去的 40 年中,进化算法得到了不同的发展,现主要有三类:
1) 主要由美国 J. H. Holland 提出的的遗传算法 (Genetic Algorithm, GA);
2) 主要由德国 I. Rechenberg 提出的进化策略 (Evolution strategies, ES);
3) 主要由美国的 L. J. Fogel 提出的进化规划 (Evolutionary Programming, EP)。
三种进化算法都是受相同的自然进化原则的启发下创立的,文献 [1] 以及国内的诸
多资料也有详细的介绍。除此之外,进化算法还有差分进化 (Differential Evolution)、基
因表达式编程 (Gene Expression Programming) 等众多分支。本文档只介绍经典的遗传算
法、差分进化算法和多目标进化优化算法,不对众多改进的进化算法以及其他分支作详
细介绍,如有需要进行相关研究的可以参考相关的专业和权威的文献。
文档第一章是有关遗传算法的概述和基本框架;第二章介绍了编码;第三章是关于
适应度的计算;第四章讲述了选择算法;在第五章中,介绍了不同的重组算法;第六章
解释了如何变异;第七章详细讲解了与多目标优化有关的概念。
最后值得一提的是,虽然进化算法在近 20 年来已经得到了快速的发展,在当今已
经比较成熟,在金融、工程、信息学、数学等领域已经有广泛的应用,但是,众多新兴
的进化算法 (如差分进化算法等) 以及不断改进和完善的拥有高维、多目标问题求解能
力的进化优化算法等等,正给进化算法注入源源不断的新活力。与此同时,深度神经网
络的蓬勃发展让进化算法有了一个更加前沿和广阔的前景——神经进化。量子计算机的
出现,也使得拥有高度并行能力的进化算法有着更大的潜能。
参考文献
[1] Fogel, D. B . An introduction to simulated evolutionary optimization[J]. IEEE Trans-
actions on Neural Networks, 1994, 5(1):3-14.
评论0