罰函式法又稱乘子法，是指將有約束最最佳化問題轉化為求解無約束最最佳化問題：其中M為足夠大的正數， 起"懲罰"作用， 稱之為罰因子，F(x, M )稱為罰函式。內部罰函式法也稱為障礙罰函式法。
這種方法是在可行域內部進行搜尋，約束邊界起到類似圍牆的作用，如果當前解遠離約束邊界時，則罰函式值是非常小的，否則罰函式值接近無窮大的方法。在進化計算中，研究者選擇外部罰函式法的原因主要是該方法不需要提供初始可行解。其中B(x)是最佳化過程中新的目標函式，Gi和Hj分別是約束條件gi(x)和hj(x)的函式，ri和cj是常數，稱為罰因子。
基本介紹
- 中文名：罰函式法
- 套用：數學
定理,種類,常用函式法,罰因子取值,研究方法,
定理
對於某個確定的正數M, 若罰函式F(x, M )的最優解x* 滿足有約束最最佳化問題的約束條件，則x* 是該問題的最優解。序列無約束最小化方法 ：罰函式法在理論上是可行的，在實際計算中的缺點是罰因子M的取值難於把握，太小起不 到懲罰作用；太大則由於誤差的影響會導致錯誤。
這些缺點，可根據上述定理加以改進，先取較小的正數M， 求出F(x, M )的最優解x* 。當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） 採用到可行域距離的罰函式方法比採用約束違反個數的罰函式方法性能優越。
（3） 罰函式的性能可以通過以下兩個標準進行評價：最大完成成本和期望完成成本。完成成本與可行性的距離有關。
（4） 罰函式應該接近期望完成成本，但是並不需要在期望完成成本之下。越精確的罰函式越能夠找到更好的解。當罰函式低估完成成本時，搜尋可能會找不到解。
罰函式法既可以處理不等式約束也可以處理等式約束，並且一般情況下是將等式約束轉化為不等式約束形式
為：| hj(x)|-e<=0
