离散变量优化问题课件.ppt

1、 离散变量问题优化算法 （Algorithms for Discrete Variable Problem）一般的优化方法只能求得连续变量的最优解。工程实际中存在大量混合设计变量问题。混合设计变量包含：连续设计变量、整型设计变量和离散设计变量。9.1 9.1 引言引言例如：齿轮传动装置的优化设计，齿数是一个整型量，模数是一系列离散量，变位系数可以看做连续量，齿宽若按长度1mm单位计算，则也可以看做整型量。求离散问题的最优解，传统的方法是先用连续变量优化设计方法求连续变量的最优解，然后圆整到离散值上。弊病：可能得不到可行最优解，或所得的解不是离散最优解。x*为连续变量最优解；x(1)是圆整后最近

2、的离散点，但不可行；x(2)是最近的可行离散点，但不是离散最优点；x(3)是离散最优点。传统方法的局限性 离散变量优化难点：不存在指导搜索过程的最优性条件。直接方法：枚举法（enumeration）。可行点过多时，计算量大。减少计算量：随机思想（stochastic ideas）、启发式原则（heuristic rules）。两种基本方法：（隐式）枚举法：如，分枝定界法（the branch and bound algorithm）；随机或进化方法：如，模拟退火算法、遗传算法等。离散变量优化方法9.3 9.3 分枝定界法（the branch and bound algorithm）松弛问题：

3、以整型优化问题为例：121212112max5 256 30.4,0Zxxxxxxs txxx 且全为整数121212112max5 256 30.4,0Zxxxxxxs txxx 引入概念：松弛问题。分枝定界法基本思想：设有最大化的整型优化问题A，相应有松弛问题B，从解松弛问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数 的上界，记作 ；而A的任意可行解的目标函数值将是 的一个下界，记作 。分枝定界法就是将B的可行域分成子区域(称为分枝)的方法，逐步减小 ，增大 ，最终求到 。zzz*zzz*z*z*zz（1）分枝在松弛问题B的最优解中任选一个不符合整数条件

