优化设计建模与算法选择的并行处理系统

0I:10.13374/.j.1ssn1001053x.1997.02.013 第19卷第2期 北京科技大学学报 Vol.19 No.2 1997年4月 Journal of University of Science and Technology Beijing Apr.1997 优化设计建模与算法选择的并行处理系统* 翁海珊吴加忠 陈立周 北京科技大学机械工程学院，北京100083 摘要介绍了优化设计建模和算法选择两个专家系统及其并行处理技术，以及各子系统所采用 的自律分散，并行设计和共享信息，协调工作的控制策略及其在工程优化设计的智能化和自动化 中所起的作用 关键词优化建模，算法选择，并行处理，专家系统 中图分类号TP391.72,TH122 为使优化设计能适应设计自动化的要求，作者研制了个基于知识工程的智能优化设计 软件系统IOPS山，该系统集成了连续、离散和随机变量的14种优化算法并具有诊断型、设计 型、决策型等专家系统，利用知识工程的方法进行开式直线链和闭式多重循环链2种驱动控 制，实现了优化设计过程的自动化. 优化设计建模专家系统和优化算法选择专家系统是IOPS系统中的2个关键的子系统， 它们以优化设计专家的经验和知识为基础，并利用并行工程技术和协调处理的驱动策略简化 了信息处理，提高了优化过程的自动化程度. 1优化设计建模专家系统 为使输人的设计知识表达式能符合OPS系统的要求，并能为算法选择系统提供有用的 信息，建立了一个优化设计建模专家系统.如图1所示.它由4个子系统组成，即模型输人系 统、模型诊断系统、模型识别系统和模型转换系统， 1.1模型输入系统 主要是为不熟悉优化程序和算法语言的工程技术人员提供了原始的设计信息输人环境， 该系统是以人机交互形式，按屏幕提示逐项输入，然后系统便自动生成优化设计数学模型的 原型. 1.2模型诊断系统 系统具有对数学模型作语法检错和合理性鉴别2种功能， ()语法检错：本系统设计了一个递归下降式语法分析器，它用一系列彼此递归调用的 1996-09-03收稿 第一作者女50岁副教授 ◆国家自然科学基金资助项目

第 卷 第 期 年 月 北 京 科 技 大 学 学 报 价 、 尸 优化设计建模 与算法 选择 的并行处理系统 翁海珊 吴加 忠 陈 立 周 北 京 科技 大学 机 械 工 程 学 院 ， 北 京 摘要 介绍 了优化设计建模 和 算法 选 择 两 个 专家系 统 及 其并 行 处理 技术 ， 以 及 各 子 系 统 所采用 的 自律分散 、 并 行 设计 和 共 享信息 、 协调 工 作 的控 制策略及 其在 工 程 优 化设计 的 智能 化和 自动 化 中所起 的作用 关键词 优化建模 ， 算法 选 择 ， 并 行处理 ， 专家系统 中 图分类号 ， 为使优 化设 计能适 应设计 自动 化 的要 求 ， 作 者研 制 了 一个基 于 知 识工程 的智能优 化设计 软件 系 统 ， ， 该 系 统集 成 了 连 续 、 离 散 和 随机 变 量 的 种 优 化 算 法 并具 有 诊 断 型 、 设计 型 、 决 策 型 等 专家 系 统 ， 利 用 知 识 工 程 的方 法 进 行 开 式 直 线 链 和 闭式 多 重循 环链 种 驱 动控 制 ， 实 现 了 优 化设 计过程 的 自动化 优 化设计 建模 专家 系 统 和 优 化 算法 选 择 专家 系 统是 系 统 中的 个 关 键 的 子 系统 它们 以 优化设 计 专家 的经验 和 知 识为基 础 ， 并 利 用 并行 工 程技 术 和协调处理 的驱 动策 略 简化 了信息处理 ， 提高 了优 化过程 的 自动化程 度 优化设计建模专家 系统 为使输人 的设 计知 识表 达 式 能符 合 系 统 的要 求 ， 并 能 为算 法 选 择 系 统提供有 用 的 信息 ， 建 立 了 一 个 优 化 设计建 模 专家 系 统 如 图 所 示 它 由 个 子 系 统组 成 ， 即模 型 输入 系 统 、 模 型诊 断系 统 、 模 型 识别 系 统和 模 型转换 系 统 模型输入 系统 主要 是 为不 熟 悉 优化 程序 和 算法语 言 的工 程 技术 人 员提供 了原始 的设计信息输 人 环境 该 系 统是 以 人 机 交 互 形 式 ， 按 屏 幕提 示 逐 项 输 人 ， 然 后 系 统便 自动 生 成 优 化 设计 数 学 模 型 的 原型 模型诊断 系统 系 统具 有 对数学 模 型作语法 检 错 和 合理性 鉴别 种功 能 语 法 检 错 本 系 统 设计 了 一 个 递 归 下 降式 语 法 分 析器 ， 它 用 一 系 列 彼 此 递 归调 用 的 一 一 收稿 第 一 作 者 女 岁 副教授 国 家 自然科 学 基金 资助项 目 DOI ：10．13374／j ．issn1001－53x．1997．02．013

