第1章
绪论

1.1 进化计算简介

生命自从在地球上诞生以来，就开始了漫长的演化历程，逐步从低级、简单的生物发展为高级、复杂的生物。生物进化的原因有着各种不同的解释，其中，达尔文（C. R. Darwin）的自然选择学说被广泛认同。依据达尔文的进化论，各种生物要生存下来，都要经历“自然选择，适者生存”的过程；每个物种在不断的发展过程中都越来越适应环境；物种的每个个体的基本特征被后代所继承，但后代又不完全与自己的父代相同；在个体的生存与发展中，那些更能适应环境的个体特征能被保留下来，体现了适者生存的原理。根据孟德尔（G. J. Mendel）和摩根（T. H. Morgan）的遗传学，遗传物质作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中；每个基因有特殊的位置并控制生物某个特殊的性质；不同的基因组合产生的个体对环境的适应性不同，通过基因杂交和基因突变可能产生对环境适应性强的后代；经过优胜劣汰的自然选择，适应值高的基因结构得以保存下来。在一定的环境影响下，生物物种通过自然选择、基因交换和变异等过程进行繁殖生长，形成了生物的整个进化过程。

生物进化需要4个基本条件：

（1）存在由多个生物个体组成的种群。

（2）群体具有多样性，即生物个体之间存在差异。

（3）种群能够繁衍。

（4）不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。

生物群体的进化机制有以下3种基本形式。

1. 自然选择

控制生物个体群体行为的发展方向，能够适应环境变化的生物个体具有更高的生存能力，使得它们在种群中的数量不断增加，同时该生物个体所具有的染色体性状特征在自然选择过程中得以保留。

2. 杂交

通过杂交随机组合来自父代染色体上的遗传物质，产生不同于它们父代的染色体。生物进化过程不需要记忆，能很好地适应自然环境的信息都包含在当前生物体所携带的染色体的基因库中，并由子代个体继承下来。

3. 突变

随机改变父代个体的染色体上的基因结构，产生具有新染色体的子代个体。变异是一种不可逆过程，具有突发性、间断性和不可预测性，对于保证群体的多样性具有不可替代的作用。

此外，生物进化是一个开放的过程，自然界对进化中的生物群体提供及时的反馈信息，或称外界对生物的评价。评价反映了生物的生存价值和机会。在基于相同环境的生存竞争中，生存价值低的个体被淘汰，具有较高生存价值的个体则能生存下来，这反映了生物进化的外部动力机制。

进化计算（Evolutionary Computation，EC）的基本思想来源于达尔文的进化论，以及孟德尔和摩根的遗传学说。进化算法通过程序迭代模拟这一过程，即把要解决的问题看作环境，一些随机生成的解当作初始种群，效仿生物的遗传方式，主要采用复制、交换和突变这三种遗传操作，衍生出下一代的个体；再根据适应度的大小进行个体的优胜劣汰，提高新一代群体的质量，经过多次迭代，逐步寻求最优解。与传统的基于微积分的方法和穷举法等优化算法相比，进化计算是一种成熟的具有高稳健性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性，能够不受问题性质的限制，有效地处理传统优化算法难以解决的复杂问题。

进化算法是一种全局性随机搜索算法，不是盲目搜索，也不是穷举搜索，而是以目标函数为指导（既不需要计算目标函数的导数和梯度，也不要求目标函数具有连续性）进行搜索。进化算法具有内在的隐含并行性和全局寻优能力，不断借助交叉和变异产生新个体，扩大搜索范围，因此它不容易陷入局部最优解，并能以较大的概率找到全局最优解。

进化计算包括遗传算法（Genetic Algorithm，GA），进化策略（Evolutionary Strategies，ES），进化规划（Evolutionary Programming，EP），遗传编程（Genetic Programming，GP），差分进化算法（Differential Evolution Algorithm，DEA）等[1-25]。