復(fù)合型法-罰函數(shù)法

工程中的大量優(yōu)化設(shè)計問題，都是約束優(yōu)化問題，它的一般數(shù)學(xué)模型為：

求解這類問題的方法稱約束優(yōu)化方法，最優(yōu)點X*稱為約束最優(yōu)點。。約束優(yōu)化算法大致可歸納為兩大類：●直接解法●間接解法（2-59）

約束優(yōu)化方法復(fù)合形法是適用于具有不等式約束優(yōu)化問題的一種直接算法。

該法的基本思路是：在n

維優(yōu)化設(shè)計空間的可行域D內(nèi)，構(gòu)造具有k

個頂點的多邊形(或多面體)，稱作復(fù)合形。復(fù)合形的每個頂點都代表一個設(shè)計方案。然后，計算復(fù)合形各頂點的目標(biāo)函數(shù)值并逐一進(jìn)行比較，取函數(shù)值最大者為最壞點，最小者為最好點。再以去掉最壞點的其余各點的中心點為映射軸心，在最壞點和其余各點的中心點的連線上，尋找一個既滿足約束條件，又使目標(biāo)函數(shù)值有所改善的壞點映射點，并以該映射點替換壞點而構(gòu)成新的復(fù)合形。

按照上述步驟重復(fù)多次，不斷地去掉最壞點，這樣不斷調(diào)整復(fù)合形的頂點，使復(fù)合形不斷向最優(yōu)點靠攏，最后搜索到約束優(yōu)化問題的最優(yōu)解。一、復(fù)合形法1.復(fù)合形頂點數(shù)K的選擇

小取大值,

大取小值建議:2)為避免降維,K應(yīng)取大些;但過大,計算量也大.

1)為保證迭代點能逼近極小點,應(yīng)使二、初始復(fù)合形的產(chǎn)生對于二維問題，復(fù)合形法的搜索原理，如圖2-33所示。圖2-33

復(fù)合形法原理

映射軸心壞點映射點

所以，復(fù)合形法的迭代過程實際就是通過對復(fù)合形各頂點的函數(shù)值計算與比較，反復(fù)進(jìn)行點的映射與復(fù)合形的收縮，使之逐步逼近約束問題最優(yōu)解的。（2-60）根據(jù)上述復(fù)合形法的基本思想，對于求解的優(yōu)化問題時，采用復(fù)合形法來求解，需分兩步進(jìn)行：

第一步是在設(shè)計空間的可行域

內(nèi)產(chǎn)生k個初始頂點構(gòu)成一個不規(guī)則的多面體，即生成初始復(fù)合形。一般取復(fù)合形頂點數(shù)為：。

第二步進(jìn)行該復(fù)合形的調(diào)優(yōu)迭代計算。通過對各頂點函數(shù)值大小的比較，判斷下降方向，不斷用新的可行好點取代壞點，構(gòu)成新的復(fù)合形，使它逐步向約束最優(yōu)點移動、收縮和逼近，直到滿足一定的收斂精度為止。1.初始復(fù)合形的生成

通常，初始復(fù)合形的生成方法主要采用如下兩種方法：生成初始復(fù)合形，實際就是要確定k個可行點作為初始復(fù)合形的頂點。

(1)人為給定k個初始頂點

可由設(shè)計者預(yù)先選擇k個設(shè)計方案，即人工構(gòu)造一個初始復(fù)合形。k個頂點都必須滿足所有的約束條件。

(2)給定一個初始頂點，隨機(jī)產(chǎn)生其它頂點

在高維且多約束情況下，一般是人為地確定一個初始可形點

，其余個頂點可用隨機(jī)法產(chǎn)生，即(2-61)式中，——復(fù)合形頂點的標(biāo)號；

——設(shè)計變量的標(biāo)號，表示點的坐標(biāo)分量；

——設(shè)計變量的解域或上下界；

——[0，1]區(qū)間內(nèi)服從均勻分布偽隨機(jī)數(shù)。

用上述方法隨機(jī)產(chǎn)生的k-1個頂點，雖然可以滿足設(shè)計變量的邊界約束條件，但不一定是可行點，所以還必須逐個檢查其可行性，并使其成為可行點。

