多目標及離散變量優(yōu)化方法第1頁，共45頁，2023年，2月20日，星期一第六章

多目標優(yōu)化方法和離散變量優(yōu)化方法簡介第一節(jié)多目標優(yōu)化問題第二節(jié)多目標優(yōu)化方法第三節(jié)離散變量優(yōu)化問題

與離散變量優(yōu)化方法第2頁，共45頁，2023年，2月20日，星期一第六章重點內容1.什么是非劣解？2.多目標優(yōu)化方法主要有哪四種方法？3.統(tǒng)一目標法中的線性加權法，如何將各目標函數(shù)值的變化范圍均統(tǒng)一為從0到1的變化范圍？4.統(tǒng)一目標法中的線性加權法，確定加權因子的方法有哪幾種？5.統(tǒng)一目標法中的理想點法是如何構造統(tǒng)一的目標函數(shù)的？6.統(tǒng)一目標法中的功效系數(shù)法可以怎樣確定功效系數(shù)？7.用寬容分層序列法求解的思路8.構造離散懲罰函數(shù)離散變量組合型法中如何產生初始復合形的頂點？約束條件和迭代終止是如何處理的?第3頁，共45頁，2023年，2月20日，星期一第六章結束第4頁，共45頁，2023年，2月20日，星期一機械設計中，同時要求幾項設計指標達到最優(yōu)的問題

——多目標優(yōu)化設計問題多目標優(yōu)化問題的類型：

(1)整體多目標優(yōu)化

