当前位置：文档之家 › 8、离散变量的最优化方法

8、离散变量的最优化方法

  • 格式：ppt
  • 大小：925.00 KB
  • 文档页数：42

下载文档原格式

  / 42

合集下载

第一章 离散最优化算法

第一章 离散最优化算法

∑ δ i Pi = 0
i =1
k
1．1－9
不妨假定存在某δi>0，令
o ⎧ ⎫ ⎪xj ⎪ ε = min ⎨ δ j > 0⎬ ⎪ ⎪ ⎩δ j ⎭
定义
o ⎧ …，k ， 2， ⎪ x j − εδ j , 若j = 1 x =⎨ o …，n , 若j = k + 1 ，k + 2， ⎪ ⎩x j * j
o o
o
o
∑P x
j =1 j

j
= b 的唯一解，从而由基可行解的定义知
Xo 为基可行解。当 k<m，由于 A 的秩为 m，故可在 Pk＋1，Pk＋2，…，Pn 中选取（m－k）列， 不妨设为 Pk＋1，Pk＋2，…，Pm，使 P1，P2，…，Pk，Pk＋1，…，Pm 构成线性无关的 m 列， 从而就是一个基，类似地可证明 Xo 就是对应这个基的基可行解。 引理 1．1．2 任一个线性规划，若它有可行解，则它必有基可行解。 证明 设 Xo 是（LP）的一个可行解，并且它是（LP）的所有可行解中具有正分量个数 最小的可行解。我们将证明 Xo 必是基可行解。 不妨设 Xo 的头 k 个分量 Xo1，Xo2，…，Xok 是非零的，而其余分量均为 0。如果 Xo 不是 基可行解，那么由引理 1．1 知 P1，P2，…，Pk 必线性相关，即存在不全为零的数 δ1，δ2，…， δk，使
则 x*是（LP）的一个可行解。事实上，由ε的选取保证了对一切 j＝1，2，…，k，
o x* j = x j − εd j ≥ 0 ，其次， k
Ax* = Ax o − ε ∑ Pjδ j = Ax o = b
j =1
因 此 x* 是 可 行 解 。 进 而 ， 由 ε 的 选 取 知 ， 必 有 某 一 下 标 r ， 使 ε =

多目标及离散变量优化方法-文档资料

多目标及离散变量优化方法-文档资料

min F ( x) wi fi ( x)
i 1
l
wi——加权因子 (wi≥0，i=1,2,…，l ) 加权因子取值对计算结果的正确性影响较大。
第六章 第二节 多目标优化方法
加权因子wi确定的方法: ①将各分目标转化后加权 为消除各分目标在量级上的差别，先将分目标函数fi(x) 转化为无量纲等量级目标函数 f i ( x) (i 1,2,...,l ) ( f i ( x) 1) 再组成统一目标函数。 l F ( x) wi f i ( x)
第六章
结束
第一节 多目标优化问题
机械设计中，同时要求几项设计指标达到最优的问题 ——多目标优化设计问题
T .. ( x ) [ f ( x ), f ( x ) f ( x )] F 2 l min min 1 n
s.t. g j ( x) 0 ( j 1,2,...,m)
x R
x R n
第二节 一、主要目标法
多目标优化方法
基本思想：多个目标中选择一个目标作为主要目标， 而其它目标则只需满足一定的要求即可，即 将目标转化为约束条件 目标函数转化为：
f k ( x) min (k ) x(D k) D x | f i min f i ( x) f i max (i 1,2,...,k 1, k 1,...l , x D)
式中，f imin和f imax为第i个目标函数的上、下限。 一般 f i ( x) 只有问题，通过一定方法转化为 统一目标函数或综合目标函数作为多目标优 化问题的评价函数。
第六章 第二节 多目标优化方法
常用的方法有：线性加权法、理想点法（目标规划法） 、 功效系数法和极大极小法等。

多目标及离散变量优化方法

多目标及离散变量优化方法

