进化计算

在计算机科学中，进化计算是受生物进化启发的用于全局优化的一系列算法，以及研究这些算法的人工智能和软计算的子领域。在技​​术方面，它们是具有元启发式或随机优化特征的基于群体的试错问题求解器家族。

在进化计算中，生成并迭代更新一组初始候选解。每一代都是通过随机删除不太想要的解决方案并引入小的随机变化来产生的。在生物术语中，人口的解决方案进行自然选择（或人工选择）和突变。结果，种群将逐渐演化以增加适应度，在这种情况下是算法选择的适应度函数。

进化计算技术可以在广泛的问题设置中产生高度优化的解决方案，使它们在计算机科学中很受欢迎。存在许多变体和扩展，适用于更具体的问题和数据结构系列。进化计算有时也用于进化生物学，作为一种计算机实验程序来研究一般进化过程的共同方面。

进化编程是由美国的LawrenceJ.Fogel引入的，而JohnHenryHolland将他的方法称为遗传算法。在德国IngoRechenberg和Hans-PaulSchwefel介绍了进化策略。这些领域分别发展了大约15年。从九十年代初开始，它们被统一为一种技术的不同代表（“方言”），称为进化计算。同样在90年代初期，出现了遵循一般思想的第四个流——基因编程.自1990年代以来，受自然启发的算法正成为进化计算中越来越重要的一部分。

这些术语表示进化计算领域，并将进化编程、进化策略、遗传算法和遗传编程视为子领域。

NilsAallBarricelli于1953年使用进化算法和人工生命技术对进化进行了最早的计算模拟，于1954年发表了xxx批结果。1950年代的另一位先驱是AlexFraser，他发表了一系列论文关于人工选择的模拟。由于IngoRechenberg在1960年代和1970年代初期的工作，人工进化成为一种广泛认可的优化方法，他使用进化策略来解决复杂的工程问题。遗传算法特别流行于约翰·霍兰德(JohnHolland)的著作。随着学术兴趣的增长，计算机能力的急剧增加允许实际应用，包括计算机程序的自动进化。进化算法现在比人类设计师制作的软件更有效地解决多维问题，也用于优化系统设计。

进化算法形成进化计算的一个子集，因为它们通常只涉及实现受生物进化启发的机制的技术，例如繁殖、突变、重组、自然选择和适者生存。优化问题的候选解决方案在群体中扮演个体的角色，成本函数决定了解决方案“生存”的环境（另见适应度函数）。在重复应用上述算子之后，种群的进化就会发生。

在这个过程中，有两种主要力量构成了进化系统的基础：重组突变和交叉创造了必要的多样性，从而促进了新颖性，而选择则是一种提高质量的力量。

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

遗传算法提供了建模生物系统和系统生物学的方法，这些方法与动态系统理论相关，因为它们用于预测系统的未来状态。这只是一种生动（但可能具有误导性）的方式来引起人们对生物学发展的有序、良好控制和高度结构化特征的关注。

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

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

此外，遵循计算理论的概念，生物有机体中的微观过程从根本上是不完整和不可判定的（完整性（逻辑）），这意味着“细胞和计算机之间的类比背后不仅仅是一个粗略的比喻。

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

进化自动机是进化图灵机的概括，已被引入以更精确地研究生物和进化计算的特性。特别是，它们允许在进化计算的表达能力上获得新的结果。这证实了关于自然进化和进化算法和过程的不可判定性的初步结果。进化有限自动机，在终端模式下工作的进化自动机的最简单子类可以接受给定字母表上的任意语言，包括非递归可枚举（例如，对角化语言）和递归可枚举但不能递归的语言（例如，通用图灵机的语言）。