离散变量组合型算法及其程序—MDCP

D0I:10.13374/j.issn1001-053x.1987.04.011 北京钢铁学院学报 第9卷第4期 Journal of Beijing University Vol,9 No.4 1987年10月 of Iron and Steel Technology Oct.1987 离散变量组合型算法及其程序一MDCP 陈立周 孙成宪李献人 (机械设计教研室) 捕要 本文介绍一种新的混合离散变量优化方法及通用程序，该程序适合于求解含 有整型，离散型和迩续型变量的最优化问题，能给出符合工程要求的规格化最优 解。 本程序经用30个工程设计和数学问题的考核与评定，证明这种具有多功能的 组合型算法和程序，其解题的可靠性，若按最优解的目标函数值的精度在10~以 下统计，达到100%。 文中还简介了本程序在两个工程设计问题中的应用， 关键词：有效目标函数，离散复合形，离散搜素，组合型 A Composite Algorithm and Program-MDCP for Mixed Discrete Variable Chen Lizhou Sun Chengxian Li Xianran Abstract An new optimimzation algorithm and program of mixed discrete variables are described in this paper.This program applied to solve the optimal problems that involves all or some discrete,integer and conti- nuous variables,and give normalized optimal solution in keeping with engineering requirements. This algorithm and program has stood the test of 30 problems of engineering design and mathematics.Tne results indicate that the com- 1986-10~18收稿 ·73

第 卷第 期 年 月 北 京 钢 铁 学 院 学 报 。 ， 。 离散变量组合型算法及其程序一 陈立周 孙成宪 李献人 机械设计教研室 卜 摘 要 本文介绍 一种新的混合 离散变量优化方法及通用程序 该程序适合于求解含 有整型 离散型和 连 续型变量的最优化问题 ， 能给出符合工程要求的规格化最优 解 。 本程序经用 个工程设计和 数学问题的考核与评定 ， 证明这种具有多功能的 组合型算法和 程序 ， 其解题的可靠性 ， 若按 最优解的 目标函数值的精度在 。 ， 以 下统计 ， 达到 书 。 文中还简介了本程序在两个工程设计问题中的应用 。 关镇词 有效 目标函数 ， 离散复合形 ， 离散搜索 ， 组合型 脚 一五 之 ” ， ” ， ， 一 ，以 一 一 收稿 DOI ：10．13374／j ．issn1001－053x．1987．04．011

posite algorithm and program have,with some of different reseach fun- ction in superior both in reliabilty and efficiency.The reliablity of soultion is 100%according to accuracy under 0.001 of objective function vaule。 Two examples used in mechanical engieering are given. Key words:efficient objective function,discrete complex,discrete search,composite method 引 言 在工程规划与设计、可靠性工程、系统工程和管理科学等中，普遍存在着含有整 型、离散型和连续变量的最优化问题。对这类问题应用一般的最优化方法求解，使其变量 符合标准、设计规范、以及生产与工艺要求会遇到许多麻烦，而且有时会造成它是非可 行解或得不到真正离散最优解，还有工程中的一类问题根本不允许采用连续变量方法求 离散解。为了克服这种困难，迫切需要有一种能求解这类问题的约束非线性混合离散变 量的优化方法。 混合离散组合型算法及程序MDCP是一种适合于求解上述问题的通用算法和程序。 它是以离散复合形为基础，利用有效目标函数处理约束，具有离散变量搜索策略，兼备 有多种功能（如线性和非线性加速、重新启动、离散复合形重构、贴边技术、领域查点 等)的所谓组合型算法。所以这样构造，理论与实践业已表明，对于混合离散变量问 题，任何单一的算法都不可能适应千差万别的工程实际问题的模型，只有把多种搜索功 能与技巧组合在一起，使在解题过程中，除了算法自身能根据计算进程自动地调换各种 搜索功能外，用户还可以根据计算中输出的信息，人工干预，改变搜索路线，以提高求 得问题最优解的可常率。 本算法和程序对实际问题具有很强的适应性和很高的求解可靠性。 1算法原理与通用程序MDCP 本程序适用于求解如下形式的约束非线性优化问题 minf(x)x=(x,xc)∈{RD×Rc} } (1) 5.t.g1（x)≤0i=1,2,ym 其中xD=(×,x2,.,x,)∈RP,R为p维离散空间，xC=(xt,xr+,…,x)∈ Rc,Rc为(n-p)维连续空间，n为设计变量个数；为整型和离散型变量个数，m为 不等式约束条件个数。 当x=x,即为全连续变量问题，当x=x,即为金离散变量问题，否则，即为混 合变量问题。在式(1)中，本算法对函数f(x)、g:(x)(i=1,2,,m)无 特殊要求，只要是可算的非线性函数均能适用。 当问题(1)中存在等式约束函数h;(x)=0(j=1,2,,N)时，均用 74

