（交通运输规划与管理专业论文）铁路本枢纽车流组织模型及其遗传算法研究.pdf

西 南 交 通 大 学 研 究 生 学 位 论 文第 i i 页 ab s t r a c t .，.f r a i l w a y t e r m i n a l a r e b a s i c u n i t e t o f o r m t h e r a i l n e t w o r k , k e y l i n k s t o c o n n e c t t h e r a i l n e t w o r k w i t h t h e c i t i e s a n d t h e v a r i o u s d e p a r t m e n t s i n n a t i o n a l e c o n o m y , a n d m a i n b a s e s t o o r g a n i z e t h e r a i l w a y t r a n s p o r t p r o d u c t i o n . t h e t r a n s p o r t m a n a g e m e n t a t t h e t e r m i n a l s i s t h e c r u x o f t h e w h o l e r a i l w a y t r a n s p o r t m a n a g e m e n t , m e a n w h i l e , t h e o r g a n i z a t i o n o f w a g o n f l o w a t t h e t e r m i n a l s i s t h e k e y t o t h e af t e r t r a n s p o r t r a i l w a y m a n a g e m e n t t e r mi n a l s a t t h e t e r mi n a l s . b e i n g s y s t e m a t i c a l l y , t h e c o m p l e x i t y o f a n a l y z e d t h o r o u g h l y a n d r a i l w a y t e r m i n a l s b e i n g c o n s i d e r e d , w a g o n f l o w , t h i s t h e s i s a i m s , f i r s t ,t o s p e e d t h e t r a n s i t o f b y m e a n s o f r e d u c i n g t h e d e t e n t i o nv e h i c l e s a t t h e t e r m i n a l s a n d e s t a b l i s h i n g d i f f e r e n t m o d e l s t o o r g a n i z e t h e w a g o n f l o w a t t h e t e r m i n a l s :t h e m o d e l f o r t h e t r a n s i t o f w a g o n f l o w , t h e m o d e l f o r t h e l o c a l w a g o n f l o w , a n d t h e m o d e l f o r t h e e x c h a n g e t r a i n s ;s e c o n d , t h o r o u g h s t u d y a l g o r i t h m c al c u l a t i f or b a s e d o n t h e c h a r a c t e r i s t i c s o f m o d e l s a n d t h e o n t h e g e n e t i c a l g o r i t h m，t o w o r d o u t t h e g e n e t i c t h r e e m o d e l s a b o v e m e n t i o n e d a n d t h e m a t c h i n g n g s o f t w a r e:f i n a l l y，j i l l i a n t e r m i n a l b e i n g t a k e n a c a s e , a f t e r i t s o r g a n i z a t i o n o f w a g o n f l o w b e i n g d i s c u s s e d as t h e t y p e s o f s t a r t i n g v e h i c l e s a n d t h e p l a n s o f c l a s s i f i c a t i o n b e i n g p r o v i d e d j i l l i a n t o s h o w a p r o o f t o t h e p l a n t o r e c o n s t r u c t a n d e x t e n d t e r mi n a l 西 南 交 通 大 学 研 究 生 学 位 论 文第 m页 【 k e y o p t i o n a l w o r d s i r a i l w a y t e r m i n a l， o r g a n i z a t i o n o f w a g o n f l o w g e n e t i c a l g o r i t h m 西 南 交 通 大 学 研 究 生 学 位 论 文 第 t 页 第一章绪论 一、选题的目的和意义 铁路是国民经济发展的先行官，在各种交通运输方式中起着主导作 用。 铁路曾铸就了辉煌，为我国的国民经济发展、人民生活水平的提高， 巩固边疆国防作出了重大贡献。随着社会主义市场经济体制的确立和不 断完善，改革开放不断深化和扩大，运输市场也发生了巨大变化 。昔 日 “ 门难进 、脸难看、货难装 ”，描述出铁路企业完全处于卖方市场;如 今客货运量骤然下降。 有人认为交通运输业发展经历了水运时代，随后进入了铁路时代， 继而进入高速公路和航空时代，因此铁路是夕阳产业等等。诚然，面临 着公路和航空运输的崛起，铁路承受的压力是巨大的。但是一种交通运 输方式退出历史舞台是一个漫长的过程。如水运作为一种运输方式，已 经有几千年的历史，如今在江南水乡仍然发挥着主要作用，并且随着社 会的变迁，它还会被赋予新的功能。如在公务、商务活动中，轮船的速 度是不能接受的，但在旅游中，轮船具有很大的吸引力。 运输业的发展既依赖于大工业提供的工具和提供的能源，运输业也 促进了大工业的发展。运输业在适应外部环境的过程中，自始至终在处 理一系列矛盾，包括运量多少、速度快慢、距离远近、运输物品的完好 损坏以及运费昂贵低廉和灵活性高低、限制性大小等成对矛盾。每种运 输方式在不同情况下， 或处于优势或处于劣势。 没有一种万能运输工具， 可以在一切领域领先。因为人们在反复权衡、比较各种满足的状况中， 来选择运输工具。在这个不断选择优化过程中，每种交通运输方式形成 西 南 交 通 大 学 研 究 生 学 位 论 文第 i 页 自己的技术经济特点，有自己的活动领域，有自己的生命力，所以不存 在先后互相代替的时代问题。每种运输方式的相对优劣，是这些客观标 准使之明确起来的。如对货运来说，到底是铁路好还是公路好的问题， 只有在运量、运距、效率、时间、费用等有差异时，才迫使人们选择取 舍。大宗、长途、堆装粗放货物多，自然铁路占优势;运距短、运量相 对较小、要求迅速、及时，自然公路效果好。 每种运输技术的发展，从线路、动力、装载、控制等设备来说，无 论铁路还是汽车都已达到成熟阶段。联合是今后的发展趋势。当今的时 代，是综合运输的时代。铁路在整个运输网络中起着骨干作用。 为了保证我国国民经济发展战略目标的实现，建设一个具有足够数 量、布局合理、通路强大、适度储备、与其他的运输方式协调发展的现 代化铁路运输 网，实现铁路数量上的大发展、质量上的大提高、技术上 的新突破，管理上的大改善的奋斗目标。为此，铁路网规模 2 0 0 0年要 达到七万公里左右，2 0 2 0年达到十万公里左右。可以预言，铁路运输 对社会主义市场经济将起到强有力的支撑作用 。 在社会主义市场经济条件下 ，交通运输业所处的环境也发生了巨大 的变化。为了在激烈的市场竞争中占得一席之地，作为运输业主干的铁 路运输子系统，必须锐意改革，勇于进取，主动适应社会经济环境的变 化。若它与社会经济环境相适应 ，则它能促进 国民经济持续 、健康的发 展;国民经济的进一步发展，将为交通运输业提供更广阔的运输需求， 产生人流、物流，推动交通运输业的发展，最终走向良性循环 的轨道; 反之，若交通运输业与社会经济环境不相适应，即交通运输业滞后于国 民经济的发展需要，将制约国民经济的发展，最终也使交通运输业得不 到更多的投资。如我国由于能源基地在西部，东西通道能力紧张，造成 华东能源紧缺，大量的工厂停产、限产，造成大量的经济损失;另一方 面，“ 三西”的煤炭开采后不能即时运输出来，在堆放过程中发生自姗， 西 南 交 通 大 学 研 究 生 学 位 论 文第 3 页 污染环境，浪费大量的人力、物力，教训是深刻的。 社会经济活动产生交通运输需求，没有人为出行而出行，而是为了 达到目的而出行。不同的社会经济活动对运输的需求不一致。社会经济 活动的多样性及复杂性，决定了运输需求的复杂性和运输需求影响因素 的多样性和复杂性。在市场经济条件下，运输需求变得更加复杂。 铁路枢纽是在铁路网点或网端地区，设有几个在统一指挥下协调工 作的车站、引入线路与相应的联络线的组合体。它是组成铁路网的基本 单元，是联系路网与城市和国民经济部 门的重要环节，是进行铁路运输 生产的主要基地。它除办理有关车站的列车运转、技术作业和客运业务 外，还是组织车流交换、调整列车运行和供应运输动力的主要据点。 枢纽工作组织的好坏 ，不仅直接影响到铁 路系统 内部的车流的通 畅，而且关系着铁路能不能满足客货主的运输需求，适应市场经济下的 大交通的问题。进入铁路枢纽的路网干线车流，经过在枢纽内的解体、 装卸、取送、编组作业后，组成新的出发列车，随路网干线列车出发输 送到各地。枢纽的装卸车计划、排空计划，以及列车出发计划三者的编 制可归结为一个核心一一列车出发计划的编制。因此研究在市场经济下 的铁路枢纽工作组织，具有重要的意义。 二、国内外研究现状 国外铁路枢纽的形成与我国具有显著不同的特点。由于资本主义的 市场的无序竞争，出现一个方向上有几个公司各 自经营的铁路 ，枢纽内 车站的设立也是为各公司服务的，枢纽内外的设备能力都相当富裕，形 成了以基本计划管理为主，规划型的行车组织模式，在铁路调度指挥自 动化、作业计划的自动编制等方面狠下功夫。8 0年代以来，在既有的 计算机信息网络的基础上，对各级调度指挥系统增添了不同程度的辅助 西 南 交 通 大 学 研 究 生 学 位 论 文第 4 页 决策功能，已逐步实现由管理信息系统 ( m i s )向决策支持系统 ( d s s ) 过渡。如前苏联铁路的a c y r t ，美国铁路的t o p s ，加拿大铁路的t r a c s 系统等。进入 9 0年代 以来，为了提高铁路运输的安全、效率和灵活性 以及增强运输竞争力，以计算机辅助系统为核心的调度指挥系统得到了 积 极 的 推进 。 如 日本 新 干 线 研 究 开 发 的计 算机 辅 助 行 车 管 理 系 统 ( c o m t r a c ) ，北美、西欧等国研制的先进列车控制系统 ( a t c s . a s t r e e 等) ，以及新一代智能铁路系统，都越来越强调对计划的优化 自动编制。 日本提出了对列车群指挥管理的观点，通过对相关子系统的综合，利用 计算机、信息处理技术和通信网技术，使系统具有行车计划、运营管理 和信息服务等功能;德国拟建的计算机辅助综合铁路系统 ( c i r ) ，也特 别的注重系统在制定策略计划、工作计划、作业控制和根据作业过程数 据进行效能评价和设计工作等功能的研究。 在我国，五十年代在系统学习前苏联铁路行车组织方式的基础上， 形成了组织型的行车组织模式，通过编制各级 日班、阶段作业计划实现 日常运输组织指挥。行车组织指挥水平很大程度上依赖于调度员的个人 素质 ，具有较大 的随意性 ，不能适应按 图行车的要求 。 近年来，随着我国铁路现代化进程的加快，编组站、货运站、机务 段信息系统的建立，以全路货车实时追踪系统为核心的运输管理信息系 统 t m i s的加紧建设，铁道部一一局一一分局基干信息网络的初步形成， 微机化调度集中系统的采用，研究与开发我国铁路调度指挥计算机辅助 决策支持系统的时机已日趋成熟。特别是干线列车运行图的计算机编制 己投入了实际应用，并取得了良好的效果。 铁路枢纽是我国铁路网的重要组成部分，它不仅担负着枢纽地区到 发的客、货运输任务，而且还承担着各衔接干支线之间到发的旅客、货 物、机车、车辆的中转任务，作业组织非常复杂，铁路枢纽的综合治理 是目前我国铁路现代化改造的重点工程。铁路枢纽从某种程度来说，它 西 南 交 通 大 学 研 究 生 学 位 论 文第 5 页 就是一个小分局 。现有的计算机编制列车运行图只适用于干线区段。尽 管枢纽 内的线路也可看 成是一段一段联接起来的 ，似乎也可用干线运行 图的编制方法来处理枢纽。实际上，现有的计算机编制列车运行图各版 本都特别警示:“ 枢纽禁用! ” ，实际实验的效果也不理想。研制符合我 国国情的计算机编制枢纽列车运行图已迫在眉睫 。 路网干线车流进入枢纽内的编组站，进行解体、装卸、取送、编组 等作业后，变成新的列车，随着路网干线车流转送到目的地。因此编组 站工作是枢纽工作组织的核心，其他工作都是围绕编组站工作展开一一 保证进入枢纽内的车流经过作业后能及时输送出去。因此文献【 2 2 认为 编组站的装卸车计划、排空计划以及列车出发计划三者的编制可以归结 为一个核心一一列车出发计划的编制。由于出发计划编制的核心是确定 出发列车的编组内容和车流来源 ，而装卸车和排空计划是对相应的出发 列车的编组内容做一定的配合与限制，那么，若将装卸车和排空计划视 为出发列车计划编制前的预备工作，在考虑装卸、排空对车站的重、空 车流的影响后 ，就可以把装卸、排空计划纳入编组站出发计划主要考虑 的问题一一出发列车的车流接续问题。最终归结为一带 “ 品类”和运输 时间约束的运输问题，模型的变量和约束条件都是多项式界的。在实际 求解方面，该文认为即使每日到发 1 0 0列列车的普通编组站，还是存在 规模太大的问题，因此 ，仅仅从理论上探讨了这一模型的算法。 文献 7 以济南枢纽为背景，研究了枢纽运输组织的静态优化设计 问题，建立了枢纽车流组织的整数规划模型，对枢纽内编组站作业分工 和车流径路选择进行了综合优化，并探讨了小运转工作方案和机车运用 方案。文献 2 3 在对我国主要铁路枢纽现状及运营调整分析的基础上提 出了一个简化的数学模型，研究枢纽内车流组织优化及枢纽改扩建时机 和改扩建方案比选等问题。文献【 2 4 在对铁路枢纽进行系统分析的基础 上，建立 了枢纽车流组织的优化模型并进行了灵敏度分析，最后 以成都 西 南 交 通 大 学 研 究 生 学 位 论 文第 6 jf , 铁路枢纽为背景给出了规划中的近期成都铁路枢纽车流组织方案。值得 指出的是，文献 2 4 建立的实际是一个非线性规划模型，模型求解难度 太大。因此在实际求解时，近似简化为一个线性规划模型，得到的结论 不很理想。 三、存在的问题及本文的主要研究内容 ( 一)存在的问题 目前国内外大多数都把枢纽内的编组站作为研究的重点，对枢纽内 的编组站或编组站的某一部分、某一环节，运用排队论、动态规划或随 机过程等优化理论建立优化模型，对枢纽运输组织工作整体的理论研究 做得不够，主要表现在:往往只限于对个别车站、区间的研究;定性分 析多，定量分析少;静态研究多，动态研究少。以致现场合理的方案难 以得到理论上的说明和阐述，从而形成完整的理论。 、如何实现列车工作计划、货运工作计划的协调优化，使得枢 纽中间站装、卸、排空计划、小运转列车开行与枢纽编组站大 运转列车出发车流衔接，减少车辆在枢纽内停时间，至今仍然 缺乏系统化的理论方法。 2 、现有的枢纽车流研究基于枢纽平均车流，是属于静态的。显 然，每日均衡到达与 1 8 : 0 0前后密集到达，而其他时候相对空 闲的情况是完全不同的。 3 、尽管现有的模型构造都有独到之处，但模型过于复杂 ( 很多 都是非线性的) ，导致无法求解或为了能够计算将模型作了近 似、简化等 ( 如用线性规划逼近于一个非线性规划模型) ，导致 西 南 交 通 大 学 研 究 生 学 位 论 文第 7 页 计算出来的结果与生产实际有较大的差距。 ( 二) 、本文研究的主要内容: 由前面分析知，随着路网干线进入枢纽的大运转列车，按其 作业性质可分为通过流和终到流。通过流主要是指无调中转列 车或有调中转列车。前者只需进行到、发等技术作业后继续出 、 ;后者则需进行解体、集结、编组等作业后组成新的列车出 。终到流经过解体后 由小运转 列车送 到货场 、专用 线等地 进 发发 行货物作业 ( 卸、装、双重作业等) ，作业完毕后由小运转列车 取回编组场，组成新的列车出发.因此本文分层次分别建立了 中转车流模型、地方车流 ( 含空车)模型、小运转列车模型。 由于模型是超大规模的线性规划模型，本文用遗传算法在普 通微机上以较快的速度得到了该问题的一个较优解. 、 11人q乙 3 、以正在建设中的吉林铁路枢纽为背景，给出了吉林枢纽列车 出发种类及编组 内容，为计算机编制该枢纽的列车运行 图打下 了基 础 。 西 南 交 通 大 学 研 究 生 学 位 论 文第 。页 第二章遗传算法理论基础 遗传算法( g e n e t i c a l g o r i t h m ，简称 g a ) 首先是由 j . h . h o l l a n d 等人于 7 0年代发展起来的，最初的目的是研究自然系统适应过程，建 立模拟 自然系统适应机制的人工系统。 与传统的搜索算法( 如基于微分的方法， 枚举法，随机搜索算法) 相 比，g a算法具以下的特点: ( 1 )遗传算法不是直接作用在参变量集上，而是利用参变量集的 某种编码; ( 2 )遗传算法不是从单个点，而是从一个点的群体开始搜索; ( 3 )遗传算法只利用适应值信息，无须可导、凸性、连续等其它 的辅助信息; ( 4 )遗传算法利用概率转移规则，而非确定性规则; 遗传算法中，每个非零向量称为个体 ( 或染色体)，由基因 ( 字符 或数)串组成;一定数量的个体组成群体，通过遗传操作随机融合群体 中合理的因素可以不断进化产生一批具有优良性质的个体，组成新的群 体，其中个体的适应值不断提高，最终群体中的最佳个体 ( 即适应值最 大的个体)即为问题的最优解或次优解。 遗传算法作 为一种新的搜 索算法 ，己引起 了许 多领域 的学者 的关 注，并在优化、神经网络、机器学习及控制领域得到了广泛的应用，特 别是已成功用于求解一些np完全问题， 如旅行商问题， 工厂布局问题， 任务安排问题等.随着遗传算法研究的深入和不断的取得进展，必将在 优化问题上得到更广泛的应用。 西 南 交 通 大 学 研 究 生 学 位 论 文第 9 第一节 遗传算法的基本原理 在应用遗传算法求解 问题时，主要完成下列几个步骤: ( i )确定表示方案即编码方案; ( z )确定适应值度量; ( 3 )确定控制算法的参数和变量; ( 4 )确定指定结果的方法和停止运行的准则; 在常规的遗传算法中，表示方案是把问题的搜索空间中每个可能的 点表示为确定长度的特征串，它能反映所求问题的特点和性质。不同的 问题，其变量的性质和特点不同，其表现形式也应该不同;同时解的表 示方案还应便于计算机处理，因为参与运算的不是解变量本身而是采用 某种表示方案的染色体。表示方案的确定需要选择串长 l和字母表规模 k 。二进制串是遗传算法常用的表示方法，根据实际问题也可采用浮点 编码方案，不规则形式的编码方案等。 适应值度量为群体中每个可能的确定长度的特征串指定一个适应 值，它经常是问题本身所具有的。适应值度量必须有能力计算搜索空间 中每个确定长度的特征串的适应值，它反映染色体对环境的适应能力。 控制遗传算法的主要参数有群体规模 n和算法执行的最大代数目 m ，次要参数有复制概率只，杂交概率p . 和变异概率p m 等参数，控制参 数的不同选取会对遗传算法的性能产生很大的影响。 停止准则有时表示成算法的执行的最大代数 目的形式，或相邻 n代 已无进化表现时，对那些一旦最优解出现就能识别的问题，算法可以当 这样的个体找到时就停止执行 ，把当前最好的个体指定为遗传算法的结 果 。 一旦上述准备步骤完成，就可执行遗传算法: 西 南 交 通 大 学 研 究 生 学 位 论 文第 ， 。页 随机产生一个由确定长度的特征串组成的初始 群体 将解变量映射为某一确定形式的码链，形成一个个体或染色体时， 随机产生 n个个体组成一个群体g o 钊9 1 1 9 2 1 9 3 ， 二 ， g , ，该群体代表 优化问题一些可能解的集合，称为初始种群或 “ 祖群”。遗传算法就是 从这个群体出发，模拟生物进化过程，优胜劣汰。 在产生初始群体时，可根据问题进行预处理，随机得出符合约束条 件的可行解，从中筛选出较好的个体组成 “ 祖群”，加快进化过程，此 时代数 t为 o o 二、性能评价 对第 t 代群体认钊 9 1 1 9 2 1 9 3 1 . . . 9 n ) ， 计算每个个体的适应值了 0 - 1 , 2 ，二， n ) 并确定个体g 在选择过程中被选中复制的概率 p ( g , ) . 如 确 定p ( g ) 二f , l艺f ,. ( i = 1 , 2 , 3 , . . , n ) e 三、终止判别 判断是否满足停止准则，若是，输出最佳解，结束运算 ;否则，继 续往 下进行 。 四、复制操作 置 t 二 t + l 以复制概率p ( g , ) 从第 t - 1 个群体中随机选取 2 m 个个体 西 南 交 通 大 学 研 究 生 学 位 论 文第 i 。页 作 为新 一代 个体 。 五、交叉重组操作 对复制操作得到的 2 m个个体按概率p 两两进行交换，即相互间交 换一些元素，以便使个体中可能包含的优 良特性遗传到新一代个体中， 从而派生出更好的个体。由于交叉反映了遗传算法的主要特点，并使得 所有的染色体均有可能进入种群，因此，它是遗传算法的最主要操作， 在遗传算法研究中受到广泛关注 ，这里介绍常见的几种杂交方式: ( 一)、交又点数固定的交替或交又规则 利用均匀分布的随机数发生器在父染色体中产生固定数 目的交叉 点，然后交换两个染色体交叉段的元素，产生两个子染色体。此方式有 单点交叉和多点交叉两种。 1 、单点交叉:随机选取一个交叉点， 将两个染色体在交叉点分 开后，然后交换其尾部，如: p a r e n t l : k e gc a h一 交叉 一 c h i l d l : keg i d e f p a r e n t 2 :a b c d e f c h i l d 2 :a b c c a h 2 、多点交叉:随机选取n 1 个交叉点， 将父染色体分成。 + 1 段， 然后交换其偶数段基因。n 为 2时如下: p a r e n t l : h b i c e a b一 交叉 一 c h i l d l : h b c d i a b p a r e n t 2 :a b c d! e f c h i l d 2 :a b c e e f ( 二)、随机交叉点救的交替式交叉规则 西 南 交 通 大 学 研 究 生 学 位 论 文 子染色体通过随机地从父染色体中选取基因而构成 第1 2 页 。此方式分为均 匀交叉与洗牌式的交叉。 1 、均匀交叉一一随机产生 1个 ( 染色体长度)在阳 ， 月区间均匀 分布的随机数， 然后根据这些随机数的大小，从两个父染色体中选择基 因作为子染色体中的基因。若第 i个随机数 0 . 5 ，则第 1个染色体的 第 i 个基因被选作为第 1 个子染色体的第 i 个基因。第 2 个染色体的第 1个基因构成第 2个子染色体的第 i个基因，反之则相反。如下例，得 均匀分布的随机数向量为 ( 0 . 1 6 , 0 . 4 8 , 0 . 8 3 , 0 . 0 7 , 0 . 9 2 , 0 . 4 0 ) ， 问题的 编码字母表为 a , b , c 。则交叉过程为: p a r e n t l :c a b b a c一 交叉 一 c h i l d l :c a c b b c p a r e n t 2 :a b c a b a c h i l d 2 :a b b a a a 2 、洗牌式交叉一一将父染色体按某一排列顺序调整各基因位置 称为洗牌，将洗牌后的父染色体进行单点交叉后产生子染色体，然后可 对此染色体按原顺序的逆调整各基因位置 ( 称为反洗牌)，成为最终的 子染色体。如下例:排列的顺序为 ( 5 3 6 4 1 2 )，随机交叉点为 3 , 字母表为a , b , c ，则交叉处理为: p a r e n t l : b a c b a a 一 洗牌 一 p a r e n t l : a c ab b a p a r e n t 2 :c b a a b b p a r e n t 2 :b a b i a c b 一 交叉 一 c h i l d l : acaacb c h i l d 2 : b a b r b a 一 反洗牌一 c h i l d : c h i l d 2: c b c a a a b a a b b b ( 三)、排列交叉规则 在此规则下，染色体均为问题字母表的一种排列。因此，可广泛应 用于任务安排和路径规划等，下列例子均设问题字母表达为 a , b , c , d , e , f , g , h )。 西 南 交 通 大 学 研 究 生 学 位 论 文第 1 3页 1 1序交叉 在父染色体中随机选取选取2 个交叉点，则第一个 子染色体交叉点间的基因由第一父染色体保存，其余位置基因则是从第 二交叉点开始依次由第二父染色体的非重复基因填入，直到循环到第二 交叉点，第二子染色体 的构成类似 。如下例 ， 一 一 c h 交点分别是为 3和 6 : p a r e n t l :h b c e a g id f i l d l:h b p a r e n t 2: a b c d e f g h c h i l d 2 : c d f i e g a c a g ) d e fh b 2 , p m x交叉 ( 即部分匹配交叉) 随机选择交叉点，则第一 个子染色体交叉点间的基因由第一父染色体而得，其余基因由第二子染 色体对应位置基因填上，若此基因与交叉点间基因重复，则由此交叉点 间基因对应的第二子染色体基因代替。第二子染色体构成类似。如下例 所示 : p a r e n t l : f b c a h g d e一 c h i l d : dbc j a”g f e p a r e n t 2 : a b c一 d e f g h c h i l d 2 : g b c d e f a h 3 、周期交叉一一一个周期定义为一个代数排列组，如下例的第 一个父染色体和第二个父染色体基因对应关系为 f -a , a -d , d -g , g -f ，形成一个周期 f a d g ;同样有第 2周期 b c ，第三周期 h e 。第一个 染色体的基因属于第一周期时，由相应第 1 父染色体基因代替，属第二 周期时由相应第 2父染色体基因代替，第三周期由相应的第 1 父染色体 基因代替，以此类推。第 2 子染色体的基因构成反之。 p a r e n t l : f b c a h g d e -一 c h i l d l :f c b a h g d e p a r e n t 2 : acbdefgh c h i l d 2 :a b c d e f g h 4 , r -o p t交叉法 此法是由求解 t s p问题而得的，因此需利用点对间距离信息。每个 子染色体由 r 1 个父染色体通过 r 一一o p t交叉算子产生。交叉时首 先确定各父染色体中最近放入子染色体中基因的位置，确定紧跟其后的 未选入的子染色体的基因为待选基因与最新入选基因的距离，确定距离 西 南 交 通 大 学 研 究 生 学 位 论 文第 ， ;页 最近的子染色体填入。如此循环，直到所有父染色体的基因都被选过为 止。下面以2 - 0 p t为例，点对距离如下表所示，其中假定第一子染 色体的第 1 个基 因取 自第 1 父染色体的第一基因，第二染色体的第 1 基 因取 自第 2 父染色体的第一基因: p a r e n t l :a c g f b d e-一 c h i l d l :a c b g f d e p a r e n t 2 :gefdcba c h i l d 2 :g f d e a c b 点对 间距表 间距abcdefg a0 3 81 28 04 2 2 01 4 b3 805 1 3 28 36 81 0 c1 2 5 102 2 917 35 9 d 8 03 22 2 01 52 96 0 e4 2 8 3911 50 4 47 5 f 2 06 87 32 9 4 40 3 4 g1 4 1 05 96 07 5 3 4 0 六、变异操作 复制算子提高了样本的平均适应值，杂交算子可以产生新的个体， 但都是以损失群体的多样性为代价的。为了避免陷入局部最优或搜索停 止不前，可对交叉后的染色体以一个很小的概率p随机改变串上的某 些位，如对二进制串，就是对相应的位取反，即 1 变为 0或 0变为 1 ; 对于多值串，则对相应位在字母表中随机取一个值:对于排列字符串， 则随机调换串中两点的基因。如同生物染色体一样，每一位发生变异的 概率凡很小，一般为 0 . 0 0 1 - 0 . 0 1 .在算法收敛的后期，变异操作起着 非常重要的作用 。 七、自然选择 n-2 m 选 择 速度 西 南 交 通 大 学 研 究 生 学 位 论 文第 i s 将通过三种操作产生的 2 m个新一代个体连同上一代中性能最好的 个个体，共同组成新的群体q= 9 1 1 9 2 1 9 3 1 . . . 1 8 衬。通过自 然 ，既能得到较优个体在每代群体中的连续存在性，又加快了进化的 八、转步霖二，进一步 “ 进化” 基 本遗 传算法如下 图所示 : 西 南 交 通 大 学 研 究 生 学 位 论 文第1 6 页 t = 0 产生初始群 体 ( 规模为n ) 结束 西 南 交 通 大 学 研 究 生 学 位 论 文第1 7 页 第二节遗传算法的数学分析 一、模式定理 ( 一)模式的引入 在遗传算法的执行过程中， 引入了大量的的新信息来帮助指导搜 索。为了准确统计些新信息的量，引入模式的概念。 一个模式就是一个相同的构形，它描述的是一个 串的子集。这是集 合的串之间在某些位上的相同。对于二元字母表 0 , 1 ， 添加一个*( 表 示不确定字母)，通过三元字母表 0 , 1 , * ， 一个模式就可看成一个模 型匹配器。 如模式*1 *表示一个四元子集如下示: 0 1 0 , 0 1 1 , 1 1 0 , 1 1 1 ) a 一般地，对于k个元的字母表 ( 不包括*)，共有 ( k +l )个模 式。所有模式并不是以同等机会产生的。为了定量描述模式，引入模式 的阶和定义长度 。 一个模式h的阶就是出现在模式中的确定位置的数目， 记为 。 f 时，模式 h的数量将增加;当 f ( h ) 模式 h的数量将减少。 假设模式h的适应值与群体平均适应值关系为f ( h ) 二 了 + c 为一常数，则模式 h的复制生长方程可变为: m ( h , t + 1 ) = m ( h , t ) x ( 1 + c ) 从初始群体 ( t = 0 ) 开始，假设 c为一固定值，则有: ( 2 . 2 . 3 ) m ( h , t + l ) = m ( h , 0 ) x ( 1 + c ) ( 2 . 2 这表明，在群体平均适应值以上 ( 以下)的模式将会按指数增长 . 4 ) ( 衰 减)的方式被复制。 2 . 交又操作对模式的形响: 西 南 交 通 大 学 研 究 生 学 位 论 文第 ， 9页 虽然复制可以把按指数增长或减少的模式并行的分配到下一代，但 仅仅只有复制无助于检测搜索空间中新的部分，因为复制不会产生新的 点，为 了检测模式空间中新的部分，需要采用杂交操作 。 交叉操作对模式 h的影响与 。( h )有关。o ( h )越大，模式 h被 破坏的可能性就越大。在单点交叉中，交叉操作要在随机选择出进行交 叉的一对位串的某一随机位置进行交叉，所 以 。( h )越大，h的跨度越 大，随机交叉点落入其中的可能性越大，从而模式 h受到破坏的概率越 大。模式 h被破坏的概率为: 凡= 8 ( h ) / ( l - 1 )( 2 . 2 . 5 ) 则在单点杂交操作下，模式 h的生存概率为: 只二 i 一 凡= 1 -s _ (h )l - 1 ( 2 . 2 . 6 ) 如果交叉本身也是按随机选取方式进行，即以p 进行特定的交叉，则生 存概率有下面的估计: p 2 1 一 p、s ( h ) l一1 ( 2 . 2 . 7 ) 假设复制与交叉操作是不相关 的，经过复制 与杂交后 ，模 式的数量 有下列估计式 : ( “ ， “ h , t ， 肇 “ 一 。 x 碧， ( 2 . 2 . 8 ) 上式表明，在复制与作用下，h的数量取决于:模式适应值是在群 体平均适应值之上还是之下，以及模式的长短。显然，f ( h )越大，s ( h )越小，模式 h生存下来的数量越多。 3 .变异操作对模式的影响: 变异算子是以概率p随机地改变一个位上的值。为了使h 可生存下 来，所有特定的位必须存活.因为单个等位基因存活的概率为: ( 1 - 西南交通大学研究生学位it 立 一 一途 止 2 o 耍 p)并且由于每次变异都是独立统计的，因此，当模式h中。( h )个 确定位都存活的概率为( 1 - 凡尸 h ) 。由于凡+1 ， 模式h 存活的概率可近 似表示为:1 - 凡x o ( h )。 ( 三) 模式定理: 经过复制、杂交、变异等遗传操作后，一个特定模式 h在下一代中 的期望 数量可近似表示为 m( h , t + l )- m ( h , t ) x x 1 一 只x 8 (h )l - 1 一 凡x 0 ( h ) ( 2 . 2 . 9 ) 定理 1 : ( 模式定理)具有短的定义长度，低阶并且适应值在群体 平均适应值以上的模式在遗传算法迭代过程中将按指数增长率被采用。 二. 隐含并行性: 假设在n 个串长为l 的二进制串中， 考虑包含在其中按大于某一只 的概率存活的模式。在单点杂交算子和较小的变异率作用下，其出错率 : 小于( 1 - 只) 的模式的定义长度l : 满足:1 , _ n x ( l - 1 , + i ) x 2 一 ，( 2 . 2 . 1 0 ) 限定群体规模为:n = 1 , / 2 ，则群体所包含定义长度不超过1 ， 的模式 数 为 : n = ( l - 1 ， 一 1 )x n / 4 = c n ( 2 . 2 . 1 1 ) 由上式可知，模式数与群体规模的立方成正比例。表明遗传算法具 有并行性， 即每一代除了对 n个串的处理外，遗传算法实际上处理大约 0 ( n )个模式，从而每一代只执行与群体规模成比例的计算量，就可 同时收到并行地对大约 。 ( n ) 个模式进行有效处理的目的，并且无须额 外的存储 。 三.欺编问题 具有短的定义长度，低阶及高适应值的模式称为基因块。由模式定 理可知， 基因块能够逐步采用、 重组而形成具有潜在的更高适应值的串。 因此把基 因块还可结合 形成高于平均适应值的模式，直 至产生最优解称 为基因块假设。 简单的遗传算法是依靠基因块的重组来找到最优点。如果一个问题 的编码满足基因块的假设，则 g a的求解效率较高，否则效率较低。我 们称那些引导遗传算法出错的函数编码组合为遗传算法欺骗问题。 g o l d b e r g曾设计了一个最小欺骗问题，旨在尽可能使问题的编码 违背基因块假设，使高阶基因块不能生成最优解 。但实验结果表明，对 包含欺骗的问题，用 g a求解时得到最优解和得不到最优解的情况都可 能发生，这表明欺骗不是衡量用 g a解决问题难易程度的唯一标准。 西 南 交 通 大 学 研 究 生 学 位 论 文第 : 2页 四. 遗传算法收致性的分析 设e= 1 * , 0 , 1 和f . = 1 0 , 1 是两个串字母表，el和zl 分别是 y - 和i上包含所有长度为 l串的集合。对于任意串 。 ，按从右到左的 顺序记位，并且最右边 的位 记为第 0 位 ，m 对应于第 i 位上的值。 定义 1 :艺 l中的任一元 s是一个模式，它表示艺 l 上的从属关 系条件。 定义 2 :两个模式s 。 和s 。 是非重叠的当且仅当由 它们的所定义的 串的子集互不相交，即s o 门 s b = 护 ，在其它的情况下，它们重叠。 定义 3 :两 个模式s 。 和s 。 是位置等价的当且仅当 s , =*qs 么 二*0 _ i _ l - 1 ( 2 . 2 . 1 2 ) 定义 4 :设w 是一非重叠的且位置等价的模式集合，令字母集 。 ， *被映射到整数0 ，字母 1 被映射到整数 1 ，则模式族函数f : (p - 4 1 定 义为 : f ( s ) = 艺s 2 ( 2 . 2 . 1 3 ) 定义 5 .设w 是一非重叠的且位置等价的模式集合，令字母集1 o , * 被映射到整数 。 ，字母 1 被映射到整数 1 ，则模式构成函数 9 :尹 分工 定义为: g ( s ) 二 艺s ( 2 . 2 . 1 4 ) 定义 6 e 被映射到整数 设 5 。 则 d : s b e (0 ， 令字母集 。 ，*被映射到整数 。 ，字母 v x v - + i 是一个模式距离函数并定为: ( s 各 .s 怠 ) * 2( 2 . 2 . i 5 ) 问艺t-0 d ( s 。 ， s 。 ) = 其中* 由* 二 * ，由是通常的异或算子 西 南 交 通 大 学 研 究 生 学 位 论 文果2 3贝 定义 t :对于任意的s e 艺l ,设二 二 0 , 1 2, 3,1 一 1 是 s 上位置指标的集合，则所有的可能的杂交位段的集合记为: a= ( i ， j ) ( i ， i ) 。 二x 二， 1 j ( 2 . 2 . 1 6 ) 定义 8 s设 z c ， s 。 ，s a， s 6 ( n , m) e z s 6 . e (p ， 广义杂交算子 c : ( 2 . 2 . 1 7 ) 口j为 5，5 (0 x (p x z - 4so x (p 定义为: c ( s 。 ， s 。 ， z ) = s a 其中t / i 当 n i s m , 5 几 二 5 怠 二s 二 其它情况如下 5 二 二5 么 5 h =5 h 定义 9 :对于任意的s a , s h c= p , o a b 是通过所有可能的广义杂交 算子作用在模式s 。 和s 。 上所得到的模式集合。 定义 1 0 :设y = m ( s 。 ， x ) 二 p ( z ) 为汀 的幂集， s . 变异算子m : ( o x y 斗俨 定义为: ( 2 . 2 . 1 8 ) 其 中 s 二 ， = s 二当 i e x , x 。 y ，s 二 笋 * s a = s a在其它情况下 引理1 :对 于 某 个z c a ， 如 果c ( s o , s , , z ) = s a ， 凡 ， 则 : ( 1 ) f ( s 。 ) + f ( s * ) = f ( s a ) + f ( s b)( 2 . 2 . 1 9 ) ( 2 ) g ( s 。 ) + g ( s 。 ) = g ( s , ) + g ( s ti)( 2 . 2 . 2 0 ) ( 3 ) h ( s 。 + s 。 ) = h ( s + s ,)( 2 . 2 . 2 1 ) 其中函数 h表示两个模式间与 h a m m i n g距离，即两个模式间的不同 位的数 目 证