Vol.19 No.2 翁海珊等：优化设计建模与算法选择的并行处理系统 ·179· 函数对模型的语法错误进行诊断和处理.这些自定义的特定函数及其功能见表1， 表1自定义函数及其功能（部分） 函数名 函数符号 函数功能 截取函数1 get-token() 截取分解表达式中需分析的符号 y get-exp() 截取分解括号()内的数学表示式 识别函数1 level 2() 识别处理运算符号 2 level 5() 识别处理常量、变量和函数 3 level 6() 识别处理括号的匹配 检错函数1 find-num() 检查常量的格式 2 find-vart） 检查变量的格式 3 find-fun(） 检查函数的格式 分流函数 primitive() 分流需分析的符号 转向函数 long-jmp() 执行非局部转向，返回set-jmp() 接受函数 set-jmp() 定义假定安全位置，以接受long-jmp() 示错函数 set-em( 显示出错误信息 返回函数 put-back() 将截取的符号送回输人信息流中 其工作步骤为：①将表达式分解为逐个独立的逻辑符号；②识别各类逻辑符号， 转换为内部记号格式后作分流处理；③分别检查各类符号是否符合格式要求；④对明显由误 操作所引起的错误作自动转换 处理，对需用户参与修正的错 模型输人系统 误，则显示错误信息；⑤将处理 完的逻辑符号逐一返回信息流. 模 有错误吗？ (2)合理性鉴别：格式规范 型 N 化、语法无错的数学模型若还存 诊 在一些不合理因素，也将使优化 断 合理吗？ 设计得不到最优解，这些不合理 因素主要有2类：第1类不合理 N 模 是单目标吗？ 多目标决策专家系统 因素是指一些显式不合理现象， 型 如多余的设计变量，等式约束数 识 信息辨别 大于或等于设计空间维数等.这 别 类不合理性只需知识库中经验 特征提取 算法选择专家系统 类的浅知识（因果关系类的知 模型转换系统 识)，用产生式规则即可诊断.第 2类不合理因素是指数学模型本 数学模型 身的结构.如冗余约束、矛盾约 束、可行域为空集等.这类不合 图1优化设计建模专家系统 理性需利用知识库中的一些基 本定义和公理性的深知识，并对数学模型进行分析计算才能作出诊断

翁海珊等 优化 设计建模 与算法 选择 的并行处理 系 统 函 数 对模 型 的语法 错 误进 行 诊 断和处理 这 些 自定 义 的特定 函 数及 其功 能 见 表 表 自定义 函数及其功能 部分 函 数名 函 数符号 函 数功能 截取 函数 识别 函数 检错 函数 分 流 函 数 转 向函数 接受 函 数 示错函数 返 回 函数 试 一 一 叫 而 一 一 试 一 试 截取分解表达式 中需分析的符号 截取分解括 号 内的数学表示 式 识别处理运算符号 识别 处理 常量 、 变量和 函数 识别处理括 号的匹 配 检查 常量 的格式 检查变量 的格式 检查 函 数的格式 分流需分析的符号 执行 非局 部转 向 、 返 回 试 定义假 定安全位置 ， 以接受 试 显示 出错误信息 将截取 的符号送 回 输入信息流 中 其工 作步 骤 为 ① 将 表 达式分解 为逐 个独 立 的逻辑符号 ② 识 别各类逻辑符号 ， 转换 为 内部 记 号 格 式 后 作分 流 处理 ③ 分 别检查 各 类符 号是 否 符 合格 式要 求 ④ 对 明显 由误 操 作 所 引 起 的 错 误 作 自动 转 换 处 理 ， 对 需 用 户 参 与 修 正 的 错 误 ， 则 显 示 错 误 信 息 ⑤ 将 处 理 完 的逻 辑符 号逐 一返 回信息 流 合 理 性 鉴 别 格 式 规 范 化 、 语法 无 错 的数 学 模 型 若 还 存 在 一 些 不 合理 因 素 ， 也 将 使优 化 设 计 得 不 到 最 优 解 这 些 不 合 理 因 素 主 要 有 类 第 类 不 合 理 因 素是 指 一 些 显 式 不 合 理 现 象 ， 如多余 的设 计 变 量 、 等式 约束 数 大 于 或等 于 设计 空 间维 数 等 这 类 不 合 理 性 只 需 知 识库 中 经 验 类 的 浅 知 识 因 果 关 系 类 的 知 识 ， 用 产生 式规则 即可 诊 断 第 类 不合理 因素是 指 数学模 型 本 身 的 结 构 如 冗 余 约 束 、 矛 盾 约 束 、 可 行 域 为 空 集 等 这 类 不 合 理 性 需 利 用 知 识 库 中 的 一 些 基 模 型输人 系统 多 目标决策专家系统 信息辨别 特征提取 模 型转换系统 数学模型 图 优化设计建模专家系统 本定 义 和公理性 的深 知 一 识 ， 并 对数学模 型进行分析计算才能作出诊 断

·180· 北京科技大学学报 1996年 1.3模型识别系统 主要是从输人的数学模型中辨识有关信息，提取各种特征量.模型识别系统需辨识下列 4类信息： ()是否为单目标模型. (2)设计问题的规模.它取决于设计变量的个数N,随机参数的个数凡，约束函数的个数 N。,设计问题的规模分下列3类： 小规模N≤5和R≤9和N≤7； 中规模N>6或R>10或N>8; 大规模N>20或R,>30或N.>16. (3)设计问题的类型，取决于：①设计变量（或参数）的类型，除连续变量外是否还含有离 散变量或随机变量；②约束的类型，是否有约束，是否含等式约束；③优化问题的类型，是否为 风险设计问题、容差设计问题等. (4)函数的性态.是指目标函数和约束函数的类型分以下几类： 线性函数f()=Ax+b; 二次型函数f()=c+BTx+(1/2)xTAc 低次非线性函数多项式函数的最高次幂小于3时； 高次非线性函数多项式函数的最高次幂大于3时； 超越函数三角函数、反三角函数、指数函数、对数函数等； 需特殊处理函数I因分母有变量等原因可能引起函数值趋于无穷而发散； 需特殊处理函数Ⅱ目标函数中存在含有定义域的项，若约束中未作限制可能使目标函 数无法求值； 一般函数除以上各类函数 以上各类信息辨识后转化为特征量.除第1类作为驱动控制量外，后3类特征量提取后 生成数据文件存于中间数据库，他为其它子系统（例如算法选择专家系统）调用，某些常用特 征量，如设计变量个数N等，则建立全程结构函数，供全局调用， 1.4模型转换系统 主要是将经处理后的数学模型从由C语言编制的程序模块中自动转化为FORTRAN语 言所能接受的语句，并嵌人优化算法程序的有关目标函数子程序和约束函数子程序中，完成 FORTRAN语言和C语言的集成. 2优化算法选择专家系统 2.1决策知识 算法选择系统是一种决策型的专家系统，它所依据的知识有4类：第】类是根据算法本 身特点和构造原理所决定的适用范围、解决问题的能力等一些算法功能性知识；第2类是根 据几十个模型考核后得出统计规律，如成功率、可靠性、稳定性、效率、操作简易性等算法性能

· · 北 京 科 技 大 学 学 报 年 模型 识别 系统 主要 是 从输 人 的数学模 型 中辨 识 有 关信 息 ， 提 取 各 种 特 征量 模 型识 别 系 统需 辨 识下 列 类信 息 是 否 为单 目标模 型 设计 问题 的规模 · 它 取决 于设计变 量 的个数 从 随机 参数 的个数 凡 ， 约束函 数 的个数 设计 问题 的规模分 下 列 类 小规模 ‘ 和 凡 ‘ 和 ‘ 中规模 或 凡 或 大规模 或 凡 或 · 设计 问题 的类 型 取 决 于 ① 设计 变 量 或 参数 的类 型 ， 除 连 续 变 量外是否 还 含 有 离 散变量 或 随机 变量 ② 约束的类 型 ， 是 否 有 约束 ， 是 否 含等式 约束 ③优化 问题 的类型 ， 是否 为 风 险设计 问题 、 容 差 设计 问题等 函数 的性 态 是 指 目标 函数和 约束 函数的类型 分 以下 几类 线性 函数 入 月 二 次型 函 数 。 十 刀 权 低 次非线性 函数 多 项 式 函 数 的最 高次幂 小 于 时 高次非 线性 函 数 多 项 式 函数 的最 高次幂 大 于 时 超越 函 数 三 角 函 数 、 反 三角 函 数 、 指 数 函 数 、 对数 函数等 需 特殊处理 函数 因分母 有 变量 等原 因可 能 引起 函数值趋 于 无 穷而 发 散 需 特殊处理 函 数 目标 函数 中存 在 含 有 定 义域 的项 ， 若约束 中未 作 限制可 能使 目标 函 数无法 求值 一 般 函数 除 以上各类 函数 以 上 各类 信息 辨 识 后 转化 为特 征 量 除第 类 作 为驱 动控 制量 外 ， 后 类 特 征量 提 取 后 生 成 数据 文件 存 于 中 间数据 库 ， 他 为其它 子 系 统 例如算法 选 择 专家 系 统 调 用 某 些 常用特 征量 ， 如设计变量个数 等 ， 则建 立 全程结 构 函 数 ， 供全 局 调 用 模型转换 系统 主要 是 将经处理 后 的数学模 型 从 由 语 言编 制 的程 序模块 中 自动转 化 为 语 言所 能接 受 的语句 ， 并 嵌人 优化算法 程 序 的有 关 目标 函数子程 序和 约束 函数子 程 序 中 ， 完 成 语言和 语言 的集成 优化 算法选择专家 系统 决策知 识 算法 选 择 系 统 是 一 种 决 策 型 的 专家 系 统 ， 它 所 依 据 的知 识 有 类 第 类 是 根 据 算法 本 身特 点 和 构造 原理 所 决 定 的适 用 范 围 、 解 决 问题 的能 力等 一 些 算 法 功 能性 知识 第 类 是 根 据几 十个模 型 考核后 得 出 统计规律 ， 如成 功率 、 可 靠性 、 稳 定性 、 效率 、 操作 简易性 等算法性 能

Vol.19 No.2 翁海珊等：优化设计建模与算法选择的并行处理系统 ·181· 性知识，这2类知识均以框架结构的形式存贮于知识库中的事实库；第3类是优化设计领域 的专家们根据长期积累的算法选择经验，对各算法的评价知识，这类知识以产生式规则存储 于知识库中的规则库；第4类是由优化设计建模系统提供的表达当前数学模型特性的特征 量，这类知识存储于中间数据库， 前3类知识在使用的过程中将不断更新，更新方式有2种：」种是接受专家通过人机界面 提供的信息作导师指导学习，由知识获取机制自动转换知识库中的知识；另1种是接受自学 习系统提供的信息作条件反射学习，这是一种经验积累式学习.后】种动态数据库中记录着 历次优化设计的数据，针对不同特征量的数学模型选择不同算法、不同功能时，结论是失败或 成功、运行解是优还是劣都作了统计.当统计数据量变到一定程度，并超过预定阈值时，则发 生质变形成有效经验.自学习系统据此经验自动修改知识库中的知识.知识库的知识更新将 使以后的推理更合理 算法选择系统与周边系统间的信息传输关系见图2 优化设 优化算法选择专家系统 计计算 选择算法 优化 优化设计算法 雅理机 知识库 改 算法 程序库EOPB 算法 算法功能 选择 算法性能 事实库 专 优化模 算法选择 家 数学 模型 型建立 间 算法功 规则库 据 能选择 系统 数据 数据文 参数选择 增 文件 件建立 规则 改 优化解 动态数据库 自学习专家系统 图2算法选择系统系周边系统的信息传输 2.2推理方式 算法选择的推理机采用的控 COEM SVMT MDCP SMOD SAOD SQOD 制方式一般为向前推理，即数据驱 目标（算法）节点○ 向 动的方式，见图3.它是以数学模型 前 算法功能节点 的特性作为已知事实、以算法的功 推 算法性能节点 推 理 能框架和性能框架为中间推理层 事实（模型特征） 理 的节点，以算法为推理的目标，正 向寻求适用于当前数学模型的算 图3算法推理的控制方式 法及其功能.只有在某些特殊的情况下，即用户提供的信息不全（如用户无法确定可行初始 解)，或用户提出某些特定要求（如必须是严格可行解）时，采用向后推理，即目标驱动的方式· 这时，根据具体情况，系统排除大部分目标（即算法），选择假设可满足要求的目标（算法），然 后向下位驱动，经中间节点推理验证是否满足当前数学模型的有关特性，以证明假定算法的