(2)分層(步)多目標優(yōu)化多目標優(yōu)化問題與單目標優(yōu)化問題有根本性區(qū)別:①單目標問題可以得到最優(yōu)解，而多目標問題往往得不到最優(yōu)解，而只能得到非劣解（有效解）②多目標優(yōu)化問題的任意兩個設計方案，往往不易于比較其優(yōu)劣。第一節(jié)多目標優(yōu)化問題TlRxRxxfxfxfxFnn)]()(),([)(21minmin..??=第六章第一節(jié)多目標優(yōu)化問題第5頁，共45頁，2023年，2月20日，星期一判別方案的優(yōu)劣：單目標：只要用f(x)去比較即可絕對最優(yōu)解：多目標優(yōu)化設計時，幾個分目標同時達到最優(yōu)的解。絕對最優(yōu)解幾乎不可能找到，因為各分目標函數(shù)有時會相互矛盾。非劣解(有效解)：指有m個目標函數(shù)，找不到一個x，使得其中一個目標函數(shù)值fi(x)比fi(x*)更好，而其余(m-1)個目標函數(shù)值不變壞，則稱x*為非劣解（有效解）;多目標優(yōu)化設計時，各分目標往往互相矛盾，甚至對立，這就需在各分目標函數(shù)之間協(xié)調，互相作些讓步，以便取得較好的方案。

多目標：（j=1,2,…l）第六章第一節(jié)多目標優(yōu)化問題第6頁，共45頁，2023年，2月20日，星期一例1在最優(yōu)解為：但兩者無共同的最優(yōu)解內兩單目標函數(shù)]2,0[?x第六章第一節(jié)多目標優(yōu)化問題第7頁，共45頁，2023年，2月20日，星期一①內，(若，對任意都有，則x*是多目標優(yōu)化的絕對最優(yōu)解)③若，且不存在使，則x*為非劣解。的所有點均為非劣解。是絕對最優(yōu)解。內，a’，a點都是劣解（若，存在，有②則x*成為劣解。）Dxx*?第六章第一節(jié)多目標優(yōu)化問題例如b點。第8頁，共45頁，2023年，2月20日，星期一一、主要目標法基本思想：多個目標中選擇一個目標作為主要目標，而其它目標則只需滿足一定的要求即可，即將目標轉化為約束條件目標函數(shù)轉化為：二、統(tǒng)一目標法基本思想：將多目標優(yōu)化問題，通過一定方法轉化為統(tǒng)一目標函數(shù)或綜合目標函數(shù)作為多目標優(yōu)化問題的評價函數(shù)。第二節(jié)多目標優(yōu)化方法式中，fimin和f

imax為第i個目標函數(shù)的上、下限。一般只有單邊限制第六章第二節(jié)多目標優(yōu)化方法第9頁，共45頁，2023年，2月20日，星期一1．線性加權法基本思想：將各個分目標函數(shù)依其數(shù)量級和在整體設計中的重要程度相應地給出一組構成一新的統(tǒng)一的目標函數(shù)F(x)wi——加權因子(wi≥0，i=1,2,…，l)加權因子取值對計算結果的正確性影響較大。常用的方法有：線性加權法、理想點法（目標規(guī)劃法）、功效系數(shù)法和極大極小法等。加權因子，,取fi(x)和wi(i=1,2,…，l)的線性組合，第六章第二節(jié)多目標優(yōu)化方法第10頁，共45頁，2023年，2月20日，星期一為消除各分目標在量級上的差別，先將分目標函數(shù)fi(x)轉化為無量綱等量級目標函數(shù)再組成統(tǒng)一目標函數(shù)。

wi——按各分目標的重要程度來決定如各分目標有相同的重要性，則取wi=1(i=1,2,…,l)—稱為均勻計權，否則取各分目標不同的加權因子，取將fi(x)轉換為無量綱的等量級目標函數(shù)的方法

第六章第二節(jié)多目標優(yōu)化方法①將各分目標轉化后加權加權因子wi確定的方法:第11頁，共45頁，2023年，2月20日，星期一設各分目標函數(shù)值的變動范圍為：②即將各單目標函數(shù)的最優(yōu)值的倒數(shù)作為權系數(shù)，它反映了各單目標函數(shù)離開各自最優(yōu)值的程度。另外相當于各分目標函數(shù)進行了無量綱的處理，而消除了各分目標在數(shù)量級上的差別。第六章第二節(jié)多目標優(yōu)化方法第12頁，共45頁，2023年，2月20日，星期一其中，w1i——本征權因子，反映各分目標的重要程度w2i——校正權因子，調整各分目標間量級差別的影響加權因子w2i愈小，反之，亦然。這樣可調整不同的目標函數(shù)值同步下降。③直接加權法一個分目標函數(shù)fi(x)變化越快，的值越大，將加權因子分成兩部分一般?。簑i=w1i·w2i

(i=1,2,…,l)第六章第二節(jié)多目標優(yōu)化方法第13頁，共45頁，2023年，2月20日，星期一基本思想：先定出各分目標函數(shù)的最優(yōu)值，根據(jù)多目標優(yōu)化設計的總體要求對這些最優(yōu)值進行調整，定出各分目標的最合理值（也可以是最優(yōu)值），再構造新的統(tǒng)一的式中，除如引入加權系數(shù)wi，則目標函數(shù)為：2．理想點法（目標規(guī)化法）是為使目標函數(shù)無量綱化。目標函數(shù)：第六章第二節(jié)多目標優(yōu)化方法第14頁，共45頁，2023年，2月20日，星期一V——其中，則統(tǒng)一目標函數(shù)為即要求位于分子的各分目標函數(shù)應盡量小，而位于分母的各分目標函數(shù)應盡量大。一般要求各分目標函數(shù)fi(x)在D上均取正值。3．分目標乘除法多目標混合優(yōu)化問題：第六章第二節(jié)多目標優(yōu)化方法第15頁，共45頁，2023年，2月20日，星期一基本思想：對應每一目標函數(shù)都用功效系數(shù)來表示該項指標的好壞總功效系數(shù)（評價函數(shù)）C值越大越好，C=1---方案最滿意C=0---表示此方案不能被接受。只要有一個方案，Ci=0，此方案都不能被接受功效系數(shù)類型：1）Ci與fi成正比，即要求目標函數(shù)越大越好2）Ci與fi成反比，即要求目標函數(shù)越小越好3）fi取某適當值時，Ci就越大；否則Ci就越小。4．功效系數(shù)法第六章第二節(jié)多目標優(yōu)化方法第16頁，共45頁，2023年，2月20日，星期一功效系數(shù)的確定方法：①直線法②折線法第六章第二節(jié)多目標優(yōu)化方法第17頁，共45頁，2023年，2月20日，星期一③指數(shù)法功效系數(shù)法的優(yōu)點：

1、各分目標函數(shù)的值數(shù)量級大小對優(yōu)化無影響

2、評價函數(shù)比較直觀、易于調整

3、適于要求目標函數(shù)取值適中的情況第六章第二節(jié)多目標優(yōu)化方法第18頁，共45頁，2023年，2月20日，星期一基本思想：多目標優(yōu)化問題中，存在目標函數(shù)間相互矛盾的情況，一個（些）目標函數(shù)值的減小，將導致另一個（些）目標函數(shù)值的增大。因此，各分目標函數(shù)值之間需要進行協(xié)調，以便取得合理的方案。如圖所示，兩維雙目標函數(shù)f1(x)、f2(x)的等值線和兩個不等式約束曲面.三、協(xié)調曲線法第六章第二節(jié)多目標優(yōu)化方法第19頁，共45頁，2023年，2月20日，星期一

f1(x)最優(yōu)點T點，f2(x)最優(yōu)點P點可行域中任意一點R.

從R點起沿f1(x)=5等值線，向約束面移動f2(x)不斷改善，直至邊界上S點。從R點起沿f2(x)=8等值線，向約束面f1(x)移動不斷改善，直至邊界上Q點。f1(x)=5時，對應f2(x)的最佳點為S點由此可得f1(x)（或f2(x)）為定值時對應的最佳f2(x)（或f1(x)）的點關系曲線T-Q-S-P—協(xié)調曲線。f2(x)=8時，對應f1(x)的最佳點為Q點。均為約束邊界點第六章第二節(jié)多目標優(yōu)化方法S、Q點都比R點優(yōu)第20頁，共45頁，2023年，2月20日，星期一該曲線反映了兩個設計目標全部最佳方案的調整范圍,再建立一個衡量設計方案滿意程度的準則，建立一組反映不同滿意程度的曲線u(f1,f2)，使隨著滿意度增加，同時使目標函數(shù)f1(x)和f2(x)都有所下降。滿意度曲線與協(xié)調曲線的切點，即為最優(yōu)設計方案。如圖所示O點滿意度曲線不同，則最優(yōu)設計方案也不同。第六章第二節(jié)多目標優(yōu)化方法第21頁，共45頁，2023年，2月20日，星期一基本思想：將多目標優(yōu)化問題的各目標函數(shù)按重要程度排列，然后，依次對各個目標函數(shù)求最優(yōu)解，而后一目標函數(shù)應在其前面目標函數(shù)最優(yōu)解的集合域內尋優(yōu)。1、分層序列法設分目標函數(shù)重要程度次序為：f1(x)、f2(x)，…則首先對f1(x)尋優(yōu)：在的集合內對f2(x)尋優(yōu)：四、分層序列法和寬容分層序列法第六章第二節(jié)多目標優(yōu)化方法問題：如其中第k個目標函數(shù)的最優(yōu)解為唯一時，再往下求解就失去意義，而后面l-k個目標函數(shù)也沒法得到最優(yōu)化解。

以下類推。第22頁，共45頁，2023年，2月20日，星期一2、寬容分層序列法基本思想：即先對各目標函數(shù)的最優(yōu)值取一定的寬容量ε1，ε2，…，εl(>0)，使求后一個目標函數(shù)最優(yōu)值時，對前一些目標函數(shù)的約束擴大為在其最優(yōu)值附近的某一范圍內。②③……④①第六章第二節(jié)多目標優(yōu)化方法第23頁，共45頁，2023年，2月20日，星期一如圖，兩目標優(yōu)化問題，不作寬容時，為最優(yōu)解，即f1(x)的嚴格最優(yōu)解，給定寬容值ε1，則最優(yōu)解為x(1)第六章第二節(jié)多目標優(yōu)化方法第24頁，共45頁，2023年，2月20日，星期一例1用寬容分層序列法求解式中，解：如圖所示，由給定ε1=0.052，解∴V—第六章第二節(jié)多目標優(yōu)化方法第25頁，共45頁，2023年，2月20日，星期一

等間隔的離散變量非均勻間隔離散變量→特例：整數(shù)變量—整數(shù)規(guī)劃問題最簡單處理辦法：按連續(xù)變量處理，得最優(yōu)解后，再圓整為最近的離散值問題：①圓整后的點在非可行域;②圓整為哪一個附近的離散值難于確定;③有些情況下設計變量不允許最后取整。第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法一、概述離散變量第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第26頁，共45頁，2023年，2月20日，星期一式中——離散變量子集合xD為空集時，為連續(xù)變量型問題xC為空集時，為全離散變量型問題——連續(xù)變量子集合約束非線性混合離散變量優(yōu)化問題的數(shù)學模型：第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第27頁，共45頁，2023年，2月20日，星期一二、約束非線性離散變量的優(yōu)化方法常用方法：

1)以連續(xù)變量優(yōu)化為基礎的方法：圓整法、擬離散法、離散型罰函數(shù)法

2)離散變量隨機優(yōu)化方法：隨機試驗法，隨機離散搜索法