“ 。 ‘ ， 。 ’ ， 一 “ ， “ “ 贝 一 。 ， 引 言 在工程规划与设计 、 可靠性工程 、 系 统工 程 和管理科 学 等 中 ， 普遍存在 着 含 有 整 型 、 离散型 和连续变量的最优化问题 。 对这 类问题 应用 一般的最优 化方法求 解 ， 使其变量 符合标堆 、 设计规范 、 以及生 产与工 艺要求 会遇 到 许多麻烦 ， 而 且有时会造 成它是非可 行 解或得不 到真正 离散最优 解， 还 有工 程 中的一 类问题 根本不 允许采用连续变量方法求 离散解 。 为 了克服这种困难 ， 迫切需要 有一种能求 解这 类问题 的约束非线性混合离散变 量 的优化方法 。 混合离散组合型算法及程序 是 一种适合于求 解上述 问题 的通用算法 和程序 。 它是 以离散复合形 为基础 ， 利 用 有效 目标函数处理 约 束 ， 具有离散变量搜索策略 ， 兼备 有多种功能 如线 性和非线性加速 、 重新启动 、 离散复合形重 构 、 贴边技术 、 领域查 点 等 的所 谓组 合 型算法 。 所 以这样构造 ， 理论 与实践业已表 明 ， 对于混合离 散 变 量 问 题 ， 任何单一的算法都不可 能适应 千差万别的工 程实际 问题的模型 ， 只 有把多种搜索功 能与技巧组合在一起 ， 使在解题 过程中 ， 除 了算法 自身能根据计算进程 自动地调换各种 搜索功能外 ， 用 户还可以 根据计算 中输 出的信息 ， 人工 干预 ， 改变搜索 路线 ， 以提高求 得问题最优解的可靠率 。 本算法和程序对 实际问题具 有很强的适应性和很 高的求 解可靠性 。 算法原理 与通 用程序 本 程序适 用于求 解如下形 式的约 束非线 性优化问题 】 《 ， 〔 。 。 其 中 ” ， ， ， “ 二、 阴 二 ， … ， 二 ， 〔 ， 为 维离散空 间 二 二 ，十 ， ， 二 ， ， … ， 二 。 〔 “ ， “ 为 ” 一 维连续空 间， 为设 计变量 个数 为整型 和离散型 变量 个数， 为 不等式约束条件个数 。 ， 当 “ ， 即为全连续 变量 问题 当 ” ， 即为全 离 散变量问题 ， 否则 ， 即 为混 合 变量 问题 。 在式 中 ， 本算法对 函数 、 ‘ “ ， ， … ， 无 特殊要求 ， 只要 是 可 卜算 的非线 性函数均能适 用 。 当问题 中存在 等式约 束 函数 二 ， ， … ， 时 ， 均 用

