一个具有智能的系统是可以将自己的行为与总是改变的环境相适应。人类的智能是进化的结果。通过对进化建模，我们可能可以创建出智能的行为。进化计算在计算机里模拟了进化，它包括遗传算法、进化策略和遗传编程。1858年7月1号，Charles Darwin提出经典进化理论。它与Weismann的自然选择理论以及Mendel的遗传概念，共同构成了新达尔文主义理论框架。新达尔文主义基于复制、变异、竞争和选择的过程。
遗传算法（Genetic Algorithm, GA）是一类基于生物进化的随机搜索算法。GA有以下几个主要步骤：
1、用固定长度的染色体来表示问题变量域，选择种群染色体长度N，基因交换概率p_c和变异概率p_m；
2、定义适应性（fitness）函数来衡量问题域的个体染色体的性能。适应性函数是复制过程中选择染色体的标准；
3、随机产生一群长度为N的染色体；
4、计算每个个体染色体的适应性；
5、从当前种群选择一对染色体，适应性更高的染色体被选取到的概率更高；
6、根据交换和突变来得到一对后代染色体；
7、将得到的后代染色体放入新的种群；
8、重复第5步，直到新种群的个体数和初始数量N相同；
9、用新的种群代替老的种群；
10、回到第4步，重复，直到满足终止标准。
在选取下一代的染色体时，先算出每个染色体的适应度，再除以所有个体的适应度的和，得到每个染色体被选取的概率（适应度率）。根据这个概率分布，可以构成一个圆盘，比如适应度率为25%的染色体占据圆盘1/4的位置，12.5%的适应度的染色体占据圆盘1/8的位置。这时每次选取都类似于转盘抽奖，当圆盘上的指针落在某染色体所占据的位置时，就选取该染色体。在转转盘与种群个体数相同的次数之后，便可以得到新的种群。
在生成新种群时，还会有一定机率进行基因交换和变异。典型的交换机率为0.7，变异率0.001。交换时，在一对染色体里，随机选取一个基因片段（0、1序列），互相交换。而变异则在交换后，把某一个基因从0变为1或由1变为0。变异通常会造成坏的影响，但有时能够把整个种群从局部最优带出到全局最优。
一般会事先定好种群的繁殖的代数以便终止算法，比如100代。如果结果不满足需要，则重新开始GA。整个种群的平均适应度会在刚开始时快速增长，之后增速逐渐变慢，最后变得平缓。
遗传算法的理论基础是模式定理（schema theorem）。它适合解决一些NPC问题，如调度问题。
进化策略（Evolution strategies）在60年代被提出，适用于技术最优化问题。它只用到了变异操作。
最简单的形式是(1+1)-进化策略，具体步骤如下：
1、确定表达问题的参数的个数N，然后为每个参数确定一个可行范围：{x1_min, x1_max}, {x2_min, x2_max}, ..., {xN_min, xN_max}。为每个参数定义一个标准差d，以及用于最优化的函数。
2、为每个参数在其可行范围内随机选择一个初始值，这个参数的集合成为父参数的初始种群。
3、通过父参数计算出解决方案X = f(x1, x2, ..., xN)。
4、通过加上一个均值为0、标准差为d的正态分布的随机变量a，来为每个一个父参数创建后代参数。xi' = xi + a(0,d), i = 1,2,...,N。
5、计算后代参数的解决方案X' = f(x1', x2', ..., xN')。
6、比较X'与X。如果后代的解决方案更好，则用其代替父参数；否则保留父参数。
7、回到第4步，重复，直到找到满足需求的解决方案或者繁衍了足够多的代。
进化策略反映了染色体的本质，可以解决大范围的非线性问题且结果要比传统非线性的复杂最做优化方法好很多。实验表明单个父亲、单个后代的最简单的版本工作地最好。
遗传编程（Genetic programming）是传统GA的扩展。它创造计算机程序作为解决方案，而不是表示解决方案的二进制串。
在应用遗传编程解决问题之前，需要5个预备步骤：
1、确定终端集，对应于计算机程序的输入。
2、选择原始函数集，可以用标准算术操作符、标准程序操作符、标准数学函数、逻辑函数或特定领域的函数。终端和原始函数共同组成了遗传编程用于构建计算机程序所需的基础结构。
3、确定适应度函数，判定一个计算机程序解决问题的优秀程度。
4、确定控制运行的参数，包括种群个体数和运行的最大代数。
5、确定如何选择方案的方法，指定到目前为止，运行得到的最好的解决方案。
下面的遗传算法执行的具体步骤：
1、指定运行的最大代数，复制、交换和变异的概率。这三个概率的和必须为1。
2、随机产生大小为N的计算机程序种群。
3、在种群中执行每个计算机程序并计算它们的适应度。选取目前为止最优的个体。
4、根据设定好的概率，执行复制、交换、或变异操作。
5、复制时，把当前种群的程序复制到新种群；当交换时，从当前种群选取一对计算机程序，创建后代程序并放入新种群；当变异时，选取单个程序执行变异并放入新种群。所有操作都是根据适应度率来选取个体。
6、重复第4步，直到新种群的个体数和当前种群相同。
7、用新种群代替当前种群。
8、重复第3步，直到满足终止条件。
计算机程序可以一棵语法树，在交换时，两棵语法树的某个子树互相交换，在变异时，某个操作符变为另一个操作符。