翁海珊等 优化 设计建模 与算法 选择的并行处理系统 性知 识 ， 这 类 知 识 均 以 框 架 结 构 的形 式存贮于 知 识 库 中的事 实 库 第 类 是 优化设计 领 域 的专家们 根 据 长 期 积 累 的算法 选 择经 验 ， 对各算 法 的评 价 知 识 ， 这类 知 识 以 产 生 式规则 存 储 于 知 识 库 中 的规则 库 第 类 是 由优 化设 计 建 模 系 统 提 供 的 表 达 当前 数 学 模 型 特性 的特 征 量 ， 这类 知识存储于 中间数据库 前 类 知识 在使用 的过 程 中将 不 断更新 ， 更新 方 式有 种 种 是 接受 专家通 过人机界 面 提供 的 信息作 导 师指 导学 习 ， 由知 识 获取 机 制 自动 转换 知识 库 中 的知 识 另 种 是 接 受 自学 习 系 统提 供 的信 息作条件 反 射学 习 ， 这 是 一种 经 验 积累 式 学 习 后 种 动 态数据库 中记 录 着 历次优化设计 的数据 ， 针 对不 同特 征量 的数学模 型 选 择不 同算 法 、 不 同功 能 时 ， 结论是 失 败或 成功 、 运 行解 是 优还 是 劣 都作 了 统计 当统计 数 据量 变 到 一 定 程 度 ， 并 超 过 预定 阑值 时 ， 则 发 生质 变 形 成 有 效 经 验 自学 习 系 统据 此 经 验 自动修 改 知 识 库 中的 知 识 知 识库 的 知 识 更 新将 使 以 后 的推理 更合理 算法 选 择系统 与周 边 系统 间 的信息传输关 系见 图 优化算法选择专家 系统 优化设计算法 择算法 优化 程序库 剪 算法 推理机 园型 叠僵爵 法 专 征 选择 月期法法性选能择 家 优化模 模数型学 型系建统立 算法功 能远拜 数据 数件据建立文 文件 自学习专家系统 图 算法选择系统系周边系统的信息传输 推理方式 算 法 选 择 的 推 理 机 采 用 的 控 制方 式 一 般 为 向前推 理 ， 即数据 驱 动 的方式 ， 见 图 它是 以 数学 模 型 的特性 作 为 已 知 事 实 、 以 算 法 的 功 能 框 架 和 性 能 框 架 为 中 间 推 理 层 的 节 点 ， 以 算 法 为 推 理 的 目标 ， 正 向寻 求 适 用 于 当前 数 学 模 型 的 算 目标 算法 算法功能节点 算法性能节点 事实 模型特毛 前推理向 图 算法推理的控制方式 法 及 其功 能 只 有 在 某 些 特 殊 的情 况 下 ， 即 用 户 提 供 的信 息 不 全 如 用 户 无 法 确 定 可 行 初 始 解 ， 或 用 户提 出某 些 特定 要 求 如必 须是 严 格 可行解 时 ， 采用 向后 推理 ， 即 目标 驱 动 的方 式 这 时 ， 根 据具体情 况 ， 系 统排 除 大部 分 目标 即算法 ， 选 择假 设 可 满 足 要 求 的 目标 算法 ， 然 后 向下 位 驱 动 ， 经 中间节 点 推理 验 证是 否 满足 当前 数学模 型 的有 关特性 ， 以 证 明假 定 算法 的

