演化算法完整版本

演化算法理论研究一、研究背景1、引言演化计算采用简单的编码技术来表示各种复杂的结构,并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于它采用种群(即一组表示)的方式组织搜索,这使得它可以同时搜索解空间内的多个区域。而且用种群组织搜索的方式使得演化算法持别适合大规模并行。在赋予演化计算自组织、自适应、自学习等特征的同时,优胜劣汰的自然选择和简单的遗传操作使演化计算具有不受其搜索空间限制性条件(如可微、连续、单峰等)的约束及不需要其它辅助信息(如导数)的特点。这些崭新的特点使得演化算法不仅能获得较高的效率而且具有简单、易于操作和通用的特性,而这些特性正是演化计算越来越受到人们青睐的主要原因之一。2、演化算法的分支演化计算最初具有三大分支:遗传算法（GA）、演化规划（EP）、演化策略（ES）。20世纪90年代初,在遗传算法的基础上又发展了一个分支:遗传程序设计（GP）。虽然这几个分支在算法实现方面具有一些细微的差别,但它们具有一个共同的特点,即都是借助生物演化的思想和原理来解决实际问题。2.1遗传算法把计算机科学与进化论结合起来的尝试开始于20世纪50年代末,但由于缺乏一种通用的编码方案,使得人们只能依赖变异而不是交配来产生新的基因结构,故而收效甚微。到20世纪60年代中期,美国Michigan大学的JohnHolland在Fraser和Bremermann等人工作的基础上提出了位串编码技术,这种编码既适合于变异又适合交配操作,并且他强调将交配作为主要的遗传操作。随后,J.Holland将该算法用于自然和人工系统的自适应行为的研究之中,并于1975年出版其开创性的著作《AdaptationinNaturalandArtificialSystems》。后来JHolland与他的学生们将该算法加以推广并应用到优化及机器学习等问题之中,而且正式定名为遗传算法。遗传算法的通用编码技术及简单有效的遗传操作为其广泛的应用和成功奠定了基础。2.2演化策略在20世纪60年代初,当时在柏林工业大学的I.Rechenberg和H.P.Schwfel等在进行风洞实验时,由于在设计中描述物体形状的参数难以用传统的方法进行优化,从而他们利用生物变异的思想来随机地改变参数值并获得了较好的结果。随后,他们便对这种方法进行了深入的研究和发展,形成了演化计算的另一个分支——演化策略。2.3演化规划演化规划的方法最初是由LJ.Fogel等在20世纪60年代提出的。他们在人工智能的研究中发现,智能行为即是要具有能预测其所处环境的状态,并按照给定的目标作出适当响应的能力。在研究中,他们将模拟环境描述成是由有限字符集中的符号组成的序列。于是问题便转化为:怎样根据当前观察到的符号序列作出响应以获得最大的收益,这里收益的计算是按照环境中将要出现的下一个符号及预先定义好的效益目标来确定的。演化规划中常用有限态自动机(简称FSM)来表示这样的策略。这样,问题便成为:如何设计出一个有效的FSM?LJ.Fogel等借用演化的思想对一群FSM进行演化以获得较好的FSM。他们将此方法应用到数据诊断、模式识别和分类以及控制系统的设计等问题之中,并取得了较好的结果。后来,D.B.Fogel借助于演化策略方法对演化规划进行了发展,并用到数值优化及神经网络的训练等问题之中。2.4遗传程序设计自计算机出现以来,计算机科学的一个重要目标即是让计算机自动进行程序设计,即只要明确地告诉计算机要解决的问题,而不需要告诉它如何去做,遗传程序设计便是在该领域的一种尝试。它采用遗传算法的基本思想,但使用一种更为灵活的表示方式——分层结构来表示解空间。这些分层结构的叶结点是问题的原始变量,个间结点则是组合这些原始变量的函数。它们很类似于LISP语言中的S—表达式。这样的每一个分层结构对应问题的一个解,也可以理解为求解该问题的一个计算机程序。遗传程序设计即是使用一些遗传操作动态地改变这些结构以获得解决该问题的可行的计算机程序。遗传程序设计的思想是stanford大学的J.R.Koza在20世纪90年代初提出的。3、演化算法的特点3.1智能性演化计算的智能性包括自组织、自适应和自学习性等。采用演化计算求解问题时,在确定了编码方案、适应值函数及遗传算子以后,算法将利用演化过程中获得的信息自行组织搜索。由于基于自然的选择策略为:适者生存、不适应者淘汰,故而适应值大的个体具有较高生存概率。通常适应值大的个体具有与环境更适应的基因结构,再通过杂交和基因突变等遗传操作就可能产生与环境更适应的后代。演化算法的这种自组织、自适应特征同时也赋予了它具有能根据环境的变化自动发现环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍:即需要事先描述问题的全部特点,并说明针对问题的不同特点算法应采取的措施。于是,利用演化计算的方法我们可以解决那些结构尚无人能理解的复杂问题。3.2本质并行性演化计算的本质并行性表现在两个方面:一是演化计算是内在并行的,即演化算法本身非常适合大规模并行。最简单的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算,运行过程中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果),等到运算结束时才通信比较,选取最佳个体,这种并行处理方式对并行系统结构也没有什么限制和要求。可以说,演化计算适合在目前所有的并行机或分布式系统上进行并行处理,而且对其并行效率没有太大的影响。二是演化计算的内合并行性。由于演化计算采用种群的方式组织搜索,从而它可以同时搜索解空间内的多个区域,并相互交流信息,这种搜索方式使得它虽然每次只执行与种群规模成比例的计算,而实质上已进行了大约O(N3)次有效搜索。这使得演化计算能以较少的计算获得较大的收益。4、展望随着演化计算研究热潮的兴起,人工智能再次成为人们关注的一个焦点。有些学者甚至提出演化计算是人工智能的未来。目前,演化计算与神经网络、模糊系统一起已形成一个新的研究方向——计算智能。人工智能已从传统的基于符号处理的符号主义向以神经网络为代表的连接主义和以演化计算为代表的演化主义方向发展。由于演化计算在机器学习、过程控制、经济预测、工程优化等领域取得的成功,已引起了包括数学、物理学、化学、生物学、计算机科学、社会科学、经济学及工程应用等领域科学家们的极大兴趣。自80年代中期以来,世界上许多国家都掀起了演化计算的研究热潮。目前,有数种以演化计算为主题的国际会议在世界各地定期召开。国际互联网上也有多种相关的mailing1ist,USENET上还有专门的新闻组。而由于演化计算应用范围之广泛,从一些杂志及国际会议论文集中都比较容易看到有关演化计算应用方面的文章。现在已出版两种专门关于演化计算的新杂志:“EvolutionaryComputation”(由MITPress出版,1993年创刊)和“IEEETransactionsonEvo1utionaryComputation”(IEEE汇刊,1997年创刊),而且一些国际性期刊也竞相出版以演化计算为主题的专刊。甚至新的一轮日本计算机发展规划—RWC计划(RealWorldComputingProgram)也把演化计算作为它的主要支撑技术之一,以进行信息的集成、学习及组织等。另外,某些学者研究了演化计算的自现行为后声称,演化计算将与混沌理论和分形几何一道成为人们研究非线性现象和复杂系统的新的三大方法,并将与神经网络一道成为人们研究认知过程的重要工具。当前,演化计算的研究内容十分广泛,如演化算法的设计与分析、演化计算的理论基础及其在各个领域中的应用等等。可以预料,随着演化计算理论研究的不断深入和应用领域的不断拓广,演化计算必将取得更大的成功。二、演化算法2.1演化算法的基本结构不同的编码方案、选择策略和遗传算子相结合,可构成不同的演化算法,但其基本结构可描述如下:PROCEDURE{随机初始化种群P(0)={X1,X2,…,Xn},t:=0;计算P(0)中个体的适应值;While(不满足终止准则)do{由P(t)通过遗传操作形成新的种群P(t+1);计算P(t+1)中个体的适应值,t=t+1;}输出结果;}可以看出,上述基本结构是一个比较粗略的框架。在具体实现时,可使用较为详细的结构。如按种群的组织方式,可分为非重叠和重叠种群的演化算法,以及单种群和多种群的演化算法;按遗传算子的执行方式,可分为非重叠和重叠遗传操作的演化算法等。下面给个列举：（1）种群非重叠：从P(t)中选择个体进行遗传操作，用后代替换掉整个群体产生新种群P(t+1)。（2）种群重叠：从P(t)中选择N1个个体进行遗传操作，用产生的N1个后代替换掉P(t)中N1个较差的个体，生成新种群P(t+1)。（3）遗传操作非重叠：for(k=0;k<N,k=k+2){在P(t)中选择两个父体;r=random[0,1];if(r≤pr)执行繁殖操作，即将两个父体直接插入到P(t+1);elseif(r≤pr+pc)执行杂交操作，将两个后代插入到P(t+1);else对两个父体分别执行变异操作，将两个后代插入到P(t+1);}（4）遗传操作重叠：for(k=0;k<N,k=k+2){在P(t)中选择两个父体;r=random[0,1];if(r≤pr)执行繁殖操作，并变异后插入到P(t+1);else执行杂交操作，并变异后插入到P(t+1);}2.2设计演化算法的基本步骤在设计演化算法时，通常按以下步骤进行：(1)确定编码方案：用演化算法求解问题时所做的演化操作不是直接作用于问题的解空间上，而是首先将解对应于某种编码表示，操作是在编码空间上进行的。选择何种编码表示有时对算法的性能、效率等产生很大的影响；(2)确定适应度函数：适应值是对解的质量的一种度量，它通常依赖于解的行为与环境（即种群）的关系。一般以目标函数或费用函数的形式来表示。解的适应值是演化过程中进行选择的唯一依据；(3)选择策略的确定：优胜劣汰的选择机制使得适应值大的个体有较高的存活概率，这是演化算法与一般搜索算法的主要区别之一。不同的选择策略对算法的性能也有较大的影响；(4)控制参数的选取：控制参数主要包括种群的规模、算法执行的最大代数、执行不同遗传操作的概率以及其它一些辅助性的控制参数；(5)遗传算子的设计：演化算法中的遗传算子，主要包括繁殖、杂交、变异以及其它高级操作；(6)确定算法的终止准则：由于演化计算没有利用目标函数的梯度等信息，所以在演化过程中，无法确定个体在解空间的位置，从而无法用传统的方法来判定算法的收敛与否以终止算法。常用的办法是预先规定一个最大的演化代数或算法在连续多少代以后解的适应值没有什么明显的改进时即终止；(7)编程上机运行：完成上述工作后,即可按演化计算的算法结构编程,进行问题求解。由于演化算法的随机性及不确定性等特点,通常要多运行几次才能得到可靠的解。应该注意的是,上述基本步骤密切相关,编码方案与遗传算子的设计等是同步考虑的,有时甚至需要上机运行与算法设计交替进行。2.3演化算法的编码表示设计演化算法的一个重要步骤是,对所解问题的变量进行编码表示,编码表示方案的选取在很大程度上依赖于问题的性质及遗传算子的设计。通常,在设计演化算法时,只有两个方面与所求问题有关,即问题的编码表示与适应函数的确定。根据编码方式的不同,演化算法的编码策略大致可分为二进制编码、实数编码、有序串编码与结构性编码等。二进制编码就是将原问题的解空间映射到位串空间Bl={0,1}l上,然后在位串空间上进行遗传操作,结果再通过解码过程还原成其表现型,以进行适应值的评估。当变量不止一个分量时,我们可以对各分量分别进行编码,然后合并成一个长串。解码时,根据其对应的子串分别进行解码即可。采用二进制编码时,一般要先给出求解精度以确定串长。而一旦精度确定后,就很难在算法执行过程中进行调整,因而算法缺乏微调(fine-tuning)的功能。在求解高维优化问题或要求精度很高时,二进制串很长,因而算法的搜索效率很低。基于上述原因,有人提出了Gray编码、动态编码等策略。Gray编码是将二进制编码通过Gray变换后得到的编码,目的是为了减少翻转次数,克服二进制编码的Hamming悬崖(Hammingcliffs)的缺点。动态编码是当算法收敛到某局部最优时,增加搜索的精度。办法是,在保持二进制串长不变的前提下减小搜索区域。为了克服二进制编码的缺点,对于问题的变量是实向量的情况,也可直接采用实进制进行编码。这样,可直接在解的表现型上进行遗传操作,从而便于引入与问题领域相关的启发式信息,以增加演化算法的搜索能力。从演化计算的各分支看,在求解数值优化问题时,演化策略及演化规划都采用实数编码,而且在早期不使用杂交算子(演化策略中现在使用的重组算子非常类似杂交算子)。遗传算法则较多地采用二进制编码。近几年,遗传算法在求解高维或复杂优化问题时也大多使用实数编码。由于实数编码表示比较自然,而且较易引入相关的领域知识,因此,我们认为其使用将越来越广泛。对很多组合优化问题,目标函数的值不仅与表示解的字符串中各字符的值有关,而且与其所在字符串的位置有关,这样的问题称为有序问题。若目标函数的值只与表示解的字符串中各字符的位置有关,与其具体的字符值无关,则称为纯有序问题。对这类问题,较自然的编码表示就是有序串编码。用演化算法求解有序问题时,传统的遗传操作可能产生非法的后代。因此,对这类问题要针对具体问题专门设计有效且能保证后代合法的遗传算子。这类编码方案较多地用在组合优化问题中。对很多问题,更自然的表示是树或图的形式。这时,采用其它形式的编码可能很困难。这种将问题的解表示成树或图的形式的编码称为结构式编码。对这种非线性编码方式,我们应非常谨慎地设计遗传算子,以便不产生或少产生非法的后代。对结构式编码要讨论通用的遗传算子很困难,一般是就具体问题具体分析。因为遗传算子直接在解的表现型上进行操作,所以比较容易加入与领域有关的知识和一些启发式信息。2.4适应函数的确定在自然界中,个体的适应值就是其繁殖能力,这将直接关系到其后代的数量。在演化计算中,适应函数是区分群体中个体好坏的标准,是算法演化过程的驱动力,是进行自然选择的唯一依据。改变种群内部结构的操作都通过适应值进行控制。在演化计算中,度量适应性的方法有很多种,既可以用目标函数的形式给出,也可以用目标函数变换的方式来定义。在协同演化(coevolution)时,适应值通常由某一对策与群体中相佐的对策进行抗衡的获利来确定。个体在种群中的存活量和繁殖量也可以作为适应值的一种度量,这种度量方式常在人工生命的研究中使用。目前,我们在设计演化算法时,群体规模一般在几十到几百之间,与实际物种的规模相差甚远。因此,个体繁殖数量的调节在演化计算中比较重要。如果群体中出现了超级个体,即该个体的适应值大大超过群体的平均适应值,则按适应值比例进行选择时,该个体很快会在群体中占有绝对的比例,从而导致算法较早地收敛到一个局部最优点,这种现象称为过早收敛。又如在搜索过程的后期,虽然群体中存在足够的多样性,但群体的平均适应值可能会接近群体的最优适应值。在这种情况下,群体中实际上已不存在竞争,因而搜索目标难以得到改善,这种现象称为停滞现象。基于上述原因,改变算法性能的方法之一,就是对适应值进行调节,即通过变换来改变原适应值间的比例关系。常用的比例变换有线性变换及指数函数变换等。2.5选择策略选择策略对算法性能有举足轻重的影响作用。不同的选择策略将导致不同的选择压力,即下一代中父代个体的复制数目的分配关系不同。较大的选择压力使最优个体具有较高的复制数目,从而使算法收敛速度较快,但也容易出现过早收敛现象。相对地,较小的选择压力一般能使群体保持足够的多样性,从而增大了算法收敛到全局最优的概率,但算法的收敛速度一般较慢。按选择机制的不同,常用的选择策略可分为基于适应值比例的选择、基于排名的选择和基于局部竞争机制的选择。基于适应值比例的选择包括繁殖池选择、轮盘式选择、Boltzmann选择等。基于排名的选择主要包括基于线性排名和基于非线性排名的选择。基于局部竞争机制的选择主要包括锦标赛选择、(μ,λ)和(μ+λ)选择、Boltzmann锦标赛选择等。2.6遗传算子的设计遗传算子的设计是演化计算中最富有特色和创造性的部分。基本的演化算法只使用再生、杂交和变异三种操作。编码策略的不同造成了遗传操作的多样性。对二进制编码,杂交算子有点式杂交和均匀杂交方式,且点式杂交算子又分为单点式杂交和多点式杂交。其它编码方式的杂交算子和变异算子更是丰富多彩。自然界的遗传操作按操作对象的不同可分为基因级、个体级和群体级三个层次。基本的演化算法所使用的三种操作属于个体级层次的遗传操作。为此,有的研究者便将其它层次的一些遗传操作(称为高级操作)引入到演化算法中。虽然高级操作的引入对演化算法的稳健性有一定改善,但它们增加了额外的计算开销且适应的编码种类较少,而且不少人对采用这些操作能否增强演化算法的计算性能和求解效率持怀疑态度。在演化计算中使用的基因级的高级操作包括:倒位(inversion)、显性基因(dominance)、二倍体(diploidy)、重复(duplication)、缺失(deletion)、易位(