hj(x)≤0和h,(x)≥0两个不等式约束代替，然后转化为求如下问题 N min中(x)=f(x)+r〔h,(x)〕2，x=(x,xe) j1 (2) s.t.9i(x)≤0=1,2，…，m,m+1,…,m+N 其中参数r可近似取为，当初始点x°为已知时 If(x)I r=N (3) 〔h;(x))2 j=1 实践计算表明，这样处理是可行的。 1,1用有效目标函数处理约束问题 设x∈D,D={x/g:(x)≤0，V:},定义有效目标函数 f(x) Ef(x)M+SUM 当x∈D (4) 当x不∈D 式中M为常数，是一个比f(x)值在数量级上大得多的数；SUM是与x点的违反约束量 总和成正比的数，例如取 SUM=∑g:(x) J={i/g:(x)>0,Vi} (5) 这样，当对E∫(x)进行离散一维搜索时，则 无论从可行点和非可行点出发，均会自动使当 Ef(x). 前的搜索点进入D域内。图1所示为一维变量 有效目标函数的示意图。 (x) 1,2初始离散复合形的构成 f(x) 设变量规定有上界值x和下界值x,则取 H6,(x=0 82(x小=0时 离散初始点x满足如下条件 x≤x:°≤x:i=1,2,,n(6) 图】单变量约桌问题有效目标晒数 由此点为基础构造出有NV=(2n+1)个项 Fig.I Effec.ive objec,ive func,ion for 点为多面形体，其顶点的坐标分别取 single variable cons;rainte problom xf1)=3x:° =1,2,…,n (7) i=1,2,…,n,但i≠k影k=1,2,…,n .(8) i=k i=1,2,但i*k;k=1,2n (9) i=k 1.3一维离散搜索 NV个顶点按其有效目标函数值的大小排列，并设： 75

’ 《 和 义 两个不 等式约 束代替 ， 然后转化为求 如下 问题 妞、矛 、少 了、、、夕、 功 〔 人， 〕 么， 二 ， 一 ， ， … ， 拼， ， … ， 其 中参数 可近 似取为 ， 当初 始 点 。 为已知 时 一 〔 一 〕 实践计算表 明 ， 这 样处理 是 可 行的 。 用 有效 目标函数处理约束问题 设 〔 ， 二 ， ， 犷 ， 定义 有效 目标 函数 二， 二 入 当 〔 当 不 〔 式中 为常数 ， 是 一个比 值在数量级上大得多的数 是 与 点的违反约 束量 总和成正 比的数 ， 例如取 名 夕 一 王 夕 ， 犷 这 样 ， 当对 进 行离散一维搜索 时 ， 则 无论 从可 行 点和非可 行 点出发 ， 均会 自动 使 当 前 的 搜索 点进 入 域 内 。 图 所示 为一 维变量 有效 目标函数的示意 图 。 。 初 始离散复合 形的构 成 设 变量 规 定有上 界值 ” 和下界 值 “ ， 则 取 离散初始点 。 满 足 如下 条件 义 份《 。 《 戈 丫 ， ， … ， 由此 点为基础构造 出有 犷 ， 十 个顶 点为多面形 体 ， 其顶 点的坐标分别取 二 矛” 劣 ‘ 。 ‘ 二 口 乌 洲勺侧 ‘ 叫 囚 卜一 一 图 单变量约束 问题有效目标函数 。 。 ‘ ， 。 ‘ ， ， ‘ 川 ， … ， “ “ “ “ 二 “ “ “ 二 二 ， … ， ， 但 特 … ， ， ， 但 沪 ， 二 … ， ” 一 维 离散搜索 厂个 顶点按 其有效 目标函数值的大小 排列 ， 并设

搜索基点xb:max{Ef(x),j=1,2,…,NV} (10) 儿何中心华，好=-工 NV xi=1,2,",m (11) 则可以构造一个有利的搜索方向 S:=（x-x)/△： i=1,2…,n 其新点按下式进行迭代计算 x1=x月+ks:i=1,2,…,n 式中△：为第i个离散变量的离散间隔；k为步长因子，由Ef(x)值的大小而定。若搜索 ks:≤△mi,则一维离散搜索结束。其中△min=min{△：，i}。 1.4重新启动技术 沿S方向对Ef(x)进行一维离散搜索，由于各种因素（如函数f(x)、9(x)的 严重非线性、病态等)的影响，有可能不一定均成功，为此在算法中设计了两种新启动 技术：一是按Ef(x)值由大到小的原则依此取为搜索基点x,二是将2n+1个顶点 均向最好顶点(Ef(x)值最小者)收缩1/3。 1.5离散寻优的终止准则 离散复合形在寻优迭代过程中，各顶点的坐标值发生变化并且向最好点集中。当各 顶点的坐标值不再发生有意义的变化时，复合形运算结束。所谓不再发生有意义的变 化，对离散型变量，就是复合形各顶点的最大坐标值与最小坐标值之差不大于一个离散 间隔△，对连续型变量，就是不大于拟增量ε：（一个很小的量，由使用者根据实际问题 的意义事先给定)。这样，复合形顶点各坐标方向上的差L:值为 L:=0:-b:i=1,2,…,m a:=max{x}j=1,2,",NV} (12) 6i=min {x j=1,2,.,Ny) 与相应的变量增量△：（或e:)比较，当L:≤△：（或e:),i=1,2,,n的个数RW 规定大于某个预先给定的正整数EN时。则离散复合形寻优迭代终止。一般EN可取 1≤EN≤n个。 1,6算法的辅助功能 为了适应函数的非线性，提高计算效率和 Begin 增加求得最优解的可靠性，在MDCP程序中设 Input design's in for mation 置了几种辅助功能：以非线性函数轨线分析为 0,g红 Specific program 基础的线性加速或平方加速；以变量分离为基 General program mathematical model MDCP 础的由子空间到全空间的离散搜索，以领域查 End 点为基础的单位领域反射技术，复合形重构技 Output design's information 术和贴边技术等。 1.7通用优化程序MDCP 图2.MDCP通用程序模块与专用程序间的关系 根据实际工程问题的使用要求，将木算法 Fig.2 MDCP program related of specific 编成通用程序模块MDCP,其关系如图2所示。 progra 76

