离散变量最优化方法

1、关于离散变量的最优化方法第一张，PPT共四十三页，创作于2022年6月 钢丝直径、钢板厚度、型钢的型号也都应符合金属材料的供应规范等等 在许多工程问题中，设计变量实际上不是连续变化的。 8.1 引 言齿轮的齿数只能是正整数是整型变量；齿轮的模数应按标准系列取用； 属于这样的一些必须取离散数值的设计变量均称为离散变量。 第二张，PPT共四十三页，创作于2022年6月一、 变量类型 工程实际问题中不是单一的连续变量，经常是各种类型变量的混合。有： 连续变量 确定型 整型变量 离散变量 随机变量 不确定型 混合变量 所以需要相应的优化方法。 8.1 引 言（续）第三张，PPT共四十三页，创作于202

2、2年6月二、工程实际设计的需要例：决定修建一条防洪堤坝。根据历年的水文资料，台风的年最大风速：8.1 引 言（续）服从正态分布第四张，PPT共四十三页，创作于2022年6月 现在需要设计堤坝的截面尺寸 b 和 h，在保证不受灾害的概率不低于99.9%，堤坝不受冲压损坏的概率不低于 99.0% 的要求下，使投资最小。8.1 引 言（续）第五张，PPT共四十三页，创作于2022年6月三、传统方法的局限性 求离散问题的最优解，传统的方法是先用连续变量优化设计方法求连续变量的最优解，然后圆整到离散值上。 弊病：可能得不到可行最优解，或所得的解不是离散最优解。8.1 引 言（续）第六张，PPT共四十三页

3、，创作于2022年6月 x* X(1) X(2) X(3)x(3)是离散最优点。x10 x28.1 引 言（续） x*是连续变量的最优点；x(1)是圆整后最近的离散点，但不可行； x(2)是最近的可行离散点，但不是离散最优点；第七张，PPT共四十三页，创作于2022年6月一、离散设计空间1、一维离散设计空间qij-1 qij qij+1 Xi7.2 离散变量优化设计的基本概念 在一条表示变量的坐标轴上的一些间隔点的集合，这些点的集合称为离散设计空间； 这些点的坐标值是该变量可取的离散值，这些点称为一维离散设计空间的离散点。 第八张，PPT共四十三页，创作于2022年6月 二维连续设计变量的设计

4、空间是代表该两个变量的两条坐标轴形成的平面； 这些点的坐标值分别离散变量可取的离散值称为二维离散设计空间的离散点，二维离散设计空间则是上述平面上的某些点的集合；7.2 离散变量优化设计的基本概念（续）2、二维离散设计空间第九张，PPT共四十三页，创作于2022年6月7.2 离散变量优化设计的基本概念（续） 这些交点就是三维离散设计空间中的离散点。 对于三维离散变量，过每个变量离散值作该变量坐标轴的垂直面这些平面的交点的集合就是三维离散设计空间。3、三维离散设计空间第十张，PPT共四十三页，创作于2022年6月P 个离散设计变量组成P维离散设计空间。7.2 离散变量优化设计的基本概念（续）4、P

