进化算法——昂贵、有噪声与动态适应度函数

1.昂贵适应度函数

在很多实际问题中，对适应度做一次评价会需要几分钟、几小时、几天甚至更长时间的计算或实验。我们在这里讨论如何减少适应度评价所需的时间以便降低进化算法对计算量的要求。

实际问题涉及的适应度函数常常包含下列的一种或多种特征：

做一次适应度函数评价需要数分钟、数小时、数天的时间；
不能以并行的方式评价适应度函数；
适应度函数评价的次数受到时间或其他资源的限制

下面几种方式有助于减少适应度函数评价的计算量。

对以评价过得个体不再计算其费用。
如果个体看起来很好或太差，可以缩短适应度函数评价。
如果需要在大量案例测试中评价费用函数，可以用测试案例的一个子集求近似费用。
如果在计算机上评价适应度函数，可以采用让软件运行加速的标准方法。

（1）适应度函数的近似

我们可以建立适应度函数模型以减少评价适应度函数的工作。即使计算量不是瓶颈，我们也可以使用适应度函数模型来改善进化算法的性能。我们称这样的模型为代理、响应曲面或元模型。用代理这个词是因为可以用适应度模型临时替换精确的适应度评价。用元模型这个词是因为适应度评价本身也是一个近似值。因此，适应度函数模型是对高阶模型的降阶。

假设有一个适应度函数f(x)，我们已经在M个个体 $\left \{ x_{i} \right \}$ 上对它做了评价。可以利用这M个函数值估计搜索空间中任一点的适应度。下图说明适应度估计的基本思路，基于已知的函数值 $f(x_{i})$ 生成一个估计 $\hat{f}(x)$ 。

几乎所有的近似算法都能用于适应度近似。最简单的一个估计算法是将个体的适应度近似为已经评价过得最近邻居的适应度。这个方法被称为适应度模仿，它退化为适应度景观的分段常值近似。

在上图中，当得到新的数据时应该如何更新适应度估计 $\hat{f}(\cdot )$ 。我们希望适应度估计算法是迭代的，当有新的适应度信息时就更新 $\hat{f}(\cdot )$ 。然而，如果适应度景观是动态的，在生成 $\hat{f}(\cdot )$ 的时候估计算法不能完全相信旧的适应度函数。用新的数据更新适应度近似被称为在线代理更新。

适应度近似的另个一方法基于父代的适应度值为子代分配适应度，它被称为适应度继承。我们可以将子代的适应度近似为父代适应度值的平均，或者它与每一个父代的相似程度取加权平均。这个想法可以推广到子代有任意多父代的算法，也可以将这个思路扩展，让子代的适应度近似为整个群众适应度的加权平均，由子代与种群中已被评价过得每一个个体相似的程度来决定权重。还可以采用更高级的适应度继承，比如考虑独立变量和适应度值之间的相关性。特别地，对于多目标问题，适应度继承仅在帕累托前沿连续且为凸的情况下才有效。

a.多项式模型

适应度模仿的分段常值近似是一个好的起点，它告诉我们如何将适应度近似扩展为高阶多项式。例如，可以将适应度近似为线性函数

其中，n是问题的维数，x(k)是个体x的第k个元素。这是多项式模型的一个简单例子，它也被称为响应曲面，通过解下面的问题可以算出a(k)的值：

其中，M是我们已经确切知道适应度值的个体数， $x_{i}$ 是其中第i个个体， $x_{i}(k)$ 是 $x_{i}$ 的第k个元素。欲求出让（2）式最小的（n+1）个参数a(k)，k属于[0,n]，可以用迭代最小二乘法，当得到更多适应度值（M=1,2，以此类推）时更新（2）式的解所需的计算量很少。

我们可以写出一个比（1）式线性模型更精确的模型：

这是一个二次模型，有（n^2+n+1）个参数。此模型关于参数a(k)和a(j，k)仍然是线性的，可以用迭代最小二乘法来求解，只要领会了多项式建模的思想，就可以尝试不同形式的模型，比如：

其中，g(·)和·h(·)可以是任意的线性或非线性函数。

我们也许想用非最小二乘的方法来近似适应度模型，比如，不是通过求解（2）式而是求解下面的问题找出模型：

这里还是（n+1）个参数a(k)上最小化。下图显示了最小化估计误差的平方和与最小最大化估计误差之间的差别。

（2）式的最小二乘准则较好，因为容易用解析方法求解，但最小最大化准则可能更稳健，因为能找出在最坏情况下误差最小的近似。为了在搜索空间的较困难的区域中减小近似误差，最小最大化近似会牺牲掉搜索空间中易于拟合区域的近似误差。

b.计算机实验的设计与分析

