（车辆工程专业论文）基于遗传算法的邮运汽车组织与优化研究.pdf

西华大学硕士学位论文 一 b 3 8 6 1 1 摘要 本文以省级邮政运输企业为研究对象，讨论大型邮政汽车运输企业的邮路优 化和运行成本的控制两方面的问题，给出了理论公式和算法。本文的研究课题来源 于实践，研究成果又用于指导实践，具有现实意义。本文的主要内容和完成的工作 有： 1 、用遗传算法求解邮路问题。遗传算法是一类模拟生物界自然选择和自然 遗传机制进化过程来求解复杂问题的随机搜索算法。本文在深刻认识遗传算法 ( g a ) 运行机理的基础上，紧紧抓住“交叉”这一g a 思想的精髓，把g a 的 基本原理、分析技术和先进算法较完整地引入到省级邮区中心局的邮路优化中。本 文在图形变换的基础上，用遗传算法实现了对有向邮路的求解。本文所提方法比传 统方法更易于编程实现和求解大规模复杂网络问题。实例表明，本方法能很好地收 敛到有向邮路网络传统算法的结果。 2 、运行成本的控制。为准确核算成本，向成本管理要效益，文章对作业成 本法( a b c ) 进行了深入分析。介绍了作业成本法产生的背景、基本概念、应用步 骤等基本内容，并结合邮政实际提出了作业成本法在我国邮政企业的应用构想。对 成都邮区中心局的汽车运输中心进行了作业分析。 关键词：邮政运输、遗传算法、作业成本法、邮路、优化 ii ( = 尊c ，o 西华大学硕士学位论文 a b s t r a c t t h i st h e s i se x p o u n d st w oa s p e c t s w i t hp r o v i n c i a le n t e r p r i s eo f p o s tt r a n s p o r ta si t s r e s e a r c ho b j e c t s p o s t m e np r o b l e m sa n dac o n t r o lo nc o s t t h em e t h o d sa n df o r m u l a sa r e p r e s e n t e d i ti sm e a n i n gt h a tt h ep r o b l e mc o m e sf r o mp r a c t i c e ，a n dt h ep r o d u c t i o no f s t u d y d i r e c t sp r a c t i c e t h e a c c o m p l i s h e d w o r ki sa sf o l l o w s ： 1 s t u d yo fs o l v i n gp o s t m e np m b l e t n sb yg e n e t i ca l g o r i t h m ( g a ) g - c n e l i e a l g o r i t h m ( g a ) i s ac l a s so fs t o c h a s t i ca l g o r i t h m sf o rs i m u l a t i n gt h ep r o c e s so f n a t u r a l s e l e c t i o na n dm u t a t i o n b a s e do nt h ek n o w l e d g eo ft h er u n n i n gm e c h a n i s mo f g e n e t i c a l g o r i t h ma n dt h ei d e ao f c r o s s o v e r , w h i c hi sq u i n t e s s e n c eo f g e n e t i ca l g o r i t h m , t h eb a s i s p r i n c i p l e ，a n a l y s i st e c h n i q u ea n da d v a n c ea l g o r i t h mo fg e n e t i ca l g o r i t h mi ss y s t e m i c a l l y i n t r o d u c e di n t ot h ep o s t m e np r o b l e m so f p o s t a lt r a n s p o r t a t i o np r o b l e m ( p t p ) t h i s m e t h o di n t r o d u c e di n t h i s p a p e r m a k e st h e p r o g r a m m i n g a n d s o l v i n g m a s s i v e c o m p l i c a t e dn e t w o r kp r o b l e m se a s i e rt h a nb yt r a d i t i o n a la l g o r i t h m s e x a m p l e ss h o wt h a t i tc a l lc o n v e r g et h er e s u l to f t r a d i t i o n a ld i r e c t e d p o s t m e np r o b l e ma l 窟o r i f f t m s 2 ac o n t r o lo nc o s t t h i st h e s i st h o r o n g h l ya n a l y s i st h ea c t i v e l y - b a s e dc o s t i n g ( a b c ) ，f o rt h es a k eo fc o s ta c c o u n t i n ga n db e n e f i t ；i ti sb a c k g r o u n d ，c o n c e p t i o na n d p r o g r e s so f a b c t h a ta r ei n t r o d u c e d t h ec o n c e i v eo f a p p l y i n ga b c o ne n t e r p r i s eo f p o s t t r a n s p o r t i sc o m eu pw i t h t h ea b ca n a l y s i so nt h ep o s tt r u c k so fc h e n g d up o s t a l d i s t r i c tt r a n s p o r t a t i o nc e n t e ri sp u ti n t op r a c t i c e k e yw o r d s ：p o s tt r a n s p o r t a t i o n ，g e n e t i ca l g o r i t h m ，a c t i v e l y - b a s e dc o s t i n g ，p o s tr o a d ， o p t i m i z e i i 堕兰奎堂堡主堂堡丝兰 一 1 1 引言 1 绪论 邮政运输路由规划1 1 2 1 3 1 是典型的多目标运输决策问题，它同时追求运输时限 和运输成本两个目标，并受制于“存储转发”式的作业规范。目前，在国外特别是 西方发达国家，由于其道路网发达，联通性好，且运力充足，因此其邮政运输的矛 盾并不表现在邮件的干线运输上，而主要考虑如何提高收寄与投递的效率；在国内 由于我国道路网相对不发达，地区性差异特别明显，而且运力相对不足，因此在我 国邮政运输规划主要需要解决全国干线( 包括一、二、三级邮政中心局间) 运输的问 题：另一方面由于邮政运输涉及的数据量大、数据种类多，数据之间的关系复杂， 邮政运输规划的软件化工作十分困难。到目前为止，国内整个邮政运输发运计划的 编制基本上依赖于手工凭经验操作，不仅效率低下，而且难以保证方案的最优性， 同时对国内每年至少两次的飞机、火车改点可适应性差。 随着电子商务的快速发展，对物流配送系统提出更高要求，邮政运输部门如何 改进路由规划，通过计算机快速、合理安排邮运路线和邮运车次，以保证在提高传 统服务质量的同时，适应电子商务的发展具有重要意义。 邮路结构是实现邮件异地转移的基础设施，它是在交通运输网的基础上，按照 一定的要求确定的适合于邮政运输的道路集合。邮政运输网可分为全国干线网和省 内网。干线网主要针对全国一、二级邮政中心局间的邮件运输，省内网则主要面对 省内二、三级邮政中心局间的邮件运输。在不同的地域，邮路等级有着很大的差别。 相对而言，东南部交通运输网络发达，邮路等级较高：而西部地区则相对落后，邮 路状况不甚理想：另外，由于自然灾害造成的邮路断路也时有发生。 运输工具是实现邮件异地转移的载体，是以一定的邮路结构为基础的：邮政运 输主要依赖于委托办理，特别是干线运输，需要依托航空和铁路部门提供的运能支 西华大学硕士学位论文 持，车辆丌行时刻、停靠站点和容间大小都不具备自主权力。虽然经过一定时间的 积累，自办邮路有了很大的发展，但主要还是通过汽车邮路来完成部分省内邮件的 运输。另外，邮件运输还涉及到少量的轮船运输。 路由优化目的就是要从现有的交通运输网中寻找到各邮政中心局对间的最短 路径。中国邮路问题是一个目前尚未完全解决的著名图论问题，是为数不多由中国 学者首先提出并引起世人重视的当代著名难题，在实际生活中有许多应用。有向邮 路问题是它的一种形式。传统的有向邮路算法存在编程不容易、手工操作容易出错 和当邮路网络规模和复杂性较大时，运算量急剧增加以致手工操作不可能的缺陷。 遗传算法g a ( g e n e t i ca l g o r i t h m s ) 是计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ) 的一 个重要分支，它是一种智能化、仿生类随机寻优算法，具有传统优化算法无可比拟 的优点。如：g a 不依赖于具体问题：采用进化机制、作用对象为一群体：不易陷于 局部极优，具有全局收敛性：不要求目标函数连续可微，甚至不要求有明确的目标 函数表达式；g a 的搜索过程具有隐并行性( i m p l i c i tp a r a l l e l i s m ) ，同时g a 本身也可 以并行实现。此外，g a 还具有很强的自适应、自组织、自学习性和高度的鲁棒性 ( r o b u s t n e s s ) 。 遗传算法是一种比较好的全局搜索算法，用遗传算法来求解有向邮路问题从而 探索用遗传算法求解整个邮路问题是本文的出发点。 1 2 研究背景、内容与目的 1 2 1 研究背景 省一级的邮政运输( 中心) 局是比较典型的大型汽车运输企业，主要承担从邮 件集散地如铁路、航空枢纽到各地、市( 州) 、县的邮政运输任务，在其业务管理 中包括了生产组织、指挥调度、设备和车辆的管理、车务统计与分析、邮路上邮件 袋( 套) 数的平衡计算和袋公里统计分析、车辆的维护保养以及对驾驶员的综合管 理等方面的工作。由于管理的内容和层次具有多样性、复杂性，因此，有必要在邮 政汽车运输企业中，通过将计算机技术与现代企业管理相结合，实现对企业的运输 2 西华大学硕士学位论文 规划和生产过程的全自动控制管理，提高由日运生产的效率f 4 。 近年来，发达国家在物流管理理论和实践方面的发展，和它带给公路运输业的 巨大变革与进步，引起国内公路运输界的密切关注【埘。现代物流业是把握竞争优势 的有效方式，将为国民经济在高起点上持续发展，提供基础动力。在经济全球化和 信息化的推动下，现代物流业已从为社会提供传统运输服务，扩宽到以现代科技、 管理和信息技术为支柱的综合物流系统。物流，被人们看作我国公路运输业在下世 纪发展的新领域，新的经济增长点，被人们称之为货物运输企业在经营方式发展上 的高级阶段。中国邮政运输企业从事的是传统的物流业，正在朝着现代物流企业迅 速发展。 邮政在开拓电子商务物流配送市场有着许多天然的优势：邮政的物流系统在规 模上可以浼是全国晟大的；作为一个传统的物流企业，许多先进的物流理论、技术、 设备等往往最先在它上面得到实施和应用；同时它还有一套比较合理的管理和运作 组织；邮政的信誉也是一个极大的优势。邮政物流只要能够合理地与电子商务结合， 就可以发挥出巨大的作用【7 l 。 随着我国加入w t o 和人民群众通信方式、生活方式以及国民经济的发展、变 化，邮政运输的业务范围发生了巨大变化，曾经不被邮政人注目的现代物流业务将 成为中国邮政今后几年内重点培育的支柱型业务，邮政物流也将由此迈开大步。据 【雪家邮政局有关部门介绍，在今年，邮政物流业务收入计划已经要求达到1 5 3 5 亿 兀。 随着物流理论和实践的发展，物流业自身业在迅速的发展，其中物流信息支持 系统在现代物流管理中的具有举足轻重的特殊地位和作用就是一个最典型的特征。 比如，第三方物流企业就是集成物流服务供应商，它的四个显著特点，这也是区别 于传统物流企业最显著的特征就是：一是它以信息技术为主导，离开了信息技术， 集成物流服务只能成为空谈，也可说，信息技术是第三方物流企业的灵魂：二是它 强调物流功能的集成。也就是说，它能为使用者提供集成化功能服务，而以往传统 的物流企业其物流功能是分开的；第三，它提供的是个性化的服务，即第三方物流 是按企业的实际情况，根据企业流程为企业度身订做的一种物流服务；第四，它能 西华大学硕士学位论文 提供网络化服务。也就是它能有效协调第四方、第五方物流资产，以达成为使用者 提供满意服务。所有这些，围绕的一个核心，就是信息系统。 对于在物流业务信息支持系统的建设，必须完善信息系统的功能以满足客户对 物流运递时限和配送服务方面的需求，要更好地通过这套系统强化物流业务的管理 功能，起到客户查询、业务咨询和内部费用结算的作用，解决好部分局已开发信息 软件接口等方面的问题，增加物流业务所需的功能。同时还要将系统的应用推广到 承办业务的所有运营部门，以满足业务发展的需要。 本课题是在指导老师已经进行了六年的研究基础上，并且研究的成果( 本课题 组使用f o x p r 0 2 5 和p o w e r b u i l e r6 0 等工具，开发了事务处理类型的邮运管理系统： p t m i s v 1 0 版v 3 2 版) 已经被国内四省( 四川、浙江、陕西、西藏) 省一级邮政 运输局应用于汽车运输的全面管理的前提下提出来的，目前获得国家拨款的纵向课 题已丌展理论方面的研究。 1 2 2 研究内容与目的 研究内容： 随着现代计算机信息技术、企业管理理论和现代物流技术的不断发展以及用户 的进一步要求，原系统作为运输信息支持系统，表现出一定的局限性。本课题组总 结以往邮政运输信息管理系统开发的经验和教训，结合相关学科新的研究和发展成 果，在现代计算机网络平台和大型数据库技术应用基础上进行了全面的改版、再开 发工作。 本人参加的研究项目主要有： 【1 】四川省科技厅应用研究项目：汽车运输信息支持系统应用研究 ( j i l 科基 2 0 0 1 1 7 号，项目编号0 1 g y 0 5 1 7 1 ) 2 】四川省科技厅应用研究项目：汽车运输规划与管理信息系统( 课题编号 0 0 2 3 7 7 7 ) 3 】四川省科技厅应用研究项目：交通运输规划与管理信息系统开发研究 ( 川科计 2 0 0 0 1 4 号，课题编号0 0 2 8 7 4 4 ) 4 西华大学硕士学位论文 4 1 企业委托邮运时限与收发班微机管理系统( 课题编号0 0 2 8 7 5 5 ) 其中，汽车运输规划与管理信息系统和交通运输规划与管理信息系统开 发研究已经在2 0 0 3 年1 0 月分别通过四川省科技厅与教育厅的成果鉴定。邮运 时限与收发班微机管理系统于2 0 0 3 0 4 月通过企业( 成都邮区中心局) 验收。本 人在上述项目中承担的主要工作是邮路( 即邮运汽车行驶线路) 的优化和运行成本 的控制两个方面，作为上述项目的重要组成部分，已经经过指导老师反复的检查， 并且在成都邮区中心局( 原四川i 省邮政运输局) 正式运行。 研究目的： 在我国邮政运输中，汽车运邮的比重近十多年来呈迅速不断增长之势，使用范 围遍及全国。邮政汽车的运输问题涉及因数众多，关系十分复杂，现有的理论、方 法、模型和实际生产中，基本上是采用静态、单一物流或确定型的运输问题。对于 邮政运输这样随机的、动态的和多种物流、有严格时限和众多外部约束的特大型、 复杂、并行的特种汽车运输组织优化问题的研究，应当从整体角度出发，全面综合 考虑各种邮件的特点、要求，研究在动态时间变化及各种随机因数条件下的综合物 流问题，并且应当对一定历史时间的邮运生产数据收集整理，进行数据挖掘，在现 代信息技术的平台上深入研究邮政汽车运输组织优化。这个问题的研究，对于邮政 通信生产“拉近空间、缩短时间”两个主要质量指标，对于降低生产成本都具有相 当大的意义。 1 2 3 完成的主要工作 邮路优化和运行成本的控制主要完成的工作包括： ( 1 ) 邮路优化。根据省一级的邮路的实际情况，首次将人工智能技术引入到中 心局邮路这一复杂系统的计划安排的优化中，根据邮政运输动态的运输量、运行成 本、点与点之间的距离采用遗传算法，建立数学模型，对邮路进行优化。 ( 2 ) 运行成本的控制。 邮政运输是实现实物邮件空间异地转移的基础，邮运路线安排是否合理直接影 响到邮政通信的质量和效果。电子商务的快速发展对物流配送系统提出了更高的要 西华大学硕士学位论文 求，邮政部门正在努力提高服务质量、降低运营成本。作业成本法( a c t i v i t yb a s e d c o s t i n g ，简称a b c ) 是一种全新的企业管理理论和方法，是以作业为基础，通过对 作业成本的确认、计量而计算产品成本的方法。在邮政的生产环节上实施作业成本 法是个创新，具有可行性，在邮政企业的扭亏增盈中具有现实意义 1 3 国内外研究现状及发展趋势 在欧、美等发达国家，邮政汽车运输中开展计算机管理较早，应用的范围大致 包括：运输网点规划、车辆行驶线路选择、运输任务分配、运输管理决策、编制运 输生产计划、各项运输数据的统计、分析与处理等。 在国内，有的学者从汽车运输的最优经营管理问题着手，应用分布参数控制理 论和方法建立了汽车运输问题最优控制的数学模型【8 】，并用算子半群理论和方法给 出了最优控制问题的解和经济学解释【9 】，但这些研究都没有针对邮政运输的特殊性 进行研究；一些邮政运输业内人士则从生产实践出发，分别就运输环节控制、指挥 调度系统设计、邮路建设、基于g i s 的邮运网路管理调度、干线快速邮路建设、中 心局体制下邮区网结构优化、汽车邮运作业组织的优化、干线邮运汽车的动态管理 以及邮政运输介入第三方物流等问题提出了一些思路和方案，但没有从理论上进行 深入研究【 0 j ；另外一些作者等对p t p 问题( 邮政运输问题) 较详细的研究，并对c i m s 下邮政物流网最优计划调度提出了方案，但其数学模型是基于多种运输方式下的， 没有对中心局模式下汽车运输进行讨论 1 ”。在我国加入w t o 、i t 技术的日益发展和 中心局模式下，开展汽车运输组织与优化的研究是十分必要的。 6 西华大学硕士学位论文 2 遗传算法的基本原理及其数学基础 2 1 遗传算法( g e n e t i ca l g o r i t h m s ) 简介 遗传算法( g e n e t i ca l g o r i t h m s ) 是基于生物进化理论的原理发展起来的一种广 为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个 体之阳j 的信息交换，搜索不依赖于梯度信息。它是在7 0 年代初期由美国密执根 ( m i c h i g a n ) 大学的霍兰( h o l l a n d ) 教授发展起来的。1 9 7 5 年霍兰教授发表了第一 本比较系统论述遗传算法的专著自然系统与人工系统中的适应性( a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ) ) 0 2 1 ) 。遗传算法最初被研究的出发点不是为专门解决 最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架， 都是为当时人工智能的发展服务的m 叫w 。迄今为止，遗传算法是进化算法中最广为 人知的算法。 近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用，取得了一 些令人信服的结果，所以引起了很多人的关注，而且在发展过程中，进化策略、进 化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、 可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等【l 卜 2 4 1 2 1 1 生物遗传概念在遗传算法中的对应关系 遗传算法与其他的优化方法不同，它师法大自然，摒弃了传统的搜索方式，模 拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问 题域中的可能解看作是群体的一个个体( i n d i v i d u a l ) 或染色体( c h r o m o s o m e ) ，并 将每一个体编码( e n c o d e ) 成符号串形式，模拟达尔文的遗传选择和自然淘汰的生 西华大学硕士学位论文 物进化过程，对群体反复进行基于遗传学的操作( 选择( s e l e c t i o n ) ，交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ) ，根据预定的目标适应度函数( f i 恤e s s ) 对每个个体进行评价，依据 适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式 来搜索优化群体中的最优个体，它能够在搜索过程中自动获得和积累有关搜索空间 的知识，并且自适应地控制搜索过程以求得最优解。遗传算法类似于自然进化，通 过作用于染色体上的基因寻找好的染色体来求解问题。 生物遗传概念在遗传算法中的对应关系f 2 5 l 见下表： 生物遗传概念遗传算法中的作用 适者生存在算法停止时，最优目标值的解有最大的可能被留住 个体( i n d i v i d u a )解 染色体( c h r o m o s o m e )解的编码( 字符串、向量等) 基冈( g e n e )接种每一分量的特征( 如各分量的值) 适麻性( f i t n e s s )适应函数值 群体( p o p u l a t i o n )选定的一组解 种群( r e p r o d u c t i o n )根据适应函数值选取的一组解 交配( c r o s s o v e r )过交换原则产生的一组新解的过程 变异( m u t a t i o n )编码的某一个分量发生变化的过程 表2 一l 生物遗传概念在遗传算法中的对应关系 2 1 2 遗传算法的特点 遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用1 2 卜 ”j 。搜索算法的共同特征为：( 1 ) 首先组成一组候选解；( 2 ) 依据某些适应性条件 测算这些候选解的适应度；( 3 ) 根据适应度保留某些候选解，放弃其他候选解；( 4 ) 对保留的候选解进行某些操作，生成新的候选解。 遗传算法是一种通过模拟自然进化过程解决最优化问题的计算模型。最优化问 8 西华大学硕士学位论文 题通常可归结为极大化问题，利用数学公式描述就写作： m a xf ( x ) ( 2 1 ) 其中f ( x ) 为目标函数，s 为可行域，它们是由工程实际问题的具体条件决定 的。利用遗传算法解最优化问题，首先应对可行域中的点进行编码，然后在可行域 中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的b 标函数 值，也就是编码的适应度，接着就像自然界中一样，利用选择机制从编码组中随机 挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较 多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过 程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交 换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某 位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过 程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解 最优化问题所得到的最终结果。 从以上介绍可以看出，遗传算法还具有以下几方面的特点： ( 1 ) 遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。 此操作使得遗传算法可直接对结构对象进行操作。 ( 2 ) 许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算 法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局 部最优解的风险，同时算法本身易于实现并行化。 ( 3 ) 遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函 数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束， 而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。 ( 4 ) 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜 索方向。 ( 5 ) 具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自 行组织搜索，时硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。 9 西华大学硕士学位论文 2 1 3 遗传算法的运用领域 前面描述的是简单的遗传算法模型，可以在这一基本型上加以改进 学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域： ( 1 ) 优化：遗传算法可用于各种优化问题。既包括数量优化问题 合优化问题。 使其在科 也包括组 ( 2 ) 程序设计：遗传算法可以用于某些特殊任务的计算机程序设计，如元胞 计算机。 ( 3 ) 机器学习：遗传算法可用于许多机器学习的应用，包括分类问题和预测 问题等，如预测天气或预测蛋白质的结构。 ( 4 ) 经济学：应用遗传算法对经济创新的过程建立模型，可以研究投标的策 略，还可以建立市场竞争的模型。 ( 5 ) 免疫系统：应用遗传算法可以对自然界中免疫系统的多个方面建立模型， 研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。 ( 6 ) 生态学：遗传算法可以应用于对生态学的一些现象进行建模，包括生物 间的生存竞争，宿主寄生物的共同进化，共生现象，甚至包括生物学“军备竞 赛”。 ( 7 ) 进化现象和学习现象：遗传算法可以用来研究个体是如何学习生存技巧 的，一个物种的进化对其他物种会产生何种影响等等。 ( 8 ) 社会经济问题：遗传算法可以用来研究社会系统中的各种演化现象，例 如在一个多主体系统中，协作与交流的是如何演化出来的。 2 2 遗传算法的基本原理 在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体， 形成初始群体：通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体， 选择高适应度的个体参加逮传操作，经过遗传操作后的个体集合形成下一代新的种 群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。 1 0 西华大学硕士学位论文 下面就是遗传算法思想 2 7 3 0 j ： ( 1 ) 初始化群体； ( 2 ) 训。算群体上每个个体的适应度值： ( 3 ) 按由个体适应度值所决定的某个规则选择将进入下一代的个体： ( 4 ) 按概率p 。进行交叉操作： ( 5 ) 按概率p m 进行突变操作； ( 6 ) 没有满足某种停止条件，则转第( 2 ) 步，否则进入( 7 ) 。 ( 7 ) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。 程序的停止条件有如下二种：完成了预先给定的进化代数则停止；种群中的最 优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。 根据遗传算法思想可以画出如右图所示的简单遗传算法框图： 图2 - 1 简单遗传算法框图 1 1 西华大学硕士学位论文 下面是算法的形式化描述： 迭代开始( i t e r a t i o n ) ：t = 0 初始化( i n i t i a l i z e ) ：p ( 0 ) = t 8 l ( o ) ，a 2 ( o ) ， a i l ( o ) ) 适麻性评价( e v a l u a t e ) ：p ( o ) = “( 8 】( o ) ) ，f f a 2 ( 0 ) ) ，f ( ( 0 ) ) ) w h i l e ( 循环) t ( p ( t ) ) t r u e d o 选抒( s e l e c t ) ：p7 ( t ) = s ( p ( t ) ，p s ) 交义( c r o s $ o v e t ) ：p 4 ( t ) = c ( p ( t ) ，p c ) 变异( m u t a t e ) ：p ”( t ) ；r 1 1 ( p ( t ) ，p i ) 新一代群体：p ( t + 1 ) = p 。( f ) ，t = t + 1 适应性评价( e v a l u a t e ) ：p ( t 十1 ) = “( a l ( 什1 ) ) ，f ( a 2 ( t + 1 ) ) ，f ( a t l ( 什1 ) ) ) 结束( e n dd o ) 遗传算法的形式化定义为8 元组： g a = ( c ，e ，p o ，m ，中，r ，、i ，t ) ( 2 - 2 ) 式中 c 个体的编码方式e个体适应度评价函数 p o 初试群体m群体大小 0 选择算子r交叉算子 、l ，变异算子t遗传算法的终止条件 2 2 1 编码方式( c o d i n g ) 在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作， 而是对表示可行解的个体编码施加选择，交叉，变异等遗传操作，通过这种遗传操 作来达到优化的目的，这是遗传算法的特点之一。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步 骤。d e j o n g 曾提出了两条操作性较强的实用编码原则( 1 5 】。 编码原则一应使用能易于产生与所求问题相关的且具有低阶，短定义长度模 式的编码方式。 1 2 耍兰查堂堡主堂垡堕苎 编码原则二应使用能使问题得到自然表示或描述的具有最小编码字符集的编 码方案。 总的来说这些编码可咀分为三大类：二进制编码方式，浮点编码方式，符号 编码方式。 1 ) 二进制编码方式。 二进制编码方式是遗传算法中最常用的一种编码方式，它使用的编码符号集是 由二进制符号0 和1 所组成的二值符号集( 0 ，1 ) ，它所构成的个体基因型是 一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。 假设某一参数的取值范围是 u 一，l ，t 。 ，我们用长度，二进制编码符号串来表示 该参数，则它总共能够产生2 种不同的编码，若使参数编码时的对应关系如下： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 020 斗u 。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = l 斗u 。+ 6 1 1 1 1 1 1 1 l 1 1 1 1 1 1 1 l 2 2 一l _ 己，。 则二进制的编码精度为： 占：u m a x - u m i n( 2 3 ) 2 。一1 二进制编码方式有以下一些优点： 编码，解码操作简单易行。 交叉，变异等遗传操作便于实现。 符合最小字符集编码原则。 便于利用模式定理对算法进行理论分析。 2 ) 浮点数编码方式 对于一些多维，高精度要求的连续函数优化问题，使用二进制编码来表示个体 时将会有一些不利之处。首先是二进制编码存在着连续函数离散化的映射误差。个 体编码串的长度较短时，蕺熊达不裂精凄要求 两个体编码串的长度较长时。虽然 1 3 西华大学硕士学位论文 能提高编码精度，但会使遗传算法的搜索空间急剧扩大。其次是二进制编码不便于 反映所求问题的特定知识，这样也就不便于开发对问题专门知识的遗传运算算予， 人们在一些经典优化算法的研究中所总结出的一些宝贵经验也就无法在这里加以 利用，也不便于处理非平凡约束条件。 为改进二进制编码方法的这些缺点，人们提出了个体的浮点数编码方法。所谓 浮点数编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个体 的编码长度等于其决策变量的个数。 在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中 所使用的交叉，变异等遗传操作也必须保证其运算结果所产生的新个体的基因值也 在这个区间限制范围内。 浮点数编码方式有下面几个优点： 适合于在遗传算法中表示范围较大的数。 适合于精度要求较高的遗传算法。 便于较大空间的遗传搜索。 改善了遗传算法的计算复杂性，提高了运算效率。 便于遗传算法与经典优化方法的混合使用。 便于设计针对问题的专门知识的知识型遗传算予。 便于处理复杂的决策变量约束条件。 3 ) 符号编码方式 符号编码方式是指个体染色体编码串中的基因值取自一个无数值含义，而只有 代码含义的符号集。这个符号集可以是一个字母表，如( a ，b ，c ，d ，) ： 也可以是一个数字符号表，如( 1 ，2 ，3 ，4 ，5 ，) ；还可以是一个代码 表，女口 a l ，a 2 ，a 3 ，a 4 ，a 5 ，) 等等。 符号编码的主要优点是： 符合有定义积木块编码原则。 便于在遗传算法中利用所解问题的专业知识。 便于遗传算法与相关近 臻算法之润骢瀛合馕囝。 。 1 4 西华大学硕士学位论文 2 2 2 遗传算子 2 2 2 1 选择算子( s e l e c t i o no p e r a t o r ) 选择即从当前群体中选择适应值高的个体以生成交配池( m a t i n gp 0 0 1 ) 的过程。 选择的基础是适应度值，不同的问题有不同的适应度函数，对于适应度函数值高的 个体在下一代中有较多的选择机会，而适应度值低的个体，则在下一代产生数目较 少后代，最终逐渐被淘汰。通过这样的筛法，使得群体一代比一代优良，最终取得 最优解。目前常用的选择算子有以下几种旧2 7 】： 适应值比例选择( f i t n e s s - p r o p o r t i o n a t es e l e c t i o n ) 、精英选择( e l i t i s t s e l e c t i o n ) 、联赛选择方法( t o u r n a m e n ts e l e e t i o n o 1 ) 适应值比例选择 它是目前遗传算法中最基本也最常用的选择方法，也叫赌轮或蒙特卡罗选择 法。在浚方法中，各个个体的选择概率与其适应度值成比例。其选择概率公式如下： p = _ ( 2 4 ) f ，；1 式中： p 为选择概率；i 为染色体序号；，为个体i 的适应度值；n 为染 色体群体数。显然，概率p 反映了个体i 的适应度在整个群体的个体适应度总和 中所占的比例，、个体适应度越大，其被选中的概率就越高，反之亦然。按上式计算 出群体中各个个体选择概率后，就可以决定那些个体被选出。 2 ) 精英选择 精英选择 1 6 1 的思想是把群体中适应度值最高的个体不进行配对交叉而直接复 制到下代中，这种选择方法又称复制。其优点是，进化过程中某一代的最优解可不 被交叉和变异操作所破坏，但是，这也隐含了一种危机，即局部最优个体的遗传基 因会急速增加而使进化有可能陷入局部解。也就是说，该方法的全局搜索能力差， 更适合单峰性质的搜索空间搜索，而不适合多峰性质的搜索空间搜索，所以此方法 一般要与其他选择方法结合使用。 西华大学硕士学位论文 3 ) 联赛选择 联赛选择方法【”1 的基本思想是每次选取个体中适应度最高的几个遗传到下一 代群体中。在联赛选择操作中，只有个体适应度之间的大小比较运算，而无个体适 应度之间的算术运算，所以它对个体适应度是取正值还是取负值无特别要求。联赛 规模用q 表示，也称为q 一联赛选择( q t 0 啪锄e n ts e l e c t i o n ) 1 5 】。根据大量实验总 结，联赛规模一般取q = 2 。 联赛选择的具体操作过程是： 从群体中随机选取n 个个体进行适应度大小的比较，将其中适应度最高的个 体遗传到下一代群体中。将上述过程重复m 次，就可得到下一代群体中的m 个个 体。 2 2 2 2 交叉算子( c m s s o v e ro p e m t o r ) 交叉是将选择后的种群中的个体，放入交配池中，随机地配对，称父代，按照 选定的交叉方式及确定的交叉概率只，把成对个体的基因，部分地进行交换，形 成一对子代。可见交叉后，生成新的个体。交叉方式分为： 单点交叉( o n e p o i mc r o s s o v e r ) 、多点交叉( m u l t i p o i mc r o s s o v c r ) 、一致交 叉( u n i f 0 咖c r o s s o v e r ) 。本文采用单点交叉。 1 ) 单点交叉又称为简单交叉 具体操作是：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两 个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的例子 例1 配对个体 p a r e n t s 父代 个体1ol110 j 01 l01 个体2 1ol01lloo1 0 交叉点位黉5 交叉后 。镌p r i n g 后代 后代1 0lll 0 j100l0 1 6 堕些查堂堡主兰堡笙苎 一 后代2 10l01 f o1 101 父代 后代 匿惑添随圆圈蕊圈圜圆 蹈疆盈豳嘲蹈蕊图随圆 圈2 - 2 单点交叉圈 2 ) 多点交叉 将一对父代个体的基因链，随机地多点切断，部分交换重组，产生一对新个体， 为子代。 下面给出了多点交叉的例子 例2 p a r e n t s 父代 个体1 ol1l00l101 个体2 l0l0ll00l0 交叉点位置 569 交叉后 o f f s p r i n g 后代 j ，j ，0 后代1o1111l1111 后代2 10lo000000 3 ) 一致交叉 致交叉是指通过设定屏蔽字( m a s k ) 来决定新个体的基因继承两个| 日个体 中哪个个体的对应基因。致交叉的操作过程表示如下：当屏蔽字中的位为0 时， 后代l 继承旧个体l 中对应的基因，当屏蔽字位为1 时，后代l 继承旧个体2 中对应的基因，因此生成一个完整的后代1 。反之，可生成后代2 。 下面给出一致交叉的例子 西华大学硕士学位论文 例3 p a r e n t s 父代 个体1 011l001l010 个体2 10101l00101 屏蔽样本l00l 1100101 交叉后 o f f s p r i n g 后代 后代1 11110l111l1 后代2 0 011l000000 22 _ 23 逆转算子( i n v e r s i o n ) 在自然遗传学中有一种称作倒位的现象，在染色体中有两个倒位点，在这两点 问的基因位置倒换，使得那些在父代中离得很远的基因位在后代中紧靠在一起。在 g a 中相当于重新定义基因块，使染色体位串上的重要基因更加紧凑，更不易被交 叉算子所分裂。仿照此现象，h o l l a n d 提出了逆转操作算子盼2 引。 逆转操作首先在个体位串上随机地选择两个点，位串染色体被这两个点分成三 段，将中| 日j 段的左右顺序倒转过来与另两段相连，形成新的个体位串。比如：长度 为1 0 的二进制位串，其中下划线标示的等位基因为重要基因： 工少1 11 011 01 ( 一是倒位位置) 经例位后变为l 旦l1 011101 。新的位串中重要基因更为靠近，被单点交叉 算子分离的可能性大大降低了。 逆转算子一般要求采用类似于乱序编码的带基因位标号的染色体结构。比如， 长度为l o 的位串： 位串： 101 1101l0l 基因位编号： 123456789 1 0 按照上述方法实施逆转操作后，编号也随之翻转： 位串： 一1 01 l01l101 基因位编号： l28 765439 1 0 埔 西华大学硕士学位论文 这样倒位操作就不会影响个体位串的适应值计算。 采用逆转算子一般遵循五种交换规则： i 1 严格同序交换，只允许同序位串才能交换。 2 生存性交换，允许不同序位串进行交换，如果子代码串不包含完整的遗传信息， 则不把它们放入新代群体中。 3 任选方案交换，随意选择两个位串，并将其中任何一个指定为主序位串，另一 个位串则按主序位串的次序映射，然后再进行通常的交换，这样保证了交换结 果的合法性。 f 4 最佳方案交换，与任选方案交换基本相同，只是将两个位串中适应值高的位串 做为主序位串。 5 结构修复，对于两个子代位串中重复或短缺的基因，随机将重复的基因改变为 缺省的基因，形成完整的位串结构。 目f j ，这五种原则在基于二避制编码的参数优化问题的g a 求解中还很少采 用。对于某些问题要求采用具有显著物理含义的特殊编码方式，可以根据g a 进化 的困难程度适当应用。 2 2 2 4 变异算子( m u t a t i o no p e r a t o r ) 从遗传算法运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的 主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助 方法，但它也是必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能力。 交叉算子与变异算子的互相配合，共同完成对搜索空间的全局搜索和局部搜索，从 而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。一般分为：基 本位变异( s i m p l em u t a t i o n ) 、均匀变异( u n i f o r mm u t a t i o n ) 、边界变异( b o u n d a r y m u t a t i o n ) 。 基本位变异操作2 7 1 是指对个体编码串中以变异概率只随机指定的某一位 或某几位基因座上的基因值作变异运算。 例 1 9 西华大学硕士学位论文 j ， 【变异前 ol1ioo1l o1o _- 变异厉