約束優(yōu)化

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

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

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

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

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

簡介

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

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

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

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

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

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

存在的不足

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

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

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

其中 x 是決策變量，f( x )是目標(biāo)函數(shù)，

若對某一

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

約束最優(yōu)化問題就是求目標(biāo)函數(shù)

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

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

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

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

由于從約束條件x y=a中容易解出y=a-x，代入目標(biāo)函數(shù)

由

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

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

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

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

設(shè)

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

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

①構(gòu)造拉格朗日函數(shù)

②解方程組

③根據(jù)實際問題的性質(zhì)，在可能極值點處求極值 。2100433B

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