计算机实验设计与分析DACE是一个随机的近似方法，它用诊断测试度量近似的好坏。已知n维向量x的M个适应度函数评价 $f(x_{i})$ ，我们假定适应度函数可以近似为

其中， $\mu$ 是一个常数（不一定是适应度函数 $f(x_{i})$ 评价的均值）， $\epsilon (x)$ 是一个修正项。DACE假定,对所有x修正项是 $\epsilon (x)$ 均值为0方差为 $\sigma ^{2}$ 的高斯分布；也就是说，f(x)的概率密度函数为

DACE的另一个重要假设是，对于x的不同值， $\epsilon (x)$ 不独立，即若x的值相似，修正项也应该相似。DACE假定 $f(x_{i})$ 和 $f(x_{j})$ 之间的关系数 $\rho _{ij}$ 可以表示如下：

其中， $x_{i}(k)$ 是第i个候选解的第k个元素， $p_{k}$ ∈[1,2]和 $\theta _{k}\geq 0$ 是参数模型， $d_{ij}$ ＞0是一个距离度量。若 $d_{ij}$ 小， $x_{i}$ 和 $x_{j}$ 的相关性接近1；若 $d_{ij}$ 大， $x_{i}$ 和 $x_{j}$ 的相关性接近0。已知M个适应度函数评价，我们把它们集中写成向量的形式：

其中， $1_{M}$ 是一个列向量，它的每一个元素都是1.注意，我们用符号f(x)表示单个候选解x的适应度，也表示M个元素的向量，它包含 $\left \{ x_{i} \right \}$ 的M个适应度；（9）中M个适应度函数的高斯概率密度哈数为

其中，C是协方差矩阵，方差都为 $\sigma ^{2}$ 的两个随机变量 $f(x_{i})$ 和 $f(x_{j})$ 之间的协方差 $C_{ij}$ 可以表示为如下

因此，（10）式可以写成

其中，R是相关矩阵，R的第i行第j列的元素等于 $\rho _{ij}$ 。

已知一组候选解 $\left \{ x_{i} \right \}$ 和适应度评价f(x)的向量，我们可以找出测量得到的f(x)的值与假定的f(x)的参数形式匹配得最好的 $\mu$ 和 $\sigma$ 的值。已知f(x)的随机性质，（12）式给出f(x)的概率密度函数与得到具体的f(x)的可能性成正比。因此，为找到f(x)的参数形式与f(x)的测量值之间的最好的拟合，我们要找出让（12）式的PDF(f(x))最大的 $\mu$ 和 $\sigma$ 。首先考虑关于 $\mu$ 的偏导数并令它等于0，得到

这里忽略坟墓中的2 $\sigma ^{2}$ ，因为他独立于 $\mu$ ，解（13）式，有

取（12）式关于 $\sigma ^{2}$ 的偏导数，得到

令上面的式子等于0，有

（14）和（16）式给出了用DACE近似适应度函数的 $\mu$ 和 $\sigma$ 的最优值。

现考虑候选解 $\left \{ x_{i} \right \}$ 的M个适应度函数评价f(x)。假设适应度函数相关，如（8）式所示，假设我们得到另一个候选解 $x^{*}$ 的适应度函数评价 $f(x^{*})$ 。将适应度函数向量扩大为（M+1）个元素。

新的相关矩阵为

其中，r是M个适应度函数评价f(x)与新增的适应度函数评价 $f(x^{*})$ 的相关性向量。我们想要关于 $f(x^{*})$ 最大化（12）式的概率密度函数，由此得到最适合新数据 $f(x^{*})$ 的形如（16）式的估计。它被称为极大似然估计。通过最大化

就能最大化（12）式的概率密度函数。用矩阵求逆引理可以证明

将它带入（19）式，有

想要最大化这个关于 $f(x^{*})$ 的表达式，就对 $f(x^{*})$ 求导并置为零，即

求 $f(x^{*})$ ，得到

这个式子告诉我们如何利用已有的模型来近似新的点 $x^{*}$ 的适应度值。推导出近似的均方误差为

我们利用均方误差可以为更多的适应度评价确定合适的采样点。在搜索空间中有两个区域会特别需要更多的适应度评价。首先，在适应度近似的最小值附近采样以期找到优化问题的更好的解。其次，在均方误差大的区域采样，因为这些区域中有很大的不确定性。

选择采样点以提高建模的准确度这种方式被称为主动学习。主动学习通常意味着学习算法中通过采样点来优化某个费用函数。

只要得到新的候选解 $x^{*}$ ，就可以用（23）式计算其适应度近似。

例1，我们用DACE估计二维Branin基准函数

其中，x(1)和x(2)是候选解的两个分量（n=2）。函数的域是x(1)∈[-5,10]，x(2)∈[0.15]。首先要决定用哪些采样点。我们在这里任意选定25个均匀分布于二维搜索域的采样点（M=25）。下面用MATLAB中的fmincon函数关于 $p_{k}$ 和 $\theta _{k}$ 最大化（12）式得到

