进化计算概述

人类从自然中获取灵感解决自身面临的难题,已证明是一条卓有成效的途径。仿生学方法正是在支持人类沿着这条充满挑战但又收获颇丰的路径走下去的重要武器和工具[40]。借助计算机等先进工具,模拟万千生物的特异性形态、功能、结构完成科学研究、生产实践,在信息技术时代的今天更是发挥着难以替代的独特作用。有作者认为,这种模拟有两大作用[6]:试图建立一种人工模拟环境,以便使用计算机进行仿真以更好地了解人类自己和人类的生存空间;另一目的则是从研究生物系统出发,探索产生基本认知行为的微观机理,然后设计成具有生物智能的机器或模拟系统以解决复杂问题。进化计算是这种模拟的一个成功范例。

进化计算最初具有三大分支:遗传算法,进化规划和进化策略。20世纪90年代,在遗传算法的基础上又发展了一个分支:遗传程序设计[6,7]。虽然这几个分支在算法实现方面具有一些细微的差别,但它们具有一个共同的特点,即都是借助生物进化的思想和原理来解决实际问题。许多学者如Michalewicz等认为进化计算的各分支正在互相借鉴,互相融合,已很难决然分开[8]。

2.2.1　进化计算的结构框架

作者认为,进化计算的结构框架可由下图表示:

图2.1　进化计算的结构框架

图2.1表明,进化计算按层次分可分为理论层次、方法层次和应用层次。其中进化计算理论由生物学相关理论(进化论、基因学说、遗传学等)和计算科学(无约束优化理论、约束优化理论、多目标优化理论、并行算法等)构成;方法层次由遗传算法、进化规划、进化策略等具体算法构成,而这些算法的基本成员又是编码、评价、进化算子等;而应用层次则覆盖了进化计算已经以及可能应用的诸多领域。

2.2.2　进化计算的算法描述

1)遗传算法的算法描述

基本遗传算法流程可如图2.2所示,其算法关键在于:适应度评价与适应度函数的选取;复制设计;遗传算子的确立。

图2.2　GA的算法流程图

2)演化策略的算法描述

演化策略有两个基本特征:浮点编码和进化算子中仅有变异算子(原个体加高斯随机干扰)。特征1决定了演化策略的主要应用范围是连续域的参数优化问题;特征2使得变异在算法中的地位至关重要。

目前,变异采用的多为多成员演化策略:(μ＋λ)－ES,(μ,λ)－ES。前者是μ个父代个体产生λ个中间个体,然后在μ＋λ个个体中产生μ个子代个体;后者是μ个父代产生λ(λ＞μ)个个体,然后在λ个个体中产生μ个子代个体。

关于遗传算法与演化策略的比较问题,Michalewicz在文献[8]中给出了详尽的论述。

由于本书的研究过程中并未涉及演化规划、遗传规划,因此关于它们的算法描述这里就不展开了。详细的论述可见文献[7]和[8]。