（计算机软件与理论专业论文）遗传算法在物流配送优化调度中的应用.pdf

太原理工大学硕士研究生学位论文 遗传算法在物流配送优化调度中的应用 摘要 随着科学技术的日益进步，物流系统逐渐成为现代社会经济系统的重 要支柱，物流总成本已在国民生产总值中占有相当的比重。物流配送是企 业与消费者在物流活动中直接相连的环节，在物流的各项成本中，物流配 送成本又占了相当高的比例。因此，配送车辆调度( v e h i c l er o u t i n g p r o b l e m ，简称v r p ) 的合理与否直接影响到配送的成本和企业效益。 近年来，将遗传算法应用于v r p 是一大研究热点。目前，国内外有很 多关于基于遗传算法的v r p 问题研究，但大都淡化了网络拓扑限制，侧重 于理论性的算法研究，基于这一点，无论是在初始群体的产生还是变异交 叉策略上，都有相当大的自由空间，处理起来比较容易，然而，现实中， 网络拓扑的限制是不可忽略的，因此，实用性较弱。本文在充分考虑到网 络拓扑限制的基础上，运用遗传算法思想，展开对v r p 问题的进一步研究。 另外，本文还构造了可以产生个体的有穷自动机，它不仅可以用来方便地 产生初始群体，而且也还为进化时新个体的注入提供了极大的便利，有利 于保证群体的多样性，避免陷入局部最优解。 本文主要研究内容有： 1 针对单源点的v r p 建立数学模型，不同于以往的研究，本文注重网络拓 扑限制； 2 首次构造自动机，用以产生初始群体和向进化群体中补充新个体； 3 运用遗传算法思想优化群体以取得最优解； 4 以山西省长治市煤炭物流为背景，进行具体的实验实现，并进行 t 太原理工大学硕士研究生学位论文 试验分析，得出试验结论。 关键字：物流配送，车辆调度，遗传算法，有穷自动机 太原理工大学硕士研究生学位论文 t h ea p p l i c a t i o no f g e n e t i ca l g o r i t h m i nv e h i c l er o u t i n gp r o b l e m a b s t r a c t w i t ht h ed e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y ，l o g i s t i c s s y s t e mi s b e c o m i n gm o r ea n dm o r ei m p o r t a n ti nt h es o c i a le c o n o m i c sa n dt h el o g i s t i c s g r o s sc o s tt a k e sah i g ha c c o u n ti ng d p l o g i s t i cd i s t r i b u t i o ni sad i r e c tl i n k i n g c o n j u n c t i o nb e t w e e ne n t e r p r i s ea n dc u s t o m e r s ，t a k i n gac o n s i d e r a b l ep r o p o r t i o n i nt h ec o s to fl o g i s t i c t h ev e h i c l er o u t i n gi nd i s t r i b u t i o nw i l lt a k eg r e a te f f e c t o nd i s t r i b u t i o nc o s ta n db e n e f i t so fe n t e r p r i s e r e c e n t l y ，i t sah o tt o p i ct oi n t r o d u c eg e n e t i ca l g o r i t h m ( g a ) i n t ov e h i c l e r o u t i n gp r o b l e ma n dt h e r ea r em a n yp a p e r sd o i n gr e s e a r c ho ni t b u tm o s to f t h e ma n e m p h a s i z et h el i m i t a t i o n so ft h en e t w o r k i nt h i sw a y ，i th a sm o r e f r e e d o mi nt h ep r o d u c t i o no ft h ei n i t i a li n d i v i d u a lp o p u l a t i o na n di nt h ep r o c e s s o fe v o l u t i o n m o r ei m p o r t a n t ，i th a saf a rw a yf r o mt h er e a lu t i l i 哆l a r r u p i n g ，o n t h ef o u n d a t i o no fs t r e s s i n gt h el i m i t a t i o n so ft h en e t w o r ki nv e h i c l er o u t i n g p r o b l e m ，t h i sp a p e r ，u s i n gg e n e t i ca l g o r i t h m ，d o e sf u r t h e rr e s e a r c h b e s i d e s ，t h e p a p e ri n t r o d u c e sa u t o m a t o n ，w h i c hc a np r o d u c ei n d i v i d u a l ，t oc r e a t ei n i t i a l i n d i v i d u a lp o p u l a t i o na n di n s e r tn e wi n d i v i d u a l si ne v o l u t i o np r o c e s s ，k e e p i n g i i i 太原理工大学硕士研究生学位论文 t h ed i v e r s i t yo fp o p u l a t i o na n da v o i d i n gl o c a l l yo p t i m a ls o l u t i o n t h i sp a p e rd o e st h ef o l l o w i n gm a i n l yw o r k ： 1 c o n s t r u c tt h em a t h e m a t i c a lm o d e lb a s e do nv r p ，d i f f e r e n tf r o mo t h e r s ， o nt h ef o c u so fl i m i t a t i o n so ft h en e t w o r k ； 2 f o u n da u t o m a t o nt oc r e a t ei n i t i a li n d i v i d u a lp o p u l a t i o na n di n s e r tn e w i n d i v i d u a l si ne v o l u t i o np r o c e s s ； 3 u s et h et h o u g h to fg e n e t i ca l g o r i t h mt os o l v ev r p ； 4 d oe x p e r i m e n tb a s e do nt h ec o a lt r a n s p o r ta n dd i s t r i b u t i o ns y s t e mi n c h a n g z h i ，s h a n x i k e y w o r d s ：l o g i s t i cd i s t r i b u t i o n ，v e h i c l er o u t i n gp r o b l e m ，g e n e t i ca l g o r i t h m ， a u t o m a t o n i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：耋：l 叁簋 日期： 竺塑：一基! 三一 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为：目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在勰密后遵守此规定) 。 签名： 鑫：3 鱼：耸 日期： 篮型i ：王 导师签名：翌! 递日期：竺堡! 墨： 太原理工大学硕士研究生学位论文 第一章绪论 1 1 车辆物流配送优化调度问题的提出 科学技术的日益进步、生产力和经济的飞速发展，以及需求的不断提高，使物流系 统已逐渐成为现代社会经济系统的重要支柱，物流总成本已在国民生产总值中占有相当 的比重。现代企业为了在市场中提高企业竞争力，加强物流管理就成为降低物资消耗、 提高劳动生产率之后的“第三利润源泉”。物流管理的核心问题就是物流配送，在物流 的各项成本中，物流配送是企业与消费者在物流活动中直接相连的环节，是货物从物流 节点送达收货人的过程。物流配送成本在企业成本中占了相当高的比例。配送的核心部 分为配送车辆的集约、货物配送及送货过程。进行配送系统优化，主要是配送车辆调度 的优化。因此，配送车辆调度( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 的合理与否直接 影响到物流配送的成本和企业效益。特别是多用户配送车辆调度的确定更为复杂。运用 合理的，科学的方法进行配送车辆调度，可以提高物流经济效益、实现物流科学化。在 当前众多研究课题中，车辆调度问题已成为众多学者竞相研究的热门话题。 近年来，将遗传算法应用于物流调度是一大热点。目前，国内外有很多关于基于遗 传v r p 问题研究，但大都侧重于遗传算法而淡化了网络拓扑限制。基于这一点，无论 是在初始群体的产生还是变异交叉策略上，都有相当大的自由空间，处理起来比较容易。 然而，现实中，网路拓扑的限制是不可忽略的，因此，实用性较弱。本文在充分考虑到 网络拓扑限制的基础上，运用遗传算法思想，对v r p 问题进行研究。 1 2 遗传算法的研究背景 随着人工智能技术的引入和不断发展，遗传算法、模拟退火算法、免疫算法等新的 方法以及人工神经网络和专家系统等新技术，为解决大规模优化问题提供了新的辅助手 太原理工大学硕士研究生学位论文 段。特别是遗传算法，在求解全局最优解问题上的性能突出。 遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体 内部染色体的随机信息交换机制相结合的搜索算法。它在搜索之前，先将变量以某种形 式进行编码( 编码后的变量称为染色体) ，不同的染色体构成一个群体。对于群体中的 染色体，将以某种方法评估出其适应值。新一代群体的产生是按下面两个步骤完成的： 首先，根据染色体的适应值选择被保留的染色体以及相应的复制次数；其次，对被选择 的染色体进行重组、变异，产生新的染色体。 遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人 工智能技术，已广泛应用于计算机科学、人工智能、信息技术及工程实践。 传统的遗传算法在个体的产生上未对其进行规范，而本文利用有穷自动机，针对 v r p 问题，将遗传算法中个体的产生规范化。 1 3 自动机 本文创新性地将自动机引入遗传算法，将两者结合。将有穷状态自动机与遗传算法 结合的切入点就在于遗传算法中可行解的编码。有穷状态自动机可以用来识别一定规则 的字符串编码，同时当这个规则确定并且输入列表确定的情况下，它是可以用来，产生 符合一定规则的字符串的。而遗传算法恰好是将问题域中的可能解看作是一个个体或染 色体组成，是一系列的编码。因此，将自动机应用于遗传算法是可行的。针对v r p 问 题，可以构造出相应的产生字符串的自动机，产生字符串的规则为随机原则，输入列表 为受网络拓扑限制的节点集。 自动机( a u t o m a t o n ) 原来是模仿人和动物的行动而做成的机器人的意思。但是现 在已被抽象化为如下的机器。时间是离散的( r - o ，1 ，2 ) ，在每一个时刻它处于所 存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个 时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时 刻的内部状态所决定。作为自动机的例子可以举出由m c c u l l o c h - p i t t s 的神经模型组合所 得到的神经网络模型、数字计算机等。 自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和 识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于 2 太原理工大学硕士研究生学位论文 作为信息处理系统乃至一切信息系统的数学模型。 1 4 本论文主要完成的工作 本文首先介绍了物流配送的相关知识，然后从理论上对遗传算法的基础原理和各 种类型的遗传算法做了阐述，还对有穷自动机做了简单介绍，在此基础上，本文做了一 下研究工作： 1 针对单源点的v i 心建立数学模型，不同于以往的研究，本文注重网络拓扑限制； 2 首次构造自动机，用以产生初始群体和向进化群体中补充新个体； 3 运用遗传算法思想优化群体以取得最优解； 4 以山西省长治市煤炭物流为背景，进行具体的实验实现，并进行试验分析，得出试 验结论。 3 太原理工大学硕士研究生学位论文 2 1 物流配送产生 第二章车辆物流配送优化调度 配送作为先进的物流形式，它的产生以及推广并不是偶然的，而是随着现代商业经 营环境和经营形式的变化而出现的。这些变化主要体现在： ( 1 ) 消费者消费行为的变化 随着人们生活水平的提高，2 0 世纪9 0 年代以来，人们对生活的追求己逐渐从原来 的温饱型、数量型转向小康型，对生活质量的要求越来越高。伴随着这种生活观念的变 化，在经济社会向国际化、信息化急剧转变的基础上，消费者价值观趋于多元化和多样 化，喜欢购买具有差别化的商品。这种消费行为变化对企业的生产和经营产生了深远的 影响，使生产和销售企业在适应消费者消费行为变化的过程中，开始强化物流管理，通 过少批量、多品种、快速化、柔性化的生产和经营来满足消费者的需求。 ( 2 ) 生产商生产策略的转变及其对物流管理的强化 为改变这种状况，现代生产企业空前重视物流管理，要求其物流系统既讲求效率， 又能促进生产、销售战略的灵活调整和转换。为此，生产厂商一方面运用m r p ( 物料需 求计划，m a t e r i a lr e q u i r ep l a n n i n g ) ，j r r ( 准时生产制，j u s ti nt i m e ) 等先进系统加大对 生产和供应中的物流管理，另一方面更加重视销售中的物流管理，即d r p ( 配送资源计 划，d i s t r i b u t i o nr e s o u r c e p l a n n i n g ) 管理，通过构筑物流配送系统直接靠近客户并加强与 客户关系的管理，动态跟踪客户需求状况，以获取最前端的市场需求信息用以化解因市 场信息反馈缓慢、曲解、变形带来的生产、供应、库存决策的失误。这种将物流管理过 程延伸至上、下游环节并具有强大电子商务功能的系统，就是当今最先进的企业经营系 统e r p ( 企业资源计划，e n t e r p r i s e sr e s o u r c ep l a n n i n g ) 系统。 ( 3 ) 电子商务的兴起 近年来，随着网络、通信和计算机技术的迅速发展，使用i n t e m e t 从事商务活动 4 太原理工大学硕士研究生学位论文 已经成为现实。电子商务以其相对低廉的成本、简化的贸易流程、超越时空限制的经营 方式以及其巨大的利润，吸引着世界各国众多厂商。据有关资料显示，目前全世界已有 几十万家公司，1 5 0 0 多家银行介入这一领域。许多专家学者认为，电子商务将成为2 1 世纪新的经济增长点。 在电子商务中，除了少数的电子出版物，如软件、c d 等可以通过网络以电子的方 式送给购买者，其他绝大多数商品仍要通过物流过程完成从供应商到购买者的空间转 移。因为网上购物的消费者地点分散、购物数量少，其配送费用无疑与快速送达相矛盾。 如何低成本、高速度、准确无误地将商品送达，成为物流配送所要研究的对象 ( 4 ) 城市交通限制与燃油成本的上升 随着现代社会城市化的加速发展和私人拥有车辆的增多，城市尤其是大都市的人口 与车辆急剧增加，城市交通尽管通过构筑地面、地上和地下立体化的交通网络体系，但 仍然满足不了人口与车辆的交通需求，城市交通越发拥挤。此外，由于石油能源的严重 减少，燃油价格上涨很快，对汽车提高运营效率、降低运输成本提出挑战。传统收货人 直接从工厂接收货物，构成蛛网状交叉运输路线、运输混乱、效率很低。而配送的优点 就是消除了交叉运输、节约了运输费用，提高了运输工具的装载率，降低空驶，并及时 送货，提高服务质量，用户不需要四处订货，降低了消费者库存。 2 。2 物流配送的流程 物流配送是物流系统中的一个重要环节，由于它直接与消费者相连，因而其地位十 分突出。物流配送的一般定义为，将货物从物流节点送达收货人的过程。配送是在集货、 配货基础上，完全按着用户的要求，包括种类搭配、数量、时间等方面的要求所进行的 运送，是“配 和“送 的有机结合形式。配送的一般流程如图2 1 所示： 图2 - 1 配送流程图 f i g 2 1f l o wc h a r to fl o g i s t i c s 5 太原理工大学硕士研究生学位论文 ( 1 ) 集货 集货是物流配送的准备工作和基础工作。集货工作包括筹集货源、订货、采购、进 货及有关的质量检查、结算、交接等。 配送的优势之一，就是可以集中若干用户的需求进行一定规模的集货。集货是决定配送 成败的初期工作，如果集货成本太高，会大大降低配送的效益。 ( 2 ) 存贮 配送中的储存有储备及暂存两种形态。 储备 配送储备是按一定时期的配送经营要求，形成的对配送的资源保证。这种类型的储 备数量较大，储备结构也较完善，视货源及到货情况，可以有计划地确定周转储备及保 险储备结构及数量。配送的储备保证有时在配送中心附近单独设库解决。 暂存 另一种储存形态是暂存，是具体执行配送时，按分拣配货要求，场地所做的少量储 存准备。由于总体储存效益取决于储存总量，所以在理货，这部分暂存数量只会对工作 方便与否造成影响，而不会影响储存的总效益，因而在数量上控制并不严格。还有另一 种形式的暂存，即是分拣、配货之后，形成的发送货载的暂存，这个暂存主要是调节配 货与送货的节奏，暂存时间不长。 ( 3 ) 分拣及配货 这是配送不同于其他物流形式的有特点的功能要素，也是配送成败的一项重要支持性 工作。分拣及配货是完善送货、支持送货的准备性工作，是不同配送企业在送货时进行 竞争和提高自身经济效益的必然延伸，所以，也可以说是送货向高级形式发展的必然要 求。有了分拣及配货，就会大大提高送货服务水平，所以，分拣及配货是决定配送系统 水平的关键要素。 ( 4 ) 配装 在单个用户配送数量不能达到车辆的有效载运负荷时，就存在如何集中不同用户的 配送货物，进行搭配装载以充分利用运能、运力的问题，这就需要配装。 和一般送货不同之处在于，通过配装可阻大大提高送货水平及降低送货成本，所以配装 也是配送系统中有现代特点的功能要素，是现代配送不同于传统送货的重要区别之处。 ( 5 ) 配送运输 6 太原理工大学硕士研究生学位论文 配送运输属于运输中的末端运输、支线运输，和一般运输形态主要区别在于：配送 运输是较短距离、较小规模、频度较高的运输形式，一般使用汽车和其他小型车辆做运 输工具。 与干线运输的另一个区别是，配送运输路线选择问题是一般干线运输所没有的，干 线运输的干线是惟一的运输线，而配送运输由于配送用户多，一般城市交通路线又较复 杂，如何组成最佳路线，如何使配装和路线有效搭配等，是配送运输的特点，也是难度 较大的工作。 ( 6 ) 送达服务 配好的货运输到用户还不算配送工作的完结，这是因为送达货和用户接货往往还会 出现不协调，使配送前功尽弃。因此，要圆满地实现运到之货的移交，并有效地、方便 地处理相关手续并完成结算，还应讲究卸货地点、卸货方式等。送达服务也是配送独具 的特殊性。 ( 7 ) 回程 在执行完配送的使命之后，车辆需要回程，在一般情况下，回程车辆往往是空驶， 这是降低配送效益、提高配送成本的因素之一。在规划配送路线时，回程路线应当尽量 缩短；在进行稳定的、计划配送时，回程车辆可将包装物、废弃物、残次品运回集中处 理，或者将用户的产品运回配送中心，作为配送中心的资源，向其他用户进行配送。 2 3 物流配送车辆优化调度 国外将物流配送车辆优化调度问题归结为或称之为v e h i c l er o u t i n g p r o b l e m ( v r p ) 。v r p 问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年提出。其目的是在一系 列已知装货点和卸货点组成的运输网络中，组织适当的行车线路，使车辆有序地通过它 们，在满足一定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行 驶里程限制、时间限制等) 下，达到一定的目标( 如路程最短、费用最少、使用车辆数量 尽量少等) 【2 1 。物流配送车辆优化调度问题涉及的面广，需要考虑的因素较多，对配送企 业提高服务质量、降低物流成本、增加经济效益的影响较大，是物流配送系统优化的关 键。 v r p 被提出后，国内外许多学者按不同的标准对其进行了分类，综合起来可分为以 7 太原理工大学硕士研究生学位论文 下几种。 按车辆载货状况区分，有满载问题和非满载问题：按任务目标分，集货或送货和集 送一体化的车辆优化调度问题；按车场数目分，有单源点问题和多源点问题；按车辆类 型分，有单车型问题和多车型问题；按车辆对车场的所属关系分，有车辆开放问题和车 辆封闭问题。按v r p 中各项任务是否有时间限制来区分，有时间窗和没时间窗的车辆 优化调度问题。 ( 1 ) 满载和非满载车辆的优化调度问题 满载问题指当货物量不小于车辆容量时，执行每项任务需要的车辆可能不只一辆， 车辆为完成任务，需满载运行。这类问题可能有两种情况：一种是由一辆车往返多次运 送，另一种是由多辆车分别运送。但对于这类问题可以通过两个步骤将其转化为非满载 车辆优化调度问题：第一步解决整车运输，这就是典型的最短路问题；第二步对于剩下 不满一车的，就按非满载车辆优化调度问题加以解决。 非满载问题指当货物量小于车辆容量时，用一辆车执行任务就存在不满载运行情 况，调度时可安排一辆车执行多项任务，即在一辆车上装载不同货主的货物。当然，这 类问题有一个前提条件，即不同货主的货物允许混装。 ( 2 ) 集货或送货和集送一体化的车辆优化调度问题 集货或送货问题也称为纯装问题或纯卸问题，指所有任务全是集货点( 装货点) 或 全是送货点( 卸货点) ，车辆空车从配送中心出发，去各货主处装满货后返回配送中心， 或是车辆装满货物去各货主处卸货后返回配送中心，这种情况称为集货或送货的车辆调 度安排。 集送一体化问题也称为装卸混合问题，指每一项货运任务都有自己的集货点和送货 点，车辆从配送中心出发，去某一任务的集货地点装货后运至其送货地点卸货( 即装卸 混合) ，完成所有任务后返回配送中心。这种情况称为集货和送货一体化的车辆调度安 排问题。 ( 3 ) 单源点和多源点的车辆优化调度问题 单源点车辆优化调度问题是指所有的车辆均从一个配送中心发出，完成各自的任务 后都返回该配送中心。 多源点车辆优化调度问题是指，存在着多个配送中心，车辆可以从任何一个配送中心派 出，完成任务后，车辆也可以返回其中的任何一个配送中心。随着供应链的集成一体化， 8 太原理工大学硕士研究生学位论文 多源点的车辆优化调度问题将越来越多，越来越重要。对于这类问题可以通过一定的方 法将其转化为单源点的车辆优化 ( 4 ) 单车型问题和多车型问题 单车型问题指车辆和容量都相同；多车型问题指执行任务的各车辆的类型和容量不 完全相同。 ( 5 ) 车辆开放问题和车辆封闭问题 车辆开放问题指车辆完成配送任务后可以不返回其发车场；车辆封闭问题指车辆在 完成配送任务后必须返回其发车场。 ( 6 ) 有时间窗和没时间窗的车辆优化调度问题 如果到达任务点的时间是事先规定的，则称该问题是带时间窗要求的车辆优化调度 问题；若到达和离开时间没有规定，则称该问题就是一个直接的线路安排、没有带时间窗 的车辆优化调度问题。 本文主要讨论单源点、单车型、满载送货车辆封闭优化调度问题。 9 太原理工大学硕士研究生学位论文 3 1 遗传算法的描述 第三章遗传算法介绍 遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体 内部染色体的随机信息交换机制相结合的搜索算法。它在搜索之前，先将变量以某种形 式进行编码( 编码后的变量称为染色体) ，不同的染色体构成一个群体。对于群体中的 染色体，将以某种方法评估出其适应值。新一代群体的产生是按下面两个步骤完成的： 首先，根据染色体的适应值选择被保留的染色体以及相应的复制次数；其次，对被选择 的染色体进行重组、变异，产生新的染色体。遗传算法包括以下基本步骤： ( 1 ) 编码。由于遗传算法不能直接处理解空间的数据，因此，必须通过编码将它们表示 成遗传空间的基因型串结构数据。 ( 2 ) 初始群体生成。由于遗传算法是一种群体型搜索方法，所以必须为遗传操作准备一 个由若干个体组成的初始群体，每个个体一般都通过随机方法产生，并分别对应研究问 题的一个解。 ( 3 ) 适应度评估。遗传算法在搜索过程中一般不需要其它外部信息，仅用适应度来评估 个体的优劣，并以其作为实施遗传操作的依据。 ( 4 ) 选择。选择操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为下 一代繁殖子孙，个体的适应度越高，其被选择的机会就越大。 ( 5 ) 交叉。它是遗传算法中最主要的操作，一般分两步进行，一是对群体中的个体进行 随机配对；二是在配对个体中，随机设定交叉处，使配对个体彼此交换部分信息。 ( 6 ) 变异。是指按一定的概率改变个体的基因链。变异操作同样是随机进行的，其目的 是挖掘群体中个体的多样性，克服遗传操作可能限于局部最优解的弊端。 ( 7 ) 运行参数。遗传算法的运行参数主要包括群体规模、终止进化代数、交叉概率、变 1 0 太原理工大学硕士研究生学位论文 异概率等。这些参数对遗传算法的求解结果和求解效率都有一定的影响。 遗传算法的基本流程如下： 图3 - 1 遗传算法流程图 f i g 3 1f l o wc h a r to fg e n e t i ca l g o r i t h m 3 2 遗传算法的研究内容 遗传算法理论研究的内容主要有分析遗传算法的编码方法、适应值函数、遗传算法 太原理工大学硕士研究生学位论文 的遗传算子、遗传算法参数的选择、全局收敛性和搜索效率的数学基础、欺骗问题、收 敛性分析、并行计算、遗传算法的局部改进及混合遗传算法等。 1 编码方法 遗传算法编码在许多问题的求解中，对算法的性能有很重要的影响。简单二进制编 码的采用得到了h o u a n d q 理论结果s c h e m a 定理、最小字母表原理的支持，但它仍有许 多不足之处。灰色编码可用于克服二进制编码映射的不连续问题，即欧式空间中临近点 的二进制编码在h a m m i n g 距离下并不邻近。动态参数编码的提出是为了克服搜索效率 与表示精度间的矛盾，同时对克服过早收敛现象也有所帮助。此外，多值编码、实值编 码、区间值编码、d e l t a 编码、对称编码以及将以往的合成编码分解成多个相对独立编 码的独立编码策略等多种编码方法也都被证明各有优缺点。这些编码方法的提出是启发 式的，缺乏一个理论基础来判断各种编码方法的好坏并指导它们的设计。为了缓解二进 制编码带来的“组合爆炸和遗传算法的早熟收敛问题，提出了十进制编码。 2 适应值函数 在遗传算法中，适应值是用来区分群体中个体( 问题的解) 的好坏。遗传算法正是 基于适应值对个体进行选择，以保证适应值好的个体有机会在下一代中产生更多的子个 体。在使用遗传算法求解具体问题时，适应值函数的选择对算法的收敛性以及收敛速度 的影响较大，故针对不同的问题需根据经验来确定相应的参数。例如：考虑函数在搜索 点的函数值及其变化率，并将该信息加入适应值函数，使得按概率选择的染色体不但具 有较小的函数值( 对极小化问题而言) ，而且具有较大的函数变化率值。实验结果表明， 这类方法的收敛速度明显高于标准遗传算法。 基于约束区域神经网络的动态遗传算法，将遗传算法的全局搜索和约束区域神经网 络模型的局部搜索结合起来。利用动态遗传算法确定神经网络模型的初始点，同时使用 神经网络确定动态遗传算法的适应值函数。 3 遗传算法算子 遗传算法的3 个算子分别是选择、杂交和变异。选择体现“适者生存 的原理，通 过适应值选择优质个体而抛弃劣质个体。杂交能使个体之间的遗传物质进行交换从而产 生更好的个体。变异能恢复个体失去的或未开发的遗传物质，以防止个体在形成最优解 过程中过早收敛。下面分别介绍选择、杂交和变异3 个算子的主要研究内容。 ( 1 ) 选择算子 1 2 太原理工大学硕士研究生学位论文 选择算子从群体中按某一概率成对选择个体，某个体x i 被选择的概率p i 与其适应度 值成正比。最通常的实现方法是轮盘赌( r o u l e t t ew h e e l ) 模型。 选择策略的选取在遗传算法的操作中是很重要的一个环节，它的一个重要特点是它 几乎独立于算法的其它部分。由于选择策略对遗传搜索过程具有较大的影响，很多人早 就意识到它在遗传算法中的重要性。p o t t s 3 1 括了2 3 种选择方法，选择算子的收敛模型由 g o l d b e r 9 1 2 1 引入，随后由g o l d b e r g 和d e b 作了扩展 2 。 ( 2 ) 杂交算子 交叉算子( c r o s s o v e r ) ：交叉算子将被选中的两个个体的基因链按概率p c 进行交叉， 生成两个新的个体，交叉位置是随机的。其中p c 是一个系统参数。 杂交操作使不同个体间的基因互换。在不同成员中进行基因互换是为了能够在下一 代产生新的成员。p o t t s 3 提出了1 7 种杂交方法，另外，文献 1 0 研究了交配算子与其探 索子空间的关系，提出设计良好算子的指导性原则，并构造出一种启发式交配算子。 ( 3 ) 变异算子 变异操作是为了在运算过程中能改变某些成员的值，以避免失去一些有用的基因， 防止某些成员的值处于不变状态，是一种防止算法早熟的措施。p o t t s t m 结了3 种变异技 术：管理变异、变化的变异概率和单值运算。考虑将被优化函数的梯度或一阶差分引入 到十进制实数编码的遗传算法变异算子中，实现了定向变异。为克服传统变异算子不能 有效地保持同一基因位上等位基因的多样性，提出用二元变异算子代替传统的变异算 子。此外，对于不同问题可提出不同的自适应算子，如从染色体个体个性化和染色体编 码基因位个性化两个方面对标准变异算子进行改进 4 遗传算法的参数选择 遗传算法的参数选择包括群体规模、收敛判据、杂交概率和变异概率等。目前对遗 传算法的参数设置的合理选择还缺少相应的理论作为指导。由于参数选择关系到遗传算 法的精度、可靠性和计算时间等诸多因素，并且影响到结果的质量和系统性能，因此， 参数选择的研究受到重视。当采用自然数编码时，从理论上可以证明遗传算法的最优群 体规模的存在性，并给出相应的计算方法。种群规模影响到遗传算法的最终性能和效率。 种群规模过小将影响搜索范围，从而得不到最优解，种群规模过大则使搜索效率降低。 在试验中，种群规模的变化范围是从1 0 到1 6 0 ，增量1 0 。收敛判据：遗传算法是一种 反复迭代的搜索方法，它通过多次进化逐渐逼近最优解而不是恰好等于最优解，因此需 1 3 太原理工大学硕士研究生学位论文 要确定收敛判据。目前采用的遗传算法收敛判据有多种。如规定遗传迭代的代数所确定 的判据；或根据解的质量确定的判据，如连续几次得到的最优个体的适应值没有变化或 变化很小时，则认为遗传算法收敛了；或种群中最优个体的适应值与平均适应值之差与 平均适应值的百分数之比小于某一给定允许值等等。为评价遗传算法的收敛性能，定义 离线性能函数 荆= 掣 公式3 - 1 其中：二x 为第i 代的最大个体适应值，p ( ，) 是第t 代的离线性能值。在早期搜索 过程中，p ( ，) 将迅速增长；在后期搜索过程中，p o ) 的增长将平缓下来，并最终趋向于 收敛值。 由于杂交概率以和变异概率的设置关系到遗传算法的收敛性和群体中个体的多 样性，即探索和开发i 口- j 题，因此倍受重视。 传统的p 。和p 。的设置是静态人工设置。现在有人提出动态参数的设置方法，以减 少人工选择参数的困难和盲目性。见、以越大，则算法的探测能力越强，越容易探测 到新的超平面，而个体的平均适应值波动较大；相反，见、p 。越小，则算法的开发能 力越强，使得较优个体不易被破坏，而个体的平均适应值波动较小。 5 遗传算法的数学基础 1 9 7 5 年，h o l l a n d 在其专著自然界和人工系统的自适应中详细描述了模式理论， 引入模式概念，将遗传算法理解为在模式集合中的操作，从模式操作的角度观察分析遗 传算法的性能特点，并且指出，只要问题编码满足构造块假设，就容易用遗传算法求解， 模式理论是目前影响最广，研究最多的一种遗传算法理论。 模式定理的一般数学表达式为 所胁吣擎( - 一见掣二即c 日) ) 一2 其中所，r ) 为在t 代群体中存在模式h 的串的个数，7 【可表示在t 代群体中包含 模式h 的串的平均适应值，( 表示t 代群体中所有串的平均适应值，表示串的长度， 太原理工大学硕士研究生学位论文 见为交换概率，p m 为变异概率。 模式定理是遗传算法的理论基础，它说明高适应值、长度短、阶数低的模式在后代 中至少以指数增长包含该模式的串h 的数目。原因在于再生使高适应值的模式复制更多 的后代，而简单的交换操作不易破坏长度短、阶数低的模式，而变异概率很小，一般不 会影响这些重要模式。 用这种方式处理相似性，遗传算法减少了问题的复杂性，在某种意义上这些高适应 值、长度短、低阶的模式成了问题的一部分解( 又叫积木块b u i l d i n gb l o c k s ) 。遗传算 法是从父代最好的部分解中构造出越来越好的串，而不是去试验每一个可能的组合。长 度短的、低阶的、高适应值的模式( 积木块) 通过遗传操作再生、交换、变异，再再生、 再交换、再变异的逐渐进化，形成潜在的适应值较高的串，这就是积木假说。遗传算法 通过积木块的并置，寻找接近最优的特征。 借鉴二进制编码遗传算法中的概念，对十进制编码的模式定理进行研究，并给出了 以十进制整数编码遗传算法的基本定理，称之为十进制整数编码模式定理。模式定理中 模式适合度难以计算和分析，b e t h k e 4 1 将w a l s h 函数用于遗传算法模式操作的分析，他 建立了w a l s h 模式变换，用离散形式的w a l s h 函数有效的计算模式的平均强度，然后用 这一变换的系数区分问题的难易。b e t h k e l 4 1 的论述晦涩难懂，g o l d b e r g t 2 1 并发展了b e t h k e t 4 1 的结论。对于判断一个函数相对于遗传算法的难易程度，b e t h k e l 4 1 的结论并不适用，因 为大部分遗传算法应用中的目标函数都不容易表示成w a l s h 多项式，即使容易表示，计 算w a l s h 系数需要对搜索空间的每个点计算目标函数，这对大多数函数是不可能的，而 且，如果计算了目标函数的所有值，那么就知道了其最优解，而没必要再用遗传算法求 解了，分析就失去了意义。但是w a l s h 分析是一个强有力的理论工具。b e t h k e t 4 1 用w a l s h 系数和模式变换构造不同难易程度的问题测试遗传算法。这一方法的缺陷有- - ：一是度 量标准不精确，二是不能直观解释遗传算法的操作过程。 另一种新的理论，尝试从知识表示与算符相结合的角度考察遗传算法，首先引出一 致类的概念，给出判别一致类的直观办法；优类，然后推导出了遗传算法收敛的充分条 件，由此得到遗传算法难题的新定义，并解释了m d p 问题。 6 遗传算法的欺骗问题 在遗传算法过程中，那些阻碍高适应值的模式生成的问题叫做欺骗问题( d e c e p t i v e p r o b l e m ) 。算法在种群的进化过程中总是将具有高适应值、低阶、短定义矩等优良特征 1 5 太原理工大学硕士研究生学位论文 的基因片段进行重组以整合到一个模式上从而生成更为优秀的模式及其所对应的个体， 但在某一时刻具有这些相对优良基因片段的模式可能不包含最优模式所需具备的遗传 信息，这样的话，遗传算法就可能收敛到一个局部最优解。 欺骗函数的形式和类型可以有多种。一个可能产生欺骗问题的目标函数就是关于自 变量的非单调函数。即随着自变量参数的递增( 或递减) ，目标函数的值，即个体适应 值的变化不是单调增或减，遗传算法就可能收敛到一个次优解当中。另一种可能产生欺 骗问题的就是二进制编码时，编码空间的拓扑不连续性。编码空间上相邻的两个模式可 能在实数空间中却不连续，甚至相差很大。 欺骗问题是遗传算法研究中的一个热点。根据模式定理：低阶、短距的优模式在遗 传子代中将以指数级增长，最终，不同的最优模式相互组合，从而得到最优解。但是， 对于欺骗问题，复制算子受欺骗性质条件的“迷惑 ，使最优低阶模式在组合后形成非 最优高阶模式，从而使遗传算法偏离最优解。由于欺骗问题的存在，许多问题被归结为 遗传算法难题，使遗传算法的应用受到一定的局限。目前遗传算法的欺骗问题研究主要 集中在3 个方面：设计欺骗函数，例如g o l d b e r 9 1 2 1 计一个离散遗传算法的最小欺骗问题； 修改遗传算法以解决欺骗函数的影响，如文 1 7 提出一种基于可调变异算子的方法，即 在遗传搜索过程中通过改变变异算子的方向和概率来求解遗传算法欺骗问题，这种方法 能够在消除遗传算法中的欺骗性条件的同时保持群体的多样性，使遗传算法可以顺利地 收敛到全局最优解；理解欺骗函数对遗传算法的影响，文 1 8 就讨论了一类遗传算法求 解完全欺骗性问题的平均计算时间。 7 遗传算法的收敛性分析 一般收敛性分析是通过计算群钵的收敛牲进行的，设适应值函数p j 、，v x h ， j s 0 ，使忙一x i | 0 车辆总数k ： k - 5 0 每辆车的最大运载量w - w = 5 0 每个需求点的需求量c l i ：q 。 w 每辆车的运载量w 。：0 p k 0 完成一次配送的耗费c ： c ：y 。窆羔k 毛y 壮) t j i = l ，。，nj - - 1 ，1 3k - - 1 ，o - k 所有配送方案中耗费最小的： 2 6 公式5 - 1 太原理工大学硕士研究生学位论文 厂向) = r n i n ( c 胂