多目標及離散變量優(yōu)化方法（45頁)ppt課件

1、第一部分 現(xiàn)代機械設計概述第二部分 機械優(yōu)化設計第三部分 創(chuàng)新設計TRIZ 第四部分 綠色設計第五部分 逆向設計課程內(nèi)容第六章多目的優(yōu)化方法和離散變量優(yōu)化方法簡介第一節(jié) 多目的優(yōu)化問題第二節(jié) 多目的優(yōu)化方法第三節(jié) 離散變量優(yōu)化問題 與離散變量優(yōu)化方法第六章 重點內(nèi)容1. 什么是非劣解？2. 多目的優(yōu)化方法主要有哪四種方法？3. 一致目的法中的線性加權(quán)法，如何將各目的函數(shù)值的變化范圍均一致為從0到1的變化范圍？ 4. 一致目的法中的線性加權(quán)法，確定加權(quán)因子的方法有哪幾種？5. 一致目的法中的理想點法是如何構(gòu)造一致的目的函數(shù)的？6. 一致目的法中的效果系數(shù)法可以怎樣確定效果系數(shù)？7. 用寬容分層序

2、列法求解的思緒8. 構(gòu)造離散懲罰函數(shù) 離散變量組合型法中如何產(chǎn)生初始復合形的頂點？ 約束條件和迭代終止是如何處置的?第六章終了機械設計中，同時要求幾項設計目的到達最優(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)化問題判別方案的優(yōu)劣：單目的：只需用

3、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é)調(diào)，相互作些退讓，以便獲得較好的方案。 多目的：j=1,2,l第六章 第一節(jié) 多目的優(yōu)化問題例1 在最優(yōu)解為：但兩者無共同的最優(yōu)解 內(nèi)兩單目的函數(shù)2,0 x第六章 第一節(jié) 多目的優(yōu)化問題 內(nèi)，(假設，對恣意都有，

4、那么x*是多目的優(yōu)化的絕對最優(yōu)解)假設，且不存在使，那么x*為非劣解。的一切點均為非劣解。是絕對最優(yōu)解。內(nèi)，a，a點都是劣解假設，存在，有那么x*成為劣解。Dxx*第六章 第一節(jié) 多目的優(yōu)化問題例如b點。一、主要目的法 根本思想：多個目的中選擇一個目的作為主要目的，而其它目的那么只需滿足一定的要求即可，即將目的轉(zhuǎn)化為約束條件 目的函數(shù)轉(zhuǎn)化為： 二、一致目的法 根本思想：將多目的優(yōu)化問題，經(jīng)過一定方法轉(zhuǎn)化為一致目的函數(shù)或綜合目的函數(shù)作為多目的優(yōu)化問題的評價函數(shù)。 第二節(jié) 多目的優(yōu)化方法式中，f imin和f imax為第i個目的函數(shù)的上、下限。普通 只需單邊限制第六章 第二節(jié) 多目的優(yōu)化方法1線

5、性加權(quán)法 根本思想：將各個分目的函數(shù)依其數(shù)量級和在整體設計中的重要程度相應地給出一組構(gòu)成一新的一致的目的函數(shù)F(x) wi加權(quán)因子 (wi0，i=1,2,，l )加權(quán)因子取值對計算結(jié)果的正確性影響較大。常用的方法有：線性加權(quán)法、理想點法目的規(guī)劃法 、效果系數(shù)法和極大極小法等。加權(quán)因子，,取fi(x)和wi(i=1,2,，l) 的線性組合，第六章 第二節(jié) 多目的優(yōu)化方法為消除各分目的在量級上的差別，先將分目的函數(shù)fi(x)轉(zhuǎn)化為無量綱等量級目的函數(shù)再組成一致目的函數(shù)。 wi按各分目的的重要程度來決議如各分目的有一樣的重要性，那么取wi =1 (i=1,2,l) 稱為均勻計權(quán)，否那么取各分目的不同

