基于遗传算法的多辆洒水车最优路径求解（其中包含MATLAB的一些关键语句说明和FloydDijkstraEuler算法的综精品资料.doc

广西工学院毕业设计（论文）说明书摘要车辆路径问题可以分为以点为服务和以边为服务两种，洒水车问题是以边为服务的一个子问题。作为容量限制弦路径车辆行驶问题(CARP)的一种实际应用，洒水车路线规划涉及带有一定容量限制的总行程最小，以及多辆洒水车工作的合理分配问题，属于复杂的N-P难车辆路径优化问题。因此，在容量限制下实现作业车的总行驶路径最小，节约成本，提高效率，成为我们研究的中心环节。本文采用了遗传算法，对多辆洒水车线路优化问题进行了容量均衡性方面的研究。首先在矩阵计算过程中采用了Floyd和Dijkstra算法求解了作业区域上任意两点之间的距离，以及指定两点之间的具体路径，为车辆的部分路段行驶获得了指向。接着对洒水车作业图的奇数度点进行随机匹配，从而把洒水车的作业图补成了每个顶点都是偶数，这样就可以获得一条Euler回路，即对应一个花费数值。然后通过遗传算法，初始化，编码，解码，适应度函数的计算以及选择，交叉，变异等一系列操作，最终获得一条花费最小的Euler回路。最后对这条回路进行分割，从而实现多辆车之间的作业分配。本文通过引用柳州市区的一部分区域地图进行实验，获得了比较理想的结果，并服合一定的现实意义。关键词:路线优化 遗传算法 匹配 Euler算法AbstractVehicle routing problem can be divided into the service for points and the service for sides， while sprinkler service is a subset of the side problem. As a practical application of CARP(Capacitated ARC Routing Problem) ，the sprinkler route planning demanks the total trip Minimum with a certain capacity and shares alike the work .So it is the complexity of VRP(Vehicle routing problem).In order to achieve the total trip minimum， to increase the least cost and increase the efficiency that becomes the central link of our research.In this paper， we use the genetic algorithm to research how to finishes the sprinklers work equal. First of all， we apply the the Floyd and Dijkstra to achieve the distance between any two points and the specific path between two cettain points， which provide a method for the car to some setions road.Then the point of odd-degree random match in the routing graph，in this way， we can change the degree of every vertex into even.This can be an Euler circuit， which corresponds to a cost value.Whats more， through the genetic algorithm， initialization， encoding， decoding， the calculation of fitness function， as well as selection， crossover， mutation， such as a series of operations, eventually we get the answer.In the paper,we use Part of the liuzhou mapto experiment,and obtain a more satisfactory results,in the same time show the algorithm has practical significance. Key words: path optimization ， Genetic Algorithm，matching; Euler Algorithm目 录Abstract21绪论41.1 研究的目的和意义41.2 车辆路径问题的国内外研究现状41.3 主要研究内容52洒水车路线优化问题72.1 路径优化问题72.2图论的相关知识和算法72.2.1Floyd与warshall算法92.2.2Dijkstra算法92.2.3Euler算法102.2.4奇数度路口的匹配112.2.5遗传算法113单辆洒水车的路线优化143.1问题及模型描述143.2 路径优化设计思路143.3 实例分析154多辆洒水车路线优化184.1多辆洒水车路线优化的描述184.2 多辆洒水车路线优化的设计思想194.3 实例的设计与实现204.3.1洒水车路线优化问题的编码214.3.2奇数度点的初始化214.3.3解码及洒水车行进路线的获取224.3.4计算目标函数254.3.5选择算子264.3.6交叉算子274.3.7变异算子284.3.8参数设计294.3.9多辆洒水车行进路线的分配29结束语32参考文献33致谢341绪论1.1 研究的目的和意义在经济高速发达时代，人们绞尽脑汁地节约投入的成本，人们费尽心血地研制出更加高效的生产工具，人们不断完善人力资源的调度理论，其目的就是为了获得高效的工作效率，合理地人力资源配置。人们生活方式的自动化水平是一个反映时代的发展的标志，随着人们生活水平的提高，人们也更加地关注着他们所生存和发展的环境，人们所生活的环境，空气的清净度对人们的健康有着重要的意义。为了能够更地完成城市的除尘工作，实现最低的成本花费，高效的工作效率，合理的人力资源配置这一目标。如何合理地对洒水车的作业线路进行优化将成为本课题的核心。由于洒水车的作业是一个N-P难问题。如何合理地规划洒水车的作业路线，从而减少不必要的行驶路程，不但可以更好地提高工作效率，而且可以可以有效地节约燃油的成本，对本课题的研究具有重要的现实意义。同时当我们为了提高洒水车对城市除尘工作的效率，而使用了多辆洒水车同时工作时，如何地分配好各辆车之间的作业路线，在保证高效的同时做到燃油的花费最小，将比单辆洒水车的除尘应用更加具有现实意义。1.2 车辆路径问题的国内外研究现状洒水车问题是以边为服务的问题。类似的还有冬季除冰车，城市垃圾回收，以及最古老的中国邮递员问题都属于ARP问题，由于它们都存在有一个共同的特点，即容量限制的问题，因此洒水车的问题又称为CARP问题的一个扩展问题。而CARP问题属于N-P难问题。对于小数量的(20条边或弧以内) 还可以用精确算法来来解决(分为整数规则和分枝定界)，但是实际问题往往规模较大，如果仍采用精确算法，在运行时间和计算的复杂度将出现瓶颈。到目前为至，虽然国外对边服务的论文仍比较少，但较于去年的研究情况。关于洒水车方面的论文开始有一些了，如邓欣等人在2007年，针对单车场洒水车线路优化问题，将路径优化问题转化CARP的扩展，提出了改进遗传算法OX交叉和局部搜索(local search)的方法，通过实际生活的例子验证了算法的可靠性和适用性，从而保证算法在解决一定规模的CARP具有一定的实用价值1。李小花等人在2008年针对多车场洒水车路线优化的问题，将传统遗传算法的种群结构进行改进，提出了车辆的时间约束来保证各辆车工作时间的均衡性，即使效果并不理想，但仍有一定的参考价值2。刘建辉等人在2008年，针对多车场路线优化的问题，提出了一种双层遗传算法，处理了车场与路径的分配，以及每条路径的服务弧之间的优化问题，对人力资源的优化和减少车辆总行程，取得了很好的效果3。朱征宇等到人在2008年针对复杂CARP问题中的多车型，多路型等因素，以传统的遗传算法为基础，提出了一种高性能遗传算法(HEGA)，使得染色体代表的含意截然不同，同时加入了重优化措施的收入，防止了随着迭代次数的不断增加，优化曲线逐渐平缓，算法将会收敛，而此时可能并没有达到全局最优，这些算法和设计思想均对现实问题的考虑提供了很有价值的参考4。但正刚等人在2006年针对CARP的求解问题，研究了CARP与CVRP的转化，提出了小环路方法(实质为禁忌)来求解CARP，验证了算法的准确性和效率，为实际应用奠定了基础5。 同时针对车辆线路优化的均衡性问题，认识到了LU算法在时间对车辆的均衡性的约束不够，从而提出了一种新的算法，主要的思想为牺牲了车辆路径的饱和来实现车辆路径的均衡性6。贾立双等人在2008年针对，单车场车辆调度问题，提出了一种综合运用最邻近算法和遗传算法的相关原理组合实现了单车场多车型的调度7。李松等人在2007年针对大规模车辆路径中存在的缺陷，提出了Sweep分区技术和分区的禁忌搜索算法与相邻区域的优化技术相结合，有效解决了大规模车辆路径的优化问题8。付彤等人在2006年针对一般网络上单车型车辆配送问题，借鉴Floyd算法与节约路径法，构造出一种在所用车辆数最少的条件下，使总配送里程最短9。张涛等人在2002年针对车辆数目不确定的车辆路径优化问题，提出了遗传算法GA和禁忌搜索算法TSA相结合，主要以GA为主，把TSA用在GA的变异操作中，从而获得了最小化距离和最小化车辆的双目标优化10。陈文兰在2007年讨论了VRP问题的分类，以及介绍了近年来的相关算法的主要成果11.。相对于(容量限制弧的边路径问题)CARP，国外的应用相对国内而言，就多一点。Maria Candida Mourao在2004年针对垃圾回收问题的求解，提出了一种新颖的HM启发式算法12。Anita Amberg等人针对M-CARP问题提出了一种禁忌搜索算法，不过对于M-CARP的问题的研究还处于初步探索阶段，能查到的相关文献不多13。Dino Ahr在06年针对中国邮递员问题利用了一种禁忌搜索算法，但是中国邮递员的最大最小解属于N-P难问题，因此，在论文中主要依赖启发式算法产生近似解。同时，在许多情况下人们所能得到的解也是近似或更优的解14。Jose Brandao在2006年针对CARP问题提出一种基于禁忌搜索的启发式算法，在应用到标准例子的各种情况下，得到结果，说明了算法处理的过程可以在合理的计算时间内得到较高的准确性15。 洒水车的路径优化的问题，要考虑的问题还是有很多的。就单一的目标:要求路径最短而言。当道路的情况多种时，如单行道(要求只能从某个方向行驶)，双边道路(中间有绿化带)，道路中有上下坡的(要求下坡时洒水)，还有在某个十字路口只能左转或右转的限制是时，都需要对算法作出一定的修改。当在城市的道路中加入了一定数量的加水点(水桩)时，就要对洒水车加水点选择的优先性进行考虑。当为了提高洒水车除尘的效率，引入多车辆同时工作时，就要对洒水车间的路径分配的均衡性问题进行考虑。还有当有多个车场时，道路与车场的分配问题，对道路除尘时，对车型容量的选择(多车型)等等都会限制算法的适用性1.3 主要研究内容在原来单辆洒水车的基础上，实现多辆洒水车的线路优化问题。由于原来做的是单辆洒水车在无限容量下的情况，这样一来，只要形成一条最短回路就可以了。现在要做的是，把这种无限容量下的路线优化变得现实一点，即把无限容量的的情况考虑成有容量限制的情况，这样不但增加了课题的复杂性，而且实现了课题的现实性，在单辆洒水车现实性的前提下，为了可以更好地提高洒水车的作业效率，实现多辆洒水车同时进行城市的除尘工作。本文的研究内容主要有以下几个方面首先从线路优化问题出发，介绍了常见的两类线路优化问题VRP和CARP，分析了两者的应用区别，明确洒水车线路优化问题的数学模型，并说明了洒水车在线路优化的具体设计时用到的一些算法，其中遗传算法是整个寻优求解的中心环节，而warshall，Dijkstra，Euler算法只是作为遗传算法解码计算的辅助算法。其次介绍了单辆洒水车线路优化的总体设计思路结果。最后对多辆洒水车线路优化问题以多辆车作业分配和总行程最小为目标，提出了容量分割的方法并进行了详细的设计，包括路线优化的模型描述，设计原理，编码的方式与确定，种群的初始化，如何对染色体进行解码，转换到问题的现实解(难点)，计算目标函数及适应度函数和各种操作算子进化方式的确定(重点)。本文用MATLAB7.0在Window XP下进行编程并调试，并对实验结果进行了比较和分析。2洒水车路线优化问题2.1 路径优化问题说到路径优化问题，我们会很自然地就想起车辆路径问题(Vehicle Routing Problem，VRP)，因为配送问题在商业领域的应用十分广泛。VRP的一般描述为:用于送货的若干辆相同型号的车从配送中心出发，到不同的地理位置的客户那里去送货，然后返回配送中心，要求每辆车只能出发一次，任何一个客户有且只有一辆车访问，并且所配送的货物不能超过车辆的载重量，求解一种配送方案使得配送总成本最少。VRP问题根据不同的标准可以分为不同的类别。根据车辆是否有容量约束，可分为有容量约束的VRP问题(货担郎问题)，和无容量约束的VRP问题(TSP问题);根据货运任务的完成是否有时间要求，又可分为有时间约束和无时间约束两种。对于有时间约束的VRP还可以进一步分为带软时间窗的VRP和带硬时间窗的VRP。从1959年的VRP问题的开始提出到现在的半世纪以来，国内外对VRP的研究已经相当成熟，在各类VRP(如有时间窗、多车场等)的研究上都取得了丰富成果，采用的解决方法也多种多样，可分为精确算法(如整数规划、分枝定界等)和启发式算法(禁忌搜索、遗传算法、蚁群算法等)两大类。还有另外一种路径问题，也是本文的路径优化问题，那就是与VRP相类似的弧路径规划问题(Arc Routing Problem，ARP)这类问题在基础设施中的应用就相对就要多一些。本文研究的洒水车的路径优化问题就属于特殊的ARP问题，由于洒水车的城市除尘作业，车辆本身带有容量限制，因而洒水车路径优化问题属于“容量限制弦路径车辆行驶问题”。有容量限制的ARP，在现实中拥有广泛的应用背景，如前面提到的洒水车作业路线安排，以及冬季除冰车作业路线安排，城市垃圾车作业路线安排，还有城市输电线路的检查等。这时，我们会提出这样一个疑问:在前面的提到的两种路线优化问题中(VRP问题与CARP问题)，它们都可以有容量限制方面的约束条件，到底是怎样的一种分类方式把它们分成了两种不同的路线优化问题。这个划分的关键就在于它们在线路优化中的具体服务的对象是不一完全一样的，对于VRP问题而言，它主要是以点的服务主，而对于CARP问题，它主要是以边的服务为主。如果说到了这里还是不大清楚，也许可以通过一个问题的对比来说明。例如VRP问题中的车辆的配送问题(不带时间窗的)，因为车辆要装载货物，因此有一定的装载容量。同样的对于CARP问题中的洒水车路线优化问题，车辆本身就有一定的装水容量。这是相同的地方。然而不同的就是它们的服务对象是不同的。车辆的配送只要把货物送到指定的点就可。配送的本质在于遍历所有的点，所以不用遍历所有的边。而洒水车的路线优化则要遍历完所有的边。边集往往包含了点集，而点集不一定可以包含边集。也正是因为这点的不同这两类问题在路线优化时，即有相似点，但又不相同。2.2图论的相关知识和算法图论中所讨论的”图”，不是微积分，解析几何，几何学中讨论的图形，而是客观世界中某些具体事物间联系的一个数学抽象。如二元关系图，在关系图，在关系图中，我们不考虑点的位置及边线的长短曲直，而只关心哪些点之间有线相连通。这种数学抽象就是”图”的概念。图论在洒水车路线优化过程中起到的作用是:实现客观道路网到数学模型上的抽象。图是一个三元组，包括结点集合，边集合以及关联函数。无向图:每条边都是无向边的图称为无向图。有向图:每一条边都是有向边的图称为有向图。连通图:如果无向图G中每一对不同的顶点X和Y都有一条路，则称G是连通图。强连通图:如果有向图D任何一对结点之间都可以相互到达，则称这个有向图是强连通的。弱连通图:若在有向图D的基础图是连通的，则称有向图D是弱连通的。简单图:无环并且无平行边的图称为简单图。环:两端点相同的边称为环或称为自回路。平行边:两个结点间方向相同的若干条边称为平行边或重边。NP问题:至今既没有找到多项式算法，又不能证明它不存在多项式算法一类问题称为NP问题。度数:设G是任意图，X为G的任意结点，与结点X关联的边数(一条环要计算两次)称为X的度数(degree)。入度与出度:设D是任意有向图，X为D的任意一结点，射入X的边数称为X的入度(in-degree) ，射入X的边数称为X的入度(in-degree)。最短路径:给定一个起始点S和一个结束顶点T，在图中找出从S到T的一条最短路径。我们将起始点称为”源点”，结束点T称为”汇点”。单源最短路径:给定一个起始点S找出从S到图中其他各顶点的最短路径。最短路径的操作实质称为”淞弛”。开始进行最短路径算法时，只知道网的边和权值，随着要遍历中间点的加入，可以获得一条新的路径距离，如果在这一过程中出现这个新获得的路径距离比保存的记录值小，则把这个新得到的最小值传送给保存的最小记录中。这样的一个不断比较并更新最小值的遍历过程。可以形象地这样来描述，在两个顶点之间用一根橡皮筋系起来，后把它拉紧绕过另一个顶点，然后在这三个点的内部找到一个新的点，(相当于找到了新的当前最小值)，然后把被绕过的那个顶点拔掉，这样就在橡皮筋的张力作用下，而收缩，直到橡皮筋打在了那个新的顶点上。这样的一个过程就好像一张拉满的弓，慢慢松开的过程。 在洒水车的线路优化过程中，为了得到线路的最小值，在求解一条回路的过程中，首先要把实际的作业图转化到图的模型下，其次通过Floyd求解任意两点间的距离值，但又因为图中存在奇数度顶点而无法实现回路，所以要消除奇数度顶点。再次通过Dijkstra获得在遗传算法随机编码下对应奇数度点间的具体路径，接着用Euler求得对应编码下的一条回路，最后通过遗传算法的寻优思想获得所有回路中线路值最小的一条。2.2.1Floyd与warshall算法为了在洒水车线路优化中求得求得转换模式下的任意两点间距离，使用了Floyd算法已知矩阵A=(aij)m*l，B=(bjk)l*n， C=A*B=(Cij)m*n， 其中 Cij =min(ai1+b1j，ai2+b2j，ail+blj)已知矩阵A=(aij)m*n， B=(bij)m*n， 规定其中dij=min(aij，bij) 可以利用上面定义的运算求任意两点间的最短矩离。已知N阶加权简单图G，设D=(dij)n*n是图G的边权矩阵，即dij=w(i，j)(若G是有向图，则dij=w<i，j>)，若结点i到结点j无边相连时，则取dij=。 然后依次计算出矩阵D2，D3，Dn及S其中D2=D*D=(d2ij)n*nD3=D2*D=(d3ij)n*nDn=Dn-1*D=(dnij)n*n由定义可知，dkij表示从结点i到j 经k边的路(在有同图中即为有向路)中的长度最短者，而Sij为结点i到j的所有路(若是有向图，即为有向路)中的长度最短者。 不难看出，Floyd算法的时间复杂性是O(n4)，下面看介绍求任意两点间最短路的Warshall算法。已知n阶加权简单G，设D=(dij)n*n是图G的边权矩阵。(1) 输入D;(2) k:=1;(3) i:=1;(4) dij:=min(dij，dik+dkj)，j=1，2，n;(5) i:=i+1，若，转(4);(6) k:=k+1，若，转(3);否则停止。该算法是对i，j，k进进行行循环，故它的复杂性是O(n3)，即对矩D进行k次修改。2.2.2Dijkstra算法在洒水车线路优化中，一条Euler回路的获得要求图中没有奇数度顶点，而图中必定存在奇数度顶点。为了消除图中奇数度顶点，主要通过Dijkstra的指定点路径实现来完成。迪克斯屈拉算法求出一个连通加权加权简单图中从指定结点(如a)到指定终点(如z)的最短路。边i，j的权w(i，j)>0，且结点x的标号为L(x)。L(z)是从指定结点a到z的最短路的长度。Dijkstra的算法描述:对于一个所有权都为正数的加权连通简单图G，G中有顶点a=v0，v1，vn=z和权w(vi，vj)，若vi，vj不是G中的边，则w(vi，vj)=，(1)初始化标志，令L（a）=0，其余结点为无穷大，并定义一个记录现实路径的集合如S为空集。（2）第一次时把起点a存入S中，并逐个比较当前记录的结点L（a）+w(a，u)与L（u）的大小，u为不属于S的顶点，如果L（a）+w(a，u)<L（u），则L（a）+w(a，u)= L（u），记下这一轮中结点标号的最小值，并把这一标号送入S中，这样就给S中添加带最小标记的顶点并且更新不在S的顶点，当遍历完所有的顶点时，也就相应地得到了这个指定起点和终点的现实路径了。当然是一种合理的描述，但是考虑到在前面已经用到了Floyd算法实现任意两点之间的距离值（边权），因此在实现Dijkstra时，可以充分地利用前面得到的任意两点间的边权结果。这样一来就可以大大提高求解结果的快速性，而没有必要再重新地由已知的顶点维数以及边权初始化开始一一遍历。2.2.3Euler算法 在完成了Dijdstra算法以后，洒水车的作业图就不存在奇数度顶点，从而可以形成一条Euler回路。这对应于洒水车的一种作业方案。欧拉路:对于给定无孤立结点的无向图G，经过图G每边一次且一次的迹称为欧拉路。欧拉回路:对于给定无孤立结点的无向图G，经过图G每边一次且一次的回路称为欧拉回路。欧拉图:含有欧拉回路和无向连通图与含有向欧拉回路的弱连通有向图，统称欧拉图。 欧拉回路的充分必要条件:连通图G具有欧拉回路当且仅当它的每点都有偶数度。Euler回路的遍历算法可以用Fleury算法出实现。其思想是:(1) 任意选取一个顶点V0，置W0=V0(2) 假定迹(若是有向图，则是有向图)Wi=v0e1v1eivi已经选出，那么用下列方法从E(G)e1，e2，ei中选取ei+1(a) ei+1与vi关联(若是有向图，ei+1以vi为起点(b) 除非没有别的边可以选择，ei+1不是Gi=Ge1，e2，ei的割边。(3) 当(2)不能执行时，停止。否则让i+1i，转(2)显然，Fleury算法作出了G的一条迹。2.2.4奇数度路口的匹配因为不同的匹配结果对应不同的Euler回路，一条Euler回路对应洒水车作业的一种方案，奇数度路口的匹配就是要尽可能地找出所有的洒水车作业方案。同时它也是实现Dijkstra指定点的数据准备。对于一个任意的图，它有没有一条欧拉回路，就看连通图G中的每一个点的度数是不是都为偶数。如果说是偶数，那么毫无疑问，可以从连通图中获得一条欧拉回路。但是在实际的应用中我们对实际情况所转化的图往往是带有奇数度的点。这种情况下是不满足形成欧拉回路的充要条件。如果我们又很想用这种方法，那么只能对不满足欧拉充要条件的进行修改。就是对对些是奇数度的点进行两两组合，从而让奇数度的点变为偶数。这种方法在图论中称为最优球游的奇偶点图上作业法。其实这样的设计思想还有别外一个好处，因为Euler本身就是为了要获得一条路径最小的回路，然而这条回路的最终选择是通过遗传算法来实现的，即由遗传算法的适应度函数来决定。 遗传算法的应用或要达到它的一种较好的实验效果，那就不得不考虑遗传算法的寻优能力。粗略地讲要求遗传算法设计的染色体长度或染色体的基因位数(在遗传算法一章中会有详细的说明)在20位左右。因此奇偶点图上作业法的奇数度点之间的组合，它是考虑了遗传算法的编码问题对寻优效果的响影。虽然这样的思想不仅考虑了遗传算法的编码的寻优能力而且实现了在奇数度点下的Euler回路。给我们带来了很大的欣慰。但是在原来的图中用编程去实现的时候会产生错误。即那次是本来走的通路，那次是因为奇数点的原因而使奇数度点间的通路要重复行走，在计算机中并没有可以自动识别。所以我们又要加入虚拟点以区分要重复行走的那一次或几次。所谓虚拟就是实际上不存在，只是作为一种标志罢了，确切的说，在实际上这些路线仍然是要走的。说它是虚的是针对于优化问题中的现实意义而言，那些重复要走的边针对于优化过程不作为要考虑的过程，只能是标记用于区分:那一次是要进行除尘作业，那一次只是作为一种辅助Euler回路的形成，而并没有把它作为要进行除尘作业的路线。因为重复边是不作为为除尘计算考虑。所以要加入虚拟点来进行除尘计算的区分。2.2.5遗传算法在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优或准最优解。像VRP问题和规划问题等组合优化问题就是典型的的例子。在求解此类问题时，若不肥利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索过程，从而得到最优解或准最优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是这样一种特别有效的算法。它的主要特点是简单，通用，具有全局搜索性，搜索时只使用适应度函数，不用其他辅助信息，鲁棒性强，遗传算法的基本思想是优胜劣汰，适者生存。解的性能越优，越容易进入一下代进化，将其优良基因承下去，直至搜索到满意解或近似最优解。模拟进化的方法主要是用于求解组合优化问题以及存在不可微的目标函数或约束条件的复杂的非线性优化问题。常规的数学优化技术是基于梯度寻优技术，计算速度快，但要求优化问题具有可微性，且通常只能求得局部最优解，而模拟进化方法无可微性要求，适用于任意优化问题，而且由于它们采用随机优化技术，保证了有较大的概率求得全局最优解。从前面的说明我们已经知道，一种匹配对应一条回路，一条回路对应一种洒水车的作业方案.在洒水车的作业图中共有22个奇数度顶点，这22位的排列组合是一个非常大的数目，如果说要精确地求解，那么花费的计算时间是十分惊人的，因此，我们想通过GA的随机优化技术来实现解的获得.编码:这是应用GA时要解决的首要问题，也是设计GA的一个关键。编码方法除了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法。一个好的编编码方法，有可能会使得交叉运算，变异运算等GA操作可以简单地实现和执行。编码原则:1.(有意义积木块编码原则):就使用能易于产生与所求问题相关的且有低阶，短定义长度模式的编码方案。2.(最小字符编码原则):就使用能使得问题得到自然表示或描述的具有最小编码字符集的编码方案。编码方法:大体上可以分为三类，二进制编码，浮点数编码，符号编码。 二进制编码是GA中最常用的一种编码方法，是由0 和1所组成的二进制符号串。符号编码;是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集。如A，B，C，D或1，2，3，4，这种编码的主要优点:1.符合有意义积木块编码原则2.便于在GA中利用所求解问题的专门知识3.便于GA与相关近似得法的混合使用。 评价个体适应度的一般过程是:1.对个体编码串进行解码处理后，可得到个体的表现型。2.由个休的表现型可计算出对应 个体劳动的目标函数值。3.根据最优化问题的类型，设计目标函数值与适应度间的转换规则(一般目标函数值越好其对应的适应度值越大)。在计算适应度函数的过程中，需要对编码形式下的染色体进行解码，才可以计算其目标函数，进而得到其对应转换法则下的适应度函数值。适应度值的尺度变换:主要有线性变换，乘幂尺度变换和指数尺度变换。这变换思想是针对选择过程中，存在初期易于发生早熟现象。而在后期个体的适应度差异不大，从而无法对重点区域的重点搜索。需要对个体的适应度适当地放大，提高个体间差异和竞争。选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失，提高全局收敛性和计算效率。常用的方法有比例选择算子(赌盘法)。其基本思想是，各个个体被选中的概率与其适应度大小成正比。即适应度越高的个体被选中的概率也越大，反之越小。由于是随机操作的原因 ，有时甚至连适应度较高的个体也选择不上。从多样性分析，这恰恰是一个优点。交叉算子的设计和实现与所研究的问题密切相关，一般要求它不要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式。另外交叉算子的设计要和个体编码设计统一考虑。交叉一般有单点交叉和双点交叉。GA中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用相应基因座上的基因值来相互替换，从而形成一个新的个体。从遗传运算过程中产生新个体的方面来说。交叉运算是产生新个体的主要方法，决定了GA的全局搜索能力，而变异只是产生新个体的辅助方法，但它是必不可少的步骤。因为它决定了GA的局部搜索能力。3单辆洒水车的路线优化3.1问题及模型描述洒水车路径优化优化问题是以道路为服务对象的车辆路径问题，并带有容量限制，则问题可以看成是一个CARP的子问题。令作业图G由无向边组成。G=(V，E)。其中V表示图G的顶点集合，在这这些顶点中有一点代表车场，可以任意给定。E表示图G边集合。假设车场有一辆洒水车，让它从出发，对所有的边进行有且仅有一次的除尘工作，并且有一个重要的前提:要求进行完所有边的除尘的需水量q小于这辆洒水车的总装水容量W。在这个前提下实现该洒水车的行驶距离最小的目的。因此目标函数为洒水车的总花费最小。即MinZ=Cost(T) (3.1)相应的约束条件为: (3.2) (3.3)t=m,其中m表示边的条数 (3.4) (3.5)公式(3.4)和(3.5)共同保证每个服务边都有且仅被服务一次。3.2 路径优化设计思路根据单辆洒水车的问题描述，我们可以把握两个重要的信息点，就是1。要对图中所有的边都要进行有且仅有一次的除尘工作(即图中所有边都有走一次)，这是一个固定的值，无论你如何优化这一个距离是必需的。但这又不是实际行驶距离的最小值，因为任意一片城市的道路网，很难保证每一个路口的度数都是偶数，也就是说必定存在路口的度数是奇数的情况，那么由欧拉回路形成的充分必要条件可知，在图中是无法得到一条欧拉回路，如果说要遍历图中每条边有且仅一次，那么就要对某些边进重复地行驶。因此我们可以得到这样一个结论:总的花费=所有边的花费+重复行驶边的花费。如果要总的花费最小，那么在所有边的花费是一个固定值的条件下，只要重复边的花费最小，则有总的花费最小。单辆洒水车的路径优化思想用了四个算法把路径优化分为了四个相对独立的部分。每一部分完成不同的工作，最终实现一条总的花费最小的除尘路径。步骤如下:1. 用Floyd算法算出各奇数度点之间的距离，这样就得到了任意奇数度点之间的距离矩阵。这一个数值矩阵将成为GA实现最优的奇数度路口的匹配提供了一张选择，比较的数据表。2. 通过利用遗传算法的随机优化技术，保证以较大的概率求得全局的最优解的优点，实现了各个奇数度路口之间的最优匹配。3. 接着再对GA获得的最优匹配结果用Dijkstra求得对应匹配的现实路径，这样就对原来的作业图补成了一个各各路口都是偶数度的路口。从而满足了Euler形成的条件。4. 最后通过Euler回路算法实现单辆洒水车的具体优化路径。也是总花费最小的结果。3.3 实例分析实验设计使用的是柳州某区域部分路段见下图所示图1 柳州市某区域地图图2 图1的加权图图中线条表示各条需要的道路，带有数字的圆圈和方框表示路口，且圆圈表示偶数度路口，方框表示奇数度路口，数字表示路口的标号。经过调查知道，该区域地图的道路对于洒水车来说都是单行道路即洒水车只需要行走一遍就可以了。用遗传算法实现奇数度路口的匹配，得到的最优匹配结果为:Value=2037 3-4 17-18 21-20 19-13 15-16 7-8 12-14 11-6 5- 22 10-9 2-1 用Dijkstra算法求出固定路口到距离及路径，要求得出两个匹配好的奇数度路口的匹配路线，得到的结果如下:3479.003-4171856.00 17-182021310.00 20-211913 651.0019-24-26-27-131516110.0015-1678 124.007-81214252.0012-32-31-14116 297.0011-43-652258.005-22910 299.00 9-101271.001-2生成Euler闭迹回路。由Euler可知Euler回路里不允许有重复边的存在，但是在洒水车线路优化中对奇数点进行了匹配的同时，用Dijkstra实现匹配奇数度点间的具体路径的同时引入了重复边，这会使得Euler回路无法完成。因此要加入虚拟点，这样重复的那条道路就被划分为两条道路，从而可以得到一条Euler闭迹回路。虚拟点的手工安排如下:奇数度路吕匹配实现路径虚拟点343-59-459171817-1873202120-74-2