兰州大学硕士学位论文 进化程序设计模式研究和生命进化现象的程序模拟
在达尔文在世时以及死后相当长一段时间，大部分生物学家，特别是古生物学家，都相信生物进化是能够出现跃变的，认为新的形态和器官是源自大的跃变，而不是微小的变异在自然选择的作用下缓慢而逐渐地累积下来的。包括赫胥黎在内的一些古生物学家由于强调生物化石的不连续性而持这种观点。在遗传学诞生之后的一段时间内，早期遗传学家们由于强调遗传性状的不连续性，也普遍接受跃变论。在20世纪40年代，“现代综合”学说将遗传学和自然选择学说成功地结合起来，渐变论逐渐占了优势。但是近二、三十年来，古生物学和进化发育生物学的研究表明，生物进化过程很可能是渐变和跃变两种模式都存在的，跃变论又有抬头的趋势。不过，进化论所说的跃变，除了某些非常特殊的情形（例如植物经杂交出现新种），并非是指在一代或数代之间发生的进化，而可能经历了数千年、数万年乃至数百万年，只不过以地质年代来衡量显得很短暂而已。
达尔文所提倡的生物进化理论向大家论证了生物是不断进化的，并且对生物进化的原因提出了合理的解释，但缺点在于未对遗传变异的真正的内涵作出合理的解释，他也仅是在个体水平对生物进化作出了一定的解释，他认为物种的形成是渐变的结果，却对物种大爆发现象无法作出合理的解释。
2.4拉马克进化理论和达尔文进化理论比较
虽然拉马克和达尔文都认识到了生物是进化的并提出了各自的进化学说，但他们的思想又是不同的，主要有以下区别：第一，他们都同意变异的普遍性，但达尔文认为变异是随机的[13]，拉马克认为变异不是随机的而是有目的的[10]；第二，拉马克认为引起进化演变的原因之一是生物对环境的特殊条件做出的反射，而达尔文却不同意这一点。达尔文认为变异是随机的无意义的，只是后来的自然环境选择和它相适应的生物体[14]。简单地说，拉马克学说的要点是用进废退，生物体对环境变化的反射导致了变异从而使得生物进化，变异是有目标和意义的；达尔文学说的要点是自然选择，生物体的变异是随机的无意义的，自然环境选择保留和它相适应的物种，从而实现了生物进化。
达尔文和拉马克在进化机制上的根本区别在于拉马克认为环境及其变化在顺序上居先。它们在生物中产生需求与活动，而后引起适应性变异。而就达尔文来说，首先是随机的变异，然后才是环境的有次序的 “自然选择”，变异并不是由环境直接或间接引起的。
对于长颈鹿的长颈如何而来这个著名的问题，达尔文的理论这样认为：长脖子如何而来？这是因为长颈鹿的祖先当中本来就有长脖子和短脖子的变异品种，当外界环境改变时或者当食物变少时，长脖子的长颈鹿因为能够吃到高处的树叶而存活下来，
6
兰州大学硕士学位论文 进化程序设计模式研究和生命进化现象的程序模拟
短脖子的长颈鹿却由于食物少而逐渐消亡，经过若干代的选择之后，长脖子的性状在鹿群中扩散开来，因而长颈鹿这个新的物种就产生了。
而拉马克的理论这样认为：因为早期的长颈鹿经常伸长了脖子去吃高处的树叶，脖子因而得到了锻炼，变得长了一些（这就是所谓的用进废退），这些可以遗传给后代并且在后代中加强，所以长颈鹿的后代的脖子比父母的长一些（后代获得了性状的遗传），这样很多代以后，长颈鹿的脖子就变长了。
本文并不打算论述拉马克和达尔文谁的学说更正确，这超出了作者的能力，我们只是在本文中使用进化程序设计模式，用程序模型来解释拉马克的进化机制和达尔文的进化机制在程序层面都有其实现的可能，并演示其实现技巧。
2.5 综合进化理论
随着不断深入的科学研究和新的自然现象的发现,近现代的科学进化论研究在达尔文的理论基础上不断发展完善。虽然我们认识到变异的很多内容,但是我们在很大程度上还没有认识到进化的本质。上世纪70 年代, 生物学家们先后提出了生物进化的“间断平衡学说”和分子进化的“中性学说”等新的生物进化理论。
综合目前所有人们所提出的进化思想, 人们对生命进化的历史认识逐步明朗。通过对比已出现的各种进化思想, 现代的综合进化论(现代达尔文主义, Modern
[15]Derwinism) 是目前大家认为比较完善而且在生物学界起主导作用的理论。它的主要
思想就是:生物进化的基本单位是群体而非个体, 自然选择是生物进化方向的决定力量,生物进化的实质是种群基因频率的改变。突变和基因重组，自然选择及隔离是物种形成过程的三个基本环节，通过它们的综合作用，种群产生分化，最终导致新物种形成。在这个过程中，遗传物质突变和通过有性杂交实现的基因重组是生物进化的原材料,自然选择使种群的基因频率定向改变并决定生物进化的方向，隔离是新物种形成的必要条件。该理论认为进化是渐进的，它不承认获得性的遗传,它认为自然选择是在群体水平上的进行的。
2.6 本章小结
本章主要介绍了生物学界几种生物进化理论的主要内容。首先介绍了拉马克的用进废退学说，接着介绍了达尔文的自然选择学说，然后对这两种理论进行了比较，最后提到了现代的综合进化理论。
7
兰州大学硕士学位论文 进化程序设计模式研究和生命进化现象的程序模拟
第三章 传统进化算法介绍
在计算领域，基于生物进化理论中的遗传变异和自然选择等生物进化机制产生了一类全局随机搜索算法——进化算法。进化算法主要包括四部分：遗传算法(GA)、进化策略(ES)、进化规划和遗传规划[16]。本章主要就其中的遗传算法（Genetic Algorithms，GA）从基本原理、算法的内容和特点、存在的问题方面做一些简单的介绍，其目的主要是为了区别本文中的生物进化模拟算法与传统进化算法的不同。
3.1 遗传算法
3.1.1 遗传算法概述
美国密西根大学的霍兰德（John Holland）教授最早借鉴达尔文的生物进化论和孟德尔遗传定律的基本思想，用计算科学的语言加以提取、简化和抽象后，提出了第一个成熟的进化计算方法，最终发展成为遗传算法（Genetic algorithms）。1975年，霍兰德教授出版了《自然与人工系统的适应》一书，标志着遗传算法的正式诞生[17]。
从原理上来讲，生命进化现象最终归结于基因组的进化，遗传算法就是利用计算机来模拟种群繁殖过程中基因组的重新组合以及“优胜劣汰”这一自然选择机制的复合作用。类似于生物体中的基因编码，遗传算法用“编码”和“解码”等概念简化了自然进化过程中的若干要素，如图3-1所示。
图3-1 自然进化与遗传算法的对应关系
遗传算法通过模拟生物物种的进化过程，把一组模型中优良个体的存活度和随机变异的编码交换结合在一起。根据给定的参数变化范围及变化步长，将每个初始模型的全部参数用许多串联在一起的二进制编码(或其他编码)串表示。通过选择、交叉和变异不断保留优势特征，最后得到问题的最优解[18]。换句话说，它是通过模拟自然进化过程来搜索最优解，首先利用某种编码技术，将待解问题编码成类似于染色体的编码串，然后模拟由这些码串组成的群体在特定问题环境中的演变过程，最终找到求解
8
兰州大学硕士学位论文 进化程序设计模式研究和生命进化现象的程序模拟
问题的最优近似解。它是智能优化算法的一种，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。从理论上说可以在一定的时间内找到最优解或近似最优解。30多年来，遗传算法在基础理论研究及算法设计和实际应用中，都有了较大发展，成为求解全局优化问题的有力工具之一。
遗传算法虽然具有群体并行搜索特性和很强的鲁棒性(强壮性)等一些优点，但它的编码不规则及编码存在的不准确性、其搜索的计算量大且搜索效率低、出现早熟收敛等等一些不足之处，严重影响了遗传算法的应用，也是需要今后解决和改进问题的地方。
3.1.2 遗传算法的基本原理与特点
遗传算法主要模拟了自然选择和自然遗传过程中所发生的一系列繁殖、交叉和基因突变等现象，从问题域可能存在解的一个种群开始，而一个种群则是由经过基因编码的一定数目的个体组成。每个个体本质上都是类似于染色体的编码串，该编码串代表一个问题域的近似解。按照适者生存和优胜劣汰的原理，从初代种群产生开始，逐代演化产生出越来越好的近似解。在每一个子代中，首先根据问题域中个体的适应度和大小挑选出个体，然后借助于生物遗传学中的遗传算子进行组合，进行一些交叉和变异，这样就产生出了代表新的解集的新的种群。上述过程将导致所产生的后生代种群将比前一代更加适应外界环境，而我们最后将末代种群中的最优个体经过解码，就能得到问题的近似最优解。
Goldberg总结出了基本遗传算法（SGA，Simple Genetic Algorithms，又称简单遗传算法或标准遗传算法），它的特点是操作过程比较简单，读者很易理解，它是其它遗传算法的基础。
下面我们就以最典型、最简单的二进制型遗传算法为例，介绍遗传算法的基本原理和特点[17]。 （一）构成要素
? 染色体编码：对问题的解空间进行编码，使之能进行遗传操作，目前最常用的
是二进制编码方案。
? 适应度函数：用来评价一个染色体编码串对环境的适应度。
? 选择算子/复制算子：按照某种策略从父代中挑选个体进入下一代，可以使用
比例选择或者轮盘选择。
? 交叉算子/杂交算子：从群体上挑选两个个体，按照某种策略，如单点插入或
一致交叉等，使它们相互交换部分染色体编码，从而形成两个新的个体。 ? 变异算子：按照一定概率改变染色体中某些基因码串，从而可导致和父代不同。 （二）实现步骤
9
