1、工程優(yōu)化設(shè)計內(nèi)容提要 工程優(yōu)化問題建模工程優(yōu)化問題建模 優(yōu)化數(shù)學(xué)理論優(yōu)化數(shù)學(xué)理論 一維搜索方法一維搜索方法 無約束問題直接搜索方法無約束問題直接搜索方法 無約束問題間接接搜索方法無約束問題間接接搜索方法 約束問題直接搜索方法約束問題直接搜索方法 線性規(guī)劃與二次規(guī)劃問題求解線性規(guī)劃與二次規(guī)劃問題求解 約束問題間接搜索方法約束問題間接搜索方法 啟發(fā)式算法啟發(fā)式算法 優(yōu)化軟件系統(tǒng)優(yōu)化軟件系統(tǒng)約束直接搜索方法直接法直接法: : 利用迭代過程已有信息和再生信息進(jìn)行試探和求優(yōu)利用迭代過程已有信息和再生信息進(jìn)行試探和求優(yōu), ,不需要用到函數(shù)導(dǎo)數(shù)和分析性質(zhì)。不需要用到函數(shù)導(dǎo)數(shù)和分析性質(zhì)。 適用于僅含不等式約束

2、的優(yōu)化問題適用于僅含不等式約束的優(yōu)化問題. . 新的迭代點必須限新的迭代點必須限制在不等式約束構(gòu)成的可性域內(nèi)制在不等式約束構(gòu)成的可性域內(nèi), ,且保證目標(biāo)函數(shù)的穩(wěn)定下降且保證目標(biāo)函數(shù)的穩(wěn)定下降. .隨機實驗法隨機實驗法隨機方向法隨機方向法復(fù)合形法復(fù)合形法1.1. 實驗設(shè)計法實驗設(shè)計法約束直接搜索方法一一. .隨機實驗法隨機實驗法( (Monte-CarloMonte-Carlo法法) )(1) (1) 算法思想算法思想通過逐步隨機取樣通過逐步隨機取樣, ,逼近最優(yōu)解逼近最優(yōu)解. .每步隨機取樣得到一組點上的函數(shù)值每步隨機取樣得到一組點上的函數(shù)值, ,通過比較確定最優(yōu)解通過比較確定最優(yōu)解的較小范圍

3、的較小范圍. .下一步在上一步確定的范圍內(nèi)再隨機取樣下一步在上一步確定的范圍內(nèi)再隨機取樣, ,確定確定更小的最優(yōu)解范圍更小的最優(yōu)解范圍, ,如此下去如此下去, ,不斷逼近最優(yōu)解不斷逼近最優(yōu)解. .不斷縮小最優(yōu)解不斷縮小最優(yōu)解的范圍的范圍隨機實驗法隨機實驗法( (Monte-CarloMonte-Carlo法法) )(2) (2) 算法算法隨機實驗法隨機實驗法( (Monte-CarloMonte-Carlo法法) )(3) (3) 算法分析算法分析約束直接搜索方法算法簡單算法簡單, , 容易實現(xiàn)容易實現(xiàn). .依概率收斂依概率收斂, ,即以概率為即以概率為1 1收斂到最優(yōu)解收斂到最優(yōu)解, ,但采

4、樣點需要無窮多但采樣點需要無窮多. .采樣點多采樣點多, ,運算量大運算量大, ,效率低效率低. .約束直接搜索方法二二. .隨機方向法隨機方向法(1) (1) 算法思想算法思想通過在當(dāng)前點的附近隨機采樣，確定最速下降方向，進(jìn)行有通過在當(dāng)前點的附近隨機采樣，確定最速下降方向，進(jìn)行有約束的一維搜索，找到新的點。約束的一維搜索，找到新的點。約束直接搜索方法二二. .隨機方向法隨機方向法(2) (2) 算法算法- -初始點生成初始點生成約束直接搜索方法二二. .隨機方向法隨機方向法(2) (2) 算法算法- -搜索方向生成搜索方向生成約束直接搜索方法二二. .隨機方向法隨機方向法(2) (2) 算法

