优化离散变量问题

在工程优化问题中，经常会遇到非连续变量的一些参数。它们有些是整数变量，如齿轮的齿数、冷凝器管子的数目、行星轮的个数等；有些是离散变量，如齿轮模数、型钢尺寸以及大量的标准表格、数据等。整数也可视为是离散数的一种特殊情形。

由于离散变量在工程中大量存在，故研究离散变量的优化方法是非常必要的。目前，解决该类问题主要有两种方法：①将所有离散变量视为连续变量，在连续域内搜索，得到最优点后再圆整，即连续变量优化加圆整处理；②依不同变量分别在连续域和离散域内轮换搜索，取得最优解，即混合变量优化。采用方法①不仅会造成设计上的不可行解或得不到真正最优解，而且在有些情况下将失去优化解的实用价值（违背技术标准和技术规范）；若采用方法②，由于必须轮换在连续、离散域内搜索，使得搜索困难、转换次数繁多、算法和程序复杂。

约束非线性混合离散变量优化设计问题的数学模型可表达为

minf（X）

s.t. g_j（X）≤0 （j=1，2，…，m）

x_imin≤x_i≤x_imax （i=1，2，…，m）

式中，X=（x^Dx^C）∈Rⁿ；X^D=（x₁x₂ … x_p）^T∈R^D；X^C=（x_p+1x_p+2 … x_n）^T∈R^C；Rⁿ=R^D×R^C。

其中，x_imin、x_imax分别为变量x_i的上、下界限，X^D为离散变量的子集合，X^C为全连续变量的子集合。当X^D为空集时，为全连续变量型问题；当X^C为空集时，为全离散型问题；两者均为非空集时为混合型问题。若将整数视为离散数的一种特殊情况，则混合离散变量优化问题实际上已包含了混合整数变量的优化问题。

解决工程问题离散变量优化的方法需要与处理连续变量优化技术不完全相同的一种理论和方法。离散最优化是数学规划和运筹学中最有意义，但也是较困难的领域之一。

Dantzig继1949年提出解线性规划的单纯形法不久后所提出的线性整数规划问题，1958年Gomory提出的割平面法，1960年Lang和Doig提出的分支定界法，1965年Balas提出的0-1规划的隐枚举法，奠定了求解线性整数规划的常用三大类算法的基础。后来虽经一些学者对其作了改进与发展，但仍存在计算效率低及只能求解维数较低的问题。工程优化设计的数学模型多数为非线性的，本节主要介绍非线性问题，但非线性离散优化技术要比线性整数规划更困难。目前，数学家们所做的工作还仅限于一些特殊的问题，例如，非负可分离函数、可微凸函数、线性约束的半正定二次函数等，或用线性整数规划向非线性整数规划推广。对于工程中遇到的一般函数，特别是有约束非线性离散变量问题，在理论、算法和程序方面还不十分成熟，缺少有效的通用算法和系统的理论。目前能在工程中解决复杂问题的实用的非线性离散优化方法多数是由从事工程优化的学者提出来的，未必都有严格的数学证明。

约束非线性离散变量的优化方法有：①以连续变量优化方法为基础的方法，如圆整法、拟离散法、离散型惩罚函数法；②离散变量的随机型优化方法，如离散变量随机试验法、随机离散搜索法；③离散变量搜索优化方法，如启发式组合优化方法、整数梯度法、离散复合型法；④其他离散变量优化方法，如非线性隐枚举法、分支定界法、离散型网格与离散型正交网格法、离散变量的组合型法。上述这些方法的解题能力与数学模型的函数状态和变量多少有很大关系，下面只介绍其中的几种主要方法。

1.按连续变量优化为基础的方法

（1）整型化、离散化法（圆整法、凑整法） 该法的特点是先按连续变量方法求得优化解X∗，然后再进一步寻找整型量或离散量优化解，这一过程称为整型化或离散化。下面介绍按连续实型量优化得到优化解后如何圆整化、离散化的方法，并讲述其中可能产生的问题。

设有n维优化问题，其实型最优点为X^∗∈Rⁿ，它的几个实型分量为x_i^∗（i=1，2，…，n），则x_i^∗的整数部分（或它的偏下一个标准量）[x_i^∗]和整数部分加1即[x_i^∗]+1（或它的偏上一个标准量）便是最接近x_i∗的两个整型（或离散型）分量。由这些整型分量的不同组合，便构成了最邻近于实型最优点X∗的两个整型分量及相应的一组整型点群[X_i^∗]^（t）（t=1，2，…，2ⁿ，n为变量维数）。

该整型点群包含有2ⁿ个设计点，在整型点群中，可能有些点不在可行域内，应将它们剔除。在其余可行域内的若干整型点中选取一个目标函数值最小的点作为最优的整型点给予输出。图3-32所示是二维的例子，在实型量最优点X∗周围的整型点群有A、B、C、D四点，图中B点在可行域外，A、B、C三点为在可行域内的整型点群。分别计算其目标函数，由图中等值线可看出，其最优整型点是C点，它即为最优整型设计点[X^∗]。但这样做有时不一定行得通，因为连续变量的最优点通常处于约束边界上，在连续变量最优点附近凑整所得的设计点有可能均不在可行域内，如图3-33所示。显然，在这种情况下，采用连续变量优化点附近凑整法就可能得不到一个可行设计方案。另一方面，这种简单的凑整法是基于一种假设，即假设离散变量的最优点是在连续变量最优点（图3-32中X^∗周围的整型点群）附近。然而，这种假设并非总能成立。下面一个例子可说明这个情况。

