离散变量优化问题

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

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

3、thm）,松弛问题：,以整型优化问题为例：,引入概念：松弛问题。,分枝定界法基本思想： 设有最大化的整型优化问题A，相应有松弛问题B，从解松弛问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数 的上界，记作 ；而A的任意可行解的目标函数值将是 的一个下界，记作 。 分枝定界法就是将B的可行域分成子区域(称为分枝)的方法，逐步减小 ，增大 ，最终求到 。,（1）分枝 在松弛问题B的最优解中任选一个不符合整数条件的变量 ,其值为 ,以 表示小于 的最大整数。构造两个约束条件,将这两个约束条件,分别加入问题B,求两个后继规划问题B1和B2,不考虑整数条件求解这两个后继

4、问题.,三个基本操作：,（2）定界 以每个后继问题为一分枝标明求解结果,在解的结果中,找出最优目标函数值最大者作为新的上界.从已符合整数条件的各分支中,找出目标函数值为最大者作为新的下界,若无,则下界为0. （3）比较与剪枝 各分支的最优目标函数中若有小于 ，则剪掉这枝；若大于 且不符合整数条件，则重复前两步，直到找到最优解。,分枝定界法计算过程：,上界,x1x*01,x1x*01+1,当所有的子问题均被关闭或剪枝后,目标函数值最大的整数解既为所求的最优解,若 的最优值 ，剪枝,若 的最优值 ；,将下界改为,例：用分枝定界法求解整型优化问题（用图解法计算）：,首先去掉整数约束，变为一般线性优化

5、问题（松弛问题），记为LP：,求出松弛问题最优解：,即 也是离散问题目标函数的上限。,先将（LP）划分为（LP1）和（LP2）,取 。,松弛问题最优解：,现在只要求出（LP1）和（LP2）的最优解即可。,将（LP）划分为（LP1）和（LP2）,取 。,先求（LP1）,如图所示。,先求（LP1）,如图所示。,此时B在点取得最优解。,求（LP2）,如图所示。,在C 点取得最优解。,Z (2)Z(1) =16 ， 原问题可能有比（16）更大的最优解； 但 x2 不是整数，故利用 x2 3 ， x2 4 加入条件。,现在只要求出（LP21）和（LP22）的最优解即可。,将（LP2）划分为（LP21）和

6、（LP22）,取 。,先求（LP21）,如图所示。,在D 点取得最优解。,求（LP22），如图所示。 无可行解，不再分枝。,LP21取得最优解： 且有 x12.4不是整数，可继续分枝，令 x12， x1 3。,剪枝,现在只要求出（LP211）和（LP222）的最优解即可。,将（LP21）划分为（LP211）和（LP222）,取 。,先求（LP211）,先求（LP211）,如图所示，此时E 在点取得最优解：,求（LP212）,如图所示，此时F 在点取得最优解：,找到最优解,（1） 若分枝后得到整数解，则这枝不必再分枝； （2） 若分枝后得到非整数解, 如果比整数解更好，则这枝继续分枝； （3）

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

8、3.1 初始离散组合形的产生,顶点数： 初始离散点记为 ，不必满足约束条件，但各分量必须满足变量值边界条件，即 式中， 第 个变量的下界值； 第 个变量的上界值。 组合形 个顶点： 第一个顶点： 第2个至 个顶点： 二维离散组合形的初始顶点 第 至 个顶点：,9.3.2 离散一维搜索,对初始组合形各顶点目标函数值排序，最大值处为最坏顶点，最小值处为最好顶点。 离散一维搜索以最坏点为基点，设标号为 ，以最坏顶点至其余各顶点的几何中心点的方向向量为搜索方向 ，其各分量为： 式中， 除最坏顶点 后其他顶点的几何中心。 新点各分量值为： 式中， 离散一维搜索步长因子； 对离散变量取最靠近的离散值 。,

9、9.3.2 离散一维搜索（续）,离散一维搜索采用进退对分法。 1）令 ； 2）求新点 ； 3）若 点较 点好，则 ，否则 ； 4）若 ，则 ，返回步骤2）；否则 ， 返回步骤2）； 5）终止准则，当 时，离散一维搜索终止。 为最小有用步长因子。,离散变量增量,连续变量拟增量或精度值,9.3.3 约束条件的处理,初始组合形顶点的产生及一维离散搜索未考虑约束条件，为使组合形调优迭代在可行域内进行，定义一个有效目标函数： 式中， 比 值的数量级大得多的常数； 与所有违反约束量的总和成正比的量。 式中， 常数； 违反约束的集合。 如右图所示，有效目标函数 的几何图形，像一个向可行域倾斜的“漏斗”。 程

10、序会自动先从不可行点寻找可行点，然后再从可行点寻找最优点。,9.3.4 辅助功能和终止准则,辅助功能：组合形调优方向 找不到新点，可用下面两种方法： （1）用次坏点（也可以取第2、3直至第 个顶点）与其余顶点几何中心的连线取代原搜索方向。 （2）若未取得更好效果，则将每个顶点向好点方向收缩1/3，构成新的组合形继续迭代。 两个步骤可交替进行。,9.3.4 辅助功能和终止准则（续）,终止准则： 回顾，连续变量复合形法，各顶点目标函数值与几何中心点的目标函数值得均方根差小于某个很小的正数，或者当复合形的“边长”很小时而定。 组合形在每个坐标上的当前点的检验长度： 第 个坐标方向上的“长度”为 将 值与相应的离散坐标的离散增量值（连续变量拟增量为 ）进行比较，若小于离散增量值得分量总数小于预先给定的个数（ ），则认为收敛。,9.3.5 离散变量组合形算法基本步骤,1）选取符合变量边界条件的初始顶点 ；确定各设计变量上下界值 和 ，连续变量拟离散增量 （ ）；收敛准则分量数 。 2）产生 个离散变量组合形的顶点；计算各顶点目标函数值并排序。 3）计算除最坏点 外其余各顶点的几何中心点 及其目标函数值 。 4）确定离散搜