接下来利用（23）式在细网格上近似f(x)。结果如下图所示，这个近似很好的捕捉了基准函数的基本形状，尤其是多峰的特征。

上例用的是均匀采样，用其他的采样方法得到的结果可能效果会更好。常用的采样方法有Latin超立方采样。此方法在每一维上将域分割为多个区间，然后在每一维的每一个区间中只设置一个采样点。与均匀采样相比，有时候它能捕捉函数无法预知的未知特征。下图说明均匀采样和Latin超立方采样的区别。

（a）显示在搜索域中均匀采样的4个点，（b）显示Latin超立方采样。注意，每一行每一列都只有一个点。Latin超立方采样不唯一。

例2，用Latin超立方采样与DACE估计例1的二维函数。我们任意决定用21个采样点（M=21）。用 MATLAB中的fmincon函数关于 $p_{k}$ 和 $\theta _{k}$ 最大化（12）式得到

接下来利用（23）式在细网格上近似f(x)。结果如下图所示，看起来用Latin超立方采样的结果比均匀采样的好。事实上，例1中用均匀采样的DACE近似的均方误差是24.9，而用Latin超立方采样的均方误差是14.3。即使采样点少，由Latin超立方采样得到的近似误差比均匀采样几乎好50%。可见采样方法会明显影响DACE的近似结果。

（2）近似变换函数

适应度近似方法有时候表现得不好，（23）式的DACE方法需要对矩阵求逆，但矩阵的逆可能不存在。如果逆不存在，可以用伪逆。不过，这里的要点是用来近似适应度函数的基函数可能与适应度函数的形状不太匹配。例如，用傅里叶函数近似一个不规则并带有尖锐边缘的函数，就不能指望在所有的函数域中的所有点上都有好的近似。在这种情况下，可以先对原始的适应度函数做变换，然后找出变换后的函数的近似。例如，我们对M个采样点 $\left \{ x_{i} \right \}$ 评价了它的适应度函数。如果近似效果不好，在变换时可以取适应度函数样本 $f(x_{i})$ 的自然对数：

然后用采样点的 $L(x_{i})$ 找出L(x)的近似，记为 $\hat{L}(x)$ 。然后通过反变换得到原函数的近似：

例3，我们在Goldstein-Price函数上用DACE方法。

其中，x(1)和x(2)的域为[-2,2]。这个函数在它的最小值附近很平坦，在 $x^{*}$ (1)=0和 $x^{*}$ (2)=1处函数达到最小值， $f^{*}$ =3.DACE的近似方法对这个平坦的区域无能为力。

因为在平坦的区域中采样点高度相关，这意味着相关矩阵R中的一些列几乎全部都由1组成，R几乎是奇异的。在本例中我们选用采样点的自然对数，如（29）式所示。函数的形状因此发生了巨大改变；它将靠在一起的较小的f(x)值摊开，将较大的f(x)值聚拢，这样会让相似的函数值分开同时压缩函数的总范围。然后我们用DACE近似L(x)，再计算原始函数的近似，如（30）式所示，凭借对近似过程的简单修改，我们可以得到一个不错的近似，如下图所示。

（3）在进化算法中如何使用适应度近似

这里有几个方案，首先，可以让适应度近似只替换固定比例r的适应度评价。假设适应度函数评价在进化算法的计算量中占据支配地位，这会让计算量从E减少到（1-r）E。但我们不能滥用这个思路，如果用近似替换的适应度评价过多，进化算法的收敛需要更多的时间，这样反而会浪费计算资源。在极端情况下，如果用近似替换所有的适应度评价r=1.此时计算量的确可能近似为0，但进化算法不会收敛到一个有用的结果。

另一个方案是在每一代多生成一些子代并用它们的近似适应度值决定哪些留作下一代。我们称这个想法为进化控制，或模型管理。如果用准确适应度评价某些个体并用近似适应度函数评价其他个体，我们称之为个体进化控制。可以用不同的方法决定哪些个体用准确评价哪些个体用近似评价。比如，对每一个个体随机的决定它的评价方式。也可以在每一代只对近似适应度好的个体用准确适应度评价。用准确适应度评价的个体被称为受控个体。

如果在某些代用准确适应度函数评价所有个体，在另一些代用近似适应度函数评价所有个体，就得到基于代的进化控制。可以用不同的方法决定哪些代用准确评价哪些代用近似函数评价。比如，确定每k代中仅有一代用准确适应度函数评价，这里k是用户自定义的参数。或者，随机的决定在每一代用准确评价或近似评价。也可以一直用近似适应度评价直到检测到收敛（例如，最好的个体在某几代中不再有改善，或者种群的标准差降到某个阈值内），然后用准确适应度函数评价下一代，之后再回到近似适应度评价。用准确适应度评价所有个体的代被称为受控代。

