罚函数

罚函数
2011年04月14日
　　　它将有约束最优化问题转化为求解无约束最优化问题:
　　[/b]
　　[b]　　其中M为足够大的正数, 起"惩罚"作用, 称之为罚因子, F(x, M )称为罚函数.
　　[/b]
　　[b]　　定理 对于某个确定的正数M, 若罚函数F(x, M )的最优解x* 满足有约束最优化问题的约束条件, 则x* 是该问题的最优解.
　　[/b]
　　[b]　　序列无约束最小化方法
　　[/b]
　　[b]　　罚函数法在理论上是可行的, 在实际计算中的缺点是罚因子M的取值难于把握, 太小起不到惩罚作用;太大则由于误差的影响会导致错误.
　　[/b]
　　[b]　　这些缺点, 可根据上述定理加以改进, 先取较小的正数M, 求出F(x, M )的最优解x* .
　　[/b]
　　[b]　　当x*不满足有约束最优化问题的约束条件时, 放大M (例如乘以10)重复进行, 直到x* 满足有约束最优化问题的约束条件时为止.
　　       　传统的罚函数法一般分为外部罚函数法和内部罚函数法。外部罚函数法是从非可行解出发逐渐移动到可行区域的方法。内部罚函数法也称为障碍罚函数法，这种方法是在可行域内部进行搜索，约束边界起到类似围墙的作用，如果当前解远离约束边界时，则罚函数值是非常小的，否则罚函数值接近无穷大的方法。
　　　　由于进化计算中通常采用外部罚函数法，因此本文主要介绍外部罚函数法。在进化计算中，研究者选择外部罚函数法的原因主要是该方法不需要提供初始可行解。需要提供初始可行解则是内部罚函数法的主要缺点。由于进化算法应用到实际问题中可能存在搜索可行解就是NP难问题，因此这个缺点是非常致命的。
　　　　外部罚函数的一般形式为
　　　　B(x)=f(x)+[∑ riGi+∑ cjHj]
　　　　其中B(x)是优化过程中新的目标函数，Gi和Hj分别是约束条件gi(x)和hj(x)的函数，ri和cj是常数，称为罚因子。
　　　　Gi和Hj最常见的形式是
　　　　Gi=max[0, gi(x)]a
　　　　Hj=| hj(x)|b
　　　　其中a和b一般是1或者2。
　　　　理想的情况下，罚因子应该尽量小，但是如果罚因子低于最小值时可能会产生非可行解是最优解的情况（称为最小罚因子规则）。这是由于如果罚因子过大或者过小都会对进化算法求解问题产生困难。
　　　　如果罚因子很大并且最优解在可行域边界，进化算法将很快被推进到可行域以内，这将不能返回到非可行域的边界。在搜索过程开始的时候，一个较大的罚因子将会阻碍非可行域的搜索。如果在搜索空间中可行域是几个非连通的区域，则进化算法可能会仅移动在其中一个区域搜索，这样将很难搜索到其他区域，除非这些区域非常接近。另一方面，如果罚因子太小，这样相对于目标函数罚函数项是可以忽略的，则大量的搜索时间将花费在非可行域。由于很多问题的最优解都在可行域的边界，大量时间在非可行域进行搜索对找到最优解是没有多大作用的，这对于进化算法来说非常致命的。
　　　　最小罚因子规则概念是很简单的，但是实现起来却是非常的困难。对于一个确定的进化算法，很多问题的可行域和非可行域的边界是未知的，因此很难确定它的精确位置。
　　　　非可行个体和搜索空间可行区域之间的关系对于个体的惩罚时具有非常重要的作用。但是，怎样利用这种关系指导搜索方向并将它引导到期望区域的原理并不清楚。
　　　　在现有方法中，主要存在三种定义可行域和非可行域之间关系的方法。
　　　　（1） 个体惩罚值仅与它的非可行性有关，与约束违反量无关（即不使用个体与可行域之间距离的信息）。
　　　　（2） 违反约束条件的个数作为衡量标准，并且用于确定相应的惩罚值。
　　　　（3） 非可行个体的修复代价（即需要修复个体可行性需要的成本）。
　　　　很多研究者研究了设计罚函数的启发式方法。其中最著名的是Richardson等人提出的一种方法，它的具体的内容如下：
　　　　（1） 采用到可行域距离的罚函数方法比采用约束违反个数的罚函数方法性能优越。
　　　　（2） 如果问题仅有几个约束条件并且可行解非常少，则单独使用约束违反个数的罚函数的方法可能找不到任何解。
　　　　（3） 罚函数的性能可以通过以下两个标准进行评价：最大完成成本和期望完成成本。完成成本与可行性的距离有关。
　　　　（4） 罚函数应该接近期望完成成本，但是并不需要在期望完成成本之下。越精确的罚函数越能够找到更好的解。当罚函数低估完成成本时，搜索可能会找不到解。
　　　　罚函数法既可以处理不等式约束也可以处理等式约束，并且一般情况下是将等式约束转化为不等式约束形式
　　　　| hj(x)|-e<=0
　　[/b]
　　[b]　　罚因子：penalty
　　[/b]
　　[b]　　罚常数：penalty constant
　　[/b]
　　[b]　　罚函数法：penalty function method