演化计算

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索


在计算机科学中， 演化计算 Evolutionary computation，又称进化计算，是一个受生物演化启发的全局优化算法家族，这些算法的研究属于人工智能和软计算的子领域。在技术术语上，它们是一类基于群体的试错型问题求解器，具有元启发式或随机优化特性。


在演化计算中，一个初始的候选解决方案集被生成并迭代更新。每一代都是通过随机去除不太理想的解法，引入小的随机变化而产生的。在生物学术语中，一个解决方案的群体会经历自然选择(或人工选择)和突变。因此，种群会逐渐演化，其适应度不断提高，在这个语境中所谓适应度就是算法选择的目标函数。


演化计算技术可以应用在在诸多问题领域中，并产生高度优化的解决方案，这使其在计算机科学中广受欢迎。演化计算存在许多变体和扩展，能适用于更具体的问题和数据结构。演化计算有时也被用在演化生物学中，作为一种电子实验程序来研究一般演化过程的共性特点。


历史

使用演化原理来进行自动化问题求解 automated problem solving起源于20世纪50年代。直到20世纪60年代，才在三个不同的地方形成了对这一观点的三种不同的解释。

演化程序设计 Evolutionary programming是由美国的 Lawrence J. Foge提出的，而约翰·霍兰德 John H Holland称他的方法为遗传算法。在德国，Ingo Rechenberg 和 Hans-Paul Schwefel 引入了演化策略 evolution strategies。这些领域分别独立地发展了大约15年。从九十年代早期开始，它们被统一为一种被称为演化计算的技术的不同表示(类似“方言”)。也是在九十年代初期，出现了继一般思想之后的第四种思潮——遗传程序设计 genetic programming。自20世纪90年代以来，以自然为灵感的算法正在成为演化计算日益重要的一部分。

这些术语表示演化计算领域，并将演化程序设计、演化策略、遗传算法和遗传程序设计作为子领域。

利用演化算法和人工生命模拟进化始于20世纪60年代 Nils Aall Barricelli的工作，后来被Alex Fraser扩展，他发表了一系列关于人工选择模拟的论文[1] 。20世纪60年代和70年代早期，Ingo Rechenberg 使用演化策略解决复杂的工程问题，人工演化因此成为被广泛认可的优化方法。尤其是遗传算法，因为约翰·霍兰德的著作而变得流行起来[2]。学术界兴趣增长的同时，计算机能力的急剧增长使得这种算法可以被实际应用起来，其中包括计算机程序的自动演化。[3] 演化算法现在被用来解决多维度问题，且比人类设计者生产的软件更有效，同时还可以优化系统的设计。 [4][5]

技术

演化计算技术主要涉及元启发式优化算法。一般来说，这个领域包括:


  • 蚁群优化算法
  • 人工免疫系统 Artificial immune systems
  • 人工生命 (also see digital organism)
  • 文化算法 Cultural algorithms
  • 差分演化 Differential evolution
  • 双相演化Dual-phase evolution]
  • 分布算法估计 Estimation of distribution algorithms
  • 演化算法
  • 演化编程 Evolutionary programming
  • 演化策略 Evolution strategy]
  • 基因表达式编程算法 Gene expression programming
  • 遗传算法Genetic algorithm
  • 遗传程序设计 Genetic programming
  • 文法演化 Grammatical evolution
  • 可学习演化模型 Learnable evolution model
  • 学习分类器系统 Learning classifier systems
  • 模因算法 Memetic algorithms
  • 神经演化 Neuroevolution
  • 粒子群优化算法
  • 协作成纤维细胞优化 Synergistic Fibroblast Optimization
  • 自组织
  • 集体智能 Swarm intelligence

演化算法

演化算法是演化计算的一个子集，因为它们通常只涉及实现生物演化机制的技术，如繁殖、变异、重组、自然选择和适者生存。最佳化问题的候选解决方案扮演了人口中个体的角色，而成本函数决定了解决方案“生存”的环境(参见适应度函数)。在重复应用上述算子之后，种群的演化就发生了。

在计算智能 computational intelligence 领域，演化算法（EA）（或称进化算法）是演化计算的子集 ，是一种基于群体的元启发式最优化算法。演化算法使用到了各种模拟生物演化机制的操作，比如繁衍、变异、重组、选择等。在群体中每一个个体都是问题的备选解，而损失函数 cost function（决定了这些个体的生存环境（亦即用于计算个体对于环境的适应度）。演化就是在不断在群体中进行繁衍、变异、重组、选择这些操作进而找出最优解的过程。



在这个过程中，有两种主要的力量构成了演化系统的基础: 重组（Recombination）、突变（mutation）和交换（crossover）创造了必要的多样性，从而促进了新颖性，而选择带来的优胜劣汰则是一种提高质量的力量。


