第七章进化计算.pdf

《人工智能：算法之美》草稿 第七章 进化计算 第第7 章章 进化进化计算计算 第第 章章 进化进化计算计算 [1] [2] 以生物遗传学说 和达尔文生物进化论 为核心的进化（evolution ）理论是目前为人们 所广泛接受的生物优化学说。生物在群体繁殖和自然选择的作用下不断进化的过程正是生 物系统动态的自组织和自适应过程。在这一过程中，生物组织对环境的适应能力逐渐增强， 生物群体不断得以发展和完善。生物智能不仅体现在其个体解决问题的能力上，而且体现 在其群体的进化过程中。而人工智能中核心的搜索问题本质上亦是寻找问题最优解答的优 化问题。因此，生物进化理论对于解决人工智能中的搜索问题具有借鉴意义，基于该理论 的优化计算问题被统称为进化计算（evolutionary computation ）或模拟进化（simulated evolution ）。 目前，进化计算方法主要包括遗传算法（genetic algorithms ）、遗传规划（genetic programming ）、进化策略（evolutionary strategy ）和进化规划（evolutionary programming ） 四种。这四种方法在利用进化理论求解问题最优解的基本思路上是一致的，但在对于进化 对象的理解上存在差异，从而在进化过程的模拟实现上具有不同的侧重点和实现方式。其 中，遗传算法和遗传规划相似之处更多，本书统称其为基因型进化算法；进化策略和进化 规划的相似之处更多，本书统称其为表现型进化算法。这两类算法的区别在于：1）基因型 算法注重遗传物质的作用，认为进化发生在基因上，生物的进化是基因适应的过程，因此 主要通过模拟基因上的遗传操作完成解的进化。2 ）表现型算法强调进化的外在表现，认为 不存在进化发生的单一地点，进化是通过生物在环境中的表现反映出来的，是外在表现适 应环境的过程，因此主要通过直接对系统性能进行改进来发现最优解。 本章阐述进化计算的基本思想和一般框架。基因型算法与表现型算法的具体细节将分 别在第8-9 章介绍。 7.1 生物进化对搜索的启示生物进化对搜索的启示 生物进化对搜索生物进化对搜索的启示的启示 按照达尔文的生物进化论，地球上的每一物种都经历了漫长的进化历程。生物在繁衍 生息的过程中，使自身品质不断得到改良以逐渐适应生存环境，显示了优异的自组织能力 和对自然环境的自适应能力。这种生命现象被称为进化。 生物进化是以物种群体的形式进行的，组成种群（population ）的单个生物被称为个体 （individual ）。每个个体对其生存环境有不同的适应能力，这种适应能力被称为个体对环境 的适应度（fitness ）。 遗传是生物繁殖和进化的基础。生物的所有遗传信息都包含在生物细胞中的染色体上。 染色体主要由蛋白质和脱氧核糖核酸构成。具有遗传效应的DNA 片段就是生物遗传的物质 单位，被称为基因。生物的各种性状受相应基因的控制。基因组合的特异性决定了生物的 多样性，基因结构的稳定性则保证了生物物种的稳定性，而繁殖过程中基因的重组和突变 造成同种生物世代之间或同代不同个体之间的差异，使物种进化成为可能。 在一定生存环境的影响下，大多数高等生物物种通过自然选择和有性繁殖这两个基本