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

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

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

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

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

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

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

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

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

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

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

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

=由該式還可知

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

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

（5-19）式中，

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

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

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

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

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

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

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

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

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

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

——單位壓力

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

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

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

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

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

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

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

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

首先求解

得最優(yōu)點(diǎn)

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

然后求解

而得最優(yōu)點(diǎn)為

=1.9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

——不等式約束條件；——離散項(xiàng)罰因子

例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ù)項(xiàng)。由圖可知，參數(shù)、、數(shù)值的選取直接影響著離散懲罰函數(shù)的曲線形狀。逐步減小，增加，得圖5-19a、b、c，使離散優(yōu)化點(diǎn)從，最終找到離散優(yōu)化解。如最初即選擇圖5-19c則有可能陷在偽優(yōu)化點(diǎn)，即解，找不到真正優(yōu)化解。

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

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

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

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

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

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

2）按行生成正交表

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

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

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

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

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

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

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

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

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

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

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

令

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