4、的变量 ,其值为 ,以 表示小于 的最大整数。构造两个约束条件jxjbjb 1jjjjxbxb和jb将这两个约束条件,分别加入问题B,求两个后继规划问题B1和B2,不考虑整数条件求解这两个后继问题.三个基本操作：（2）定界以每个后继问题为一分枝标明求解结果,在解的结果中,找出最优目标函数值最大者作为新的上界.从已符合整数条件的各分支中,找出目标函数值为最大者作为新的下界,若无,则下界为0.（3）比较与剪枝各分支的最优目标函数中若有小于 ，则剪掉这枝；若大于 且不符合整数条件，则重复前两步，直到找到最优解。zz分枝定界法计算过程：:0L讨论松弛问题无最优解，、01L无最优解则)(IP结束0020

5、10),*,*(*2zxxxXon最优值，、最优解为整数解0*)1(X的最优解为，则)(*0IPX中至少有一个是分数，0*)2(X结束是分数设01*x：分枝上界x1x*01:1L子问题x1x*01+1:2L子问题无最优解，、11L剪枝为下界1,z关闭继续分枝1112111),*,*(*2zxxxXn最优值，、最优解为整数解1*)1(X中至少有一个是分数：1*)2(X：设已找到下界0iZ是整数解最优解kX*)1(:kL讨论子问题kL关闭,不是整数解最优解kX*)2(分枝继续对kL当所有的子问题均被关闭或剪枝后目标函数值最大的整数解既为所求的最优解若 的最优值 ，剪枝kL0kiZZ若 的最优值 ；

6、0kiZZkL将下界改为kZ例：用分枝定界法求解整型优化问题（用图解法计算）：121212112max5 256 30.4,0Zxxxxxxs txxx 且全为整数 首先去掉整数约束，变为一般线性优化问题（松弛问题），记为LP：121212112max5 256 30.4,0Zxxxxxxs txxx 求出松弛问题最优解：即 也是离散问题目标函数的上限。121212112max5 256 30.4,0Zxxxxxxs txxx 12(0)*(x,x)(18/11,40/11)218/1119.8Zx x0Z（）先将（LP）划分为（LP1）和（LP2）,取 。11122218/111.64124

7、0/11 3.6434xxxxxx对于，取值，对于，取值，12(0)*(x,x)(18/11,40/11)218/1119.8Zx x松弛问题最优解：1 11,2xx 现在只要求出（LP1）和（LP2）的最优解即可。12121211max5 256 30(1)4 1ZxxxxxxIPxx 12121211max5 256 30(2)4 2ZxxxxxxIPxx 将（LP）划分为（LP1）和（LP2）,取 。1 11,2xx 先求（LP1）,如图所示。12121211max5 256 30(1)4 1ZxxxxxxIPxx 先求（LP1）,如图所示。此时B在点取得最优解。1121,3,16xxZ

8、12121211max5 256 30(1)4 1ZxxxxxxIPxx 求（LP2）,如图所示。在C 点取得最优解。1222,10/3,56/318.7xxZ12121211max5 256 30(2)4 2ZxxxxxxIPxx Z(2)Z(1)=16 ，原问题可能有比（原问题可能有比（16）更大的最优解；）更大的最优解；但但 x2 不是整数，故利用不是整数，故利用 x2 3，x2 4 加入条件。加入条件。现在只要求出（LP21）和（LP22）的最优解即可。将（LP2）划分为（LP21）和（LP22）,取 。223,4xx121212112max5 256 30(21)4 2 3Zxxxx

9、xxIPxxx 121212112max5 256 30(22)4 2 4ZxxxxxxIPxxx 先求（LP21）,如图所示。在D 点取得最优解。122112/52.4,3,87/517.4xxZ121212112max5 256 30(21)4 2 3ZxxxxxxIPxxx 求（LP22），如图所示。无可行解，不再分枝。121212112max5 256 30(22)4 2 4ZxxxxxxIPxxx LP21LP21取得最优解：取得最优解：且有且有x12.4不是整数，可继续分枝，令不是整数，可继续分枝，令 x12，x1 3。12312/52.4,3,87/517.4xxZ 13ZZ剪枝

10、剪枝 现在只要求出（LP211）和（LP222）的最优解即可。将（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 2ZxxxxxxxIPxxx 先求（LP211）如图所示，此时E 在点取得最优解：122112,3,17xxZ1212121121max5 256 30 4(211)2 3 2ZxxxxxxxIP

11、xxx 求（LP212）如图所示，此时F 在点取得最优解：122123,2.5,31/215.5xxZ1212121121max5 256 30 4(212)2 3 3ZxxxxxxxIPxxx 找到找到最优最优解解（1）若分枝后得到整数解，则这枝不必再分枝；（2）若分枝后得到非整数解,如果比整数解更好，则这枝继续分枝；（3）若分枝后得到非整数解,如果比整数解更差，则这枝不必再分枝。几点注意事项：9.3 9.3 离散变量优化离散变量优化组合形法组合形法DC TDT12T12minf().()01,2,=,nuDDpCCCppnnDCRstgumxx xxxxxxxxxxxXRxXRRRR （P

12、维)离散变量向量；（n-P维)连续变量向量；离散设计空间；连续设计空间；分别表示离散子空间和连续子空间。DxCxDXCXDCRR和离散变量数学模型的一般形式：离散变量数学模型的一般形式：以复合形法为基础发展而来，使之能在离散空间中直接搜索离散点，从而满足求解离散变量优化问题的需要。基本思想：通过对初始复合形调优迭代使新的组合形不断向最优点移动和收缩，直至满足一定的终止条件为止。下面分五个部分介绍离散变量组合形法：（1）初始离散组合形的产生 （2）离散一维搜索 （3）约束条件处理 （4）组合形的调整 （5）收敛准则9.3.1 9.3.1 初始离散组合形的产生初始离散组合形的产生 顶点数：初始离散

13、点记为 ，不必满足约束条件，但各分量必须满足变量值边界条件，即 式中，第 个变量的下界值；第 个变量的上界值。组合形 个顶点：第一个顶点：第2个至 个顶点：二维离散组合形的初始顶点第 至 个顶点：K21n(0)x(0)1,2,LUiixxxinLixUxii21n(0)=1,2,iixxin（1）1n(0)1,2,;1,2,iixxinijjn（j+1）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 离散一维搜索离散一维搜索 对初始组合形各顶点目标函数值排

