遗传算法

序言

进化算法(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)。三种进化算法都是受相同的自然进化原则的启发下创立的，[Fdb94] 以及国内的诸多资料也有详细的介绍。本文档我们只介绍经典的遗传算法，不对改进的遗传算法以及用途更广的多目标优化遗传算法作详细介绍，需要进行相关研究的可以参考相关的专业性书籍。文档第一章是有关遗传算法的概述和基本框架。第二章介绍了编码。第三章是关于适应度的计算。第四章讲述了选择算法。在第五章中，介绍了不同的重组算法。第六章解释了如何变异。第七章讲解了什么是重新插入和生成后代。第八章详细讲解了与多目标优化有关的入门知识。最后值得一提的是，虽然进化算法已经比较成熟，在近20 年来已经得到了快速的发展，在金融、工程、信息学、数学等领域已经有广泛的应用，但是，众多新兴的进化算法(如差分进化算法等) 以及不断改进和完善的拥有高维、多目标问题求解能力的进化算法等等，正给进化算法注入源源不断的新活力。与此同时，深度神经网络的蓬勃发展让进化算法有了一个更加前沿和广阔的前景——神经进化。量子计算机的出现，也使得拥有高度并行能力的进化算法有着更大的潜能。