（计算机应用技术专业论文）遗传算法在公路路线智能决策系统中的应用研究.pdf

摘要 公路选线在公路设计工作中占有重要的地位。选线质量决定着公路的工程费用和维 护费用，而且与交通安全关系很大。传统的公路选线大部分由人工完成，存在主观性缺 陷，而且长期的线形设计，使得设计人员凭借经验设计线形，缺乏创新。随着计算机技 术的普及和优化技术的迅速发展，使得计算机智能选线成为可能。本文结合公路选线的 现状和最优化技术的发展趋势，以解决上述问题为目标，对智能选线展开了研究。 从智能选线的内涵出发，选取特点鲜明的遗传算法作为优化技术，以地理信息系统 ( 简称g i s ) 为平台，对给定区域内，无控制点和有控制点两种情况下的平面线形进行 优化。总结了遗传算法的基本原理、特点和关键的实现技术，并根据公路选线的特点， 确定了遗传算法的流程和遗传过程中的遗传参数和遗传算子。对系统的运行数据进行了 处理，实现了遗传算法与g i s 平台接口，并编制了程序。 本文的技术特色有两个：1 自定义了遗传算法的适应度函数。2 首次在路线优化过 程中加入了控制点，使得智能选线更贴近实际。 通过系统实验验证，本系统能够达到平面线形优化的要求，具有实用价值。 关键字：遗传算法，优化技术，控制点，适应度函数 a b s t r a c t h i g h w a ya l i g n m e n t sh o l da l li m p o r t a n tp o s i t i o ni nt h eh i g h w a yd e s i g n i tn o to n l y d e c i d e st h ep r o je c t i o nc o s t sa n dm a i n t e n a n c ec o s t s ，b u ta l s oh a sg r e a tr e l a t i o n s h i pw i t ht h e r o a ds a f e t y m a j o r i t yo ft h et r a d i t i o n a lh i g h w a y a l i g n m e n t sa r em a d eb ya r t i f i c i a l l y ，i th a s m a n ys u b j e c t i v ed e f e c t s ，a n dl o n g t e r ml i n e a rd e s i g ne n a b l e st h ed e s i g n e r sw o r kw i t h e x p e r i e n c e ，l a c ko fi n n o v a t i o n s w i t ht h ep o p u l a r i t yo fc o m p u t e rt e c h n o l o g ya n dt h er a p i d d e v e l o p m e n to fo p t i m i z a t i o nt e c h n i q u e s ，d e s i g n i n gt h er o a da l i g n m e n tw i t hc o m p u t e ri s p o s s i b l e i nt h i sp a p e r ，a c c o r d i n gt ot h ep r e s e n ts i t u a t i o no fh i g h w a ya l i g n m e n ta n dt h et r e n d s o fo p t i m i z a t i o nt e c h n o l o g yd e v e l o p m e n t ，t or e s o l v et h ei s s u e sa b o v e ，t h ea u t h o rl a u n c h e dt h e s t u d yo nt h ei n t e l l i g e n th i g h w a ya l i g n m e n t sd e c i s i o n f r o mt h ec o n n o t a t i o no fi n t e l l i g e n th i g h w a ya l i g n m e n t sd e c i s i o n ，t h ea u t h o rc h o o s e d g e n e t i ca l g o r i t h m sa st h eo p t i m i z a t i o nt e c h n o l o g y ，w h i c hh a sd i s t i n c t i v ec h a r a c t e r i s t i c s u s i n gg e o g r a p h i ci n f o r m a t i o ns y s t e m s ( g i s ) a st h ep l a t f o r m ，f r o mt w os i t u a t i o n s w i t h o u t c o n t r o lp o i n t sa n dw i t hc o n t r o lp o i n t s ，t h eh o r i z o n t a la l i g r m a e n to p t i m i z e do nag i v e na r e a t h ea u t h o rs u m m a r i z e dt h eb a s i cp r i n c i p l e ，t h ec h a r a c t e r i s t i co fg e n e t i ca l g o r i t h m sa n dt h e k e yr e a l i z a t i o nt e c h n o l o g yo fi t ，a n da c c o r d i n gt ot h ec h a r a c t e r i s t i co fh i g h w a ya l i g n m e n t s ，h e d e t e r m i n e dt h ep a r a m e t e r sa n do p e r a t i o n si nt h eg e n e t i ca l g o r i t h m sa n dt h ep r o c e s so ft h a t h em a d ed a t ap r o c e s s i n go ft h es y s t e ma n dag e n e t i ca l g o r i t h mi n t e r f a c et og i s p l a t f o r m ，a n d p e r f o r m e dt h ep r o g r a m s i nt h i sp a p e r ，t h e r ea r et w oi n n o v a t i o n s ：f i r s t ，t h ea u t h o rd e s i g n e dt h ea d a p t a b i l i t y f u n c t i o ni ng e n e t i ca l g o r i t h mb yh i m s e l f ；s e c o n d ，i na l i g n m e n to p t i m i z a t i o np r o c e s s ，h ea d d e d t h ec o n t r o lp o i n t sf o rt h ef i r s tt i m ei nt h es t u d yf i e l d ，a n di tm a d ei n t e l l i g e n th i g h w a y a l i g n m e n t sd e c i s i o nm o r ec l o s et ot h er e a l i t y t h r o u g ht h ev e r i f i c a t i o no fd a t a ，t h es y s t e mc a ns a t i s f i e dt h er e q u i r e m e n t so fh o r i z o n t a l a l i g n m e n to p t i m i z a t i o n ，a n dh a sp r a c t i c a lv a l u e k e yw o r d s ：g e n e t i ca l g o r i t h m s ，o p t i m i z a t i o nt e c h n o l o g y ，c o n t r o lp o i n t s ， a d a p t a b i l i t yf u n c t i o n 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均己在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名： 油。毫年弓窍嗲b 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 导师签名： 油。8 年弓羁l5 b 2 e 0 8 年多只l 午日 长安大学硕 ：学位论文 1 1 课题提出 第一章绪论 1 1 1 传统选线的思考 公路选线在整个公路设计工作中占有非常重要的地位。选线的质量很大程度上决定 着新建公路的工程费用，而且与交通安全有很大的联系。 传统选线主要是人为参与。从实地勘测，到纸上定线，都是人工完成。相同的选线 工作，不同的选线人员会得出不同的选线结果。评价方案，不同的评价人员，相同的路 线方案，也会得出不同的结论。这都归结于人的主观性差异。人的主观性差异导致传统 选线的最终方案难以最优或者相对最优。对于选线人员来说，随着工作年限的增加，选 线经验随之增多，选线更加熟练，线路也更加合理，但同时也产生了一个缺点，就是选 线人员在后来的设计中，不再思考，思维定势，根据经验直接套用先前的设计案例，使 选线工作由脑力劳动转变为体力劳动，设计缺乏创新。创新是发展的动力，当大多数设 计人员依靠经验缺乏创新时，整个行业就会发展缓慢，甚至停滞，出现行业发展瓶颈。 现代社会是信息社会，科技高速发展，计算机迅速普及，计算机技术渗透到各行各 业，同样在公路行业得到了普遍应用。计算机技术为传统的公路选线融入了新的设计元 素，同时对公路选线提出了新要求，也向传统公路选线提出了挑战。能否让计算机智能 的选线，将选线人员从繁重的劳动中解脱出来，降低选线中人的主观性和经验主义，提 高线形设计多样性，是选线人员和计算机软件设计人员一直苦苦探求的问题。 1 1 2 优化技术的发展 公路选线一般的情况是，得出几条方案，根据设计原则和工程费用，进行比选，或 者对方案进行多次、反复的尝试，修改，得出最优或相对最优传统的路线方案。由此看 出，选线的实质就是一个路线优化的过程。 优化技术在国民经济的各个领域里获得了广泛的应用。因为同一个设计任务，可以 有多种不同的可用设计方案，从所有可用方案中选用最满意的方案自然是理所当然的追 求。也就是说，任何情况下“择优而用 是人们无法回避的要求。近几年来，以遗传算 法、模拟退火、禁忌搜索以及人工神经网络为代表的智能优化技术发展迅速，受到人们 的普遍关注。其中遗传算法以其优良的计算性能和显著的应用效果而特别引人注目，也 在工程优化中得到广泛应用。 第一章绪论 遗传算法是一种借鉴生物界自然选择和遗传机制的全局优化概率搜索算法，由于对 求解问题本身限制较少，无需问题的先验信息，对问题的目标函数和约束形式没有严格 要求，搜索过程始终遍及整个解空间，广泛地适用于处理传统搜索方法难于解决的复杂 和非线性的问题。同其他优化算法相比，它主要有以下特点： ( 1 ) 遗传算法对问题参数编码成“染色体”后进行进化操作，而不是针对参数本身， 这使遗传算法不受函数约束条件的限制，如连续性、可导性等。 ( 2 ) 遗传算法的搜索过程是从问题解的一个集合开始的，而不是从单个个体开始的， 具有并行搜索特性，从而大大减小了陷入局部极小的可能。 ( 3 ) 遗传算法使用的遗传操作是随机操作，它既不是盲目的也不是穷举式的，它是根 据个体适应度信息进行搜索。遗传算法是一种有导向的随机搜索算法，它的导向就是个 体的适应度，但它不需要导数或其他辅助信息，具有简单和适应性广泛的特点。 ( 4 ) 遗传算法具有全局搜索能力，最善于搜索复杂问题和非线性问题。 针对小节1 1 1 中传统公路选线的缺陷和计算机技术的普及，我们希望将计算机技 术引入到公路选线中来，降低选线的“主观性”，增加线形创新，于是本课题在这样的 环境下产生了公路路线智能决策系统。 该系统采用最优化技术进行公路选线，得到最优或者相对最优的线形。在本小节开 始详细阐述了最优化技术，其中以遗传算法特点最为鲜明，所以系统采用遗传算法对路 线进行优化。 1 2 研究现状 路线线形设计分为纵断面设计和平面设计，相应的，在国内外的路线优化研究中也 从纵断面优化、平面优化和平纵联合优化三个方向进行。 1 2 1 国外的研究现状 ( 1 ) 纵断面优化方面： 从上世纪6 0 年代开始，计算机技术的发展，使得理论的数学优化方法成为纵断面 优化研究的有力工具，美国、西德、英国、法国、丹麦等国家相继开展了纵断面优化研 究。经过多年研究，逐步形成了可以实用的优化系统，其中具有较大影响有前联邦德国 的e p o s 系统、英国的h o p s 纵断面选线最优化系统、美国的c a n d i d 系统和法国的a p p l o n 程序等。纵断面优化程序的应用，在一定程度上提高了设计质量并相应降低了工程费用。 2 长安人学硕士学位论文 根据联合国经济合作与开发组织于7 0 年代初在意大利西西里岛的某高速公路上进行的 联合试验表明：使用纵断面优化程序可以节省土方工程量8 1 7 平均约为1 0 ，大大降 低了道路的建设费用。 在西西里岛的联合试验之后的十多年时间内，许多国家在纵断面优化设计技术的基 础上，又对一定范围内的公路平面线形和空间立体线形的优化技术进行了研究，并取得 了初步成果。到目前为止，路线优化设计在理论和应用下整体而言仍处在研究探索阶段， 表1 1 列出了从事路线研究的主要学者及优化研究的数学方法。 表1 1 国外路线优化研究状况 优化方法类别研究者及时间 目标 微分优化法 w a n ( 1 9 9 5 ) ，h o w a r d e t a 1 ( 1 9 6 8 ) ，t h o m s o n a n d s y k e s 平 ( 1 9 8 8 ) ，s h a wa n dh o w a r d ( 1 9 8 1a n d1 9 8 2 ) 面 线 网络优化法 d 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 n 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 r i 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 ( 1 9 7 6 ) 遗传算法 j o n g ( 1 9 9 8 ) 枚举法 e a s e ( 1 9 8 8 ) 。 纵 断 动态规划法 p u yh u a r t e ( 1 9 7 3 ) ，m u r c h l a n d ( 1 9 7 3 ) ，g o he ta 1 ( 1 9 8 8 ) a n d 面 f w a ( 1 9 8 9 ) 线 形 线性规划法r e v e l l ee 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 ( 19 7 0 ) ，g o h e t a 1 ( 19 8 8 ) ，r o b i n s o n ( 19 7 3 ) ， f w a ( 1 9 8 8 ) a n dm i n e r v a ( o e c d 1 9 7 3 ) 遗传算法 j o 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 ne ta 1 ( 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 t s c h ( 1 9 8 7 的 遗传算法 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 ， p a u ls c h o n f 等学者在9 0 年代中后期利用遗传算法建立了三维线形优化的进化模型。在 此基础上，为了解决路线优化过程中涉及如土地、环境和拓扑数据等复杂地理信息问题， m k j h a 基于g i s 和遗传算法对路线优化问题进行深入研究【l 】。长期从事线形研究的 t f f w a 教授继利用动态规划法和数值搜索法进行纵断面优化研究之后，利用遗传算法 详细地分析了不同约束条件对纵断面优化结果的影响【2 1 。 第一章绪论 ( 2 ) 平面优化方面： 国外从上世纪6 0 年代就开始研究路线平面优化，早期由于受计算机软、硬件发展 水平，存在优化效率不高以及目标函数过于简单等缺陷，所得到的优化结果实用性不高。 近些年来，随着计算机硬件的发展以及地理信息系统的广泛应用，国外的路线平面优化 研究也得到了进一步发展。国外的路线平面优化方法主要有四种，表1 1 中已经列出， 即：微分优化法( c a l c u l u so fv a r i a t i o n s ) 、网络优化法( n e t w o r ko p t i m i z a t i o n ) 、动态规划 法( d y n a m i cp r o g r a m m i n g ) 及遗传算法( g e n e t i ca l g o r i t h m s ) 。 微分优化法 h o w a r de ta l ( 1 9 6 8 ) 最早提出将微分优化法用于路线平面优化，并且提出了最佳弯 曲法贝i j ( o p t i m u mc u r v a t u r ep r i n c i p l e ，o c p ) 。l a t e rs h a w 和h o w a r d ( 19 81 ) 应用o c p 法则，提出了两种应用于路线平面优化的数值积分算法。该方法假设路线平面优化的目 标函数是连续可积的，由此根据变分法原理导出最佳路线上每一点的弯曲等于垂直于路 线方向的目标函数的对数定向导数，目标函数表示路线上通过点的造价与效益，以经济 性原则进行优化。 虽然基于o c p 法则的变分法得到的优化结果具有连续和全局优化的特点，但由于 组成目标函数的各项费用具有不连续性( 如占地费用) ，因此目标函数连续的假设并不 符合实际情况。 网络优化法 这种方法将平面优化问题转化为网络优化问题，平面线形被表示成起终点相连的许 多圆弧。这样平面优化就是分别计算各连接段的综合费用，从而得到整体费用最小的目 的。其代表性的程序有美国普渡大学的g c a r s 程序。 该程序的做法是：首先按照地形、地物和地质等条件，将宽带范围内的面积转化为 成本区。当路线经过该区时，单位长度路线所需要的修建成本一致；将一些江河、峡谷、 公路等线形构造物表示为成本线，当路线跨过某一成本线时，意味着需修建跨线构造物， 从而增加修建成本。然后将选线范围划分为矩形网格，根据成本区和成本线，由计算机 自动形成任意两点间的成本矩阵。利用该矩阵，通过线性规划找出最佳方案。 该算法由于要计算网格间的连通费用，而且缺乏g i s 系统的支持，因此其成本区划 分以及网格连通费用计算量非常大。 动态规划法 由于选用动态规划法解决平面优化比较理想，因此得到了比较广泛的应用。该方法 4 长安大学硕士学位论文 通常与随机搜索法相结合，无需把可行域划分为一系列的网格并大量地通过每一网格点 的路线分段计算目标函数值，而是以确定的步长和随机的方向在可行域内形成两个新 点，再运用动态规划法选优，不断重复可使优化问题有效的收敛。但该方法不适合于连 续搜索空间，而且要求目标函数为显函数、要求子问题独立等缺点。 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ) 是基于自然进化模型和“适者生存 的一种高度并行、 随机和自适应的优化算法。1 9 9 8 年马里兰大学的j o n g 博士首次将其引入到路线优化中 t 3 】。随后，j h a ，m k 等人对其提出的算法进行了进一步的完善，目前已开始走向实用阶 段【l 】o j o n g 等提出的基本思路为：由程序随机给出一组平面线形，利用遗传算法，对其进 行交叉、变异等遗传操作，直至找出满意解为止。该算法原理简单，寻优速度也较快【3 j 。 1 2 2 国内的研究现状 ( 1 ) 纵断面优化方面： 上世纪7 0 年代后期，我国开始纵断面优化课题研究。到9 0 年代，随着计算机技术 的发展，利用计算机进行纵断而自动化设计取得了较大的进步，钱水祥、刘朝阳、任福 田和吴国雄等均通过对纵断面线的平顺拟合进行纵断面的自动设计研究，为纵断面优化 提供了更为合理的初始方案。 许金良教授提出了一种基于遗传算法的纵断面优化方法，这种方法可以在一个可行 域中自动搜索一个最优或较优解【4 1 。其基本思想是首先根据纵断面初始解建立一个可行 域，通过编码建立染色体与实际设计变量之间的一一对应关系，然后对可行域中的可能 解用一个评价函数( 适应度) 进行度量，利用遗传算法在可行域中选择最优解。实践表明： 该方法具有全局解空间搜索能力，从而实现了全局寻优的目的，对道路优化设计是有效 的，可行的。 顾晓林以对工程造价产生较大影响的填、挖量为主要研究对象，用线性回归方法对 线路纵断面设计进行优化【5 1 。方法是将所有的图形数据转化为图形数据文件，在a u t oc a d 的环境下生成纵断面拉坡设计图，供设计者根据需要直接在计算机上进行修改调整，知 道满意为止，并可绘出纵断面设计参考图，这就使优化意图的实现具有较大的可能性， 使软件具有较高的实用性。 叶霞飞在前人研究成果的基础上，将铁路线路设计的纵断面最优化问题视为三维空 第一章绪论 间中的路线最优决策问题，采用动态规划法对该问题的三维最优化数学模型【6 】。 到目前为止，由于优化模型的简化处理，优化成果可信度不高，优化方法过于繁杂， 耗时长，尚未出现广泛应用于实际生产的纵断面优化模型。 ( 2 ) 平面优化方面： 1 9 9 6 年西南交通大学邓域才教授提出用梯度投影法进行平面优化的思路【_ 7 1 。随后易 思蓉教授等对其进行了进一步的完善和发展【8 1 。其基本思路为：利用航空折线分段判断 紧、缓坡地段，产生合适的初始线位，再用圆顺函数对不规则的线路平面位置进行圆顺 以后，拟合成符合规范的线路平面位置，然后用梯度投影法进行初步优化，从而得到线 路的平面优化结果。该方法目标函数是以各计算点的设计高程与地面高程之差为基础进 行的，往往假定地形变化规律不变，只有在很小范围内这种假定才接近实际，因此在优 化的迭代过程中每次迭代的步长不能太大。另外，该方法在接近最优解时收敛速度较慢。 2 0 0 0 年易思蓉教授和邓域才教授合作开发了“铁路新线设计智能c a d 原型系统 ， 简称p i r l c a d 9 1 。该系统将知识库技术、交互式图形技术、优化方法和数据库技术相结 合，在主要控制点已定、主要技术标准已定、地形条件较好的平丘地区，用智能c a d 方 法解决路线局部走向选择问题。 同济大学朱照宏教授等根据公路设计的不同阶段，分别采用不同的技术层次对路线 进行优化，其平面线形优化仍然是基于动态规划法的原理，与美国普渡大学的g c a r s 程序基本类似。 ( 3 ) 平纵联合优化方面： 1 9 9 2 年长沙铁道学院完成了平纵联合优化的课题，提出了r d b 方法，即随机搜索 一动态规划一b 样条函数综合方法。其基本思想为：先用随机法产生几组状态点，用动 态规划进行优化，选出其中的最佳路线。在这条最佳路线上用b 样条函数法进行纵断面 优化，得到目标函数值，在该平面线和纵断面线的基础上运用随机搜索法继续产生新状 态点，用动态规划法进行优化，循环往复，直至达到平面和纵断面线联合最优。该方法 依赖于随机产生的状态点，在随机搜索的状态点足够多的情况下，才能得到比较满意的 结果。另外，这种方法的收敛性如何，目前还未得到充分的论证。 冯春综合了单纯进行平面优化和平、纵优化一对一( 每进行一次平面优化就进行相 应的纵断面优化) 的长处，从平纵交合的最优性出发，采用空间交点来确定公路空间线形， 且应用随机动态规划模型来优化这种空间线形【1 0 】。 6 长安大学硕士学位论文 1 2 3 国内外研究总结 无论是国外所言的道路线形优化问题，还是国内谈及的道路选线问题，实际上都表 达的是同一个概念在给定的起、终之间，众多因素的综合考虑下，寻找一条经济上最优 的道路空间线形。这是一个十分复杂的问题，两点之间存在的道路空间走向方案的数量 是无穷多的，另外，考虑的比较因素之间相互作用，互相制约，可谓是错综复杂。 目前，研究的焦点就是将道路选线问题抽象表达为一个合理的数学优化问题，讨论 研究如何建模的问题。提出了一个优秀的线形优化模型应该具有以下的属性： ( 1 ) 考虑所有主要的费用和敏感的费用； ( 2 ) 量化所有重要的约束限制； ( 3 ) 生成一条符合实际的线形； ( 4 ) 能够生成迂回的曲线线形； ( 5 ) 同时优化平面和纵面线形； ( 6 ) 获得全局或是接近全局的最优解； ( 7 ) 有一个高效的求解算法； ( 8 ) 有一个连续的搜索空间； ( 9 ) 考虑交叉口、桥、隧道的费用； ( 1 0 ) 自动避免不可达到的区域； ( 11 ) 与地理信息系统兼容。 1 3 研究目的、意义 传统的公路选线中，对设计人员具有较高要求，需要设计人员具有丰富的路线设计 “经验 ，路线线形具有很强的“主观性 ，而且，“经验 过多，设计者往往不再思考， 参考先前设计案例，使设计缺乏创新。鉴于以上缺点，和计算机技术的迅速普及，以及 以遗传算法为代表的智能优化技术的迅速发展，本文在参考国外研究成果的基础上，提 出了“公路路线智能决策系统”，并将遗传算法作为主要的优化技术，应用到该系统中。 “智能 选线增加了计算机技术和优化技术，和传统的公路选线相比，具有明显的 优点： ( 1 ) “智能 选线在地图数据提供好的前提下，选线的速度取决于计算机硬件的运行 速度和优化算法的时间复杂度，设计人员几个月甚至成年的工作量，最多几天便可完成 选线的任务，大大提高设计效率。 7 第一章绪论 ( 2 ) “智能选线可以提供多条路线方案，供设计人员参考、比选，根据不同的需求 选择最终方案，传统选线的只有一条或者几条线路，更加具备科学性。 ( 3 ) “智能”选线不是“乱 选线，设计遵守公路线形的设计规范，采用规则，但不 拘泥于“经验”，具备更好的创新性。 对应于“智能选线 的优点，本文研究的意义如下： ( 1 ) 提高设计效率，减少设计者工作量，缩短设计周期，减少人力、物力消耗，减少 开支，节省资金。 ( 2 ) 设计方案更加科学，合理。 ( 3 ) 遵守规范的前提下，设计更加灵活，降低设计中“主观性 ，增加设计创新。 1 4 研究内容 路线设计分为平面线形设计和纵断面线形设计。路线平面优化设计涉及诸多因素， 如社会环境、地形、地质等，远比纵断面设计复杂。本文主要研究平面线形的优化设计。 本文采用应用比较广泛的遗传算法，原因在于其对求解问题本身限制较少，无需问 题的先验信息，对问题的目标函数和约束形式没有严格要求的鲜明特点和强大的空间搜 索能力。以地理信息系统( 简称g i s ) 为平台，对给定区域内的平面线形进行优化。为 此，主要包括以下几个方面内容： ( 1 ) 遗传算法的设计思想、原理及其主要流程。 ( 2 ) 遗传算法中选择算法的选择。 ( 3 ) 遗传算法在路线平面优化中特定交叉算子、变异算子的设计。 ( 4 ) 遗传参数，如遗传代数、初始种群数、选择概率、交叉概率、编译概率等的确定。 ( 5 ) 路线平面优化中的数据处理和接口设计。 ( 6 ) 系统试验分析及评价。 长安人学硕士学位论文 第二章遗传算法的基本理论 生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能 力而被大自然所选择或淘汰。这种自然界中的生存繁衍，显示了其对自然环境的优异自 适应能力。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现 型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交 叉、变异来适应大自然环境。 受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应 系统的设计和开发提供了广阔的前景。遗传算法就是这种生物行为的计算机模拟中令人 嘱目的重要成果。 遗传算法是根据生物进化思想而启发得出的一种全局优化算法，是仿真生物遗传学 和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对 生物进化过程进行的数学方式仿真。遗传算法的概念最早是由b a g l e yj d 在1 9 6 7 年提出 的；而开始遗传算法的理论和方法的系统性研究的是1 9 7 5 年，这一开创性工作是由 m i c h i g a n 大学的霍兰德( j h h o l l a n d ) 所实行，他在著作( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a l s y s t e m s ) ) 中首次提出遗传算法，并主要由他和他的学生发展起来的【1 。 遗传算法自提出以来，在国际上已经形成了一个比较活跃的研究领域，已召开了多 次比较重要的国际会议和创办了很多相关的国际刊物。 遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排 序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。 2 1 遗传算法的基本概念 遗传算法的基本思想是基于d a r w i n 进化论和m e n d e l 的遗传学说的。d a r w i n 进化 论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体 的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只 有那些适应环境的个体特征方能保留下来。m e n d e l 遗传学说最重要的是基因遗传原理。 它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的 位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突 变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因 结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方 9 第二章遗传算法的摹本理论 法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下： ( 1 ) 串( s t r i n 曲 它是个体( i n d i v i d u a l ) 的形式存在于算法中的一个数据( 二进制或其他) 串，并且对 应于遗传学中的染色体( c h r o m o s o m e ) 。 ( 2 ) 群体( p o p u l a t i o n ) 个体的集合称为群体，串是群体的元素。 ( 3 ) 群体大d x ( p o p u l a t i o ns i z e ) 在群体中个体的数量称为群体的大小。 ( 4 ) 基因( g e n e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串s = 1 0 1 1 ，则其中的 1 ，0 ，1 ，1 这4 个元素分别称为基因。它们的值称为等位基因( a l l e l e s ) 。 ( 5 ) 基因位置( g e n ep o s i t i o n ) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右 计算，例如在串s = 1 1 0 1 中，0 的基因位置是3 。基因位置对应于遗传学中的地点( l o c u s ) 。 ( 6 ) 基因特征值( g e n ef e a t u r e ) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串s = 1 0 1 1 中，基 因位置3 中的l ，它的基因特征值为2 ；基因位置1 中的1 ，它的基因特征值为8 。 ( 7 ) m 结构空间s s 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结 构空间对应于遗传学中的基因型( g e n o t y p e ) 的集合。 ( 8 ) 参数空间s p 这是串空间在物理系统中的映射，它对应于遗传学中的表现型( p h e n o t y p e ) 的集合。 ( 9 ) 非线性 它对应遗传学中的异位显性( e p i s t a s i s ) 。 ( 1o ) 适应度( f i t n e s s ) 表示某一个体对于环境的适应程度。 遗传算法还有一些其它的概念，限于篇幅，在此不再阐述。 2 2 遗传算法的发展过程 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种抽象于生物进化过程的、基于自然选择和 l o 长安大学硕士学位论文 生物遗传机制的优化技术，自产生至今已有3 0 多年的历史。其研究发展过程大体上可 分为下三个阶段： ( 1 ) 7 0 年代的兴起阶段 19 7 5 年，美国m i c h i g a n 大学j h o l l a n d 等人在进行能学习的机器的研究中，受达尔 文进化论”适者生存”的启发，首次提出了遗传算法这一新概念【1 1 】。同时，他还提出用简 单的位串形式编码表示各种复杂结构，并用简单的变换来改进这种结构，从而证明了遗 传算法可以在搜索空间中收敛到全局最优解，开创了对遗传算法这一新领域的研究局 面。美国d e j o n g 博士首先将遗传算法应用于函数优化，为这一技术的应用奠定了基础。 ( 2 ) 8 0 年代的发展阶段 1 9 8 0 年，s m i t h 教授首次将遗传算法应用于机器学习领域，并研制出一种称作分类 器( c l a s s i f i e r ) 的系统。1 9 8 9 年，g o l d b e r g 撰写了遗传算法在搜索优化和机器学习中的 应用一书，对g a 的原理及应用做了比较详细、全面的论述【1 2 1 。该书至今仍是遗传算 法研究中广泛适用的经典之作。此后，许多学者对原来的遗传算法( 或称标准遗传算法) 进行了大量改进和发展，提出了许多成功的遗传算法模型，从而使遗传算法应用于更广 泛的领域。 ( 3 ) 9 0 年代的高潮阶段 进入9 0 年代后，遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为 迅速，在各种不同领域( 如机器学习、模式识别、神经网络、控制系统优化及社会科学 等) 中得到广泛应用，引起了许多学者的关注。在最近兴起的人工生命、遗传编程、进 化策略、进化计算等领域中，研究人员将遗传算法与计算机科学相结合，试图模拟自然 界的自适应、自组织和再生能力，设计出具有“生命 的人工系统。 2 3 遗传算法的特点 ( 1 ) 遗传算法以决策变量的编码作为运算对象。 这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染 色体和基因等概念，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便 地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的 优化问题，编码处理方式更显示出了其独特的优越性。 ( 2 ) 遗传算法从问题解的串集开始嫂索，而不是从单个解开始。 这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最 第二章遗传算法的基本理论 优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大利于全局择优。 ( 3 ) 遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用适应度这一信息进行搜索，并不需要问题导数等与问题直接相关 的信息。遗传算法只需适应度和串编码等通用信息，故几乎可处理任何问题。 ( 4 ) 遗传算法直接以目标函数值作为搜索信息。 传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他 一些辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数 值，就可确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信 息。这个特性对很多目标函数是无法或很难求导数的函数，或导数不存在的函数的优化 问题以及组合优化问题，应用遗传算法时就显得比较方便，因为它避开了函数求导这个 障碍。再者，直接利用目标函数的值或者个体适应度，也能够使得我们可以把搜索范围 集中到适应度高的部分搜索空间中，从而提高了搜索效率。 ( 5 ) 遗传算法有极强的容错能力 遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异 操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤 波机制。故而，遗传算法有很高的容错能力。 ( 6 ) 遗传算法使用概率搜索技术。 遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概 率的方式来进行的，都是随机操作，而不是确定的精确规则。选择体现了向最优解迫近， 交叉体现了最优解的产生，变异体现了全局最优解的覆盖从而增加了其搜索过程的灵活 性。另外遗传算法的鲁棒性又会使得参数对其搜索效果的影响尽可能地低。 ( 7 ) 遗传算法具有隐含的并行性 遗传算法同时使用多个搜索点的搜索信息。对这个群体所进行的选择、交叉、变异 等运算，产生出的乃是新一代的群体，在这之中包括了很多群体信息。这些信息可以避 免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的 种隐含并行性。这种隐含并行性，可使它容易改造成为并行分布式算法，用来解决那 些复杂性问题。 2 4 遗传算法的原理 遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问 1 2 长安大学硕上学位论文 题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产 生的每个染色体进行评价，并基于适应度来选择染色体，使适应性好的染色体有更多的 繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体， 形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择 高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这 个新种群进行下一轮进化。这就是遗传算法的基本原理。 2 4 1 基本遗传算法描述 遗传算法都有共同特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的 模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点，g o l d b e r g 总结出了 一种统一的最基本的遗传算法基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m s ，简称s g a ) 。 基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化 操作过程简单，容易理解，是其它一些遗传算法的雏形和基础，它不仅给各种遗传算法 提供了一个基本框架，同时也具有一定的应用价值。 2 4 2 基本遗传算法的构成要素 ( 1 ) 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个 体，其等位基因是e h - - 值符号集 o ，1 ) 所组成的。初始群体中各个个体的基因值可用均 匀分布的随机数来生成。如x = 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 就可以表示一个个体，该个体的染 色体长度是n = 1 8 。 ( 2 ) 个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中 每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的 适应度必须为正数不为零。必须预先确定好由目标函数值到个体适应度之间的转换规 则。 ( 3 ) 遗传算子。基本遗传算法使用下述三种遗传算子： 选择运算使用比例选择算子； 交叉运算使用单点交叉算子； 变异运算使用基位变异算子或均匀变异算子。 ( 4 ) 基本遗传算法的运行参数。基本遗传算法有4 个运行参数需要提前设定：群体 大小m ( 一般取3 0 1 0 0 ) ，终止进化代数( 一般取1 0 0 - - 5 0 0 ) ，交叉概率p c ( 一般取0 2 5 0 7 5 ) ， 变异概率p m ( 一般取o 0 1 - - 4 ) 2 ) 。 第二章遗传算法的基本理论 需要说明的是，这些运行参数对遗传算法的求解结果和求解效率都有一定的影响， 但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。 2 4 3 基本遗传算法伪代码描述及形式化定义 ( 1 ) 下面给出基本遗传算法的伪代码描述： p r o c e d u r es g a b e g i n i n i t i a l i z ep ( o ) ； t = - o ；