D0I:10.13374/i.issn1001-053x.2001.04.023 第23卷第4期 北京科技大学学报 Vol23 No.4 3001年8月 Journal of Unlversity of Scieece and Technology Beljing Ag2001 基于遗传算法的网络优化技术 在设备维修中的应用 张武军 徐金梧 杨德斌 北京科技大学机械工程学院，北京100083 摘要遗传算法用于维修网络优化，是求解网络优化问题的一个新思路.实例证明，遗传算 法用于机床维修网络优化，其计算结果比模潮网络规化得出的最优解更精确. 关鑪词遭传算法：网络优化：设备维修 分类号TH17 随着科学技术的进步和社会化大生产的发 1基于遗传算法的网络优化技术 展，现代化的工程技术、生产组织、经营管理等 问题具有规模庞大、工艺复杂、影响因素多、时 遗传算法是由Holland提出的、基于自然遗 间观念强等特点，从系统的角度来看，它们都是 传学和计算机科学的优化方法.它通过遗传基 由众多互相关联、互相制约的要素组成的复杂 因代码，利用复制、杂交、变异3种基本算子，进 系统，而且以大系统居多.描述、分析和研究这 行全局寻优.当染色体域足够大和遗传代次足 类复杂（或大）系统的有效方法是广义模型.可 够多时，从理论上讲，遗传算法可以给出原问题 以根据具体情况，选择广义模型中的若干类 的最优解. (个)模型来描述和分析，网络模型是广义模型 构造适用于网络优化问题的遗传算法步骤 的集成模型中一个重要的组成部分 如下： 应用参数线性规划求网络计划的时间一费 1)编码.编码一般采用二进制方式假设一 用最优解时，首先要求找出在整个网络图中的 个变量x的取值范围为[a,a),则可将该实数区 所有从起始节点到达终止节点的线路.但对于 域线性映射到整数区域[0,2"].其中n为变量x 大型网络，不仅线路很多，而且逐一确定相当困 的编码长度，它与“粒度”的取值有关如x的取 难而且，应用矩阵和计算机求解，公式本身在计 值为[4.0,8.0]，取粒度为0.1时，编码长度为6；取 算上也是相当复杂的.遗传算法采用从自然界 粒度为0.01时，则编码长度为9. 选择机理中抽象出来的几种算子对参数编码字 对于多变量优化问题，可先将每个变量进 符串进行操作，由于这种操作是针对多个可行 行编码，然后再按变量的顺序将这些编码连接 解构成的群体进行，具有本质的并行计算特点， 起来. 故在其世代更替中可以并行地对参数空间的不 2)初始化.选择一个整数N作为群体的规 同区域进行搜索，并使得搜索朝更有可能找到 模参数，然后随机地产生N个个体组成初始群 全局最优的方向进行，最后给出全局最优解，并 体 且求解速度快.针对遗传算法的上述优点，本文 3)计算适应值.取工程总费用为适应值 提出一种基于遗传算法的网络优化技术并用于 fitness=E (by-a)+tR, 刀E票 机床维修， 并按适应值大小排列. 4)遺传算子.先利用选择策咯从群体中选 收稿日期2000-03-09张武军男，33岁，博士生 择进行繁殖的个体组成父代，然后对其进行重 ★国家教委“跨世纪优秀人才”基金资助课题 组，即作用杂交和变异算子来形成下一代新的
第 23 . 第 4 期 月的卫年 8 月 北 京 科 技 大 学 学 报 Jo . 口目 。 f U . 加. . 勺 时 歇匆. o . . d l 娜卜. 。灿盯 跳幼加g 、勺L 23 N O . ` A . 卜 2娜l 基于遗传算法的网络优化技术 在设备维修中的应用 张武军 徐金格 杨德斌 北京科技大学机械工程学院 , 北京 】0 0 83 摘 共 遗传算法用于维修网络优化 ,是求解网络优化间题的一个断思 路 . 实例证明 ,遗传算 法用于机床维修网络优化 ,其计算结果 比模绷网络规化得出的最优解更精确 . 关位询 遗传算法 ; 网络优化; 设备维修 分类号 T H 17 随着科学技术的进步和社会化大生产的发 展 , 现代化 的工程技术 、 生 产组 织 、 经营管理等 问题具有规模庞大 、 工艺复 杂 、 影响因素多 、 时 间观念强等特点 , 从 系统 的角度来看 , 它们都是 由众多互相关联 、 互相 制约的要素组成 的复杂 系统 , 而且 以 大系统居多 . 描述 、 分析和研究这 类 复杂 ( 或大 )系统 的有效方法是 广义模型 . 可 以根 据具 体情况 , 选择 广义模型 中的若 千类 ( 个 )模型来描述 和分析 , 网络模 型是广义模型 的集成模 型中一个重要 的组成 部分 . 应用参数线性规划求 网络计划 的时间一费 用 最优解时 , 首先要求找 出在 整个网络 图中的 所 有从起始节 点到达终止节点 的线 路 . 但对于 大型 网络 , 不仅线路很 多 , 而且逐 一确定相 当困 难 . 而且 , 应用矩阵和计算机求解 , 公式本身在计 算 上也是相 当复杂 的 . 遗传算法采用 从 自然界 选择机理中抽象 出来 的几种算子对参数编码字 符 申进行操作 , 由于这种操作是针对 多个 可行 解 构成的群体进行 , 具有本质 的并行计算特点 , 故在其世代更替 中可 以并行地对参数空间 的不 同区域进 行搜索 , 并使得搜索朝更有 可能找到 全 局最优的方 向进行 , 最后 给 出全局最优解 , 并 且求解速 度快 . 针对遗传算法 的上述优点 , 本文 提 出一种基于遗传算 法的网络优化技术并用于 机床维修 . 收稿 日期 2 0( 协刁3刊均 张武军 男 , 3 岁 , 博士生 * 国家教委 “ 跨世纪优秀人 才 ” 基 金资助课题 1 基于遗传算法的网络优化技术 遗传算法是由 H o l an d 提 出的 、 基于 自然遗 传学和计算机科学 的优化方法 . 它通过遗传基 因代码 ,利用 复制 、 杂交 、 变异 3 种基本 算子 , 进 行全局寻优 . 当染色体域足 够大和遗传代次足 够多时 , 从理论上讲 , 遗传算法可以 给 出原 问题 的最优解 . 构造适用 于网络优化 问题的遗传算法步骤 如下 : l) 编码 . 编码一般采用二进制方式 . 假设一 个 变量x 的取值范 围为 a[ , , az) ,则可将该实数 区 域 线性映射到整数区域 0[ 2 ] . 其中 n 为变量 x 的编码长度 ,它 与 “ 粒 度 ” 的取值有关 . 如 x 的取 值 为.4[ 0, .8 0] , 取粒度为 0 . 1 时 , 编码 长度为 6 ; 取 粒度 为 .0 01 时 , 则编码长度 为 .9 对 于多变最优化 问题 , 可先将每个 变量进 行编码 , 然后再按变量 的顺序将这些编码连接 起来 . 2) 初始化 . 选择一 个整数 N 作为群体的规 模参数 , 然后随机地产 生 N 个个体组成初始 群 体 . 3) 计算适应值 . 取工程总 费用 为适 应值 iftn es ` = 。盈低一 口山卜切 , 并按适应值大小排列 . 4) 遗传算子 . 先利用选 择策略从群体 中选 择进 行繁殖 的个体组 成父代 , 然后 对其进行重 组 , 即作用杂 交和变异算子来形成 下一代新的 DOI: 10. 13374 /j . issn1001 -053x. 2001. 04. 023
374 北京科技大学学报 2001年第4期 个体，在前代染色体域的基础上产生新一代染 进行变异，得到新的染色体如下所示： 色体城的工作称为遗传操作. 1011001011→1010001011 基本的遗传操作有以下3种： 染色体是否进行变异操作是由事先给定的 (1)复制.根据前代染色体的适应值所确定 变异率决定的 的繁殖概率选择染色体并将其拷贝到下一代， 染色体不发生变化 2在设备维修中的应用实例 (2)杂交.杂交操作随机地选择两个已经进 表1为CA6140车床修理网络图时间一费 行繁殖的染色体作为母体，再随机地选择一个 用参数表，图1为机床维修网络图.图1中共有 交叉位置，将这两个母体位于交叉位置后的符 21个工作，表2为21个工作的参数取值范围. 号串互换，形成两个新的染色体.例如，对于下 表中各参数取值来自某机床厂，min与max表示 列2个染色体，当随机地选择交叉位置在第7 各个节点的最大和最小值，Length表示在一定粒 位时，交叉操作后产生的2个新的染色体（右边）： 度下二进制串的长度，工程间接费用率R=5.0元. 0010111000 0010110101 运用遗传算法进行网络优化时，只有选择 0101010101 0101011000 合理的参数，尤其是交配与变异率，才能保证在 染色体是否进行杂交操作是由杂交率决定 迭代次数内找到最优解，本文选定的参数见 的，杂交率是事先给定的进行染色体杂交操作 表3. 的概率 经过1000次遗传迭代，最后得出的最优解 (3)变异.将前代染色体的某位基因值由1 为3742元，低于文献[2]中用模糊网络规化得出 变为0，由0变为1.例如将一个染色体的第4位 的最优解3859元.各参数最优值如表1所示. 表1CA6140车床修理网络图时间一费用参数优化表 Table 1 Parameter optimization of CA6140 lathe maintenance network 序号 工作代号节点编号 正常条件下 最快条件下 D,hCW元D,hC元 aw元h'ywlh A (0,2) 8 20 2 50 5 4.80 2 B (2,4) 20 3 45 5 7.00 3 C (4,6) 48 120 16 212 6 47.47 4 D (6,8) 20 48 16 96 12 17.90 5 (8,12) 26 65 16 165 10 25.94 6 F (8,10) 32 40 16 2 2 16.00 7 G (12,20) 65 325 60 370 9 64.74 8 H (8,20) 26 32 1E 83 5 2582 9 I (6,16) 1 1.25 0.65 2 2 0.79 o J (16,18) 20 25 3 5 0.1 19.55 11 K (18,20) 65 162.5 56 165 0.3 65.00 12 L (20,30) 140 350 78 846 8 109.00 13 M (4,22) 4 5 p 31.4 12 1.80 14 N 22,26) 16 40 14.5 46 4 14.50 15 0 (22,24) 24 60 18 66 1 18.00 16 P (26,28) 15 40 8 51 1.5 15.00 17 Q (28,30) 8 20 30 2.5 4.00 18 R 30,32 9 20 8 5 8.00 19 (32,34) 58 145 26 222 3.5 26.05 20 人 (34,36) % 100 6 102 0.1 16.00 21 (36,40) 16 40 12 48 1.0 12.00 注：a4一费用变化率，4一时间最优值
. 3 74 . 北 京 科 技 大 学 学 报 20 1 年 第 4 期 个体 . 在前代染 色体域的基础上产生新一代染 色体域的工作称为遗传操作 . 基本 的遗传操作有以下 3 种 : ()l 复制 . 根据前代染色体的适应值所确定 的繁殖概 率选择 染色体 并将其拷 贝到下 一代 , 染 色体不发生变化 . (2 )杂交 . 杂交操作随机地选择两个 已经进 行 繁殖的染色体作为母体 , 再随机地选择一个 交叉 位置 , 将这两个母 体位于交叉位置后 的符 号 串互换 , 形成两个新 的染 色体 . 例如 , 对 于下 列 2 个染 色体 , 当随机地选择交叉位置在第 7 位时 , 交叉操作后产生的 2 个新 的染色体(右边) : 进行 变异 , 得到新的染色体如下所 示 : 1 0 1 1 0 0 1 0 1 1 , 1 0 10 0 0 1 0 1 1 染色体是否进行变异操作是由事先给定 的 变异率决定的 . 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 染色体是否进行杂交操作是 由杂交率决定 的 , 杂交率是事先给定 的进行染 色体杂交操作 的概 率 . (3 ) 变异 . 将前代染 色体的某位基 因值由 1 变为 0 , 由 0 变为 1 . 例如将一个染色体的第 4 位 2 在设备维修中的应用 实例 表 1 为 c 6A 140 车床修理 网络 图时 间一费 用参数表 , 图 1 为机床维修 网络 图 . 图 1 中共有 21 个 工作 , 表 2 为 21 个工作 的参数取值范 围 . 表 中各参数取值来 自某机床厂 , m in 与 ~ 表示 各个节点的最大和最小值 ,肠理油表示在一定粒 度下二进制 串的长度 ,工程间接 费用率卜5 . 0 元 . 运用 遗传算法进行 网络优化 时 , 只有选择 合理 的参 数 , 尤其是交配与变异率 , 才能保证在 迭 代 次数 内找到 最优 解 . 本 文 选定 的参 数见 表 .3 经过 1 0 0 次遗传迭代 , 最后得 出的最优解 为 3 7 42 元 ,低 于文献 2[ 』中用模糊 网络规化得 出 的最优解 3 8 5 9 元 . 各参数最优值如表 1 所示 . 衰 1 c 6A 1叨 车床修理 网络圈时 间一费 用 , 教优化 衰 介 b触 I .P… 加 r o p廿. 山. 伽 . of C A 6 140 h 恤 e m .加加 . 一 ce n e幻冲 o比 序号 工作代号 节点编号 正常条件下 乌几 以 元/ 最快条件下 马儿 哪玩 ’a 玩 · h 一 , 为 hl (0 夕) (2 ,4 ) (4 , 6) (6 , 8) ( 8 , 12) ( 8 , 10) ( 12 2 0 ) ( 8 一 20) ( 6 , 16 ) ( 16 , 1 8) ( 18 , 2 0) ( 2 0 一 3 0) (4 二2 ) (2 2只6) (2 2 , 2 4) (2 6 , 2 8) (2 8 , 3 0) 3 0 , 3 2 (3 2 , 3 4) ( 34 , 3 6) (3 6 ,4 0) 2 0 2 5 0 5 2 0 3 4 5 5 12 0 1 6 2 12 6 4 8 16 96 12 6 5 16 16 5 10 4 0 16 7 2 2 3 25 6 0 3 70 9 3 2 1〔 8 3 5 1 . 25 0 . 6 5 2 2 2 5 1 3 2 6 0 . 1 16 2 . 5 56 165 0 . 3 3 50 78 8 46 8 5 1 . 8 3 1 . 4 12 4 0 14 . 5 4 6 4 60 18 66 1 4 0 8 5 1 1 . 5 2 0 4 3 0 2 . 5 20 8 25 5 14 5 2 6 2 2 2 3 . 5 l 0() 16 1 0 2 0 . 1 4 0 1 2 4 8 1 . 0 4 . 80 7 . 0 0 4 7 . 4 7 .90洲加.74 17科256 482063285“20651 140 BA 1624580156498 且. 2 25 82 0 . 79 19 . 55 65 . 0 109 . 00 1 . 80 14 . 50 1 8 . 00 15 . 0 0 .4 o .8 o 2 6 . 0 5 1 6 . 00 12 . 0 0 MUDE0HKNQUF1LpR5JT . j 气4 ó 6 ù了tR 1042021n13567899 注 : 内一费用 变化率 , 为 一时 间最优值
Vol23 No.4 张武军等：基于遗传算法的网络优化技术在设备维修中的应用 ·373· ②N文 P A R S T ⊙②0 10 20 +⊙+②④©o H D 8 o+⊙ 图1机床蝶修网络图 Fig.1 Lathe maintenance network 表221个节点的参数取值范置 3结论 Table 2 Parameter scope of 21 node 参数1234567891011 遗传算法是一种行之有效的优化方法，用 min231616161660160.651356 于网络优化，模型简单，求解速度快，并能在全局 max8848202632652612065 意义上给出最优解.遗传算法用于维修网络优 Le地109129101191061010 化，是求解网络优化问题的一个新思路.实例证 参数12131415161718192021 明，遗传算法用于机床维修网络优化，其结果比 mim781.814.518848261612 模糊网络规化得出的最优解更好. max140416241589584016 Length138810109712129 参考文献 表3试验参数 1陈国良。遗传算法及其应用.北京：人民邮电出版社， Table 3 Test parameter 1996 2高立新.精度诊断和维修决策的理论、方法及其应 参数 含义 选值 用：[博士论文].北京：北京科技大学，1995 Total Trials 送代遗传次数 1000 3王大东.基于计算智能的设备故障诊断方法研究与 Structure Lengt 每一个体的二进制串长度 193 实现[博士论文]，北京：北京科技大学，1997 Crossover 交配率 0.60 Mutation rate 变异率 0.007 Generation Gap 代间距 1.0 Equipment Maintenance Network Technique Based on Genetic Algorithm ZHANG Wujun,XU Jinwu,YANG Debin Mechanical Engncering School,UST Beijing.Betjing 100083,China ABSTRACT Set up a new network optimization method based on genetic algorithm,the method has the advantage of high speed,it can find the most optimal solution in global search.Equipment maintenance net- work technique based on genetic algorithm is a new direction for solved network optimization.It has been proved that equipment maintenance network technique base on genetic algorithm is better than that based on fuzzy network optimization. KEY WORDS genetic algorithm;network technique;equipment maintenance
丫b U 3 N 0 . 4 张武军 等 : 基 于遗传算法 的 网络优化 技术 在设 备维修中 的应用 . 3竹 . 圈 1 机床维修网络 圈 F 电 . 1 La ht e 二加 t e . . n ce . e 幻口。 kr 衰 2 21 个节点的参傲取位范围 介b 触 2 h ar . 晓 r 抑件 o f Z I . do e 参数 1 2 3 4 5 6 7 8 9 10 11 m 玩 2 3 16 16 16 16 60 16 0 . 6 5 13 56 m a x 8 8 4 8 2 0 2 6 3 2 砧 26 1 2 0 6 5 杯雌两 10 9 12 9 . 10 二 11 9 10 6 10 10 参数 12 13 14 15 16 17 18 19 2 0 2 1 m ni 78 1 . 8 14 . 5 18 8 4 8 2 6 16 12 m 以 140 4 1 6 2 4 15 8 9 5 8 4 0 16 玩n gbt 13 8 8 10 10 9 7 12 12 9 衰 3 一 试脸参傲 介b el 3 T 曰t 钾.r m e et r 参数 含又 选值 介加1Tri ai s 迭代遗传次数 1 00() S臼u d 理茂 从n gt 每一个体的二进制申长度 1 93 C or s s o v e r 交配率 .0 60 加加电山。n n 吐e 变异率 .0 0 7 C沁。 . 成 ino G 叩 代间距 1.0 3 结论 遗传算法是一种行 之有效的优化方法 , 用 于 网络优化 ,模型简单 , 求解速度快 ,并能在全局 意义上 给出最优解 . 遗传算法用于维修网络优 化 , 是求解 网络优化 问题 的一个新思路 . 实例证 明 , 遗传算法用 于机 床维 修网络优化 ,其结果 比 模糊 网络规 化得出的最优解更好 . , 考 文 嗽 1 陈国 良 . 遗传算法及其应用 . 北京:人民 邮电出版社 , 19 96 2 高立新 . 精度诊断和维修决策的理论 、 方法及其应 用 :[ 博士论文 1 . 北京 : 北京科技大学 , 19 5 3 王大东 . 基于计算智能的设备故障诊断方法研究与 实现:[ 博士 论文 ], 北京: 北京科技大学 , 19 7 E qu iP m ent M a l n t e n an c e N e 七万o kr eT e lm iqu e B a s e d on eG n e t i e A lg ior ht m 刀划刃吞 牙斌翻叹 尤U iJ ” w u, 别刀召 刀e石in M ce 恤园 侧目助甲峨仙 9 S c bo L U S T B e ij in g , B e lj ign l峨洲X) 8 3 , C b 丘旧 A B S T R A C T S et uP a n e 、 v n et w o 攻 叩石m 血at ion m e ht ed b as ed on g en iet c ia g a ir ht m , het m 改h( 川 b a s het 耐v an at g e of hi hg s声ed , it c an 6 n d het m o st OP 垃nI a 】s ol iut on in g 】o b a l s e aJ 限h . 鞠访pm ent m iaJ 曲m an eC n e t . w o kr etC 腼q p e ba se d on g en e t i c al g o ilr ht m is a ~ 山茂ict on for so 】v e d n et w o kr OP 位刘比币on . tI h as be e n 扭。 v e d ht at e q切 LP m ent m ia nt er 囚阴 e n e wt o 次 et c hj ia q u e b创犯 on g en e t i c al 砰i)r ht m 15 b e伪叮 也曲 也吐 b as ed on 几刃甲 n et w ol t 叩t如七以ion · K E Y W O R D S g e n e t i e al g ior ht m ; n et w o kr etC hn iq砰e 冲甲咖. e 址 m ia nt e n a n e e
