1、 離散變量問(wèn)題優(yōu)化算法 （Algorithms for Discrete Variable Problem）一般的優(yōu)化方法只能求得連續(xù)變量的最優(yōu)解。工程實(shí)際中存在大量混合設(shè)計(jì)變量問(wèn)題?；旌显O(shè)計(jì)變量包含：連續(xù)設(shè)計(jì)變量、整型設(shè)計(jì)變量和離散設(shè)計(jì)變量。9.1 9.1 引言引言例如：齒輪傳動(dòng)裝置的優(yōu)化設(shè)計(jì)，齒數(shù)是一個(gè)整型量，模數(shù)是一系列離散量，變位系數(shù)可以看做連續(xù)量，齒寬若按長(zhǎng)度1mm單位計(jì)算，則也可以看做整型量。 求離散問(wèn)題的最優(yōu)解，傳統(tǒng)的方法是先用連續(xù)變量?jī)?yōu)化設(shè)計(jì)方法求連續(xù)變量的最優(yōu)解，然后圓整到離散值上。 弊?。嚎赡艿貌坏娇尚凶顑?yōu)解，或所得的解不是離散最優(yōu)解。x *為連續(xù)變量最優(yōu)解；x(1)是圓整

2、后最近的離散點(diǎn)，但不可行；x(2)是最近的可行離散點(diǎn)，但不是離散最優(yōu)點(diǎn)；x(3)是離散最優(yōu)點(diǎn)。傳統(tǒng)方法的局限性 離散變量?jī)?yōu)化難點(diǎn)：不存在指導(dǎo)搜索過(guò)程的最優(yōu)性條件。 直接方法：枚舉法（enumeration）?？尚悬c(diǎn)過(guò)多時(shí)，計(jì)算量大。 減少計(jì)算量：隨機(jī)思想（stochastic ideas）、啟發(fā)式原則（heuristic rules）。 兩種基本方法： （隱式）枚舉法：如，分枝定界法（the branch and bound algorithm）； 隨機(jī)或進(jìn)化方法：如，模擬退火算法、遺傳算法等。離散變量?jī)?yōu)化方法9.3 9.3 分枝定界法（the branch and bound algorit

3、hm）松弛問(wèn)題：以整型優(yōu)化問(wèn)題為例：121212112max5 256 30. . 4,0Zxxxxxxs txxx 且全為整數(shù)121212112max5 256 30. . 4,0Zxxxxxxs txxx 引入概念：松弛問(wèn)題。分枝定界法基本思想：設(shè)有最大化的整型優(yōu)化問(wèn)題A，相應(yīng)有松弛問(wèn)題B，從解松弛問(wèn)題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù) 的上界，記作 ；而A的任意可行解的目標(biāo)函數(shù)值將是 的一個(gè)下界，記作 。 分枝定界法就是將B的可行域分成子區(qū)域(稱為分枝)的方法，逐步減小 ，增大 ，最終求到 。zzz*zzz*z*z*zz（1）分枝在松弛問(wèn)題B的

4、最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量 ,其值為 ,以 表示小于 的最大整數(shù)。構(gòu)造兩個(gè)約束條件jxjbjb 1jjjjxbxb和jb將這兩個(gè)約束條件,分別加入問(wèn)題B,求兩個(gè)后繼規(guī)劃問(wèn)題B1和B2,不考慮整數(shù)條件求解這兩個(gè)后繼問(wèn)題.三個(gè)基本操作：（2）定界以每個(gè)后繼問(wèn)題為一分枝標(biāo)明求解結(jié)果,在解的結(jié)果中,找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界.從已符合整數(shù)條件的各分支中,找出目標(biāo)函數(shù)值為最大者作為新的下界,若無(wú),則下界為0.（3）比較與剪枝各分支的最優(yōu)目標(biāo)函數(shù)中若有小于 ，則剪掉這枝；若大于 且不符合整數(shù)條件，則重復(fù)前兩步，直到找到最優(yōu)解。zz分枝定界法計(jì)算過(guò)程：:0L討論松弛問(wèn)題無(wú)最優(yōu)解，、01L