·182· 北京科技大学学报 1996年 正确性 2.3数据文件的建立 数据文件由2部分组成：一部分为统一格式的公共数据文件：另一部分为各算法专用数 据文件，算法原理不同，算法数据文件不仅格式不同，数据个数也不相同. 数据文件的建立有2种方式：一种为用户输人，另1种是系统自动生成.用户输人时，系 统提供输人环境，屏幕不仅提示要求输入的参数名、参数符号、数据类型（如整型、浮点数等） 和格式，还在用户请求帮助时提供参考值，对输人的数据系统协助查错并提供修改意见，当输 人的全部数据得到再次确认后生成数据文件， 系统自动生成文件时，则由推理机根据系统选定的算法及其功能、性能、数学模型的特征 量及专家经验推算出各参数值，生成数据文件.系统对2种方式生成的文件均自动按 FORTRAN程序要求的格式编辑、存机. 3优化设计中的并行处理技术 上述2个系统在运行中，数学模型和优化算法互相适应、双向选择，各自都提出了许多匹 配要求，也提供了许多特征.因此，信息的处理流已从传统的单列型直线流转换为并列型网络 优化设计建模系统 算法选择系统 横型诊断 模型识别 模型输入 语法检错 合理性鉴别 信息辨别 特征提取 横型转换 算法选择 算法功能选择 数据文件建立 图4(a)单列型直线流程 棋型输入 语法检错 合理性鉴别 模型转换 模型 信息辨别 特征提取 优化算法 算法 算法选择 算法功能选择 数据 序运行模块 数据文件建立 图4(b)并列型网络流程

