下载掌阅APP，畅读海量书库
立即打开
一直以来，人类从大自然中不断得到启迪，通过发现自然界中的一些规律，或模仿其他生物的行为模式，从而获得灵感解决各种问题。进化算法（Evolutionary Algorithm，EA）是通过模拟自然界中生物基因遗传与种群进化的过程和机制，而产生的一种群体导向随机搜索技术和方法。它的基本思想来源于达尔文的生物进化学说，认为生物进化的主要原因是基因的遗传与突变，以及“优胜劣汰、适者生存”的竞争机制。能在搜索过程中自动获取搜索空间的知识，并积累搜索空间的有效知识，缩小搜索空间范围，自适应地控制搜索过程，动态有效地降低问题的复杂度，从而求得原问题的最优解。另外，由于进化算法具有高度并行性、自组织、自适应、自学习等特征，效率高、易于操作、简单通用，有效地克服了传统方法解决复杂问题时的困难和障碍，因此被广泛应用于不同的领域中。
进化算法仿效生物的进化和遗传，与生物学的进化法则一样，也是一种迭代进化法。每一次迭代被看成是一代生物个体的繁殖，因此被称为一个“代”（Generation）。在进化算法中，一般是从原问题的一群解出发，改进到另一群较好的解，然后重复这一过程，直到达到全局的最优值。每一群解被称为一个“解群”（Population），每一个解被称为一个“个体”（Individual），每个个体要求用一组有序排列的字符串来表示，因此它是用编码方式进行表示的。进化计算的运算基础是字符串或字符段，它就相当于生物学的染色体，字符串或字符段由一系列字符组成，每个字符都有自己的含义，相当于基因。
生物学的基本原则在进化计算中有相应的体现，进化算法无须了解问题的全部特征，就可以通过体现进化机制的进化过程来完成对问题的求解。进化计算的迭代过程，相当于生物学的逐代进化；进化计算中的选择算子体现生物界中的“自然竞争、优胜劣汰”机制；进化计算的交叉、重组，相当于生物界的交配；进化计算的变异，相当于生物界的变异。此外，生物学中的等位基因、显性性状、隐性性状、表现型、基因型等术语，在进化计算中都有相应的体现。
进化算法采用简单的编码技术来表示一个个体所具有的复杂结构，在寻优搜索过程中，对一群用编码表示的个体进行简单的操作算子，如交叉算子（Crossover）、重组算子（Re-combination）、变异算子（Mutation）而繁殖出子代（OffSprings），然后对子代进行性能评价（Evaluation），由选择算子（Selection）挑选出下一代的父代（Parents）。在初始化参数后，进化计算能够在进化算子的作用下进行自适应调整，并采用优胜劣汰的竞争机制来指导对问题空间的搜索，最终达到最优值。进化计算的算法流程如图2-1所示。
图2-1 进化计算的算法流程
通过进化计算流程可知，实现进化计算需要完成以下几个关键步骤：
① 原问题中的解需要用编码表示；
② 设置初始参数，定义环境选择机制，定义技术参数、如变异概率、种群大小；
③ 产生若干个体；
④ 定义适应度函数，评价每个个体的性能；
⑤ 定义交叉算子、重组算子和变异算子；
⑥ 定义选择算子；
⑦ 找出当代最优解。
进化计算具有以下优点。
① 渐进式寻优。它和传统的方法有很大的不同，它不要求所研究的问题是连续、可导的；进化计算从随机产生的初始可行解出发，一代一代地反复迭代，使新一代的结果优越于上一代，逐渐得出最优的结果，这是一个逐渐寻优的过程，但是却可以很快得出所要求的最优解。
② 体现“适者生存，劣者消亡”的自然选择规律。进化计算在搜索过程中，借助进化算子操作，无须添加任何额外的作用，就能使群体的品质不断得到改进，具有自动适应环境的能力。
③ 有指导的随机搜索。既不是盲目式的乱搜索，也不是穷举式的全面搜索，而是一种有指导的随机搜索。指导进化计算执行搜索的依据是适应度，也就是它的目标函数。在适应度的驱动下，使进化计算逐步逼近目标值。
④ 并行式搜索。进化计算每一代运算都针对一组个体同时进行，而不是只对单个个体。因此，进化计算是一种多点齐头并进的并行算法，这大大提高了进化计算的搜索速度。并行式计算是进化计算的一个重要特征。
⑤ 直接表达问题的解，结构简单。进化计算根据所解决问题的特性，用字符串表达问题及选择适应度，一旦完成这两项工作，其余的操作都可按固定方式进行。
⑥ 黑箱式结构。进化计算只研究输入与输出的关系，并不深究造成这种关系的原因，具有黑箱式结构。个体的字符串表达如同输入，适应度计算如同输出。因此，从某种意义上讲，进化计算是一种只考虑输入与输出关系的黑箱问题，便于处理因果关系不明确的问题。
⑦ 全局最优解。进化计算由于采用多点并行搜索，而且每次迭代借助交换和突变产生新个体，不断扩大搜索范围，因此进化计算很容易搜索出全局最优解而不是局部最优解。
⑧ 通用性强。传统的优化算法，需要将所解决的问题用数学式表示，而且要求该函数的一阶导数或二阶导数存在。采用进化计算，只用某种字符表达问题，然后根据适应度区分个体优劣。其余的交叉、变异、重组、选择等操作都是统一的，由计算机自动执行。因此有人称进化计算是一种框架式算法，它只有一些简单的原则要求，在实施过程中，无须额外的干预。
进化计算基于其发展历史，有4个重要的分支：遗传算法（Genetic Algorithms，GA），进化规划（Evolution Programming，EP），进化策略（Evolution Strategy，ES）和差分进化（Differential Evolution，DE）。
遗传算法最初的发展是在美国，1975年，Holland教授出版了《自然系统和人工系统的自适应性》一书，对生物的自然遗传现象与人工自适应系统行为之间的相似性进行探讨，提出模拟生物自然遗传的基本原理，借鉴生物自然遗传的基本方法研究和设计人工自适应系统。遗传算法在20世纪80年代以后被广泛研究和应用，取得了丰硕的成果，并且在实际应用中得到了很大的完善和发展。
L.J. Fogel最早提出进化规划算法，在1966年L.J. Fogel出版了《基于模拟进化的人工智能》一书，阐述了进化规划算法的基本思想。但是当时这一技术未能得到广泛接受，直到20世纪90年代，才逐步被认可，并在一定范围内开始解决一些实际问题。D.B.Fogel将进化规划思想拓展到实数空间，使其能够用来求解实数空间中的优化计算问题，并在变异运算中引入正态分布技术，从而使进化规划成为一种优化搜索算法，并作为进化计算的一个分支在实际领域中得到了广泛的应用。进化规划可应用于求解组合优化问题和复杂的非线性优化问题，它只要求所求问题是可计算的，使用范围比较广。
进化策略是独立于遗传算法和进化规划外，在欧洲独立发展起来的。1963年，德国柏林技术大学的两名学生I.Reehenberg和H.P.Schwefel进行风洞实验时，由于设计中描述物体形状的参数难以用传统的方法进行优化，因此提出按照自然突变和自然选择的生物进化思想，对物体的外形参数进行随机变化并尝试其效果，获得了良好的效果。随后，他们便对这种方法进行了深入的研究和发展，形成了进化计算的另一个分支——进化策略。进化策略的思想便由此诞生。
差分进化算法是由Rainer Storn和Kenneth Price为求解切比雪夫多项式而于1996年共同提出的一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法。差分进化的原理简单，受控参数少，实施随机、并行、直接的全局搜索，易于理解和实现。差分进化已成为一种求解非线性、不可微、多极值和高维复杂函数的一种有效和鲁棒的方法，引起了人们的广泛关注，在国外的各研究领域得到了广泛的应用，已成为进化计算的一个重要分支。
进化计算的各种实现方法是相对独立提出的，相互之间有一定的区别，各自的侧重点不尽相同，生物进化背景也不同，虽然各自强调了生物进化过程的不同特性，但本质上都是基于进化思想的，都是较强的计算机算法，适应面比较广，因此统称为进化计算。近年来，进化计算已经在最优化、机器学习和并行处理等领域得到越来越广泛的应用。