5、算法- -步驟步驟約束直接搜索方法二二. .復(fù)合形法復(fù)合形法(1) (1) 算法思想算法思想對于對于n n維變量空間維變量空間, ,單純形是單純形是n+1n+1個頂點個頂點. .復(fù)合形法是多個單純形合并成的超多面體復(fù)合形法是多個單純形合并成的超多面體, ,頂點數(shù)頂點數(shù) n+1.n+1.復(fù)合形法與復(fù)合形法與單純形無約束直接搜索法單純形無約束直接搜索法極為相似極為相似, ,其不同之處其不同之處: :1.1.復(fù)合形法不限制頂點個數(shù)為復(fù)合形法不限制頂點個數(shù)為n+1,n+1,復(fù)合形法頂點個數(shù)是復(fù)合形法頂點個數(shù)是k, k, 2n 2n k k n+1.n+1.2.2.復(fù)合形法需要檢查頂點的可行性復(fù)合形法需

6、要檢查頂點的可行性, , 即是否滿足約束即是否滿足約束. .初始復(fù)合形法生成初始復(fù)合形法生成復(fù)合形法復(fù)合形法(2) (2) 算法算法XcXl轉(zhuǎn)（轉(zhuǎn)（3）復(fù)合形法復(fù)合形法(2) (2) 算法算法約束直接搜索方法二二. .復(fù)合形法復(fù)合形法(3) (3) 算法分析算法分析1.1.適應(yīng)性強適應(yīng)性強, ,無需導(dǎo)數(shù)無需導(dǎo)數(shù). .2.2.程序較簡單程序較簡單. .3.3.當(dāng)變量與約束較多時當(dāng)變量與約束較多時, ,計算效率顯著降低計算效率顯著降低. .4.4.當(dāng)當(dāng)n n 5 5時時, ,可取可取k=2n,k=2n,當(dāng)當(dāng)n5n5時時, ,可取可取k2n.k2n.約束直接搜索方法三三. .實驗設(shè)計法實驗設(shè)計法(

7、(Design Of Experiments, DOE)Design Of Experiments, DOE)(1) (1) 算法思想算法思想通過合理的采樣和統(tǒng)計分析通過合理的采樣和統(tǒng)計分析, ,得到優(yōu)化問題總體變化趨勢得到優(yōu)化問題總體變化趨勢, ,為進(jìn)一步搜索提供基礎(chǔ)為進(jìn)一步搜索提供基礎(chǔ). .試驗設(shè)計試驗設(shè)計試驗設(shè)計試驗設(shè)計1234 1 1 1 3 2 2 2 1 1 1 3 3 1 2 3 4 1 2 2 1 5 2 2 3 3 6 3 2 1 2 7 1 3 1 3 8 2 3 2 2 9 3 3 3 1在一列中每一水平值出現(xiàn)頻率相等：在一列中每一水平值出現(xiàn)頻率相等： 出現(xiàn)次數(shù)出現(xiàn)次數(shù)

8、= =實驗數(shù)實驗數(shù)/ /水平數(shù)水平數(shù); ; 1 1出現(xiàn)次數(shù)出現(xiàn)次數(shù) =9/3=3 =9/3=3在兩列中每兩水平值組合在兩列中每兩水平值組合( (L L1 1,L,L2 2) )出現(xiàn)出現(xiàn)頻率相等：頻率相等： 出現(xiàn)次數(shù)出現(xiàn)次數(shù)= =實驗數(shù)實驗數(shù)/(/(列列1 1水平數(shù)水平數(shù)* *列列2 2水水平數(shù)平數(shù));); (2,1) (2,1)出現(xiàn)次數(shù)出現(xiàn)次數(shù)=9/(3=9/(3* *3)=13)=1試驗設(shè)計試驗設(shè)計試驗設(shè)計ANOVA （Analysis of Variance）變差分析變差分析:紅色紅色: : 負(fù)影響負(fù)影響藍(lán)色藍(lán)色: : 正影響正影響影響幅度大影響幅度大影響幅度小影響幅度小試驗設(shè)計試驗設(shè)計試

