車輛優(yōu)化設(shè)計理論與實踐課件：多目標(biāo)及離散變量優(yōu)化方法 -

車輛優(yōu)化設(shè)計理論與實踐多目標(biāo)及離散變量優(yōu)化方法

概述統(tǒng)一目標(biāo)法

協(xié)調(diào)曲線法

分層序列法及寬容分層序列法

離散變量優(yōu)化方法

5.1概述在工程實際中，經(jīng)常會碰到多個設(shè)計指標(biāo)同時作為評價指標(biāo)。這時若進行優(yōu)化設(shè)計,就不能用單一的目標(biāo)函數(shù),而是用這些評價指標(biāo)構(gòu)成的多目標(biāo)函數(shù),這種優(yōu)化問題就是多目標(biāo)優(yōu)化設(shè)計。

由于多目標(biāo)優(yōu)化設(shè)計的目標(biāo)函數(shù)由多個目標(biāo)函數(shù)構(gòu)成,其目標(biāo)函數(shù)可用多目標(biāo)函數(shù)構(gòu)成的一個向量來表示，多目標(biāo)優(yōu)化的數(shù)學(xué)模型可表示為：

（5-1）式中稱為向量目標(biāo)函數(shù)。而表示目標(biāo)極小化數(shù)學(xué)模型用向量形式的簡寫，公式，為設(shè)計變量應(yīng)滿足所有約束條件。多目標(biāo)優(yōu)化問題與單目標(biāo)優(yōu)化問題相比較可以看出，在單目標(biāo)優(yōu)化問題中得到的是最優(yōu)解，而在多目標(biāo)優(yōu)化問題中得到的只是非劣解。而且，非劣解往往不只一個。如何求得能接受的最好非劣解，關(guān)鍵是要選擇某種形式的折衷。所謂非劣解（或稱有效解，Pareto最優(yōu)解），是指若有m個目標(biāo),當(dāng)要求(m-1）個目標(biāo)值不變壞時，找不到一個X,使得另―個目標(biāo)函數(shù)值比更好，則將此作為非劣解顯然，多目標(biāo)優(yōu)化問題只有當(dāng)求得的解是非劣解或弱非劣解時才有意義，劣解是沒有意義的，而絕對最優(yōu)解存在的可能性很小。多目標(biāo)優(yōu)化的求解方法甚多，其中最主要的有兩大類。一類是直接求出非劣解，然后從中選擇較好解。另一大類是將多目標(biāo)優(yōu)化問題求解時作適當(dāng)?shù)奶幚?。屬于這一大類求解的前一種方法有：主要目標(biāo)法，線性加權(quán)和法，理想點法，平方和加權(quán)法，分目標(biāo)乘除法，功率系數(shù)法——幾何平均法，極大極小法等。屬于后一種的有分層序列法等。此外還有其他類型的方法，如協(xié)調(diào)曲線法等等。下面簡要介紹幾種常用的方法。5.2統(tǒng)一目標(biāo)法統(tǒng)一目標(biāo)法又稱為綜合目標(biāo)法。它是通過一定方法，將多目標(biāo)優(yōu)化問題中的目標(biāo)函數(shù)轉(zhuǎn)化為統(tǒng)一的目標(biāo)函數(shù)或綜合目標(biāo)函數(shù)作為該多目標(biāo)優(yōu)化問題的評價函數(shù)，這樣，就能用單目標(biāo)函數(shù)優(yōu)化方法求解。其轉(zhuǎn)化方法有線性加權(quán)和法、極大極小法等，下面逐一講解。用與(=1,2,,)的線性組合構(gòu)成一個評價函數(shù)將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，即求評價函數(shù)的最優(yōu)解，它就是原多目標(biāo)優(yōu)化問題式（5-1）的解。使用這個方法的難處在于如何找到合理的權(quán)系數(shù)，權(quán)系數(shù)選取，反映了對各分目標(biāo)的不同估價、折衷，故應(yīng)根據(jù)具體情況作出處理。下面介紹一種確定權(quán)系數(shù)的方法。按此法，多目標(biāo)優(yōu)化問題的評價函數(shù)的極小化如式（5-5）所示。其中線性加權(quán)法基本思路是把多目標(biāo)優(yōu)化問題式(5-1)中各個目標(biāo)函數(shù)，…，依其量級和在設(shè)計中的重要程度分配相應(yīng)的加權(quán)因子，…，，并有5.2.1線性加權(quán)法對于多目標(biāo)優(yōu)化問題,可用這樣的思想求解，即考慮對各個目標(biāo)最不利情況下求出最有利的解。就是對多目標(biāo)極小化問題采用各個目標(biāo)（i=1,…,）中的最大值作為評價函數(shù)的函數(shù)值來構(gòu)造它。即?。?-8）為評價函數(shù)，其中f=。對式（5-8）求優(yōu)化解就是進行如下形式的極小化（5-9）將上述問題的優(yōu)化解作為多目標(biāo)優(yōu)化問題的解。由式（5-8）、式（5-9）可知；該法特點是對各目標(biāo)函數(shù)作極大值選擇后,再在可行域內(nèi)進行極小化，故稱極大極小法，對n=1、=2的情況，用極大極小法求的方法如圖5-2所示。其中粗線表示對函數(shù)，取較大值。5.2.2極大極小法