minf（X）=-（x₁+5x₂）

s.t. x₁+10x₂≤20

x₁≤2

x₁≥0，x₂≥0

图3-32 X^∗周围整型点群

图3-33 X^∗周围整型点群均不在可行域内

从图3-34中可以看出，这个线性规划问题的设计变量为连续时，在x₁=2，x₂=1.8处有最小目标函数值-11，在这个连续最优解周围最好的可行整数解是（x₁，x₂）=（2，1），此时目标函数值为-7。然而这个问题的最优整数解（x₁，x₂）=（0，2）却不在连续解的附近，这个整数解的最小目标函数值为-10。这些情况表明，凑整法虽然简便，但不一定能得到理想的结果。

图3-34 离X^∗较远处整型点为优化点的情况

由上面分析可知，离散优化点不一定落在某个约束面上，因此对连续变量约束最优解的K-T条件不再成立。与连续变量优化解一样，离散变量优化解通常也是指局部优化解。而局部离散优化解的是指在此点单位邻域UN（x）内查点未搜索到优于X^∗点的离散点，所得的解即为局部离散优化解X^∗。当目标函数为凸函数、约束集合为凸集时，此点也是全域的约束离散优化解。

（2）拟离散法 该法是在求得连续变量优化解X∗后，不是用简单的圆整方法来寻优，而是在X∗点附近按一定方法进行搜索来求得优化离散解。该法虽比前述圆整法前进了一步，但因仍是在连续变量优化解附近邻域进行搜索，往往也不可能取得正确的离散优化解。

1）交替查点法（Luns法）。该法适用于全整数变量优化问题，其优化离散解的搜索方法为：

①先按连续变量求得优化解X^∗，并将它圆整到满足约束条件的整数解上。

②依次将每个圆整后的优化分量[x_i^∗]（i=1，…，n）加1，检查该点是否为可行点，然后仅保留目标函数值为最小的x_i点，重复此过程，直到可行的x_i不再增大为止。

③将一个分量加1，其余n-1个分量依次减l，如将x₁增加x₁+1，再将x₂减到x_2-1，但暂不做代换。继续此循环，将x₃减到x₃-1，也暂不做代换，直到继续循环到x_n为止。最后选择目标函数值最小的点去替换旧点，再依次增大x₂，x₃，…，直到x_n，重复上述循环。最终比较目标函数值的大小，找到优化解，即认为它是该问题的整数优化解。

2）离散分量取整，连续分量优化法（Pappas法）。

①该法是针对混合离散变量问题（即变量中既含有离散分量，也含有连续分量）提出来的。其步骤为：

a.先将连续变量优化解X^∗圆整到最近的一个离散点[X^∗]上。

b.将[X^∗]的离散分量固定，对其余的连续分量进行优化。

c.若得到的新优化点可行，且满足收敛准则，则输出优化结果，结束。

d.否则，把离散分量移到X^∗邻近的其他离散点上，再对连续分量优化，即转到第b步。如此重复，直到X^∗附近离散点全部轮换到为止。

该法实际上只能是从上述几个方案中选出一个较好的可行解作为近似优化解。由于离散变量移动后得到的离散点可能已在可行域之外，故要求连续变量所用优化程序应选择其始点可以是外点的一种算法。上述算法可适用于设计变量较多但连续变量显著多于离散变量的情形，且其计算工作量增加不大。

②对离散变量较多，而变量维数又较低（少于6）的混合离散变量问题，Pappas又提出了另一种算法。其步骤为：

a.求出连续变量优化解X∗，取整到最靠近X^∗的离散值上。(www.xing528.com)

b.令变量的灵敏度为S_i，它是目标函数的增量与自变量增量的比值，即它反映了变量对目标函数的影响程度。计算各离散变量的灵敏度S_i，并将离散变量按灵敏度从大到小的顺序排列：x₁，x₂，…，x_k，1≤k≤n。

c.先对灵敏度最小的离散变量x_k做离散一维搜索，并使其他的离散变量x₁，x₂，…，x_k-1固定不变。每当搜索到一个较好的离散点时，便需要对所有连续变量优化一次。然后，再对x_k-1做一维离散搜索，此时将其余的离散变量x₁，x₂，…，x_k-2保持不变，但对分量x_k还要再做一次搜索。找到好的离散点后仍需对所有连续变量再次优化，如此重复，直到x₁为止。

d.由上述第c步所得终点，重新计算灵敏度并进行排列。若与第b步结果相近，则停止计算，其终点即为优化解。否则，若两者相差较大，则转第c步继续搜索。该法是采用连续变量优化程序对初始点是外点的一种算法。