算法1概述了基于动态近似适应度的混合算法（DAFFHEA）。

我们可以尝试算法1的变种，比如 $N_{c}$ 可以不用5N这个值；还可以尝试适应度近似的各种算法；可以尝试不同的方法决定何时生成新的近似。我们可以使用置信域来决定何时生成新的近似。置信域方法以近似适应度值和实际值的对比为基础。如果近似值和实际值接近，就是一个好的近似，因此可以延长生成新的近似的时间间隔。反之，就要缩短生成新的近似的时间间隔。

可对算法1做修改以便只用适应度近似就能决定为下一代保留哪些子代，它被称为知情算子方法。

（4）多重模型

在进化算法的早期的代中可以用近似费用函数评价，在后期的代中做更准确的评价。假设费用函数评价涉及求Riccati方程：

这种类型的方程经常出现在求解控制和估计问题中。已知方阵F，Q和R，以及不一定是方阵的矩阵H。控制或估计算法的性能常常与P的迹成正比。解上述方程很费事，但我们可以用近似方法得到解的估计。在进化算法的早期，用（32）式解做粗略的近似，在后期的代中用更准确的近似。

下图说明这个过程。采用低准确度的适应度模型的进化算法运行 $T_{1}$ 代。在 $T_{1}$ 代之后用所得的种群初始化接下来的进化算法，这个算法用中准确度的适应度模型的进化算法运行 $T_{2}$ 代。在进化算法结束时，用最后的种群初始化最后的进化算法，这个进化算法采用高准确度的适应度模型的进化算法运行 $T_{3}$ 代。

若需要很多准确度水平的模型时，可以将这个放法扩展。用这个方法是要注意，每一个进化算法都需要不同的种群初始化。我们可以采取一些措施，保证每一个种群在它迁移到下一个高水平书适应度函数近似之前能充分地多样化。

多模型优化更紧密的集成方法是用不同水平的适应度函数近似并行的运行进化算法。这个方法中的个体按指定的频率在并行的进化算法之间迁移。这个方法被称为分层进化计算，它包含几种不同的方案。首先，可以让个体从准确度较高的进化算法迁移到准确度较低的进化算法，如下图所示。其次，可以让个体在适应度近似水平差不多的进化算法发之间来回迁移，如下图所示。无所所需的模型准确度水平有多少层都可以用分层进化算法。

使用多重模型的另一个方法是对每一个个体x生成在各种组合中使用的多重模型。例如，假设我们已经评价了M个个体 $\left \{ x_{i} \right \}$ 的适应度。我们可以使用聚类算法将 $\left \{ x_{i} \right \}$ 分为C个簇。然后对C个簇中每一个生成适应度近似模型。由此得到 $\hat{f_{k}}(x)$ ，k∈[1,C]。当我们想近似个体x的适应度时，可以用这几种方法中的一种。比如将f(x)近似为 $\hat{f_{k}}(x)$ ，这里指标k是距x最近的簇。或者，将f(x)近似为 $\hat{f}(x)$ 的加权组合，这里的权重和为1且权重会随着x与每一簇的距离变化。

（5）过拟合

某些适应度近似的方法会遇到过拟合问题。在使用适应度近似时，进化算法的设计者总是小心过拟合的情况。下图为针对一组数据点拟合曲线这一简单问题的过拟合的例子。如图所示，与低阶多项式相比，高阶多项式能更好的与数据匹配，但高阶多项式的推广并不好，它记住了数据点但在数据点之间的性能不好。为了得到更好的推广性能，我们经常允许在数据点处存在较大的拟合误差。

利用集成的技巧可以减轻过拟合的程度。集成是一组单独训练的适应度近似，对于以前在搜索域中从未遇到的点，将集成的适应度近似组合起来估计它们的适应度值。

（6）近似方法的评价

在得到函数近似之后，用它之前需要验证近似能够得到较好的结果。我们往往会从检查采样点（即，用来生成近似的点）的近似值开始。

评估近似方法准确度的一种方法是选出几个采样点，它们没有被用来构造近似。比方说，我们选择另外Q个采样点 $\left \{ x_{i} \right \}$ ，称之为测试点。这里i∈[M+1,M+Q]，然后评价在测试点出的函数和近似，度量均方根RMS近似误差

还可以度量在最坏情况下的近似误差

可以根据优先级和具体问题，选择其中一个估计指标。