圖5-2極大極小法求解示意圖若考慮用加權(quán)系數(shù)（i=1，…），對應(yīng)于分目標(biāo)表示各目標(biāo)函數(shù)重要程度，則式（5-8）可寫成更一般的加權(quán)系數(shù)形式為式（5-9）可寫為當(dāng)式中﹥0（i=1，…）時求解式（5-11）所得優(yōu)化解為多目標(biāo)優(yōu)化問題的弱有效解。若引人一個變量，令由上式可知則式（5-11）可轉(zhuǎn)化為增加一個變量和個約束條件的如下形式的單目標(biāo)極小化問題由此可知，對式（5-13）求出最優(yōu)解[,],其中的即為原多目標(biāo)極小化問題的弱有效解。（5-10）（5-11）（5-13）理想點法是以各分目標(biāo)函數(shù)作為各個目標(biāo)各自的理想值，若能使各個目標(biāo)盡可能接近各自的理想值，那么，就可以求出較好的非劣解。根據(jù)這個思想，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為求單目標(biāo)函數(shù)（評價函數(shù)）的極值。具體的做法是先分別求出各個目標(biāo)函數(shù)最優(yōu)解和相應(yīng)的最優(yōu)點。然后構(gòu)造出理想點的評價函數(shù)為:求此評價函數(shù)的最優(yōu)解，即是求原多目標(biāo)優(yōu)化問題的最優(yōu)解。式中用相除是使之無量綱化。5.2.3

理想點法與平方和加權(quán)法若在理想點法的基礎(chǔ)上引入權(quán)系數(shù)，構(gòu)造的評價函數(shù)為（5-15）此即為平方和加權(quán)法。

求得評價函數(shù)的最優(yōu)解，就是原多目標(biāo)優(yōu)化問題式（5-1）的解（5-16）評價函數(shù)也可采用加權(quán)極大模型式對上述評價函數(shù)求最優(yōu)解，有若令

=由該式還可知

（5-17）設(shè)上述問題的優(yōu)化解為[，],則即為式（5-17）的優(yōu)化解

式（5-17）可轉(zhuǎn)化為如下等價的輔助問題求解上述優(yōu)化模型的方法可用分目標(biāo)乘除法。即求解

（5-19）式中，

（5-20）以上所述利用極小化乘除分目標(biāo)函數(shù)求解式(5-19）模型的方法，實際上是對它構(gòu)造了評價函數(shù)=多目標(biāo)優(yōu)化問題中，有一類屬于多目標(biāo)混合優(yōu)化問題，其優(yōu)化模型為5.2.4

分目標(biāo)乘除法多目標(biāo)優(yōu)化問題中，各個單目標(biāo)的要求不全相同。為了在評價函數(shù)中反映這些不同的要求，可引人功效函數(shù)。的取值方法為：通常為0～1之間的某個值。當(dāng)之值最滿意時，可取=1；當(dāng)?shù)闹挡粷M意時，則取為0；其他情況應(yīng)視的值取0～1的中間數(shù)。當(dāng)對應(yīng)于各分目標(biāo)函數(shù)值的確定后，對所有取其幾何平均值，組成評價函數(shù)5.2.5功效系數(shù)法——幾何平均法（5-22）功效函數(shù)值即功效系數(shù)，按照對目標(biāo)函數(shù)的不同要求，功效函數(shù)可分為三種類型:1）當(dāng)越大，越大；越小，越小。該類功效函數(shù)適用于要求目標(biāo)函數(shù)越大越好。2）當(dāng)越小，越大；越大，越小。該類功效函數(shù)適用于要求目標(biāo)函數(shù)越小越好3）當(dāng)取的值越靠近預(yù)先確定的適當(dāng)值時，就越大；否則就越小。功效系數(shù)的確定方法有：直線法、折線法和指數(shù)法。1）直線法。該法需事先定出=1時的和=0時的,在-坐標(biāo)上將此二點連接后即可求得與相應(yīng)的值。2)折線法。該法需先確定的兩個臨界值與。前者為比較滿意的目標(biāo)函數(shù)值；后者為可接受與不可接受的目標(biāo)函數(shù)值的分界值。當(dāng)前者比后者還要差0.5～1倍，即為時，令=0；當(dāng)=時,令=03；當(dāng)=時，令=0.7；當(dāng)為理想時，令=1。在坐標(biāo)系上將上述這些特殊點用直線相連，就形成了折線形的功效系數(shù)圖。當(dāng)處在與之外時，可分別取為1或03)指數(shù)法。該法對前述第1）類功效函數(shù)的選取表達式可表示為

c=e（5-23）其中，可以用下法來確定：設(shè)取為某一剛合格值時,c=0.37；f

為某一剛不合格值時c=0.07，將將上述值代人式（5-23），可解得c=e;c=e由上二式可得由上二式可解得代人式（5-23）可得c=實踐證明，功效系數(shù)法有如下優(yōu)點：可直接按所要求的性能指標(biāo)來評價函數(shù)，非常直觀。試算后調(diào)整方便。只要有一個性能指標(biāo)不能接受時，則相應(yīng)的功效系數(shù)為零，從而使評價函數(shù)也為零。方案被否決。這正是實際問題所要求的。它可以避免某一目標(biāo)函數(shù)值不可接受而評價函數(shù)值卻較好，使優(yōu)化計算引人歧途。此法還可以處理目標(biāo)函數(shù)值既不希望太大，且又不希望太小，而希望取某一適當(dāng)值的情況。這也是其他優(yōu)化方法難以對付的一種情況。該法的缺點是事先要求明確目標(biāo)函數(shù)值的取值范圍。對某些問題，若難以確定取值范圍時，此法就不適用。例5-2

