演化计算

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

此词条暂由Henry翻译。

本词条已由Ricky翻译。


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


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


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


历史

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

演化程序设计 Evolutionary programming是由美国的 Lawrence J. Foge提出的,而约翰·霍兰德John Henry 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]




技术

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


自我管理(例如自组织特征映射模型 竞争性学习)

演化算法

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

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



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


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



演化算法和生物学

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


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



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


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

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


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

著名的参与者

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



相关会议

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


更多

外部链接

参考书目