另一种方法名为交叉验证或旋转估计，它在评估近似的质量时不需要追加采样点。在交叉验证中，我们使用除第k个点之外的所有采样点计算近似，记为 $\hat{f_{k}}(x)$ 。按这个方式每次略掉一个点，总共会算出M个近似。这M个近似 $\hat{f_{k}}(x)$ ，k∈[1,M]的每一个都用了不同的（M-1）个采样点。与上面一样，我们才用均方误差RMS或最坏情况下的近似误差评价 $\hat{f_{k}}(x)$

由交叉验证让我们确信近似方法正确之后，就使用全部的M个采样点找出将在进化算法中使用的函数近似 $\hat{f}(x)$ 。

如果有足够的资源对近似适应度值和准确适应度值作比较，可以用其他指标来评价适应度近似的质量。这些指标包括：比较用近似适应度值和真实适应度值选出的重组个体的个数；用近似适应度值选错了的个体的排名；真实适应度值和近似适应度值之间的相关性；真实适应度值和近似适应度值之间排名的相关性。

要定义“最好的” 适应度函数近似方法并不容易，除（35）式的均方根和最大误差指标之外，我们还需考虑其他几个准则。

对已知的问题近似方法有多准确？
不管近似方法的准确度如何，在使用近似方法时进化算法的表现如何？
近似方法能减少多少计算量？
近似方法有多复杂？（代码的可维护性、扩展性及移植性）

精英

对于进化算法总是采用精英这一规则来说，昂贵的适应度函数可能会是一个例外。所需要函数评价次数较少的进化算法在无精英时的表现会比有精英时的表现好。这是因为当种群规模较小或者评价次数较少时，探索会比开发更重要。非精英的进化算法允许加大探索力度。

2.动态适应度函数

适应度函数常常随时间变化，也就是说，它们是非稳态的。

动态优化的首要挑战在于检测适应度函数景观的变化。我们可以使用一些标记个体，评价它们在每一代的适应度值来检测景观的变化。如果它们的适应度值从一代到另一代明显改变（超出因噪声而改变的预期），就可以判断适应度景观已经发生两个变化。检测适应度景观不是一个非此即彼的命题，景观可能会在标记位置发生变化而在最优点处未发生变化，也有可能在最优点处发生变化而在标记点处未发生变化。如下图所示。

检测到适应度景观的改变之后，可以用几种方法来跟踪变化后的最优值。一种是用新的随机种群替换全部旧种群并重新开始进化优化过程。如果适应度景观变化很大，大到令先前的种群不再包含新景观的有用信息，这样做可能是适当的。

然而对于大多数问题，旧适应度景观和新景观之间会有某种相似性。也就是说，景观是渐变的不是巨变的。在这种情况下，我们要探索新景观同时也要利用进化算法在旧景观上取得的进展。比如，可以留下大部分旧种群，但在尝试探索新景观时用一些新的个体作为种子。为了增加探索也可以临时提高变异水平。这个方法被称为突变。

下面讨论几种动态进化算法。

（1）预测进化算法

将预测的技巧与进化算法相结合，这就是所谓的进化预测算法。如果正在运行的进化算法可以预测其最优值随时间变化的方式，也许我们就能建立它随时间变化的模型。当检测到景观发生变化时，可以利用模型培育新的成员。这里的关键是最优值必须“以一种可预测的方式”变化。如果不满足这个条件，也可以用随机初始化的种群重新培育整个种群并重新开始进化算法。算法3说明预测进化算法的基本思想，下图是进化算法的最优值动态进化的例子。

算法3在实施上还有几个细节需要设计者来确定。例如，如果在外推之间运行恒定的T代，应该如何确定T的值?如何才能检测到适应度景观的变化？如果使用标记个体，应该用多少个？标记个体太少，检测不到适应度景观的变化，标记个体太多，又可能在适应度函数评价上浪费时间。

应如何用算法3中的集合 $X^{*}$ 来估计新的最优值？也就是说，应该用那种外推算法？如何生成 $\hat{x}^{*}$ 附近的子种群？我们可以简单的将S设置为只有一个元素的集合{ $\hat{x}^{*}$ }。另一种可能是将S设置为 $\hat{x}^{*}$ 的M个变异版本的集合，这里M是由用户定义的参数。还有一个方案是将S设置为围绕 $\hat{x}^{*}$ 的超立方或超球面中的M个个体的确定性的集合。最后我们还得决定在算法3中用S替换旧种群的哪些个体，通常是替换旧种群中最差的个体或替换其中随机选出的个体。

（2）迁入方案

在某些情况下，我们检测不到适应度函数的变化，或者适应度函数几乎在不停地变化。这时可以在种群中不断地加入新个体，从而让进化算法能够稳健应对适应度景观的变化。我们称这种算法为迁入方案。有两个基本的方式。直接迁入方案采用种群中的个体生成新个体。间接迁入方案基于种群的模型生成新个体。