設(shè)計一曲柄搖桿機構(gòu)，要求實現(xiàn)搖桿擺角

=60°，最大壓力角盡可能小，以改善機構(gòu)的傳力性能；極位夾角盡可能大，以提高機構(gòu)的急回性能。如圖5-6所示，設(shè)、、、分別為該四桿機構(gòu)的桿長。令=1,=a,=b,=c,按上述設(shè)計要求，可列出該設(shè)計的分目標(biāo)函數(shù)分別為：

圖5-6曲柄搖桿機構(gòu)示意圖1）為極位夾角，希望越大越好，其取值范圍為17°～0°,=17°時=1；=0°時=0。2）為最大壓力角，希望越小越好，其取值范圍0°～55°，=0°時，=1；=55°時，=0。3）為擺角，希望越接近60°越好，其取值范圍59°～61°，=60°時，=1；=59°時，=0或=61°時=0。按上述取值范圍,用直線法可做出圖5-7所示的求功效系數(shù)圖。代入式（5-22)得該多目標(biāo)優(yōu)化問題的評價函數(shù)為C=經(jīng)優(yōu)化可解出該多目標(biāo)優(yōu)化問題的解為：當(dāng)=100mm時,=533.33mm,=200mm,

=500mm。若取=100mm，=352.60mm，=203.62mm,=394.70mm，這時=0°即=0°，此時=0，則c=0，表示此方案不能被接受。圖5-7直線法功效系數(shù)圖5.3協(xié)調(diào)曲線法這種方法主要是用來解決設(shè)計目標(biāo)互相矛盾的多目標(biāo)優(yōu)化設(shè)計問題的。現(xiàn)在以兩個目標(biāo)的優(yōu)化問題來說明這種方法的基本原理。在這兩個目標(biāo)中，一個目標(biāo)的函數(shù)值減小，將導(dǎo)致另一個目標(biāo)函數(shù)值的增大，這就是一對互相矛盾的設(shè)計目標(biāo)。這種設(shè)計目標(biāo)互相矛盾的優(yōu)化設(shè)計問題如圖5-8所示.圖中表示出兩個目標(biāo)函數(shù)的等值線和兩個不等式約束的約束面。顯然，兩個目標(biāo)函數(shù)各自的最優(yōu)解一個是T點和另一個是P點。設(shè)從可行域中的一個設(shè)計方案R點出發(fā)來考察，當(dāng)保持不變，極小化可得到S點，即從R點起，沿著等值線向約束面移動，得到不斷改善，直到S點。另一方面，當(dāng)保持不變時，極小化可得到Q點，即從R點起，沿著等值線向約束面移動，得到不斷改善，直到Q點。根據(jù)圖5-8繪出的兩個目標(biāo)函數(shù)值的關(guān)系曲線，如圖5-9所示。顯然，在曲線TP上的QS段中任意一個設(shè)計方案都比R點好，因為目標(biāo)函數(shù)值減小了。TP這條曲線包含兩個設(shè)計目標(biāo)全部最佳方案的調(diào)整范圍，所以將TP曲線稱協(xié)調(diào)曲線圖5-8兩個目標(biāo)函數(shù)的等值線和約束邊界

圖5-9協(xié)調(diào)曲線下面舉一個恒載下動壓滑動軸承優(yōu)化設(shè)計的例子來說明協(xié)調(diào)曲線法應(yīng)用的大致情況。例5-3設(shè)軸頸直徑為D，軸承長度為L，每分鐘轉(zhuǎn)數(shù)為n、徑向載荷為F，軸承徑向間隙為C（近似等于，為軸承孔直徑），潤滑油粘度為。一般動壓滑動軸承的工作能力和壽命主要決定于供油流量

Q和溫升。供油流量不足，則不能產(chǎn)生油膜，有足夠的流量才能補充泄漏量，并由泄漏的油帶走一部分熱量而不致發(fā)生過熱現(xiàn)象。另一方面，軸承溫升高會減小油的粘度，油的粘度減小又使泄漏量增加。所以，實際設(shè)計中，要求流量和溫升最小，顯然，這是相互矛盾的兩目標(biāo)優(yōu)化設(shè)計問題。如果選定設(shè)計變量為，C和，則動壓滑動軸承優(yōu)化設(shè)計的數(shù)學(xué)模型是求s.t.使式中——壓力油膜厚度

——單位壓力