3)離散變量搜索優(yōu)化方法：組合優(yōu)化法，整數(shù)梯度法

4)其它離散變量優(yōu)化方法：非線性隱枚舉法，分支定界法(一)以連續(xù)變量優(yōu)化為基礎的方法1、整型化、離散化法基本思想：先按連續(xù)變量方法求得最優(yōu)解x*，再進一步尋找整型量或離散量優(yōu)化解。第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第28頁，共45頁，2023年，2月20日，星期一設最優(yōu)點的n個實型分量為，則最靠近的兩個離散量（或整型量）由這些離散（整型）分量的不同組合，便構成了最鄰近于實型最優(yōu)點x*的兩個整型（離散）分量及其相應一組離散（整型）點群共2n個設計點。去除不在可行域內點，其余在可行域內的若干點中，選取一個目標函數(shù)值最小的點作為最優(yōu)解輸出。第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第29頁，共45頁，2023年，2月20日，星期一問題：如中圖:x*點（通常在約束邊界上）附近的離散點（整型點）均不在可行域內的情況如右圖:離x*較遠的點P為離散最優(yōu)點的情況。如左圖，x*點附近整型（離散）點群為ABCD。B點在可行域外，C點為最優(yōu)點。第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第30頁，共45頁，2023年，2月20日，星期一2．擬離散法基本思想：在求得連續(xù)變量最優(yōu)解x*后，在x*點附近按一定方法進行搜索來求得優(yōu)化離散解。

