进化计算的过去、现在与未来

“遗传算法/进化计算研究生学术论坛” 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 集 1 进化计算的过去、现在与未来 * 孙瑞祥 屈梁生 西安交通大学诊断与控制学研究所 摘 要 本文对“进化计算”的历史、现状与展望进行了系统地综述。进化计算是 20世纪 90年代兴起的一门模拟生物进化与遗传规律的计算学科。目前已发展成为与人工神经网络、 模糊逻辑相并列的智能计算支撑技术。进化计算最重要的应用是传统优化 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 无法或难以解 决的科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 中的复杂优化问题。与传统优化方法相比，进化计算的优势在于全局优化性、 梯度信息不依赖性、简单易实施等。当前，进化计算主要由遗传算法、遗传编程、进化策略、 进化编程、DNA计算、分子计算等不同的分支组成。文中简介了它们的基本原理、异同点和 适合应用的问题，以及目前存在的难题。对未来的重要研究方向也进行了展望。 关键词 进化计算 计算智能 遗传算法 遗传编程 进化策略 进化编程 Evolutionary Computation: Past, Present and Future SUN Rui-Xiang and QU Liang-Sheng Institute of Diagnostics and Cybernetics (IDC), Xi’an Jiaotong University Abstract This paper systematically reviews the history, the state-of-the-art, and the prospects of evolutionary computation(EC), a novel computing discipline rose in 1990’s. Roughly speaking, EC is motivated from the principles of biological evolution and genetics. Now, it has been developed as one of the underpinning technologies for computational intelligence (CI), being the partnerships with artificial neural networks(ANN) and fuzzy logic(FL). From the viewpoint of application, EC is mainly applied to optimize the complicated industrial problems, which can not be tackled well with the traditional optimization methods. EC possesses many advantages over the conventional optimization techniques such as global optimization, independence of gradient, ease of implementation, and so on. Contemporarily, EC consists of the following avenues: genetic algorithms, genetic programming, evolution strategies, evolutionary programming, DNA computing, and molecular computing, etc. The rationales, similarities and differences, the application problems, and the puzzles of EC’s avenues are formulated. At the end, the future promising research directions are prospected. Key words Evolutionary Computation; Computational Intelligence; Genetic Algorithms; Genetic Programming; Evolution Strategies; Evolutionary Programming 1. 引言 “进化计算（Evolutionary computation, 简称 EC）”这一术语是在二十世纪九十年代初被提出的。它是 模拟生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的算法的总称，主要用来解决实 际中的复杂优化问题。目前，进化计算主要有遗传算法（Genetic algorithms, 简称 GA）、遗传编程（Genetic * 本文节选自西安交通大学博士学位论文“进化计算与智能诊断”(孙瑞祥， 2000年 4月)，并经修改与完善。 进化计算的过去、现在与未来 2 programming, 简称 GP）、进化策略（Evolution strategies, 简称 ES）和进化编程（Evolutionary programming, 简称 EP）等分支组成，其它的诸如 DNA计算和分子计算(Molecular computing)，也开始应用在实际问题中， 但还没有形成一个体系，比较零散。进化计算学科的出现，促进了它的不同分支之间的交流，可以取长补 短。上述四个主要分支是由不同的学者独立提出的，在 1992 年之前，基本上是独立发展，没有交流。各 个分支都有自己的优缺点，研究它们的优越性，并融合成新的进化算法，可以促进进化计算更广泛的应用。 目前，进化计算已经在人工智能、知识发现、模式识别、图象处理、决策分析、产品工艺 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 、生产调度、 股市分析等仍然不断增加的领域中发挥出了显著的作用。 本文对进化计算这一新兴学科作一综述，并对未来的研究方向进行展望。论文的主要内容为：首先， 概述了第一个进化计算算法—遗传算法的产生与发展；其次主要介绍了进化计算的国内外研究现状；然后， 给出了进化计算与其他学科的关系，各个分支的计算原理与实施技术；最后是进化计算的研究展望。 2. 第一个进化计算算法—遗传算法的产生与发展 大自然是人类获得灵感的源泉。将生物界所提供的答案应用于工程问题的求解被实践证明是一个成功 的有着辉煌前景的方法。进化的历史告诉我们，生物的进化是一个漫长而复杂的过程，在这个过程中，生 物从低级、简单的状态向高级、复杂的状态演变。现在，人们已经认识到进化不仅仅是生命科学的范畴， 进化是一种优化的过程，可以在计算机上模拟，并应用到工程领域中 [1] 。早在二十世纪六十年代初，美国 Michigan大学的 J. H. Holland教授就意识到了生物进化过程中蕴含着的朴素的优化思想，他借鉴了达尔文 的生物进化论和孟德尔的遗传定律的基本思想，并将其进行提取、简化与抽象，提出了第一个进化计算算 法－遗传算法。1975年出版了他的专著《Adaptation in Natural and Artificial Systems》[2]，标志着遗传算法 的正式诞生。在这本专著中，他称之为“Genetic Plans”，详细阐述了遗传算法的基本思想和结构框架。 "Genetic Algorithms"一词是首先出现在 J.D.Bagley的博士论文中，他研究了遗传算法在博弈论(六子棋)中的 参数搜索，这是遗传算法最早的应用[3]。 “遗传”与“算法”的结合体现了生物科学与计算机科学的相互渗透，相互融合。它借鉴生物的进化 思想，通过计算机模拟物种繁殖过程中父代遗传基因的重新组合与“优胜劣汰”的自然选择机制联合作用， 用来解决科学与工程中的复杂问题。图 1原理性地描述了自然进化与遗传算法之间的对应关系。 基因串 (染色体) 问题的 可行解 解的 评价值 目标函数解 码 编 码 基因型基因型基因型基因型 表现型表现型表现型表现型 适应度适应度适应度适应度 解 码 不同环境 图 1. 自然进化与遗传算法的对应关系 遗传算法产生后，在八十年代以前，并没有引起人们的关注，一方面是因为它本身还不成熟；另一方 面，当时的计算机容量小，计算速度慢，也使得需要较大计算量的遗传算法难以实际应用。但 Holland 和 他的学生一直在进行坚持不懈的努力，进行了理论研究，并开拓其应用领域[4]。直至现在，仍被认为是遗 传算法理论基础的模式定理（Schema Theorem）就是在这个阶段提出的，它揭示了遗传算法的内部机理和 解释了遗传算法的优化能力。 进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论还是应用都成了研究热点。尤其是应用研 究显得格外活跃，给遗传算法注入了新的活力。研究工作主要在以下几个方面开展。 进化计算的过去、现在与未来 3 (1)．遗传算法的基本理论 由于遗传算法是一种启发式的有向随机搜索算法，在进化过程中是否收敛到全局最优解成为其应用于 实际问题是否成功的关键。然而，Holland 的模式定理并没有从理论上回答遗传算法的全局优化性，它只 是研究了群体中部分特征模式的样本数目随进化代数的变化规律。近年来，关于遗传算法的全局收敛性证 明，许多学者进行了理论上的研究，取得了一定的成果[5-11]。 除了收敛性的证明，遗传算法的控制参数选取也是一个极其重要的理论问题，因为控制参数直接影响 着遗传算法的优化效率。但控制参数的选择与使用的遗传算子和具体应用问题密切相关。J.J.Grefenstette 利用离线性能（Off-line Performance）和在线性能（On-line Performance）评价控制参数的优化效率，研究 了用遗传算法来优化控制参数[12,13]。 自适应的杂交率和变异率[14]、特殊问题（如组合优化问题）的遗传算子的研究[15-18]也是遗传算法基 本理论的重要研究内容。 (2)．生物进化思想的深层利用 虽然遗传算法已经在许多领域中获得了成功的应用，但目前仍 存在几个悬而未决的问题。究其原因，主要是因为当前的遗传算法 只是简单地模拟了生物的进化，对生物进化机理作了很大简化，而 生物的进化是一个非常复杂的过程，单就目前生物学中对于遗传物 质的载体－染色体 DNA的研究，就足以令人感到遗传算法在利用生 物进化的思想方面已经滞后。分子生物学告诉我们 DNA 的结构 为由 4 种碱基配成的扭转阶梯螺旋，如图 2 所示。生物技术的发展 已经使保留在化石中的 DNA复活生命和历史、利用 DNA分析技术 进行刑事分析成为可能。而遗传算法的染色体的表示则简单得多， 而且用来模拟生物有性繁殖的杂交算子也多是线性串的部分交换，如 图 2 DNA的双螺旋结构 图 3所示。所以，要提高遗传算法的性能，必须深入地研究生物的结构与进化规律，如近年发展起来的免 疫系统模型和协同进化模型等。 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 杂交点 杂交点 杂交点 杂交点 父代 1 父代 2 子代 1 子代 2 (a) 杂交前 (b) 杂交后 图 3 遗传算法的杂交算子 除了常用的二进制单点杂交与位变异算子，一些借鉴生物进化的新型遗传算子也已经应用在遗传算法 中，如倒位（Inversion）、显性（Dominance）、二倍体（Diploidy）、缺失（Deletion）等[19-23]，至于它们对 提高遗传算法优化能力的作用大小仍然值得深入研究。 (3)．遗传算法的并行处理 遗传算法具有内在并行性（Inherent Parallelism）和内含并行性（Implicit Parallelism）。前者是指遗传 算法的适应度评价是并行的，可以在并行机上进行，同时，可以采用多群体进化，群体之间可以进行通信。 后者是指遗传算法虽然每代仅处理 N 个个体（ N 为群体规模），但却有效处理了 )( 3NO 个模式。关于遗 传算法的并行处理研究多集中于前者[24]。 (4)．遗传算法的广泛应用 遗传算法的应用是一个发展最为迅速的研究方向。目前已经在模式识别[25,26]、图象处理[27]、人工智能 进化计算的过去、现在与未来 4 [28,29]、经济管理[30]、机械工程[4,31]、电气工程[4]、通讯[32]、分子生物学[33]等举不胜举的领域中获得了较成 功的应用。但如何将各专业的知识融入到遗传算法的算子中，目前仍在继续研究。 除了遗传算法 GA外，遗传编程 GP、进化策略 ES、进化编程 EP等也是模拟生物的进化计算算法。 它们的产生与发展将在本文的第 5部分详细介绍。在进化计算的这几个分支中，遗传算法的研究与应用最 为广泛与深入。目前，进化计算已经和人工神经网络（Artificial Neural Networks,简称 ANN），模糊逻辑（Fuzzy Logic,简称 FL）相结合，产生了一门新的综合性的计算技术学科－计算智能（Computational Intelligence， 简称 CI），这些学科之间的关系将在论文的第 4部分介绍。 3.3.3.3. 进化计算的研究现状 进化计算的研究与应用，无论是研究队伍的规模，发表的论文数量还是网上的信息资源，发展速度都 很快，已经得到了国际学术界的广泛认可。1994 年，IEEE 神经网络委员会主持召开了第一届进化计算国 际会议，并成立了 IEEE进化计算委员会，此会每 3年与 IEEE神经网络国际会议、IEEE模糊系统国际会 议在同一地点先后连续举行，共同称为 IEEE计算智能 CI国际会议，并分别出版并列的 IEEE Transactions on Evolutionary Computation, IEEE Transactions on Neural Networks 和 IEEE Transactions on Fuzzy Sets学术期 刊[4,34]。另外，进化计算的国际期刊 Evolutionary Computation也于 1993年诞生。以遗传算法为主的进化计 算的研究内容也在其他学术期刊中出版了专辑 [35-38] ，同时在Machine Learning; IEEE Transactions on Systems, Man and Cybernetics; Complex Systems; Artificial Intelligence等重要国际期刊上经常见到。由此可见进化计 算的发展之快。 除了 IEEE举行的进化计算国际会议以外，其实，早在 1985年，就在美国的 Pittsburgh召开了第一届 遗传算法国际会议[39]，在会议期间，国际遗传算法学会（International Society of Genetic Algorithms）也宣 告成立。自此，来自不同学科和工程应用领域的各国学者在遗传算法方面有了交流、探讨的国际论坛。国 际遗传算法会议每两年召开一次[40-45]。此外，其他类型的各种会议，如以遗传编程、进化策略或进化编程 为主题的研讨会也很频繁 [46-50]。 Internet 技术的发展给进化计算的研究者带来了丰富的信息资源，使他们可以获取更广泛、快捷的交 流以及极大地获取有关进化计算的科研资料，同时可以随时了解有关进化计算研究与应用的最新进展。美 国海军后勤研究中心对进化计算的研究极为重视，于 1985 年首先在电子网络上建立了全球性的有关遗传 算法的信息交流节点（GA-List-Request@aic.nrl.navy.mil），不定期编辑出版电子遗传算法文摘（GA Digest）， 交流有关遗传算法的最新信息（如有关研究和应用以及会议等方面的最新信息）。网络上与进化计算有关 的信息实际上是一个有关进化计算的巨大资料库，为使研究人员更方便地利用这些资源，在交互网络上建 立了几个比较大的节点，称为 ENCORE（Evolutionary Computation Repository Network）。通过这几个节点 中的任一个，不仅可以了解到网络上主要的有关进化计算的信息，而且可以获取自由软件，交流科技报告 等，如，可获得 1957年到现在的所有有关遗传算法的科技论文的目录，该目录中包括 2500多篇文献[34]。 除了期刊、会议、电子信息库外，进化计算的软件也形成商业化产品。根据系统开发和设计目标的不 同，可分为三类：面向应用的系统、面向算法的系统和工具包系统，如表 1所示 [21,51]。在面向应用的系统 中，采用了许多创新性的策略，如 PC/Beagle和 XpertRule GenAsys等系统可用遗传算法生成知识域的新规 则。 表 1 进化计算的软件产品及分类 面向算法的系统 工具包系统 面向应用的系统 专门算法 算法库 教学系统 通用系统 Evolver Omega Escapade GAGA EM GAlib GA Workbench ComputerAnts GAOT Engeneer 进化计算的过去、现在与未来 5 PC/Beagle Generator XpertRule GenAsys GAUCSD mGA Genesis Genitor libGA PGApack OOGA GAMusic SGA DOUGAL GAME MicroGA Splicer Pagasus 进化计算的研究内容十分广泛，国外的发展也瞬息万变。下面概述一下国外的研究现状，特别是美国、 英国和德国等走在进化计算研究前列的国家的研究成果。 (1) 美国 Illinois大学的 D.E.Goldberg在他领导的 Illinois遗传算法实验室（Illinois Genetic Algorithms Laboratory, IlliGAL）中对遗传算法的基本理论进行了广泛地研究，取得了一系列的成果[52-58]。早在 1989 年，他就出版了目前被认为是遗传算法最经典、最全面的教科书[19]。 (2) H.Kargupta将 Shannon的信息熵[59]引入遗传算法，研究了遗传算法群体的多样性，他借鉴了通信 领域中的信息冗余性，研究了在不损失进化群体的多样性的情况下如何提高冗余性[60]。 (3) 关于遗传算法的控制参数的优化和优化效率的性能评估的研究也引起一些学者的重视，遗传算法 的控制参数是指群体规模、杂交率、变异率以及其他一些遗传算法的参数。目前，还没有一种通用的方法， 可以根据要解决的问题自动地设置高效的控制参数，只能根据经验和多次运行遗传算法的结果进行人工设 置和修正。J.J.Grefenstette利用遗传算法来优化遗传算法的控制参数（MetaGA），通过 K.A.DeJong提出的 优化效率的性能评价指标“在线性能”与“离线性能”[13]来构造适应度，获得了一些有益的结论[12]。 (4) Holland的标准遗传算法并没有提供如何解决约束优化问题，在应用遗传算法解决工程中的复杂优 化问题时，对于约束的处理是一个至关重要的问题。Michalewicz 对此作了坚持不懈地研究，提出了几种 较有效的方法[16,61]。对于约束的处理，应用最多的方法是惩罚函数法[62,63]。 (5) 模式识别是机器智能与自动化的支撑技术，进化计算在模式识别中也发挥了它的优势，主要集中 在特征提取上。从 N 个初始特征中选出 n（n 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 如图 5所示。从图 5可以看出遗传算法实质上是一个迭代计算过程(虚线框内)，其实 施的主要步骤包括编码、群体初始化、选择、遗传操作、评价和终止判定六步。 ① 编码 编码的主要任务是建立解空间与染色体空间点的一一对应关系。遗传算法通常在染色体空间中进行操 作。在多数情况下，不同的编码方式决定了不同的遗传操作方式。对编码的一般原则性要求主要有完备性、 健全性和非冗余性。完备性是指解空间中的所有点都能表示为染色体空间中的点；健全性是指染色体空间 中的所有点都能表示为解空间中的点；非冗余性是指解空间到染色体空间的一一对应。 ② 群体初始化 与传统优化方法相比，遗传算法一个显著的特点是对群体操作，所以在进化的开始必须进行群体初始 化，产生进化的起点群体。通常随机构造初始群体，当然也可以在初始群体中植入一些具有特殊“性状” 的个体，以加速算法向全局最优解的收敛。 ③ 选择 遗传算法的选择操作与生物的自然选择机制相类似，它体现了“适者生存，不适者被淘汰”的生物进 化机理。实现原则为“性状”优良的个体具有较多的机会被选进交配池产生后代，而“性状”低劣的个体 则具有较少的机会被选择。这里的“性状”通过评价操作进行定量化。最常用的选择方式是赌轮选择、联 赛选择和排序选择。 ④ 遗传操作 遗传操作被视为遗传算法的核心。它直接影响和决定了遗传算法的优化能力，是生物进化机理在遗传 算法中最主要的体现。目前，已有适用于各种不同类型问题的多种遗传操作算子。其中，杂交与变异是最 常用的遗传操作，杂交体现了同一群体中不同个体之间的信息交换，而变异则能维系群体中信息的多样性。 它们在优化中的主要作用是以不同的方式不断产生新的个体。 ⑤ 评价 评价是遗传算法的驱动力，是遗传算法体现有向搜索，区别于随机游荡的标志。它将同一群体中不同 个体的优劣进行数值标量化，为选择操作提供客观依据。遗传算法评价准则的确定主要依赖于要求解的问 题。 表 2 生物学术语在遗传算法中的含义 生物学生物学生物学生物学 遗传算法遗传算法遗传算法遗传算法 进化计算的过去、现在与未来 8 染色体 字符串 基因 字符位 基因型 字符串结构 表现型 字符串含义 杂交 字符串片段的互换 变异 字符位的改变 01011101 0101 0001 0110 1001 1101 0101 0 选择 解空间 初始化 0101 001随机 变异 杂交 遗传算子 11010001 01100101 001 01010101 0101 1 11010101 01101001 01010001 01010101 1101100100110110 编码 评价 ? 终止判定 No Yes 01001011 01100101 01010001 10010101 11000110 终止群体 解码 最优解 迭代过程 赌轮 可行解 适应度 图 5 遗传算法的计算流程 ⑥ 终止判定 如果说初始化是遗传算法的入口，终止判定则是它的出口。一般用事先给定的进化最大代数作终止判 据，它的设定较大地依靠经验和运行结果。 与传统优化算法(主要包括共轭方向类算法和以牛顿法为主的下降方向类算法 [101] )相比较，遗传算法的 主要特点有以下四个方面： ① 群体搜索策略。传统优化算法采用点到点的搜索方式；而遗传算法则采用群体到群体的搜索方式， 因而较易于达到全局最优。 ② 搜索不依赖于目标函数的梯度信息，只需提供能够评价个体相对优劣的数量指标(适应度)即可。 因此，遗传算法的适用面更广，尤其适合于处理复杂的非线性问题，包括目标函数为高维、不可导、不连 续或带有噪声的优化问题；而传统优化方法对此无法或难以解决。 ③ 进化过程具有有向随机性，这是遗传算法与穷举法的本质区别。同时，遗传算法的搜索结果具有 非稳定性；与传统优化方法相比，优化效率相对较低。 ④ 简单通用，鲁棒性强。 (2).遗传编程 在遗传算法的发展中，将线性编码改进为非线性编码，是近年来提出的一种新的思路。1992年 Stanford 大学的 J.R.Koza[102,103]首先提出了一种在编码方式上与常规遗传算法有着本质不同的仿生进化算法，它采 用了层式编码结构，由于在遗传算法的基础上，改进了编码方法，他称之为“遗传编程”（Genetic Programming，简称 GP），同遗传算法一样，它们都属于新兴的进化计算学科；但相对于遗传算法，遗传 编程更适合应用于层式结构的优化。 遗传编程 GP[102-107]是由遗传算法发展、延伸而来的, 传统的遗传算法是用定长的线性字符串表达问 题，而工程中许多复杂问题往往不能用简单的字符串表达所有的性质，因此有必要对传统的遗传算法进行 改进。遗传编程就是在此背景下产生的，它与遗传算法最大的不同是以层次结构（“树”型）表达问题， 而且其结构与大小都是动态自适应调整；因此，遗传编程更适于表达复杂的结构问题。遗传编程的任务就 进化计算的过去、现在与未来 9 是从由许多树型可行解组成的搜索空间中寻找出一个具有最佳适应度的“树”。遗传编程提供了一套寻找 具有最好适应度的“树”的方法。目前，遗传编程的研究已经渗透到工程技术科学，生命科学及社会科学 的各个领域中。 图 6是遗传编程的计算流程，图中 Gen表示遗传代数，N表示群体规模，i表示个体计数器。从该图 中可以看出，遗传编程与遗传算法的原理基本相同，但在以下三个方面的操作与遗传算法有所不同。 a.编码 前文已经提到，遗传编程采用层式的编码形式。例如，遗传编程用于特征构造时，代表由简单特征组 合而成的复合特征如图 7(b)中的个体所示，(a)是遗传算法的个体，从(a)，(b)两图可看出二者编码的不 同。图中， ),...,2,1( SiOPi = 表示 S个运算符（单目或双目）； ),...,2,1( TjFj = 表示T 个初始特征。遗传 编程的个体就是通过运算符和初始特征的不同树形组合来表达。 b.构造初始群体 遗传编程初始群体的构造比遗传算法复杂得多，主要是由于层式树形个体的构造比线性基因串的构造 复杂。在构造初始群体以前，要做好以下两方面的工作： 构造初始群体 终止条件 满足？ 输出结果 结 束评价 开 始 Gen:=0 Yes No i:=0 i=N? Gen:=Gen+1 Yes 选择遗传算子 杂 交 变 异 i:=i+1 i:=i+1 No 图 6 遗传编程的计算流程 1) 终止符集的构造 终止符是指如图 7中所示的树形结构末端的叶子节点 ),...,2,1( TjFj = 。终止符集根据求解对象的不 同而不同，通常由常量、变量、符号等组成。 进化计算的过去、现在与未来 10 1 0 1 …… 0 1 0 n 位 OP1 OP2 OP3 F1 F2 F3 （a）遗传算法的个体 (b) 遗传编程的个体 图 7 遗传算法与遗传编程的编码结构 2) 运算符集的构造 运算符 ),...,2,1( SiOPi = 代表了一个或多个终止符之间执行的操作。运算符集的构造也因具体问题而 异。常见的运算符主要有： 算术运算符，如 ＋，－，×，÷等； 标准数学函数，如 sin，cos，exp，log等； 布尔运算符，如 and，or，not等； 条件运算符，如 if-then-else，case等。 以上列举的都是计算机程序中经常使用的运算符。另外，也可以根据适用的问题自行设计面向对象的 运算符。终止符与运算符皆称为遗传编程的元素。 有了以上两步准备，就可以进行初始群体的构造了。首先从运算符集中随机选择一个运算符，没有从 终止符集选择是为了避免产生空的个体；然后根据运算符的目数，确定从该运算符引出的线数；其次，依 次在每条线的终端，加入随机选出的元素；最后，重复上述过程，直至“生长”为满足要求的个体。实际 上，终止符可看作是零目运算符。初始群体由 N个以同样方式产生的个体组成（N为预先确定的群体规模）。 c.遗传算子 编码方式决定了相应的遗传算子操作方式，因此，遗传编程的遗传算子比遗传算法也要复杂得多。下 面，就最常用的杂交和变异算子作一对照。 1) 杂交 遗传算法的杂交算子如图 3所示；遗传编程的杂交算子如图 8所示。对比二者，可以发现遗传算法的 杂交仅需要线性串的复制操作；而遗传编程的杂交操作则涉及到子树结构的拆合。对遗传算法，如果参与 杂交操作的两个个体完全相同，则不会产生新个体；而对遗传编程，所产生的子代个体与父代一般是不相 同的，除非两个个体的杂交点恰好也相同，但出现这种情况的概率极小，所以遗传编程的杂交施加了一个 偏离同一化的反平衡作用，有利于维持群体的多样性。 2) 变异 图 9 是遗传算法的变异算子；图 10 是遗传编程的变异算子。遗传算法的变异采用位的置反操作；而 遗传编程的变异方式有两种：运算符变异和终止符变异。为了保证变异后产生的新个体在语法上的合法性， 必须首先判断变异点是运算符还是终止符，然后，根据判断结果，从相应的集合中随机选取一个元素代替 原来的元素。如果是运算符，还要注意变异前后的“运算目数”相同。 进化计算的过去、现在与未来 11 OP1 OP2 OP3 F1 F2 F3 OP4 F4 F5 杂交点 杂交点 父代 1 父代 2 (a) 杂交前 OP1 OP2 OP3 F1 F2 F3 OP4 F4 F5 杂交点 杂交点 子代 1 子代 2 （b）杂交后 图 8 遗传编程的杂交算子 变异位 变异位 1 1 1 0 0 0 0 10 单亲父代 子代 1 1 1 0 0 0 0 11 （a）变异前 (b) 变异后 图 9 遗传算法的变异算子 OP1 OP2 OP3 F1 F2 F3 变异点 单亲父代 OP1 OP2 OP4 F1 F2 F3 变异点 子代 （a）运算符变异 进化计算的过去、现在与未来 12 OP1 OP2 OP3 F1 F2 F3 变异点 单亲父代 OP1 OP2 OP3 F1 F4 F3 变异点 子代 (b) 终止符变异 图 10 遗传编程的变异算子 遗传编程的理论和应用虽然还只是刚刚起步，在如何优化数值和“回旋体”的避免方面[141]仍然需要 继续的研究工作，但这并不能限制住遗传编程的广泛应用，特别是在模式识别中的特征构造和特征选择中， 将大有用武之地。 (3).进化策略 进化策略ES[1,105,108-111]是于二十世纪六十年代由德国的H.-P.Schwefel 和 I..Rechenberg在研究流体动力 学中的弯管形态优化过程中，共同开发出的一种适合于实数变量的、模拟生物进化的一种优化算法。其优 化能力主要依靠变异算子的作用，后来受遗传算法的启迪，也引入了杂交算子，不过，杂交是进化策略的 辅助算子。 设群体规模为N ，进化策略的个体表示为 NPi 1,2,...,iσ),( =x, 。其中， }x,...,x,{x M21=xxxx 为群体 中的一个候选实数解, }σ,...,σ,{σ M21=σσσσ 为候选解 xxxx变异时的正实数参数，称为“策略参数”;M为优化 变量的个数，即优化空间的维数。Schwefel 引入了一种高斯变异算子，如果父代某个个体表示为 NPk ≤≤ k1 ,σ( )x, ，由该个体变异后的子代个体表示为 )σ(' ',x'kP ，其中 }x,...,x,{x 'M'2'1=''''xxxx ， }σ,...,σ,{σ 'M ' 2 ' 1= ''''σσσσ ，则变异过程为： 先按均值为 0，标准差为 1的正态分布产生一个随机实数α； 然后按下面两式计算 ),...,2,1(]exp[ ''j Mjjj =⋅+⋅⋅= βτατσσ (1) ),...,2,1('j Mjxx jj =+= ε (2) 其中： )10(~ ，NIDjβ — 对循环变量 j，表示按均值为 0，标准差为 1的高斯分布而产生的一个随机实数。 即每个循环变量采用不同的随机数； ),0(~ 'jj NID σε —表示按均值为 0，标准差为 ' jσ 的高斯分布而产生的一个随机数； τ — 群体变异步长； 'τ — 个体变异步长。 从变异公式(1)和(2)可以看出，进化策略的变异主要是 jσ 的带有随机性的调整，τ 和 'τ 是对调整起 关键作用的两个参数，一般取: M2 1 =τ ; M2 1' =τ (3) 它们是固定不变的，所以，实质上，新的候选解是以原来候选解加上一个满足高斯分布的随机变量的一个 样本值来变异的。 进化计算的过去、现在与未来 13 (4). 进化编程 进化编程 EP 也是在六十年代由美国的 L.J.Fogel 等[1,110,112-114]为求解预测问题而提出的一种有限状态 机进化模型，在这个进化模型中，机器的状态基于均匀随机分布的规律来进行变异。90年代，D.B.Fogel[113] 又将其思想拓展到实数空间，使其能够用来求解实数空间中的优化问题，并在其变异中引入正态分布技术。 它与进化策略有许多相似之处。个体的表示同进化策略，不同之处在于它不用杂交算子，变异与选择方式 也与进化策略不同。变异方式为 ),...,2,1()('j MjxF jj =+⋅= γβσ (4) 候选解的变异按(2)式进行。这里， )(xF 为适应度函数， jβ ， jγ 为特定参数，一般取为 1 和 0。从(4)式 可以看出，进化编程的 jσ 是根据适应度函数的大小来调整的。 6 进化计算的研究展望 进化计算虽然在理论与应用方面都取得了令人瞩目的成就，但仍然存在许多理论和应用技术中的不足 与缺陷，值得深入研究；同时，开辟进化计算应用的新领域也迫在眉睫。昔日的美好不能决定未来的辉煌， 对未来的研究展望可以明确进化计算的研究方向。在生物技术与计算机科学高度发展的二十一世纪，进化 计算将在以下几个关键问题上获得进展。 (1).遗传算法的早熟问题 遗传算法的早熟问题（Premature Convergence）是指进化过程收敛于非期望的局部极值或群体的最佳 个体进化到问题的非最优解，进化过程就停止不前的现象。早熟问题严重影响了遗传算法的应用，目前， 还没有一种通用的解决方法。早熟问题的困难在于用遗传算法求解一个复杂的实际优化问题，无法定量准 确地判断在优化过程中何时出现早熟，因而，控制或消除它就比较困难。随着其他技术的发展，早熟问题 也必将从遗传算法的遗留问题中销声匿迹。 (2).进化计算在人工智能中的应用 随着人们对工业系统智能性能要求的增长，人工智能的研究必将得到迅速的发展；而人工智能中存在 着大量的复杂优化问题，单凭传统的优化技术，如梯度法，共轭方向法[101]等是无能为力的。作为新颖的 智能优化技术，进化计算必将在未来的人工智能中起到核心的优化技术作用，如机器学习中的规则优化， 分类器系统中知识的自动获取、筛选，进化计算与人工神经网络的融合，图象识别等。 (3).进化计算在人工生命研究中的应用 人工生命是研究用人工的方法模拟自然生命的特有行为，而基于进化计算的模型是研究人工生命的主要基 础理论之一。这里，特有行为是指自组织行为、学习行为等。人工生命研究的意义在于，从科学的角度讲， 通过对生命现象基本动力学的抽象，可以研究生命的起源，再现生命的原始进化过程，揭示生命遗传信息 的存储与处理原理；从工程的角度讲，可以利用生命计算原理研究进化系统和自适应系统的构造，并应用 在实际工程问题中。进化计算的进展必然也会促进人工生命的研究。 (4).进化计算与进化硬件 进化硬件的发展空间依然很大，需要硬件、软件和进化计算界的学者共同努力。 参考文献 [1] D.B.Fogel: An Introduction to Simulated Evolutionary Optimization, IEEE Transactions on Neural Networks, Vol.5, No.1, 3-14,1994 [2] J.H.Holland: Adaptation in Natural and Artificial Systems, MIT Press,1992 [3] J.D.Bagley: The Bahavior of Adaptive System which Employ Genetic and Correlation Algorithm, Ph.D. 进化计算的过去、现在与未来 14 dissertation, Univeristy of Michigan, No.68-7556,1967 [4] 陆金桂，李 谦，王 浩，曹一家：遗传算法原理及其工程应用，中国矿业大学出版社，1-4，1997.12 [5] G.Rudolph: Convergence Analysis of Canonical Genetic Algorithms, IEEE Transactions on Neural Networks, Vol.5, No.1,96-101,1994 [6] G.Rudolph: Convergence of Non-elitist Strategies. Proceedngs of the IEEE Conference on Evolutionary Computation, New York,1994 [7] A.E.Eiben, E.H.L.Aarts, and K.M.Van Hee: Global Convergence of Genetic Algorithms: A Markov Chain Analysis, in Parallel Problem Solving from Nature, H.-P. Schwefel and R.Manner, Eds. Springer,4-12,1991 [8] R.Das, D.Whitley: The Only Challenging Problems are Deceptive: Global Search by Solving Order-1 Hyperplanes. Proceedings of International Conference on Genetic Algorithms,166-173,1991 [9] A.Nix and M.D.Vose: Modeling Genetic Algorithms with Markov Chains, Annals of Mathematics and Artificial Intelligence, Vol.5,1992 [10] X.Qi and F.Palmieri: Theoretical Analysis of Canonical Genetic Algorithms with a Population