-——潤滑油的動力粘度為了使這個兩目標(biāo)優(yōu)化設(shè)計問題獲得滿意的設(shè)計方案，借助于協(xié)調(diào)曲線來求解，圖5-10是按計算結(jié)果作出的油的流量與溫升的協(xié)調(diào)曲線，要在這條曲線上選取最滿意的設(shè)計方案，可根據(jù)協(xié)調(diào)曲線相應(yīng)點作出各個主要參數(shù)的變化曲線來分析，如圖5-11所示。從這些曲線可以看出，相應(yīng)于協(xié)調(diào)曲線上的點，是一個好的設(shè)計方案。由圖可知，從點向左減小，軸承間隙急劇增大，間隙過大將導(dǎo)致軸的軸線運轉(zhuǎn)不穩(wěn)定并產(chǎn)生噪聲。若從點向右增大，則油的粘度增大且功率損耗亦增大，這是對軸承性能不利的。所以點無疑是一個較理想的設(shè)計方案。圖5-10流量與溫升協(xié)調(diào)曲線圖5-11

主要參數(shù)變化曲線5.4分層序列法及寬容分層序列法

分層序列法的基本思想是將多目標(biāo)優(yōu)化問題式（5-1）中的個目標(biāo)函數(shù)分清主次，按重要程度逐一排除，然后依次對各個目標(biāo)函數(shù)求最優(yōu)解，不過后一目標(biāo)應(yīng)在前一目標(biāo)最優(yōu)解的集合域內(nèi)尋優(yōu)現(xiàn)在假設(shè)最重要，其次，再其次，…。首先對第一個目標(biāo)函數(shù)求解，得最優(yōu)值在第一個目標(biāo)函數(shù)的最優(yōu)解集合域內(nèi)，求第二個目標(biāo)函數(shù)的最優(yōu)值，也就是將第一個目標(biāo)函數(shù)轉(zhuǎn)化為輔助約束。即求下式的最優(yōu)值，記作

然后，再在第一、第二個目標(biāo)函數(shù)的最優(yōu)解集合域內(nèi)，求第三個目標(biāo)函數(shù)的最優(yōu)值，此時，第一、第二個目標(biāo)函數(shù)轉(zhuǎn)化為輔助約束。照此繼續(xù)進行下去，最后求第個目標(biāo)函數(shù)的最優(yōu)值，即其最優(yōu)值是，對應(yīng)的最優(yōu)點是。這個解就是多目標(biāo)優(yōu)化問題式（5-1）的最優(yōu)解。

采用分層序列法，在求解過程中可能會出現(xiàn)中斷現(xiàn)象，使求解過程無法繼續(xù)進行下去。

為此引入“寬容分層序列法”。這種方法就是對各目標(biāo)函數(shù)的最優(yōu)值放寬要求，可以事先對各目標(biāo)函數(shù)的最優(yōu)值取給定的寬容量，即這樣，在求后一個目標(biāo)函數(shù)的最優(yōu)值時，對前一目標(biāo)函數(shù)不嚴(yán)格限制在最優(yōu)解內(nèi)，而是在前一些目標(biāo)函數(shù)最優(yōu)值附近的某一范圍內(nèi)進行優(yōu)化，因而避免了計算過程的中斷。例5-4

用寬容分層序列法求解式中

若按重要程度將目標(biāo)函數(shù)排隊為：，

首先求解

得最優(yōu)點

對應(yīng)的最優(yōu)值為設(shè)給定的寬容值=0.052可得

然后求解

而得最優(yōu)點為

=1.9

這就是該兩目標(biāo)函數(shù)的最優(yōu)點

，其對應(yīng)的最優(yōu)值為

=1.948=25.5離散變量優(yōu)化方法

前面討論的優(yōu)化方法，都是針對連續(xù)變量而言的。本節(jié)將簡要介紹常見的幾種離散變量優(yōu)化方法，包括混合整數(shù)優(yōu)化方法，約束非線性混合離散變量優(yōu)化方法等。5.5.1約束非線性混合離散變量優(yōu)化的數(shù)學(xué)模型約束非線性混合離散變量優(yōu)化設(shè)計問題的數(shù)學(xué)模型，可表達為式中

（5-30）為離散變量的子集合，為全連續(xù)變量的子集合約束非線性離散變量的優(yōu)化方法有：①以連續(xù)變量優(yōu)化方法為基礎(chǔ)的方式，如圓整法，擬離散法；離散型罰函數(shù)法；②離散變量的隨機型優(yōu)化方法，如離散變量隨機試驗法；隨機離散搜索法；③離散變量搜索優(yōu)化方法，如啟發(fā)式組合優(yōu)化方法；整數(shù)梯度法；離散復(fù)合型法；④其他離散變量優(yōu)化方法，如非線性隱枚舉法；分支定界法；離散型網(wǎng)格與離散型正交網(wǎng)格法，離散變量的組合型法。下面只介紹其中幾種主要方法:（一）以連續(xù)變量優(yōu)化方法為基礎(chǔ)的方法

5.5.2約束非線性離散變量優(yōu)化方法1.整型化，離散化法（圓整法、湊整法）該法的特點是先按連續(xù)變量方法求得優(yōu)化解，然后再進一步尋找整型量或離散量優(yōu)化解，這一過程稱為整型化或離散化。

