《决策支持系统的自适应建模研究及应用实例分析.pdf》由会员分享，可在线阅读，更多相关《决策支持系统的自适应建模研究及应用实例分析.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 3 卷第 1 期 2 0 0 0年 3月 管理科学学报 J OU P N AL O F MANA GE ME N T 8 C I E N C E S I N C H I NA Vn 1 3No 1 Ma r 2 0 0 0 决策支持系统的自适应建模研究及应用实例分析。一 葛志远，王永 奕晋(清 军 济 香 i 写 磊，北 京1 0 0 0 8 4)C ；摘要：在进行决策的过程中，建立正确的系统模型是解决问题的关键 由于多 方面的原因，有时 要针对研究对象选用适用的模型来进行分析是很 困难的 本文根据遗传算法在程序设计中的 应用，探讨j 基于遗传算法的自 适应建模方法，并对实际应用中自 适应
2、建模的算法存在的问题 提出7改进方法 最后应用 自适应建模方法对全 国的集装箱与外贸数据进行j建模分析，应 用 实例表明自适应建模方法对于解决难以选择合适的模型进行建模分析时是很有效的 关键 词：决策 支 持系 缝；自 适 应 建 模；遗传 算法；二又 树 结 构 墨嘎。分类号：C 9 3 4；文献标识码：A；文章编号：1 0 0 7 9 8 0 7(2 0 0 0)0 1 0 0 7 3 0 6 0 引 言 0 1 问题背景 在决策支持系统中的预测、计划、决策问题 中，建立系统的模型是分析和解决问题的前提，系 统常常需要对历史资料和现有的信息进行分析，建立起其量化分析模型，来分析系统的行为特
3、性 等 现有的系统解决建模问题的方法有很多种，如 回归分析、数据拟合及逼近论等，这时问题将转化 为确定某一给定函数(模型)，)中的参数 一(，)去拟合、插值或逼近已知数据 对 在这种情况下，模型的选择是至关重要的，不 适合的模型很难很好地描述系统的状态行为，使 建模过程失去意义 例如，对于回归分析，要求数 据有较好的分布规律，在实际的应用中还需要根 据对象本身的变化特点，并且对分析结果进行评 价，比较不同方法效果来选用适用的模型 因此，这就要求决策者对于各类分析方法和研究对象有 深入的了解，并掌握其应用背景，才能正确运用它 来分析和解决问题 然而，现实中很多的情况是：对于研究对象的了解很少，从
4、而难以选择出合适 的模型来对问题进行分析，有时即使对问题的背 景知识比较了解，如何选择一个合适的模型和进 行参数估计也是很困难的 很多实际问题都可以归结为如下图所示的一 个有输入和输出的系统：堕生一 厂 堕 一 对该系统，若已知有限个输入输出对(嚣，)；i 一 1，2，)，要求模拟系统的行为，这就 是一个建模问题 本文重点讨论的是具有明确数 学表达式的数学模型的建模问题 0 2 问题描述 设 (，)；z X，Y，i，J 是给定 的输入输出对，x，y都是实有限空蚵的子集，是 指标集；又若F是c(x)(x上所有连续函数全体)的一个子集，P 是定义在乘积空间I l y上的一个 ，距离，则建模问题便是
5、确定一个函数，F使得 对任意，F有 P()，()P(l，(置)，)(1)成立，或使得对某给定的 0 有 P(i f(丑)，)(2)实际上，建模问题可看成如下一个优化问题；P(五)，)(3)收稿日期：1 9 9 9 0 5 1 2 基金项目：9 5国家重点科技攻关项日(9 6 9 2 0-3 5 0 2)作者简升：葛志远(1 9 7 4 一)，男(汉族)，湖南双峰县，清毕大学经济管理学院博士生 维普资讯 http:/ 7 4 管 理科 学 学 报 2 0 0 0 年 3 月 遗传算法(g e n e ti c a lg o r it h ms，G A s)是一种 基于自然界生物机制的概率搜索方法
6、 作为一种 全局优化搜索方法，遗传算法具有简单通用、鲁棒 性强、适于并行处理以及应用范围广等特点，对于 一些复杂问题，它表现出极强的解决问题的能力 本文探讨利用遗传算法求解优化问题的能力，研 究自 适应建模问题 1 自适应建模 1 1 函数模型表示 对于建模同题，搜索优化模型是在函数空间 F(称为模型族)上进行的，通常F可以有一些简 单的函数经过有限次运算及符号生成的 因此，F 中的函数可以像用基本初等函数表示初等函数一 样用一些简单的函数及运算来表示它，而函数表 达式可 以树形结构来表示 例如函数表达式 口*(6+c d)*)*f(i，y，2)对应的一 棵有序树如图1 所示 圈 l 有序树表
7、示示倒 定义 l 设 F是一函数空间，P是F的一个 子集，是有限个从F到F或从FF到F的映 射组成的集合，则称F到F的映射为F上的一元 或二元运算组成的集合 如果F中的每一个函数 都可以通过 P中的函数及有限此 M 中的运算得 到，并且反之亦然，则称 P是F的一个原型集，M 为F的一个运算集，记为 FS p a n(P，M)例如：若P一(3 2 a 是 上的恒等函数，n R 表示常 函数 M 一(+，一，则 S p a n(P，M)为所有有理函数全体 从定义1 易知，如果P是F的一个原型集，M 是 F的一个运算集，则 F中的每一个函数 都可 以表示为集合P U M 中元素的一个串 然而，P U
8、 M 中元素组成的任何一个串却未必表示 F中的 一个函数 定义2 集合P U M中元素的一个串若对应 F中的一个函数 f 坝4 称该串是，的串表示，若，的串表示的某个子串也对应F中的一个函数，则 称该子串为的一个合法子串 易知，每一个函数，的串表示都对应一个二 叉树，这些二叉树具有叶节点的元素属于P而非 叶节点的元素属于M 定义3对应于，的串表示的二叉树称为 的(二叉)树表示 由此，可以利用遗传算法的结构编码来求解 式(3)所表述的建模问题 1 2 基于遗传算法的自适应建模4 在 以上分析的基础上，就式(3)所描述的优 化问题进行研究，来设计遗传算法的基本算子对 问题进行求解，提出自 适应建模
9、算法 通常对模型，的评价是根据观测值(与模 型的期望值，(-T D)的误差检验来度量的，因此 式(3)中的目标函数直接采用模型，的方差：q(，)：P(，(嚣)，y )=八五)一 2(4)遗传算法的编码：采用上面描述的二叉树结 构式，每一个二叉树个体表示一个函数 由于与 标准遗传算法的编码不同，因此遗传算子的设计 与标准遗传算子也有很大的不同 下面对自 适应 建模过程中遗传算子进行描述 适应性的度量：原始适应函数直接采用个体，的方差 选择策略：采用线性排名选择策略若 q ()是第 代时第 i 个模型()的目标函数 值，()表 示(i l，2，)按 从 小 到 大 q(f)的排序序号，则分配给()
10、的选择概率 为 r，“一 盟二堡 N(+1)交叉算子：在两个父代个体中独立随机设定 各自的交叉点，实行交叉时 两个个体以其交叉点 作为根节点的部分子树进行交叉互换，生成两个 维普资讯 http:/ 第 1 期 葛志远等：决策支持系统的自 适应建模研究及应用实例分析 新个体，例如图2 中所示的两个父代通过交叉算子获得两个子代 口 X 父代2 子代 2 圈 2 交叉算子示倒 实际上，这种交叉算子与标准遗传算子的交 群内个体的选择概率；叉算子有类似之处 图中父代 l 的波兰表达式(后 根据 从P(f)中选择个体进行遗传操 序)为 一型*+，父代 2的波兰表达式为 作，用后代替换整个群体，产生新种群P
11、(t 十 1)；m*+m*，父代l 中以交叉点为根节点的子 计算P(t 4-1)中个体的适应值，t +1；串为 R-，父代 2 中以交叉点为根节点的子串为&v 1-Z *+，二者交叉的结果相当于将这两个子串 进行切断和拼接，重新组合为两个新的个体 变异 算 子；在 父 代个 体中 随 机 选择 变异 点进 2 算法的改进 行变异，如图3 所示的例子 +圉 3 变异鼻子示倒 算法结构：上述对树结构的遗传操作实际上 是基本遗传操作的一种扩展，其遗传操作的完整 算法框架与标准的遗传算法基本类似 如采用非 重叠种群的算法：随机初始化种群P(0)，f 一0；计算P(0)中个体的适应值；Wh i le(不
12、满足终止准则)d 0 根据个体的适应值及选择策略，计算种 通过试验和实际的应用，上述定义的基于遗 传算法能够解决实际应用中的建模问题，并且与 传统的解决建模问题的方法相比有很多的优点，表现出了很大的应用潜力，文 6 对此作了一些 的研究、但其遗传算子是从标准遗传算法扩展而 来，由于结构编码与标准编码有很大的不同，对遗 传操作功能有很大的影响，在应用时表现出很多 的缺点和局限性，如很容易出现未成熟收敛现象，获得的有较好结果的函数，的表达式太长而过于 复杂，并且不符合实际，等等阿题，因此需要对其 进行改进 在上述定义了基于遗传算法的自适应 建模方法的基础上，作了深入的研究与试验，对算 法进行了改进
13、，使算法在性能与应用上都取得了 进展 1)对结构编码的修改；对树结构进行限制 将树结构限制在一定的深度之内，即树结构有一 个最大深度 实际上，如果不限制树结构的深度的 J 一 。姗 维普资讯 http:/ 7 6 管理科学学 报 2 D O 0 年 3 月 话，遗传算法的搜索是在一个无限空间中进行的，因为树的深度是可以无限大 限制了树的最大深 度后，遗传算法的搜索就限制在一个有限空间中 进行了 2)对目 标函数的修改：添加控制树结构复杂 程度的参量 如果通过遗传算法搜索得到的函数 _厂 的表达式过于复杂，在一般情况下很难反映实 际的问题，复杂的模型对于分析原问题没有什么 帮助 实际上这就是建模
14、结果的模型评价问题，得 到的模型的好坏，除了模型应该有较小的误差外，模型的简洁性也是一个评价因素 因此，在目 标函 数中添加反映模型复杂度的参量 C*(_厂)，其中 c为一个常数，(_厂)表示f所对应的树的结点的 个数 实际上，模型复杂度的参量C*(_厂)相当 于每一个二叉树的节点都具有一定的能量，增加 一个节点需要消耗系统的能量才能实现 添加了 这一项是为了使系统获得的结果不需要消耗较多 的能量，即最终模型不会太复杂 在优化的开始阶段，个体_厂 的误差都比较大，此时模型的复杂度不成为主要的评价因素，当进 行到优化的后期阶段时，大部分个体的最小二乘 误差均有较大的改善，此时模型的复杂度成为一
15、个重要的评价因素 但随着遗传算法的进化，获得 的个体适应值越来越好，即目标函数的误差越来 越小，如果上述的模型复杂度参量C*(_厂)保持 一定的值不变，会使得算法停留在一个简单但不 太理想的个体上，从而阻碍算法的继续寻优 因 此，将算法的复杂度参量进一步修正为一个自 适 应的值，修正的方案是在复杂度参量基础上乘一 个修正因子(f)，“()表示第 t 代时模型复杂度 的修正因子，随着算法的进化而变化 此时，模型 复杂度参量为C*(_厂)*()，修正因子“(f)用 以调整不同阶段时模型复杂度的评价值“(幻还 要使得模型复杂度的修正值与模型的最小二乘误 差匹配“()可取为线性函数或者与最优个体的 最
16、小二乘误差相关取值 同时，在计算过程中所产生的函数有可能没 有定义或者计算时溢出，比如对负数取对数或者 指数函数的指数很大，目标函数也需要处理这些 情况 因此，在目标函数中添加一惩罚项g(_厂)，当 g(_厂)充分大时可使得这些意外的个体被淘汰 这样，目 标函数由式(4)修正为：g(_厂)一P(i _厂(五)，Y )一：_厂()一 ：一 C*(力*(f)一 g(5)3)选择策略的修改：为了保证算法的收敛 性，与标准的遗传算法的改进类似，也采用在选择 后保留当前最好解的选择策略 4)交叉算子的修改：由于对树结构有了深度 的限制，因此在交叉的结果也要求满足这个限制，杂交点的选择要使得两个后代模型对
17、应的树结构 的深度不超过最大深度的限制 5)变异算子的修改：上面所定义的变异算子 是随机选择树的一个结点，然后用其它的元素替 代 但这样进行的变异有可能产生不合法的子串，因此需要进行修正 树的内部结点(即非叶结点)由F的运算集 中的元素组成，叶结点由F的原 型集P中的元素组成，在变异时需要区分这两种 结点 变异树的内部结点有多种，如下所示：重新产生新的子树来替代旧子树；交换结点的左右子树；对以结点为根节点的子树进行化简等 对子树的化简一般来说比较复杂，化简包括 合并 同类项、计算 结果、简化 互逆函 数(如 e x p(1n x)一z)等，由于遗传算法搜索的遍历性，树的化简可以略去，也可以保留
18、以加快进化的速 度 可以以等概率的方法执行上述树的内部结点 的变异操作 变异叶结点也有多种，如果元素为变量，可以 用 P中其它的元素替换；如果元素为数n，采用非 一致性变异，即变异策略为 f+0，U B 一 )i f a n d(2)一 0 一1 一(f，一L B k)i f a n d(2)一1 其中 L ，U B k 为n 的取值范围，t 为当前代数，r a n d(n)为随机生成从 0 到 n一 1 的整数，函数 (f，)的值域为 0，可取 0，)一 y (1一 r(I-t m)r 为随机数，0 r 1，丁为最大代数，t 为当 前代数 可以看出随着t 的增加，(f，)r)减少 当t 小的
19、时候，这种变异可以均匀地搜索整个空间，它 能体现一种自适应的遗传性，即在一定代数后的 子孙不会离它太远 维普资讯 http:/ 第 1 期 葛志远等：决策支持系统的自 适应建模研究及应用实例分析 7 7 3 应 用 利用上述的自 适应建模的方法对全国港口 进 出E l 集装箱量与全国进出E l 贸易额的关系，根据 历史数据进行建模分析 其数据列入表 1 中，其原 始数据分布如图4中的曲线C所示 表 1 进出口集装箱量和外贸进出口颤数据 外贸进出口额 进出口 集装箱量 年份(十亿元)(万T E U)1 9 85 6 9 60 5 O 3 1 3 3 1 9 86 7 3 85 6 3 0 5 8
20、 3 1 9 87 82 65 7 0 0 7 0 9 1 9 88 1 0 2 79 9 6 4 9 0 4 1 9 8 9 】l 1 6 8 11 7 6 85 4 1 9 9 0 1 1 5，4 4 1 4 2 7 2 2 6 1 9 9 1 1 3 5 6 3 2 0 4 9 00 0 1 9 9 2 1 6 5 5 3 2 5 9 5 4 4 6 1 9 9 3 1 9 5 7 0 3 3 5 3 25 2 1 9 9 4 2 3 6 6 2 4 3 6 7 89 9 1 9 9 5 2 8 吼 8 5 6 0 8 9 97 3 1 9 9 6 2 8 9 9 o 7 7l _ 4
21、00 0 1 9 9 7 3 2 5 0 6 9 8 3 7 0o 0 数据来源；中国交疆统计年鉴 利用一元线性回归分析获得的模型为，0)一3 2 8 6*一2 3 3 8 2 9(其中，表述全国进出口 贸易额，)表示全国港口进出口贸易集装箱量 的回归曲线)，其图形如图4中的直线L所示 比 较上面图中两条曲线，可看出，一元线性回归模型 并不能很好地反映实际的模型，其误差较大 为了 寻找二者之间的关系，采用了前面所述的自 适应 建模方法 )15。，0 2D 0 3 图 4 一元线性回归分析结果 在研究中，算法采用的是通过改进后的基于 遗传算法的自适应建模 选取P ，。；n R ，M 一 +，一，
22、S I N，C 0S，E X P，L N，这样 以 尸为原型集，为运算集所生成的模型族 s p a n(尸，)是有理函数集合的一个子集 应用实例中的选择策略、交叉算子、变异算子 均采用改进后的算法 初始群体随机生成，根据模 型的编码表述，每个模型对应一个二叉树，树的中 间节点和叶节点的元素从运算集和原型集中按均 匀分布随机选取 模型的控制参数取：群体大小 一1 0 0，最大代数 T 一5 0 0，繁殖概率 一0 1，杂交概率 A一0 6，变异概率 一0 3，树的最 大深度D一6，复杂度系数C一4 0 0，自 适应修正 因子(f)一lt (1 1*丁)下面的一些模型是 通过基于遗传算法的自适应建
23、模获得的一些模 型：)一2 8 1 9 6 2+0 0 0 7 9 4 9 8 3 f 2(x)一 6 3 3 7 5 4一 韭 【】o 7 9 4 9 8 3 (z)=2 9 3 5 4 3 4-O 0 0 7 4 9 1 5 一=丽面 亍 _=_ j=_ _j 1 0 而 这些模型的最大误差、最小误差、最大相对误差 r 一、最小相对误差、最小二乘误差q 等 数据分别列于表2中 裹 2 模型的比较 模型 9 ，()5 8 3 4 8 8 5 3 O 1 4 9 4 0 0 2 2 7 7 8 O 1 1 o 1 9 o o 1 9 5 ()1 1】3 7，0 9 2 9 7 5 0 8 41
24、 2 6 6 2 5 o 3 2 5 8 o 0 0 7 9 ()1 1 6 4 4 7 1 2 6 6 6 2 5 9 5 3 9 5 6 9 o 2 2 2 6 o o 1 5 8 ()3 5 9 7 8 3 3 o 3 7 4 7 7 7 2 6 9 1 3 o 3 0 6 9 O 0 0 3 5 蜘 锄 蝴 姗 0 姗 维普资讯 http:/ 7 8 管 理 科 学 学 报 2 0 0 0年 3 月 J I一 一 5 0 】U 0 】0 2 00 2 5 0 3 0 U 350 图 5自适应建模结果 比较以上几个模型，非线性模型)比线 性回归模型，)获得的结果更好 其中 )和)如图5
25、中、曲线所示 从模型分析，进 出口集装箱量与外贸进出口额呈二次非线性关 系()增加了一个修正项，使得模型的误差指 标中除了最大相对误差外，其余指标比其他模型 好 实际上，)模型中的最大相对误差是 1 9 8 5 年时的误差，1 9 8 6 年 以后的最大相对误差为 0 1 8 2 9，说明集装箱运输市场早期的不成熟 更 进一步的分析说明，我国的集装箱运输市场是一 参 考 文 献 个新兴的市场，市场从 8 O 年代中期开始开拓，外 贸运输中适合集装箱运输的货物采用集装箱运输 方式的比例越来越大，这同我国改革开放以来，经 济的发展和技术的进步是密切相关的 4 结论 通过上面的实例，说明了基于遗传算
26、法的自 适应建模方法与传统建模方法相比，具有很多的 优点 自适应建模不需要建模者具有很强的专业 背景知识，就能够建立较好的系统模型，并且在建 模过程中可以提供多个较好的模型供决策者进行 分析和参考 但由于自适应建模方法的研究还不 成熟，在实际的应用中存在一些问题 首先对于结 构编码的遗传算法本身的收敛性分析在理论上尚 未得到很好的证明，而且自适应建模的结果是提 供多个模型供分析和参考，对这些模型缺乏较好 的评价标准 如何判断和选择自适应建模所提供 的模型，以及模型是否能够很好地反映系统等方 面的问题，需要进行进一步的研究 1 D a s g u p t a D，Mic h a l e wl c
27、 z z(E d i t o r s)E v o l u t i o n a r y a l g o r i t h m si n e n g i n e e r i n g a p p l i c a t i o n s r im B e r li nH e i d e b e r g S p r i n g e r Ve r l a g，1 9 9 7 醢 He r r e r a F V e r d e 8：a y J 1 e d s G e n e t i c a l g o r i t h ms a n d s o f t c o mp u t i n g M H e i d e l
28、 b e r g：P h y s i ca Ve r l a g 1 9 9 6 ：3 A n g e l i n e P J K i n n e a r KE(E d i t o r s)A d v a n c e s i n g e n e t i c p r o g r a m m i n g M-MI T P r e s s C a m b r i d g e MA-1 9 9 6 -4 K o z a J R Gen e t i c P r o g r a mmi n g M Camb r i d g e，：MI T P r e s s，v i a-1 9 9 2 一j K o z
29、a J RG e n e t i c P r o g r a mmi n g一2 M Cam b r i d g e：MI T P r e s s，i v l A，1 9 9 4 ：s 潘正君等 演化计算E M_-北京：清华大t l：l 版社，南宁：广西科学技术t l：l 皈社-1 9 9 8 A s t u dy o n a d a p t i v e mo d e l i n g o f DS S a n d i t s a pp l i c a t i o n GE Zh i y u a n，W A N G Yo n g Ma n，Y IJ i n S c h o o l o f E c
30、 o n o mi c s a n d Ma n a g e me n t，Ts i n g h u a Un i v e r s i t y，B e i j i n g 1 0 0 0 8 4 Ab s t r a c t：Th i s p a p e r s t u d i e s a d a p t i v e mnd e h n g o n g e n e t i c a l g o r i t h ms Th e mo d e l i n g p r o b l e m c a n b e r e _ g a r d e d a s a n o p t i mi z i n g p
31、r o b l e m wi t h a s i mp l e c o n v e r s i o n B a s e d o n t h e r e s e a r c h of g e n e t i c a l g o r i t h ms i n a u t o ma t i c p r o g r a mmi n g，t h i s p a p e r d c u s s e s a d a p t i v e mnd di n g me t h o d O i l g e n e t i c a l g o r i t h ms，a n d p u t s f o r wa r d
32、 f h e i mp r o v e d a l g o r i t h ms o f a d a p t i v e mo d e l i n g F i n a l l y，a c o n c r e t e c a s e u s i n g a d a p t i v e mo d e l i n g o n g e n e t i c a l g o r i t h ms i s p r e s e n t e d Ke y wo r d s：DS S，a d a p t i v e mo d e l i n g，g e n e t i c dg o fi t h r r s，b i n t r e e 啪 。维普资讯 http:/