单目标极小化问题
（5-13）
由此可知，对式（5-13）求出最优解[X *, ],其中的 x*即为原多目标
极小化问题的弱有效解。
《车辆优化设计理论与实践》教学课件
5.2.3 理想点法与平方和加权法
理想点法是以各分目标函数作为各个目标各自的理想值，
若能使各个目标尽可能接近各自的理想值，那么，就可以
求出较好的非劣解。根据这个思想，将多目标优化问题转
介绍一种确定权系数的方法。按此法，多目标优化问题的评价函数的
极小化如式 （5-5）所示。其中 Wi 1/ fi*
《车辆优化设计理论与实践》教学课件
5.2.2极大极小法
对于多目标优化问题 min F(X ) ,可用这样的思想求解，即考虑对各个 目标最不利情况下求出xD最有利的解。就是对多目标极小化问题采用
若在理想点法的基础上引入权系数，构造的评价函数为
l
U ( X ) Wi ( fi ( X ) fi )2 i1
此即为平方和加权法。
（5-15）
求得评价函数的最优解，就是原多目标优化问题式（5-1）
的解
l
min [
X D
Wi (
i1
fi(X )
fi )2]
（5-16）
评价函数也可采用加权极大模型式 U (X ) m1iaxl {Wi | fi (X ) fi |}
各个目标f
它。即取
（i=
i
1,…,
l
）中的最大值作为评价函数的函数值来构造
U
(
f
)
max{
1il
fi
(
X
)}
（5-8）
为评价函数，其中f=[ f1, f2,, fl ]T 。对式（5-8）求优化解就是进行

连续优化、离散优化、组合优化与整数优化

连续优化、离散优化、组合优化与整数优化

连续优化、离散优化、组合优化与整数优化最优化问题（optimization problem）⾃然地分成两类：⼀类是连续变量的问题，称为连续优化问题；另⼀类是离散变量的问题，称为离散优化问题。

1. 连续优化（continuous optimization）连续优化是求解连续优化是求解在连续变量的问题，其⼀般地是求⼀组实数，或者⼀个函数。

离散优化（discrete optimization）2. 离散优化连续优化是求解离散变量的问题，是从⼀个⽆限集或者可数⽆限集⾥寻找⼀个对象，典型地是⼀个整数，⼀个集合，⼀个排列，或者⼀个图。

3. 组合优化（combinatorial optimization）组合优化问题的⽬标是从组合问题的可⾏解集中求出最优解，通常可描述为：令Ω={s1，s2，…，sn}为所有状态构成的解空间，C(si)为状态si对应的⽬标函数值，要求寻找最优解s*，使得对于所有的si∈Ω，有C(s*)=minC(si)。

组合优化往往涉及排序、分类、筛选等问题，它是运筹学的⼀个重要分⽀。

典型的组合优化问题有旅⾏商问题（Traveling Salesman Problem－TSP）、加⼯调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）、0-1背包问题（Knapsack Problem）、装箱问题（Bin Packing Problem）、图着⾊问题（Graph Coloring Problem）、聚类问题（Clustering Problem）等。

这些问题描述⾮常简单，并且有很强的⼯程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运⾏时间与极⼤的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。

正是这些问题的代表性和复杂性激起了⼈们对组合优化理论与算法的研究兴趣。

4. 整数优化（integer programming, IP）要求所有的未知量都为整数的线性规划问题叫做整数规划 (integer programming, IP) 或整数线性规划 (integer linear programming, ILP) 问题。

06多目标及离散变量优化方法简介

06多目标及离散变量优化方法简介