在我们决定使用直接或者间接迁入方案之后，还需要确定下列几项：

如何生成新个体？可以基于精英生成一组个体 $X_{e}$ ，也可以随机生成一组个体 $X_{r}$ 。如果我们认为适应度景观可能大幅变化，可以生成一组对偶个体 $X_{d}$ 。也可以将三种方案组合。
应该将多少新个体引入种群？大多是研究人员会引进0.2N-0.3N个新个体，N是种群规模。可以根据适应度景观的变化来调整替换频率。比如，适应度景观变化很大，进引入更多的新个体。
应该用新个体替换种群中的哪些个体？常见的是替换随机选出来的个体或者替换最差的个体。新个体在种群中并不是非常合适，因为景观的变化它们的适应度可能随时得到改进。因此，我们要记录年龄因子以防止个体还不到某个年龄就被替换掉。

算法4概述动态优化基于迁入的进化算法。

它为算法决策者留有很大的决策空间。

1. $r_{r}$ ， $r_{d}$ 和 $r_{e}$ 应该取什么值？总替换比 $r_{T}$ 的值是在0.2或03左右，我们在开始时通常让随机、对偶和精英代替个体的个数相同，因此， $r_{r}$ $\approx$ $r_{d}$ $\approx$ $r_{e}$ $\approx$ $r_{T}/3$ 。

2.是否应该调整 $r_{r}$ ， $r_{d}$ 和 $r_{e}$ ？如算法4所示，可以对它们进行调整以改善算法的性能，但这样会让算法更复杂。下面的调整方案：在每一代评价新个体的适应度，如果随机个体的那一组表现得比对偶和精英个体好，就做入下调整：

其中，α控制调整的速度， $r_{min}$ 定义每类新个体在每一代中所占的最小比例，常数 $r_{T}$ 定义新个体在每一代中的总比例。这个方法调整存在一个问题，如何决定哪一类新个体表现“最好”？可以用最好的随机个体、最好的对偶个体，以及最好的基于精英个体为基础来决定；或者根据整组随机个体、对偶个体，以及基于精英个体的平均性能来决定。

3.应该用新个体替换种群 $\left \{ x_{i} \right \}$ 中的哪些个体？替换最差的个体，或替换随机选出的个体，或者替换最差个体和随机个体的一个组合。此外，可以将最初的种群 $\left \{ x_{i} \right \}$ 与替换种群X合在一起，再用随机选择的机制选出最好的N个个体。

4.算法4中需要选择重组和变异方法来进化 $\left \{ x_{i} \right \}$ 。

（3）基于记忆的方法

费用函数有时候会在函数的一个有限集中变化，这种变化是确定的而不是随机的。显式的基于记忆的方法是将好的个体存入档案。每次检测到费用函数发生变化时，就从档案中取回个体并把它们加入种群。如果费用函数变成之前曾遇到过的函数，档案中的个体就是好的解进而进化算法非常迅速地收敛到新的最优值。算法5说明这个方法，但只是一个基本的概述。

对于适应度函数为时间的周期函数或适应度函数等于适应度函数的一个有限集的情况，本算法特别适合。下面这些问题值得进一步研究：

当检测到变化时我们应该在档案中保存多少个个体？
我们应该允许档案增加到多大？算法5并没有给它设限。实际上，我们可能想要检测问题的“工况点” 。如果工况点与前面遇到的工况点相同，则对此工况点的精英已经存入了档案，我们不会把当前的精英存入档案除非它们比档案中的还好。
如何才能检测到f(·)的变化？
当检测到f(·)的变化时，应该用归档的个体替换种群中的哪些个体？

（4）动态优化性能的评价

在评价静态优化性能时，我们通常由上一代的种群了解进化算法的表现。在评价动态优化性能时，我们反倒要着眼于在所有代的性能。动态优化问题的两个常见指标是最好性能的平均 $\bar{f}_{b}$ ，以及平均性能的平均 $\bar{f}_{a}$ ：

3.有噪声适应度函数

进化算法的适应度评价经常会伴有噪声。有噪声的适应度函数评价可能会错误地将高适应度分配给低适应度的个体。下图为两个有噪声但无偏的适应度函数 $f(x_{1})$ 和 $f(x_{2})$ 的概率密度函数。我们看到， $f(x_{1})$ 的真实值为0， $f(x_{2})$ 的真实值为4，但这些评价都是有噪声的。因此，对 $x_{1}$ 的评价所得的适应度实际上可能会大于对 $x_{2}$ 的评价。在这种情况下，对 $x_{1}$ 和 $x_{2}$ 的相对适应度的评价不再准确，会让进化算法在重组时选错个体。噪声会欺骗进化算法。