9、驗設(shè)計試驗設(shè)計試驗設(shè)計試驗設(shè)計試驗設(shè)計ANOVA 分析結(jié)果分析結(jié)果:1616次實驗次實驗, , sfc sfc 的兩個的兩個水平上各計算水平上各計算8 8個點個點, ,8 8個點上的平均個點上的平均RangeRange值變化如右圖值變化如右圖, , 是是sfcsfc對對RangeRange的主效應(yīng)圖的主效應(yīng)圖. .在在8 8個點中，個點中，sfcsfc相同，但相同，但其他設(shè)計變量的變化，引其他設(shè)計變量的變化，引起起RangeRange變化。變化。試驗設(shè)計ANOVA 分析結(jié)果分析結(jié)果: :單因子主效應(yīng)圖單因子主效應(yīng)圖多因子主效應(yīng)圖多因子主效應(yīng)圖試驗設(shè)計PricemfrrangePricemfrr

10、angeInteraction effectsrange 的變化對的變化對mfr-price 關(guān)系有影響關(guān)系有影響試驗設(shè)計試驗設(shè)計試驗設(shè)計在在range相同的條件下相同的條件下, 計算計算Mfr的均差的均差.計算不同計算不同range的的Mfr 效果的變化效果的變化.在短航程中在短航程中,Airbus比比Boeing貴平貴平均均$4.8M在長航程中在長航程中,Airbus比比Boeing貴平貴平均均$0.45M隨著航程的增加隨著航程的增加, Airbus比比Boeing高高出的價格在減小出的價格在減小試驗設(shè)計試驗設(shè)計WingArea=LowWingArea=HighCruiseVelCruis

11、eVelAircraftRangeCruiseVelWingArea1.1.評估設(shè)計變量對目標(biāo)性能的影響評估設(shè)計變量對目標(biāo)性能的影響, ,確定確定最有影響的設(shè)計最有影響的設(shè)計變量變量. .2.2.找出設(shè)計變量之間的找出設(shè)計變量之間的重要相互作用重要相互作用. .3.3.對設(shè)計空間作大致的分析對設(shè)計空間作大致的分析, ,找出最優(yōu)解在設(shè)計空間中的找出最優(yōu)解在設(shè)計空間中的大致位置大致位置, ,為優(yōu)化搜索算法為優(yōu)化搜索算法提供初始搜索起點提供初始搜索起點. .4.4.通過粗略計算分析通過粗略計算分析, ,剔除對性能目標(biāo)函數(shù)不取作用的設(shè)剔除對性能目標(biāo)函數(shù)不取作用的設(shè)計變量計變量, ,使得優(yōu)化使得優(yōu)化搜索空間減小搜索空間減小. .5.5.為為響應(yīng)面近似響應(yīng)面近似計算原始數(shù)據(jù)計算原始數(shù)據(jù). .約束直接搜索方法DOE的作用的作用約束直接搜索方法約束直接搜索方法總結(jié)總結(jié)Monte-CarloMonte-Carlo法法-程序簡單，程序簡單，應(yīng)用較廣應(yīng)用較廣；但但隨機采樣效率較低。隨機采樣效率較低。復(fù)合形法復(fù)合形法-繼承傳統(tǒng)無約束問題精確搜索計算的特點。繼承傳統(tǒng)無約束問題精確搜索計算的特點。隨機方向法隨機方向法結(jié)合隨機采樣與精確搜索的優(yōu)點。結(jié)合隨機采樣與精確搜索的優(yōu)點。DOEDOE法法-簡單實用簡單實用, , 在優(yōu)化設(shè)計中具有重要作用。在優(yōu)化設(shè)計中具有重