适应度函数及比例变换的优化方法

在遗传算法中，适应度函数f（x）的作用是对每一个个体v 指定一个函数值f（v），使我们可以区分群体中个体（问题解）的好坏。适应值越大的个体越好，相应地，个体越好，其适应值越大。在遗传算法中，适应度函数是判断解的质量的唯一办法。

对一个给定问题，虽然有多种方式设计适应度函数，但一般都要求最优解与具有最大适应值的个体相对应。这是因为遗传算法在极限形式下收敛于具有最大适应值的个体，所以我们希望这些具有最大适应值的个体相对应问题的最优解。除此之外，一般还希望个体的质量与该个体的适应值之间有密切的联系，即个体间质量的差异能够反映出个体适应值之间的差异，反之亦然。

例2-6 考虑下列优化问题：

一般来说，好的适应度函数不但能够加快演化优化，而且能够处理遗传算子与适应度函数之间的相互作用，即当个体的变化较小时，其适应值的变化也较小。

在遗传算法中，由于在每一演化代，都要对群体中的所有个体进行适应值计算，所以适应度函数的计算是算法中最花费时间的部分，因而对适应度函数的另一个要求是其计算量应尽可能的少。

1.常见的适应度函数

常见的适应度函数有以下几种，这些适应度函数可以直接从目标函数变化而来。

1）原始适应度函数

原始适应度函数是直接由目标函数表示的适应度函数。

若f（x）为目标函数，那么当优化问题为maxf（x）时，适应度函数可取为fitness（x）=f（x）；当优化问题为minf（x）时，适应度函数可取为fitness（x）=-f（x）。

原始适应度函数简单直观，直接反映了优化问题的求解目标。但存在以下不足之处：适应度函数值有可能为负，这样就不能满足轮盘赌选择中要求选择概率非负的要求。

值得注意的是，采用原始适应度函数可能使得算法在迭代过程中收敛到一些目标值近似的不同染色体，因此再采用原始适应度函数已难于区别这些染色体。

例2-7 考虑下列优化问题：

假定适应度函数为目标函数，问题的解采用二进制编码，且解的精度要求为10-2，那么由

可知，解的二进制编码的长度为6。同时，假定遗传算法的某一代个体特征如表2-3所示。

表2-3　遗传算法的某一代个体特征

从表2-3中可以看出，此时群体中个体选择概率之间的差别很小，因此在下一代父体的选择过程中，很难区别哪一个染色体占优势。

2）简单适应度函数

为了克服原始适应度函数值有可能为负的情形，常常需要将原始适应度函数作以下简单的变换。

对于最大化优化问题：maxf（x），适应度函数可以定义为：

式中，cmin 是目标函数f（x）的一个下界。若cmin 未知，则它也可以用当前代或到目前为止的各演化代中f（x）的最小值来代替。

对于最小化优化问题minf（x），适应度函数可以定义为：

式中，cmax 是目标函数f（x）的一个上界。若cmax 未知，则它也可以用当前代或到目前为止的各演化代中f（x）的最大值来代替。

有时为了使适应值改进的速度较快，可以将原始适应度函数作以下简单的变换。

对于最大化优化问题maxf（x），适应度函数可以定义为：

对于最小化优化问题minf（x），适应度函数可以定义为：

例2-8 若在例2-7中，适应度函数取为：

那么可得表2-4。

表2-4　简单适应度函数运算后的其他代个体特征

此时，个体的适应值及选择概率已有较明显的区别。

2.适应度函数的比例变换

在遗传算法中，选择过程是根据个体适应值进行的。一般个体的适应值越大，被选择作为父体的可能性就越大。但这会产生以下问题：其一是产生过早收敛现象，即在算法的初期，群体为少数几个适应值较大的个体所统治，以至于算法不能收敛到问题的最优解或近似最优解；其二是可能产生停滞现象，即在算法的后期，群体中的个体适应值的差异过小，这使得由于选择压力过小而减慢算法的收敛速度。对适应度函数进行比例变换就是为了减缓上述两个问题以提高算法的性能。

常见的适应度比例变换有以下几种。

1）线形比例变换

线形比例变换指用一个线性函数对个体的适应值进行变换。

设f（x）为原适应度函数，f′（x）为变换后的适应度函数，那么有：

式中，a，b 为常数且a ＞0。常数a，b 的选择有多种方法，但应满足以下条件：

（1）原平均适应值等于变换后的平均适应值；

（2）变换后的最大适应值等于原平均适应值的c 倍，c 是一个预先指定的常数。(www.xing528.com)

解上述方程组得：

当c 取不同的值时，得到不同的a，b。当群体中个体的数目为50～100时，通常c 的取值范围为1.2～2。

如图2-6所示，线性变换改变了适应值之间的差距，保持了群体中的多样性，而且计算简便。

应用线性比例变换需要注意的问题是，若群体中某些个体的适应值远远低于平均适应值，且群体中个体最大适应值与平均适应值较为接近时，线性比例变换有可能导致负的适应值，如图2-7所示。

图2-6　线性比例变换

图2-7　变换后出现负适应值的情况

例如，假定群体中有6个个体，分别记为1，2，3，4，5，6。个体的适应值如表2-5中第2行所示，那么有fmax=25，favg=21。若在线性比例变换中取c=2，那么可得：

经线性比例变换后所得的适应值如表2-5中第3行所示。

表2-5　某群体中个体适应值表

为了防止出现负适应值的情形，可采取如下方式：仍保持原平均适应值等于变换后的平均适应值，但要求变换后的最小值为0，即有：

解上述方程组得：

2）σ截断

σ 截断是Forrest为改进线性比例变换而提出的，以便能将问题的信息结合到映射中，从而能适应有负适应值问题的需要。Goldberg改进后的公式为：

3）幂函数变换