（道路与铁道工程专业论文）遗传算法在路面管理系统中的应用研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 自上个世纪八十年代以来，我国高速公路建设发展迅速，目前已经初步 完成高速公路网的建设，随之而来的是大量的养护工作。在国外，路面管理 系统已经被证明是个统筹养护资金分配，维持路网服务水平的有效工具。 在我国，“七五”期间曾经开展普通公路路面管理系统的研究，而高速公路路 面管理系统的研究、应用则刚刚起步不久。因此，本文开展了对高速公路沥 青路面路面管理系统算法的研究，主要包括二个方面的内容：1 、将遗传算法 应用与高速公路路面管理系统，对公路路面平整度的变化趋势预测。2 、应用 遗传算法的多目标规划能力，进行公路养护决策模型的研究。分别取得了良 好的效果。 自1 9 6 9 年首次提出组合预测方法以来，组合预测己经取得了很大发展。 理论研究和实际应用表明，应用组合预测模型比单个预测模型具有更多的好 处，能增强预测的稳定性，具有较高的适应未来预测环境变化的能力。因此 本文在阐述了国内外常用的组合预测模型的基础上，总结了现有的路面平整 度预测模型，将遗传算法应用于路面平整度模型的组合预测。分别建立了遗 传线性平整度组合预测模型，和遗传非线性平整度组合预测模型。在非线性 组合预测模型中，将遗传算法与神经网络结合，用遗传算法优化神经网络的 结构与权值、阈值。 高速公路路面养护决策优化分为单目标路面养护决策优化和多目标路面 养护决策优化。养护决策优化常用的优化方法可以分为两类：数学规划的优 化方法和人工智能的优化方法，后者主要是指遗传算法。数学规划的优化方 法在我国目前的高速公路中应用得最广，但对高速公路大规模路网路面养护 决策进行优化时，其存在解的不稳定性和运算速度慢的不足。 首先，本文分析了各种高速公路路面养护决策模型和优化方法，在此基 础上建立了高速公路路面养护决策多目标优化模型。然后，针对高速公路单 目标路面养护决策优化模型，提出了一种基于n s g a - i i 的遗传算法。在该算 法中，带精英策略的非支配排序的引入，使其具有较强的全局搜索能力和局 部搜索能力，有效地克服了简单遗传算法的过早收敛问题。同时，将该算法 应用于高速公路单目标路面养护决策优化问题中，取得了满意的结果。最后， 针对高速公路多目标路面养护决策优化模型，将n s g a - i i 应用于高速公路多 目标路面养护决策优化问题中，结果证明其性能优于传统的数学规划方法。 西南交通大学硕士研究生学位论文第1 l 页 关键词：遗传算法；组合预测；路面平整度预测；多目标遗传算法； 养护决策 西南交通大学硕士研究生学位论文第l li 页 a b s t r c t s i i 瞄1 9 8 0 s , t h ec o n s t r u c t i o no fh i g h - g r a d eh i g h w a yh a sd e v e l o p e dr a p i d l yi n o u rc o u n t r y w i t ht h e i n i t i a l l yc o m p l e t e d o fh i g h w a yn e t , m a i n t e n a n c e m a n a g e m e n tw o r ki sh e a v ym o r ea n dm o r e i nf o r e i g nc o u n t r y , p m sh a v e b e e n a p p r o v e dt ob ea e f f e c t i v et o o lu s e di nm a i n t e n a n c eh i g h w a yn e ta n dg i v eo v e r a l l p l a n n i n gi nf u n da l l o c a t i o n p a v e m e n tm a n a g e m e n ts y s t e mi si n t r o d u c e di n t oo u r c o u n t r yi n7 t hf i v ey e a r sp l a n , b u tr e s e a r c ha n da p p l i c a t i o no nh i g hp m ss t a rs o o i l t h i sp a p e rr e s e a r c ho na l g o r i t h mu s e di nh i g h w a yp m s t h i sp a p e ri n v o l v e s2 a s p c c b ：1 、u s e dg e n e t i ca l g o r i t h mi nh i g h w a yr o u g h n e s sc o m b i i l a t i o nf o r e c a s t m o d e l 2 、t h er e s e a r c ho fp a v e m e n tm a i n t e n a n c ed e c i s i o no p t i m i z a t i o nb a s i n go n g e n e t i ca l g o r i t h m s s i n c et h ef i r s tt i m ei tw a s p u tf o r w a r di n1 9 6 9 ，c o m b i n a t i o nf o r e c a s th a sm a d e g r e a td e v e l o p m e n t t h e o r yr e s e a r c ha n dp r a c t i c a la p p l i a n c eh a v ei n d i c a t e dt h a t c o m b m t i o nf o r e c a s th a sb e t t e rp r e c i s i o nt h a ni n d l 删o n e s t h i sp a p e rp r e s e n t s 2m e t h o d sf o rp a v e m e n tr o u g h n e s sc o m b m t i o nf o r e c a s t , o n ei sl i n e a rp a v e m e n t r o u g h n e s sc o m b m t i o nf o r e c a s t , w h i c hu s e dg e n e t i ca l g o r i t h mt oc o m p u t et h e w e i g h tf o re a c hs i n g l ep a v e m e n tr o u g h n e s sf o r e c a s tm o d e la n da n o t h e ri s n o n l i n e a rr o u g h n e s sc o m b i n a t i o nf o r e c a s t , i nt h i sm e t h o d ，g e n e t i ca l g o r i t h mi s u s e dt od e s i g nt h ef r a m e w o r k , t h r e s h o l da n dw e i g h to fn e t w o r kt h a tm a k e st h e t r a i n i n gp r o c e s st e n d i n gt og l o b a lo p t i m a s a t i s f i e dc h r o m o s o m e s 锄b ef o u n d a f t e rc h o o s i n g , a c r o s s i n ga n da b e r r a n c i n g t h e r ea r et w oo p t i m i z a t i o ns o l u t i o n st om a i n t e n a n c ed e c i s i o n , o n ei st h em a t h p r o g r a m m i n g , a n dt h eo t h e ri st h ea r t i f i c i a li n t e l l i g e n c ew h i c hm o s t l yr e f e r st o g e n e t i ca l g o r i t h m s t h o u g ht h em a t hp r o g r a m m i n gi su s e dw i l d l yi np m s d o m e s t i c a l l y , t h es o l u t i o n sa l el o wp r e c i s ea n du s e da l o to ft i m ew h e nt h ep r o b l e m i sc o m p l e xa tt h en e t w o r kl e v e l i ti sf o u n dt h a tt h er o b u s ts e a r c hc h a r a c t e r i s t i c sa n d p a r a l l e lh a n d l i n gc a p a b i l i t yo fg e n e t i ca l g o r i t h m sa l ew e l ls u i t e df o rp a v e m e n t m a i n t e n a n c ed e c i s i o no p t i m i z a t i o na tt h en e t w o r kl e v e l f i r s t l y , t h i sp a p e ri n t r o d u c e dt h es i n g l eg o a lo p t i m a lm o d e lo fp a v e m e n t m a i n t e n a n c ed e c i s i o na n dt h e m u l t i o b j e c t i v eo p t i m a l m o d e lo f p a v e m e n t m a i n t e n a n c ed e c i s i o na r ee s t a b l i s h e da f t e ra n a l y z i n ga l lk i n d so f p a v e m e n t 西南交通大学硕士研究生学位论文第l v 页 m a i n t e n a n c ed e c i s i o nm o d e l sa n di t so p t i m i z a t i o na p p r o a c h e sa tp r c s g n lt h e na h y b r i dg e n e t i ca l g o r i t h mi sp r o p o s e dt os o l v et h es i n 出g o a lo p t i m a lm o d e lo f m a i n t e n a n c ed e c i s i o nb a s i n go na l l a l 灿gt h e a d v a n t a g ea n dd i s a d v a n t a g eo f s i m p l eg e n e t i ca l g o r i t h m s t h eh y b r i dg e n e t i ca l g o r i t h mw i t hc h a r a c t e r i s t i c so f a d a p t i v ep s e u d o - p a r a l l e la n do p t i m u mm a i n t a i ni sc a p a b l eo fo v e r c o m i n g p r e m a t u r ec o n v e r g e n c ea n df i n dg l o b a lo p t i m ae f f i c i e n t l y m o r e o v e r , i ti sp r o v e st o b ee f f e c t i v et h r o u g hs o l v i n gt h e s i n g l eg o a lo p t i m a lp r o b l e mo fm a i n t e n a n c e d e c i s i o n a tl a s t , t h ec u r r e n ts t a t eo ft h er e s e a r c h o nt h eb a s i ct h e o r yo f g e n e t i c a l g o r i t h m sa b o u tm u l t i o b j e c t i v eo p t i m i z a t i o ni ss y s t e m a t i c a l l yp r e s e n t e d i n a d d i t i o n , g r e a ti m p o r t a n c e i sa t t a c h e dt ot h e i n t r o d u c t i o no ft h ee l i t i s t n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o f i t h m ( n s g a - i d ，w h i c hi sw i d e l yu s e di nt h e p r o b l e m so fm u l t i o b j e c t i v eo p t i m i z a t i o n a tt h es a m et i m e ，t h i sm e t h o di sp r o v e d t o b em o r ee f f e c t i v et h a nm a t hp r o g r a m m i n ga f t e rt h em u l t i o b j e c t i v eo p t i m a lm o d e l o fm a i n t e n a n c ed e c i s i o no p t i m i z e db yn s g a - i l 。 k e yw o r d s ：g e n e t i ca l g o r i t h m；c o m b i n a t i o n f o r e c a s t ；p a v e m e n t r o u g h n e s s f o r e c a s t ；m u l t i o b j e c t i v eg e n e t i c a l g o r i t h m ；p a v e m e n t m a i n t e n a n c e d e c i s i o n o p t i m i z a t i o n ； 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密d 使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名：硝g 宠0 日期：蚴矿以z 7 指导老师签名：阳访 e i 舞i - 瑚3 6 ； 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本文的创新点主要有： 1 、将组合预测模型应用于路面使用性能组合预测，克服了单预测模型 产生的过大误差，分散风险，利用不同预测模型的组合提高预测精度。 2 、分别将遗传算法引入路i 面- t 整度两种形式的组合预测。线性组合预测 和非线性组合预测。在线性组合预测模型种，主要采用遗传算法对单预测 模型的权值m 进行求解计算。克i j 及y 使用线性规划计算权值m 的弊端。充分 利用遗传算法在函数优化时对目标函数并无连续、可导，以及遗传算法可以有 效地在整个解空间进行搜索，其计算量较小，能较快地收敛到全局最优权系数 等优点，将遗传算法应用于神经网络非线性平整度组合预测模型，摒弃了神 经网络模型原有的梯度下降法求权值，阈值的算法。以预测值误差绝对值之， 和和平均误差百分比为目标，采用遗传算法对神经网络模型的拓扑结构，权 值，阈值进行自适应快速求解。计算结果表明遗传算法应用于线性、非线性 组合预测模型取得了良好的求解精度。 3 、使用保留精英策略的多目标遗传算法( n s g a - i i ) ，以路面养护决策效 益一费用模型为研究对象进行双目标寻优决策。 西南交通大学硕士研究生学位论文第1 页 1 1 论文的研究背景 第1 章绪论 在世界各国的经济发展中，公路运输起着极为重要的作用，投资也愈来 愈大，并朝着重型、密集、高速方向发展。世界上许多发达国家如美国、德 国、法国等，公路运输占有相当重要的位置，我国在改革开放以来，公路建 设取得了长足的发展，通车里程大幅度增加，技术等级不断提高，特别是“五 横七纵工程的实施，一个以高等级国家干线为骨架，连接大、中、小城市、 辐射乡村的公路网正在中国大地上形成。公路事业的发展，为振兴经济，提 高全国各族人民的物质文化生活水平，起到了极大的推动作用。图1 1 ，1 - 2 显示了我国公路通车总里程自1 9 9 8 年的1 3 0 万公里增加到2 0 0 6 年的3 8 0 万 公里，与此同时高速公路的通车里程自1 9 9 8 年的不足一万公里迅速增加至 4 5 万公里。 l ，0l ，2 0 0 02 0 0 l 2 0 0 22 0 0 32 0 0 42 0 0 52 0 口 图1 1 我国公路通车总里程增长幅度 1 9 9 8l ， 2 0 0 0o l2 0 0 2 2 0 0 32 0 0 42 0 0 52 0 0 6 西南交通大学硕士研究生学位论文第2 页 图1 - 2 我国高速公路通车增长幅度 在国民经济和公路交通事业的发展的同时，交通量的增加更加迅速，我 国公路网的逐步完善，公路管理部门面临的主要任务将从建设公路网转向养 护、改建、维护和改善现有公路网，实践己证明路面管理系统( p a v e m e n t m a n a g e m e n ts y s t e mp m sy l j 是进行公路养护管理的有力工具，一个有效的 p m s 应包含三个基本部分：( 1 ) 路面使用性能评价；( 2 ) 路面性能预测；( 3 ) 养护方 案优化决策。而针对路面管理系统各部分的算法也层出不穷。为了能够对路 面进行有效的管理，道路工作者将系统工程理论、工程技术经济理论及计算 机技术引入到路面管理过程中。路面管理系统的核心部分是各种评价、预测 以及优化决策算法在p m s 中的使用。随着计算机技术的发展以遗传算法为 代表的众多智能算法以其对复杂非线性问题的良好解决而越来越收到重视。 1 2 国内外研究现状分析 早在1 9 6 9 年，世界银行就开展了公路养护方面的研究工作。1 9 7 1 年完 成了第一阶段研究，开发了一个概念性的框图和公路施工养护及车辆运营费 用的第一代指标。1 9 7 0 - 1 9 7 2 年，世界银行在肯尼亚、加勒比地区、巴西和 印度先后完成了四项主要的道路用户费用的研究。经过许多国家的实践和改 进后，在这些经验基础之上建立了第三版公路设计与养护标准指标( h i g h w a y d e s i g nm a i n t e n a n c ei i i ，h d m 1 1 1 ) 2 。 1 9 7 0 年北美开始研究路面管理系统。1 9 8 1 年，美国联邦公路管理局出版 了 p r o c e e d i n g ) ) 一书，总结了开发和应用路面管理系统的1 3 个步骤。1 9 9 1 年，美国国会通过地面运输联运及效率法案，规定各州必须开发路面管理 系统等6 个管理系统。到1 9 9 0 年代初，全美5 0 个州及哥伦比亚特区都建成 和实施了某种路面管理系统德克萨斯大学开发的“城镇道路管理系统 是一 种专门为中小城镇设计的综合型p m s ，可同时在“网络级和“项目级 两 个层次上，提供有效的计算机管理手段。 目前，美国大多数城镇所采集的数据己能满足实施u r m s 的最低要求， 无需在数据准备上耗费太多的人力、财力。但城镇道路管理系统主要问题是 检测仪器、检测方法、评价指标的不统一。这对州与州之间的数据对比、经 验交流造成很大障碍。 亚利桑那州路面管理系统【3 j 主要是供给财政规划使用的网级优化系统。 这个系统最大的特点是首次成功的把马尔可夫决策过程引进网级路面管理系 统。它所考虑的是整个路网而不是个别路段或个别项目方案。把路网内的路 西南交通大学硕士研究生学位论文第3 页 段归类到不同的路况状态，并得到各种状态路面的比例。系统的目的是确定 以最低的费用保持规定的路面性能水平密西根州路面管理系统的最大特点是 提出了路面性能衰减曲线，并利用该方程和马尔可夫指标结合，预测路面的 使用性能，从而实现了养护费用的动态规划。 泰国路面管理系统( t h a i l a n dp a v e m e n tm a n a g e m e n ts y s t e m t p m s ) 在 1 9 8 4 年首次投入应用，到1 9 8 8 年已开始在全国路网上使用。它采用m b a s i c 语言编写。t p m s 根据对每2 0 0 米长的路况评价，一旦路况降到预先确定的 标准之下，就由模型选定处置措施，各种处治措施将根据一个权重指标来排 序，稍后才进行费用计算。但是泰国路面管理系统存在一个严重不足是不能 比较各养护策略的寿命周期费用以及标准的随意性。同时系统也不能预测路 面破损的发展。 我国对路面管理系统的研究始于1 9 8 0 年。最早的路面管理系统是交通部 公路研究所与英国合作在辽宁营口地区建立的沥青路面养护管理系统。“七 五 期间，国内开发了一系列路面管理系统，一些学者提出了我国普通公路 网的网级路面管理系统的基本构架和一些指标。同济大学和北京、广东的公 路管理部门，参考国外经验，合作建立了沥青路面使用性能评价指标、评价 方法和评价标准，提出了大、中修方案的选择方法。又研究了水泥混凝土路 面使用性能的评价方法和指标，在预测路面使用性能时采用了马尔可夫法， 初步分析了动态规划指标。 我国在英国路面评价系统、芬兰路面管理系统及世界银行公路投资效益 分析指标的基础上，开发研究c p m s ( c h i n ap a v e m e n tm a n a g e m e n ts y s t e m ) 系统1 4 1 1 5 1 6 7 。系统中路面使用性能评价、预测、养护决策指标都是基于回归 方法得到。c p m s 是包括硬件设备和计算机软件系统的技术实体，它包括路 面数据库及为数据库提供数据信息的数据采集设备，网级路面管理系统( 用于 了解路网质量、长期路面性能、长期养护资金需求及战略养护标准和方案) 和项目级系统( 用于养护工程项目设计及经济分析) 。c p m s 是一个复杂的决 策系统，它涉及了道路工程、工程经济、系统工程及计算机技术，是公路养 护工程师路网评价、路况性能分析、养护资金需求及养护资金优化分配的辅 助决策工具。 1 3 目前须解决的问题 1 、路面使用性能预测的质量在很大程度上取决于对预测对象以及各种客 观条件的认识水平和所采用方法的科学性。目前，尽管路面使用预测的模型 西南交通大学硕士研究生学位论文第4 页 和方法很多，但在实际运用上，由于区域差别较大，影响因素较多，而且各 种模型适用条件不同，很难找到一种既方便使用，结果又较为真实合理的方 法：另一方面，在预测实践中，对同一问题常采用不同的预测方法，不同的预 测方法提供不同的有用信息，其预测精度往往也不同，如果简单地将预测误 差较大的一些方法舍弃掉，将会丢失一些有用的信息，这种做法对信息是一 种浪费，应予以避免。一种更为科学的做法是，将不同的预测方法进行适当 的组合，从而形成所谓的组合预测方法。组合的主要目的是综合利用各种方 法所提供的信息，尽可能地提高预测精度，降低预测模型选择失败所带来的 风险。 2 、目前常用于高速公路养护决策优化的方法有数学规划优化方法与遗传 算法。数学规划优化方法主要有线性规划法、近似优化法、动态规划法等。 数学规划优化方法在中国目前的高速公路中应用得最广，但对高速公路大规 模路网路面养护决策进行优化时，其存在2 个不足：解的不稳定性，即当高速 公路养护预算资金有较小的变化时，优化的策略就会有较大的变化：当决策空 间较大时，数学规划方法运算速度非常缓慢。 1 4 本文研究的主要内容 本文将遗传算法引入了路面管理系统，介绍了遗传算法的生物学理论基 础。算法流程，主要算子的选择。本文分别采用了g m ( 1 ，1 ) 灰色理论预测 模型、时间序列预测模型，回归分析模型。对基于时间序列的路面平整度数 据进行拟合与预测。在单项预测模型的结果的基础上，分别使用遗传线性组 合预测模型和遗传神经网络组合预测模型对单一预测模型的结果进行组合预 测，以降低单个预测模型的使用风险，提高模型的预测精度。本文研究了基 于遗传算法的n s g a _ i i 模型，并将其引入路面养护决策的多目标优化问题。 通过实例计算表明。该方法优于动态规划，0 - 1 规划等传统方法。 西南交通大学硕士研究生学位论文第5 页 第2 章路面管理系统概述 2 1 路面管理和路面管理系统 路面管理是协调和控制与路面有关各项活动的一系列过程，其目的是使 路面管理部门通过这一过程能有效地使用资源( 资金、劳动力、机械设备、材 料、能源等) ，并以最低的资源消耗，提供并维持在预定使用期内具有足够服 务水平的路面嘲。路面管理工作的基本内容包括规划、设计、施工、养护、 路况监测和评价及研究等方面。 不同国家和地区的机构组织对路面管理系统有不同的定义。 文献恻认为路面管理系统( p a v e m e n tm a n a g e m e n ts y s t e m ，简称p m s ) 是通 过系统分析的方法，综合考虑技术、经济、社会和政治等各方面因素，协调 各项路面管理活动，促使路面管理过程系统化。美国从s h t o 的路面管理系统 指南将p m s 定义为：用于决策者在公路评价养护中寻求投资有效分配方案的 工具嘲。澳大利亚道路研究所则认为：p m s 是用于优化路面养护可用资源，包 含信息采集、信息分析和方案决策的管理方法，并把它分为网级( n e t w o r k l e v e l ) 系统和项目级( p r o j e c tl e v e l ) 系统两个不同的层次n o 】。 2 2 路面管理系统的组成 路面管理系统的运行一般都是通过尽可能多的调查来获取有关的路面状 况及其它数据，进行路面状况的评定，根据评定结果按一定的原则确定养护 对策，制定养护计划。并且通过路况预测来达到对策优化，以实现养护资金 和资源的最佳利用的管理目的。网级路面管理系统是涉及整个公路网的、用 来制定路网养护决策、确定路网养护需求和养护费用优化分配的宏观分析系 统，其决策基础是整个路网，目标是追求系统整体效益的最大化，其主要任 务是为公路管理部门进行关键性决策提供依据：项目级路面管理系统则是以 具体项目为研究对象，从技术和经济的角度分析养护方案的系统，系统往往 受到网级路面管理系统所确定的资金和时间条件约束，其目标是实现项目效 益的最优化，主要任务是为公路管理部门对某一工程项目进行技术决策提供 依据1 。 路面管理系统的主要内容 一般情况下用于公路的养护资金是有限的，因此公路规划和管理部门将 力图在技术和经济上对公路养护的各个可行方案从多方面进行比较，寻求最 西南交通大学硕士研究生学位论文第6 页 佳的建设养护方案，以使有限的资金发挥最大的经济和社会效益。这些技术 和经济上的分析一般从以下方面进行： ( 1 ) 对路面使用性能进行评定，了解路网的基本情况： ( 2 ) 利用预测模型，针对路网中不同的道路和交通条件，分析预测各路段 的道路未来的使用性能，提出道路改建计划： ( 3 ) 规定路网内各级道路的养护标准，预估路网的养护需求： ( 4 ) 分析达到预定要求的路网水平所需要的最小养护资金： ( 5 ) 利用优化决策模型对养护资金进行优化分配。确定路网中需要养护处 治的路段及处治时间和方法。分析不同投资水平对路网使用性能的影响，确 定最佳投资水平： ， 2 2 1 路面使用性能及路面使用性能预测 路面使用性能( p a v e m e n tp e r f o r m a n c e ) 的概念最早由美国各州公路与运 输工作者协会( a a s h t o ) 在1 9 6 2 年提出。对道路路面使用性能的一般理解是， 路面为保障公路运输车辆的安全正常行驶所应具备的能力和属性。对于高速 公路路面而言，还要满足车辆在一定的使用年限内高速、安全、舒适、经济 地行驶。分析研究高速公路路面使用性能，是进行路面使用性能评价和预测 的前提，也是高速公路路面养护管理决策的基础。根据我国高速公路的特点， 其路面使用性能主要包括以下方面：功能性能，外观性能，安全性能，结构 性能。 管理的关键是决策，而决策的前提是预测。为了决策的科学化、民主化， 提高决策的正确性，需要通过预测提供有关决策对象的未来状况的信息，分 析和判断这些信息，做出最优决策。所以预测的目的在于探索不确定事件的 发展规律和未来状况，为决策提供科学依据。预测的意义在于它能够为计划 和决策提供依据，是提高管理水平、改善计划统计工作的途径之一。路面在 使用过程中，其使用性能会随时间或行车荷载作用次数的增加而逐渐变坏。 当损坏达到某一标准时，路面就应该采取相关措施以恢复或提高其使用性能。 在路面管理系统中，为了得到路面养护方案，选择最佳养护改建对策，需要 了解何时采取养护和改建措施。这就需要预先估计路面使用性能的各项指标 在不同的外部条件下随时间变化的规律。为进行这种预估而建立的关系式， 称为路面使用性能预测模型。在路面管理系统中，使用性能预测是分析过程 中一个极其重要的方面，建立各种使用性能预测模型是路面管理系统最重要 的一项内容。 西南交通大学硕士研究生学位论文第7 页 2 2 2 路面养护决策 决策是一种系统的方法或过程，是对未来的行为确定目标，并从两个以 上可行方案中选取一个满意方案的分析决断过程。它通过对系统当前所处状 态的评估和未来发展的分析，判断、选择恰当的系统对策，以最大限度地满 足系统的要求n 羽。对于路面管理系统而言，“决策 的核心内容是在指定的预 算资金和其它资源的约束下，寻求最优养护策略，使得效益目标最大化( 路面 性能、维修效率设备使用率等) ，或是在一定的路面使用性能要求和资源限制 的约束下，寻求最优养护策略，使得费用目标最小化，使用效益最大化。 目前常用于高速公路养护决策优化的方法有，排序法、数学规划优化方 法等，数学规划优化方法主要有线性规划法、近似优化法、动态规划法等” 数学规划优化方法在中国目前的高速公路中应用得最广，但对高速公路大规 模路网路面养护决策进行优化时，其存在2 个不足：解的不稳定性，即当高速 公路养护预算资金有较小的变化时，优化的策略就会有较大的变化：当决策空 间较大时，数学规划方法运算速度非常缓慢。而排序法则很大程度上取决于人 的主观判断。遗传算法因其并行性、全局寻优等特点，非常适合高速公路大规 模路网路面的养护决策优化问题。 西南交通大学硕士研究生学位论文第8 页 第3 章遗传算法及其原理 3 1 遗传算法的特点 遗传算法是寻找求解优化问题的效率和稳定性之间的有机协调，计算方 法独特新颖，与传统优化相比有以下特点： ( 1 ) 对于优化问题，遗传算法不是直接处理决策变量本身的实际值，而是 对它进行的编码为运算对象。此编码处理方式，使优化计算过程可以借鉴生 物学中的染色体和基因等概念，通过模拟自然界中生物的遗传和进化等机理。 可以方便地应用遗传算子，特别是对于只有代码概念的优化问题，这种编码 处理方式显示出独特的优越性，使得遗传算法具有广泛的应用领域。 ( 2 ) 许多传统的优化方法是单点搜索，遗传算法在搜索空间中同时处理群 体中多个个体的方法，即同时对搜索空间多个解进行评估，多点并行搜索， 从而提高了搜索效率，有效地防止了搜索过程限于局部最优解，减少了陷于 局部最优解的风险，而且具有较大的求得全局最优的可能性。 ( 3 ) 遗传算法对目标函数不要求连续，更不要求可微，既可以是数学解析 所表示显函数，也可以是其他方式的隐函数，可以说对目标函数没有限制， 仅用适应度来评估个体。利用适应度来指导搜索向不断改进的方向前进。 ( 4 ) 很多传统优化算法通常使用确定性搜索法，从一个搜索点到另一个搜 索点有确定的转移方法和转移关系，这种确定性有可能是搜索难以达到最优 点。而遗传算法是属于自适应概率搜索法，采用概率变迁规则来指导搜索空 间。虽然也能够产生一些适应度不高的个体，但随着进化过程的进行，新种 群中会有更多的优良个体产生，继续沿最优解方向前进。 遗传算法具有隐含并行性，不但使优化计算提高搜索效率，而且易于 采用并行机制和并行高速计算，因此适合大规模复杂问题的优化。 3 2 遗传算法结构与操作 3 2 1 遗传算法的结构 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。与传统 搜索算法不同的是遗传算法从一组随机产生的初始解，称为“初始种群 开 始搜索过程，种群中的每一个个体是问题的一个解，称为“染色体”，“染色 体”由位串组成，位串中的每一位称为“基因 。衡量一个染色体的标准是“适 西南交通大学硕士研究生学位论文第9 页 应值一的大小，即“适应值 越大说明该解越好，染色体在后续的迭代中不 断地用适应值高的替代适应值低的染色体，这样的不断进化的过程称为遗传， 在迭代过程中，新一代染色体洙为子代) 是通过前一代染色体( 称为父代) 通过 交x ( c r o s s o v e r ) 或者变异( m u t a t i o n ) ：运_ 算形成的。形成新一代染色体后，根据 适应值的大小，部分后代得以保留，淘汰部分后代，从而保持种群大小是常 数。适应值高的染色体被保留的概率较高，这样经过若干代之后，算法收敛 于最好的染色体，它很可能就是问题的最优解或次优解。设p ( t ) 和c 粥分别 表示第t 代的父代和子代，遗传算法的一般结构可描述如下【b 】： 岫 t - o ； 随机产生初始种群p ( t ) ； 评估p ( t ) ； w h i l e 不满足终止条件d 0 b e g i n 重组p ( t ) 获得c ( t ) ； 评估； 从p ( t ) 和中选择p ( t + 1 ) ； t - t + 1 e n d e n d 一 3 2 2 遗传算法的操作与运算 在基本遗传算法中初始种群是随机产生的，通过遗传运算( 包括交叉和变 异) 产生后代，通过进化运算，即选择，在父代和子代中选择形成新一代种群， 遗传运算模拟了基因在每一代中的创造新后代的繁衍过程，进化运算则是种 群迭代的更新过程。 3 2 2 1 交叉操作 模仿生物的遗传过程，遗传算法引入了交叉算子，遗传算法中的交叉运 算是指两个染色体按某种方式相互交换部分基因，从而产生新的个体。在遗 传算法迭代过程中，交叉是产生新个体的主要方法。 交叉算子每次作用在种群中随机选取的两个个体上，通过两个个体部分 基因的交换产生的两个新个体称为子代，通常子代与父代不同，包含着两个 父代的遗传信息。交叉操作一般分为以下几个步骤： 西南交通大学硕士研究生学位论文第10 页 ( 1 ) 按交叉率在种群中随机选取参加交叉运算的染色体。 ( 2 ) 根据位串长度t g ，在【1 ，n 一1 】中随机选取一个或多个整数作为交叉位 置。 ( 3 ) 实施交叉操作，参加交叉的个体在交叉位置处相互交换各自的部分基 因。从而产生一对新的染色体。 在实施交叉操作时要解决两个问题，一是确定有多少个体需要进行交叉 操作，种群中进行交叉的个体数目与种群中的个体总数之比称作交叉率，一 般用表示，取值范围是0 5 0 8 。另一个问题是确定染色体中交叉点的位置， 交叉点的位置是随机的，可分为单点交叉、两点交叉和多点交叉几种方式【1 4 】 1 ) 单点交叉：假设做交叉运算的两个染色体表示的位串长为厅a 和b 为种群中两个染色体，其位串分别表示为： 以a l a 2 口一； ( 3 1 ) b ：b i b 2 饥 在1 到n - 1 中随机产生随机数f ，则a 和b 从第i + l 到咒段内字符相互交换， 产生两个新的染色体，即a 与b 的子代彳和曰，其字符串分别表示为 么：口l 口2 口j b i + l b i + 2 屯；( 3 - 2 ) b ：b i b 2 b i a i + 1 a i + 2 a 2 ) 两点交叉：假设做交叉运算的染色体a 、b 依然如前，在1 到咒产生 两个随机数f 、j ，然后对两个字符串从第f 位到第j 位所有字符进行交换，得 到新一代染色体a 和b 为 当i 一歹时，只交换一个字符，当f ，j 分别为1 和一时两字符串整体互换，等 于没有新的染色体产生，以上两种情况可以认为随机数产生无效，重新产生。 当字符串较短时可采用单点交叉，较长的字符串采用两点交叉，甚至多 点交叉，多点交叉的方法与两点交叉相似，此处不再详述。 3 2 。2 2 变异操作 变异也是生物界遗传进化的重要方式，遗传算法中的变异是指按照一定 的概率将染色体中的某位( 或几位) 基因改变，进而产生一个新的染色体。变 oo q 饥 m 心 一屯即 巩町 三 d嵋钆 一 一 n a 彳 b 西南交通大学硕士研究生学位论文第1 1 页 异操作作用于参加变异运算的染色体位串的等位基因上，变异操作的一般步 骤为： 按变异率( 一般取值为0 0 0 1 - 0 1 ) 在种群中选择参加变异的染色体。 ( 2 ) 根据位串长度n ，在1 1 厅i 中随机选取一个或多个整数作为随机产生变 异基因位。 ( 3 ) 实施变异操作，在需变异的基因位上改变基因值，从而产生新一代染 色体。对于二进制编码，变异运算有两种方式，一种是补运算，即原基因是 1 则改为o ，原基因是o 则改为1 。另一种是将该基因按o 5 概率随机产生0 或1 。对于其他的编码方式可以采用相应的变异操作方法，这些方法后面再 作介绍。 3 2 2 3 选择 选择是遗传算法的基本操作之一，目的是使适应度高的优良个体在下一 代中得以繁殖，体现“适者生存的自然选择原则，但是，单纯的按照适应 度大小实行选择，虽然保留了相对优良的染色体，却不一定有利于产生更好 的个体，因为最优解可能在某个劣解附近，这样丢掉了某个劣解却不利于实 施遗传操作去寻找最优解。所以，在遗传算中，并不是简单地利用适应度大 小进行选择操作，而是采用随机选择的方法，但是为了体现“适者生存”的 原则，保证适应度高的染色体被选择的概率大于适应度低的染色体。 按适应度比例选择是最基本的选择方法【1 4 1 ，其中每个个体被选择的期望 数量与其适应度和群体平均适应度比例有关，设毛，工：，工是给定的n 个染 色体所组成的种群，其中每个染色体具有相同的位串长度，其中而的适应度 函数值为，纯) ，且，“) 0 。 西南交通大学硕士研究生学位论文第12 页 图3 1 轮盘赌选择原理 定义只- 厂“) 厂 ，) 为染色体t ，的选择概率，显然，v ；札2 ，以 j - j 有只o 且只一1 。如果，“) f ( x ，) ，则 弓，所以可以保证优良 个体被选中的概率较大，同时劣质个体也有一定的被选择机会，以保证迭代 避免陷入局部最优。实现选择操作通常采用旋转轮法，即取一个周长为一个 单位长度的圆盘，按照种群中各个染色体选择概率的大小，将圆盘分成n 个 区间，如图3 1 所示。当转动轮盘停止后，箭头所指位置代表的染色体被选 中。操作中通常采用于上述操作等价的方法，设 互一只+ 最+ + 只一罗最，i 。l 2 ，靠故，只一e e ，。一1 选择 忍 操作时，在 o ，1 】区间内产生一个均匀分布的随机数r ，则选择染色体鼍被保 留到下一代种群。 3 3 遗传算法的理论基础 3 3 1 模式理论 在标准遗传算法( s g 砷中，所有个体都被表示为 o ，1 ) 字符串集，它们是 西南交通大学硕士研究生学位论文第1 3 页 优化问题的可行解，利用遗传算法在可行解集中搜寻最优解是通过对字符串 的复制、交叉和变异来实现的。通过对字符串实施一系列遗传操作，字符串 的形态会发生变化，特别是字符串中某一位或几位影响个体性质的字符的变 化会影响遗传操作的最终效果，j h o l l a n d 教授建立了一种揭示遗传操作中字 符串演变机理的理论，称为模式理论。它对遗传算法的设计有着重要的指导 意义。 3 3 1 1 模式的定义 在个体的字符串中引入一个通配符 ，这样二字字符集即扩展为三字 字符集【0 ，1 ，) ，由此可以产生如1 掌0 1 , 形式的编码串，这个字符串可以 代表四个体1 1 1 0 1 1 ，1 1 0 1 0 , 1 0 0 1 1 ，1 0 0 1 0 ，这个带有不确定字符