离散变量的最优化方法

关于离散变量的最优化方法

钢丝直径、钢板厚度、型钢的型号也都应符合金属材料的供应规范等等

在许多工程问题中，设计变量实际上不是连续变化的。

8.1引言齿轮的齿数只能是正整数．是整型变量；齿轮的模数应按标准系列取用；

属于这样的一些必须取离散数值的设计变量均称为离散变量。

第2页,共43页，2024年2月25日，星期天一、变量类型

工程实际问题中不是单一的连续变量，经常是各种类型变量的混合。有：连续变量确定型整型变量离散变量随机变量不确定型混合变量所以需要相应的优化方法。

8.1引言（续）第3页,共43页，2024年2月25日，星期天二、工程实际设计的需要例：决定修建一条防洪堤坝。根据历年的水文资料，台风的年最大风速：8.1引言（续）服从正态分布第4页,共43页，2024年2月25日，星期天

现在需要设计堤坝的截面尺寸

b

和h，在保证不受灾害的概率不低于99.9%，堤坝不受冲压损坏的概率不低于99.0%

的要求下，使投资最小。8.1引言（续）第5页,共43页，2024年2月25日，星期天三、传统方法的局限性

求离散问题的最优解，传统的方法是先用连续变量优化设计方法求连续变量的最优解，然后圆整到离散值上。弊病：可能得不到可行最优解，或所得的解不是离散最优解。8.1引言（续）第6页,共43页，2024年2月25日，星期天●x*●X(1)●X(2)●X(3)x(3)是离散最优点。x10x28.1引言（续）

x*是连续变量的最优点；x(1)是圆整后最近的离散点，但不可行；x(2)是最近的可行离散点，但不是离散最优点；第7页,共43页，2024年2月25日，星期天一、离散设计空间1、一维离散设计空间qij-1

●qij

●qij+1

●Xi§7.2

离散变量优化设计的基本概念

在一条表示变量的坐标轴上的一些间隔点的集合，这些点的集合称为离散设计空间；这些点的坐标值是该变量可取的离散值，这些点称为一维离散设计空间的离散点。

第8页,共43页，2024年2月25日，星期天

二维连续设计变量的设计空间是代表该两个变量的两条坐标轴形成的平面；

这些点的坐标值分别离散变量可取的离散值．称为二维离散设计空间的离散点，二维离散设计空间则是上述平面上的某些点的集合；§7.2离散变量优化设计的基本概念（续）2、二维离散设计空间第9页,共43页，2024年2月25日，星期天§7.2离散变量优化设计的基本概念（续）

这些交点就是三维离散设计空间中的离散点。

对于三维离散变量，过每个变量离散值作该变量坐标轴的垂直面．这些平面的交点的集合就是三维离散设计空间。3、三维离散设计空间第10页,共43页，2024年2月25日，星期天P个离散设计变量组成P维离散设计空间。§7.2

离散变量优化设计的基本概念（续）4、P维离散设计空间

对于p维离散变量，过每个变量离散值作该变量坐标轴的垂直面，这些超平面的交点的集合就是p维离散设计空间，用表示。而这些交点就是p维离散设计空间中的离散点，用表示。

第11页,共43页，2024年2月25日，星期天注：①因为离散变量是有限个,所以离散空间是有界的。②某个离散变量的取值不足l个，其余值可用预先规定的自然数补齐。§7.2

离散变量优化设计的基本概念（续）p个离散变量全部可取的离散值的集合称为p维离散变量的值域，可用一个p*l阶的矩阵Q来表示l为各离散设计变量可取离散值个数中的最大值第12页,共43页，2024年2月25日，星期天§7.2