6、的加權(quán)因子， 取將fi(x)轉(zhuǎn)換為無量綱的等量級目的函數(shù)的方法 第六章 第二節(jié) 多目的優(yōu)化方法將各分目的轉(zhuǎn)化后加權(quán) 加權(quán)因子wi確定的方法:設各分目的函數(shù)值的變動范圍為： 即將各單目的函數(shù)的最優(yōu)值的倒數(shù)作為權(quán)系數(shù)，它反映了各單目的函數(shù)分開各自最優(yōu)值的程度。另外相當于各分目的函數(shù)進展了無量綱的處置，而消除了各分目的在數(shù)量級上的差別。 第六章 第二節(jié) 多目的優(yōu)化方法其中，w1i本征權(quán)因子，反映各分目的的重要程度w2i校正權(quán)因子，調(diào)整各分目的間量級差別的影響加權(quán)因子w2i愈小，反之，亦然。這樣可調(diào)整不同的目的函數(shù)值同步下降。 直接加權(quán)法一個分目的函數(shù)fi(x)變化越快，的值越大，將加權(quán)因子分成兩部分

7、普通取：wi=w1iw2i (i=1,2,l)第六章 第二節(jié) 多目的優(yōu)化方法根本思想：先定出各分目的函數(shù)的最優(yōu)值，根據(jù)多目的優(yōu)化設計的總體要求對這些最優(yōu)值進展調(diào)整，定出各分目的的最合理值也可以是最優(yōu)值，再構(gòu)造新的一致的式中，除如引入加權(quán)系數(shù)wi，那么目的函數(shù)為：2理想點法目的規(guī)化法是為使目的函數(shù)無量綱化。目的函數(shù)：第六章 第二節(jié) 多目的優(yōu)化方法V其中，那么一致目的函數(shù)為即要求位于分子的各分目的函數(shù)應盡量小，而位于分母的各分目的函數(shù)應盡量大。普通要求各分目的函數(shù)fi(x)在D上均取正值。 3分目的乘除法多目的混合優(yōu)化問題：第六章 第二節(jié) 多目的優(yōu)化方法根本思想：對應每一目的函數(shù)都用效果系數(shù)來表示

8、該項目的的好壞總效果系數(shù)評價函數(shù)C值越大越好，C=1-方案最稱心C=0-表示此方案不能被接受。 只需有一個方案， Ci=0，此方案都不能被接受效果系數(shù)類型：1Ci與fi成正比，即要求目的函數(shù)越大越好2Ci與fi成反比，即要求目的函數(shù)越小越好3fi取某適當值時，Ci就越大；否那么Ci就越小。4效果系數(shù)法第六章 第二節(jié) 多目的優(yōu)化方法效果系數(shù)確實定方法：直線法折線法第六章 第二節(jié) 多目的優(yōu)化方法指數(shù)法效果系數(shù)法的優(yōu)點： 1、各分目的函數(shù)的值數(shù)量級大小對優(yōu)化無影響 2、評價函數(shù)比較直觀、易于調(diào)整 3、適于要求目的函數(shù)取值適中的情況第六章 第二節(jié) 多目的優(yōu)化方法根本思想：多目的優(yōu)化問題中，存在目的函數(shù)

9、間相互矛盾的情況，一個些目的函數(shù)值的減小，將導致另一個些目的函數(shù)值的增大。因此，各分目的函數(shù)值之間需求進展協(xié)調(diào)，以便獲得合理的方案。如下圖，兩維雙目的函數(shù)f1(x)、f2(x)的等值線和兩個不等式約束曲面.三、協(xié)調(diào)曲線法第六章 第二節(jié) 多目的優(yōu)化方法 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)

10、的點關(guān)系曲線T-Q-S-P協(xié)調(diào)曲線。f2(x)=8時，對應f1(x)的最正確點為Q點。 均為約束邊境點第六章 第二節(jié) 多目的優(yōu)化方法S、Q點都比R點優(yōu) 該曲線反映了兩個設計目的全部最正確方案的調(diào)整范圍,再建立一個衡量設計方案稱心程度的準那么，建立一組反映不同稱心程度的曲線u(f1,f2)，使隨著稱心度添加，同時使目的函數(shù)f1(x)和f2(x)都有所下降。 稱心度曲線與協(xié)調(diào)曲線的切點，即為最優(yōu)設計方案。如下圖O點 稱心度曲線不同，那么最優(yōu)設計方案也不同。第六章 第二節(jié) 多目的優(yōu)化方法根本思想：將多目的優(yōu)化問題的各目的函數(shù)按重要程度陳列，然后，依次對各個目的函數(shù)求最優(yōu)解，而后一目的函數(shù)應在其前面目