5、無(wú)最優(yōu)解則)(IP結(jié)束002010),*,*(*2zxxxXon最優(yōu)值，、最優(yōu)解為整數(shù)解0*) 1 ( X的最優(yōu)解為，則)(*0IPX中至少有一個(gè)是分?jǐn)?shù)，0*)2(X結(jié)束是分?jǐn)?shù)設(shè)01*x：分枝上界x1x*01:1L子問(wèn)題x1x*01+1:2L子問(wèn)題無(wú)最優(yōu)解，、11L剪枝為下界1,z關(guān)閉繼續(xù)分枝1112111),*,*(*2zxxxXn最優(yōu)值，、最優(yōu)解為整數(shù)解1*) 1 ( X中至少有一個(gè)是分?jǐn)?shù)：1*)2(X：設(shè)已找到下界0iZ是整數(shù)解最優(yōu)解kX *) 1 (:kL討論子問(wèn)題kL關(guān)閉,不是整數(shù)解最優(yōu)解kX *)2(分枝繼續(xù)對(duì)kL當(dāng)所有的子問(wèn)題均被關(guān)閉或剪枝后目標(biāo)函數(shù)值最大的整數(shù)解既為所求的最優(yōu)解

6、若 的最優(yōu)值 ，剪枝kL0kiZZ若 的最優(yōu)值 ；0kiZZkL將下界改為kZ例：用分枝定界法求解整型優(yōu)化問(wèn)題（用圖解法計(jì)算）：121212112max5 256 30. . 4,0Zxxxxxxs txxx 且全為整數(shù) 首先去掉整數(shù)約束，變?yōu)橐话憔€性優(yōu)化問(wèn)題（松弛問(wèn)題），記為L(zhǎng)P：121212112max5 256 30. . 4,0Zxxxxxxs txxx 求出松弛問(wèn)題最優(yōu)解：即 也是離散問(wèn)題目標(biāo)函數(shù)的上限。121212112max5 256 30. . 4,0Zxxxxxxs txxx 12(0) *(x , x )(18 /11, 40 /11) 218 /1119.8Zx x0Z

7、（ ）先將（LP）劃分為（LP1）和（LP2）,取 。11122218 /111.641240 /11 3.6434xxxxxx對(duì)于 ，取值，對(duì)于，取值，12(0) *(x , x )(18 /11, 40 /11) 218 /1119.8Zx x松弛問(wèn)題最優(yōu)解：1 11, 2xx 現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。12121211max5 256 30(1) 4 1ZxxxxxxIPxx 12121211max5 256 30(2) 4 2ZxxxxxxIPxx 將（LP）劃分為（LP1）和（LP2）,取 。1 11, 2xx 先求（LP1）,如圖所示。12121211max5

8、 256 30(1) 4 1ZxxxxxxIPxx 先求（LP1）,如圖所示。此時(shí)B在點(diǎn)取得最優(yōu)解。 1121,3, 16xxZ12121211max5 256 30(1) 4 1ZxxxxxxIPxx 求（LP2）,如圖所示。在C 點(diǎn)取得最優(yōu)解。 1222,10 / 3,56 / 318.7xxZ12121211max5 256 30(2) 4 2ZxxxxxxIPxx Z (2)Z(1) =16 ，原問(wèn)題可能有比（原問(wèn)題可能有比（16）更大的最優(yōu)解；）更大的最優(yōu)解；但但 x2 不是整數(shù)，故利用不是整數(shù)，故利用 x2 3 ， x2 4 加入條件。加入條件。 現(xiàn)在只要求出（LP21）和（LP2

9、2）的最優(yōu)解即可。將（LP2）劃分為（LP21）和（LP22）,取 。223,4xx121212112max5 256 30(21) 4 2 3ZxxxxxxIPxxx 121212112max5 256 30(22) 4 2 4ZxxxxxxIPxxx 先求（LP21）,如圖所示。在D 點(diǎn)取得最優(yōu)解。122112 / 52.4,3,87 / 517.4xxZ121212112max5 256 30(21) 4 2 3ZxxxxxxIPxxx 求（LP22），如圖所示。無(wú)可行解，不再分枝。121212112max5 256 30(22) 4 2 4ZxxxxxxIPxxx LP21LP21取得