U (x ) =
∑
l
i =1
f i (x ) f i fi
2
分层序列法及宽容分层序列法
分层序列法的基本思想是将多目标优化问 题式中的J个目标函数分清主次,按其重要程度 逐一排除,然后依次对各个目标函数求最优解. 不过后一目标应在前一目标最优解的集合域内寻 优.
现在假设f1(x)最重要,f2 (x)其次,f3 (x)再其次,…. 首先对第一个目标函数f1(x)求解,得最优值
x∈R
s.t . g j ( x ) ≤ 0 ( j = 1, 2, , p ) hk (x ) = 0 ( k = 1,2, , q )
f 2 (x )
f 3 (x )
T f 4 ( x )]
在多目标优化模型中,还有一类模型,其特点 是,在约束条件下,各个目标函数不是同等地被最优 化,而是按不同的优先层次先后地进行优化.例如: 工厂生产:1号产品,2号产品,3号产品,…,M号 产品.应如何安排生产计划,在避免开工不足的条件 下,使工厂获得最大利润,工人加班时间尽量地少. 若决策者希望把所考虑的两个目标函数按其重 要性分成以下两个优先层次:第一优先层次——工厂 获得最大利润.第—优先层次——工人加班时间尽可 能地少.那么,这种先在第一优先层次极大化总利润, 然后在此基础上再在第二优先层次同等地极小化工人 加班时间的问题就是分层多目标优化问题.
主要目标法的思想是抓住主要目标,兼顾其它 要求.求解时从多目标中选择一个目标作为主要目 标,而其它目标只需满足一定要求即可.为此,可 将这些目标转化成约束条件.也就是用约束条件的 形式来保证其他日标不致太差,这样处理后,就成 为单目标优化问题. 设有l个目标函数f1(x),f2(x),…,fl(x),其 中 x ∈ D,求解时可从上述多目标函数中选择一个 f(x)作为主要目标,则问题变为

离散变量优化问题

离散变量优化问题
z z 各分支的最优目标函数中若有小于 ，则剪掉这枝；若大于
且不符合整数条件，则重复前两步，直到找到最优解。
分枝定界法计算过程：
上界
讨论松弛问题L0 : 1、L0无最优解， 则(IP)无最优解 结束 2 、X 最 * 0 ( x * 优 0， 1 x * 0, 2 解 ,x * o)n 最 , z 0优值
，则认为收敛。
（2） 若分枝后得到非整数解, 如果比整数解更好，则这枝继续分枝；
m a x Z x 5 x 在松弛问题B的最优解中任选一个不符合整数条件的变量 ,其值为 ,以 表示小于 的最大整数。
1
2
分枝定界法就是将B的可行域分成子区域(称为分枝)的方法，逐步减小 ，增大 ，最终求到 。
x x 先求（LP21）,如图所1 示。 2 2
x1 x2 2
s
.t
.
5
x1 x1
6
x2
30 4
x 1 , x 2 0
分枝定界法基本思想： 设有最大化的整型优化问题A，相应有松弛问题B，从解松弛问题 B开始，若其最优解不符合A的整数条件，那么B的最优目标函数
必是A的最优目标函数 z * 的上界，记作 z ；而A的任意可行解
z 的目标函数值将是 z * 的一个下界，记作 。
§9.3 离散变量优化——组合形法
离散变量数学模型的一般形式：
min f ( x)
x Rn
s.t. gu ( x) 0 u 1, 2, , m
x=[x D , x C ]T
x D [ x1, x2 , , x p ]T X D R D
x C [ x p1, x p2 ,
, xn ]T
基本思想：通过对初始复合形调优迭代．使新的组合形不断 向最优点移动和收缩，直至满足一定的终止条件为止。

离散优化问题及其求解技术

离散优化问题及其求解技术在我们的日常生活和工作中，经常会遇到各种各样需要做出最优决策的情况。

比如，在生产线上如何安排工人的工作任务，以达到最高的生产效率；在物流运输中，如何规划车辆的行驶路线，以最小化运输成本；在项目管理中，如何分配资源，以确保项目按时完成。

这些问题都可以归结为离散优化问题。

离散优化问题是指在有限个或可数个可行解中，寻找最优解的问题。

与连续优化问题不同，离散优化问题的可行解是离散的，不是连续的。

这就使得离散优化问题的求解更加具有挑战性。

离散优化问题的类型多种多样。

其中，最常见的包括整数规划问题、组合优化问题和网络优化问题。

整数规划问题要求决策变量必须取整数值。