11、的函數(shù)最優(yōu)解的集合域內(nèi)尋優(yōu)。1、分層序列法設分目的函數(shù)重要程度次序為：f1(x)、f2(x)，那么首先對f1(x)尋優(yōu)：在的集合內(nèi)對f2(x)尋優(yōu)：四、分層序列法和寬容分層序列法第六章 第二節(jié) 多目的優(yōu)化方法問題：如其中第k個目的函數(shù)的最優(yōu)解為獨一時，再往下求解就失去意義，而后面l-k個目的函數(shù)也沒法得到最優(yōu)化解。 以下類推。2、寬容分層序列法 根本思想：即先對各目的函數(shù)的最優(yōu)值取一定的寬容量1，2，l (0)，使求后一個目的函數(shù)最優(yōu)值時，對前一些目的函數(shù)的約束擴展為在其最優(yōu)值附近的某一范圍內(nèi)。第六章 第二節(jié) 多目的優(yōu)化方法如圖，兩目的優(yōu)化問題，不作寬容時，為最優(yōu)解，即f1(x)的嚴厲最優(yōu)解，

12、給定寬容值1，那么最優(yōu)解為x(1)第六章 第二節(jié) 多目的優(yōu)化方法例1 用寬容分層序列法求解式中，解：如下圖，由給定1= 0.052，解V第六章 第二節(jié) 多目的優(yōu)化方法 等間隔的離散變量 非均勻間隔離散變量 特例：整數(shù)變量整數(shù)規(guī)劃問題最簡單處置方法：按延續(xù)變量處置，得最優(yōu)解后， 再圓整為最近的離散值問題：圓整后的點在非可行域; 圓整為哪一個附近的離散值難于確定; 有些情況下設計變量不允許最后取整。第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法一、概述離散變量 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法式中 離散變量子集合xD為空集時，為延續(xù)變量型問題xC為空集時，為全離散變量型問題延續(xù)變量子

13、集合約束非線性混合離散變量優(yōu)化問題的數(shù)學模型：第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法二、約束非線性離散變量的優(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)化方法設最優(yōu)點的n個實型分量為，那么最接近的兩個離散

14、量或整型量由這些離散整型分量的不同組合，便構(gòu)成了最臨近于實型最優(yōu)點x*的兩個整型離散分量及其相應一組離散整型點群共2n個設計點。去除不在可行域內(nèi)點，其他在可行域內(nèi)的假設干點中，選取一個目的函數(shù)值最小的點作為最優(yōu)解輸出。第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法問題： 如中圖: x*點通常在約束邊境上附近的離散點整型點均不在可行域內(nèi)的情況 如右圖: 離x*較遠的點P為離散最優(yōu)點的情況。 如左圖，x*點附近整型離散點群為ABCD。B點在可行域外，C點為最優(yōu)點。 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法2擬離散法 根本思想：在求得延續(xù)變量最優(yōu)解x*后，在x*點附近按一定方法進展搜索

15、來求得優(yōu)化離散解。 (1)交替查找法：適于全整數(shù)變量優(yōu)化問題略 (2)離散分量取整，延續(xù)分量優(yōu)化法： 適用于混合離散變量優(yōu)化問題略 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法根本思想：將設計變量的離散性視為對該變量的一種約束條件，再用延續(xù)變量的優(yōu)化方法來計算離散變量問題的優(yōu)化解。 1構(gòu)造一個具有以下性質(zhì)的離散懲罰函數(shù)項Qk(xD) 3、離散懲罰函數(shù)法RD設計空間離散點的集合 其意義為：當離散變量趨于離散值時，懲罰函數(shù)值為零 離散懲罰函數(shù)定義方法:其中，xi為相鄰兩離散點xij和xij+1間任一點坐標。Qk(xD)為規(guī)范化的對稱函數(shù)，其最大值為1，xi取xij或xij+1時為0。如圖,

16、對k1情形，在離散值之間范圍內(nèi)，函數(shù)的一階導數(shù)是連續(xù)的。 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法(1)2將離散懲罰函數(shù)項Qk(xD)加到內(nèi)點法SUMT的懲罰項中，得離散懲罰函數(shù)為：其中，s(k)為離散懲罰因子， 時第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法例1 求f(x)=x/2的最小整數(shù)優(yōu)化解，約束函數(shù) g1(x)=1.3-x0如下圖，分別表示k不同時，離散優(yōu)化點 最終離散最優(yōu)解為x2 變化情況隨著k不斷變化，r減小，s添加第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法 方法缺陷：離散懲罰函數(shù)易出現(xiàn)病態(tài)，使優(yōu)化搜索帶 來困難。(二) 離散變量搜索型方法離散復合形法特點