这种演化过程的许多方面都是随机的。由于重组和突变而改变的信息片段是随机选择的。另一方面，选择操作可以是确定性的，也可以是随机的。在后一种情况下，适合度较高的个体比适合度较低的个体有更高的机会被选中，但通常即使是适应度较差的个体也有机会成为父本或生存下来。



演化算法和生物学

遗传算法提供了与动力系统理论相关的生物系统和系统生物学模型的方法，因为它们可以被用来预测系统的未来状态。这是一种生动的(但也许是误导性的)方式，提醒人们注意生物学发展的有序、控制良好和高度结构化的特征。


然而，算法和信息学的使用，特别是计算理论的使用，超越了对动力系统的类比，这也与理解演化本身有关。



这一观点的优点是认识到发育没有中央控制；生物体的发育是细胞内部和细胞之间局部相互作用的结果。在我们看来，关于程序开发并行的最有前途的想法似乎是那些指出细胞内的进程与现代计算机的低级操作之间明显相似的思想。[6] 因此，生物系统就像计算机器，处理输入信息来计算下一个状态。这样看来，生物系统比经典的动力系统更接近于计算。[7]


此外，根据计算理论的概念，生物有机体中的微进程从根本上来说是不完整的和不可判定的 ，这意味着细胞和计算机之间的类比不只仅仅只是一个粗略的比喻。[8]

计算的类比也延伸到遗传系统和生物结构之间的关系，这通常被认为是揭示解释生命起源最紧迫的问题之一。


演化自动机是演化图灵机 图灵机Turing machines的一种推广。人们引入了这一概念来更精确地研究生物和演化计算的性质。特别是，他们在演化计算的表现力上获得新的成果。这证实了关于自然演化和演化算法及过程不可判定性的初步结果。演化有限自动机是演化自动机中最简单的子类，在终端模式下可以接受给定字母表上的任意语言，包括非递归的可枚举语言(例如，对角化语言)和递归的可枚举但不递归语言(例如，通用图灵机语言)。

著名的参与者

活跃的研究人员名单自然是动态的，并非详尽无遗。社区的网络分析在2007年发表。[9]



相关会议

演化计算领域的主要会议包括


更多

  • Adaptive dimensional search 适应性多维研究
  • Artificial development 人工发展
  • Autoconstructive 自动建设性
  • Developmental biology 发展性生物学
  • Digital organism 数字化器官
  • Estimation of distribution algorithm 分布算法估计
  • Evolutionary robotics 演化机器人
  • Evolved antenna 演化天线* Fitness approximation 适应值近似
  • Fitness function 适应度函数
  • Fitness landscape 适应度景观
  • Genetic operators 遗传操作
  • Grammatical evolution 文法演化
  • Human-based evolutionary computation 人类演化计算
  • Inferential programming 推断程序设计
  • Interactive evolutionary computation 互动演化计算
  • List of digital organism simulators 数字化有机体模拟器表
  • Mutation testing 变异测试
  • No free lunch in search and optimization 研究和优化中的“没有免费午餐”
  • Program synthesis 程序综合
  • Test functions for optimization 优化测试函数
  • Universal Darwinism 普适达尔文主义

外部链接

参考书目

  • Th. Bäck, D.B. Fogel, and Zbigniew Michalewicz (Editors), Handbook of Evolutionary Computation, 1997
  • 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.
  • S. Cagnoni, et al., Real-World Applications of Evolutionary Computing, Springer-Verlag Lecture Notes in Computer Science, Berlin, 2000.
  • R. Chiong, Th. Weise, Zbigniew Michalewicz (Editors), Variants of Evolutionary Algorithms for Real-World Applications, 2012
  • K. A. De Jong, Evolutionary computation: a unified approach. MIT Press, Cambridge MA, 2006
  • A. E. Eiben and M. Schoenauer (2002). "Evolutionary computing". Information Processing Letters. 82: 1–6. doi:10.1016/S0020-0190(02)00204-1.{{cite journal}}: CS1 maint: uses authors parameter (link)
  • A. E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, First edition, 2003,
  • D. B. Fogel. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. IEEE Press, Piscataway, NJ, 1995.
  • L. J. Fogel, A. J. Owens, and M. J. Walsh. 人工智能 through Simulated Evolution. New York: John Wiley, 1966.
  • 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.
  • P. Hingston, L. Barone, and Zbigniew Michalewicz (Editors), Design by Evolution, Natural Computing Series, 2008
  • J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Evolution. MIT Press, Massachusetts, 1992.
  • F.J. Lobo, C.F. Lima, Zbigniew Michalewicz (Editors), Parameter Setting in Evolutionary Algorithms, 2010
  • Zbigniew Michalewicz, Genetic Algorithms + Data Structures – Evolution Programs, 1996
  • Zbigniew Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics,2004
  • I. Rechenberg. Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Stuttgart, 1973. 模板:In lang
  • H.-P. Schwefel. Numerical Optimization of Computer Models. John Wiley & Sons, New-York, 1981. 1995 – 2nd edition.
  • D. Simon. Evolutionary Optimization Algorithms. Wiley, 2013.
  • M. Sipper, W. Fu, K. Ahuja, and J. H. Moore (2018). "Investigating the parameter space of evolutionary algorithms". BioData Mining. 11: 2. doi:10.1186/s13040-018-0164-x. PMC 5816380. PMID 29467825.{{cite journal}}: CS1 maint: uses authors parameter (link)
  • Y. Zhang and S. Li. (2017). "PSA: A novel optimization algorithm based on survival rules of porcellio scaber". arXiv:1709.09840 [cs.NE].{{cite arxiv}}: CS1 maint: uses authors parameter (link)

