第二篇　进化算法

自然界的生物处在不断生殖繁衍过程中，通过遗传和变异，“优胜劣汰”的自然选择法则，使优良品种得以保存，并且比上一代的性状有所进化。生物在不断进化中，体现了一种优化的思想。本书的进化算法是模拟生物进化过程与机制求解优化问题的一类优化算法的总称，而遗传算法则是进化计算的基础。本书的进化算法共包括以下10种。

1. 遗传算法

模拟生物进化与遗传机理并用字符串作为染色体表达问题，通过选择、交叉和变异对字符串进行操作，逐步实现遗传进化对复杂问题的优化求解。

2. 遗传编程

遗传算法用定长的字符串表示问题，限制对问题的结构和大小的处理，遗传编程采用层次化结构，类似于计算机程序分行或分段描述问题。在遗传进化过程中个体不断动态变更结构及大小，自适应搜索寻找合适的广义计算机程序形式表达复杂问题。

3. 进化规划

进化规划采用传统的十进制实数表达问题，个体进化主要依靠突变，没有重组或交换操作。这种突变方式是指在旧个体的基础上添加一个与适应度有关的随机数而产生新个体。经过反复迭代，直至得到满意的结果。

4. 进化策略

与进化规划类似，个体也采用传统的十进制实数表达问题，而个体进化依靠突变、重组（交换）、选择等进化操作。进化策略经过反复迭代过程，改进群体质量，逐渐得出最优解。

5. 分布估计算法

分布估计算法是一种基于概率模型的遗传算法，通过对当前优秀个体集合建立概率分布函数产生新的个体并用来指导算法下一步的搜索。它没有交叉和变异操作，改变了遗传算法通过重组操作产生群体的途径，改善了基本遗传算法中存在的欺骗问题和连锁问题。

6. 差分进化算法

差分进化算法是具有特殊“变异”“交叉”和“选择”方式且采用实编码的遗传算法。“变异”是把种群中两个个体之间的加权差向量加到第三个个体上产生新参数向量；“交叉”是将变异向量的参数与另外预先决定的目标向量的参数按一定规则混合产生子个体；“选择”是指新的子个体只有当它比种群中的目标个体优良时才对其进行替换。

7. DNA计算

利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶作用下生成各种数据池。按一定规则将原始问题的数据运算高度并行地映射成DNA分子链的可控生化过程，再用分子生物技术检测出求解的结果。

8. 基因表达式编程算法

基因表达式编程算法继承了遗传算法的刚性，使用定长线性串简单编码解决简单问题；又继承了遗传编程的柔性，采用非线性树结构的复杂编码解决复杂问题。因此，它是刚柔相济，利用简单编码形式来解决复杂问题的进化算法。

9. Memetic算法

Memetic算法是将生物层次进化与社会层次进化相结合，应用基因与模因分别作为这两种进化信息编码的单元，可将它视为具有全局搜索的遗传算法和局部搜索相结合的进化算法。基于模因理论的局部搜索有利于改善群体结构，及早剔除不良种群，进而减少迭代次数，增强局部搜索能力，提高求解速度及求解精度。

10. 文化算法

文化算法是一种基于知识的双层进化系统，包含两个进化空间：一是进化过程中获取的经验和知识组成的信念空间；二是由个体组成的种群空间，通过进化操作和性能评价进行自身的迭代实现对问题求解。