当适应度函数评价带有噪声时，就无法确定哪一个个最好。在进化算法的执行过程中因为不知道真实的适应度函数（假设它是有噪声适应度函数的均值），所以也不知道有噪声适应度函数的概率密度函数。不过我们可能直到真实的适应度函数的概率密度函数。这类似于上图，但是要反过来，将真实的适应度函数看成是均值等于有噪声评价的适应度函数的随机变量，而不是将有噪声适应度函数看成均值等于真实的适应度函数的随机变量。

下面介绍处理有噪声适应度函数的三种方法。

（1）再采样

降低噪声的一种简单的方法是对适应度函数再采样。如果对给定个体的适应度函数做N次评价，并且这N个样本的噪声值是独立的，则平均适应度函数的方差会减少为原来的1/N。假设候选解x的被评估的适应度g(x)为：

其中，f(x)是真实的适应度，w是方差为 $\sigma ^{2}$ 的零均值噪声。这意味着测量到的适应度值g(x)的均值为f(x)，方差为 $\sigma ^{2}$ 。如果我们做N次独立的测量 $\left \{ g_{i}(x) \right \}$ ，则每一个测量值 $g_{i}(x)$ $g_{i}(x)$ 的方差为 $\sigma ^{2}$ ， $g_{i}(x)$ 真实适应度最好的估计为

$\hat{f}(x)$ 的方差为 $\sigma ^{2}$ /N。如下图所示，N个有噪声适应度函数评价的平均比单个评价准确N倍。

实线为有噪声适应度函数的概率密度函数。虚线为4个适应度函数评价的概率密度函数。它们都是零均值，但平均评价的方差是单个评价方差的1/4.平均评价有可能比单个评价更接近其均值。

只有当适应度函数评价的噪声对不同样本独立的时候，再采样策略才完全有效。比如，假设我们用有噪声的仪表测量候选解的适应度，如果仪表的噪声和它本身的采样时间相关，则N个样本的平均不会让方差减少到1/N。在这种情况下，方差减少的量取决于样本之间噪声的相关性。

假设我们有候选解x的N个适应度评价 $\left \{ g_{i}(x) \right \}$ ，可以找出适应度估计方差 $\sigma ^{2}$ 个估计 $\hat{\sigma }^{2}$ ，即

$\hat{\sigma }^{2}$ 为 $\sigma ^{2}$ 的无偏估计，这点概率上已经做出了证明。为了适应度估计的方差达到想要的值可以用（41）式确定采样的次数。想要的方差由用户定义，它也依赖于具体的问题。当N→无穷，方差趋于0适应度估计也不再有误差。

有些研究人员建议对每一个候选解按固定次数采样。这样做忽略了不同候选解适应度评价的噪声可能不同的情形。如果用噪声与测量到的信号成比例的传感器进行适应度评价，可能就会如此。在这种情况下，可以将（39）式替换为

即适应度的噪声依赖于被评价的具体的候选解。这时，对每一个x按固定次数采样效率会很低，因为不同候选解的准确度不同。但我们还是可以用（41）式来决定每一个候选解的采样次数。

为了达到想要的方差，再采样策略需要很多样本。对于昂贵适应度函数来说不太可行。因此，我们需要将再采样与前面提到的适应度近似的方法结合。只对种群中最好的个体采样，也可以减少再采样的次数。只凭单个适应度评价，可能不知道哪些个体最好，但是至少会有一些思路，并能为种群中最好的个体预留再采样所需的计算量。

决定再采样次数的另一种方法是基于前面提到的适应度继承的想法。假设由几个父代 $\left \{ p_{i} \right \}$ 生成一个子代x。进一步假设第i个父代适应度评价估计值为 $g(p_{i})$ ，标准差为 $\sigma (p_{i})$ 。在我们评价子代的适应度之前，可以用适应度继承得到适应度的估计 $\hat{f}(x)$ 及其标准差 $\hat{\sigma }(x)$ ，然后评价子代的适应度。如果适应度评价g(x)落在 $\hat{f}(x)$ 的±3 $\hat{\sigma }(x)$ 之间，则认为g(x)有效。否则可以推断g(x)的噪声很大，需要继续利用再采样降低噪声。这个方法在某些方面与我们的直觉相反。它表明父代的噪声越大，我们越有可能接受对子代的评价。但我们期望的是，父代的噪声越大，就更应该对子代的适应度再采样。

较少适应度评价次数的另一个方法是在进化算法开始时只做几次采样，在进化算法运行过程中经常的在采样。这样做的道理是，在优化过程初期，进化算法的搜索通常比较粗糙。在早期的代中进化算法试图找到最优解的一个大致的邻域；在后期的代中则试图收敛到更准确的解。当进化算法开始收敛，优化过程快结束，我们才需要更精确的适应度函数值。也就是说，只有在准确度较好的情况下准确度才有意义。

