惩罚函数法：有效解决非可行解的方法

惩罚函数法是一种常用的处理约束条件的方法[5-7]。本质上它是通过惩罚不可行解，将约束问题转化为无约束问题。

惩罚策略的主要问题是如何设计一个惩罚函数Φ（x），从而能有效地引导遗传搜索到达解空间的最好区域。

带有惩罚项的新的目标函数具有如下形式：

式中，f（x）为原目标函数，Φ（x）惩罚项。

对于约束极小化问题，若新的目标函数的形式为F（x）=f（x）+Φ（x），惩罚函数应具有这样的性质：对非可行解产生一个正的值，而对可行解则产生值0。

通常惩罚函数由解到可行区域F 的距离或对解的修正策略来确定。对于形如gi（x）≥0，i=1，2，…，m，hj（x）=0，j=1，2，…，l的约束条件，惩罚函数可定义为：

这里p 是正整数，一般取1或2。于是新的目标函数可定义为：

式中，θ ＞0，称为惩罚因子。

如何设计惩罚函数以有效地惩罚非可行解，对问题的解决至关重要，下面讨论几种常用的方法。我们假定问题有m 个约束，对应的惩罚函数为fj（x），j=1，2，…，m。

1.静态惩罚函数

该方法对每一约束建立一族区间及一些惩罚因子。其详细描述如下：

（1）对每个约束，确定l 个区间[a0，a1]，（a1，a2]，…，（al-1，al]，以度量惩罚函数值反映的偏离可行区间的程度；

（2）对每个约束及偏离程度，建立一个惩罚因子θij，i=1，2，…，l，j=1，2，…，m，使得偏离程度越高，惩罚因子越大；

（3）随机地生成一个初始群体，群体内可以是可行解，也可以是非可行解；

（4）演化该群体，并使用式（3-9）计算个体的适应值：

这里θj 由fj（x）的偏离程度来决定。若fj（x）∈（ai-1，ai]，则θj=θij。(www.xing528.com)

该方法的优点是简单、直接、易于实现。但该方法的性能在很大程度上依赖于惩罚因子θij 的选取。对具有m 个约束的问题，需要确定m（2l+1）个参数。即m（l+1）个待确定区间的端点，m·l个惩罚因子。

2.动态惩罚函数

静态惩罚函数在算法的演化过程中是静止不变的，而由Joines和Houck提出的动态惩罚函数却随着算法的演化而演化。在算法的第t代时，它按下式计算个体的适应值：

式中，C、α、β 都为正常数，通常取C=0.5，α=β=2。

与静态惩罚函数相比，该方法需要很少的参数。并且随着演化代数的增加，对非可行解的惩罚量越来越大。该方法的一个弱点是惩罚因子（Ct）α 的增大过于迅速，以至于很难从局部极小中逃脱出来。

3.退火惩罚函数

针对动态惩罚函数的缺点，Michalewicz Z[5]等提出了退火惩罚函数的策略，其描述如下：

（1）将约束分为4类：线性方程、线性不等式、非线性方程和非线性不等式；

（2）随机地选取一点作为初始点，并且初始种群中只含有该点的多个副本。该初始点满足所有的线性约束；

（3）设置初始温度T=T0；

（4）用下列适应度函数演化群体：

（5）如果T ＜Tf 则终止，否则：①降低温度；②将最优解作为下一次迭代的初始点；③重复算法的前述步骤。

该方法将线性约束与非线性约束区分开，并使用算子修正法，使种群中的个体满足线性约束，而且随着温度T 的降低，对非可行解的惩罚加大。

Michalewicz Z等推荐的参数取值为T0=1，Tf=0.0000001，冷却方案为Ti+1=0.1·Ti。