参考文献

  1. ↑ Fraser AS (1958). "Monte Carlo analyses of genetic models". Nature. 181 (4603): 208–9. Bibcode:1958Natur.181..208F. doi:10.1038/181208a0. PMID 13504138. {{cite journal}}: Invalid |ref=harv (help)
  2. ↑ Holland, John H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 978-0-262-58111-0. https://archive.org/details/adaptationinnatu00holl. 
  3. ↑ Koza, John R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press. ISBN 978-0-262-11170-6. 
  4. ↑ G. C. Onwubolu and B V Babu, Onwubolu, Godfrey C.; Babu, B. V. (2004-01-21). New Optimization Techniques in Engineering. ISBN 9783540201670. https://www.springer.com/in/book/9783540201670. Retrieved 17 September 2016. 
  5. ↑ Jamshidi M (2003). "Tools for intelligent control: fuzzy controllers, neural networks and genetic algorithms". Philosophical Transactions of the Royal Society A. 361 (1809): 1781–808. Bibcode:2003RSPTA.361.1781J. doi:10.1098/rsta.2003.1225. PMID 12952685. {{cite journal}}: Invalid |ref=harv (help)
  6. ↑ "Biological Information". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2016. https://plato.stanford.edu/entries/information-biological/#InfEvo. 
  7. ↑ J.G. Diaz Ochoa (2018). "Elastic Multi-scale Mechanisms: Computation and Biological Evolution". Journal of Molecular Evolution. 86 (1): 47–57. Bibcode:2018JMolE..86...47D. doi:10.1007/s00239-017-9823-7. PMID 29248946. {{cite journal}}: Invalid |ref=harv (help)
  8. ↑ A. Danchin (2008). "Bacteria as computers making computers". FEMS Microbiol. Rev. 33 (1): 3–26. doi:10.1111/j.1574-6976.2008.00137.x. PMC 2704931. PMID 19016882. {{cite journal}}: Invalid |ref=harv (help)
  9. ↑ J.J. Merelo and C. Cotta (2007). "Who is the best connected EC researcher? Centrality analysis of the complex network of authors in evolutionary computation". arXiv:0708.2021 [cs.CY].

集智推荐

文章推荐

人工生命全景图：如何创造出超越人工智能的生命系统

人工生命全景图：如何创造出超越人工智能的生命系统

该文章是对Lana Sinapayen的《Introduction to Artificial Life for People who Like AI》一文进行的总结，主要从研究目标、发展历史、与人工智能的关系等方面对人工生命进行了介绍。


基于垫脚石原理的神经演化算法：为人工智能注入创造力

该文章主要介绍了计算机科学家 Kenneth Stanley提出的基于垫脚石原理的神经演化算法。


课程推荐

颠覆式创新与AI发展前沿追踪

课程简介：本课程主要介绍了当前人工智能在社会领域的应用及优化，包括人工智能在智能零售、机器人、图片超分辨率、机器翻译，以及复杂网络领域的应用。除此之外还介绍了在新时代中，中国创新的的崛起。


时间与进化

课程简介：本课程将站在时间这个角度去从物理学、热力学、生物学的不同领域进行解释和探索，并介绍一些关于遗传算法的相关计算机模拟实例，来帮助我们从多视角看待时间与进化。本课程将站在时间这个角度去从物理学、热力学、生物学的不同领域进行解释和探索，并介绍一些关于遗传算法的相关计算机模拟实例，来帮助我们从多视角看待时间与进化。




本中文词条由Henry、Ricky编译，思无涯咿呀咿呀编辑。欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=演化计算&oldid=21831”