設(shè)已有q(1≤q≤k)個頂點滿足全部約束條件，第q+1點X(q+1)不是可行點，則先求出q個頂點的中心點(2-62)然后將不滿足約束條件的點向中心點

靠攏，即(2-63)

若新得到的仍在可行域外，則重復(fù)上式(2-63)進(jìn)行調(diào)整，直到點成為可行點為止。

然后，同樣處理其余諸點，使其全部進(jìn)入可行域內(nèi)，從而構(gòu)成一個所有頂點均在可行域內(nèi)的初始復(fù)合形。

這個新點X(q+1)實際就是X(s)與原X(q+1)兩點連線的中點，如圖。若新的X(q+1)點仍為非可行點，按上式再產(chǎn)生X(q+1)，使它更向X(s)靠攏，最終使其成為可行點。

按照這個方法，同樣使X(q+2)、X(q+3)、……X(K)都變?yōu)榭尚悬c，這K個點就構(gòu)成了初始復(fù)合形。2.復(fù)合形法的調(diào)優(yōu)迭代

初始復(fù)合形生成后，其調(diào)優(yōu)迭代計算按下述步驟進(jìn)行：(1)計算初始復(fù)合形各頂點的函數(shù)值，選出好點、壞點、次壞點：

(2)計算除壞點X(H)外其余k-1個頂點的幾何中心點(映射軸心）：

并檢驗映射軸心X(S)點是否在可行域內(nèi)。如果X(S)是可行點，則執(zhí)行下步(3)

；否則轉(zhuǎn)第(4)步。

(3)沿X(H)

和X(S)

連線方向求映射點X(R)：

(2-64)

式中，稱映射系數(shù)，通常取。然后，檢驗X(R)可行性，若為非可行點，將減半，重新計算，直到成為可行點。

(次壞點)X(R)X(R)X(R)

(4)若X(S)在可行域外（非可行點），此時D可能是非凸集，如圖2-34所示。此時利用映射軸心X(S)和X(L)重新確定一個區(qū)間，在此區(qū)間內(nèi)重新隨機(jī)產(chǎn)生k個頂點構(gòu)成復(fù)合形。圖2-34可行域為非凸集

重新構(gòu)成復(fù)合形后，重復(fù)第(1)、(2)步，直到成為可行點為止。

(2-66)若

則取

(2-65)新的區(qū)間如圖中虛線所示：其邊界值若則取

始終取小

(5)計算映射點的目標(biāo)函數(shù)值f(X(R))，若f(X(R))<f(X(H))，則用映射點替換壞點，構(gòu)成新的復(fù)合形，完成一次調(diào)優(yōu)迭代計算，并轉(zhuǎn)向第(1)步；否則繼續(xù)下一步。

(6)若f(X(R))>f(X(H))，則將映射系數(shù)α減半，重新計算映射點。如果新的映射點X(R)既為可行點，又滿足f(X(R))<f(X(H))，即代替X(H)，完成本次迭代；否則繼續(xù)將α減半，直到當(dāng)α值減到小于預(yù)先給定的一個很小正數(shù)

(例如)時，仍不能使映射點優(yōu)于壞點，則說明該映射方向不利，應(yīng)改用次壞點X(G)替換壞點再行映射。(7)進(jìn)行收斂判斷。

若滿足

時可結(jié)束迭代計算。此時復(fù)合形中目標(biāo)函數(shù)值最小的頂點即為該約束優(yōu)化問題的最優(yōu)點。為復(fù)合形所有頂點的點集中心，即(2-67)(2-68)

復(fù)合形法的迭代計算框圖，如圖2-35所示。圖2-35復(fù)合形法的計算框圖

懲罰函數(shù)法是一種用來求解約束優(yōu)化問題的間接解法。

該算法的基本思想是：將約束優(yōu)化問題的數(shù)學(xué)模型改造成為無約束的數(shù)學(xué)模型，然后按無約束問題進(jìn)行一系列的無約束最優(yōu)化求解，直到求得原問題的最優(yōu)解?！?/p>

內(nèi)點懲罰函數(shù)法（內(nèi)點法）●外點懲罰函數(shù)法（外點法）●混合懲罰函數(shù)法（混合法）二、懲罰函數(shù)法根據(jù)所構(gòu)造的目標(biāo)函數(shù)的形式不同，決定了搜索點是在可行域內(nèi)、或在可行域外，因而該算法又分為如下三種：——懲罰項——懲罰因子懲罰函數(shù)一系列則構(gòu)造的新目標(biāo)函數(shù)為：式中：為懲罰因子，它是一遞減正數(shù)序列，即其中，c為遞減系數(shù)，0<c<1；為以gu(X)為函數(shù)的復(fù)合函數(shù)，或稱與不等式約束有關(guān)的懲罰項。

1.內(nèi)點懲罰函數(shù)法（內(nèi)點法）

內(nèi)點罰函數(shù)法適合于求解不等式約束優(yōu)化問題，即:

對于內(nèi)點罰函數(shù)法，求解過程要求保證：

(1)初始點和所求得的序列最優(yōu)點

，都應(yīng)是可行點；

(2)求解到最后，序列最優(yōu)點應(yīng)逼近最優(yōu)點X*。總的來說，內(nèi)點法的迭代過程始終限制在可行域內(nèi)，所求得的系列無約束優(yōu)化問題的優(yōu)化解總是可行解，是從可行域內(nèi)部逐漸逼近原約束優(yōu)化問題的最優(yōu)解。由于等式約束優(yōu)化問題不存在可行域空間，不適用。在求解過程中，針對不同的

，就有一個與之對應(yīng)的極小值點，隨著

的減小，使求得的也逐步向原問題的最優(yōu)點逼近。所以該方法也稱為“序列無約束極小化”方法。然后對新目標(biāo)函數(shù)按無約束問題求解，即圍墻函數(shù)(3)構(gòu)造懲罰函數(shù)

(4)求解無約束優(yōu)化問題，得；

(5)進(jìn)行收斂判斷，若滿足或則令，停止迭代計算，輸出最優(yōu)解；否則轉(zhuǎn)下步；

(6)取，以作為新的初始點，置轉(zhuǎn)步驟(3)繼續(xù)迭代。

內(nèi)點罰函數(shù)法的迭代步驟如下：

(1)在可行域內(nèi)確定一個初始點；（最好不要鄰近任何約束邊界）

(2)給定初始罰因子、懲罰因子遞減系數(shù)C和收斂精度ε；置k=0；

內(nèi)點法的程序框圖，見圖2-36。

圖2-36內(nèi)點法程序框圖

在內(nèi)點法中，初始罰因子的選擇很重要。根據(jù)經(jīng)驗，一般可取=1~50，但多數(shù)情況是取=1。也有建議按初始懲罰項作用與初始目標(biāo)函數(shù)作用相近原則來確定值，即

遞減系數(shù)C一般取為：C=0.1～0.5，常取0.1。

例2-1

試用內(nèi)點罰函數(shù)法求解如下優(yōu)化問題：解：此題的標(biāo)準(zhǔn)解為：。根據(jù)內(nèi)點法的基本思想，首先構(gòu)造罰函數(shù)，按式（2-71）可寫出：可以看出由兩部分組成，即，其中：內(nèi)點法例題即：是原目標(biāo)函數(shù)，為一直線；

是一族倒數(shù)曲線，當(dāng)。對求導(dǎo)并令其一階導(dǎo)數(shù)為零，即可求得其無約束極值點：：懲罰函數(shù)值為：當(dāng)選用不同的懲罰因子時，可得到不同的極值點及Φ曲線。取遞減數(shù)列，由上式可得序列如下：

上圖表示出取值不同時所得到的約束最優(yōu)點逐步逼近原問題最優(yōu)點的情形。

由上圖可以看出，當(dāng)懲罰因子為一個遞減數(shù)列時，無約束極值點

離約束最優(yōu)解愈來愈近，當(dāng)即得到了真正的約束最優(yōu)解。此時，罰函數(shù)也收斂于原目標(biāo)函數(shù)的最優(yōu)值，即

外點罰函數(shù)法適用于具有等式和不等式約束優(yōu)化問題。

該算法搜索策略與內(nèi)點罰函數(shù)法相似，不同點是將懲罰函數(shù)的定義在可行域的外部，從可行域外部逐漸逼近原約束優(yōu)化問題的最優(yōu)解。對于不等式約束問題：取外點罰函數(shù)的形式為其懲罰項的含義如下：(2-73)

上式說明，當(dāng)X是可行點時，懲罰項為零。也就是說當(dāng)極小化懲罰函數(shù)時，X由不可行點迭代成可行點，此時，懲罰函數(shù)

將與原目標(biāo)函數(shù)

等價。此時懲罰函數(shù)的最優(yōu)可行點，也將是原目標(biāo)函數(shù)的最優(yōu)點。2.外點罰函數(shù)法（X是可行點，可行域內(nèi)）（X是非可行點）外點罰函數(shù)中的罰因子是一遞增數(shù)列，即

對于等式約束的優(yōu)化問題，取外點罰函數(shù)的形式為對于同時具有不等式和等式約束問題，其罰函數(shù)的表達(dá)式為(2-75)

(2-74)

在外點罰函數(shù)法中，為保證罰因子

為遞增數(shù)列，取式中:c'為遞增系數(shù)，c'>1。外點罰函數(shù)的程序計算框圖，見圖2-37。

外點罰函數(shù)法的迭代步驟與內(nèi)點法基本相同。圖2-37外點法的程序框圖

例題看書p75

混合罰函數(shù)法是將內(nèi)點法和外點法的罰函數(shù)形式結(jié)合起來，解決同時具有等式和不等式約束的問題。其罰函數(shù)的表達(dá)式為(2-76)式中，為遞減的正數(shù)序列；為遞增的正數(shù)序列。

也可將兩個懲罰因子加以合并，取和，得以下常用的混合罰函數(shù)：

(2-77)

式中，為一遞減的正數(shù)序列。

可見，混合法與外點法一樣，可用來求解既含不等式約束又含等式約束的約束優(yōu)化問題。

3.

混合罰函數(shù)法

在工程優(yōu)化設(shè)計問題中，如果優(yōu)化模型中的目標(biāo)函數(shù)僅涉及一項設(shè)計指標(biāo)，稱為單目標(biāo)優(yōu)化問題；如果涉及兩項及兩項以上多個設(shè)計指標(biāo)，則稱為多目標(biāo)優(yōu)化問題。

例如在圖2-41所示的港口門座式起重機(jī)變幅機(jī)構(gòu)的優(yōu)化設(shè)計中，希望在四桿機(jī)構(gòu)變幅行程中能達(dá)到的幾項要求有：

(1)象鼻梁E點落差△y盡可能小(要求E點走水平直線)；

(2)E點位移速度的波動△v盡可能小(要求E點的水平分速度的變化最小，以減小貨物的晃動)；

(3)變幅中驅(qū)動臂架的力矩變化量△M盡可能小(即貨物對支點A所引起的傾覆力矩差要盡量小)。圖2-41門座式起重機(jī)變幅四桿機(jī)構(gòu)2.6多目標(biāo)優(yōu)化方法

這種在優(yōu)化設(shè)計中，同時要求幾項設(shè)計指標(biāo)達(dá)到最優(yōu)值的問題，就是多目標(biāo)優(yōu)化設(shè)計問題。多目標(biāo)優(yōu)化設(shè)計問題的數(shù)學(xué)模型的一般表達(dá)式為：式中：，是q維目標(biāo)向量（q個目標(biāo)函數(shù)）。

在單目標(biāo)函數(shù)的最優(yōu)化過程中，可通過簡單比較函數(shù)值的大小的方法去尋優(yōu)，獲得優(yōu)化問題的最優(yōu)設(shè)計方案。(2-78)

而在多目標(biāo)函數(shù)的最優(yōu)化過程中，要使幾項分目標(biāo)函數(shù)同時都達(dá)到最優(yōu)，一般是比較難以實現(xiàn)的。因此多目標(biāo)問題的優(yōu)化遠(yuǎn)比單目標(biāo)函數(shù)的最優(yōu)化要復(fù)雜得多。在多目標(biāo)優(yōu)化方法中，較常用的方法有：通常，在多目標(biāo)問題求優(yōu)過程中，當(dāng)各分目標(biāo)函數(shù)的優(yōu)化出現(xiàn)不一致時,一般是在各分目標(biāo)的最優(yōu)值之間進(jìn)行協(xié)調(diào)，相互作出一些適當(dāng)?shù)男拚?，以取得一個對各分目標(biāo)函數(shù)都能接受又比較好的最佳方案。這是多目標(biāo)優(yōu)化問題常用的處理方法。

