演化计算

来自集智百科
跳转到: 导航搜索

演化计算(Evolutionary Computation)是一系列算法的总称,这些算法往往是科学家们在受到生物演化的启发之后而开发出来的一些算法,包括遗传算法(Genetic Algorithm)、蚁群算法(Ant Colony Algorithm)等等。演化计算属于人工智能(Artificial Intelligence)或软计算(Soft Computing)的一个分支。

在通常情况下,演化计算都涉及到基于种群(Population)的试错探索和开发利用的(Trial and Exploit)过程。首先,我们需要创造一组基本单元以构成种群,这些单元可以是二进制串(如遗传算法),也可以是简单程序(如遗传编程Genetic Programming),或者是智能主体(如蚁群算法),然后让这些单元去探测环境,之后根据探测的误差从而强化或淘汰一些个体,从而优化整个种群。种群优化的过程通常需要利用一些随机化的手段来完成。

由于演化计算的灵活性和适应性,人们通常可以用它来解决一些科学或工程中的优化问题,特别是针对那些很难给出梯度信息,无法用经典的优化方法来解决的困难问题,演化算法具有一定的优势。

在复杂系统中,由于很多系统中的个体都具备自适应性,可以动态地从环境中学习。因此,我们可以利用演化计算的方法来对每一个主体进行建模,从而让这群主体在系统中进行相互适应,完成学习。这种研究范式就是John Holland(遗传算法之父)所倡导的复杂适应系统研究。

研究历史

用演化的思想来进行问题求解可以追溯到1950年代。而到了60年代,演化计算的思想在三个不同地方同时出现,并沿着不同的轨迹发展。这包括Lawrence J. Fogel提出的演化规划、John Henry Holland提出的遗传算法、以及德国人Ingo Rechenberg和Hans-Paul Schwefel提出来的演化策略。这些想法独立演化了15年,到了90年代才开始对话和融合,最终形成了演化计算这个分支。后来在这个流派的基础上又衍生出了遗传编程,以及包括蚁群算法、粒子群优化算法等受到自然启发的一系列算法。

20世纪80年代以来,随着传统的基于知识和搜索的人工智能进入瓶颈阶段,演化计算由于其灵活的自学习特性开始变得流行起来。以演化计算为主题的国际会议在世界各地定期召开,如IEEE。随着演化计算的广泛应用,一些杂志都设置专栏介绍这方面的文章。一些新杂志,如《Evolutionary Computation》和《IEEE Transactionson Evolutionary Computation》也陆续诞生。

与此同时,学者们开始利用演化计算的方法模拟复杂系统中的涌现行为(Emergent Behavior)。Christopher Langton率先提出了“人工生命”的研究方向。圣塔菲研究所(Santa Fe Institute)大力支持这个研究方向,并在John Holland的带领下提出了系统性的复杂适应系统思想和基于智能主体的复杂系统建模方法(Agent Based Modelling)。

利用演化计算的方法研究社会科学问题兴起于20世纪80年代。Robert Axelrod等人率先将演化计算的方法引入了社会学的研究中,他利用遗传算法制造了虚拟的多主体种群,并让它们玩囚徒困境博弈,从而研究什么样的策略可以导致主体之间的合作行为。Axelrod的研究开辟了演化计算应用社会经济系统的先河。到了90年代以及2000早期,一些学者利用演化计算的方法应用于模拟经济系统中主体的学习行为,并与真实的人类被试行为进行对比试验。

演化计算也被人们广泛地应用设计领域中。交互式遗传算法就是一种重要的应用方法之一。它通过巧妙地结合人类的选择行为和计算机在随机生成备选方案的特性可以完成计算机辅助设计的过程。现在,演化计算已经在机械设计、土木工程、智能控制、优化求解等问题中得到了广泛的应用。随着演化计算的理论研究的不断深入和应用领域的不断扩展,演化计算将会取得很大的成功,必将在当今社会占据更重要的位置。

参考文献

  • Th. Bäck, D.B. Fogel, and Z. Michalewicz (Editors), Handbook of Evolutionary Computation, 1997, ISBN 0750303921
  • Th. Bäck and H.-P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1–23, 1993.
  • W. Banzhaf, P. Nordin, R.E. Keller, and F.D. Francone. Genetic Programming — An Introduction. Morgan Kaufmann, 1998.
  • D. E. Goldberg. Genetic algorithms in search, optimization and machine learning. Addison Wesley, 1989.
  • J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
  • J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Evolution. MIT Press, Massachusetts, 1992.
  • Z. Michalewicz, Genetic Algorithms + Data Structures – Evolution Programs, 1996, Springer, ISBN 3540606769
  • D. Simon. Evolutionary Optimization Algorithms. Wiley, 2013.
个人工具
名字空间
操作
导航
工具箱