華中科技大學(xué)工程優(yōu)化設(shè)計(jì)-約束直接法

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

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

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

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

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

7、(Design Of Experiments, DOE)Design Of Experiments, DOE)(1) (1) 算法思想算法思想通過合理的采樣和統(tǒng)計(jì)分析通過合理的采樣和統(tǒng)計(jì)分析, ,得到優(yōu)化問題總體變化趨勢得到優(yōu)化問題總體變化趨勢, ,為進(jìn)一步搜索提供基礎(chǔ)為進(jìn)一步搜索提供基礎(chǔ). .試驗(yàn)設(shè)計(jì)試驗(yàn)設(shè)計(jì)試驗(yàn)設(shè)計(jì)試驗(yàn)設(shè)計(jì)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í)驗(yàn)數(shù)實(shí)驗(yàn)數(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í)驗(yàn)數(shù)實(shí)驗(yàn)數(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試驗(yàn)設(shè)計(jì)試驗(yàn)設(shè)計(jì)試驗(yàn)設(shè)計(jì)ANOVA （Analysis of Variance）變差分析變差分析:紅色紅色: : 負(fù)影響負(fù)影響藍(lán)色藍(lán)色: : 正影響正影響影響幅度大影響幅度大影響幅度小影響幅度小試驗(yàn)設(shè)計(jì)試驗(yàn)設(shè)計(jì)試

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

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

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