加權(quán)組合法功效系數(shù)法主要目標(biāo)法等。

加權(quán)組合法的基本思想是：將多目標(biāo)問題的各項分目標(biāo)函數(shù)按下式組合成統(tǒng)一的目標(biāo)函數(shù)：(2-79)

和以下約束優(yōu)化問題：

(2-80)

以此問題的最優(yōu)解作為原多目標(biāo)優(yōu)化問題的一個相對最優(yōu)解。這種求解多目標(biāo)優(yōu)化問題的方法就是線性加權(quán)組合法。

為加權(quán)因子，是一個大于零的正數(shù)，其值決定于各項分目標(biāo)的重要程度及其數(shù)量級大小。一、加權(quán)組合法

若取，則稱均勻計權(quán)，表示各項分目標(biāo)同等重要。否則，可以用規(guī)格化加權(quán)處理，即?。?-81）以表示各分目標(biāo)在該項優(yōu)化設(shè)計中所占的相對重要程度。

在加權(quán)組合法中，加權(quán)因子選擇得合理與否，將直接影響優(yōu)化設(shè)計的結(jié)果。目前，較為實用的加權(quán)方法有：（１）容限加權(quán)法設(shè)已知各分目標(biāo)函數(shù)值的變動范圍為則稱為各目標(biāo)容限。取加權(quán)因子為：（2-82）

