离散变量优化问题ppt课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散变量问题优化算法,（,Algorithms for Discrete Variable Problem,）,离散变量问题优化算法 （Algor,一般的优化方法只能求得,连续变量,的最优解。,工程实际中存在大量,混合设计变量,问题。,混合设计变量包含：,连续设计变量,、,整型设计变量,和,离散设计变量,。,9.1,引言,例如,：齿轮传动装置的优化设计，,齿数,是一个,整型量,，,模数,是一系列,离散量,，,变位系数,可以看做,连续量,，,齿宽,若按长度,1mm,单位计算，则也可以看做,整型量,。,一般的优化方法只能求得连续变量的最优解。9.1 引言例如：,求离散问题的最优解，传统的方法是先用,连续变量,优化设计方法求,连续变量的最优解,，然后,圆整,到,离散值,上。,弊病,：可能得不到可行最优解，或所得的解不是离散最优解。,x,*,为连续变量最优解；,x,(1),是圆整后最近的离散点，但不可行；,x,(2),是最近的可行离散点，但不是离散最优点；,x,(3),是离散最优点。,传统方法的局限性,求离散问题的最优解，传统的方法是先用连续变量优化设计,离散变量优化,难点,：,不存在,指导搜索过程的,最优性条件,。,直接方法,：,枚举法（,enumeration,）,。可行点过多时，计算量大。,减少计算量,：,随机思想（,stochastic ideas,）、启发式原则（,heuristic rules,）,。,两种基本方法,：,（隐式）枚举法：如，,分枝定界法（,the branch and bound algorithm,）,；,随机或进化方法：如，模拟退火算法、遗传算法等。,离散变量优化方法,离散变量优化难点：不存在指导搜索过程的最优性条件。离,9.3,分枝定界法（,the branch and bound algorithm,）,松弛问题,：,以整型优化问题为例：,引入概念：,松弛问题,。,9.3 分枝定界法（the branch and boun,分枝定界法,基本思想,：,设有最大化的整型优化,问题,A,，相应有,松弛问题,B,，从解松弛问题,B,开始，若其最优解,不符合,A,的整数条件,，那么,B,的最优目标函数必是,A,的最优目标函数,的上界,，记作 ；而,A,的任意可行解的目标函数值将是,的一个下界,，记作 。,分枝定界法就是将,B,的可行域分成子区域,(,称为分枝,),的方法，逐步减小 ，增大 ，最终求到,。,分枝定界法基本思想：,（,1,）分枝,在松弛问题,B,的最优解中任选一个不符合整数条件的变量,其值为,以,表示小于,的最大整数。构造两个约束条件,将这两个约束条件,分别加入问题,B,求两个后继规划问题,B1,和,B2,不考虑整数条件求解这两个后继问题,.,三个基本操作,：,（1）分枝将这两个约束条件,分别加入问题B,求两个后继规划问,（,2,）定界,以每个后继问题为一分枝标明求解结果,在解的结果中,找出最优目标函数值最大者作为新的上界,.,从已符合整数条件的各分支中,找出目标函数值为最大者作为新的下界,若无,则下界为,0.,（,3,）比较与剪枝,各分支的最优目标函数中若有小于 ，则剪掉这枝；若大于 且不符合整数条件，则重复前两步，直到找到最优解。,（2）定界,分枝定界法计算过程：,上界,x,1,x*,01,x,1,x*,01,+1,分枝定界法计算过程：上界x1x*01x1x*01,当所有的子问题均被关闭或剪枝后,目标函数值最大的整数解既为所求的最优解,若 的最优值 ，剪枝,若 的最优值 ；,将下界改为,当所有的子问题均被关闭或剪枝后目标函数值最大的整数解既为所求,例：用分枝定界法求解整型优化问题（用图解法计算）：,首先去掉整数约束，变为一般线性优化问题（,松弛问题,），记为,LP,：,例：用分枝定界法求解整型优化问题（用图解法计算）：首,求出松弛问题最优解：,即,也是离散问题目标函数的,上限,。,求出松弛问题最优解：即 也是离散问题目标函数的上限。,离散变量优化问题ppt课件,先将,（,LP,）,划分为,（,LP1,）,和,（,LP2,）,取 。,松弛问题最优解：,先将（LP）划分为（LP1）和（LP2）,取,现在只要求出（,LP1,）和（,LP2,）的最优解即可。,将,（,LP,）,划分为,（,LP1,）,和,（,LP2,）,取 。,现在只要求出（LP1）和（LP2）的最优解即可。将（LP）,离散变量优化问题ppt课件,先求（,LP1,）,如图所示。,先求（LP1）,如图所示。,先求（,LP1,）,如图所示。,此时,B,在点取得最优解。,先求（LP1）,如图所示。此时B在点取得最优解。,离散变量优化问题ppt课件,求（,LP2,）,如图所示。,在,C,点取得最优解。,求（LP2）,如图所示。在C 点取得最优解。,Z,(2),Z,(1),=16,，,原问题可能有比（,16,）更大的最优解；,但,x,2,不是整数，故利用,x,2,3,，,x,2,4,加入条件。,Z(2)Z(1)=16，,现在只要求出（,LP21,）和（,LP22,）的最优解即可。,将,（,LP2,）,划分为,（,LP21,）,和,（,LP22,）,取 。,现在只要求出（LP21）和（LP22）的最优解即可。将（L,离散变量优化问题ppt课件,先求（,LP21,）,如图所示。,在,D,点取得最优解。,先求（LP21）,如图所示。在D 点取得最优解。,求（,LP22,），如图所示。,无可行解，不再分枝。,求（LP22），如图所示。,LP21,取得最优解：,且有,x,1,2.4,不是整数，可继续分枝，令,x,1,2,，,x,1,3,。,剪枝,LP21取得最优解：剪枝,现在只要求出（,LP211,）和（,LP222,）的最优解即可。,将,（,LP21,）,划分为,（,LP211,）,和,（,LP222,）,取 。,现在只要求出（LP211）和（LP222）的最优解即可。将,先求（,LP211,）,先求（LP211）,先求（,LP211,）,如图所示，此时,E,在点取得最优解：,先求（LP211）如图所示，此时E 在点取得最优解：,求（,LP212,）,如图所示，此时,F,在点取得最优解：,求（LP212）如图所示，此时F 在点取得最优解：,离散变量优化问题ppt课件,找到最优解,找到最优解,（,1,）,若分枝后得到整数解，则这枝不必再分枝；,（,2,）,若分枝后得到非整数解,如果比整数解更好，则这枝继续分枝；,（,3,）,若分枝后得到非整数解,如果比整数解更差，则这枝不必再分枝。,几点注意事项：,（1）若分枝后得到整数解，则这枝不必再分枝；几点注意事项：,9.3,离散变量优化,组合形法,（,P,维,),离散变量向量；,（,n-P,维,),连续变量向量；,离散设计空间,；,连续设计空间；,分别表示离散子空间和连续子空间。,离散变量数学模型的一般形式：,9.3 离散变量优化组合形法 （P维)离散,以,复合形法,为基础发展而来，使之能在离散空间中直接搜索,离散点,，从而满足求解离散变量优化问题的需要。,基本思想,：通过对初始复合形调优迭代使新的组合形不断向最优点移动和收缩，直至满足一定的终止条件为止。,下面分,五个部分介绍,离散变量组合形法：,（,1,）初始离散组合形的产生,（,2,）离散一维搜索,（,3,）约束条件处理,（,4,）组合形的调整,（,5,）收敛准则,以复合形法为基础发展而来，使之能在离散空间中直接搜索,9.3.1,初始离散组合形的产生,顶点数：,初始离散点记为 ，不必满足约束条件，但各分量必须满足变量值边界条件，即,式中，,第 个变量的下界值；,第 个变量的上界值。,组合形 个顶点：,第一个顶点：,第,2,个至 个顶点：,二维离散组合形的初始顶点,第 至 个顶点：,9.3.1 初始离散组合形的产生 顶点数：,9.3.2,离散一维搜索,对初始组合形各顶点目标函数值排序，,最大值处,为,最坏顶点,，,最小值处,为,最好顶点,。,离散一维搜索以,最坏点为基点,，设标号为 ，以最坏顶点至其余各顶点的几何中心点的方向向量为,搜索方向,，其各分量为：,式中，,除最坏顶点 后其他顶点的几何中心。,新点各分量值,为：,式中，,离散一维搜索步长因子；,对离散变量取最靠近的离散值 。,9.3.2 离散一维搜索 对初始组合形各顶点目标函数,9.3.2,离散一维搜索（续）,离散一维搜索采用,进退对分法,。,1,）令 ；,2,）求新点 ；,3,）若 点较 点好，则 ，否则 ；,4,）若 ，则 ，返回,步骤,2,）,；否则 ，返回,步骤,2,）,；,5,）终止准则，当 时，离散一维搜索终止。为最小有用步长因子。,离散变量增量,连续变量拟增量或精度值,9.3.2 离散一维搜索（续）离散一维搜索采用进退,9.3.3,约束条件的处理,初始组合形顶点的产生及一维离散搜索未考虑,约束条件,，为使组合形调优迭代在可行域内进行，定义一个有效目标函数：,式中，,比 值的数量级大得多的常数；,与所有违反约束量的总和成正比的量。,式中，,常数；,违反约束的集合。,如右图所示，,有效目标函数,的几何图形，像一个向可行域倾斜的,“漏斗”,。,程序会自动先从不可行点寻找可行点，然后再从可行点寻找最优点。,9.3.3 约束条件的处理 初始组合形顶点的产生及一,9.3.4,辅助功能和终止准则,辅助功能,：组合形调优方向 找不到新点，可用下面两种方法：,（,1,）用次坏点（也可以取第,2,、,3,直至第 个顶点）与其余顶点几何中心的连线取代原搜索方向。,（,2,）若未取得更好效果，则将每个顶点向好点方向收缩,1/3,，构成新的组合形继续迭代。,两个步骤可交替进行,。,9.3.4 辅助功能和终止准则 辅助功能：组合形调优,9.3.4,辅助功能和终止准则（续）,终止准则：,回顾,，连续变量复合形法，各顶点目标函数值与几何中心点的目标函数值得均方根差小于某个很小的正数，或者当复合形的“边长”很小时而定。,组合形在每个坐标上的当前点的检验长度：,第 个坐标方向上的“长度”为,将 值与相应的离散坐标的离散增量值（连续变量拟增量为 ）进行比较，若小于离散增量值得分量总数小于预先给定的个数（），则认为收敛。,9.3.4 辅助功能和终止准则（续）终止准则：,9.3.5,离散变量组合形算法基本步骤,1,）选取符合变量边界条件的,初始顶点,；确定各设计变量上下界值 和 ，连续变量,拟离散增量,（）；,收敛准则分量数,。,2,）产生 个离散变量组合形的顶点；计算各顶点目标函数值并排序。,3,）计算,除最坏点,外其余各顶点的,几何中心点,及其目标函数值 。,4,）确定离散搜索方向 ，进行,一维离散搜索,，找到较好的离散点，则进行,第五步,；否则转向,第六步,。,5,）计算各坐标上的,检验“长度”,；若,满足收敛条件,，则转向,第七步,；否则，,新点代替最坏点,，构成新的组合形，完成一次迭代，转向,第三步,。,6,）调用离散变量组合形的,辅助功能,，转向,第三步,。,7,）计算结束，输出最优点 ，及目标函数值 。,9.3.5 离散变量组合形算法基本步骤1）选取符合变量边界,离散变量优化问题ppt课件,离散变量优化问题ppt课件,离散变量优化问题ppt课件,THE END,Thank you,！,THE ENDThank you！,