（2）适应度估计

（41）式是基于有噪声的样本估计适应度的简单平均方法。我们还可以用其他有关概率的方法，比如，假设在搜索空间中 $x_{1}$ 和 $x_{2}$ 的适应度值相似：

即 $x_{1}$ 的适应度是均值为 $f(x_{2})$ 方差为kd的高斯随机变量，这里k是未知参数，d是 $x_{1}$ 和 $x_{2}$ 之间的距离。如果适应度评价 $g(x_{1})$ 的方差为 $\sigma ^{2}$ ，则

利用这些假设，已知 $x_{1}$ 和 $x_{2}$ 的噪声评价，可以用极大似然估计 $x_{1}$ 和 $x_{2}$ 的适应度。也就是说，我们不仅可以用个体的有噪声评价，还可以用它的邻居的有噪声评价来估计它的适应度。

（3）卡尔曼进化算法

卡尔曼进化算法是为适应度函数评价有噪声且昂贵的问题设计的。最初在遗传算法背景下提出的卡尔曼进化算法会记录适应度的不确定性并相应地分配适应度评价。

卡尔曼滤波是线性动态系统状态的一个最优估计器。卡尔曼进化算法假设已知个体x的适应度是一个常数，再进一步假设适应度评价噪声不是x的函数。利用这些假设，可以用简化的卡尔曼滤波的标量形式记录每一个适应度估计的不确定性。单个适应度函数评价的方差记为R。在k次适应度函数评价后个体x的适应度估计的方差记为 $P_{k}(x)$ 。x的第k次适应度函数评价的值记为 $g_{k}(x)$ 。最后在k次适应度函数评价之后对x的适应度的估计记为 $\hat{f}_{k}(x)$ 。用这些记号，由卡尔曼滤波理论可以得到

这里k=0,1,2...，对所有x，初始化 $P_{0}(x)$ =无穷，有

也就是说，在第一次适应度函数评价 $g_{1}(x)$ 之后我们的估计 $\hat{f}_{1}(x)$ 就等于第一次评价。在第一次评价之后适应度估计中的不确定性 $P_{1}(x)$ 等于评价中的不确定性。

（45）式显示，每当评价x的适应度时，我们会基于前面的估计，不确定性以及最近的适应度函数评价的结果g(x)来修正我们的估计 $\hat{f}(x)$ ，由（45）式可知

换言之，如果我们能完全确定x的适应度（ $P_{k}(x)$ =0），再评价x的适应度也不会改变我们对它适应度的估计。另一方面，如果我们完全不能确定x的适应度（ $P_{k}(x)$ 趋近于无穷），就会将适应度的估计设置为下一次适应度函数评价的结果。（45）式还说明，每次评价x的适应度时，它的不确定性P(x)都在减小（也就是说我们对估计值的信心在不断地增加）。由（45）式可得

这些结果与我们的直觉一致。如果适应度函数噪声的方差R为0，则适应度函数很完美，所以我们的估计就是适应度函数评价的结果，并且在估计中的不确定性为0.另一方面，如果适应度函数噪声的方差R为无穷，噪声过大会令适应度函数无法提供任何有用的信息。在这种情况下，再多的评价也不能改变我们对适应度函数的估计，也不能降低其中的不确定性。

对于每一个个体x的每次适应度函数评价，卡尔曼进化算法会记下适应度函数评估 $\hat{f}_{k}(x)$ 和方差 $P_{k}(x)$ （k=1，2，...）。我们按用户定义的比例F，取出现有评价的F部分用与生成和评价新个体。按（46）式初始化新个体的适应度估计和方差。用现有评价的（1-F）部分用于重新评价已有的个体。在这种情况下，按照（45）式更新适应度估计和方差。每当有足够的资源评价适应度函数，就生成在[0,1]上均匀分布的一个随机数r，如果r＜F，用进化算法重组和变异生成新个体，然后评价它的适应度；否则，重新评价一个已有的个体。

当重新评级一个已有的个体时，要遵循两个指导原则：首先，对适应度估计的方差较大的个体可以重新评价以生成更多的信息。其次，对于适应度估计值较大的个体可以重新评估以生成更多有用的信息。也就是说，对适应度估计值低的个体，我们不用介意能否得到高精度，因为不会用它们重组生成下一代。下面是一种个体 $x_{s}$ 重新评价的方法：

其中 $\hat{f}_{k}(x)$ 和 $P_{k}(x)$ 省去了下标k；对（49）式中的每一个个体x，使用最近更新的 $\hat{f}_{k}(x)$ 和 $P_{k}(x)$ 的值。这个式子说明，适应度估计值大于均值一下一个标准差的所有个体中，选择不确定性最大的个体重新评价。这个策略假定f(x)为适应度，所以f(x)越大越好。