圖5-15周圍的整形點群圖5-16周圍整型點群均不在可行域內(nèi)圖5-17離較遠處整型點P為優(yōu)化點的情形設(shè)有n維優(yōu)化問題，其實型最優(yōu)點，它的n個實型分量為(i=1，2，…，n)，則的整數(shù)部分（或它的偏下一個標(biāo)準(zhǔn)量）[]和整數(shù)部分加1即[]+1（或它的偏上一個標(biāo)準(zhǔn)量)，便是最接近的兩個整數(shù)（或離散型）分量。由這些整型分量的不同組合，便構(gòu)成了最鄰近于實型最優(yōu)點的兩個整型分量及相應(yīng)的一組整型點群[]（t=1,2,…，2；n為變量維數(shù)）。該整型點群包含有2個設(shè)計點，在整型點群中,可能有些點不在可行域內(nèi)，應(yīng)將它們剔除。在其余可行域內(nèi)的若干整型點中選取一個目標(biāo)函數(shù)值最小的點作為最優(yōu)的整型點給予輸出。圖5-15是二維的例子，在實型量最優(yōu)點周圍的整型點群有ABCD四點，圖中B點在域外，A、D、C三點為在域內(nèi)的整型點群。分別計算其目標(biāo)函數(shù)。由圖中等值線可看出，其最優(yōu)整型點是C點，它即為最優(yōu)整型設(shè)計點[]。但這樣做有

時不一定行得通，因為連續(xù)變量的最優(yōu)點通常處于約束邊界上，在連續(xù)變量最優(yōu)點附近湊整所得的設(shè)計點有可能均不在可行域內(nèi)，如圖5-16所示。顯然，在這種情況下，采用連續(xù)變量優(yōu)化點附近湊整法就可能得不到一個可行設(shè)計方案。另一方面，這種簡單的湊整法是基于一種假設(shè)，即假設(shè)離散變量的最優(yōu)點是在連續(xù)變量最優(yōu)點附近。然而這種假設(shè)并非總能成立。如圖5-17所示,按上述假設(shè)，在連續(xù)變量最優(yōu)點附近湊整得到Q點，該點雖是可行點，但并非離散變量的最優(yōu)點。從圖中可見，該問題離散變量最優(yōu)點應(yīng)是離較遠的P點，而且如果目標(biāo)函數(shù)與約束函數(shù)的非線性越嚴(yán)重，這種情況越易出現(xiàn)。這些情況表明，湊整法雖然簡便，但不一定能得到理想的結(jié)果。2.擬離散法該法是在求得連續(xù)變量優(yōu)化解后，不是用簡單的圓整方法來尋優(yōu)，而是在點附近按一定方法進行搜索來求得優(yōu)化離散解。（1）交替查點法（Luns法）該法適用于全整數(shù)變量優(yōu)化問題，其優(yōu)化離散解的搜索方法為：

1）先按連續(xù)變量求得優(yōu)化解，并將它圓整到滿足約束條件的整數(shù)解上。

2）依次將每個圓整后的優(yōu)化分量[]加1，檢查該點是否為可行點，然后僅保留目標(biāo)函數(shù)值為最小的點；重復(fù)此過程，直到可行的不再增大為止。

3）將一個分量加1，其余n-1個分量依次減1，如將增加到+1，再將減到，但暫不做代換，繼續(xù)此循環(huán)，將減到，也暫不做代換，直到繼續(xù)循環(huán)到為止；最后選擇目標(biāo)函數(shù)值作為最小的點去替換舊點。再依次增大、，直到，重復(fù)上述循環(huán)。最終比較目標(biāo)函數(shù)值的大小，找到優(yōu)化解，即認(rèn)為是該問題的整數(shù)優(yōu)化解。（2）離散分量取整，連續(xù)分量優(yōu)化法（Pappas法）1）該法是針對混合離散變量問題（即變量中既含有離散分量，也含有連續(xù)分量）提出來的。該方法的步驟為：①先將連續(xù)變量優(yōu)化解圓整到最近的一個離散點[]上。②將[]的離散分量固定，對其余的連續(xù)分量進行優(yōu)化。③若得到的新優(yōu)化點可行，且滿足收斂準(zhǔn)則，則輸出優(yōu)化結(jié)果，結(jié)束。④否則，把離散分量移到鄰近的其他離散點上，再對連續(xù)分量優(yōu)化，即轉(zhuǎn)第②步。如此重復(fù)，直到附近離散點全部輪換到為止。2）對離散變量較多，而變量維數(shù)又較低（少于6時）的混合離散變量問題Pappas又提出了另一種算法。其步驟為：①求出連續(xù)變量優(yōu)化解，取整到最靠近的離散值上。②令變量的靈敏度為，它是目標(biāo)函數(shù)的增量與自變量增量的比值。即它反映了變量對目標(biāo)函數(shù)的影響程度。計算各離散變量的靈敏度，并將所有離散變量按靈敏度從大到小的順序排隊：。③先對靈敏度最小的離散變量做離散一維搜索，并使其他的離散變量，…

，固定不變。每當(dāng)搜索到一個較好的離散點時，便需要對所有連續(xù)變量優(yōu)化一次。然后，再對做一維離散搜索，此時將其余的離散變量保持不變，但對分量還要再做一次搜索。找到好的離散點后仍需對所有連續(xù)變量再次優(yōu)化。如此重復(fù)，直到為止。④由上述第③步所得終點，重新計算靈敏度并進行排隊。若與第②步結(jié)果相近，則停止計算，其終點即為優(yōu)化解。否則，若兩者相差較大，則轉(zhuǎn)第③步繼續(xù)搜索。3.離散懲罰函數(shù)法1)構(gòu)造一個具有下列性質(zhì)的離散懲罰函數(shù)項

