路径优化的算法.doc

广西工学院2008届毕业设计论文摘 要供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法Floyd算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。最后对基本遗传算法采用优先策略进行改进，再对同一个供货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。关键字:路径优化 遗传算法 Floyd算法 AbstractThe Path Optimization of Goods Supply Car is the effective way to reduce business costs and enhance economic efficiency.The problem of the Path Optimization of Goods Supply Car can be seen as Vehicle routing proble.This paper presents a solution to Vehicle routing proble with Single direction road by Researching the Way of Path Optimization of Goods Supply Car. First, This paper Establish the mathematics model of Vehicle routing proble and introduced the shortest path algorithm-Floyd algorithm, then taking the Single direction road into account at the same time. Seeking the shortest distance between any two points and landing path by this algorithm,then turn this problem in to TSP. Solving this problem can get the Optimize delivery routes which with Single direction road by GA,then take some district in the state City of LiuZhou road as an example start experiment.The Imitate the true result showed that this method can be better optimize results. Finally improving the basic GA with a priority strategy,then proceed to imitate the true experiment to the same Path diagram. The result expresses the improvement the heredity calculate way ratio the basic heredity calculate way can get quickly give satisfaction of excellent turn the result.Keyword: Path Optimization genetic algorithm Floyd algorithm23目 录1绪论11.1 课题研究的意义11.2国内外供货小车路径优化问题的研究现状21.3 本文的主要研究内容32供货小车行驶路径优化问题42.1无约束的供货小车路径优化问题42.2有单行道路约束的供货小车路径优化问题43 任意两送货点最短路径53.1用Floyd算法求解供货小车的任意两送货点最短距离53.2 用Floyd算法求解带单行道的任意两送货点间最短路径63.3 实例仿真结果74 供货小车路径的优化94.1建立TSP问题的数学模型94.1.1 概述94.1.2 数学模型104.2遗传算法的基本理论104.2.1遗传算法的特点114.2.2 标准遗传算法的遗传算法过程描述及步骤114.3 用遗传算法求解供货小车路径的优化问题124.3.1供货小车路径寻优问题的遗传算法实现124.4 仿真结果174.5用改进遗传算法求解供货小车路径的优化问题174.5.1遗传算法改进的思想174.5.2仿真结果分析185总 结19参考文献20致 谢221绪论1.1 课题研究的意义随着经济全球化的不断深入，许多跨国公司都已经或计划将制造、采购中心转移到中国，越来越多的国内企业也开始面向全球进行生产和经营，中国作为世界制造中心的地位日益凸显，这种大的国际环境更加刺激了我国物流业的高速发展。与此同时，国家经济建设的深入和商业活动的繁荣刺激了市场对物流服务需求的激增:一方面表现在社会物资流通总量高速增长，呼唤更优化的快递物流解决方案和专业的物流咨询服务;另一方面则是越来越国际化的商业运作要求物流服务水平跟上国际化标准，在速度、可靠性、安全性、个性化、战略远见等方面提出了更高要求。因此，通过降低物流成本，使得物流业的开展更加科学合理并进而通过开展服务创新，提升服务质量己经成了广大物流服务供应商的共识。本文着重从配送环节中的车辆行驶路径选择入手，分析如何优化调整小车送货线路问题，进而达到降低物流成本的目的。那么如何将车辆有效的使用并决定其最经济的行驶路线图，在最短的时间内把商品送到顾客的手中，提高顾客的满意度，将是配送中心作业的重点。显然配送服务的要求将越来越高，为了实现配送成本的降低，必须对配送过程进行合理规划。这就涉及到时间、财务、环境及服务质量四方面的因素，首先从时间上要考虑准时性、快速响应;财务上要考虑运输涉及的各种开支(员工薪酬、消耗等);环境上要尽可能减少不必要的行驶，避免交通拥挤、空气以及噪音污染;最后从服务质量上，要求满足顾客要求，达到顾客满意度最大化。这些都可以通过改进运输方式、线路规划等来改善。目前，物流配送活动中的配送运输路径确定问题，成为近二十多年来车辆路径问题的重点研究对象和应用领域。在配送运输中，由于配送用户多，城市交通路线又复杂，如何组成最佳路线，如何使配装和配送路线有效搭配等，是配送运输的特点，也是难度较大的工作。于是采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径，也是配送活动中非常重要的一项工作。路径优化是对车辆行驶路线的优化过程，也是对车辆进行调度的一个问题。由于运输任务的性质和特点不同、道路条件及车辆类型等各种约束标准不同，即使在相同收发货运点间完成同样任务时，所采用的行驶路线方案也可能不同。而车辆按不同运行路线完成同样的运输工作时，其利用效果是不一样的。因此，在满足货运任务要求的前提下，对各种不同的路径问题如何选择最经济的运行路线，是车辆路线安排的一项重要工作。可见VRP问题实质上就是路径优化问题，因此，规划好车辆路径的优化选择，尤为重要。所谓路径优化(即最经济的运行路线)，就是在保证货物需求的前提下，达到运输时间和运输费用最省的路线。1.2国内外供货小车路径优化问题的研究现状对于路径优化这类问题，国内外有不少学者进行了探讨和深入研究，并且提出了许多求解此类问题的有效算法，工具。东北大学信息科学与工程学院系统工程研究所的蒋忠中，汪定伟通过将B2C电子商务企业的实际物流配送网络描述为由配送中心和顾客两类节点构成的不完全无向图，建立了0-1整数规划的物流配送路径优化模型首先利用Floyd算法求得不完全无向图中各节点间的最短路径和最短路径长度，然后设计了捕食搜索算法对模型进行解通过仿真实例计算，取得了满意的结果1。华中科技大学计算机科学与技术学的黄红将其配送路径抽象为TSP问题，完成现实空间到问题空间的映射，使实际问题转化为平衡运输问题的数学模型，采用单纯形法和贪婪法配合使用，从而求出最优解或满意解2。重庆大学经济与工商管理学院的李志威，张旭梅针对蚂蚁算法在求解大规模物流配送问题中存在的不足，利用动态扫描方法在区域选择方面的实用性和蚂蚁算法在局部优化方面的优点，提出综合两种方法的混合算法，并获得了较满意的效果3。哈尔滨运通汽车销售服务有限公司的尹训波通过对改进的蚁群算法（可见度的改进，信息素浓度更新规则的改进）对物流配送路径的优化，得到了令人满意的结果4。长沙理工大学计算机与通信工程学院的柳林，朱建荣用遗传算法求解物流配送路径优化问题，有效地求解得问题的最优解或近似最优解，但遗传算法存在易陷入局部极小值和收敛速度慢等缺点，在总体上解的质量不是很高5。针对这些问题，北京交通大学交通运输学院的郎茂详、胡思继提出将爬山算法与遗传算法想结合，能有效克服遗传算法在局部搜索能力方面不足6；湖南科技大学的陈湘州，黎志明，刘祖润通过引进一种进化逆转算子，其局部寻优能力很强，收敛性明显好于标准遗传算法7；山东建筑工程学院管理工程学院，东南大学经管学院的亓霞，陈森发对带有约束度为时间窗的小车供货配送路径采用了一种改进小生境遗传算法来优化8，马炫，陈琼还用遗传算法对度约束单源多目的路径优化9。南开大学商学院,天津职业大学的张建勇 ,李军设计了具有同时配送和回收需求的车辆路径问题(VRPSDP),将正向物流和逆向物流同时加以考虑，与现实经济生活联系极为紧密10。沈阳建筑大学的韩中华，吴成东，杨丽英，邓湘宁针对基本遗传算法在计算大型网络的优化问题时表现出的求解效率低等缺点，在基本遗传算法中引入了子群体和迁移策略，提出了基于并行遗传算法的最优路径选择方法，使得在大规模路网中求解效率和求解质量的平衡问题得以解决11。长安大学的弓晋丽,程志敏基于Matlab进行了物流配送路径优化问题遗传算法的编码,利用Matlab强大的数值计算能力较好地解决了车辆行驶路径优化问题并进行了实例验证,对物流企业实现科学快捷的配送调度和路径的优化有实际意义12。自20世纪80年代以来，国际上流通业的发展出现了一种大的变化趋势整合(加egrale)即综合、集成、系统化和一体化的意思。早在1962年Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP模型13。1971年，Eilon等人提出将动态规划法用于固定车辆数的VRP，通过递归方法求解14。1974年，Wren，Gillett等人提出Sweep算法(扫描法)15。1981年，Christofides等人提出了k度中心树和相关算法，对固定车辆数m的m一TSP进行k度中心树松弛16。后来，M.L.Fishe对这种方法做了进一步改进，可求解有134个客户的VRP17。1991年，Gendreau等人将禁忌搜索方法应用于VRP18。它是针对VRP比较好的启发式算法，可以成功地应用于许多经典的VRP。其后E.Taillard等人通过按角度和路径重心对原问题的空间进行分割，结合禁忌搜索平时模拟退火对子问题求解，实现了对问题求解的并行化19。1.3 本文的主要研究内容随着物流业的发展，物流配送中的路径优化问题已不单单是求取路径最小化的问题，它要考虑的问题是越来越复杂，成为复杂性颇高的问题，传统的精确解法求解此类问题己落后。尤其本文要解决的是经典的、带单行道约束的配送路径优化相结合的问题，从难易程度上讲，以往的优化解法不仅耗时而且要求求得最优解，这是一种理想化的求解方法。因此本文的目的是建立以配送里程最短为目标的配送车辆路径优化模型，通过模型的构建，来解决实际当中可能遇到的问题，进而优化问题;在求解过程中，将遗传算法的逻辑思维应用到TC编程中，得到最合理的配送方案，避免了多目标的计算复杂性，同时达到了多目标的效果。本文的主要内容是:简单介绍了论文的研究背景、研究目的及意义，对论文涉及到的相关概念进行界定，为论文的后续工作做好铺垫;通过收集国内外学者专家关于路径优化（即VRP）的研究的相关文献资料并对其进行整理、分类，详细介绍了VRP国内外研究现状，尤其对以往解决VRP问题的方法的几个大致方向以及对带各种约束的VPR问题的解决方法的国内外研究现状分别展开了介绍;总结国内物流配送存在的问题及成因，说明了解决VRP的必要性及现实意义;紧接着针对前面涉及到的物流配送路径优化的一般方法作以介绍;在论文的核心部分，针对本文要解决的问题，构建以配送里程最短为目标的配送路径优化模型，其中充分考虑了城市单行道的情况，将单行道路径优化体现在模型当中，作为一个重要的约束条件来约束配送方案的选择，进而对配送路径优化进行制从中选择最佳路径;数学模型的求解作铺垫对模型求解过程中需要用的遗传算法的基本理论进行论述，为将遗传算法的逻辑思维应用到TC的编程当中，结合算例进行研究，验证该模型算法的合理性及有效性，说明其优越性;通过对全文内容的总结，提出了进一步研究供货小车行驶路径优化问题的方向。2供货小车行驶路径优化问题2.1无约束的供货小车路径优化问题物流配送车辆调度问题即路径优化问题最早是由DanZitg和Ramser于1599年首次提出的，国外将其归结为或称之为VehicleRoutingProblem(简称VRP问题)。该问题一般定义为:对一系列给定的顾客(取货点或送货点)确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心，并在满足一定的约束条件下(如车辆容量限制、行驶里程限制、时间限制、顾客需求量、交发货时间等)，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。VRP问题实质上就是路径优化问题，因此，规划好车辆路径的优化选择，尤为重要。所谓路径优化(即最经济的运行路线)，就是在保证货物需求的前提下，达到运输时间和运输费用(通常为吨公里)最省的路线。路径优化问题是对车辆行驶路线的优化过程，也是对车辆进行调度的一个问题。由于运输任务的性质和特点不同、道路条件及车辆类型等各种约束标准不同，即使在相同收发货运点间完成同样任务时，所采用的行驶路线方案也可能不同。而车辆按不同运行路线完成同样的运输工作时，其利用效果是不一样的。因此，在满足货运任务要求的前提下，对各种不同的路径问题如何选择最经济的运行路线，是车辆路线安排的一项重要工作。选取恰当的配送行驶路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本，因此设计合理、有效的车辆路线方案，尽量减少车辆数量和配送里程数就成为非常实际的问题。2.2有单行道路约束的供货小车路径优化问题随着城市建设的发展，市区道路出现交通秩序较乱、高峰期拥堵的情况，为了解决这一问题，越来越多城市在市区的一些地方采用单行交通组织方式，这样才能对城区内车流进行重新组织，缓解交通拥堵程度。通过前人的文献来看，在研究供货小车行驶路径优化问题的时候没有把这个问题考虑进去，把城市单行道这个约束度加进去是很有必要的，这样才能满足现在的大多数城市的情况。单行道直观来理解就是线路的走向是单方向的，比如在某条特定的线路上车辆(行人)只能从一点走向另一点，而无法返回(特定规则限制)，反过来亦如此带有单行道路约束的供货小车路径优化问题和上面提到的无约束的供货小车路径优化问题差别不大,小车在送货过程中遇到的单行道都是正向时其实与没有单行道的路径规划是一样的,只有当在小车供货过程中遇到逆向单行道时,这时小车必须改道去寻另外一条路径到达送货点，为了能得到一条比较优的路径，要重新规划路径网络图。3 任意两送货点最短路径3.1用Floyd算法求解供货小车的任意两送货点最短距离供货小车行驶路径网可以看做是带权的图，图3.1就是一个加权图G=（V，E,W)来表示。其中V为顶点集，V=vii=1，2，n；E为边集，W为权集， 。本文不仅要把交叉路口看成图G的顶点，还要把各个送货点也看成图G中的顶点，边是指供货小车行驶的路径，权是指任意两顶点间路径的长度。而供货小车行驶路径网其实就是一个无向图，它要求每一个顶点经过一遍且仅经过一遍。图3.1就是一个无向图G=（V，E,W)。图3.1 无向图如图3.1无向图所示的看成是一个供货小车行驶路径示意图。其中顶点1是发货点，顶点2,4,6看成是送货点,3，5看成是交叉路口。本文用Floyd算法求解供货点间的最短路径。Floyd算法其实就是全部顶点间最短路径算法，是1962年由福劳德(Floyd)提出的算法.它的主要思想是从代表任意两个顶点vi到vj的距离的带权邻接矩阵开始，每次插入一个顶点vk，然后将vi到vj间的已知最短路径与插入顶点vk作为中间顶点(一条路径中除始点和终点外的其他顶点)时可能产生的vi到vj路径距离比较，取较小值以得到新的距离矩阵.如此循环迭代下去，依次构造出n个矩阵D(1)，D(2)，D(n)，当所有的顶点均作为任意两个顶点vi到vj中间顶点时得到的最后的带权邻接矩阵D(n)就反映了所有顶点对之间的最短距离信息，成为图G的最短距离矩阵。下面描述该方法的构造矩阵的原理。对一个有n个顶点的图G，将顶点用n个整数(从1到n)进行编号。把G的带权邻接矩阵W作为距离矩阵的初值，即D(0)=(dij(0)nn=W。第一步:构造D(1)=(dij(1)nn，其中dij(1)=mindij(0)，dil(0)，dik(0)是从vi到vj的只允许以v1作为中间路径中的最短长度。第二步:构造D(2)=(dij(2)nn，其中从vi到vj的只允许以vi，v2作为中间点的路径中最短路的长度。第n步:构造D(N)=dij(n-1)，din(n-1).dnj(n-1) 从vi到vj的只允许以v1，v2，vn作为中间点的所有路径中最短路的长度，即是从从vi到vj中间可插入任何顶点的路径中最短路的长度，因此即是距离矩阵。本文只用考虑送各个货点之间的最短路径，通过Floyd算法求出各个顶点之间的最短距离并得到最短路径走法。3.2 用Floyd算法求解带单行道的任意两送货点间最短路径带单行道约束的路径优化问题实际上可以看做是带权混合图的最短距离问题。混合图中既包括有向边，也包括无向边。图3.2就是一个带权混合图，它与图3.1区别在于其中的几条边是有向边。图3.2 混合图上图3.2混合图所示的看成是一个单行线交通示意图。已知一个各边权值均大于0的带权有向图，对每一对顶点，要求求出之间的最短路径和最短路径长度。其实用Floyd算法求解有单行道约束的最短路径问题与无约束最短路径问题是差不多的，不同的在于要考虑有向边的权值问题。本文的思想是把那些无向边看作是有往返两重边的有向边，两无向边的顶点顶为，无向边可以看成是在这两个送货点之间存在权值相同的两条有向边和。有向边正向时权值不变，有向边反向时权值赋为所有两点间距离的总和。其他的求解步骤和上面的不带约束条件的供货小车的最优行驶路径的步骤是一样的。对图3.2进行分析：顶点1是发货点，顶点2，4，6看成是送货点，3，5都看成是交叉路口。这时就要通过Floyd算法求解出任意两点间最短距离。看从1到2的线路，先随机走一条为1-2，得到一条路经，再在1-2之间插入3，就得一条新的路径1-3-2，这时候1-3是反向单行道，它的值是所有顶点间距离的总和，可以看出比较优的走法是前面一种，再拿第一种走法和另外一种走法1-6-5-3-2相比，再通过比较两条路径的长度，再选择那条比较短的路线。3.3 实例仿真结果本文采集了柳州市市中心某区域地图如图3.3所示为例进行送货，采用C语言程序对供货小车行驶路径进行仿真，得到优化的供货小车行驶路径。这个地图中包含有一个发货点,十个送货点，十四个交叉路口，把这些点都看成是混合图G=（V，E,W)的顶点，其中1是发货点，2到11这十个点是送货点，其他的为交叉路口，供货小车行驶的路径满足的要求是：要求每个送货点都有一辆小车送货且只有一辆且只送一次，使得每条行驶路线尽可能短即尽可能优。求解方案都是按上面提到的思想来解决供货小车最优行驶路径的问题。图3.3 柳州市某区域地图对这个图进行仿真得到以下结果 1 2 3 4 5 6 7 8 9 10 11 1 0 301 540 270 823 520 655 365 894 235 900 2 301 0 807 571 1124 821 956 566 1095 436 1101 3 540 807 0 398 951 648 783 905 1434 775 1079 4 270 571 398 0 553 250 385 635 1164 505 681 5 883 866 543 803 0 278 413 778 1030 1018 446 6 605 806 1056 702 637 0 267 500 1029 740 563 7 582 783 941 679 522 267 0 477 1006 717 448 8 365 566 860 462 895 592 727 0 529 500 939 9 894 1095 1389 991 1424 1121 1256 529 0 863 1128 10 235 436 775 505 1058 755 890 500 863 0 665 11 721 420 759 991 1544 1241 1376 939 1128 665 0 以上是通过Floyd算法得到的把各个供货点提取出来的矩阵，这个矩阵给出了任意两个送货点之间的最短路径值，对这个路径图仿真同时还得出任意两点(包括交叉路口)最优路径的走法。通过上面的矩阵可以看出，当这条线路中所有点边全部是无向边时, =,当中包含有有向边时, ,例如，这是因为所走的最优路径是1-24-2，所走的最优路径是2-24-2，这里面不包含有向边，即单行道，所以所走的路径都是一样；，这就是因为所走的最优路径是7-18-17-8-23-9，而的所走的路径是9-23- 8-17-15-19-20-7，这是因为所走的路线有单行道，两点间来回所走路径不是同一条，所以路径距离也是不相等的。4 供货小车路径的优化4.1建立TSP问题的数学模型4.1.1 概述由于现代配送具有多频次、小批量、多品种、高效率的特点，配送要准确做到7R(right product，right quality，right tillle，right place，right codiniton， irght customer ，right cost)，如何合理、有效的对配送路线进行优化，就成为非常现实的问题。进行配送路线优化时，必须有明确的目标，遵循基本的原则。配送路线方案目标的选择可以从以下几个方面来考虑:(1) 配送效益最高或配送成本最低。效益是企业追求的主要目标，可以简化为用利润来表示，或以利润最大化作为目标;成本对企业效益有直接的影响，选择成本最低化作为目标值与前者有着直接的联系。当有关数据容易得到和容易计算时，就可以用利润最大化或成本最低作为目标值。(2) 配送里程最短。如果配送成本与配送里程相关性较强，而和其他因素相关性较弱时，配送里程最短的实质就是配送成本最低。则可考虑用配送里程最短作为目标值，这样就可以大大简化线路选择和车辆调度方法。(3) 配送服务水准最优。如准时配送要求成为第一位时，或需要牺牲成本来确保服务水准时，则应该在成本最大容忍的限度下，以服务水准为首选目标。这种成本的损失可能从其它方面弥补回来，如优质服务可以采取较高的价格策略。(4) 配送劳动的消耗最小。即以物化劳动和活劳动消耗最小为目标，在许多情况下，如劳动力紧张、燃料紧张、车辆及设备较为紧张的情况下，限制了配送作业的选择范围，就可以考虑以配送所需的劳动力、车辆或其它有关资源作为目标值。TSP一般描述为：旅行商从驻地出发经所要去的城市经过且只经过一次后返回原地应如何安排其旅行线路才能使总的旅行距离(或时间费用等)最少,对于现实问题由于限制条件的增加TSP 可衍生出许许多多相关的问题,本文最主要是的优化目的是上面提到的第(2)个,即配送里程最短。TSP 模型数学描述为有一个配送中心（编号为0）现在有n个点需要配送，以1，n表示，求满足货运需求的费用最小的车辆行驶线路。其主要假设还有：1） 供货小车以配送中心为起点和终点；2） 车辆行驶相同的路段，其成本相同；3） 每一节点只允许车配送一次；4） 弧上没有容量限制。4.1.2 数学模型根据上述目标和假设，一般TSP 的数学模型如下min (4.1) (4.2) (4.3) (4.4) (4.5)说明1）决策变量：2）参数变量：点i到点j的行驶距离；N：配送点数；3）方程说明式（4.1）为目标函数；为极小化车辆行驶距离式（4.2）（4.4）为约束方程式(4.2) 表示对于任何一个送货点除配送中心只有一辆车到达送货点式(4.3)为消去支路约束即消去不构成完整线路的解式(4.4)为变量的取值约束4.2遗传算法的基本理论遗传算法是一种从生物进化的规律中得到灵感和启迪的自适应全局随机搜索方法。由于遗传算法的整体搜索策略和优化计算时不依赖于梯度信息的特点，所以它的应用范围非常广泛，尤其适合于处理传统搜索方法难以解决的高度复杂的非线性问题。有专家断言，遗传算法是用来解决NP难题的趋势。Berthold, Malmborg,Ochi和Luiz都曾利用遗传算法对物流配送的车辆路径问题进行求解，但仍处于尝试阶段，还有待于进一步的研究。4.2.1遗传算法的特点同传统的算法相比较，遗传算法具有以下特点:遗传算法对问题参数的代码集起作用，而不是对参数本身起作用。遗传算法处理的对象是染色体，因而要求把所要优化问题的基本参数转化成定长的优先符号的染色体。遗传算法是从初始群体开始搜索的，而不是从单点开始搜索的。许多传统优化方法都是从搜索空间的单点出发，通过某些转换规则确定下一点。这种点到点的搜索方法在多峰值优化问题中，首先找到的可能不是最优峰值;而遗传算法是以点集开始的寻优过程，初始群体是随机地在搜索空间中选取的，这样在搜索过程中达到最优峰值的概率远大于点到点方法的概率。遗传算法在搜索过程中只使用适应度函数信息，而不用导数及其他辅助信息。对于不同类型的优化问题，传统方法需要不同形式的辅助信息，没有一种优化方法能适应各类问题的要求。遗传算法在优化过程中，放弃使用这些辅助信息，具有广泛适应性。遗传算法使用概率转换规则而不用确定性规则。遗传算法使用概率转换来调整其搜索方向，各代群体间没有统一的联系规律。但使用概率转换规则并不意味着这种方法属于随机算法范畴，它只是使用随机转换作为工具来调整搜索过程趋向于目标函数不断改进的区域。与传统方法相比，遗传算法的优越性主要表现在:首先，在遗传算子的作用下，遗传算法具有很强的搜索能力，能以很大概率找到问题的全局最优解:其次，由于它固有的并行性，能有效地处理大规模的优化问题。4.2.2 标准遗传算法的遗传算法过程描述及步骤遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区城，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体，求得问题的最优解。遗传算法步骤如下:(1) 构造满足约束条件的染色体。由于遗传算法不能直接处理空间的解，所以必须通过编码将解表示成适当的染色体。实际问题的染色体有多种编码方式，染色休编码方式的选取应尽可能地符合问题约束，否则将影响计算效率。(2) 随机产生初始群体。初始群体是搜索开始时的一组染色体，其数量应适当选择。(3) 计算每个染色体的适应度.适应度是反映染色体优劣的唯一指标，遗传算法就是要寻得适应度最大的染色体。(4) 使用选择、交叉和变异算子产生子群体。这三个算子是遗传算法的基本算子，其中复制体现了优胜劣汰的自然规律，交叉体现了有性繁殖的思想，变异体现了进化过程中的基因突变。(5 )重复步骤(3),(4)直到满足终止条件为止。遗传算法的运算流程可以如下表示; 编码随机产生初始种群计算染色体的适应度轮盘赌法复制子代群体交叉算子变异算子满足终止条件Y算法结束N图4.1 遗传算法运算流程4.3 用遗传算法求解供货小车路径的优化问题4.3.1供货小车路径寻优问题的遗传算法实现(1)编码个体或当前近似解被编码为由字母组成的串，即染色体，使基因(染色体值)能在域决策变量上被唯一描述。在遗传算法中，染色体的表现形式通过编码机制来实现的。算法的编码机制直接影响着算法的整体性能，并且也决定了种群初始化和各种遗传算子的设计等各种过程，因此说，编码机制是遗传算法的关键步骤。由于遗传算法应用的广泛性,迄今为止人们已经提出了许多种不同的编码方法.总的来说,这些编码方法可以分为三大类:二进制编码方法、浮点数编码方法、符号编码方法。人们常用的编码方案有二进制编码、格雷码编码、浮点数编码、符号编码方法、多参数级联编码方法、多参数交叉编码方法、实数编码、Gary编码、自然数编码等。本文采用的Grefenstette等提出的一种新的巡回路线编码方法,该方法能够使得任意的基因型个体都能够对应于一条具有实际意义的巡回路线。下面介绍这种新的编码方法。对于一个供货小车路径优化问题的送货点列表W，假定对每个送货点的一个送货顺序为T：T=（t1 t2 t3 tn ）规定每送完一个送货点，就从送货点列表W中将该送货点去掉，则用第个所送的送货点在所有未访问送货点列表W-t1 t2 t3 ti 中的对应位置序号就可表示具体访问哪个送货点，如此这样知道处理W中所有的送货点。将全部顺序在一起所得到的一个列表： 就可表示一条巡回路线，它即为遗传算法中一个个体的基因型。假如有这样一个简单的参考点:T=(1 2 3 4 5 6 7 8 9 10 11 )一个送货路线如下:1-3-4-8-11-7-10-5-2-6-9则被表示为参考表如下:=(1 2 2 5 7 4 5 2 1 1 1 )（2）初始群体生成种群的初始化操作是指随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。一般情况下，种群的初始化操作都是随机的，因为通过随机的方式生成初始种群，能够有效地避免种群的单调性，防止种群陷入局部最优。当然，为了避免初始的种群中出现很多不合格的解，也可以采用简单的局部搜索算法获取初始解，不过这会消耗一定的问题求解时间。（3）确定适应值函数在遗传算法中使用适应度(Fitness)这个概念来度量群体中各个个体在优化计算中能达到或接近于或自助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大;而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数(FitnessFunction)。适应度函数也称为评价函数，是根据目标函数确定的用于区分群体中个体好坏的标准，算法演化过程的驱动力，也是进行自然选择的唯一依据。适应度函数通常要求是非负的，任何情况下都希望其值越大越好。而目标函数可能有正有负，既有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之问进行变换。目标函数是提供一测量手段，测量个体在问题域的完成情况。在一个最小化问题中，最适合的个体对应最小的目标必数值。未经加工的函数值通常只用在遗传算法的中期来判断一个个体的相对性能。另一函数-适应度函数通常用于转换目标许多情况下，适应度函数值对应大量子代-预计在下一代中能存在的个体。通常使用如下转换进行适应度概率分配。个体的适应度-每一个个体的F()通过个体的未加工的适应度相对整个种群的适应度被计算出来，即式中，Nind是是种群大小，是个体i的表现值，与此同时适应度分配确保每个个体均存按其相对适应度再生的机会，但它不能处理负的目标函数值。本文的适应度函数是由下面的公式得到的:=式中就是适应度函数,z是供货小车行驶路径最长的路径长度, 就是第条供货小车行驶路线的长度,则适应值越大方案越优。（4）选择选择 (Selection)又称复制(Reproduction)，它模拟了生物进化过程中自然选择的规律，按照某种特定的方法从群体中选取N个个体放入交配池。选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。选择操作的策略与编码方式无关。具体过程是:使用选择算子(又称为复制算子)来对群体中的个体进行优胜劣汰操作。根据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体中的概率较大:适应度较低的个体被遗传到下一代群体中的概率较小。这样就可以使得群体中个体的适应度值不断接近最优解。选择操作能够提高群体的平均适应度函数值，但是并没有产生新的个体，群体中最好个体的适应度函数值也不会有所改进。常见的选择算子有以下几种: 轮盘赌法、Boltzmann选择、最优保存策略、基于排序的选择，确定式选择，比例选择、无回放随机选择、无回放余数随机选择、随机联赛选择等。本文使用最佳保留的轮盘赌复制法选择得到的个体进入下一步交叉和变异。这种方法的原理是:每个个体进入下一代的概率就等于它的适应度值与整个种群中个体适应度值和的比例，适应度值越高，被选中的可能性就越大，进入下一代的概率就越大。每个个体就像圆盘中的一个扇形部分，扇面的角度和个体的适应度值成正比，随机拨动圆盘，当圆盘停止转动时指针所在扇面对应的个体被选中，轮盘赌式的选择方法由此得名。轮盘赌是一种常用的选择方法，表1表示4个染色体的适应度，选择概率和累计概率。为了选择交配给体，需要进行多轮选择。每一轮产生一个0,1随机数，将该随机数作为选择指针来确定被选择个体。如第一轮随机数为0.83则第四个染色体被选中。表 1轮盘赌选择法的选择概率计算个体1234适应度1111选择概率25%25%25%25%累计概率0.250.50.751（5）交叉在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生出新的个体或物种。模仿这个环节，遗传算法中使用交叉算子来产生新的个体。这是遗传算法区别于其他进化运算的重要特征，它在遗传算法中起着关键作用。交叉 (crossover)又称重组(Recombination)，是按较大的概率从交配池中选择两个个体，交换两个个体的某个或某些位基因，从而形成两个新的个体。交叉算子的设计包括如何确定交叉点位置和如何进行部分基因交换两个方面的内容。交叉产生的子代继承了父代的基本特征。遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。目前常用的配对算法策略是随机配对，即将群体中的M个个体以随机的方式组成M/2对配对个体组。交叉操作是在这些配对个体组中的两个个体之间进行的。交叉算子的作用是组合出新的个体，在串空间进行有效搜索，同时须降低对有效模式的破坏概率。采用不同编码方式时所采用的交叉算子设计不一样，其中自然数编码所采用的交叉算子有如下几种:单点交叉、双点交叉与多点交叉、均匀交叉、算术交叉。本文选用的是单点交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单点交叉算子的具体执行过程如下：a、 对群体中的个体进行两两随机配对。b、 对每一对相互配对的个体，随机设置某一个基因座之后的位置为交叉点。c、 对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。举例说明:随机在父代个体中选择一个交配区域,如两父代个体及交配区域选定为:A=1315344321,B=2211153311,将B的交配区域加到A的前面,A的交配区域加到B的前面,得A=1315343311,B=2211154321。（6）变异在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，这样会导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。遗传算法模仿生物遗传和进化过程中的变异环节。遗传算法中的变异运算，是指以较小的概率将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。最简单的变异算子是基本位变异算子。为适应各种不同应用问题的求解需要，人们也开发了其他一些变异算子。下面介绍其中较常用的几种变异操作方法，他们适合于二进制编码的个体和浮点数编码的个体。他们是基本位变异、均匀变异、边界变异、非均匀变异、高斯变异等。本文采用的是基本位变异算子，对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原由基因值为1，则变异操作将其变为0。基本位变异运算的示意如下所示：A：1 0 1 0 0 1 0 1 0A：1 0 1 0 0 1 0 1 0 适应度函数 =式中就是适应度函数,z是供货小车行驶路径最长的路径长度,就是第条供货小车行驶路线的长度。选择算子采用最佳保留的轮盘赌复制法 交叉算子采用单点交叉操作算子 变异算子采用基本位变异算子 运行参数群体规模取500,交叉概率和变异概率分别取0.95和0.05,对于上述问题遗传200代。4.4 仿真结果 由前面所介绍的个体编码方法和各种遗传算子可以构成不同的求解旅行商问题的遗传算法，本文利用基本遗传算法对图3.3所示的柳州市某区域地图的含有25个顶点（交叉路口加送货点）路径图进行求解。顶点1是发货点，其中顶点2，3，4，5，6，7，8，9，10，11是送货点，其他的顶点都是交叉路口。利用Floyd算法求得任意两送货点最短距离及到达路径，从而将问题转化为TSP问题，再利用遗传算法进行求解，通过遗传算法200代的选择,交叉和变异操作,仿真得到的最优的路径如下：1-24-10-25-23-9- 23-8-17-15-4-15-19-6-19-20-7-20-21-22-5-22-14-13-3-12-11-12-24-1,总长度是5080。图4.3 仿真得到行驶路径图上面的绿线就是仿真得到的供货小车最优的行驶路线。以上仿真结果显示，本文提出的把供货点看成是图的顶点，得到了有效的结果，并且证实了遗传算法在解决有单行道的供货小车行驶路径优化问题上能得到比较让人满意的结果。4.5用改进遗传算法求解供货小车路径的优化问题4.5.1遗传算法改进的思想本文基本遗传算法的改进最主要是对遗传算子的改进,采用的方法是优先策略。所谓有限策略就是把目前种群中一定数量的优秀个体直接放入下一代种群中,以防止优秀个体因复制,交叉和变异操作中偶然的因素而被破坏掉，这样达到对遗传算法的改进。本文的思路是:先是在第一代染色体中找出最优的那50个染色体用A0表示,然后保留A0不进行交叉变异,再对其余的染色体进行遗传操作,然后再在第二代染色体中找出最差的50个染色体用B1表示,然后用A0替代B1,然后再从第二代所有的染色体中找出最优的50个染色体用A1表示,然后保留A1不进行遗传操作,对其余的染色体进行遗传操作,然后再从第三代染色体中找出最差的50个染色体B2然后用A1代替,再对第三代染色体进行以上的操作，最后得到令人满意的结果。4.5.2仿真结果分析首先用基本遗传算法对图3.3所示的柳州市某区域地图的含有25个顶点（交叉路口加送货点）路径图进行求解。与上面不同的遗传算法的参数有所改变，这次遗传代数取10，其他的不变，然后用遗传算法进行仿真得到的最优的路径的value值为5211，路径走法如下：1-24-2-12-11-12-3-13-16-4-15-19-6-19-20-7-20-21-22-5-22-21-9-23-8- 17-24-