(1)交替查找法：適于全整數(shù)變量優(yōu)化問題（略）

(2)離散分量取整，連續(xù)分量優(yōu)化法：適用于混合離散變量優(yōu)化問題（略）第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法基本思想：將設計變量的離散性視為對該變量的一種約束條件，再用連續(xù)變量的優(yōu)化方法來計算離散變量問題的優(yōu)化解。

1）構造一個具有下列性質的離散懲罰函數(shù)項Qk(xD)3、離散懲罰函數(shù)法RD—設計空間離散點的集合其意義為：當離散變量趨于離散值時，懲罰函數(shù)值為零第31頁，共45頁，2023年，2月20日，星期一離散懲罰函數(shù)定義方法:其中，xi為相鄰兩離散點xij和xij+1間任一點坐標。Qk(xD)為規(guī)范化的對稱函數(shù)，其最大值為1，xi取xij或xij+1時為0。如圖,對βk≥1情形，在離散值之間范圍內，函數(shù)的一階導數(shù)是連續(xù)的。第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法(1)第32頁，共45頁，2023年，2月20日，星期一2）將離散懲罰函數(shù)項Qk(xD)加到內點法SUMT的懲罰項中，得離散懲罰函數(shù)為：其中，s(k)為離散懲罰因子，

∴時第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第33頁，共45頁，2023年，2月20日，星期一例1求f(x)=x/2的最小整數(shù)優(yōu)化解，約束函數(shù)

g1(x)=1.3-x≤0如圖所示，分別表示k不同時，離散優(yōu)化點

最終離散最優(yōu)解為[x]2

變化情況隨著k不斷變化，r減小，s增加第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第34頁，共45頁，2023年，2月20日，星期一