10、最優(yōu)解：取得最優(yōu)解：且有且有x12.4不是整數(shù)，可繼續(xù)分枝，令不是整數(shù)，可繼續(xù)分枝，令 x12， x1 3。 12312 / 52.4,3,87 / 517.4xxZ 13ZZ剪枝剪枝 現(xiàn)在只要求出（LP211）和（LP222）的最優(yōu)解即可。將（LP21）劃分為（LP211）和（LP222）,取 。112,3xx1212121121max5 256 30 4(211) 2 3 2ZxxxxxxxIPxxx 1212121121max5 256 30 4(212) 2 3 3ZxxxxxxxIPxxx 先求（LP211）1212121121max5 256 30 4(211) 2 3 2Zxxx

11、xxxxIPxxx 先求（LP211）如圖所示，此時(shí)E 在點(diǎn)取得最優(yōu)解：122112,3, 17xxZ1212121121max5 256 30 4(211) 2 3 2ZxxxxxxxIPxxx 求（LP212）如圖所示，此時(shí)F 在點(diǎn)取得最優(yōu)解：122123,2.5,31/ 215.5xxZ1212121121max5 256 30 4(212) 2 3 3ZxxxxxxxIPxxx 找到找到最優(yōu)最優(yōu)解解（1） 若分枝后得到整數(shù)解，則這枝不必再分枝；（2） 若分枝后得到非整數(shù)解, 如果比整數(shù)解更好，則這枝繼續(xù)分枝；（3） 若分枝后得到非整數(shù)解, 如果比整數(shù)解更差，則這枝不必再分枝。幾點(diǎn)注意事

12、項(xiàng)：9.3 9.3 離散變量?jī)?yōu)化離散變量?jī)?yōu)化組合形法組合形法DC TDT12T12minf( ). .( )01,2,=, ,nuDDpCCCppnnDCRstgumxx xxxxxxxxxxxXRxXRRRR （P維)離散變量向量； （n-P維)連續(xù)變量向量； 離散設(shè)計(jì)空間； 連續(xù)設(shè)計(jì)空間； 分別表示離散子空間和連續(xù)子空間。DxCxDXCXDCRR和離散變量數(shù)學(xué)模型的一般形式：離散變量數(shù)學(xué)模型的一般形式： 以復(fù)合形法為基礎(chǔ)發(fā)展而來(lái)，使之能在離散空間中直接搜索離散點(diǎn)，從而滿足求解離散變量?jī)?yōu)化問(wèn)題的需要。 基本思想：通過(guò)對(duì)初始復(fù)合形調(diào)優(yōu)迭代使新的組合形不斷向最優(yōu)點(diǎn)移動(dòng)和收縮，直至滿足一定的終止條

13、件為止。 下面分五個(gè)部分介紹離散變量組合形法： （1）初始離散組合形的產(chǎn)生 （2）離散一維搜索 （3）約束條件處理 （4）組合形的調(diào)整 （5）收斂準(zhǔn)則9.3.1 9.3.1 初始離散組合形的產(chǎn)生初始離散組合形的產(chǎn)生 頂點(diǎn)數(shù)： 初始離散點(diǎn)記為 ，不必滿足約束條件，但各分量必須滿足變量值邊界條件，即 式中， 第 個(gè)變量的下界值； 第 個(gè)變量的上界值。 組合形 個(gè)頂點(diǎn)：第一個(gè)頂點(diǎn)：第2個(gè)至 個(gè)頂點(diǎn)： 二維離散組合形的初始頂點(diǎn)第 至 個(gè)頂點(diǎn)：K21n(0)x(0)1,2,LUiixxxinLixUxii21n(0)=1,2,iixxin（1）1n(0)1,2, ;1,2,iixxinijjn（j+1）

14、L1,2,iixxijn（j+1）2n21n(0)1,2, ;1,2,iixxinijjn（n+j+1）1,2,Uiixxijn（n+j+1）+L22=xx（2 1）9.3.2 9.3.2 離散一維搜索離散一維搜索 對(duì)初始組合形各頂點(diǎn)目標(biāo)函數(shù)值排序，最大值處為最壞頂點(diǎn)，最小值處為最好頂點(diǎn)。 離散一維搜索以最壞點(diǎn)為基點(diǎn)，設(shè)標(biāo)號(hào)為 ，以最壞頂點(diǎn)至其余各頂點(diǎn)的幾何中心點(diǎn)的方向向量為搜索方向 ，其各分量為：式中， 除最壞頂點(diǎn) 后其他頂點(diǎn)的幾何中心。 新點(diǎn)各分量值為：式中， 離散一維搜索步長(zhǎng)因子； 對(duì)離散變量取最靠近的離散值 。bs(c)(b)(c)(j)11,2,11,2,1iiiKiijj bsxx