例如，在决定要购买多少台机器设备时，机器的数量只能是整数。

组合优化问题则涉及到从一组有限的对象中选择最优的组合。

比如，旅行商问题（TSP），就是要找到一个旅行商在多个城市之间旅行的最短路径，且每个城市只能访问一次。

网络优化问题则是在网络结构上进行优化，比如在通信网络中如何分配带宽，以最大化网络的性能。

那么，如何求解这些离散优化问题呢？下面我们来介绍一些常见的求解技术。

精确算法是一类能够保证找到最优解的方法。

其中，分支定界法是一种常用的整数规划精确算法。

它通过将问题不断分解为子问题，并为每个子问题设定上下界，逐步缩小搜索范围，最终找到最优解。

然而，精确算法在处理大规模问题时，往往会面临计算时间过长的问题。

启发式算法则是在合理的时间内找到一个较好的解，但不能保证是最优解。

常见的启发式算法包括贪心算法和局部搜索算法。

贪心算法在每一步都做出当前看起来最优的选择，但这种局部最优的选择并不一定能导致全局最优解。

局部搜索算法从一个初始解开始，通过在其邻域中搜索更好的解来逐步改进。

例如，模拟退火算法就是一种基于局部搜索的启发式算法，它通过模拟物理中的退火过程，在搜索过程中引入一定的随机性，以避免陷入局部最优。

元启发式算法是近年来发展起来的一类高效的求解方法，如遗传算法、蚁群算法和粒子群优化算法等。

离散控制系统中的最优控制

离散控制系统中的最优控制离散控制系统是指由一系列离散（非连续）的控制器构成的系统，它对系统进行离散化处理和采样，并根据采样值进行控制。

在离散控制系统中，最优控制是一种优化问题，旨在找到使给定性能指标最小化或最大化的控制策略。

本文将介绍离散控制系统中的最优控制方法和应用。

一、动态规划方法动态规划是离散控制系统最优控制的常用方法之一。

它通过将控制问题划分为一系列互相关联的子问题，逐步求解并获得最优解。

动态规划方法有以下几个步骤：1. 状态定义：将系统的状态用离散变量表示，例如状态矢量。

2. 动态规划递推方程：建立系统状态在不同时间步长之间的递推关系，用于计算最优解。

3. 边界条件：确定初始和终止条件，保证递推方程的有效求解。

4. 最优化准则：选择适当的性能指标，例如代价函数或效用函数，作为最优化准则。

5. 迭代求解：根据动态规划递推方程和最优化准则进行迭代求解，得到最优控制策略。

动态规划方法在离散控制系统中有广泛的应用。

例如，在机器人路径规划和自动化生产线调度等领域，动态规划方法可以帮助确定最优路径和最优调度策略，实现系统的高效控制。

二、最优控制理论最优控制理论是离散控制系统中另一种常用的最优控制方法。

它通过优化控制问题的最优化准则，找到使性能指标达到最小值或最大值的控制策略。

最优控制理论的核心是求解最优控制问题的最优化方程。

最优控制问题的最优化方程通常通过极值原理或哈密顿-雅可比-贝尔曼（HJB）方程来建立。

这些方程使用众多数学工具，如变分法和微分几何学，将控制问题转化为求解偏微分方程或变分问题。

通过求解最优化方程，可以得到最优控制器的具体形式和参数。

最优控制理论在离散控制系统中具有重要的应用价值。

例如，在飞行器姿态控制和无线传感网络中，最优控制理论可以帮助设计出具有最佳性能的控制器，提高系统的稳定性和响应速度。

三、模型预测控制（MPC）模型预测控制是离散控制系统中一种基于模型的最优控制方法。

它将系统建模为一个预测模型，并根据预测模型的结果来制定最优控制策略。

8、离散变量的最优化方法