北 京 科 技 大 学 学 报 年 正 确性 数据文件 的建立 数 据文 件 由 部 分 组 成 一 部 分 为 统 一 格式 的公 共 数 据 文件 另 一 部 分 为各算 法 专用数 据文 件 ， 算 法 原理 不 同 ， 算 法 数 据文 件不仅格式 不 同 ， 数据 个数也 不 相 同 数 据 文 件 的建 立 有 种 方 式 一 种 为 用 户 输 人 ， 另 种 是 系 统 自动生 成 用 户输入 时 ， 系 统提供 输 人 环 境 ， 屏 幕不 仅 提 示 要 求输人 的参数名 、 参数符 号 、 数 据类 型 如 整型 、 浮 点数等 和 格 式 ， 还在 用 户 请求 帮助 时提 供参考值 对输人 的数据系 统协助查 错并提供修 改意 见 ， 当输 人 的全部 数据得 到 再 次 确 认 后 生 成 数据 文件 系 统 自动生成 文件 时 ， 则 由推理 机根据 系 统选定 的算法 及 其功 能 、 性 能 、 数学模型 的特征 量 及 专 家 经 验 推 算 出 各 参 数 值 ， 生 成 数 据 文 件 系 统 对 种 方 式 生 成 的 文 件 均 自动 按 程序要 求 的格 式编 辑 、 存机 优化设计 中的并行处理技术 上述 个 系 统在 运 行 中 ， 数学模 型 和 优化算 法 互相 适应 、 双 向选 择 ， 各 自都提 出了 许多 匹 配要 求 ， 也提供 了许多 特 征 因此 ， 信息 的处理 流 已 从传 统 的单列 型 直线 流转换 为并列 型 网络 优化设计建模系统 算法选择系统 模型诊断 日 模型识别 数据件建立文 合性鉴理别 模型转换 曰川 选择算法 日曰日选择算法功能 目一日 图 单列型直线流程 语法检错 优 模型转换 化 算 法 特征提取 程 序 运 算法选择 行 模 块 算法功能选择 数据文件建立 图 并列型 网络流程