维普资讯 http://www.cqvip.com ／ 养护机Ｍ械ａｉｎ与ｔｅｎ施ａｎｃ工ｅ 技Ｍａ术ｃｈ ｉｎｅｒｙ＆Ｃｏｎｓｔｒｕｃｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ 基于多目标遗传算法帕宣速公路多目标 路面荠护决策优化 邹国平，虞安军，黄铮 （江西赣粤高速公路股份有限公司，江西南昌３３００２５） 摘要：高速公路多目标路面养护决策优化是高速公路路面养护决策优化未来发展的趋势，也是目前研 究的热点。针对传统数学规划方法用于高速公路多目标路面养护决策优化的不足，引入了目前在多目标 优化领域应用较多的带精英策略的非支配排序遗传算法ＮＳＧＡ一Ⅱ。将ＮＳＧＡ一１１应用于高速公路多目标 路面养护决策优化问题中．仿真结果表明其性能优于传统的数学规划方法。具有广阔的应用前景。 关键词：道路工程；路面养护决策优化；多目标优化；遗传算法 中图分类号：Ｕ４１８．６ 文献标识码：Ｂ 文章编号：１０００—０３３Ｘ（２００７）０７－００３０—０３ Ｅｘｐｒｅｓｓｗａｙ Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ Ｐａｖｅｍｅｎｔ Ｍａｉｎｔｅｎａｎｃｅ Ｄｅｃｉｓｉｏｎ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｂａｓｅｄ ｏｎ ＮＳＧＡ一Ⅱ ＺＯＵ Ｇｕｏ—ｐｉｎｇ，ＹＵ Ａｎ－ｊｕｎ，ＨＵＡＮＧ Ｚｈｅｎｇ （Ｊｉａｎｇｘｉ Ｇａｎｙｕｅ Ｅｘｐｒｅｓｓｗａｙ Ｃｏ．Ｌｔｄ．，Ｎａｎｃｈａｎｇ ３３００２５，Ｊｉａｎｇｘｉ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｅｘｐｒｅｓｓｗａｙ ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｐａｖｅｍｅｎｔ ｍａｉｎｔｅｎａｎｃｅ ｄｅｃｉｓｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｓ ｔｈｅ ｄｅｖｅｌｏｐｉｎｇ ｔｒｅｎｄ ｏｆ ｔｈｅ ｅｘｐｒｅｓｓｗａｙ ｐａｖｅｍｅｎｔ ｍａｉｎｔｅｎａｎｃｅ．ＮＳＧＡ一１１ ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａ－ ｔｉｏｎ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｅｘｐｒｅｓｓｗａｙ ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｐａｖｅｍｅｎｔ ｍａｉｎｔｅｎａｎｃｅ ｄｅｃｉｓｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｂａｓｅｄ ｏｎ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ｍａｔｈ ｐｒｏｇｒａｍｍｉｎｇ．Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ，ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｓｈｏｗ ｔｈａｔ ＮＳＧＡ一１１ ｉｓ ｍｏｒｅ ｅｆｆｅｃｔｉｖｅ ｔｈａｎ ｍａｔｈ ｐｒｏｇｒａｍｍｉｎｇ ｉｎ ｒｅｓｐｅｃｔ ｏｆ ｓｏｌｖｉｎｇ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｔｈｅ ｅｘｐｒｅｓｓｗａｙ ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｐａｖｅｍｅｎｔ ｍａｉｎｔｅｎａｎｃｅ ｄｅｃｉｓｉｏｎ ｏｐｔｉｉｚａｔｍｉｏｎ ａｎｄ ｈａｓ ｇｏｏｄ ｐｒｏｓｐｅｃｔ ｉｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｅｘｐｒｅｓｓｗａｙ ｐａｖｅ—。 ｍｅｎｔ ｍａｉｎｔｅｎａｎｃｅ ｄｅｃｉｓｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ． Ｋｅｙ ｗｏｒｄｓ：ｒｏａｄ ｅｎｇｉｎｅｅｒｉｎｇ；ｐａｖｅｍｅｎｔ ｍａｉｎｔｅｎａｎｃｅ ｄｅｃｉｓｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ；ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｏｐｔｉｉｚａｔｉｍｏｎ；ｇｅ—— ｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ０ 引言 高速公路路面养护受到养护资金的限制，不可能 对所有路面进行养护。使其达到最佳的路面状态。高 速公路路面养护决策优化，就是讨论如何有效地利用 有限的养护资金．使高速公路路面处于最佳服务水平 或产生最大经济效益［ 。 目前处理高速公路多目标路面决策优化问题的方 法主要有２种：一种是传统的数学规划方法，其主要思 想是将多目标决策优化问题通过以下方法转化为单目 标决策优化问题。通过对多个目标进行分解，依据各 目标的重要程序排序，将最重要的目标作为主要目标， 基金项目：江西省交通重点科研项目（２００３—０２） 而将次要目标作为其约束条件；还可以对多个目标进 行综合，采用线性加权法、理想点法、平方和加权法等 方法．形成一个新的决策目标［ｚ－。以上２种方法最多只 能得到一个Ｐａｒｅｔｏ最优解，同时Ｐａｒｅｔｏ最优解的好坏严 重依赖算法设计者的专业知识，只适应于一些特定的 高速公路多目标路面养护决策优化［ 。 另一种用于高速公路多目标路面决策优化问题的 方法是多目标遗传算法，其一次就能求出多个均匀分 布的Ｐａｒｅｔｏ最优解，且无须任何专业知识，非常适合高 速公路多目标路面养护决策优化。国外对多目标遗传 算法用于高速公路多目标路面养护决策优化进行了大 量研究 ］，国内关于这方面的研究则较少。本文将多 目标遗传算法ＮＳＧＡ一１１应用于高速公路多目标路面 企 丽撼石 泐 维普资讯 http://www.cqvip.com 莽护机赫与施工技术 Ｍａｉｎｔｅｎａｎｃｅ Ｍａｃｈｉｎｅｒｙ＆Ｃｏｎｓｔｒｕｃｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ 颟 漕 养护决策优化。通过仿真实验证明ＮＳＧＡ—ＩＩ算法优于 传统的数学规划方法。 胜出标准，使准Ｐａｒｅｔｏ域中的元素能扩展到整个Ｐａｒｅｔｏ 域，并均匀分布，保持种群的多样性。 （３）引入精英策略，增大采样的空间。将父代种群 １带精英策略的非支配快速排序遗传算法 １．１非支配排序遗传算法（ＮＳＧＡ） 与其子种群竞争得到下一代种群，容易得到更为优良 的下一代。 非支配排序遗传算法的主要思想是：一是利用非 支配排序算法对种群进行非支配分层，然后通过选择 操作得到下一代种群；二是使用共享函数的方法保持 ＮＳＧＡ—ＩＩ算法流程图见图２，其算法实现步骤如下。 － 群体的多样性。ＮＳＧＡ的基本流程和简单遗传算法相 同，其主要的流程见图１。 随机产生初始种群Ｐ¨ 进化代数ｔ：０ —————ｒ——一 锦标赛选择操作ｌ 拥挤联赛选择操作 三三三王二二二 交叉操作 二二二工二二二 变异操作 二二二］［＝二 产生子代种群Ｑ， 『 种群Ｐ．和子代 生新一代种群Ｐ ｌ ￡ ！ Ｉ 囱 （１）随机生成一个父代种群Ｐ ，并置代数计数器ｚ＝ ０。种群成员根据非劣法则进行排序，每一个解都计算 其适应度值，并归于不同的级别，１级代表最好，２级次 ｌ圭Ｉ１ ＮＳＧＡ 程 之，以此类推。然后运用常规的二进制锦标赛选择方 法，并通过交叉和变异操作产生一个大小为Ⅳ的子代 种群Ｑ 。 １．２带精英策略的非支配快速排序遗传算法（ＮＳＧＡ－ Ⅱ、 ＮＳＧＡ虽然在多目标优化问题方面得到了大量应 用，但存在如下问题： （２）合并父代Ｐ 和子代Ｑ 生成新种群Ｒ ，则Ｒ 大小 为２Ｎ。 （１）非支配排序的算法复杂，计算复杂度为Ｏ（ＭＮ３）， 其中 为目标函数个数，Ⅳ为种群大小。 （３）从尼中选择Ⅳ个个体组成新一代种群 如下： 步骤 （２）缺少精英策略，研究证明带有精英策略的多目 标遗传算法，不但可以加快整个算法求解最优解的速 度．而且还能防止优秀解的丢失。 １）对Ｒ 按照非劣排序，由于它包含了当前和以前 世代的所有成员，所以最优解也包含在内，假设生成的 序列集合分别为Ａ ，Ａ，，Ａ ，…。 （３）需要人为指定共享半径 对整个算法影响较大。 ， 设置的好坏 ２）如果Ａ 的大小大于Ⅳ，则对Ａ 进行拥挤度计算， 通过拥挤度比较算子对个体进行排序．取出前Ⅳ个个 针对以上３个问题，Ｄｅｂ等人于２００２年提出了带精 英策略的非支配排序遗传算法ＮＳＧＡ—ＩＩ，对ＮＳＧＡ进 行了有针对性的改进，主要表现在３个方面： 体组成 ＋ ；如果Ａ 的大小等于Ⅳ，则直接用Ａ 组成Ｐｌ＋ ； 如果Ａ 的大小小于Ⅳ，那么就从序列Ａ，中补足，如果还 是不够，则从序列Ａ 补足，以此类推，直到找到Ⅳ个体。 特别注意：如果所有选定的序列集合的个体总和等于 Ⅳ，则用它们直接组成Ｐ，＋ ；如果所有选定的序列集合的 个体总和大于Ⅳ，则对最后入选的序列进行拥挤度计 算并排序后，抛弃其中多余的个体。 （１）提出一种基于分级的快速非支配排序法，使得 算法的复杂度由原来的Ｏ（ＭＮ３）降￣，ＪＯ（ＭＮ２）。 （２）提出拥挤度和拥挤度比较算子，其适应度共享 策略不需要指定共享半径，并且作为排序后同级间的 企 ＲＭ…＆…ＣＭ２…００７￣～ ．维普资讯 http://www.cqvip.com 养护机挑＿与施工技术 Ｍａｉｎｔｅｎａｎｃｅ Ｍａｃｈｉｎｅｒｙ＆Ｃｏｎｓｔｒｕｃｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ （４）ｔ＝ｔ＋ｌ，如果ｔ大于算法规定的最大迭代代数，则 算法结束，否则继续步骤（４）。 ｆ５）对Ｐ。通过拥挤联赛选择、交叉操作和变异操作 得到子代种群Ｑ ，跳到步骤（２）。其中拥挤联赛的选择步 骤如下： １０８ｘ１＋１３０ｘ２＋１２ ３＋９０ｘ４＋１ ｌＯｘ５－．＜３５０ （５） ｘｉ＝Ｏ或１（１≤ ≤５，ｉ∈ （６） 本文采用Ｄｅｌｐｈｉ７为编程工具．具体比较结果见表 ２。从表２可以看出，ＮＳＧＡ—Ｉ１所求的结果无论在养护 资金的利用方面，还是投资收益和养护后整体路况均 优于文献ｆ４］通过数学规划求出的结果。因此，可以看 １）对所有个体进行非劣排序，并计算每个个体的 拥挤度。 ／￣ＮＳＧＡ—Ｉ１优于文献［４］采用的数学规划优化方法。 表２多目标高速公路路面养护决策优化仿真实验结果比较 ２）利用拥挤度比较算子，对所有的个体进行联赛 选择。 最优解 本文的 ＮＳＧＡ一Ⅱ ２仿真实验 以文献『４］中的一个高速公路养护资金分配的多 目标路面养护决策问题为例。假设某公路养护部门所 所需养护资 投资收益／ 维修后路况 金／万元 万元 （１０分制） ３ｌ０ ３ｌ５ （Ｉ，Ｉ，０，Ｉ，ｏ） （Ｉ０，Ｉ，Ｉ，０） ，２９ ３０ ２６ ２５ 文献［４］的 辖的５个路段需要进行养护维修，该部门可支配的养护 资金只有３５０万元。假定每个路段仅考虑一个养护方 案．每个方案的相关资料见表１。 表１养护方案相关资料 数学规划 （Ｉ，０，Ｉ，０，Ｉ） ２７５ ２６ ２４ ３结语 本文针对基于传统数学规划优化方法的高速公路 多目标路面养护决策优化的不足，引入了多目标遗传 算法ＮＳＧＡ—Ｉ１用于高速公路多目标路面养护决策优 化。仿真结果表明，该算法优于传统的数学规划优化 方法。ＮＳＧＡ—Ｉ１是目前在国外应用得比较多的多目标 所需资金／ 投资效益／ 维修前 维修后 采用方案后所 需修复的 方案 万元 万元 路况Ｏｏ 路况Ｏｏ 需的日常养护 面积／ｍ２ 分制１ 分制） 工作量／（人・日） 方案１ 方案２ 方案３ ｌ００ ９０ ９５ １０ ８ ９ ｌｌ ７ ７ ７ ６ ７ ７ ８ ９ ８ ９ ８ １０８ ｌ３０ １２４ ９０ ｌｌ０ ｌ０ Ｏ００ ８ Ｏ００ ９ Ｏ００ ｌ２ ５００ ８ ５００ 遗传算法，国内对其的研究还很少，本文的研究对后来 者有一定的借鉴意义。另外，本文的研究为中国高速公 路路面养护决策优化提供了一个全新的研究方向。下 一方案４ ｌ２０ 方案５ ８０ 步需要做的工作是设计通用的基于多目标遗传算法 如果该部门的养护能力有限，只能对４０ ０００ ｍ２的 破损进行养护．且要求养护后的日常工作量不超过３５０ 人・日，则应该采用哪些方案，才能够使投资收益最大、 养护后的整体路况最好。 ＮＳＧＡ—Ｉ１的高速公路多目标路面养护决策优化系统， 将该算法应用到高速公路路面养护决策优化实际问题 中去。 参考文献： ［１］资建民．路面管理和管理系统［Ｍ］．广州：华南理工出版社，２００３． ［２］喻翔．高速公路路面养护管理系统决策优化的研究［Ｄ］．西安：西 安交通大学．２００５． 设决策变量为 （１≤ ≤５，ｉ∈ ，ｘｉ＝ｌ或者０分别代 表是否采用第ｉ个方案，则根据问题的假定，得高速公 路多目标路面养护决策优化数学表达式如下。 目标函数： ｍａｘ Ｚｌ＝ｌＯｘ１＋ ２＋ ３＋１１ ４＋ ５ （投资收益最大） （１） ［３］谢涛，陈火旺．多目标优化与决策问题的演化算法［Ｊ］．中国工程科 学，２００２，４（２）：５９—６８． ｍａｘ Ｚ￣＝８ｘ ＋ ：＋ ３＋９ｘ４＋８ｘ （养护后整体路况最好）（２） 约束条件： １００ｘ１＋９０ｘ２＋９５ｘ３＋１２０ｘ４＋８０ｘ５￣＜３５０ １０ ０００ｘ１＋８ ０００Ｘ２＋９ Ｏ００ ３＋１２ ５００ｘ４＋ ［４］朱荣军．高速公路养护管理系统研究和开发一经济效益分析与资金 优化分配【Ｄ】．南京：东南大学，２０００． （３） （４） 收稿日期：２００６—１０—２８ 【责任编辑：董强柱】 ８ ５００ｘ ≤４０ ０００