方法缺點：離散懲罰函數(shù)易出現(xiàn)病態(tài)，使優(yōu)化搜索帶來困難。(二)離散變量搜索型方法——離散復合形法特點：在離散空間直接搜索，每次得到的復合形頂點都是離散點，通過不同的搜索方法來改變其形狀，使復合形逐步向離散最優(yōu)點趨近。算法步驟：1)在n維空間產生由2n+1個頂點構成的初始復合形，并將各頂點移到各自附近的離散點上。2)將各項點按目標函數(shù)值由大到小排列，找出最壞點AH3)找出除最壞點外復合形的幾何中心，并求出最壞點AH相對于中心點的反射點Ap并移到附近離散點上。4)如Ap點可行，且目標函數(shù)值比AH點好，則用Ap替代AH點，組成新復合形→轉步驟2第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第35頁，共45頁，2023年，2月20日，星期一否則，沿反射的反方向搜索定新點。5)如用上述方法失敗，則依次用次壞點…代替最壞點作為映射點，轉步驟3）6)如用最好點代替AH作為映射點，仍找不到好點，或復合形退化到n-1維空間時，表示算法收斂。此時，取復合形頂點中最好的點作為離散優(yōu)化解。(三)離散變量型網格法

1.離散變量型普通網格法基本思想：以一定的變量增量為間隔，把設計空間劃分為若干個網格，計算在可行域內每個網格節(jié)點上的目標函數(shù)值，比較其大小，再以目標函數(shù)值最小的節(jié)點為中心，在其附近空間劃分更小的網格，并計算各節(jié)點上的目標函數(shù)值，直至網格小到滿足精度——網格節(jié)點密度與離散點密度相等。第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第36頁，共45頁，2023年，2月20日，星期一開始時→網格比較稀疏→網格節(jié)點密度逐漸增加→直至按一個離散增量劃分網格節(jié)點為止。2．離散變量型正交網格法普通網格法的缺點：變量維數(shù)增加時，計算工作量大大增加正交網格法基本思想：根據(jù)正交試驗法的原理，利用正交表均勻地選取網格法中一部分有代表性的網格點作為計算點，又稱隨機正交網格法。正交網格法的特點：只計算部分網格點的目標函數(shù)值，計算工作量少。第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第37頁，共45頁，2023年，2月20日，星期一(四)離散變量的組合型法（MDCP法）

——工程離散優(yōu)化通用方法基本思想：以離散復合形法為基礎，采用多種離散搜索策略，形成的具有多種功能的組合型算法。適于求解非線性混合離散變量優(yōu)化問題1．初始離散復合形頂點的形成復合形頂點數(shù)k=2n+1給定初始離散點x(0)，x(0)須滿足變量值的邊界條件，但不必滿足約束條件，即式中，ximin，ximax分別為第i個變量的下、上限第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第38頁，共45頁，2023年，2月20日，星期一點號數(shù)分量號數(shù)復合形的2n+1個頂點按下面方法產生第1個頂點：第2至n+1個頂點：第n+2至2n+1個頂點：如此產生的復合形頂點，不要求全是可行點，如圖，5個初始復合形頂點中，C、D兩點為不可行點。例如二維：第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第39頁，共45頁，2023年，2月20日，星期一2、離散一維搜索產生新點將復合形頂點目標函數(shù)值排隊，找出目標函數(shù)值最大的點為最壞點，x(b)以x(b)為基點，向其余各頂點的幾何中心x(e)方向作一維搜索，采用映射、延伸或收縮等步驟搜索搜索方向S的各分量Si計算式為：離散一維搜索得到的新點為x(t)其各分量為：取第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法第40頁，共45頁，2023年，2月20日，星期一離散一維搜索得到的新點為x(t)其各分量為：取其中表示取最靠近離散一維搜索方法可采用離散一維搜索進退對分法，步長為單位離散步長的整倍數(shù)。的離散值。T-步長因子第六章第三節(jié)離散變量優(yōu)化問題與離散變量優(yōu)化方法在產生初始復合形頂點及一維離散搜索時，均未考慮約束條件，為保證復合形迭代限制在可行域內，定義一