笼 ‘犷 ﹁﹂一气 搜索基 点 ，一，“ “ 几何中心 “ 戈 呀 一 ， 含 ， … ， 犷 戈 ， ， ， 二 ， 则可以构造一个有利的搜索方向 呀一 兮 △ ， … ，， 其新点按下 式进 行迭代计算 兮 ， ， … ， 式 中△ 为第 个离散变量的离散间隔， 为步长因子 ， 由 八 值的大小而 定 。 若搜索 肠 《 △二 。 ， 则一维离散搜索结 束 。 其 中△ 。 △ ， 试 。 皿新启动技术 沿 方向对 了 进 行 一维离散搜索 ， 由于各 种因素 如函数 、 的 严重 非 线性 、 病态 等 的影响 ， 有可 能不一 定均 成功 ， 为此在算法 中设计 了两种新启动 技术 一 是 按 值 由大到小的 原则 依此取为搜索基 点 “ 二是 将 个顶 点 均 向最好顶 点 值最小者 收缩 。 。 离散导优的终止 准则 离散复合形在寻优迭 代 过程 中 ， 各 顶点的坐标值发生 变化并且 向最好 点集中 。 当各 顶点的坐标值不再发生 有意义 的变化时 ， 复合形运算结束 。 所谓不再发生 有 意 义 的 变 化 ， 对离散型变量 ， 就是复合形各顶点的最大坐标值与最小坐标值之差 不大于一 个离散 间隔△ ， 对连续 型变量 ， 就是不大于拟增量。 一 个很小 的量 ， 由使用者根据实际问 题 的意义 事先给定 。 这 样 ， 复合形 顶点各坐标方向上 的差 ‘ 值为 、 扩 ，二 ‘行 了‘ 、 一 ， ， 、夕，卫吸了、 … ， ‘ 王 ， ， … ， 厂 ， ， … ， 犷 与相应的变量 增量 △ 或。 比较 ， 当 《 △ 或。 ， ， ， 规 定大于 某个预先 给 定的正 整数 时 。 则离散复合形 寻优迭代终止 。 《 个 。 。 算法的辅助功能 … ， 的个数 一 般 可 取 为 了适 应 函数的非线性 ， 提 高计算效率 和 增加求得最优解的可靠性 ， 在 程序中设 置 了几 种辅 助功能 以非线性函 数轨线分 析 为 基础 的线性加速或平方加速 以 变量分 离为基 础 的 由子空 间到全空 间的离散搜索 ， 以领 域 查 点为基础的单位领域反射技术， 复合 形重 构技 术 和贴边技术等 。 通 用优化程序 根据实际工 程 问题 的 使用 要求 ， 将本算法 编 成通用 程序模块 ， 其关系 如 图 所示 。 ‘ 物 即 ， 叼 枷、 五 图 ， 通用程序模块与专用程序间的关系 尹 ‘ 一 了 。 尸 川