（2-83）（2-84）這樣選擇加權(quán)因子將起到平衡各目標(biāo)數(shù)量級的作用。（２）分析加權(quán)法

為能兼顧各項分目標(biāo)的重要程度及其數(shù)量級的影響，可將加權(quán)內(nèi)容包括本征權(quán)和校正權(quán)兩部分，即各分目標(biāo)的可由兩個因子的乘積組成，即式中：本征權(quán)的加權(quán)因子反映各項分評價指標(biāo)的重要性；

校正權(quán)的加權(quán)因子用于調(diào)整各目標(biāo)在數(shù)量級上差別的影響，并在優(yōu)化設(shè)計過程中起逐步加以校正的作用。該校征權(quán)因子值可取：(2-85)(2-86)

即目標(biāo)函數(shù)的靈敏度越大，則值越大，則相應(yīng)的校正權(quán)因子值取值小，否則，校正權(quán)因子值要求大一點，使各分目標(biāo)函數(shù)一起變化。

首先將每個分目標(biāo)函數(shù)都用一個稱為功效系數(shù)表示該項設(shè)計指標(biāo)的好壞，該功效系數(shù)

是定義于間的函數(shù)。

總功效系數(shù)η值表示該設(shè)計方案的優(yōu)劣。因此，最優(yōu)設(shè)計方案應(yīng)是：功效系數(shù)法的基本思想是：

在將每項分目標(biāo)化為相應(yīng)的功效系數(shù)后，則總功效系數(shù)η是各分項功效系數(shù)的幾何平均值，即（2-87）

二、功效系數(shù)法當(dāng)時，表示第j個目標(biāo)的效果達(dá)到最好；反之，當(dāng)時，表示它的效果很差，實際這個方案不能接受。

這樣，當(dāng)

時，表示多目標(biāo)優(yōu)化問題取得最理想的設(shè)計方案；反之，當(dāng)

時，則表示該設(shè)計方案是不能接受的，這時必有某項分目標(biāo)函數(shù)的功效系數(shù)。其中，圖(a):表示與值成正比的功效系數(shù)函數(shù)；圖(b):表示與值成反比的功效系數(shù)函數(shù)；圖(c):表示與值過大或過小都不行的功效系數(shù)函數(shù)。由上圖可知，功效系數(shù)函數(shù)

為一直線函數(shù)。當(dāng)知某一目標(biāo)函數(shù)值時就可得到相應(yīng)于它的功效系數(shù)函數(shù)值。圖2-42功效系數(shù)的函數(shù)曲線

圖2-4