15、inxxinK(c)x(b)x(t)(b)(t)(t)1,2,1,2,piiiiixxT SinxxiTijq9.3.2 9.3.2 離散一維搜索（續(xù)）離散一維搜索（續(xù)） 離散一維搜索采用進(jìn)退對(duì)分法。1）令 ；2）求新點(diǎn) ；3）若 點(diǎn)較 點(diǎn)好，則 ，否則 ；4）若 ，則 ，返回步驟2）；否則 ， 返回步驟2）；5）終止準(zhǔn)則，當(dāng) 時(shí)，離散一維搜索終止。 為最小有用步長(zhǎng)因子。10TTT，R=1(t)x(t)x(b)x(b)(t)=xx0R 1R 1112+TTTTT，111TTTTT/2，1minTTminTmin1,3,1,2,=min,iiiiipippnTSS ii離散變量增量連續(xù)變量擬增量

16、或精度值9.3.3 9.3.3 約束條件的處理約束條件的處理 初始組合形頂點(diǎn)的產(chǎn)生及一維離散搜索未考慮約束條件，為使組合形調(diào)優(yōu)迭代在可行域內(nèi)進(jìn)行，定義一個(gè)有效目標(biāo)函數(shù)：式中， 比 值的數(shù)量級(jí)大得多的常數(shù)； 與所有違反約束量的總和成正比的量。式中， 常數(shù)； 違反約束的集合。如右圖所示，有效目標(biāo)函數(shù) 的幾何圖形，像一個(gè)向可行域傾斜的“漏斗”。程序會(huì)自動(dòng)先從不可行點(diǎn)尋找可行點(diǎn)，然后再?gòu)目尚悬c(diǎn)尋找最優(yōu)點(diǎn)。( )( )M SUMf xxEF xxM( )f xSUM( )( )( )( )01,2,uu I xuSUMCgxI xu gxumC( )I x( )EF x9.3.4 9.3.4 輔助功能和

17、終止準(zhǔn)則輔助功能和終止準(zhǔn)則 輔助功能：組合形調(diào)優(yōu)方向 找不到新點(diǎn)，可用下面兩種方法：（1）用次壞點(diǎn)（也可以取第2、3直至第 個(gè)頂點(diǎn)）與其余頂點(diǎn)幾何中心的連線取代原搜索方向。（2）若未取得更好效果，則將每個(gè)頂點(diǎn)向好點(diǎn)方向收縮1/3，構(gòu)成新的組合形繼續(xù)迭代。 兩個(gè)步驟可交替進(jìn)行。( )I xs21n9.3.4 9.3.4 輔助功能和終止準(zhǔn)則（續(xù)）輔助功能和終止準(zhǔn)則（續(xù)）終止準(zhǔn)則： 回顧，連續(xù)變量復(fù)合形法，各頂點(diǎn)目標(biāo)函數(shù)值與幾何中心點(diǎn)的目標(biāo)函數(shù)值得均方根差小于某個(gè)很小的正數(shù)，或者當(dāng)復(fù)合形的“邊長(zhǎng)”很小時(shí)而定。 組合形在每個(gè)坐標(biāo)上的當(dāng)前點(diǎn)的檢驗(yàn)長(zhǎng)度：第 個(gè)坐標(biāo)方向上的“長(zhǎng)度”為將 值與相應(yīng)的離散坐標(biāo)的離散增量值（連續(xù)變量擬增量為 ）進(jìn)行比較，若小于離散增量值得分量總數(shù)小于預(yù)先給定的個(gè)數(shù)（ ），則認(rèn)為收斂。(j)(j)max1,2,21min1,2,21iiiiaxjnbxjn，i1,2,iiidabinidi1n9.3.5 9.3.5 離散變量組合形算法基本步驟離散變量組合形算法基本步驟1）選取符合變量邊界條件的初始頂點(diǎn) ；確定各設(shè)計(jì)變量上下界值 和 ，連續(xù)變量擬離散增量 （ ）；收斂準(zhǔn)