約束優(yōu)化

傳統(tǒng)方法的實現如牛頓法、梯度法等，其基本思想就是將動態(tài)的轉化為靜態(tài)的，將多目標轉化為單目標，由點及面的搜索思想。

傳統(tǒng)方法存在如下問題：

(1) 傳統(tǒng)的基于梯度的優(yōu)化方法(如可行方向法、約束變尺度法)對約束條件的處理往往是先尋找一個可行且下降的方向，然后沿此方向進行線性搜索，并重復上述步驟以得到問題的最優(yōu)解，然而該最優(yōu)解往往是局部最優(yōu)的。

(2) 對于許多實際的約束優(yōu)化問題，一方面，由于目標函數往往形式復雜，不僅問題的維數比較高，而且優(yōu)化曲面中存在多個極小點，這使得傳統(tǒng)的基于梯度的算法難以奏效。另一方面，實際問題中目標函數往往是不連續(xù)或不可微，有些問題目標函數甚至沒有解析表達式，傳統(tǒng)算法難以解決這類問題。

(3) 由于約束的存在，使得決策變量的可行搜索空間不規(guī)則(如非凸，不連通等)，從而增加了搜索到最優(yōu)解的難度，有時甚至很難找到可行解。

簡介

進化算法是一種智能的全局優(yōu)化方法，它對函數本身性質要求非常低，往往只要求目標函數值是可以計算的，不要求它具有連續(xù)性、可微性及其它解析性質，同時它又是基于群體進化的算法，因此可采用進化算法解決約束優(yōu)化問題。用進化算法解決約束優(yōu)化問題的關鍵在于如何進行有效的約束處理，即如何有效均衡在可行區(qū)域與不可行區(qū)域的搜索。

常見的用于求解約束優(yōu)化問題的進化算法有罰函數法、遺傳算法、進化策略、進化規(guī)劃、蟻群算法和粒子群算法等。

與傳統(tǒng)方法相比的優(yōu)勢

(1) 在一般情況下，進化算法能否收斂到全局最優(yōu)解與初始群體無關，而傳統(tǒng)優(yōu)化方法則依賴于初始解；

(2) 進化算法具有全局搜索能力，而很多傳統(tǒng)優(yōu)化方法往往會陷入局部最優(yōu)；

(3) 進化算法的適用范圍廣，能有效地解決不同類型的問題，而傳統(tǒng)優(yōu)化方法在設計時往往就只能解訣某一類型的問題。

存在的不足

(1) 進化算法中的參數，如群體規(guī)模、進化代數、重組概率、變異概率等，往往需要根據經驗設定，且在一定程度上與問題相關；

(2) 進化算法的收斂問題，進化算法求解實際問題時的收斂性判定缺乏理論指導。 2100433B

不失一般性，約束優(yōu)化問題可以描述為如下形式：

其中 x 是決策變量，f( x )是目標函數，

若對某一

當f(x)為線性函數時稱為線性規(guī)劃問題，反之如果是非線性則為非線性規(guī)劃問題。當約束問題包含一個目標函數時，稱為單目標約束優(yōu)化問題；當約束問題包含多個目標函數時，稱為多目標約束優(yōu)化問題。

約束最優(yōu)化問題就是求目標函數

約束最優(yōu)化問題的解法有兩種：

約束最優(yōu)化問題化約束最優(yōu)化問題為無約束最優(yōu)化問題

例1 最大面積 設長方形的長、寬之和等于

解: 這就是一個約束最優(yōu)化問題：設長方形的長為x，寬為y，求目標函數A=xy在條件x y=a之下的最大值。

由于從約束條件x y=a中容易解出y=a-x，代入目標函數

由

從上述例子可以看出化約束最優(yōu)化問題為無約束最優(yōu)化問題的思路：從約束條件

但是，這種方法有局限性，因為有時從約束條件

約束最優(yōu)化問題拉格朗日乘數法

這一方法的思路是：把求約束最優(yōu)化問題轉化為求無約束最優(yōu)化問題，看它應該滿足什么樣的條件"para" label-module="para">

設

為了便于記憶，并能容易地寫出方程組(1)，我們構造一個函數

于是，我們把用拉格朗日乘數法求解約束最優(yōu)化問題的步驟歸納如下：

①構造拉格朗日函數

②解方程組

③根據實際問題的性質，在可能極值點處求極值 。2100433B

約束最優(yōu)化問題(constrained optimization problem)是指具有約束條件的非線性規(guī)劃問題。極小化問題的一般形式為