图中MDCP程序模块不因使用要求不同而变。专用部分的程序模块需要根据使用要求 而设计，它完成求解问题的分析计算。两个模块之间通过变量x值和函数f(x)与g(x) 值来交换信息，实现寻优运算。专用部分模块须按接口要求编写，将它嵌入通用部分， 即使整个程序成为特定问题的优化计算专用程序。 在研制MDCP程序时，利用了离散值域矩阵贮存技术和非均匀与均匀空间映射技 术，使得复杂的多种多样离散空间转化为简单的均匀离散空间，保证了各种离散搜索技术 与辅助功能得到可靠地实现，同时使得程序结构简化、紧凑，大大提高了程序的使用稳 定性、可靠性和计算效率。实际使用表明，本程序用于求解n≤30和m≤80的工程优化 问题是很成功的。 2,程序的考核与评定 目前，关于对离散变量程序的考核评定尚无统一的规范，但多数服从这样两条原 则：一是考题的选择需要包括典型的数学问题和实际的工程问题，使之能够反映数学模 型的一定难度和函数的各种性态，二是对考题的计算结果需作出有关指标的统计分析， 如解题的可靠率、计算效率（由于所使用的机型不同，所以目前多数用目标函数与约束函 数的分析次数多少来评定)。为此共选用了30个考核题，其中典型数学问题4个，工程问题 26个。在各类问题中，离散设计变量由2个至30个，约束函数由1个至44个。用MDCP程 序对此30个问题的计算结果表明，若按取得正确的离散最优解统计，则其解题的可靠率 为90%，若按最优解的目标函数值在精度10-以下作为解题成功，则其可靠率为100%。 而计算效率普遍高于目前国外几种算法的1~3倍。表明这项研究结果是成功的。 图3中给出了其中一个数学问题，当其变量取不同的离散间隔△：时收敛速度的比较 曲线。表明一个最优化问题，若按工艺要求将其变量拟离散化，可以大大提高计算效率， 并给出符合生产实际要求的规格参化数值。同时离散间隔值△：愈大，收敛速度愈快。 图4给出了关于计算图3中考题时调用和不调用加速措施功能的收敛结果，若不调 用二次加速功能，则取不到最优解。 400 min f(x=)100(x子-X1-*22 400 4,t,-100x00a1,2 Call X=(0.9,0.8T4i=0,1 100 100 x0,02 FUNa279 loiFUN No oall X=C1.0,1.0)Aim0.1 10.00011936 fx=0.0 FUN=686 20.0016I■ 50 .0198 80 01 十29 1.0 十29 40 X1.0,1.00r 40 fx=0.0 Alternative number 400 1000 18002000 200 400600 800 FUN FUN 图3不同离散间隔Δ值时的收敛速度 图4调用和不调用二次加速功能的乩较 Fig.3 Convergeney speed for different Fig.4 Comparison for whether call or not interval value Ai of discrete variable function of quadrstic aceelartion 77

图中 程序模块不 因使用要求不 同而 变 。 专用部分的程序模块需要根据使 用 要 求 而设计 ， 它完成求 解问题的分析计算 。 两个模块之 间通 过变量 值和函数 ‘ 与 值来交换信息 ， 实现寻优运算 。 专用 部分模块须按接 口 要求编写 ， 将它 嵌 入通用部分 ， 即使整个程序成为特定问题 的优化计算专用程序 。 在 研制 程序时 ， 利用 了离散值域矩阵贮存技术和非均 匀与均 匀空间 映 射 技 术 ， 使得复杂的多种 多样离散空 间转化为简单的均 匀 离散空间 ， 保证 了各 种离散搜索技术 与辅助功能得到可靠地实现 ， 同时使得程序结构 简化 、 紧凑 ， 大大提 高了程 序的使用稳 定性 、 可靠性 和计算效率 。 实际使用表明 ， 本程 序用于求 解。 成 和 《 的工程 优 化 问题是 很成功 的 。 、 程序的考核与评定 目前 ， 关 于对 离散变量程序的考核评 定尚无统 一的 规范 ， 但多数服从这 样 两 条 原 则 一是考题 的选择需要 包括典型的数学 问题 和实际 的工 程 问题 ， 使之能够反映数学模 型的一 定难度 和函数的各种性态， 二是对考题 的计算结果需作 出有关指标的统计分析 ， 如解题 的可靠率 、 计算效率 由于所 使用 的机型不 同 ， 所 以 目前多数用 目标 函数与约 束函 数的分析次数多少来评 定 。 为此共选 用 了 个考核题 ， 其中典型数学问题 个 ， 工程问题 个 。 在各 类问题 中 ， 离散设计 变量 由 个至 个 ， 约 束 函数 由 个至 个 。 用 程 序对此 个问题的计算结果表明 ， 若按取得正确 的离散最优解统计 ， 则其解题的可靠率 为 ， 若按最优解的 目标函数值在精度 。 以下 作为解题成功 ，则 其可靠率为 。 而计算效率普遍高于 目前国外几 种算法的 倍 。 表明这 项研究结果是 成功 的 。 图 中给 出了其中一 个数学 问题 ， 当其变量取不 同的离散间隔△、 时收敛速度 的比较 曲线 。 表 明一 个最优化问题 ，若按工 艺要求将其变量拟离散化 ， 可以 大大 提高计算效率 ， 并给 出符 合生 产实际要求 的规格参化数值 。 同时离散间隔值△ 愈大 ， 收敛速度愈快 。 图 给 出了关 于计算图 中考题 时调 用 和不调用 加速措施功能的收 敛结果 ， 若不调 用 二次加速功 能 ， 则 取不到最优解 。 产 ” · 竹 梦 三 作吃一 ， 《 二 坦 口冲二 日 甘 胜昌 ﹄ ，一 ，一 竺 ，︸ ，︸一 、咭 ﹄︸八， ﹄叫︸、 ‘，翻、 ‘ ︺一 、已 ， 妇﹀ 飞鱿 孔 邢 比 。 。 。 五 。 王 图 不同离散 间隔吞值时 的 收敛速度 八巨 图 调用和不调用二次加速功能 的 比 较 ， 一 ‘ 一 七