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

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

2、的優(yōu)化問(wèn)題適用于僅含不等式約束的優(yōu)化問(wèn)題. . 新的迭代點(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) 算法思想算法思想通過(guò)逐步隨機(jī)取樣通過(guò)逐步隨機(jī)取樣, ,逼近最優(yōu)解逼近最優(yōu)解. .每步隨機(jī)取樣得到一組點(diǎn)上的函數(shù)值每步隨機(jī)取樣得到一組點(diǎn)上的函數(shù)值, ,通過(guò)比較確定最優(yōu)解通過(guò)比較確定最優(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) 算法分析算法分析約束直接搜索方法算法簡(jiǎn)單算法簡(jiǎn)單, , 容易實(shí)現(xiàn)容易實(shí)現(xiàn). .依概率收斂依概率收斂, ,即以概率為即以概率為1 1收斂到最優(yōu)解收斂到最優(yōu)解, ,但采

4、樣點(diǎn)需要無(wú)窮多但采樣點(diǎn)需要無(wú)窮多. .采樣點(diǎn)多采樣點(diǎn)多, ,運(yùn)算量大運(yùn)算量大, ,效率低效率低. .約束直接搜索方法二二. .隨機(jī)方向法隨機(jī)方向法(1) (1) 算法思想算法思想通過(guò)在當(dāng)前點(diǎn)的附近隨機(jī)采樣，確定最速下降方向，進(jìn)行有通過(guò)在當(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) 算法思想算法思想對(duì)于對(duì)于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ù)合形法與單純形無(wú)約束直接搜索法單純形無(wú)約束直接搜索法極為相似極為相似, ,其不同之處其不同之處: :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), ,無(wú)需導(dǎo)數(shù)無(wú)需導(dǎo)數(shù). .2.2.程序較簡(jiǎn)單程序較簡(jiǎn)單. .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) 算法思想算法思想通過(guò)合理的采樣和統(tǒng)計(jì)分析通過(guò)合理的采樣和統(tǒng)計(jì)分析, ,得到優(yōu)化問(wèn)題總體變化趨勢(shì)得到優(yōu)化問(wèn)題總體變化趨勢(shì), ,為進(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在兩列中每?jī)伤街到M合在兩列中每?jī)伤街到M合( (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對(duì)對(duì)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 的變化對(duì)的變化對(duì)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在長(zhǎng)航程中在長(zhǎng)航程中,Airbus比比Boeing貴平貴平均均$0.45M隨著航程的增加隨著航程的增加, Airbus比比Boeing高高出的價(jià)格在減小出的價(jià)格在減小試驗(yàn)設(shè)計(jì)試驗(yàn)設(shè)計(jì)WingArea=LowWingArea=HighCruiseVelCruis

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