演化计算

随机搜索技术和方法

演化计算是模拟自然界中的生物的演化过程产生的一种群体导向的随机搜索技术和方法。

由来

达尔文的自然选择学说构成了现代进化论的主体。生物在延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种现象成为演化。生物演化是以集团的形式进行的，这样的团体称为群体，组成群体的单个生物称为个体，个体间的差别使得他们对环境的适应程度不同。达尔文的自然选择学说认为，不同个体间的交配以及其他一些原因，生物的基因可能发生变异形成新的基因，这部分变异将遗传到下一代。这种变异的概率非常之低，使得种群得以保持自己的特征。但是新的基因依据与环境的适应程度决定其繁殖能力，利于环境的基因逐渐增多，从而产生优良物种。

大自然是人类灵感的源泉。我们知道，自然界解决问题的方法是漫长的自适应过程，这个过程称之为演化过程，除了演化的最终结果，我们也可以运用这一过程本身去解决问题，将生物界所提供的解决问题的方法应用到求解实际问题已被证明是个成功的方法，并由此产生了仿生学。于是，我们可以不明确的描述出问题的全部特征，只需要根据自然法则产生新的解，决定是更新还是淘汰。

它遵循自然界中生物进化的优胜劣汰原则。演化计算用简单的编码表示各种复杂的结构，通过对编码进行简单的遗传操作和优胜劣汰的竞争机制来对问题的解空间进行搜索。演化算法不用明确的了解问题的全部特征，就可以通过体现生物进化机制的演化过程来完成问题的求解。

发展现状

演化算法在20世纪60年代被提出时并未受到普遍重视，主要原因有三点，一是这些方法当时并不成熟；二是这些方法运行需要较大的计算量，当时计算机速度跟不上要求；三是当时解决类似难题人工智能方法可以得出很好的结果，人们难以过多的关注其他算法。

传统人工智能解决问题的局限性在20世纪80年代初被凸显出来，当时计算机速度已经明显提高并且普及，制约演化计算的一大瓶颈已经不复存在。演化计算在机器学习，工程优化，过程控制等领域取得极大地成功，这引起了包括数学，物理学在内的各个学科及工程应用领域专家的兴趣。

某些学者研究了演化计算的灵现行为(Emergent Behavior)后声称,演化计算与混沌理论、分形几何将成为人们研究非线性现象和复杂系统的新的三大方法,并将与神经网络一起成为人们研究认知过程的重要工具。

自20世纪80年代中期以来，世界上许多国家都掀起了演化计算的研究热潮。目前，以演化计算为主题的国际会议在世界各地定期召开，如IEEE。随着演化计算的广泛应用，一些杂志都设置专栏介绍这方面的文章，现在还出版了两种关于演化计算的影响力较大的新杂志《Evolutionary Computation》和《IEEE Transactionson Evolutionary Computation》。

演化计算是一种通用的问题求解方法,具有自组织、自适应、自学习性和本质并行性等特点,不受搜索空间限制性条件的约束,也不需要其它辅助信息。因此,演化算法简单、通用、易操作、能获得较高的效率,越来越受到人们的青睐。演化计算在大型优化问题求解、机器学习、自适应控制、人工生命、神经网络、经济预测等领域取得的成功，引起了包括数学、物理学、化学、生物学、计算机科学、社会科学、经济学及工程应用等领域科学们的极大兴趣。

现在，演化计算的研究内容十分广泛，例如演化计算的设计与分析、演化计算的理论基础以及在各个领域中的应用等。随着演化计算的理论研究的不断深入和应用领域的不断扩展，演化计算将会取得很大的成功，必将在当今社会占据更重要的位置。

分支

自计算机出现以来,生物模拟便成为计算机科学领域的一个组成部分。其目的之一是试图建立一种人工的模拟环境,在这个环境中使用计算机进行仿真,以便能够更好地了解人类自己以及人类的生存空间;另一个目的则是从研究生物系统出发,探索产生基本认知行为的微观机理,然后设计具有生物智能的机器或模拟系统,来解决复杂问题。如,神经网络、细胞自动机和演化计算都是从不同角度对生物系统进行模拟而发展起来的研究方向。演化计算最初具有三大分支:遗传算法(GeneticAlgorithm，GA)、演化规划(EvolutionaryProgramming、EP)和演化策略(EvolutionStrategy，ES)。上世纪90年代初,在遗传算法的基础上又形成了一个新的分支:遗传程序设计(GeneticProgramming，GP)。虽然这几个分支在算法实现上有一些细微差别,但是它们都有一个共同的特点,即都是借助生物演化的思想及原理来解决实际问题的。

（1）遗传算法

上世纪50年代末人们尝试把计算机科学与进化论结合起来，但由于缺乏一种通用的编码方案，人们只能依赖变异而非交配来产生新的基因结构，加上当时只有少数计算机可以满足运算速度的要求，故而收效甚微。到60年代中期,美国Michigan大学的JohnHolland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码技术不但适于变异操作。而已同样适于交配(即杂交)操作。并且强调将交配作为主要的遗传操作。遗传算法的通用编码技术和简单有效的遗传操作意义重大，并为其广泛、成功的应用奠定了坚实的基础。Holland遗传算法被称为简单遗传算法(SGA)。其操作对象是一群二进制串(称为染色体、个体)。在解决实际问题中，每个染色体都对应问题的一个可行解。从初始种群出发，使用杂交和变异来产生下一代种群。如此一代代进行演化。直到达到设定好的终止条件。需要指出的是：目前的遗传算法已不再仅仅局限于二进制编码。