离散变量优化设计的基本概念(续）4、N-P维连续设计空间

N个设计变量中有P个离散变量，此外有N-P个连续变量。N-P维连续设计空间第13页,共43页，2024年2月25日，星期天§7.2

离散变量优化设计的基本概念(续）4、N维设计空间若Rp为空集时，Rn为全连续变量设计问题；若Rn-p为空集时，Rn为全离散变量设计问题。

其中：离散设计空间为

连续设计空间为第14页,共43页，2024年2月25日，星期天

在机械优化设计中．常见的约束非线性离散变量最优化问题的数学模型为：§7.2

离散变量优化设计的基本概念(续）N—设计变量维数；m—不等式约束条件个数P—离散变量的个数；XD—离散子空间；RD—离散变量子集；XC—连续子空间；RC—连续变量子集；第15页,共43页，2024年2月25日，星期天§7.2

离散变量优化设计的基本概念(续）1、整型变量的离散

整型变量可看作为是离散间隔恒定为1的离散变量。是离散变量的特例。2、连续变量的离散化有时为了提高优化设计计算效率，将连续变量转化为拟离散变量。二、非均匀离散变量和连续变量的均匀离散化处理第16页,共43页，2024年2月25日，星期天§7.2

离散变量优化设计的基本概念（续）3、连续变量离散化的方法第17页,共43页，2024年2月25日，星期天

由于离散设计空间的不连续性，离散变量最优点与连续变量最优点不是同一概念，必须重新定义。1．离散单位邻域（UN(X))7.3

离散最优解

在设计空间中，离散点X的单位邻域UN(X)是指如下定义的集合。第18页,共43页，2024年2月25日，星期天图示为二维设计空间中离散点X的离散单位邻域7.3

离散最优解（续）

一般情况下，设离散变量的维数为p，则UN(X)内的离散点总数为N=3p(p次方）

x●

B●●GD●E●A●●FC●●

Hεiεi0x2第19页,共43页，2024年2月25日，星期天7.3

离散最优解（续）

2、离散坐标邻域（UC(X))

在设计空间中离散点X的离散坐标邻域UC(X)是指以X点为原点的坐标轴线和离散单位邻域UN（X）的交点的集合。图示离散坐标邻域为：

一般在p维离散变量情况下离散坐标邻域的离散点总数为N=2p+1。第20页,共43页，2024年2月25日，星期天3．离散局部最优解7.3

离散最优解（续）若，对所有恒有则称X*是离散局部最优点4、拟离散局部最优解若，对所有恒有则称X*是拟离散局部最优点5、离散全域最优解若，对所有恒有则称X**是离散全域最优点第21页,共43页，2024年2月25日，星期天

严格说来，离散优化问题的最优解应是指离散全域最优点而言，但它与一般的非线性优化问题一样，离散优化方法所求得的最优点一般是局部最优点，这样通常所说的最优解均指局部最优解。7.3

离散最优解（续）第22页,共43页，2024年2月25日，星期天三、收敛准则

设当前搜索到的最好点为x(k)，需要判断其是否收敛。在x(k)的单位邻域中查3n–1个点，若未查到比x(k)的目标函数值更小的点，则收敛，x*=x(k)。7.3

离散最优解（续）第23页,共43页，2024年2月25日，星期天7.4凑整解法与网格法一、凑整解法

解决离散变量的优化问题很容易考虑为；将离散变量全都权宜地视为连续变量，用一般连续变量最优化方法求得最优点（称为连续最优点），然后再把该点的坐标按相应的设计规范和标准调整为与其最接近的整数值或离散值，作为离散变量优化问题的最优（称为离散最优点）的坐标．这便构成离散变量最优化问题的凑整解法。第24页,共43页，2024年2月25日，星期天

图中A、B两点分别表示二维离散变量优化问题凑整法中的连续最优点与离散最优点。7.4凑整解法与网格法（续）第25页,共43页，2024年2月25日，星期天7.4凑整解法与网格法（续）

1、与连续最优点A最接近的离散点B落在可行域外，不可以接受；凑整法可能出现的两个问题：2、与连续最优点A最接近的离散点B并非离散最优点C，点B仅是一个工程实际可能接受的较好的设计方案。第26页,共43页，2024年2月25日，星期天改进：即在求得连续最优点A并调整到最接近的离散点B以后，在B的离散单位邻域UN（X）或离散坐标邻域UC（X)内找出所有的离散点，逐个判断其可行性并比较其函数值的大小．从中找到离散局部最优点或拟离散局部最优点。凑整解或改进的凑整法都是基于离散最优点就在连续最优点的附近。但实际问题有时并非如此，如图，真正的离散最优点C离连续最优点A很远。第27页,共43页，2024年2月25日，星期天二、网格法网格法是解离散变量优化问题的一种最原始的遍数法。7.4凑整解法与网格法（续）

在离散变量的值域内，先按各变量的可取离散值在设计空间内构成全部离散网格点，全域最优点X’”应是可行域中诸网格点目标函数值最小者．这就需要逐个检查网格点是否可行和择其最优。第28页,共43页，2024年2月25日，星期天7.4凑整解法与网格法（续）点若不可行，则去掉；若可行，则计算目标函数值f(X(k))，并与以前计算取得的可行最好点x(l)比较,若f(X(k))<f(X(l)),则将X(k)作为新的最好点

继续检查所有的全部离散点后，其最好点就是该优化问题的最优解X**。优点：原理简单缺点：设计变量维数n以及每个变量离散值数目很多时，计算量大。X(k)点第29页,共43页，2024年2月25日，星期天7.5离散复合形法

离散复合形法是在求解连续变量复合形法的基础上进行改造，使之能在离散空间中直接搜索离散点，从而满足求解离散变量优化问题的需要。通过对初始复合形调优迭代．使新的复合形不断向基本思想：最优点移动和收缩，直至满足一定的终止条件为止。特点：复合形顶点必须是可行的离散点。第30页,共43页，2024年2月25日，星期天

将第q+1点朝着点X

(s)的方向移动，新点X

(q+1)为：

X(q+1)=X(s)+0.5(X(q+1)—X(s))连续变量的复合形法第31页,共43页，2024年2月25日，星期天第32页,共43页，2024年2月25日，星期天反射系数的初值一般取第33页,共43页，2024年2月25日，星期天一、初始离散复合形的产生7.5离散复合形法（续）

用复合形法在n维离散设计空间搜索时，通常取初始离散复合形的顶点数为k=2n+1个。先给定一个初始离散点X(0)，X(0)必须满足各离散变量值的边界条件，即：、分别是第i个变量的下限值和上限值。1、初始离散点的确定第34页,共43页，2024年2月25日，星期天7.5离散复合形法（续）2、初始复合形各顶点的产生这样有2n个顶点分别分布于n个设计变量的上下限约束边界上。

二维问题产生的离散复合形的5个顶点第35页,共43页，2024年2月25日，星期天7.5离散复合形法（续）二、约束条件的处理

由于初始复合形顶点的产生未考虑约束条件，此时产生的初始复合形顶点可能会有部分甚至全部落在可行域的外面。

在调优迭代运算中必须保持复合形各顶点的可行性，故如果有部分顶点落在可行域外面，则需将其移入可行域之内。定义离散复合形的有效目标函数为：第36页,共43页，2024年2月25日，星期天7.5离散复合形法（续）f(X)为原目标函数；M为一个比f(X)值数量级大得多的常数；离散复合形的有效目标函数为：第37页,共43页，2024年2月25日，星期天7.5离散复合形法（续）一维变量时的有效目标函数1、在可行域以外，有效目标函数的曲线象一个向可行域倾斜的漏斗;2、当部分复合形顶点在可行域之外时，最坏的顶点X(H)一定位于可行域之外的一个离散点上；D第38页,共43页，2024年2月25日，星期天7.5离散复合形法（续）3、以最坏点X(H)为基点进行一维离散搜索，M在有效目标函数中保持不变；4、随搜索点离约束面的位置而变化离约束面越近，其值越小；反之，其值则越大求的极小值，当其等于