5、维离散设计空间 对于p维离散变量，过每个变量离散值作该变量坐标轴的垂直面，这些超平面的交点的集合就是p维离散设计空间，用 表示。 而这些交点就是p维离散设计空间中的离散点，用表示。 第十一张，PPT共四十三页，创作于2022年6月注：因为离散变量是有限个,所以离散空间是有界的。某个离散变量的取值不足l个，其余值可用预先 规定的自然数补齐。7.2 离散变量优化设计的基本概念（续） p个离散变量全部可取的离散值的集合称为p维离散变量的值域，可用一个p*l阶的矩阵Q来表示l为各离散设计变量可取离散值个数中的最大值第十二张，PPT共四十三页，创作于2022年6月7.2 离散变量优化设计的基本概念(续）

6、4、N-P维连续设计空间 N个设计变量中有P个离散变量，此外有N-P个连续变量。N-P维连续设计空间第十三张，PPT共四十三页，创作于2022年6月7.2 离散变量优化设计的基本概念(续）4、N维设计空间若Rp为空集时，Rn为全连续变量设计问题；若Rn-p为空集时，Rn 为全离散变量设计问题。 其中：离散设计空间为 连续设计空间为第十四张，PPT共四十三页，创作于2022年6月 在机械优化设计中常见的约束非线性离散变量最优化问题的数学模型为：7.2 离散变量优化设计的基本概念(续）N设计变量维数；m不等式约束条件个数P离散变量的个数；XD离散子空间；RD离散变量子集；XC连续子空间；RC连续变

7、量子集；第十五张，PPT共四十三页，创作于2022年6月7.2 离散变量优化设计的基本概念(续）1、整型变量的离散 整型变量可看作为是离散间隔恒定为1的离散变量。是离散变量的特例。2、连续变量的离散化 有时为了提高优化设计计算效率，将连续变量转化为拟离散变量。二、非均匀离散变量和连续变量的均匀离散化处理第十六张，PPT共四十三页，创作于2022年6月7.2 离散变量优化设计的基本概念（续）3、连续变量离散化的方法第十七张，PPT共四十三页，创作于2022年6月 由于离散设计空间的不连续性，离散变量最优点与连续变量最优点不是同一概念，必须重新定义。 1离散单位邻域（UN(X)7.3 离散最优解

8、在设计空间中，离散点X的单位邻域UN(X)是指如下定义的集合。第十八张，PPT共四十三页，创作于2022年6月图示为二维设计空间中离散点X的离散单位邻域7.3 离散最优解（续） 一般情况下，设离散变量的维数为p，则UN(X)内的离散点总数为N=3p(p次方） x B GD EA F C Hii0 x2第十九张，PPT共四十三页，创作于2022年6月7.3 离散最优解（续） 2、离散坐标邻域（UC(X) 在设计空间中离散点X的离散坐标邻域UC(X)是指以X点为原点的坐标轴线和离散单位邻域UN（X）的交点的集合。图示离散坐标邻域为： 一般在p维离散变量情况下离散坐标邻域的离散点总数为N=2p+1。

9、第二十张，PPT共四十三页，创作于2022年6月3离散局部最优解7.3 离散最优解（续）若，对所有恒有则称X*是离散局部最优点4、拟离散局部最优解若，对所有恒有则称X*是拟离散局部最优点5、离散全域最优解若，对所有恒有则称X*是离散全域最优点第二十一张，PPT共四十三页，创作于2022年6月 严格说来，离散优化问题的最优解应是指离散全域最优点而言，但它与一般的非线性优化问题一样，离散优化方法所求得的最优点一般是局部最优点，这样通常所说的最优解均指局部最优解。7.3 离散最优解（续）第二十二张，PPT共四十三页，创作于2022年6月三、收敛准则 设当前搜索到的最好点为x(k)，需要判断其是否收敛

10、。在x(k)的单位邻域中查3n 1个点，若未查到比x(k) 的目标函数值更小的点，则收敛，x*=x(k) 。7.3 离散最优解（续）第二十三张，PPT共四十三页，创作于2022年6月7.4 凑整解法与网格法一、凑整解法 解决离散变量的优化问题很容易考虑为；将离散变量全都权宜地视为连续变量，用一般连续变量最优化方法求得最优点（称为连续最优点），然后再把该点的坐标按相应的设计规范和标准调整为与其最接近的整数值或离散值，作为离散变量优化问题的最优（称为离散最优点）的坐标这便构成离散变量最优化问题的凑整解法。第二十四张，PPT共四十三页，创作于2022年6月 图中A、B两点分别表示二维离散变量优化问题

11、凑整法中的连续最优点与离散最优点。7.4 凑整解法与网格法（续）第二十五张，PPT共四十三页，创作于2022年6月7.4 凑整解法与网格法（续） 1、与连续最优点A最接近的离散点B落在可行域外，不可以接受；凑整法可能出现的两个问题： 2、与连续最优点A最接近的离散点B并非离散最优点C，点B仅是一个工程实际可能接受的较好的设计方案。第二十六张，PPT共四十三页，创作于2022年6月改进：即在求得连续最优点A并调整到最接近的离散点B以后，在B的离散单位邻域UN（X）或离散坐标邻域UC（X)内找出所有的离散点，逐个判断其可行性并比较其函数值的大小从中找到离散局部最优点或拟离散局部最优点。凑整解或改进

12、的凑整法都是基于离散最优点就在连续最优点的附近。但实际问题有时并非如此，如图，真正的离散最优点C离连续最优点A很远。第二十七张，PPT共四十三页，创作于2022年6月二、网格法网格法是解离散变量优化问题的一种最原始的遍数法。7.4 凑整解法与网格法（续） 在离散变量的值域内，先按各变量的可取离散值在设计空间内构成全部离散网格点，全域最优点X”应是可行域中诸网格点目标函数值最小者这就需要逐个检查网格点是否可行和择其最优。第二十八张，PPT共四十三页，创作于2022年6月7.4 凑整解法与网格法（续）点若不可行，则去掉；若可行，则计算目标函数值f(X(k)，并与以前计算取得的可行最好点x(l)比较

13、,若f(X(k)f(X(l),则将X(k)作为新的最好点 继续检查所有的全部离散点后，其最好点就是该优化问题的最优解X*。优点：原理简单缺点：设计变量维数n以及每个变量离散值数目很 多时，计算量大。X(k)点第二十九张，PPT共四十三页，创作于2022年6月7.5 离散复合形法 离散复合形法是在求解连续变量复合形法的基础上进行改造，使之能在离散空间中直接搜索离散点，从而满足求解离散变量优化问题的需要。通过对初始复合形调优迭代使新的复合形不断向基本思想：最优点移动和收缩，直至满足一定的终止条件为止。特点：复合形顶点必须是可行的离散点。第三十张，PPT共四十三页，创作于2022年6月 将第q+1点

14、朝着点X (s)的方向移动，新点X (q+1)为： X(q+1)= X(s)+0.5 (X(q+1)X(s)连续变量的复合形法第三十一张，PPT共四十三页，创作于2022年6月第三十二张，PPT共四十三页，创作于2022年6月反射系数的初值一般取 第三十三张，PPT共四十三页，创作于2022年6月一、初始离散复合形的产生7.5 离散复合形法（续） 用复合形法在n维离散设计空间搜索时，通常取初始离散复合形的顶点数为k=2n+1个。先给定一个初始离散点X(0)，X(0)必须满足各离散变量值的边界条件，即：、分别是第i个变量的下限值和上限值。1、初始离散点的确定第三十四张，PPT共四十三页，创作于2

15、022年6月7.5 离散复合形法（续）2、初始复合形各顶点的产生这样有2n个顶点分别分布于n个设计变量的上下限约束边界上。 二维问题产生的离散复合形的5个顶点第三十五张，PPT共四十三页，创作于2022年6月7.5 离散复合形法（续）二、约束条件的处理 由于初始复合形顶点的产生未考虑约束条件，此时产生的初始复合形顶点可能会有部分甚至全部落在可行域 的外面。 在调优迭代运算中必须保持复合形各顶点的可行性，故如果有部分顶点落在可行域外面，则需将其移入可行域之内。定义离散复合形的有效目标函数 为：第三十六张，PPT共四十三页，创作于2022年6月7.5 离散复合形法（续）f(X)为原目标函数；M为一

16、个比f(X)值数量级大得多的常数；离散复合形的有效目标函数 为：第三十七张，PPT共四十三页，创作于2022年6月7.5 离散复合形法（续）一维变量时的有效目标函数1、在可行域以外，有效目标函数 的曲线象一个向可行域倾斜的漏斗;2、当部分复合形顶点在可行域之外时，最坏的顶点X(H)一定位于可行域之外的一个离散点上；D第三十八张，PPT共四十三页，创作于2022年6月7.5 离散复合形法（续）3、以最坏点X(H)为基点进行一维离散搜索，M在有效目标函数 中保持不变；4、 随搜索点离约束面的位置而变化离约束面越近，其值越小；反之，其值则越大求的极小值，当其等于零时，即进入可行域D第三十九张，PPT共四十三页，创作于2022年6月7.5 离散复合形法（续）5、进入可行域后，由于可行域的边界好像由M筑起的一道“高墙”，从而保证始终在可行域内继续搜索f(X)的极小值。三、离散一维搜索离散复合形的迭代、调优过程： 以复合形顶点中的最坏点X(H)为基点，把X(H)和其余各顶点的几何中心点X(C)的连线方向作为搜索方向S，采用映射、延伸或收缩的方法进行一维搜索，找到好点X(R)，则以该点代替最坏点组成新的复合形，重复以上步骤迭代调优。第四十张，PPT共四十三页，创作于2022年6月7.5 离散复合形法（续） 设n为维数，p为离散变量的个数，