第七章进化计算

《第七章进化计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《人工智能：算法之美》草稿第七章进化计算第7章进化计算[1][2]以生物遗传学说和达尔文生物进化论为核心的进化（evolution）理论是目前为人们所广泛接受的生物优化学说。生物在群体繁殖和自然选择的作用下不断进化的过程正是生物系统动态的自组织和自适应过程。在这一过程中，生物组织对环境的适应能力逐渐增强，生物群体不断得以发展和完善。生物智能不仅体现在其个体解决问题的能力上，而且体现在其群体的进化过程中。而人工智能中核心的搜索问题本质上亦是寻找问题最优解答的优化问题。因此，生物进化理论对于解决人工智能中的搜索问题具有借鉴意义，基于该理论的优化计算问题被统称为进化计

2、算（evolutionarycomputation）或模拟进化（simulatedevolution）。目前，进化计算方法主要包括遗传算法（geneticalgorithms）、遗传规划（geneticprogramming）、进化策略（evolutionarystrategy）和进化规划（evolutionaryprogramming）四种。这四种方法在利用进化理论求解问题最优解的基本思路上是一致的，但在对于进化对象的理解上存在差异，从而在进化过程的模拟实现上具有不同的侧重点和实现方式。其中，遗传算法和遗传规划相似之处更多，本书统称其为基因型进化算法；进化策略

3、和进化规划的相似之处更多，本书统称其为表现型进化算法。这两类算法的区别在于：1）基因型算法注重遗传物质的作用，认为进化发生在基因上，生物的进化是基因适应的过程，因此主要通过模拟基因上的遗传操作完成解的进化。2）表现型算法强调进化的外在表现，认为不存在进化发生的单一地点，进化是通过生物在环境中的表现反映出来的，是外在表现适应环境的过程，因此主要通过直接对系统性能进行改进来发现最优解。本章阐述进化计算的基本思想和一般框架。基因型算法与表现型算法的具体细节将分别在第8-9章介绍。7.1生物进化对搜索生物进化对搜索的启示生物进化对搜索的启示按照达尔文的生物进化论，地球上

4、的每一物种都经历了漫长的进化历程。生物在繁衍生息的过程中，使自身品质不断得到改良以逐渐适应生存环境，显示了优异的自组织能力和对自然环境的自适应能力。这种生命现象被称为进化。生物进化是以物种群体的形式进行的，组成种群（population）的单个生物被称为个体（individual）。每个个体对其生存环境有不同的适应能力，这种适应能力被称为个体对环境的适应度（fitness）。遗传是生物繁殖和进化的基础。生物的所有遗传信息都包含在生物细胞中的染色体上。染色体主要由蛋白质和脱氧核糖核酸构成。具有遗传效应的DNA片段就是生物遗传的物质单位，被称为基因。生物的各种性状受

5、相应基因的控制。基因组合的特异性决定了生物的多样性，基因结构的稳定性则保证了生物物种的稳定性，而繁殖过程中基因的重组和突变造成同种生物世代之间或同代不同个体之间的差异，使物种进化成为可能。在一定生存环境的影响下，大多数高等生物物种通过自然选择和有性繁殖这两个基本[3]1过程实现进化。其中的进化因素可以分为自然选择、重组和突变三种基本形式。（1）自然选择（naturalselection）。达尔文的“自然选择、适者生存”学说表明：具有较强适应环境变化能力的生物个体具有更高的生存能力，使得它们在种群中的数量不断增加，同时该生物个体所具有的染色体性状特征在自然选择中得

6、以保留。北京理工大学计算机学院刘峡壁李冬妮《人工智能：算法之美》草稿第七章进化计算（2）重组（recombination）。来自不同父代染色体上的遗传物质进行随机组合，以产生不同于父代染色体的新染色体。那些在生物进化过程中所形成的对于自然环境有良好适应能力的信息都包含在父代个体所携带的染色体基因库中，并由子代个体继承下来。（3）突变（mutation）。父代染色体上的基因或父代染色体数目、大小和结构发生突然的改变，从而形成具有新染色体的子代个体。这种改变是一种不可逆过程，具有突发性、间断性和不可预测性。突变对于保证生物群体的多样性具有不可替代的作用。在上述三种基

7、本进化因素的作用下，自然界中的生物经历着不断循环的进化过程。在这一过程中，生物群体不断得到发展和完善。可见，生物进化过程本质上是一种优化过程，这已经成为人们的共识。既然生物进化是一种特定的优化过程，那么这一问题便可以与上一章所述的搜索问题建立类比关系。我们可以将每个解类比于生物中的个体，将每次迭代中的一组解类比于生物中的一代种群，将解的质量类比于个体对环境的适应度，将问题类比于个体所生存的环境，其类比关系如图7-1所示。根据这样的类比，便可以将解的优化过程模拟为相应的解的进化过程，从而设计出相应的进化计算方法，该类算法的一般框架将在第7.3节叙述。图7-1生物进

8、化与搜索的类比生物进化理