14、序，最大值处为最坏顶点，最小值处为最好顶点。离散一维搜索以最坏点为基点，设标号为 ，以最坏顶点至其余各顶点的几何中心点的方向向量为搜索方向 ，其各分量为：式中，除最坏顶点 后其他顶点的几何中心。新点各分量值为：式中，离散一维搜索步长因子；对离散变量取最靠近的离散值 。bs(c)(b)(c)(j)11,2,11,2,1iiiKiijj bsxxinxxinK(c)x(b)x(t)(b)(t)(t)1,2,1,2,piiiiixxT SinxxiTijq9.3.2 9.3.2 离散一维搜索（续）离散一维搜索（续）离散一维搜索采用进退对分法。1）令 ；2）求新点 ；3）若 点较 点好，则 ，否则 ；

15、4）若 ，则 ，返回步骤2）；否则 ，返回步骤2）；5）终止准则，当 时，离散一维搜索终止。为最小有用步长因子。10TTT，R=1(t)x(t)x(b)x(b)(t)=xx0R 1R 1112+TTTTT，111TTTTT/2，1minTTminTmin1,3,1,2,=min,iiiiipippnTSS ii离散变量增量连续变量拟增量或精度值9.3.3 9.3.3 约束条件的处理约束条件的处理 初始组合形顶点的产生及一维离散搜索未考虑约束条件，为使组合形调优迭代在可行域内进行，定义一个有效目标函数：式中，比 值的数量级大得多的常数；与所有违反约束量的总和成正比的量。式中，常数；违反约束的集合

16、。如右图所示，有效目标函数 的几何图形，像一个向可行域倾斜的“漏斗”。程序会自动先从不可行点寻找可行点，然后再从可行点寻找最优点。()()M SUMf xxEF xxM()f xSUM()()()()01,2,uu I xuSUMCgxI xu gxumC()I x()EF x9.3.4 9.3.4 辅助功能和终止准则辅助功能和终止准则 辅助功能：组合形调优方向 找不到新点，可用下面两种方法：（1）用次坏点（也可以取第2、3直至第 个顶点）与其余顶点几何中心的连线取代原搜索方向。（2）若未取得更好效果，则将每个顶点向好点方向收缩1/3，构成新的组合形继续迭代。两个步骤可交替进行。()I xs2

17、1n9.3.4 9.3.4 辅助功能和终止准则（续）辅助功能和终止准则（续）终止准则：回顾，连续变量复合形法，各顶点目标函数值与几何中心点的目标函数值得均方根差小于某个很小的正数，或者当复合形的“边长”很小时而定。组合形在每个坐标上的当前点的检验长度：第 个坐标方向上的“长度”为将 值与相应的离散坐标的离散增量值（连续变量拟增量为 ）进行比较，若小于离散增量值得分量总数小于预先给定的个数（），则认为收敛。(j)(j)max1,2,21min1,2,21iiiiaxjnbxjn，i1,2,iiidabinidi1n9.3.5 9.3.5 离散变量组合形算法基本步骤离散变量组合形算法基本步骤1）选

18、取符合变量边界条件的初始顶点 ；确定各设计变量上下界值 和 ，连续变量拟离散增量（）；收敛准则分量数 。2）产生 个离散变量组合形的顶点；计算各顶点目标函数值并排序。3）计算除最坏点 外其余各顶点的几何中心点 及其目标函数值 。4）确定离散搜索方向 ，进行一维离散搜索，找到较好的离散点，则进行第五步；否则转向第六步。5）计算各坐标上的检验“长度”；若满足收敛条件，则转向第七步；否则，新点代替最坏点，构成新的组合形，完成一次迭代，转向第三步。6）调用离散变量组合形的辅助功能，转向第三步。7）计算结束，输出最优点 ，及目标函数值 。(0)xLixUixi1,2,ippn(1Nn)N2+1nbx（）cx（）()f x（c）s*x*()f x