式中——設(shè)計空間離散點的集合Marcal定義離散懲罰函數(shù)項為式中，為第j個離散變量的坐標(biāo)；是該變量允許取的第j個離散值。Gisvold定義了另一種形式的離散懲罰函數(shù)項為式中

2)將離散懲罰函數(shù)項，加到內(nèi)點法SUMT的懲罰項中，可得離散懲罰函數(shù)式中——原目標(biāo)函數(shù)；一一參數(shù)(或稱罰因干)；

——不等式約束條件；——離散項罰因子

例5-6

圖5-19所示用離散懲罰函數(shù)求解一維離散變量優(yōu)化問題。設(shè)在滿足不等式約束方程下，求目標(biāo)函數(shù)為最小的X整數(shù)優(yōu)化解。b）a）c）圖5-19離散懲罰函數(shù)求解示意圖圖5-19a、b、c分別表示不同k值時，離散罰函數(shù)圖，圖中約束函數(shù)，離散懲罰函數(shù)項。由圖可知，參數(shù)、、數(shù)值的選取直接影響著離散懲罰函數(shù)的曲線形狀。逐步減小，增加，得圖5-19a、b、c，使離散優(yōu)化點從，最終找到離散優(yōu)化解。如最初即選擇圖5-19c則有可能陷在偽優(yōu)化點，即解，找不到真正優(yōu)化解。