离散变量
随机变量
不确定型
混合变量
所以需要相应的优化方法。
8.1 引 言（续）
二、工程实际设计的需要 例：决定修建一条防洪堤坝。 根据历年的水文资料，台风的 年最大风速：
b
max 服从正态分布 x , x2 (m / s) 服从对数正态分布，
max
2 即 max LN x , x (m / s ) 即 max～LN x , 2 ( m / s ) x 其中：均值 x 80(m / s )， 其中：均值 x 80( m / s )， 2 方差 x2 12(m / s )； 方差 x 12( m / s )； 海浪高度H 与年最大 速成正比， 海浪高度H与年最大风速成正比， H 0.2 max (m)； H 0.2 max ( m)； 海浪 堤 的 ：P 0.13 max 13 2 ) ( MPa) 20. ( MPa 海浪对堤坝的压强： P
3、连续变量离散化的方法
xiu xil i li 1 i p 1，p 2， ，n
其中： xiu，xil 为连续变量xi的上、下界， li 为欲取离散值的个数。 xi 坐标轴上的第 个拟离散点为： ij， j x 其相邻两个拟离散点为 xij i，xij，xij i ：
题的最优（称为离散最优点）的坐标．这便构成离
散变量最优化问题的凑整解法。
7.4 凑整解法与网格法（续） 图中A、B两点分别表示二维离散变量优化问 题凑整法中的连续最优点与离散最优点。
7.4 凑整解法与网格法（续） 凑整法可能出现的两个问题：
1、与连续最优点A最接近的离散点B落在可行域外，不 可以接受；
max
max 服 正 分布，

多目标优化与离散变量优化


(k )
2 ( k ) [min(49 x12 x2 , 0)]2 [min( x1 , 0)]2 [min( x2 , 0)]2 (k )
) 4 x1 x 12
2 2
4q1 (1 q1 )
k
离散变量优化问题程序
2 min f ( X ) 4 x1 x2 12
) 4 x1 x 12
2 2
4q1 (1 q1 )
k
( X , +
(k )
2 ( k ) [min(49 x12 x2 , 0)]2 [min( x1 , 0)]2 [min( x2 , 0)]2 (k )
) 4 x1 x 12
S.t.
2 g1 ( X ) 49 x12 x2 0
g 2 ( X ) x1 0 g3 ( X ) x2 0 x1 2, 4, 6
x1是离散变量，构造外点形式的罚函数
( X , +
(k )
2 ( k ) [min(49 x12 x2 , 0)]2 [min( x1 , 0)]2 [min( x2 , 0)]2 (k )
p为离散变量的个数，n-p为连续变量的个数。 构造罚函数
p k 1 (k) (k) (X ,r ,s k , k ) f (X ) r sk 4q j (1 q j ) g ( X ) u=1 u j=1 m
p k 1 (X , k ,s k , k ) f (X ) k sk 4q j (1 q j ) g ( X ) u=1 u j=1 m
§7－1 多目标优化概述
1、问题的提出
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

7.3 离散最优解（续）
3．离散局部最优解 若 X * D ，对所有 X UN ( X *) D 恒有 f ( X *) f ( X ) 则称X*是离散局部最优点 4、拟离散局部最优解 若 X * D ，对所有 X UC ( X *) D 恒有 f ( X *) f ( X ) 则称X*是拟离散局部最优点 5、离散全域最优解 若 X ** D ，对所有 X D 恒有 f ( X **) f ( X ) 则称X**是离散全域最优点
max
max 服 正 分布，
h H
8.1 引 言（续）
b
现在需要设计堤坝 的截面尺寸 b 和 h，在
保证不受灾害的概率不
低于99.9%，堤坝不受 冲压损坏的概率不低于 99.0% 的要求下，使投 资最小。
h H
8.1 引 言（续） 三、传统方法的局限性
求离散问题的最优解，传统的方法是先用连续变
n p
p
C
T
p 1
p2
n p
n
若Rp为空集时，Rn为全连续变量设计问题； 若Rn-p为空集时，Rn 为全离散变量设计问题。
§7.2 离散变量优化设计的基本概念(续）
在机械优化设计中．常见的约束非线性离散 变量最优化问题的数学模型为：
min f ( X ) D X g ( X ) 0
这些交点就是三维离 散设计空间中的离散点。
§7.2 离散变量优化设计的基本概念（续）
4、P维离散设计空间 对于p维离散变量，过每个变量离散值作该变量 坐标轴的垂直面，这些超平面的交点的集合就是p维 离散设计空间，用 R p表示。 而这些交点就是p维离散设计空间中的离散点，用 D x 表示。
X
D
x1 , x2 , , x p R p
2、与连续最优点A最接近的离散点B并非离散最优点C， 点B仅是一个工程实际可能接受的较好的设计方案。
改进：即在求得连续最优点A并调整到最接近的 离散点B以后，在B的离散单位邻域UN（X）或离 散坐标邻域UC（X)内找出所有的离散点，逐个 判断其可行性并比较其函数值的大小．从中找到 离散局部最优点或拟离散局部最优点。
D u
(u 1, 2,...m)
T
X D X D x1 , x2 ,...x p R D X T C C X X x p 1 , x p 2 ,...xn RC
N—设计变量维数；m—不等式约束条件个数 P—离散变量的个数； XD—离散子空间；RD—离散变量子集； XC—连续子空间；RC—连续变量子集；
X x p 1 , x p 2 ,, xn R
C T


n p
§7.2 离散变量优化设计的基本概念(续）
4、N维设计空间
R R R 其中：离散设计空间为 X x , x ,, x R 连续设计空间为 X x , x ,, x R
n p
D T 1 2 p
l为各离散设计变量可取离散值个数中的最大值 注：①因为离散变量是有限个,所以离散空间是有界的。 ②某个离散变量的取值不足l个，其余值可用预先 规定的自然数补齐。
§7.2 离散变量优化设计的基本概念(续）
4、N-P维连续设计空间 N个设计变量中有P个离散变量，此外有N-P个 连续变量。 N-P维连续设计空间
3、连续变量离散化的方法
xiu xil i li 1 i p 1，p 2， ，n
其中： xiu，xil 为连续变量xi的上、下界， li 为欲取离散值的个数。 xi 坐标轴上的第 个拟离散点为： ij， j x 其相邻两个拟离散点为 xij i，xij，xij i ：
7.3 离散最优解（续）
严格说来，离散优化问题的最优解应
是指离散全域最优点而言，但它与一般的
非线性优化问题一样，离散优化方法所求
得的最优点一般是局部最优点，这样通常
所说的最优解均指局部最优解。
7.3 离散最优解（续）
三、收敛准则 设当前搜索到的最好点为x(k)，需要判断其是否
收敛。
在x(k)的单位邻域中查3n – 1个点，若未查到比x(k)
题的最优（称为离散最优点）的坐标．这便构成离
散变量最优化问题的凑整解法。
7.4 凑整解法与网格法（续） 图中A、B两点分别表示二维离散变量优化问 题凑整法中的连续最优点与离散最优点。
7.4 凑整解法与网格法（续） 凑整法可能出现的两个问题：
1、与连续最优点A最接近的离散点B落在可行域外，不 可以接受；
T
P 个离散设计变量组成P维离散设计空间。
§7.2 离散变量优化设计的基本概念（续）
p个离散变量全部可取的离散值的集合称为p维 离散变量的值域，可用一个p*l阶的矩阵Q来表示
q11 q 21 Q q p1 q12 q22 q p2 q1l q2 l q pl pl
离散点：，qij1 , qij , qij1 , 离散间隔： ， i i
D
i 1,2,, n
j 1,2,, l代表离散点个数；
只有在均匀离散空间中 ：i i
X x1 , x2 ,, x p


T
Rp
§7.2 离散变量优化设计的基本概念（续） 2、二维离散设计空间
§7.2 离散变量优化设计的基本概念(续）
二、非均匀离散变量和连续变量的均匀离散化处理 1、整型变量的离散
整型变量可看作为是离散间隔恒定为1的离散 变量。是离散变量的特例。
2、连续变量的离散化 有时为了提高优化设计计算效率，将连续变量 转化为拟离散变量。
§7.2 离散变量优化设计的基本概念（续）
7.5 离散复合形法（续）
一、初始离散复合形的产生
1、初始离散点的确定
用复合形法在n维离散设计空间搜索时，通常取 初始离散复合形的顶点数为K=2n+1个。先给定一 个初始离散点X(0)，X(0)必须满足各离散变量值的边 界条件，即：
x x
x
( j) i
ai ri (bi ai )
( j)
i 1, 2,, n ;
j 2,3,, k
将第q+1点朝着点X (s)的方向移动，新点X (q+1)为： X(q+1)= X(s)+0.5 (X(q+1)—X(s))
X
(r )
X
(c)
(X
(c)
X
( h)
)
反射系数的初值一般取 1.3
量优化设计方法求连续变量的最优解，然后圆整到
离散值上。 弊病：可能得不到可行最优解，或所得的解不是 离散最优解。
8.1 引 言（续） x*是连续变量的最优点；
x(1)是圆整后最近的离散点，但不可行；
x2
x(2)是最近的可行离散 点，但不是离散最优点；
●
X(2) X
x(3)是离散最优点。
0
●
X(3)
7.4 凑整解法与网格法（续） 点若不可行，则去掉； X(k)点 若可行，则计算目标函数值f(X(k))，并与以前计 算取得的可行最好点x(l)比较,若f(X(k))<f(X(l)), 则将X(k)作为新的最好点 继续检查所有的全部离散点后，其最好点就是该 优化问题的最优解X**。 优点：原理简单 缺点：设计变量维数n以及每个变量离散值数目很 多时，计算量大。
的目标函数值更小的点，则收敛，x*=x(k) 。
7.4 凑整解法与网格法 一、凑整解法
解决离散变量的优化问题很容易考虑为；将离
散变量全都权宜地视为连续变量，用一般连续变量 最优化方法求得最优点（称为连续最优点），然后 再把该点的坐标按相应的设计规范和标准调整为与 其最接近的整数值或离散值，作为离散变量优化问
7.3 离散最优解
由于离散设计空间的不连续性，离散变量最优点与 连续变量最优点不是同一概念，必须重新定义。
1．离散单位邻域（UN(X)) 在设计空间中，离散点X的单位邻域UN(X)是 指如下定义的集合。
X xi i , xi , xi i , i 1, 2,... p) UN ( X ) X xi i , xi , xi i , i p 1, p 2,...n)
8.1 引 言
在许多工程问题中，设计变量实际上不是连续 变化的。 齿轮的齿数只能是正整数．是整型变量； 齿轮的模数应按标准系列取用；
钢丝直径、钢板厚度、型钢的型号也都应符合 金属材料的供应规范等等
属于这样的一些必须取离散数值的设计变量
均称为离散变量。
8.1 引 言（续）
一、 变量类型 工程实际问题中不是单一的连续变量，经常 是各种类型变量的混合。有： 连续变量 确定型 整型变量
二维连续设计变量的设计空间是代表该两个 变量的两条坐标轴形成的平面；
二维离散设计空间则 是上述平面上的某些 点的集合； 这些点的坐标值分别离 散变量可取的离散值．称 为二维离散设计空间的离 散点，
§7.2 离散变量优化设计的基本概念（续） 3、三维离散设计空间
对于三维离散变量，过每个变量离散值作该 变量坐标轴的垂直面．这些平面的交点的集合就 是三维离散设计空间。
●
●
F
G
H
0
7.3 离散最优解（续） 2、离散坐标邻域（UC(X)) 在设计空间中离散点X的离散坐标邻域UC(X)是指 以X点为原点的坐标轴线和离散单位邻域UN（X）的 交点的集合。 图示离散坐标邻域为：
UC( X ) B, D, E, G, X
一般在p维离散变量情况下 离散坐标邻域的离散点总数 为N=2p+1。
● ●
x* (1) x1
§7பைடு நூலகம்2 离散变量优化设计的基本概念