(2) 演化策略

上世纪60年代初，柏林工业大学的学生I.Rechenberg和H.P.Schwefel在进行风洞实验时，由于用传统的方法难以对设计中描述物体形状的参数进行优化。因而利用生物遗传和变异的思想来改变参数值，并获得了较好的效果。随后，他们对这种方法进行了深入的研究和探索。形成了演化计算的另一个重要分支——演化策略。

(3)演化规划

演化规划的方法最初是由L.J.Fogel等提出在上世纪60年代。他们在研究人工智能的时候发现，智能行为就是具有感应其所处环境的状态、并按给定目标自动做出适当响应的能力。在研究中，他们将模拟环境描述成由有限字符集中的符号组成的序列。于是问题就被转化为，如何根据当前观察到的符号序列做出响应，以获得最大收益。这里，收益主要由环境中将要出现的下一个符号及预先定义好的效益目标来确定。他们将此方法应用到数据诊断、模式识别和分类及控制系统的设计等问题中，取得了较好的结果。

(4)遗传程序设计

自计算机出现以来，计算机科学的一个方向性目标就是让计算机自主进行程序设计，即只要告诉计算机要解决的问题，而不需要告诉它具体如何去做。遗传程序设计便是在该领域的一种尝试。它采用演化算法中遗传算法的基本思想，但使用一种更为灵活的表示方式——使用分层结构来表示解空间。这些分层结构有叶节点和中间节点，叶结点是所需解决问题的原始变量，中间结点则是组合这些原始变量的函数。这样，每个分层结构对应问题的一个可行解。遗传程序设计就是使用一些遗传操作动态地改变这些结构，以获得解决该问题的可行的计算机程序。遗传程序设计的思想是Stanford大学的J.R.Koza在上世纪90年代初提出的。

主要特点

演化计算最主要的特点体现在以下两个方面:

(1)自组织、自适应和自学习性(智能性)

演化计算在求解问题时,在编码方案、适应值函数及遗传算子确定后,将利用演化过程中获得的信息进行自行组织搜索，即演化算法的自组织性。演化计算基于自然的选择策略:适者生存、不适应者淘汰,适应值大的个体比适值小的个体具有较高的生存概率。根据自然法则，适应值大的个体具有更加适应环境的基因结构,适值大的个体通过杂交等遗传操作,就可能产生比上一代更适应环境的后代。这就是演化算法的自组织、自适应特征。

此外，算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法。

自然选择不需要事先明确描述问题的全部特点, 只需要根据自然法则产生新的解，决定是更新还是淘汰。我们可以利用演化计算的这个特点解决那些结构尚无人能理解的复杂问题。

(2)本质并行性

演化计算的本质并行性表现在内在并行性和内含并行性两个方面。演化计算的内在并行性(inherent parallelism),即演化算法本身非常适合大规模并行。最简单的并行方式是让几百甚至更多台计算机各自进行独立种群的演化计算,运行过程中不进行任何通信或者有少量通讯,等到运算结束时比较,选取最佳个体。由于这种并行处理方式对并行系统结构没有什么限制和要求,演化计算适合在目前所有的并行机上进行并行处理,而且对并行效率没有影响很小。演化计算的内含并行性(implicitparallelism)。因为演化计算采用种群的方式组织搜索,所以算法可同时搜索解空间内的多个区域,并互相交流信息。

研究领域

演化计算主要的经过长时间的发展，主要出现了以下几个研究领域：

(1)演化计算的理论研究；

(2)新的计算模型；

(3)演化优化；

(4)演化人工神经网络；

(5)并行和分布式演化计算；

(6)演化机器学习；

(7)演化计算应用系统；

(8)演化硬件；

(9)演化软件；

(10)演化计算内涵的扩充

相关资料

EA_demo，英国格拉斯哥大学1997年出版，至今仍广泛使用，采用大学包括英国利物浦（Liverpool）大学、苏塞克斯（Sussex）大学、北安普顿（Northampton）大学，德国乌尔姆（Ulm）大学，瑞士日内瓦（Geneva）大学，西班牙格林纳达（Granada）大学，葡萄牙新里斯本（Nova de Lisboa）大学，美国加州大学戴维斯分校（UC Davies），加拿大卡尔加里（Calgary）大学，澳大利亚墨尔本皇家理工大学（RMIT），新加坡国立大学，台湾清华大学，上海交通大学，巴西PUCRS大学等。

EA_demo允许用户直接在网页上一代一代地手动运行，以看遗传/进化算法是怎样一步一步操作的，亦可在背景中批次运行，以观察算法的收敛和染色体是否跳出局部最优。用户可以改变终止代数，群体规模，交配率，变异率和选择机制。但随着web技术发展和手机浏览器的发展，2015-2017年多数浏览器客户端已经不支持java插件。不过对于学习者来说，幸运的是，2019年IE浏览器仍支持java插件，故对于EA_demo可以通过网站提示，快速体验该应用。另，其上级页面有很多自学资料，对于初学者来说，可以从中得到很大的收益。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省