(二）離散變量搜索型方法屬于這類方法的有啟發(fā)式組合優(yōu)化法、整數(shù)負(fù)梯度法及離散復(fù)合型法。下面只介紹離散復(fù)合型法。其具體算法如下所述：1）在n維空間中產(chǎn)生由2n+1個初始頂點XA組成的復(fù)合形，并將每個頂點均移到附近的可行離散點上。2）將上述已產(chǎn)生的頂點XA，按目標(biāo)函數(shù)值由大到小排列。，，…，記最壞點為。3）求出除點外所有頂點XA的點集中心（又稱幾何中心），即2n個頂點的算術(shù)平均值，連接與點集中心，并以點集中心為核心，找出的反射點作為新點，并將也移到附近離散點上。4）檢查點是否可行，比較與所有頂點的目標(biāo)函數(shù)值。5）若是可行點又比點的目標(biāo)函數(shù)值好，則表示是可接受的點。用代替點，轉(zhuǎn)第2）步；否則，沿反射的反方向收縮，并確定新點。6）若用上述方法仍得不到可接受的好點，則可令（或），轉(zhuǎn)第3）步。7）當(dāng)點后，仍找不到好點，或當(dāng)復(fù)合形退化到只是一個點或一條線或一個平面時，表示算法收斂，可取此時復(fù)合形頂點中最好的頂點作為離散優(yōu)化解。（三）分支定界法

其步驟如下：1）設(shè)所討論問題為求極小化的問題，先求出原問題不計及整數(shù)或離散約束的非線性問題的連續(xù)變量解。如果所得解的各個分量正好是整數(shù)，則它即是該問題的離散優(yōu)化解，但這種機會較少。否則，其中至少有一個變量為非整數(shù)值或非離散值則轉(zhuǎn)下一步。對非整數(shù)變量，如的值為，可將它分解為整數(shù)部分和小數(shù)部分，即構(gòu)造兩個子問題,上界約束;下界約束對離散變量，若其離散值集合為，，…，，則對于分支必定存在一個下標(biāo)，使因而應(yīng)分別構(gòu)造以：為上界約束子問題；為下界約束子問題。4）將上述兩個子問題按連續(xù)變量非線性問題求優(yōu)化解。5）重復(fù)上述過程，不斷分支，并求得分支產(chǎn)生的子問題的優(yōu)化解，直至求得一個離散解為止。6）在上述求解過程中，每個節(jié)點最多能分出兩個新的節(jié)點。當(dāng)取一個可行整數(shù)解時，如果其目標(biāo)函數(shù)值小于當(dāng)前目標(biāo)函數(shù)值的上界值，則可將該值作為目標(biāo)函數(shù)的新的上界。7）當(dāng)下列情況出現(xiàn)時，則認(rèn)為相應(yīng)的節(jié)點以及它以后的節(jié)點已考查清楚了：①所得連續(xù)變量為整數(shù)可行解。且連續(xù)變量問題解的目標(biāo)函數(shù)值比當(dāng)前的目標(biāo)函數(shù)值的上界值大時；②連續(xù)變量解為不可行解。8）當(dāng)所有節(jié)點都考查清楚后，尋優(yōu)工作結(jié)束，此時最好的整數(shù)解或離散解就是該問題的離散優(yōu)化解。（四）離散變量型網(wǎng)格法1.離散變量型普通網(wǎng)格法離散變量型普通網(wǎng)格法就是以一定的變量增量為間隔，把設(shè)計空間劃分為若干個網(wǎng)格，計算在域內(nèi)的每個網(wǎng)格節(jié)點上的目標(biāo)函數(shù)值，比較其大小，再以目標(biāo)函數(shù)值最小的節(jié)點為中心，在其附近空間劃分更小的網(wǎng)格，再計算在域內(nèi)各節(jié)點上的目標(biāo)函數(shù)值。重復(fù)進行下去，直到網(wǎng)格小到滿足精度為止。

2.離散變量型正交網(wǎng)格法正交網(wǎng)格法的基本思想相當(dāng)于正交試驗法，它是利用正交表，均勻地選取網(wǎng)格法中的一部分有代表性的網(wǎng)格點作為計算點，又稱隨機正交網(wǎng)格法，或叫正交計算設(shè)計法。下面給出正交網(wǎng)格法的正交表生成方法、計算步驟和相應(yīng)框圖。（1）正交網(wǎng)格表的生成方法

在離散變量型正交網(wǎng)格法中所采用的型正交表中：T:表示每個變量的分點數(shù)，稱為水平數(shù)，此表要求，T為素數(shù)。在正交表中1，2，3…，T叫做水平號，為了便于由水平號計算各變量的分量值，在離散變量型正交網(wǎng)格法的正交表中采用0，1，2,表示水平號。：表示基本列數(shù)，它可以為不小于2的任意正整數(shù)，為了加密網(wǎng)格點，也為了減少計算點數(shù)，宜采用的正交表。n：表示變量的維數(shù)，也即正交表的總列數(shù)。T，是正交表基本參數(shù)。當(dāng)T，確定后，正交表的總列數(shù)為：，當(dāng)時，正交表的行數(shù)為。由正交表在網(wǎng)格點中取計算點時，正交表的一行對應(yīng)于一個計算點，因此一張正交表可選取個計算點，以下取。1）按列生成正交表通常的正交表都是按列生成的。以素數(shù)T為階的正交拉丁方完全組構(gòu)成的正交表，可用來構(gòu)成型正交表。這與“完全對”，“T階拉丁方”，“正交拉丁方”等概念有關(guān)。完全對”，設(shè)有兩組元素，，與，，我們把個“元素對”：叫做由元素所構(gòu)成的“完全對”。

定義1：以1，2，，T為元素而且每行以及每列中的元素又都互不相同的T階方陣，叫做一個“T階拉丁方”。

定義2：設(shè)A與B是兩個T階拉丁方，如果它們同位置的元素所構(gòu)成的個“元素對”正好是一個“完全對”時，則稱A與B為正交拉丁方，簡稱A與B正交。顯然，A與B正交時，B與A也正交。若有這樣的正交拉丁方，那么以這些拉丁方為列（就是先排拉丁方的第一行元素，再排第二行的元素，最后排第T行元素所得到的一列），添加到基本列之右方添加列上，即得到型的正交表。

2）按行生成正交表

設(shè)T為給定的水平數(shù)，以表示型正交表中第I行的第J列（即第J個分量）的水平號的元素值，此處有。以符號“‖”表示兩個數(shù)只舍不入的整除，則的計算公式可寫為按上式計算，產(chǎn)生的水平號元素值，其最小值為0，最大值為，共T個水平號。（2）正交網(wǎng)格法的計算步驟和框圖計算步驟如下：1）確定各變量的取值范圍[，]（=1,2，，n），按單位離散變量的增量整倍數(shù)選擇變量的分點數(shù)。即選擇水平數(shù)，T為素數(shù)；令區(qū)間分段數(shù)為，單位離散變量的增量為。2）計算各變量分段步長，即網(wǎng)格點的間隔。對等間隔的離散量可取

=（=1,2，，）。=或取，E為正整數(shù)：開始對E取大值，以后逐步取小值。令行號I=1，中間變量，極差分析用數(shù)組，并以表示數(shù)組FK中的第行第列元素。3）確定第I個計算點。正交表中的第I行元素，代入下式確定計算X點（5-41）令（5-42）（5-43）式中，B是區(qū)間[0,1]上的隨機數(shù)，取小數(shù)后的位數(shù)比E的位數(shù)少1或相等；是大于1的整數(shù)，一般可取=2～10。，若時，這時即將終止計算。注意此時應(yīng)取整數(shù)或取離散值。由上述關(guān)系可產(chǎn)生由正交表中第I行的各列元素生成的第I個計算點=[]。式（5-43）含義見圖5-204）驗證點是否在域內(nèi)，若在域內(nèi)，則轉(zhuǎn)5），否則轉(zhuǎn)6）。5）計算圖5-20式（5-43）的幾何描述若，則令，，否則，保持原值。6）若，則轉(zhuǎn)3）；否則，打印，。7）極差分析：極差分析用數(shù)組按列求出每列的極差分析參數(shù)最大值，最小值及對應(yīng)于(求極小化時)的水平號，稱為第j個變量的最優(yōu)水平。第j個變量的極差為。（5-45）將從小到大排列，并與對應(yīng)的變量號一起打印出來，以便分析各變量對目標(biāo)函數(shù)從小到大的影響程度。對影響較大的變量，必要時還可依次改變變量上下限轉(zhuǎn)2）。8）計算最好水平點的目標(biāo)函數(shù)值：令，最好水平點，若在x域內(nèi)，則計算，當(dāng)時，令，。因取為單位離散量步長或單位整型量步長的整數(shù)E倍，這一做法，可使變量優(yōu)化解為所需的整型量或離散量。9）對x為在域內(nèi)的優(yōu)化解，檢驗迭代是否可以終止。如可檢驗步長是否滿足？若已滿足或總的迭代次數(shù)已足夠則輸出FA，停機。若不滿足或優(yōu)化解X在域外或，則轉(zhuǎn)10）。10）尋優(yōu)區(qū)間的收縮或擴張，計算重開始，令（5-46）（5-47）（5-48）式中，為正整數(shù)，當(dāng)取時，尋優(yōu)區(qū)間收縮；當(dāng)取，尋優(yōu)區(qū)間擴張，轉(zhuǎn)2）。這里擴張與收縮應(yīng)視具體情況決定。一般規(guī)律是先擴張，以后逐步縮尋優(yōu)區(qū)間。分析所得結(jié)果是否是所要求的優(yōu)化解。如果出現(xiàn)偽優(yōu)化解，這時可以采用將各變量在正交表中的列號互換位置，其實質(zhì)即使原正交表改變形狀。使，如此錯位后再按正交表重新尋優(yōu)。亦即轉(zhuǎn)2）計算重新開始。經(jīng)驗證明，這樣交換三次左右往往可以走出偽優(yōu)化解的死區(qū)，找出真正優(yōu)化解。圖5-21離散變量型正交網(wǎng)絡(luò)法程序框圖(五）離散變量的組合型法該法可用于求解約束非線性混合離散變量優(yōu)化設(shè)計問題。它的數(shù)學(xué)模型表達式如式（5-30）所示。該法的主要步驟是：

1.初始復(fù)合形頂點的形成給定的一個初始離散點，其各分量必須滿足變量邊界條件，即初始復(fù)合形頂點可用下述方法形成：設(shè)初始復(fù)合形頂點數(shù)個，標(biāo)記的上標(biāo)為點號數(shù)，下標(biāo)為該點的分量號值。2.離散一維搜索產(chǎn)生新點

由上一步產(chǎn)生的離散復(fù)合形頂點，可計算各頂點的目標(biāo)函數(shù)值。令目標(biāo)函數(shù)值最大的為最壞點，反之為最好點。把最壞頂點作為一維搜索初始點，以最壞頂點向其余各頂點的幾何中心

，即點集中心的連續(xù)方向作為離散一維搜索的方向

，這時可把反射、延伸或收縮幾個步驟統(tǒng)一用該離散一維搜索來替代。搜索方向S的各分量值計算式為除最壞點外的其他各頂點的幾何中心的各分量值計算式為

設(shè)離散一維搜索得到的新點，其各分量值為取

式中，T為離散一維搜索的步長因子。表示取最靠近的離散值。J=1，2，，K代表頂點數(shù)；i=1，2，，p代表離散變量子集的下標(biāo)；代表連續(xù)變量子集的下標(biāo)。

3.約束條件的處理下面用自動進入可行域?qū)?yōu)技巧來處理約束條件定義一個有效目標(biāo)函數(shù)，令（5-53）

