罰函數法

傳統的罰函數法一般分為外部罰函數法和內部罰函數法。外部罰函數法是從非可行解出發逐漸移動到可行區域的方法。內部罰函數法也稱為障礙罰函數法，這種方法是在可行域內部進行搜索，約束邊界起到類似圍牆的作用，如果當前解遠離約束邊界時，則罰函數值是非常小的，否則罰函數值接近無窮大的方法。

由於進化計算中通常採用外部罰函數法，因此本文主要介紹外部罰函數法。在進化計算中，研究者選擇外部罰函數法的原因主要是該方法不需要提供初始可行解。需要提供初始可行解則是內部罰函數法的主要缺點。由於進化演演算法應用到實際問題中可能存在搜索可行解就是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