17、：在離散空間直接搜索，每次得到的復合形頂點都是離散點，經(jīng)過不同的搜索方法來改動其外形，使復合形逐漸向離散最優(yōu)點趨近。算法步驟：1) 在n維空間產(chǎn)生由2n+1個頂點構(gòu)成的初始復合形，并將各頂點移到各自附近的離散點上。2) 將各項點按目的函數(shù)值由大到小陳列，找出最壞點AH3) 找出除最壞點外復合形的幾何中心，并求出最壞點AH相對于中心點的反射點Ap并移到附近離散點上。4) 如Ap點可行，且目的函數(shù)值比AH點好，那么用Ap替代AH點，組成新復合形轉(zhuǎn)步驟2第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法 否那么，沿反射的反方向搜索定新點。5) 如用上述方法失敗，那么依次用次壞點替代最壞點 作為映射點

18、，轉(zhuǎn)步驟36) 如用最好點替代AH作為映射點，仍找不到好點，或 復合形退化到n-1維空間時，表示算法收斂。此時， 取復合形頂點中最好的點作為離散優(yōu)化解。(三)離散變量型網(wǎng)格法 1. 離散變量型普通網(wǎng)格法 根本思想：以一定的變量增量為間隔，把設計空間劃分為假設干個網(wǎng)格，計算在可行域內(nèi)每個網(wǎng)格節(jié)點上的目的函數(shù)值，比較其大小，再以目的函數(shù)值最小的節(jié)點為中心，在其附近空間劃分更小的網(wǎng)格，并計算各節(jié)點上的目的函數(shù)值，直至網(wǎng)格小到滿足精度網(wǎng)格節(jié)點密度與離散點密度相等。 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法開場時網(wǎng)格比較稀疏網(wǎng)格節(jié)點密度逐漸添加直至按一個離散增量劃分網(wǎng)格節(jié)點為止。2離散變量型正

19、交網(wǎng)格法 普通網(wǎng)格法的缺陷： 變量維數(shù)添加時，計算任務量大大添加正交網(wǎng)格法根本思想： 根據(jù)正交實驗法的原理，利用正交表均勻地選取網(wǎng)格法中一部分有代表性的網(wǎng)格點作為計算點，又稱隨機正交網(wǎng)格法。正交網(wǎng)格法的特點：只計算部分網(wǎng)格點的目的函數(shù)值，計算任務量少。第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法(四)離散變量的組合型法MDCP法 工程離散優(yōu)化通用方法 根本思想：以離散復合形法為根底，采用多種離散搜索戰(zhàn)略，構(gòu)成的具有多種功能的組合型算法。 適于求解非線性混合離散變量優(yōu)化問題1初始離散復合形頂點的構(gòu)成復合形頂點數(shù)k=2n+1給定初始離散點x(0)，x(0)須滿足變量值的邊境條件，但不用滿足約

20、束條件，即式中，ximin，ximax分別為第i個變量的下、上限 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法點號數(shù)分量號數(shù)復合形的2n+1個頂點按下面方法產(chǎn)生第1個頂點： 第2至n+1個頂點： 第n+2至2n+1個頂點： 如此產(chǎn)生的復合形頂點，不要求全是可行點，如圖，5個初始復合形頂點中，C、D兩點為不可行點。例如二維： 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法2、離散一維搜索產(chǎn)生新點 將復合形頂點目的函數(shù)值排隊，找出目的函數(shù)值最大的點為最壞點，x(b) 以x(b)為基點，向其他各頂點的幾何中心x(e)方向作一維搜索，采用映射、延伸或收縮等步驟搜索搜索方向S的各分量Si計算式為： 離散一維搜索得到的新點為x(t)其各分量為： 取 第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法離散一維搜索得到的新點為x(t)其各分量為： 取 其中 表示取最接近 離散一維搜索方法可采用離散一維搜索進退對分法，步長為單位離散步長的整倍數(shù)。的離散值。T-步長因子第六章 第三節(jié) 離散變量優(yōu)化問題與離散變量優(yōu)化方法在產(chǎn)生初始復合形頂點及一維離散搜索時，均未思索約束條件，為保證復合形迭代限制在可行域內(nèi)，定義一個有效目的函