《演化计算》读书报告

《演化计算》读书报告

演化算法是一种模拟生物演化过程与机制

求解优化问题及搜索问题的一类自组织、自

适应人工智能技术。这类技术的核心思想源

于这样的基本知识：生物进化过程本身就是

一个自然的、并行发生的、稳健的优化过

程。这一过程的目标在于使生命体达到适应

环境的最佳结构与效果，生物种群通过“优

胜劣汰”及遗传变异来达到演化的目的。

按照达尔文的自然选择学说和孟德尔的遗

传变异理论，生物演化是通过繁殖、变异、

重组和选择这4种基本形式来实现的。演化

算法就是基于这种思想发展起来的一类随

机搜索技术。它们是模拟由个体组成的群

体的学习过程，其中每个个体表示给定问题

搜索空间的一点。演化算法从一个初始的群

体出发，通过随机选择、变异和重组过程，

使群体演化到搜索空间中越来越好的区域。

选择过程是群体中适应性好的个体比适应

性差的个体有更多的复制机会，交叉算子将

父辈信息结合在一起并将它们遗传到子代

个体，变异保证在群体中产生新的个体。演

化算法这种以生物智能或自然现象为基础

的随机搜索算法具有比数学规划方法更大

的优越性，使得演化算法已经成为人工智能

领域的研究热点。

演化算法的特点

与传统搜索算法相比，演亿计算具有以下不同点：

1)演化计算从多个点而不是i个点开始进行搜索，这是它能以较大的概率找到整体最优

解的原因之一。

2)演化计算只使用效益信息(即目标函数)，并在增加收益和减小开销之间进行权衡，而传统

搜索算法一般要使用导数等其它辅助信息。

3)演化计算所具有的内含并行性使它能以较少的计冕量获得较大的收益。

4)演化计算使用随机的转移规则而不是确定的转移规则。

5)算法不是直接作用在解空间上，而是利用解的编码形式。

演化算法的基本结构

不同的编码方案、选择策略和遗传算子相结合，可构成不同的演化算法，但其基本结构可

描述如下：

PROCEDURE演化计算的基本结构

{

随机初始化种群P(0)={xl,x2,…,xN},t:=O;

计算P(0)中个体的适应值;

While(不满足终止准则)do

(

由P(t)通过遗传操作形成新的种群网计》;

计算P(t+1)中个体的适应值,

}

输出结果;

}

可以看出，上述基本结构是一个比较粗略的框架。在具体实现时，可使用较为详细的结构。如

按种群的组织方式，可分为非重费和重费种群的演化和法，以及单种群和多种群的演化凫法;

按遗传算子的执行方式，可分为非重叠和重叠遗传操作的演化算法等。

演化算法的基本原理

编码表示

设计演化算法的一个重要步骤是，对所解问题的变量进行编码表示，编码表示方案的选

取在很大程度上依赖于问题的性质及遗传算子的设计。通常，在设计演化算法时，只有两个方

面与所求问题有关，即问题的编码表示与适应函数的确定。

根据编码方式的不同，演亿算法的编码策略大致可分为二进制编码、实数编码、有序串

编码与结构性编码等。

确定适应函数

在自然界中，个体的适应值就是其繁殖能力，这将直接关系到其后代的数量。在演化计算

中，适应函数是区分群体中个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯

一依据。改变种群内部结构的操作都通过适应值进行控制。

在演化计算中，度量适应性的方法有很多种，既可以用目标因数的形式给出，也可以用目

标函数变换的方式来定义。在为同演化(coevolution)时，适应值通常由某•对策与群体中相

佐的对策进行抗衡的获利来确定。个体在种群中的存活量和繁殖量也可以作为适应值的一种

度量，这种度量方式常在人工生命的研究中使用。

确定选择策略

选择策略对算法性能有举足轻重的影响作用。不同的选择策略将导致不同的选择压力，

即下一代中父代个体的复制数目的分配关系不同。较大的选择压力使最优个体具有较高的复

制数目，从而使算法收敛速度较快，但也容易出现过早收敛现象。相对地，较小的选择压力一

般能使群体保持足够的多样性，从而增大了算法收敛到全局最优的概率，但算法的收敛速度

一般较慢。

遗传算子的设计

遗传算子的设计是演化计算中最富行特色和创造性的部分,基本的演化算法只使用再生、

杂交和变异三种操作。编码策略的不同造成了遗传操作的多样性。对二进制编码，杂交算子

有点式杂交和均匀杂交方式，且点式杂交算子又分为单点式杂交和多点式杂交。其它编码方

