适应度函数的意义和作用分析

1.与目标函数对应的适应度函数

在遗传算法中，对适应度函数的限制较少，它可以不是连续可微函数，其定义域可以为任意集合。由于要由适应度函数计算生存概率，而概率又是正值，所以对适应度函数的唯一要求是它的值必须为非负值。

有两类优化问题，一是求代价函数g（x）的最小值，另一是求效能函数u（x）的最大值。在通常的搜索方法中，为了把最小化问题转化成最大化问题，只需要简单地把代价函数乘以-1即可，但对遗传算法而言，就不能用这一方法。代价函数与效能函数都是目标函数，适应度函数是由目标函数求得的，为了保证适应度函数是非负值函数，可以采用以下几种方法。

1）最大系数法

在最小值问题中，与代价函数g（x）对应的适应度函数f（x）为

式中：cmax是最大系数，它可以是迄今为止进化过程中g（x）的最大值或当前群体中g（x）的最大值，也可以是前k代中g（x）的最大值，cmax最好与群体无关。

2）最小系数法

在最大值问题中，与效能函数u（x）对应的适应度函数f（x）为

式中：cmin是最小系数，它是当前群体中或前k代群体中u（x）的最小值，也可以是群体的方差的函数。

3）相对系数法

无论哪一类问题，都以群体中的目标函数d（x）的相对值作为适应度函数值。

对于最大值问题有

对于最小值问题有

上面两式中，d（x）max、d（x）min分别是当前群体中或前k代群体中目标函数d（x）的最大值及最小值。

2.适应度函数定标

“适者生存”是自然选择的基本规律，在遗传算法中表现为适应度高的个体生存概率大。但对群体而言，却有些复杂的情况。有两种不利于优化的现象，应引起我们的注意。

（1）异常个体引起早熟收敛。这种现象常出现在小规模群体中。在遗传进化的早期，一些超常的个体的适应度很大，在群体中占有较大的比例，这些异常个体因竞争力太突出而控制了选择过程，结果使算法过早收敛，从而影响求得全局最优解。

（2）个体间差距不大，引起搜索成为随机漫游。当群体中个体的适应度相差不大，个体间的竞争力减弱，特别是平均适应度已接近最佳适应度时，最佳个体与其他许多个体在选择过程中就会有大体相等的选择机会，从而使有目标的优化搜索过程变成无目标的随机漫游，同时影响求得全面最优解。

对于上述第一种情况，我们要抑制这些超常个体，通过缩小相应的适应度函数值的方法，降低这些异常个体的竞争力。而对于上述第二种情况，我们则要拉开个体之间的差距，通过放大相应的适应度函数值的方法，提高个体间的竞争力。这种对适应度函数值的缩小、放大调整称为适应度函数定标（scaling）。目前，定标方法大致有以下几种。

1）线性定标

设原适应度函数为f，定标后的适应度函数为f＇，则线性定标可采用下式：

式中：系数a和b可以有多种设定途径。对于异常个体和竞争力弱的个体可以采用不同的系数。但不管怎样设定，定标要满足三个条件。(www.xing528.com)

（1）原适应度的平均值要等于定标后的适应度的平均值。这是为了保证在以后的选择处理中，前代的平均贡献可遗传给下代子孙。

（2）定标后适应度函数的最大值f＇max要等于原适应度函数平均值的给定的倍数，即

式中：C是为了得到所期望的最优个体而给定的复制数。实验表明，当群体不太大时（n=50～100），C在1.2～2.0范围内取值。

（3）定标后适应度函数的最小值f＇min不得为负值。有时，为了把、fmin拉开差距，会出现f＇min变成负数的情况。为了不产生负值，同时又不改变系数C，可以在f＇上加一个正数d，即

这样，当f＇min为负值时，f″min=0，也就是把定标后的适应度函数值提高了一个水平d。

2）σ截断

σ是群体适应度函数值的标准方差。为了保证定标后的适应度值不出现负值，在定标前对原适应度值做预处理。方差σ表示了适应度值的离散程度，显然σ值越大，适应度函数值越分散，当原f值较小时，定标后就容易出现负值，因此可采用式（9.3.44）来进行预处理

式中：常数C要适当选择。当σ较大时，上式括号中的负值越大，也就是附加项越大，这样便能保证f＇为正值。式（9.3.44）与式（9.3.43）的不同，在于式（9.3.44）是定标前进行的预处理，而式（9.3.43）则是在定标后进行的后处理。

3）乘幂标

对原适应度函数f进行乘幂处理，如

式中，幂指数K根据问题决定，且在进化计算过程中可按需要修改。一般K在1～1.2之间选择，Gillies曾在机器视觉实验中采用K=1.005，取得较好结果。

3.适应度函数对遗传算法的影响

（1）适应度函数决定了遗传算法优化搜索的性能。如前所述，采用定标技术可克服早熟收敛和随机漫游现象，从而提高了全局优化的性能。

（2）适应度函数决定了遗传算法迭代停止的条件，通常以群体中某个体的最大适应度值不再改变为迭代停止的评定条件。这一条件表明：群体中个体的进化已趋于稳定状态，即群体中一定比例的个体已完全是同一个体，这时优秀后代的个数已不再变化，进化过程便暂告结束。

（3）在适应度函数中考虑约束条件。以上讨论的适应度函数都是针对无约束优化问题的，但在实际问题中，我们常常碰到有约束的优化问题。此时，可以用一种十分自然的方法来考虑约束条件，即在进化过程中，每迭代一次就检测一下新的个体是否违背了约束条件。如果没有违背，就作为有效个体，反之，作为无效个体而被淘汰。这种方法对于弱约束问题的求解还是有效的，但对于强约束问题求解效果不佳。这是因为，此时寻找一个有效个体的难度不亚于寻找最优个体。

为了解决这类问题，我们可以采用一种惩罚方法（penalty method）。该方法的基本思想是设法对个体违背约束条件的情况给予惩罚，在适应度函数中用惩罚函数来具体体现这种惩罚。这样，就把一个约束优化问题转化成一个带有惩罚的非约束优化问题。

例如，一个约束最小化问题的数学模型是

式中：x为一向量；f（x）为目标函数（适应度函数）；gi（x）为约束条件。采用惩罚函数，可以把上述问题转化为非约束问题：

式中：P为惩罚函数；r为惩罚系数。

惩罚函数有许多确定方法，常用下列形式：

惩罚系数r的取值接近无穷大时，非约束解可收敛到约束解。在实际问题中，r的取值还可针对不同的约束条件取不同的值，这样可使惩罚更加适当。把惩罚函数加到适应度函数中的思想很简单、直观。但是惩罚函数值在约束边界处会发生急剧变化，应予注意。关于更具体的约束优化问题的遗传算法，请参阅9.4.2节的有关内容。