約束優(yōu)化進(jìn)化算法

簡(jiǎn)介

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

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

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

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

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

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

存在的不足

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

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

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

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

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

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

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

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

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

若對(duì)某一

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

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

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

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

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

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

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

由

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

但是，這種方法有局限性，因?yàn)橛袝r(shí)從約束條件

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

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

設(shè)

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

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

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

②解方程組

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

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