式中，為原目標(biāo)函數(shù)；M為一常數(shù)，其值比的值在數(shù)量級上大得多；為一特殊函數(shù)，其值與所有違反約束量的總和成正比，可由下式求出4.重新啟動技術(shù)由上所述沿方向進行離散一維搜索只是目標(biāo)函數(shù)可能的下降方向，只能表明其下降概率較大，但不一定能保證是下降方向，也就不一定能求得好的離散點。當(dāng)出現(xiàn)這種情形時候，需要采用重新啟動技術(shù)，它屬于算法的一個輔助功能。但它與離散復(fù)合形產(chǎn)生合適的新點關(guān)系十分密切。重新啟動技術(shù)可以有兩種方法：一是改變搜索基點和搜索方向；二是離散復(fù)合形的各頂點向最好頂點收縮。式中，為一常數(shù)。

5.組合型算法終止準(zhǔn)則取連續(xù)變量的精度值（或稱擬增量）為，其值由實際設(shè)計變量的含義事先選定。取離散變量的增量為；取變量中期望滿足精度的分量個數(shù)為，通常取的正整數(shù)。并設(shè)（或）的個數(shù)為，則當(dāng)，離散復(fù)合形調(diào)優(yōu)迭代運算結(jié)朿。將這時最好頂點作為離散變量的優(yōu)化解輸出。

令

6.組合型算法的輔助功能為提高求解效率及可靠性，通常在算法中還需要加入其他輔助功能，除了上面講的重新啟動技術(shù)外，還有：加速技巧、變量分解策略、網(wǎng)絡(luò)搜索技術(shù)、貼界搜索技術(shù)、離散復(fù)合形最終反射技術(shù)和離散復(fù)合形重構(gòu)技術(shù)等6種輔助功能。（1）直線加速與二次曲線加速當(dāng)目標(biāo)函數(shù)嚴(yán)重非線性時，即若函數(shù)具有尖峰脊線，即存在“谷”時，則希望能沿著脊線方向進行搜索，可迅速提高算法的尋優(yōu)效率，該算法稱為具有脊線加速能力。加速的措施是以分析軌跡為其理論基礎(chǔ)。圖5-24所示為具有脊線的目標(biāo)函數(shù)。確定目標(biāo)函數(shù)存在“谷”的主要依據(jù)認(rèn)為離散復(fù)合形最好頂點一定是在谷的脊線上或其附近求得，當(dāng)由初始點沿下降方向搜索時，總