（道路与铁道工程专业论文）基于遗传算法的道路选线优化方法研究.pdf

摘要 本文从道路优化设计方面的理论出发，研究探讨道路选线问题，提 出了一个基于费用的道路选线优化模型。本研究旨在提高道路选线的效 率，优化道路选线结果，为道路设计工作者和相关领域的研究者提供新 的思路和方法，以使在道路选线工作中能够更加高效、科学、准确地找 寻到最优的新建道路空间线形方案。 本论文研究的模型是在给定新建道路起、终点的条件下，将道路选 线中需要考虑的各种因素转化为费用因素，确定一个以费用最小为最佳 的道路空间线形方案的优化问题。该模型以地理信息系统为平台，将原 始c a d 数字地形图分层整饰后导入g i s ，建立选线区域的空间数据库，并 根据模型的数据需求对不同的图层添加不同的属性字段。在此基础上， 采用遗传算法求解。 在地理信息系统中，首先根据控制点的不同，随机生成新建道路空 间线形优化方案的集合，并自动详细设计每一个候选方案的平面线形和 纵断面线形。接着计算道路候选方案本身导致的各项费用，包括基本建 设费用、土方工程费用、占地费用、桥梁隧道建设费用、养护费用；同 时计算道路使用者的费用，包括出行时间成本费用和车辆驾驶费用；对 道路穿过湿地和耕地时，施以一定的惩罚费用，使线路尽量避开这些高 费用区域。将以上各部分费用累加求和作为候选方案的总费用，在g is 中 自动化道路线形设计无法完全满足道路设计规范的所有限制，采用惩罚 函数加以弥补。 在遗传算法中，将候选方案作为种群人口，每个方案中的控制点作 为人口染色体中的基因，将方案所产生的费用值、使用者费用值、惩罚 函数费用值这三者设计为人口的适应度值。初始化种群人口，计算人口 的适应度值，经过遗传算法的选择、交叉和变异，逐代进化，达到终止 条件，得到一个最佳的新建道路的空间线形方案。 通过试验来检验模型，验证了该模型在道路选线中是有效的、可行的， 具有良好的应用价值。 关键词：道路线形优化；地理信息系统；费用优化模型；遗传算法 a b s t r a c t t h i sa r t i c l es t a r tf r o mt h et h e o r yo fr o a dd e s i g n i n go p t i m i z a t i o n ，s t u d yt h er o a d a l i g n m e n tp r o b l e m s ，c r e a tar o a da l i g n m e n to p t i m i z a t i o nm o d e lb a s e do nt h ec o s t f r o mt h ep e r s p e c t i v eo ft h et h e o r yo fh i g h w a y0 p t i m a ld e s i g n ，t h i sa r t i c l e r e s e a r c h e sa n dd i s c u s s e st h ep r o b l e m s0 ft h es e l e c t i o no fh i g h w a yr o u t e ， a n dp r o p o s e sac o s t b a s e dm o d e lf o ri t ss e l e c t i o n t h ep u r p o s eo ft h i sr e s e a r c h i st oi m p r 0 v et h ee f f i c i e n c y0 ft h es e l e c t i o no fh i g h w a yr o u t e ，o p t i m i z ei t sr e s u l t ，a n d p u tf 6 r t hn e wi d e a sa n dm e t h o d sf o rd e s i g n e r sa n dr e s e a r c h e r s ，s ot h a tt h e yc a nf i n d t h em o s to p t i m a l s p a c ea l i g n m e n tp l a n o f n e w l y c o n s t r u c t e dh i 曲w a ym o r e e f f i c i e n t l y ，s c i e n t i f i c a l l y ，a n da c c u r a t e l y w i t ht h eg i v e ns t a r t i n gp o i n ta n de n d i n gp o i n to fah i g h w a y ，t h em o d e lt r a n s f b m s v a r i o u sf a c t o r si n t e 盯e l a t e dr o a da l i g n m e n tt oc o s tf a c t o r ，i d e n t i f y i n gap r o b l e mo f o p t i m i z i n gh i g h w a ys p a c ea l i g n m e n tp l a nw i t ham i n i m u mc o s t b a s e du p o ng i sa sa p l a t f o r i n ，t h em o d e li m p o n st h e0 r i g i n a lc a dd i g i t a lt e r r a i nm a p s t r a t i f i e di n t og i s a f t e rg r o o m i n gt h eo r i g i n a lc a d d i g i t a lt e r r a i nm a p ，s e t su pr o a dr e g i o n a las p a t i a l d a t a b a s eo ft h er e g i o no fh i g h w a ys e l e c t i o n ，a d d sd i f f e r e n tf i e i d sp r o p e r t yt od i f f e r e n t l a y e r si na c c o r d a n c ew i t ht h er e q u i r e m e n to ft h em o d e ld a t a ，a n ds o l v e st h ep r o b l e mb y g e n e t i ca l g o r i t h m i nt h eg e o g r a p h i ci n f b r m a t i o ns y s t e m ，f i r s t ，a c c o r d i n gt ot h ec o n t r o lp o i n t ，as e r i e s o fn e wh i g h w a ya l i g n m e n ts p a c ep r o g r a m sa r er a n d o m l y g e n e r a t e d ， a n de a c h a l t e r n a t i v e sl i n e a rv e n i c a ls e c t i o na n dh o r i z o n t a la l i g n m e n ti sd e s i g n e da u t o m a t i c a l l y i nd e t a i l t h e na l lt h ec o s tr e s u l t e df r o mt h ec a n d i d a t er o a da l i g n m e n ti t s e l fs h a l lb e c a l c u l a t e d ，i n c l u d i n ge s s e n t i a lc o n s t r u c t i o nc o s t ，e a r t h w o r k sc o s t ，c o v e r a g ec o s t s ，t h e c o s t0 fb r i d g eo rt u n n e lc o n s t r u c t i o n ，m a i n t e n a n c ec o s t ；a tt h es a m et i m e ，t h e e x p e n d i t u r eo fr o a du s e r s s h a l lb ec a l c u l a t e d ，i n c l u d i n gt h ec o s t0 ft r a v e l i n gt i m ea n d v e h i c l e d r i v i n gc o s to fd r i v i n g ；p e n a l t yf e e ss h a l lb ep a i d ew h e ni ft h er o a dp a s s e s t h r i l lt h r o u g ht h ew e t l a n d sa n da r a b l el a n d ，i m p o s es o m ep u n i s h m e n tc o s t s ，s ot h a tt h e a l i g n m e n ta sf a ra sp o s s i b l et ot r yt 0a v o i dt h e s eh i g h c o s tr e g i o n s t h et o t a lc o s th e r e a b o v e ，w i l lb ep a r t0 ft h ec o s to ft h ec a n d i d a t ea l t e r n a t i v ep l a n s ，a sac u m u l a t i v es u m o ft h et o t a lc o s to ft h ep r o g r a m ，i ng i sw h e nt h ea u t o m a t i ch i g h w a ya l i g n m e n td e s i g n c a nn o tf h l l ym e e ta l lt h er e s t r i c t i o n so ft h ed e s i g ns p e c i f i c a t i o n s ，p u n i s hf u n c t i o n s h a l lb ea p p l i e dt 0m a k eu p i ng e n e t i ca l g o r i t h m ，w er e g a r dt h ea l t e r n a t i v ep l a n sa s p o p u l a t i o n ，t h ec o n t r o l p o i n t si ne a c hp l a na sg e n e si np o p u l a t i o n sc h r o m o s o m e ，a n dt h ec o s to ft h ep l a nt h e u s e r s e x p e n d i t u r ea n dt h ep u n i s hf u n c t i o nf e e sa st h ef i t n e s sv a l u eo ft h ep o p u l a t i o n a no p t i m a l h i g h w a ya l i g n m e n tw i l l b ew o r k e do u tb y i n i t i a l i z i n gp o p u l a t i o n ， c a l c u i a t i n gt h ep o p u i a t i o n sf i t n e s sv a l u e ，s e l e c t i n g ，o v e r l a p p i n ga n dt r a n s f o r m i n g g e n e t i ca l g o r i t h mt od e v e l o pa n dm e e tt h ec o n d i t i o n s t h em o d e lo ft h eh i g h w a ya l i g n m e n ts e l e c t i o ni se f f e c t i v e ，f 色a s i b l et h r o u g hd i g i t a l t e s t s ，a n di tp r o v e st oh a v eg o o da p p l i c a b l ev a l u e k e y w o r d s ：o p t i m i z a t i o no fr o a da l i g n m e n t ；g i s ；c o s to p t i m i z a t i o nm o d e l ；g a m 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：固彬 日期：1 7 年 月2 岁日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：同林 日期：知。7 年罗月衫日 导师签名：弋丸至三 日期：叫年厂月2 铲日 1 1 引言 第一章绪论 我国公路水路交通“十一五 发展规划重点提出，到2 0 l o 年，国家高速公路网 骨架基本形成，国省干线公路技术等级进一步提高。至2 0 0 7 年年底，贯通“五纵 七横 1 2 条国道主干线；2 0 1 0 年，基本建成西部开发8 条省际公路通道；重点建 设高速公路网规划中的“五射两纵七横 共1 4 条路线，并力争到2 0 1 0 年基本贯 通1 - 2 1 。 截止2 0 0 7 年底，我国高速公路通车总里程达到了5 3 万公里。基本完成“五 纵七横”1 2 条国道主干线的建设任务，国家高速公路网规划采用放射线与纵横网 格相结合布局方案，由7 条首都放射线、9 条南北纵线和1 8 条东西横线组成，简 称为“7 9 1 8 ”网，总规模约8 5 万公里，其中主线6 8 万公里，地区环线、联络线 等其它路线约1 7 万公里。 我国公路事业发展速度迅猛，通车总里程持续增长，但同时在发展过程中也暴 露出不少的问题。比如过分强调路线线形高指标，忽视经济效益和环保因素；设 计时重点考虑建设阶段的造价因素，而公路建成后运营阶段的养护费用和道路使 用者费用考虑较少等。 现代公路路线的最优设计已突破传统意义上的概念，不仅要求通行时间短、工 程费用少，而且要与周围的社会、人文、自然环境协调。在这种可持续发展战略 思想指导下的公路规划和勘测设计中，除要考虑地形、地质、水文、交通量等常 规因素，还要考虑沿线的经济、人文自然景观、生态环境等因素。因此公路路线 方案比选是一个考虑社会、经济、工程、环境等因素的多目标空间决策问题b 1 。 近几年发展起来的遗传算法，是一种模拟生物进化的自适应随机搜索方法，由 于它对问题本身的限制较少，对问题目标函数和约束条件既不要求可微也不要求 连续，仅要求该问题是可计算的；同时，它的搜索始终遍及整个解空间，能找到 近乎全局最优解。遗传算法对所要求的解没有太多的数学要求，利用它的进化特 性，它在解的搜索中不需要了解问题的内在性质，可以处理任意形式的目标函数 和约束，无论是线性的还是非线性的，离散的还是连续的，甚至混合的搜索空间。 因而在道路选线优化方面具有广泛的应用价值hr 引。 1 2 论文研究的目的和意义 因为道路选线的复杂性，传统的人工道路选线设计需要有经验的工程师反复 地根据各种因素考虑并找出若干候选线路或线路段，然后通过综合评价最终选择 出一条较为满意的线路。然而连接两点之间的线路可以有无数条，所以人工选线 设计只能从有限的几条中找到一条基本满足要求的线路，而不能找到最优的或者 说接近最优的线路。 虽然以图形交互技术为主要特征的多种计算机辅助设计方法的普及应用极大 改变了选线设计面貌，勘测设计一体化的目标已基本达到，这使得选线设计工作的 速度、质量都得到很大程度提高，但是，这并没有从根本上解决选线设计中方案 决策周期长、评价指标单一、设计劳动强度大以及对采用方案的科学性缺乏有效 论证等问题。这些问题得从选线设计自动化、智能化的角度加以解决，通过利用 计算机技术实现大量方案自动生成和评价，从而能快速提供真正具有说服力的方 案，实现科学决策3 。 现今地理信息系统、全球定位系统、遥感、航测等空间信息技术和计算机技 术的发展和普及，以及国家、省级基础地理信息数据建库工程的启动，为解决公 路路线方案确定这一多目标空间决策模型提供了先进的技术支持和理论方法。本 论文的研究就是借助于地理信息系统、遗传算法的相关理论、方法和技术分析手 段，通过理论分析、模型建立、模型验证等步骤，在g i s 基础上，对拟定路线方 案进行科学评价。达到为公路可行性研究和初步设计阶段的路线方案比选提供必 要的、有效的决策支持信息。 本论文的研究，旨在提高路线设计方案决策的科学性和规范性以及决策方案 的经济、社会和环境效益，尽可能摆脱决策者的经验和主观判断局限性，这在目 前我国增加公路交通基本建设投资、加快高等级公路建设进度的大好形势下，对 合理利用资金、提高公路建设投资综合效益等具有十分重要的意义。 1 3 国内外研究发展现状 1 3 1 国外的研究与发展概况 路线优化设计技术是随着计算机技术的发展和应用数学的日趋成熟而逐步发 展和形成的。自6 0 年代以来，国外一些发达国家广泛开展了这方面的开发研究。 美国、前苏联、日本、前联邦德国、丹麦、法国、英国、西班牙等国先后推出了 较成熟的纵断面优化程序系统。联合国经济合作与开发组织于1 9 7 3 年曾对英国、 法国、前联邦德国和丹麦四国的路线优化程序，在意大利西西里岛的一条高速公 路1 4 k m 长的一段已建成道路上进行联合试验。这次测试结果表明，纵断面优化设 计可以节约土石方费用8 。1 7 ，平均约1 0 。充分论证和肯定了路线优化技术 的研究及其巨大的应用价值，使路线优化设计的研究工作更为活跃。在西西里岛 的联合试验之后的十多年时间内，许多国家在纵断面优化设计技术的基础上，又 对一定范围内的公路平面线形和空间立体线形的优化技术进行了研究，并取得了 2 初步成果。到目前为止，路线优化设计在理论和应用上整体而言仍处在研究探索 阶段，表1 1 列出了从事路线研究的主要学者及优化研究的数学方法。 表1 1 国外路线优化研究概况 1 优化 方法类别研究者及时间 目标 w a n ( 1 9 9 5 ) ，h o w a r de ta 1 ( 1 9 6 8 ) ，t h o m s o na n ds y k c s ( 1 9 8 8 ) ，s h a w 微分法 a n dh o w a r d ( 19 8 la n d1 9 8 2 ) 平 面 o e c d ( 1 9 7 3 ) ，t u m e ra n dm i l e s ( 1 9 7 1 ) ，a t h s a l l a s s o u l i sa n d 线 网络优化法 形 c a l o g e r o ( 1 9 7 3 ) ，p a r k e r ( 1 9 7 7 ) ，t “e t s c h ( 1 9 8 7 aa n d1 9 8 7 b ) 动态规划法 h o g a n ( 1 9 7 3 ) a n dn i c h o l s o ne ta 1 ( 19 7 6 ) 遗传算法j o n g ( 1 9 9 8 ) 枚举法e a s a ( 1 9 8 8 ) 纵 动态规划法 p u y h u a r t e ( 1 9 7 3 ) ，m u r c h l a n d ( 1 9 7 3 ) c o he ta 1 ( 1 9 8 8 ) a n df w a 断 ( 1 9 8 9 ) 面 线性规划法 r e v e l l ce ta 1 ( 1 9 9 7 ) a n dc h a p r aa n dc a n a l e ( 1 9 8 8 ) 线 形h a y m a n ( 1 9 7 0 ) ，g o he ta 1 ( 1 9 8 8 ) ，r o b i n s o n ( 1 9 7 3 ) ，f w a ( 1 9 8 8 ) a n d 数值搜索法 m i n e r v a ( o e c d ，l9 7 3 ) 遗传算法 j 0 n g ( 19 9 8 ) ，f w a ( 2 0 0 2 ) 动态规划法 h o g a n ( 1 9 7 3 ) a n dn i c h o l s o n e t a l ( 1 9 7 6 ) 平 纵 数值搜索法 c h e we ta 1 ( 1 9 8 9 ) 线 两阶段法 p a r k e r ( 1 9 7 7 ) a n dt r i e l s c h ( 1 9 8 7 a ) 形 遗传算法 j o n g ( 1 9 9 8 ) ，j h a ( 2 0 0 0 ) a n dk i m ( 2 0 0 1 ) 这些优化方法多偏重于利用计算机的强大的数据计算功能，在计算过程中具 有难以克服的缺陷。枚举法是对问题可行区域进行尽可能多点组合的搜索，对目 标函数没有太多的数学性质要求，计算策略简单，却难以利用有效的已知设计信 息，计算量巨大；动态规划法的计算量与网格数目具有指数关系，网格密度的提 高会造成计算量增加巨大，而且为了避免状态变量的维数障碍而将变坡点里程等 距划分，导致了寻优能力的减弱；解析搜索法具有收敛速度快和处理约束条件方 便的优点，却易陷入局部最优，且要求目标函数连续可导，在工程情况复杂目标 函数不连续可导时便无法求解。 进入2 0 世纪9 0 年代后，如遗传算法的现代计算方法有了进步的发展，并开 始应用于路线优化研究中。 最早将遗传算法引入高速公路选线优化的是马里兰大学的j y h c h e r n gj o n g ， 3 1 9 9 8 年在其博士论文中哺1 ，在分析了现有优化方法的不足之处后，引入了遗传算法。 随后在美国、英国和新加坡都开始出现这方面的研究，研究范围从纵断面优化、 平面优化到平纵断面的联合优化，其目标函数建立不仅考虑了土石方，而且把隧 道、桥梁、交叉道口等因素考虑进去，同时为了目标函数的快速准确建立，把g i s 和计算机可视化技术也引入优化系统阳1 利，该方法的基本原理是：首先自动生成连 接起、终点的大量方案组成方案集合，然后对各方案进行费用和约束满足情况评 价，从方案集合中选出较优的方案进行杂交以产生下一代方案集合，如此反复计 算，直到评价指标没有较大改进为止。 在这方面的研究中，美国摩根马州立大学和马里兰大学m a n o jk u m a rj h a 、 j y h c h e m gj o n g 等人的研究比较引人注目，j o n g 等开发了同时优化三维空间线形 的进化模型n5 1 ，该模型重点强调遗传算法在线形优化中的应用和实现，算法中设计 了以控制点坐标为基因构成种群中个体的染色体，用五类方法给定初始线形方案， 以保证算法中原始种群的信息丰富性，定义四种突变和四种交叉操作的算子，以保 证遗传算法在线形优化过程中的高效性能。j h a 等介绍了他们在基于遗传算法和 g i s 进行线路优化的成果，并展示了4 个演示实例。在其开发的系统中用c 语言实 现了方案产生、费用计算和遗产算法优化等算法，其中费用计算是联合g i s 和c 语 言实现的，可以实现平面、纵断面单独优化或三维空间曲线的联合优化，在展示的 实例中考虑了土方、用地、路面、交通事故、时间消耗等费用，考虑了小范围选 线时应用情况，具有一定的适用性和借鉴价值。k i m 等提出了一个阶梯式的遗传算 法求解模型，以提高优化模型的计算效率。该方法先利用模型，选取小数量的控 制变量进行一次求解，以此为基础，按一定的原则选取断点，将研究的区域划分 为多个合适的子区域，再进行分段的线形优化。j h a 等在模型的基础上，引入了可 达性、亲近性、土地利用的变化三个因素的量化公式，探讨了它们对于道路线形 的影响，证实了它们的重要性。j h a 等利用计算机可视化技术将道路最优线形直观 地变现出来，以此作为评价道路方案优劣的基础【l 昏1 8 1 。 1 3 2 国内的研究与发展概况 国内自1 9 7 9 年以来，同济大学、西安公路交通大学、重庆交通学院与重庆公 路研究所、交通部第二公路勘察设计院等先后对公路的纵断面优化技术、平面及 空间线形优化技术等进行了研究，开发了各自的优化程序，这些系统经过试算证 明其优化效果是令人满意的。由于优化过程涉及到的因素很多，特别是优化目标 的价值难以确定等各种影响，国内的优化设计至今尚末广泛地应用到实际的工程 设计中，还有待于进一步研究、完善和提高n 引。 国内将遗传算法引入到道路选线领域的时间稍晚，许金良的基于遗传算法的 公路纵断面优化阻叫，提出了一种基于遗传算法的纵断面优化方法，这种方法可以 4 在一个可行域中自动搜索一个最优或较优解，该方法具有全局解空间搜索能力， 从而实现了全局寻优的目的，对道路优化设计是有效、可行的。樊涛的基于遗传 算法的路基土石方数量估算方法陋，介绍了一种自动选择地面点的方法，连接这 些所选地面点的模拟地面线较好地吻合了实际地面线，将模拟地面线和实际地面 线之间的误差平方和的最小化作为该方法的目标函数，而将遗传算法作为寻找该 方法目标函数最优解的工具。陈秀玲心2 1 的基于遗传算法的公路纵断面优化设计方 法介绍了用遗传算法实现纵断面优化设计的具体方法步骤，并编制出了计算机应 用程序，证明了遗传算法在纵断面优化设计中的可行性及全局寻优的性能。冯晓 的基于遗传算法的公路纵断面优化应用分析，提出了一种基于遗传算法的计算机 优化方法，用数学模型将纵断面线形简化为一个点序列，以填挖总量为目标函数， 同时采用约束条件来控制线形，对变坡点序列进行优化，在实际工程中适当增加 约束条件，设计出更合理的线形。 马庆雷心们的基于遗传算法的公路平面优化，提出了一种基于遗传算法的公路 平面线形优化方法，将遗传算法应用于公路平面优化设计，根据平面初始解建立 一个可行域，然后对可行域中的可能解用一个评价函数( 适应度) 来度量，利用交叉、 变异算子在可行域中选择最优解。 陈艳艳他钉强调利用遗传算法自动搜索新建道路方案进行比选，并将地理信息 系统与遗传算法相结合，进行交通系统道路选线决策。选线过程中，考虑与道路 长度相关的费用，与道路位置相关的费用和与道路使用者相关的费用。杨忠振心町 利用遗传算法，从改善道路网的服务水平、工程造价和土方费用的角度优化新建 道路的空间走向，应用g i s 开发了在数字地形上自动生成新建道路走向初始方案的 方法。提出了优化新建线路空间走向的目标函数，并设计了相应的遗传算法。杨 忠振等瞳7 2 刚结合道路设计理论与交通规划理论，以地理信息系统为平台，开发道 路选线优化模型，该模型是一个费用指向的优化问题，最小化费用目标函数中包 括道路建设费用、土方工程费、道路交通诱发的环境污染的不经济费用，o d 交通 在路网中总走行时间的时间费用等。 1 3 3 已有研究特点总结 上述国内外文献中所论述的道路线形优化问题，表达了这样一个概念：在给 定的起、终点之间，众多因素的综合考虑下，寻找一条经济上最优的道路空间线 形。这是一个十分复杂的问题，两点之间存在的道路空间走向方案是有无穷多的， 并且选线中考虑的各种因素属性不同，各种因素相互影响，相互制约，因此道路 线形优化问题是个错综复杂的问题。 目前，研究的焦点是将道路选线问题抽象表达为一个合理的数学优化问题， 讨论如何合理建立道路选线优化模型的问题。 5 总结上述国内外文献，目前已有的基于遗传算法的平纵面优化模型还存在如 下缺陷： 目标函数较为单一，考虑的因素还不够全面，实际上选线设计涉及因素众多， 且各种因素属性不同，怎样合理确定不同属性因素对道路线形的影响程度，这 仍然是个难点问题。 没有有效地利用g i s 建立选线区域的空间数据库，道路选线需要在真实准确的 地形图上进行，将地形图中的各种不同因素，分层整合后建立空间数据库，并 采用遗传算法结合地理信息系统进行平纵面的优化方面分析，目前这方面的研 究还较少。 1 4 论文的主要研究工作 1 )考虑道路选线中的各种因素，将这些不同属性的因素全部其转化为费用因素， 在此基础上，设计基于费用的道路选线优化模型。 2 )设计求解该选线优化模型的遗传算法，包括基因的编码、初始种群的产生、 交叉算子和变异算子的选择、以及约束条件处理与停止规则。 3 )在g i s 中分析、实现并且求解该道路选线优化模型，并且尽可能详细的设计 出候选道路方案的平面和纵断面线形。 4 )在g i s 中建立道路选线区域的空间数据库，根据道路选线模型的数据需求， 将选线区域分成不同的数据层，同时对传统地形图的图面数据赋以相应的属性值。 1 5 论文的结构 本论文共由七章构成。 第一章绪论介绍论文的研究目的、意义、研究背景、国内外的研究概况及 解决的关键问题。 第二章遗传算法的基本原理与实现系统介绍了遗传算法的相关理论以及道 路选线模型建立过程中遗传算法的设计。 第三章道路选线优化模型的设计将道路选线中要考虑的各种不同属性的因 素转化为费用属性，建立与道路位置相关的费用模型。 第四章道路选线优化模型的分析实现根据第三章的费用模型，在g i s 中实 现上述模型，包括初始方案的产生、平曲线、竖曲线、以及横断面 在g i s 中的实现。 第五章道路选线区域空间数据库设计详细介绍了在a r c g i s 平台上，基于 g e o d a t a b a s e 模型道路选线区域空间数据库的设计过程。 第六章模型的试验及评价 第七章结论与展望 6 第二章遗传算法的基本原理 遗传算法起源于对生物系统所进行的计算机模拟研究。早在上世纪4 0 年代， 就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进 行了生物的进化过程模拟、遗传过程模拟等研究工作。2 0 世纪6 0 年代末期到7 0 年代初期，美国m i c h i g a n 大学的j o h nh o l l a n d 与其同事，学生们研究形成了一个 较完整的理论和方法，从试图解释自然系统中生物的复杂适应度过程入手，模拟 生物进化的机制来构造人工系统的模型，受到这种生物模拟技术的启发，创造出 一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术一遗 传算法。随后经过2 0 余年的发展，取得了丰硕的成果和理论研究的进展瞳9 1 。 2 0 余年来，遗传算法的应用无论是解决实际问题还是建模，其范围不断扩展， 这主要依赖于遗传算法本身的逐渐成熟。近年来，许多冠以“遗传算法 的研究 与h o l l a n d 最初提出的算法已少有雷同之处，不同的遗传基因表达方式，不同的交 叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，这些改进方法产 生的灵感都来自大自然的生物进化。 2 1 遗传算法概要 2 1 1 遗传算法的基本思想 遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经 过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组成。每个个体实际上是 染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体，即多个 基因的集合，其内部表现( 即基因型) 是某种基因组合，它决出了个体的形状的外部 表现，如黑头发的特征是由染色体中控制这一表达特征的某种基因组合决定的。 因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编 码的工作很复杂，我们往往进行简化，如二进制编码。初代种群产生之后，按照 适者生存和优胜劣汰的原理，逐代( g e n c m t i o n ) 演化产生出越来越好的近似解。在 每一代，根据问题域中个体的适应度( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借助于自 然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ， 产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群 比前代更加适应于环境，末代种群中的最优个体经过解码( ( d e c o d i n g ) ，可以作为问 题近似最优解口0 | 。 7 第一步 第三步 步 第五步 七步 图2 1 遗传算法的主要过程示意图 2 1 2 遗传算法的特点 随着问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解 决搜索和优化的通用方法，遗传算法正是为我们提供了一个有效的途径，它不同 于传统的搜索和优化方法。主要区别在于： 1 ) 有组织、自适应和自学习性( 智能性) 。应用遗传算法求解问题时，在编码 方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组 织搜索。由于基于自然的选择策略为“适者生存、不适应者被淘汰 ，因而适应度 大的个体具有较高的生存概率。通常，适应度大的个体具有更适应环境的基因结 构，再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。进 化算法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环 境的特性的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先 描绘问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此， 利用遗传算法的方法，我们可以解决那些复杂的非结构化问题。 2 ) 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点， 而不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的( i n h e r e n t p a r a l l e l i s m ) ，即遗传算法本身非常适合大规模并行。二是遗传算法的内含并行性 ( i m p l i c i tp a r a l l e l i s m ) 。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解 空间内的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种 群规模n 成比例的计算，但实质上已进行了大约n 了次有效搜索，这就使遗传算法 能以较少的计算获得较大的收益。 3 ) 遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目际函 数和相应的适应度函数。 2 2 编码方法 在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操 作而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种 遗传操作来达到优化的目的，这是遗传算法的特点之一。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键 步骤。编码方法除了决定了个体的染色体排列形式之外，它还决定了个体从搜索 空间的基因型交换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、 变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何 进行群体的遗传进化运算以及遗传进化运算的效率。 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方 法。我们从具体实现的角度出发介绍一下二进制编码方法和浮点数编码方法。 1 ) 二进制编码方法 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集 是由二进制符号o 和l 所组成的二值符号集1 0ll ，它所构成的个体基因型是一个 二进制编码符号串。 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取 值范围是【u 岫，u 一】，我们用长度为f 的二进制编码符号串来表示该参数，则它总共 能够产生2 。种不同的编码，使参数编码时的对应关系如下： 9 o o o 0 0 0 0 0 o 0 0 0 0 0 0 0 = o 专u r i l i 。 o 0 0 0 ( ) 0 0 0 o | d c l 0 0 0 0 l = l u m i 。+ 万 1 1 1 1 1 1 l l 1 1 1 1 1 1 1 1 = z 一1 专【，眦 则二进制编码的编码精度为： 艿= 警 ( 2 1 ) 2 。一l 一7 假设某一个个体的编码是： x ：岛包一。包一2 吃包 则对应的解码公式为： l z = u 础n + ( 包2 卜1 ) f ：l u 懈一u m i n 2 7 一l ( 2 2 ) 2 ) 浮点编码方法 对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个 体时将会有一些不利之处。 首先是二进制编码存在着连续函数离散化时的映射误差。个体编码串的长度较 短时，可能达不到精度要求；而个体编码串的长度较长时，虽然能提高编码精度， 但却会使遗传算法的搜索空间急剧扩大。 其次是二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对 问题专门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一 些宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。 为改进二进制编码方法的这些缺点，人们提出了个体的浮点数编码方法。所谓 浮点数编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个 体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真 实值，所以浮点数编码方法也叫做真值编码方法。 例如，若某一个优化问题含有5 个变量x j ( f = 1 ，2 ，5 ，) ，每个变量都有其对应的 上下限【。巩。，】，则x ： 就表示一个体的基因型，其对应的表现型是：舴 5 8 0 ，6 9 0 ，3 5 0 ，3 8 0 ，5 0 0 t 在浮点数编码方法中，必须保证基因值在给定的区域限制范维内，遗传算法中 所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值 l o 也在这个区间限制范围内。再者，当用多个字节来表示一个基因值时，交叉运算 必须在两个基因的分界字节处进行，而不能在某个基因的中间字节分隔处进行。 浮点数编码方法有下面几个优点： 1 ) 适合于在遗传算法中表示范围较大的数。 2 ) 适合于精度要求较高的遗传算法。 3 ) 便于较大空间的遗传搜索。 4 ) 改善了遗传算法的计算复杂性，提高了运算效率。 5 ) 便于遗传算法与经典优化方法的混合使用。 6 ) 便于设汁针对问题的专门知识的知识型遗传并子。 7 ) 便于处理复杂的决策变量约束条件。 根据道路选线模型的特点，我们采用浮点编码的形式，见式2 3 a = 【 ，五，乃，以，：，乃州，五。】= b ，y n ，z n ，) ， ，z 其中：人为染色体，a 为基因，工矿y a 、z n 分别为第j 个交点的横、 高程。染色体内的基因和其交点坐标关系见式2 4 ： 五i _ 2 = 。； 乃h = y a ； 如= z a ： 2 3 适应度函数 v i = l ，n v f = 1 ，疗 = 1 ，n ( 2 3 ) 纵坐标及 ( 2 4 ) 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来 度量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有 更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少， 甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概念来度量群体中 各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适 应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代 的概率就相对小一些。度量个体适应度的函数称为适应度函数( f i t n e s s f u n c t i o n ) 。 1 ) 目标函数与适应度函数 遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有 关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个 体适应度的一般过程是： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型。 ( 2 ) 由个体的表现型可计算出对应个体的目标函数值。 ( 3 ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应 度。 最优化问题可分为两大类：一类为求目标函数的全局最大值，另一类为求目标 函数的全局最小值。对于这两类优化问题，可以作解空间中某一点的目标函数值 厂( 工) 到搜索空间中对应个体的适应度函数值f ( x ) 的转换： 对于求最大值问题，作下述转换： f c x ，= x + c m i l l ；：二；：乏：三三 c 2 5 ， 其中，。为一个适当地相对较小的数。 对于求最小值问题，作下述转换： m = 。 x 三；然乏 眨6 ， 其中，c 呱为一个相对较大的数。 道路选线模型是一个基于费用最小的优化问题，根据第三章中费用模型公式的 要求，选线优化模型的适应度函数采用式3 6 的形式。 2 4 选择算子 在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多的 机会遗传到下一代，而对生存环境适应程度较低的物种遗传到下一代的机会就相 对较少。模仿这个过程，遗传算法使用选择算子( 或称复制算子，r e p r o d u c t i o n o p e r a t o