离散变量的最优化方法讲稿.ppt

关于离散变量的最优化方法第一页，讲稿共四十三页哦 钢丝直径、钢板厚度、型钢的型号也都应符合钢丝直径、钢板厚度、型钢的型号也都应符合金属材料的供应规范等等金属材料的供应规范等等 在许多工程问题中，设计变量实际上不是连续在许多工程问题中，设计变量实际上不是连续变化的。变化的。8.1 引引 言言齿轮的齿数只能是正整数是整型变量；齿轮的齿数只能是正整数是整型变量；齿轮的模数应按标准系列取用；齿轮的模数应按标准系列取用；属于这样的一些必须取离散数值的设计变量属于这样的一些必须取离散数值的设计变量均称为离散变量。均称为离散变量。第二页，讲稿共四十三页哦一、一、变量类型变量类型 工程实际问题中不是单一的连续变量，经常是各种工程实际问题中不是单一的连续变量，经常是各种类型变量的混合。有：类型变量的混合。有：连续变量连续变量 确定型确定型 整型变量整型变量 离散变量离散变量 随机变量随机变量 不确定型不确定型 混合变量混合变量 所以需要相应的优化方法。所以需要相应的优化方法。8.1 引引 言（续）言（续）第三页，讲稿共四十三页哦二、工程实际设计的需要二、工程实际设计的需要例：决定修建一条防洪堤坝。根例：决定修建一条防洪堤坝。根据历年的水文资料，台风的年最据历年的水文资料，台风的年最大风速：大风速：8.1 引引 言（续）言（续）服从正态分布服从正态分布第四页，讲稿共四十三页哦 现在需要设计堤坝的截现在需要设计堤坝的截面尺寸面尺寸 b 和和 h，在保证不，在保证不受灾害的概率不低于受灾害的概率不低于99.9%，堤坝不受冲压损，堤坝不受冲压损坏的概率不低于坏的概率不低于 99.0%的要求下，使投资最小的要求下，使投资最小。8.1 引引 言（续）言（续）第五页，讲稿共四十三页哦三、传统方法的局限性三、传统方法的局限性 求离散问题的最优解，传统的方法是先用连续变量优化求离散问题的最优解，传统的方法是先用连续变量优化设计方法求连续变量的最优解，然后圆整到离散值上。设计方法求连续变量的最优解，然后圆整到离散值上。弊病：可能得不到可行最优解，或所得的解不是离散弊病：可能得不到可行最优解，或所得的解不是离散最优解。最优解。8.1 引引 言（续）言（续）第六页，讲稿共四十三页哦 x*X(1)X(2)X(3)x(3)是离散最优点。是离散最优点。x10 x28.1 引引 言（续）言（续）x*是连续变量的最优点；是连续变量的最优点；x(1)是圆整后最近的离散点，但不可行；是圆整后最近的离散点，但不可行；x(2)是最近的可行离散是最近的可行离散点，但不是离散最优点；点，但不是离散最优点；第七页，讲稿共四十三页哦一、离散设计空间一、离散设计空间1 1、一维离散设计空间、一维离散设计空间qij-1 qij qij+1 Xi7.2 离散变量优化设计的基本概念离散变量优化设计的基本概念 在一条表示变量的坐标轴上的一些间隔点的集在一条表示变量的坐标轴上的一些间隔点的集合，这些点的集合称为离散设计空间；合，这些点的集合称为离散设计空间；这些点的坐标值是该变量可取的离散值，这些点这些点的坐标值是该变量可取的离散值，这些点称为一维离散设计空间的离散点。称为一维离散设计空间的离散点。第八页，讲稿共四十三页哦 二维连续设计变量的设计空间是代表该两个二维连续设计变量的设计空间是代表该两个变量的两条坐标轴形成的平面；变量的两条坐标轴形成的平面；这些点的坐标值分别离散这些点的坐标值分别离散变量可取的离散值称变量可取的离散值称为二维离散设计空间的离为二维离散设计空间的离散点，散点，二维离散设计空间则二维离散设计空间则是上述平面上的某些是上述平面上的某些点的集合；点的集合；7.2 7.2 离散变量优化设计的基本概念（续）离散变量优化设计的基本概念（续）2 2、二维离散设计空间、二维离散设计空间第九页，讲稿共四十三页哦7.2 7.2 离散变量优化设计的基本概念（续）离散变量优化设计的基本概念（续）这些交点就是三维离这些交点就是三维离散设计空间中的离散点。散设计空间中的离散点。对于三维离散变量，过每个变量离散值作该变量坐对于三维离散变量，过每个变量离散值作该变量坐标轴的垂直面这些平面的交点的集合就是三维离散设标轴的垂直面这些平面的交点的集合就是三维离散设计空间计空间。3 3、三维离散设计空间、三维离散设计空间第十页，讲稿共四十三页哦P 个离散设计变量组成个离散设计变量组成P P维离散设计空间。维离散设计空间。7.2 离散变量优化设计的基本概念（续）离散变量优化设计的基本概念（续）4、P维离散设计空间维离散设计空间 对于对于p维离散变量，过每个变量离散值作该变量维离散变量，过每个变量离散值作该变量坐标轴的垂直面，这些超平面的交点的集合就是坐标轴的垂直面，这些超平面的交点的集合就是p维维离散设计空间，用离散设计空间，用 表示。表示。而这些交点就是而这些交点就是p维离散设计空间中的离散点，用维离散设计空间中的离散点，用表示。表示。第十一页，讲稿共四十三页哦注：注：因为离散变量是有限个因为离散变量是有限个,所以离散空间是有界的。所以离散空间是有界的。某个离散变量的取值不足某个离散变量的取值不足l个，其余值可用预先个，其余值可用预先 规定的自然数补齐。规定的自然数补齐。7.2 离散变量优化设计的基本概念（续）离散变量优化设计的基本概念（续）p个离散变量全部可取的离散值的集合称为个离散变量全部可取的离散值的集合称为p p维维离散变量的值域，可用一个离散变量的值域，可用一个p*l阶的矩阵阶的矩阵Q来表示来表示l为各离散设计变量可取离散值个数中的最大值为各离散设计变量可取离散值个数中的最大值第十二页，讲稿共四十三页哦7.2 离散变量优化设计的基本概念离散变量优化设计的基本概念(续）续）4、N-P维连续设计空间维连续设计空间 N个设计变量中有个设计变量中有P个离散变量，此外有个离散变量，此外有N-P个连个连续变量。续变量。N-P维连续设计空间维连续设计空间第十三页，讲稿共四十三页哦7.2 离散变量优化设计的基本概念离散变量优化设计的基本概念(续）续）4、N维设计空间维设计空间若若Rp为空集时，为空集时，Rn为全连续变量设计问题；为全连续变量设计问题；若若Rn-p为空集时，为空集时，Rn 为全离散变量设计问题。为全离散变量设计问题。其中：离散设计空间为其中：离散设计空间为 连续设计空间为连续设计空间为第十四页，讲稿共四十三页哦 在机械优化设计中常见的约束非线性离散变量在机械优化设计中常见的约束非线性离散变量最优化问题的数学模型为：最优化问题的数学模型为：7.2 离散变量优化设计的基本概念离散变量优化设计的基本概念(续）续）N设计变量维数；设计变量维数；m不等式约束条件个数不等式约束条件个数PP离散变量的个数；离散变量的个数；X XD D离散子空间；离散子空间；R RD D离散变量子集；离散变量子集；X XC C连续子空间；连续子空间；R RC C连续变量子集；连续变量子集；第十五页，讲稿共四十三页哦7.2 离散变量优化设计的基本概念离散变量优化设计的基本概念(续）续）1 1、整型变量的离散、整型变量的离散 整型变量可看作为是离散间隔恒定为整型变量可看作为是离散间隔恒定为1 1的离散变量。的离散变量。是离散变量的特例。是离散变量的特例。2 2、连续变量的离散化、连续变量的离散化 有时为了提高优化设计计算效率，将连续变量转化为拟有时为了提高优化设计计算效率，将连续变量转化为拟离散变量。离散变量。二、非均匀离散变量和连续变量的均匀离散化处理二、非均匀离散变量和连续变量的均匀离散化处理第十六页，讲稿共四十三页哦7.2 离散变量优化设计的基本概念（续）离散变量优化设计的基本概念（续）3、连续变量离散化的方法连续变量离散化的方法第十七页，讲稿共四十三页哦 由于离散设计空间的不连续性，离散变量最优点与由于离散设计空间的不连续性，离散变量最优点与连续变量最优点不是同一概念，必须重新定义。连续变量最优点不是同一概念，必须重新定义。1离散单位邻域离散单位邻域（UN(X)7.3 离散最优解离散最优解 在设计空间中，离散点在设计空间中，离散点X的单位邻域的单位邻域UN(X)是指如下是指如下定义的集合。定义的集合。第十八页，讲稿共四十三页哦图示为二维设计空间中离散点图示为二维设计空间中离散点X的离散单位邻域的离散单位邻域7.3 离散最优解（续）离散最优解（续）一般情况下，设离散变量一般情况下，设离散变量的维数为的维数为p p，则，则UN(X)内的离内的离散点总数为散点总数为N=3p(p次方）次方）x B GD EA F C Hii0 x2第十九页，讲稿共四十三页哦7.3 离散最优解（续）离散最优解（续）2、离散坐标邻域离散坐标邻域（UC(X)在设计空间中离散点在设计空间中离散点X的离散坐标邻域的离散坐标邻域UC(X)是指是指以以X点为原点的坐标轴线和离散单位邻域点为原点的坐标轴线和离散单位邻域UN（X）的的交点的集合。交点的集合。图示离散坐标邻域为：图示离散坐标邻域为：一般在一般在p维离散变量情况下离散维离散变量情况下离散坐标邻域的离散点总数为坐标邻域的离散点总数为N=2p+1。第二十页，讲稿共四十三页哦3离散局部最优解离散局部最优解7.3 离散最优解（续）离散最优解（续）若若，对所有，对所有恒有恒有则称则称X*是离散局部最优点是离散局部最优点4、拟离散局部最优解拟离散局部最优解若若，对所有，对所有恒有恒有则称则称X*是拟离散局部最优点是拟离散局部最优点5 5、离散全域最优解、离散全域最优解若若，对所有，对所有恒有恒有则称则称X*是离散全域最优点是离散全域最优点第二十一页，讲稿共四十三页哦 严格说来，离散优化问题的最优解应严格说来，离散优化问题的最优解应是指离散全域最优点而言，但它与一般的是指离散全域最优点而言，但它与一般的非线性优化问题一样，离散优化方法所求非线性优化问题一样，离散优化方法所求得的最优点一般是局部最优点，这样通常得的最优点一般是局部最优点，这样通常所说的最优解均指局部最优解。所说的最优解均指局部最优解。7.3 离散最优解（续）离散最优解（续）第二十二页，讲稿共四十三页哦三、收敛准则三、收敛准则 设当前搜索到的最好点为设当前搜索到的最好点为x(k)，需要判断其是否收，需要判断其是否收敛。敛。在在x x(k)(k)的单位邻域中查的单位邻域中查3 3n n 1 1个点，若未查到比个点，若未查到比x x(k)(k)的的目标函数值更小的点，则收敛，目标函数值更小的点，则收敛，x*=xx*=x(k)(k)。7.3 离散最优解（续）离散最优解（续）第二十三页，讲稿共四十三页哦7.4 凑整解法与网格法凑整解法与网格法一、凑整解法一、凑整解法 解决离散变量的优化问题很容易考虑为；将离解决离散变量的优化问题很容易考虑为；将离散变量全都权宜地视为连续变量，用一般连续变量散变量全都权宜地视为连续变量，用一般连续变量最优化方法求得最优点（称为连续最优点），然后最优化方法求得最优点（称为连续最优点），然后再把该点的坐标按相应的设计规范和标准调整为与再把该点的坐标按相应的设计规范和标准调整为与其最接近的整数值或离散值，作为离散变量优化问其最接近的整数值或离散值，作为离散变量优化问题的最优（称为离散最优点）的坐标这便构成离题的最优（称为离散最优点）的坐标这便构成离散变量最优化问题的凑整解法。散变量最优化问题的凑整解法。第二十四页，讲稿共四十三页哦 图中图中A、B两点分别表示二维离散变量优化问题凑两点分别表示二维离散变量优化问题凑整法中的连续最优点与离散最优点。整法中的连续最优点与离散最优点。7.4 凑整解法与网格法（续）凑整解法与网格法（续）第二十五页，讲稿共四十三页哦7.4 凑整解法与网格法（续）凑整解法与网格法（续）1 1、与连续最优点、与连续最优点A最接近的离散点最接近的离散点B落在可行域外，不可以接受；落在可行域外，不可以接受；凑整法可能出现的两个问题：凑整法可能出现的两个问题：2、与连续最优点与连续最优点A A最接近的离散点最接近的离散点B B并非离散最优点并非离散最优点C C，点，点B B仅是仅是一个工程实际可能接受的较好的设计方案。一个工程实际可能接受的较好的设计方案。第二十六页，讲稿共四十三页哦改进：改进：即在求得连续最优点即在求得连续最优点A A并调整到最接近的离散并调整到最接近的离散点点B B以后，在以后，在B B的离散单位邻域的离散单位邻域UN（X）或离散坐标邻或离散坐标邻域域UC（X)内找出所有的离散点，逐个判断其可行性内找出所有的离散点，逐个判断其可行性并比较其函数值的大小从中找到离散局部最优点并比较其函数值的大小从中找到离散局部最优点或拟离散局部最优点。或拟离散局部最优点。凑整解或改进的凑整法凑整解或改进的凑整法都是基于离散最优点就都是基于离散最优点就在连续最优点的附近。在连续最优点的附近。但实际问题有时并非如但实际问题有时并非如此，如图，真正的离散此，如图，真正的离散最优点最优点C C离连续最优点离连续最优点A A很远。很远。第二十七页，讲稿共四十三页哦二、网格法二、网格法网格法是解离散变量优化问题的一种最原始的遍数法网格法是解离散变量优化问题的一种最原始的遍数法。7.4 凑整解法与网格法（续）凑整解法与网格法（续）在离散变量的值域内，先按在离散变量的值域内，先按各变量的可取离散值在设计空间各变量的可取离散值在设计空间内构成全部离散网格点，全域最内构成全部离散网格点，全域最优点优点X”X”应是可行域中诸网格点目应是可行域中诸网格点目标函数值最小者这就需要逐个标函数值最小者这就需要逐个检查网格点是否可行和择其最优。检查网格点是否可行和择其最优。第二十八页，讲稿共四十三页哦7.4 凑整解法与网格法（续）凑整解法与网格法（续）点若不可行，则去掉；点若不可行，则去掉；若可行，则计算目标函数值若可行，则计算目标函数值f(X(k)，并与以前计算取，并与以前计算取得的可行最好点得的可行最好点x(l)比较比较,若若f(X(k)(k)f(X(l),则将则将X(k)作作为新的最好点为新的最好点 继续检查所有的全部离散点后，其最好点就是该优化继续检查所有的全部离散点后，其最好点就是该优化问题的最优解问题的最优解X*X*。优点：原理简单优点：原理简单缺点：设计变量维数缺点：设计变量维数n以及每个变量离散值数目很以及每个变量离散值数目很 多时，计算量大。多时，计算量大。X(k)点点第二十九页，讲稿共四十三页哦7.5 离散复合形法离散复合形法 离散复合形法是在求解连续变量复合形法的基础上进离散复合形法是在求解连续变量复合形法的基础上进行改造，使之能在离散空间中直接搜索离散点，从而满足行改造，使之能在离散空间中直接搜索离散点，从而满足求解离散变量优化问题的需要。求解离散变量优化问题的需要。通过对初始复合形调优迭代使新的复合形不断向通过对初始复合形调优迭代使新的复合形不断向基本思想：基本思想：最优点移动和收缩，直至满足一定的终止条件为止。最优点移动和收缩，直至满足一定的终止条件为止。特点：特点：复合形顶点必须是可行的离散点。复合形顶点必须是可行的离散点。第三十页，讲稿共四十三页哦 将第将第q+1点朝着点点朝着点X(s)的方向移动，新点的方向移动，新点X(q+1)为：为：X(q+1)=X(s)+0.5(X(q+1)X(s)连续变量的复合形法连续变量的复合形法第三十一页，讲稿共四十三页哦第三十二页，讲稿共四十三页哦反射系数的初值一般取反射系数的初值一般取 第三十三页，讲稿共四十三页哦一、初始离散复合形的产生一、初始离散复合形的产生7.5 离散复合形法（续）离散复合形法（续）用复合形法在用复合形法在n维离散设计空间搜索时，通常取初始离维离散设计空间搜索时，通常取初始离散复合形的顶点数为散复合形的顶点数为k=2n+1个。先给定一个初始离散点个。先给定一个初始离散点X X(0)(0)，X X(0)(0)必须满足各离散变量值的边界条件，即：必须满足各离散变量值的边界条件，即：、分别是第分别是第i个变量的下限值和上限值。个变量的下限值和上限值。1 1、初始离散点的确定、初始离散点的确定第三十四页，讲稿共四十三页哦7.5 离散复合形法（续）离散复合形法（续）2 2、初始复合形各顶点的产生、初始复合形各顶点的产生这样有这样有2n2n个顶点分别个顶点分别分布于分布于n n个设计变量的个设计变量的上下限约束边界上。上下限约束边界上。二维问题产生的离散复合形二维问题产生的离散复合形的的5 5个顶点个顶点第三十五页，讲稿共四十三页哦7.5 离散复合形法（续）离散复合形法（续）二、约束条件的处理二、约束条件的处理 由于初始复合形顶点的产生未考虑约束条件，此时产由于初始复合形顶点的产生未考虑约束条件，此时产生的初始复合形顶点可能会有部分甚至全部落在可行域生的初始复合形顶点可能会有部分甚至全部落在可行域 的外面。的外面。在调优迭代运算中必须保持复合形各顶点的可行性，在调优迭代运算中必须保持复合形各顶点的可行性，故如果有部分顶点落在可行域外面，则需将其移入可故如果有部分顶点落在可行域外面，则需将其移入可行域之内。行域之内。定义离散复合形的有效目标函数定义离散复合形的有效目标函数 为：为：第三十六页，讲稿共四十三页哦7.5 离散复合形法（续）离散复合形法（续）f(X)为原目标函数；为原目标函数；M为一个比为一个比f(X)值数量级大得多的常数；值数量级大得多的常数；离散复合形的有效目标函数离散复合形的有效目标函数 为：为：第三十七页，讲稿共四十三页哦7.5 离散复合形法（续）离散复合形法（续）一维变量时的有效目标函数一维变量时的有效目标函数1 1、在可行域以外，有效、在可行域以外，有效目标函数目标函数 的曲线象的曲线象一个向可行域倾斜的漏一个向可行域倾斜的漏斗斗;2 2、当部分复合形顶点在可、当部分复合形顶点在可行域之外时，最坏的顶点行域之外时，最坏的顶点X(H)一定位于可行域之外一定位于可行域之外的一个离散点上；的一个离散点上；D第三十八页，讲稿共四十三页哦7.5 离散复合形法（续）离散复合形法（续）3 3、以最坏点、以最坏点X(H)为基点为基点进行一维离散搜索，进行一维离散搜索，M在有效目标函数在有效目标函数 中保持不变；中保持不变；4 4、随搜索点离约随搜索点离约束面的位置而变化束面的位置而变化离约束面越近，其值越小；反之，其值则越大离约束面越近，其值越小；反之，其值则越大求求的极小值，当其等于零时，即进入可行域的极小值，当其等于零时，即进入可行域D第三十九页，讲稿共四十三页哦7.5 离散复合形法（续）离散复合形法（续）5 5、进入可行域后，、进入可行域后，由于可行域的边界好像由于可行域的边界好像由由M筑起的一道筑起的一道“高墙高墙”，从而保证始终在可行域内继续搜索，从而保证始终在可行域内继续搜索f(X)的极小值。的极小值。三、离散一维搜索三、离散一维搜索离散复合形的迭代、调优过程：离散复合形的迭代、调优过程：以复合形顶点中的最坏点以复合形顶点中的最坏点X(H)为基点，把为基点，把X(H)和其余和其余各顶点的几何中心点各顶点的几何中心点X(C)的连线方向作为搜索方向的连线方向作为搜索方向S，采用，采用映射、延伸或收缩的方法进行一维搜索，找到好点映射、延伸或收缩的方法进行一维搜索，找到好点X(R)，则以该点代替最坏点组成新的复合形，重复以上步骤迭代调则以该点代替最坏点组成新的复合形，重复以上步骤迭代调优。优。第四十页，讲稿共四十三页哦7.5 离散复合形法（续）离散复合形法（续）设设n为维数，为维数，p为离散变量的个数，则通过一维搜索为离散变量的个数，则通过一维搜索得到的新的离散点得到的新的离散点X(R),其各分量值应为：其各分量值应为：a离散一维搜索的步长因子；离散一维搜索的步长因子；Si离散一维搜索方向离散一维搜索方向S=X(C)-X(H)的各分量，即：的各分量，即：表示取表示取 最靠近的离散值最靠近的离散值qij第四十一页，讲稿共四十三页哦复合形法的终止准则复合形法的终止准则当离散复合形所有顶点在各坐标轴方向上的最大距离当离散复合形所有顶点在各坐标轴方向上的最大距离di不大于相不大于相应设计变量应设计变量xi的离散值增量的离散值增量i（对连续变量为拟离散增量（对连续变量为拟离散增量i i）时，）时，表明离散复合形各顶点的坐标值已不再可能产生有意义的变化，表明离散复合形各顶点的坐标值已不再可能产生有意义的变化，按下式计算：按下式计算：第四十二页，讲稿共四十三页哦感感谢谢大大家家观观看看第四十三页，讲稿共四十三页哦