式的杂交算了•和变异算了•更是丰富多彩。

控制参数的选取

在设计演化算法时,一方面，需要针对具体问题选择适当的编码方案及相应的遗传算子；

另一方面,需要选择算法的控制参数。对一个具体问题，要想获得最优的参数设置，通常采取

下述两种方法之一。

⑴试验法该方法是对每个参数在某区间上按一定的间隔取有限个值,然后根据不同的参数

组合执行演化算法，以比较它们的性能，并在其中选择最优的组合。

⑵二级演化算法(meta-EA)这种方法将演化算法控制参数的选取问题也作为一个优化问题，

从而用一个二级演化算法去优化控制参数。

虽然上述两种方法能就某类问题获得较佳的参数设置，但它们的计算量都比较大，因而

在计算实际问题时用得并不是很多。常用的方法是根据经验取定控制参数值,然后多次执行

算法,以获得问题的最优或近似最优解o

算法的改进

基本演化算法源于对生物演化过程的直接模拟，求解问题时，一般需要较大的运算量且

有时收敛不到全局最优解。为了提高算法的效率、改善算法的性能，人们对传统的演化算法

做了诸多改进，如多种群和变种群策略、混合策略、稳态(steadystate)策略等。

演化算法在水利工程中的应用

用于梯级电站和泵站的调度仿真

原文林(2008)【1】探讨了梯级水库联合优化调度的差分演化算法中，针对传统优化算

法在高维梯级水库优化调度时多约束条件难以处理、计算机时长等缺陷，提出了非参数惩罚

的约束条件处理机制，并对差分演化算法进行了改进。通过实际算例验证了该方法的可靠性，

从而为高维梯级水库的优化调度提供了一种新的求解途径。

实际算例的应用情况表明，该算法与DPSA相比较，其优化调度结果合理、有效,并且具

有较高的计算精度与计算效率，从而为多约束、高维梯级水库的联合优化调度提供了一种新

颖、有效的求解方法。

由于泵站和水电站分别可以视为两种相反的水、电能量转换

过程，在实际的生产中，梯级泵站数目比梯级发电水库要多。

因此差分演化算法能够广泛应用于这一领域的调度实际中。

用于水文过程模拟

王丰赞(2008)⑶等将差分演化算法应用于马斯京根模型参数估计,实例仿真结果表明，

该方法精度高、收敛速度快，灯求解实际水文模型参数优选问题非常有效。

王燕飞(2008)[2],将其应用于水文优化适线，结果表明搜索

效率较高。

地基稳定分析

郭涛(2005)[的从演化计算中的遗传算法思想出发，构造了一个寻找最小安全系数的控

制收敛矩阵。由该控制收敛矩阵4个角点的安全系数的大小决定下一个控制收敛矩阵移动

的方向。当该矩阵的安全系数在型心为最小时，运用二分法将控制收敛矩阵尺寸减小一半进

行计算，直到满足要求为止。并结合一个具体的工程,给出了在寻找最小安全系数的过程，验

证了所给方法的可行性。

在水利工程中，地基、边坡稳定研究是一个关乎工程质量、

工程造价需要考虑的重要条件。应用演化计算的遗传算法可

以有效找到地基稳定点，能够有效节省资本和资源。

水质监测

闵涛(2003)等15〕给出了利用演化计算方法求解河流水质多参数反问题的一种新方

法。该方法把参数识别反问题转化为优化问题用演化方法求解,它的特点在于:从多个初始

点开始寻优,并借助交叉和变异算子来获得水质参数的全局最优解。数据模拟结果表明，该方

法具有很高的精度，收敛速度快，旦编程简单，易于计算机实现，值得在实际工作中采用。

演化算法在水利工程的个人想法

(1)应用演化遗传算法可以应用于水库调度。不仅包括发电调度，而且应用于灌溉、防

洪等多方面的调度工作。

应用演化计算确定节水灌溉中各作物各生育期的缺水敏感性分析，进行模拟。

节水灌溉同水文现象都有尺度效应。当前研究中，节水灌溉同水量、水质的变化密切相

关。应用演化算法，结合混沌理论、分形等非线性研究进展，改进演化算法，使其避免陷入

局部最优解的境地。应用于水文尺度效应分析，找到影响环境恶化，水质变化演变的关键点

等。

参考文献

[1]原文林，黄强，万芳，张双虎，刘招，.梯级水库联合优化调度的差分演化算法研究[J].水力发

电学报,2008,⑸.

⑵王燕飞.基于差