拟离散法是目前求解离散变量优化的一种常用方法，但这类算法都是基于离散优化解一定在连续优化解附近这样一种观点之上，而实际情况又不一定是这样的，而且这类算法工作量较大，因此具有一定局限性。

（3）离散惩罚函数法 若将设计变量的离散性视为对该变量的一种约束条件，则可用连续变量的优化方法来计离散变量问题的优化。按此思想可以Lagrange乘子法或SUMT法等连续变量优化方法为基石做些变换后，再用来求解离散变量的优化问题。由于有些方法只适用于凸函数或可分离函数等特殊情况，不具有普遍性，因此不作介绍。下面介绍一种离散惩罚函数法。

1）构造一个具有下列性质的离散惩罚函数项Q_k（x^D）

式中，R^D为设计空间离散点的集合。

Marcal定义离散惩罚函数项为

式中，x_ij为第j个离散变量的坐标；z_ij是该变量允许取的第j个离散值。乘积项可保证求和式中的每一项在变量趋于离散值时为零。上式所定义的函数形式简洁，但此函数值变化范围较大，计算时不易控制。

Gisvold定义了另一种形式的离散惩罚函数项为

式中，；x_imin≤x_i≤x_imax。

其中，x_i为x_imin和x_imax之间任一点坐标，x_imin和x_imax是两个相邻的离散值。离散惩罚函数项Q_K（X^D）是一对称的规范化的函数，如图3-35所示。上式中的每一项的最大值为1，而且对于所有β_k≥1的情形，在离散值之间的范围内，函数的一阶导数是连续的。

2）将离散惩罚函数项Q_K（X^D）加到内点法SUMT的惩罚项中，可得离散惩罚函数。其中，离散惩罚函数项

图3-35 离散惩罚函数项

式中，f（X）为原目标函数；γ_k为参数（或称罚因子）；g_u（X）为不等式约束条件；S_k为离散项罚因子。γ_k＞γ_k+1而S_k＜S_k+1，当K→∞时即有γ_k→0，此时

min{ϕ（X，γ，S）}→minf（X）

g_u（X）≥0 （u=1，2，…，m）

Q_K（X^D）→0

2.离散变量的分支定界法

离散变量的分支定界法是一种解线性整数规划问题的有效方法。O.K.Gupta和A.Ravindran将该方法的原理推广到解非线性离散变量问题中，取得了较好效果。

此法与线性整数规划的分支定界法类似，其步骤如下：

1）设所讨论问题为求极小化的问题，先求出原问题不计整数或离散约束的非线性问题的连续变量解。如所得解的各个分量正好是整数，则它是该问题的离散优化解，但这种机会较少。否则，其中至少有一个变量为非整数值或非离散值，则转下一步。

2）对非整数变量，以a_i的值为例，可将它分解为整数部分[a_i]和小数部分f_i，即

a_i=[a_i]+f_i，0＜f_i＜1

3）构造两个子问题：上界约束，x_i≤[a_i]；下界约束，x_i≥[a_i]+1，对离散变量，若其离散值集合为q_i1，q_i2，…，q_il，则对于分支x_i必定存在一个下标j（1≤j≤l），使

q_ij≤x_i≤qij+1

因而应分别构造以x_i≤q_ij为上界约束子问题和以x_i≥q_i1+1为下界约束子问题。

4）将上述两个子问题按连续变量非线性问题求优化解。

5）重复上述过程，不断分支，并求得分支产生的子问题的优化解，直至求得一个离散解为止。

6）在上述求解过程中，每个节点最多能分出两个新的节点。当取一个可行整数解时，如果其目标函数值小于当前目标函数值的上界值，则可将该值作为目标函数新的上界。

7）当下列情况出现时，则认为相应的节点以及它以后的节点已考查清楚：①所得连续变量为整数可行解，且连续变量问题解的目标函数值比当前的目标函数值的上界值大；②连续变量解为不可行解。

8）当所有节点都考查清楚后，寻优工作结束，此时最好的整数解或离散解就是该问题的离散优化解。

此法的计算时间与所解问题的变量数和约束数的多少密切相关。要使这一方法能有好的计算结果，必须要有一种有效的可靠的解非线性规划问题的方法及待查分支节点信息的存储方法。

3.离散变量型普通网格法

离散变量型普通网格法就是以一定的变量增量为间隔，把设计空间划分为若干个网格，计算在域内的每个网格节点上的目标函数值，比较其大小，再以目标函数值最小的节点为中心，在其附近空间划分更小的网格，再计算在域内各节点上的目标函数值。重复进行下去，直到网格小到满足精度为止。此法对低维变量较有效，对多维变量因其要计算的网格节点数目成指数幂增加，故很少用它。为提高网格搜索效率，通常可先把设计空间划分为较稀疏的网格，如先按50个离散增量划分网格。找到最好点后，再在该点附近空间以10个离散增量为间隔划分网格，在这个范围缩小，但密度增大的网格空间中进一步搜索最好的节点。如此重复，直至网格节点的密度与离散点的密度相等，即按1个离散增量划分网格节点为止，这时将搜索到的最好点作为离散优化点。