毕业设计（论文）用遗传算法解决车辆优化调度.doc

摘 要近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。在高度发展的商业社会中，传统的VSP算法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。带有时间窗的车辆优化调度问题是比VSP复杂程度更高的NP难题。本文在研究物流配送车辆优化调度问题的基础上，对有时间窗的车辆优化调度问题进行了分析。并对所采用的遗传算法的基本理论做了论述。对于有时间窗的非满载VSP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VSP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。经实验分析，取得了较好的结果。由于此问题为小组成员共同研究，本文重点论述了本人完成的关于适应度函数和变异操作的部分。关键词：物流配送 车辆优化调度 遗传算法 时间窗Abstract Recent years, logistics, taken as "third profit resource”, has been developing rapidly. In the developed commercial society, traditional VSP algorithm have been unable to meet the requirement that Quick Response to customer demand had brought forth, then the conception of Time Window has come into being. The vehicle-scheduling problem with time window is also a NP-hard problem being more complicated than VSP. This text has been researched to the vehicle-scheduling problem with time window on the basis of researched to logistic vehicle scheduling problem. And it has explained the basic theory of genetic algorithm.On the VSP with time window, while the restraints of capacity and time windows are changed into object restraints, a mathematic model is established. We use technique such as maximum preserved crossover and design genetic algorithm on nature number, which can deal with soft time windows through experimental analysis, have made better result. Because this problem was studied together for group members, this text has expounded the part about fitness function and mutation operator that I finished.Key words: logistic distribution vehicle scheduling problem genetic algorithm time windows目 录摘 要IAbstractII目 录III引 言1第1章 概 述21.1 研究背景21.2 物流配送车辆优化调度的研究动态和水平41.2.1 问题的提出41.2.2 分类51.2.3 基本问题与基本方法61.2.4 算法61.2.5 货运车辆优化调度问题的分类81.3 研究的意义91.4 研究的范围10第2章 有时间窗的车辆优化调度问题(VSPTW)112.1 时间窗的定义112.2 VSPTW问题的结构13第3章 遗传算法基本理论143.1 遗传算法的基本原理143.1.1 遗传算法的特点143.1.2 遗传算法的基本步骤和处理流程153.1.3 遗传算法的应用163.2 编码173.2.1 二进制编码183.2.2 Gray编码183.2.3 实数向量编码183.2.4 排列编码193.3 适应度函数193.3.1 目标函数映射成适应度函数193.3.2 适应度定标203.4 遗传算法的基因操作213.4.1 选择算子213.4.2 交叉算子223.4.3 变异算子253.5 遗传算法控制参数设定28第4章 遗传算法求解有时间窗非满载VSP304.1 问题描述304.2 数学模型314.2.1 一般VSP模型314.2.2 有时间窗VSP模型324.3 算法设计334.3.1 算法流程图334.3.2 染色体结构334.3.3 约束处理354.3.4 适应度函数364.3.5 初始种群364.3.6 遗传算子364.3.7 控制参数和终止条件374.4 算法实现394.5 实验及结果分析394.5.1 控制参数选定394.5.2 实例实验434.5.3 实例数据444.5.4 实例数据分析44结 论45参考文献47谢 辞48引 言随着市场经济的发展，大量经营规模较大的制造企业和商业企业纷纷建立起配送中心向商品流通效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业开始转向第三方物流经营。此外，我国具有强大物流配送资源优势的邮政业更是在递送包裹的基础上为企业、商家和电子商务网站积极开展配送业务。物流配送开始在我国迅速兴起发展起来，对物流配送的研究引起了国内物流专家学者的广泛关注。 目前国内采用遗传算法解决物流配送的车辆优化调度问题的研究还处在起步阶段。本文针对客户提出时间约束这一配送需求，对有时间窗的物流配送车辆优化调度问题（VSPTW）进行数学分析，研究探索性能更强的解决VSPTW的遗传算法。 本文第1章研究目前物流配送车辆优化调度问题的研究动态和水平；第2章进一步研究有时间窗的物流配送车辆优化调度问题；第3章阐述和研究所采用遗传算法的基本理论；第4章详细论述如何采用遗传算法解决有时间窗的物流配送车辆优化调度问题并通过实验数据分析所采用改进的遗传算法的性能。第1章 概 述1.1 研究背景随着社会主义市场经济的发展，在经济大循环中提高经济运作效率的物流对经济活动的影响日益明显，越来越引起人们的重视。据中国物流信息中心统计测算，2004年，全国社会物流总额达38.4万亿元，同比增长29.9%(按现价计算)，增幅比上年同期提高2.9个百分点。虽然我国物流发展持续加速，但与国民经济发展的要求还相差甚远，这就要求我们对物流产业的各个环节进行研究。 配送是物流中一个重要的直接与消费者相连的环节。我国国家标准物流术语中对配送的定义是：“在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。”配送是在集货、配货基础上，按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送”的有机结合形式，其主要功能是输送。配送的流程一般如下图所示。 用户 工厂 进货 送货 集货 存储 配货 车辆 配装 图1-1 配送流程图在传统的配送系统中，由于商品的需求量及种类较少，零售商可凭借较多的存货及较常的定货周期来减少供货商的配送频率，以降低运输成本。但是在现代的配送系统中，零售商为了减少资金积压及提供多样化的商品，势必要减少各种商品的存货数量，而同时又必须考虑到提供最好的服务品质(不允许缺货)。物流中心的功能就在于对商品的仓储与运输进行有效的统筹规划以降低配送成本。所谓“物流中心”，根据美国物流管理协会(The Council of Logistics Management, CLM)定义：“以适合顾客要求为目的，对原物料、在制品、制成品与其相关信息，从产地到消费者的间的流程与保管，为求有效率且最小的机会成本，而进行计划、执行、控制的场所(Depot) ”。在物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配送的频率，以i个供应商和j个零售商为例，传统的配送模式是假设j个零售商的需求都是由i个供应商自行配送，则一共有i×j次的运送，如图1-2所示。假设零售商与供应商之间通过一个物流配送中心来配送，则只需i+j次配送，如图1-3所示，如此一来即可减少(i×j-(i+j)的配送次数，当供应商与零售商数目越多，节省的配送次数也就会越多。 供应商（S） 零售商（R） 图1-2 传统的物流配送模式物流中心配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路线图，使商品能在最短的时间内送到顾客的手中。国外将此类问题称之为Vehicle Scheduling Problem，简称为VSP问题。该问题一般定义为:对一系列装（卸）货点，组织适当的行车线路，使车辆有序的通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。供应商（S） 零售商（R） 物流中心 图1-3 以物流中心为主的配送模式 1.2 物流配送车辆优化调度的研究动态和水平1.2.1 问题的提出物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983年Bodin, Golden等人在他们的综述文章中就列举了700余篇文献。在Christofides(1985)，Golden和Assad(1988)编辑的论文集，以及Altinkermer和Gavish(1991)，Laporte(1992)，Salhi(1993)等的综述文章中都进行了详尽阐述。该领域的代表人物有Bodin，Christfids，Golden，Assad，Ball，Laporte，Rinnooy Kan，Lenstra，Desrosiers和Desrochers等人。国内对物流配送车辆优化调度问题的研究相当少，主要研究对象是旅行商问题(Traveling Salesman Problem，简称TSP)、中国邮递员问题(Chinese Postman Problem ,简称CPP)、有向中国邮递员问题(Directed Chinese Postman Problem，简称DCPP)等，系统性研究还尚未见到。李大为等(1998)以TSP的最近距离启发式为基础，通过设置评价函数来处理时间窗约束，求解了简单的VSP。张震(1995)针对单车场满载问题，提出了考虑运输行程约束的优化方法。遗传算法和神经网络方法对简单TSP的求解取得了一定成果。蔡延光等(1998)应用并行表搜索法和模拟退火法针对简单情形对满载问题进行了求解。目前，问题的形式己有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法己用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。1.2.2 分类VSP被提出后，Linus (1981),Bodin和Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和Savelsbergh(1990)等许多学者对VSP从不同角度，按不同的标准进行了分类。按任务特征分，有纯装问题或纯卸题(pure pick up or pure delivery, 车辆在所有任务点装货或卸货，及集货或送货问题) 及装卸混合问题(combined pick up and delivery，每项任务有不同的装货点和卸货点，即集货、送货一体化问题)。按任务性质分，有对弧服务问题(如中国邮递员问题)和对点服务问题(如旅行商问题)以及混合服务问题(如交通车线路安排问题)。按车辆载货状况分，有满载问题(货运量不小于车辆容量，完成一项任务需要不只一辆车)和非满载问题(货运量小于车辆容量，多项任务用一辆车)。按车场(或货场、配送中心等)数目分，有单车场问题和多车场问题。按车辆类型数分，有单车型问题(所有车辆容量相同)和多车型问题(执行任务的车辆容量不完全相同)。按车辆对车场的所属关系分，有车辆开放问题(车辆可以不返回其发出车场)和车辆封闭问题(车辆必须返回其发出车场)。按优化目标数来分，有单目标问题和多目标问题。由于情况的不同，车辆优化调度问题的模型构造及算法有很大的差别。1.2.3 基本问题与基本方法 为简化货运车辆优化调度问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原货运车辆优化调度问题的最优解或满意解。 常用的基本问题有：旅行商问题、分派问题、运输问题、背包问题最短路问题、最小费用流问题、中国邮路问题等。 常用的基本理论和方法有：分枝界定法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况分析、经验分析等。1.2.4 算法货运车辆优化调度问题的求解方法非常丰富，目前主要有以下四类： 1、系统仿真法(Simulation )此方法最早由Golden和Skiscim于1986年提出，主要应用于行车线路与物流中心区位的选择，优点在于可直接观察系统安排的效率与效果，但由于问题的实际情况多变且具有不确定性，是否能将实际的配送情形系统逻辑化为仿真程序，往往令人质疑。2、人机互动法此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人机交互模式，结合专家的决策信息，并据以计算出结果；优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致的成本变化。3、精确解法(Exact procedures )精确解法指可求出最优解的算法，精确解法主要有：分枝界定法(Branch and Bound Approach)、割平面法(Cutting Planes Approach)、网络流算法(Network Flow Approach)、动态规划方法(Dynamic Programming Approach)。精确算法的计算量一般随着问题规模的增大呈指数增长。 4、启发式解法(Heuristics)由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速的求解困难问题的算法。目前已提出的启发式算法很多，按Cesar Rego的分类法有以下四类：（1）算法(Constructive Algorithm)根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止。该类算法的每一步，把当前的线路构形（很可能是不可行的）跟另外的构形（也可能是不可行的）进行比较并加以改进，后者是根据某个判别函数（例如总费用）会产生最大限度的节约的构形，或是以最小代价把一个在当前构形上的需求对象插入进来的构形(Clarke和Wright，1964；Mole和Jamesson，1976；Paessens，1988；Altinkemer和Gavish，1991；Desrochers和Verhoog，1989)。构造算法是最早提出用来解决旅行商问题(Traveling Salesman Problem,简称TSP)及VSP的，这些方法一般速度快，也很灵活，但这类方法有时找到的解离最优解差的很远。（2）阶段法(Two-phase Algorithm)两阶段法是：第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止(Gillett和Miller，1974；Christofids、Mingozzi和Toth，1979；Fisher和Jaikumar，1981；Renaud、Boctor和Laporte，1996；Bramel和Simchi-Levi，1995)。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2-opt(Lin，1965)、3-opt(Lin Kernighan，1973)和Or-opt(Or，1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。（3）不完全优化算法(Incomplete Optimization Algorithm)以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间(Toth、 Christofides和Mingozzi，1979等)。（4）改进算法(Improvement Algorithm)从一个初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。基于启发式的并行算法和一些称为亚启发式算法(Metaheuristics、Laporte 和Osman，1996)的方法都属于此类(Cesar Rego，1998；Gendrea、Laporte和Potvin，1994)。 亚启发式算法包括表搜索算法(Table Search)、模拟退火算法(Simulated Annealing)、遗传算法(Genetic Algorithm)和神经网络(Neural Networks)方法。1.2.5 货运车辆优化调度问题的分类 根据任务的性质将货物运输分成以下几类： 1、非满载车辆优化调度问题 当货物量小于车辆容量时，用一辆车执行任务，存在不满载运行情况，调度时可安排一辆车执行多项任务，即在一辆车上同时载有不同货主的货物。该类问题根据任务特征又分为以下两类： （1）集货或送货的车辆优化调度 所有任务全是集货点或全是送货点，车辆空车从车场出发，去各货主处装满货后返回车场。这种情况下，货运量总数不超过车辆容量的任务可用一辆车来完成。 （2）集货和送货一体化的车辆优化调度每一项货运任务都有自己的集货点和送货点，车辆从车场出发，去某一任务的集货地点装货后运至其送货地点卸货（即装卸混合），完成所有任务后返回车场。 2、满载车辆优化调度问题当货主的货物量不小于车辆容量时，执行每项任务需要的车辆可能不只一辆，车辆为完成任务，需满载运行。根据任务特征可分为以下两类：（1）集货或送货的车辆优化调度 载货车辆由车场出发到几个集货点装货后返回车场（仅有装货），或是车辆出发到几个送货点卸货（仅有卸货）后返回车场。（2）集货和送货一体化的车辆优化调度每一项货运任务都有自己的集货点和送货点，各项任务需要的车辆数不一致，这时需要对车辆进行优化调度，确定行车路线。1.3 研究的意义目前有关VSP的研究，多致力于单一车种或多车种优化调度问题，很少涉及结合时间窗口的VSP问题。所谓时间窗口是指配送车辆或顾客希望服务或被服务的时间范围。由于消费者需求趋于多样化，对送货时间的要求日趋严格，尤其是运送有时效性的商品，例如海鲜、花卉、蔬菜、水果等讲究新鲜度的货物，除了因缺货造成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。因此，在配送运输上，时间因素是十分重要的。有时间窗的VSP问题也称为VSPTW(Vehicle Scheduling Problem with Time Windows），根据时间约束的严格与否，分为软时间窗和硬时间窗的VSP。由于有时间窗的VSP是典型的NP难题，会随着节点的增加出现组合爆炸的现象，因此求解的困难度及时效性会有影响。1.4 研究的范围由于有时间窗约束的车辆优化调度问题所牵涉的因素相当多，本研究仅针对具有普遍性的物流中心予以探讨，就研究范围与假设界定如下：1、仅考虑区位己知的单一物流配送中心和供应商；2、物流配送中心无缺货的可能，而且商品种类单一；3、物流配送中心已知顾客的基本配送资料(需求量、地理位置、时间窗约束等)；4、物流配送中心拥有足够数量的同类型配送车辆，即每辆车的载重量、时速相同。第2章 有时间窗的车辆优化调度问题(VSPTW)2.1 时间窗的定义VSPTW问题是传统的车辆优化调度问题加上时间窗约束，时间窗约束可分为硬时间窗、软时间窗与混合型时间窗。三者分述如下：1、硬时间窗(Hard Time Windows)：指配送车必须在特定时间区段(如图2-1中的)内将货品送达顾客手中，不论是迟到或早到都完全不予接受。图2-1为一惩罚函数(Penalty Function)当货品送达时间超出时，其惩罚值等于一个非常大的正值，表示硬时间窗的限制。Desrochers (1988)曾指出硬时间窗宽度会影响寻优程序，并提出时间窗宽度评价指标，时间窗越宽则VSPTW问题越接近路线安排(Routing)问题，越窄则越近似行程安排(Scheduling)问题。 图2-1 硬时间窗约束示意图2、软时间窗(Soft Time Windows)：指配送车辆如果无法将货物在特定的时段(如图2-2的)内送到顾客手中，则必须按照违反时间的长短施以一定的罚金或其它惩罚法则。图2-2就是一种可能的惩罚函数。 图2-2 软时间窗约束示意图3、混合型时间窗(Mixed Time Windows )：系统中有些顾客属于硬时间窗，有些则属于软时间窗；同一顾客，往往软、硬两种时间窗混合使用。在实际的物流配送中，配送车辆如果能在最佳时段(如图2-3中的内将货物送到顾客处，则不处罚；若在图2-3中的（或）时段内才送达，则顾客的满意度降低(转化为惩罚函数)，而且顾客不接受上述两个时段以外的时间 （或）收货。 图2-3 混合型时间窗约束示意图2.2 VSPTW问题的结构时间窗约束的车辆优化调度问题是在传统的车辆优化调度问题的基础上再加入顾客的时间窗约束，所以该问题包含以下三项关键问题：1、巡回(Routing)问题一般车辆优化调度问题中的配送车辆由配送中心出发后，必须完成其所指派客户的配送，然后回到配送中心。所以对每一部车辆来说，是一个旅行商问题(TSP)。2、装载(Loading)问题因为每一配送车辆都有规定负荷的载重量限制，所以在TSP问题中加入配送车辆的装载量限制，此时的问题成为一般车辆优化调度问题。3、行程安排(Scheduling)问题一般车辆优化调度问题再加入时间窗约束，则必须考虑到达各顾客的先后顺序，也就是行程安排问题。有时间窗约束的车辆优化调度问题可以用图2-4表示：旅行商问题 一般车辆优化调度问题 有时间窗约束的车 辆优化调度问题 加入车辆装载能力约束加入时间窗约束图 2-4 VSPTW问题的结构第3章 遗传算法基本理论3.1 遗传算法的基本原理遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，它由美国Holland教授首先在自然结合人工智能系统的适应性一书中提出，是利用生物进化的特性所发展的方法，由一群群体(Population)以随机配对产生下一代，利用交叉(Crossover)及变异(Mutation)等操作进行基因的进化，并经由选择(Selection)机能决定下一代相对的个数，使适应度越大的解存活的机会越大；也就是“适者生存”的原则来选择随机的值域，最后留下的就是最优解。3.1.1 遗传算法的特点同传统的寻优算法相比，遗传算法具有以下特点： 1、算法对问题参数的代码集起作用，而不是对参数本身起作用。遗传算法处理的对象是染色体，因而要求把所要优化问题的基本参数转化成一定长度的有限符号的染色体。 2、遗传算法是从初始群体开始搜索的，而不是从单点开始搜索的。许多传统优化方法都是从搜索空间的单点出发，通过某些转换规则确定下一点。这种点到点的搜索方法在多峰值优化问题中，容易误入局部最优解。遗传算法是以点集开始的寻优过程，初始群体是随机地在搜索空间中选取的，覆盖面大，利于全局寻优。3、遗传算法在求解时只使用适应度函数的信息，而不使用导数及其他辅助信息。对于不同类型的优化问题，传统方法需要使用不同形式的辅助信息，没有一种优化方法能适应各类问题的要求。遗传算法在优化过程中，放弃使用这些辅助信息，具有广泛适应性。4、算法具有极强的容错能力。遗传算法的初始种群本身就带有大量与最优解甚远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的染色体。5、算法具有隐含的并行性。Goldeberg对GA的处理并行性进行了合理的分析，指出了GA对模式的处理效率是，Holland称之为GA的“隐式并行性”。 6、遗传算法中的选择、交叉、和变异都是随机操作，而不是确定的精确规则。复制体现了向最优解的逼近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。与传统方法相比，遗传算法的优越性主要表现在：首先，在遗传算子的作用下，遗传算法具有很强的搜索能力，能以很大的概率找到问题的全局最优解：其次，由于它固有的并行性，能有效地处理大规模的优化问题。3.1.2 遗传算法的基本步骤和处理流程遗传算法的主要处理步骤是：首先构造满足约束条件的染色体。编码的目的主要是使优化问题解的表现形式适合于遗传算法中的遗传运算。实际问题的染色体有多种编码方式，染色体编码方式的选取应尽可能的符合问题约束，否则将影响计算效率。第二是随机产生初始群体。初始群体群体的染色体数量应适当选择。第三是是适应度函数的构造和应用，计算每个染色体适应度。适应度函数基本上依据问题的目标函数而定，是反映染色体优劣的唯一指标，遗传算法就是要寻得适应度最大的染色体。当适应度函数确定以后，复制是以适应度函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。第四是染色体的交叉。父代的遗传基因的结合是通过父代染色体之间的交叉并到达下一代个体的。子代的产生是一个生殖过程，它产生了一个新解；最后是变异，新解产生过程中可能产生基因变异，变异使某些解的编码发生变化，使解具有更大的遍历性。遗传算法的基本流程如图3-1所示。问题 确定表示问题解答的染色体（编码） 初始化染色体种群 计算每个染色体的适应度 满足终止条件？ 根据适应度选择串进行复制 交叉 变异 输出最优解 否 是 图3-1 遗传算法的基本流程3.1.3 遗传算法的应用遗传算法是60年代由美国J. Holland教授首先在自然结合人工智能系统的适应性一书中提出的，是一种新兴的自适应随机搜索方法，具有极强的鲁棒性和内在的并行计算机制，特别适合于非凸空间中复杂的多极值优化和组合优化，在机器学习、自动控制、机器人技术、电器自动化以及计算机和通信领域以取得了非凡的成就。遗传算法的应用总的来说可以分为如下三大类： 1、优化计算优化计算是遗传算法最直接的应用，应用面也最广。对于复杂的函数优化问题(如非线性、不连续、多峰值函数的优化等)和组合优化问题(如VSP, TSP,0-1背包问题、工作计划制定等)都有广阔的发展前景。目前在运筹学、机械优化设计、电网设计、生产管理等应用学科中都尝试着用遗传算法解决现实优化计算问题。 2、机器学习基于遗传算法的机器学习也是遗传算法应用研究的一个重要方面。机器学习是为解决专家系统设计中的知识获取瓶颈问题而设计的。遗传算法从其开始就与机器学习有着密切的联系。分类器CS-1是Halland与Keitman实现的第一个基于遗传算法的机器学习系统。 3、神经网络遗传算法的另一个活跃的研究方向是在神经网络方面的应用，这包括优化神经网络的连接权系数、网络的空间结构等。遗传算法与神经网络的相结合应用于机械设计、结构优化、决策分析。近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索，如在生产调度问题中的应用、对一般TSP (Traveling Salesman Problem,旅行商问题)问题的求解都取得了一些成果(Oliver和Smith, 1989:Fogel, 1993 )。但在VSP中的应用才刚刚开始，已有文献利用遗传算法对VSP进行求解(Berthold,1995;Malmborg,1996;Ochi和Luiz 1998 )，但仅仅是开始尝试阶段，还有待于进一步的研究。有专家断言遗传算法是用来解决NP完全问题和NP难题的趋势。3.2 编码将问题的解编码为染色体是用遗传算法解决各类问题的第一步，也是关键一步。编码方法决定了染色体的排列形式。它实际上确定了对问题的描述方式，直接影响到选择、交叉、变异这一系列基因操作，最终影响到整个遗传算法的性能。设计优良的编码方案是遗传算法的应用难点之一。下面是几种常用的编码方法。3.2.1 二进制编码 二进制编码是最常用的编码技术之一，许多数值与非数值优化问题的解都可以用二进制位串进行编码。 二进制编码是将原问题的解空间映射到位串空间上，其中L为某个固定常数。二进制编码结构简单，易于进行交叉、变异等遗传操作。但也存在以下缺点：（1）相邻整数的二进制编码可能具有较大的Hamming距离。例如7和8的二进制编码分别为0111和1000.这一缺陷称为Hamming悬崖（Hamming cliffs）,有可能降低遗传算法的搜索效率。（2）在求解连续优化问题时，采用二进制编码，一般要预先给出解的精度以确定串长，而精度确定后难以在算法中调整。若在一开始就选取较高的精度，则串长很大，也会降低算法的效率。（3）在求解多维高精度优化问题时，二进制编码将会非常长，从而降低算法效率。3.2.2 Gray编码Gray编码的目的是为了克服二进制编码的Hamming悬崖缺陷。 一个n阶Gray码是一个由所有n位二进制位串组成的有序循环序列，使得相邻的位串之间恰有一位不同。Gray编码的方法是首先对问题的解进行二进制编码，再将二进制编码转换为相应的Gray编码，然后进行遗传操作，当进行适应度计算时，再将Gray编码转换为相应的二进制编码。Gray编码可以有效的解决二进制编码的Hamming悬崖缺陷，但由于长度与二进制编码相同，因此同样存在二进制编码中（2）、（3）两项缺点。3.2.3 实数向量编码 在求解一些多维高精度优化问题时，二进制编码会占用大量的存储空间，而且使得搜索空间极其庞大，从而影响遗传算法的性能。因此当问题的解是实数向量时，可以直接采用实数向量编码。这样，可以直接在解的表现型上操作，从而便于引入与问题领域相关的启发式信息，增加遗传算法的搜索能力。3.2.4 排列编码 对于某些问题，排列是其解的一种自然的表示。 例如旅行商问题（TSP）：选择一条商人遍历若干城市的最短路径。设共有n个城市，分别用来表示，每两个城市和之间的距离用表示，则商人的一次遍历路线可以用一个的全排列表示，该排列表示遍历路线。因此的全排列就可以作为TSP的染色体。3.3 适应度函数在遗传算法中，适应度是用来区分群体中个体（问题的解）的好坏，适应度越大的个体越好，反之，适应度越小的个体越差。遗传算法正是基于适应度对个体进行选择，以保证适应性好的个体有机会在下一代中产生更多的子个体。适应度函数是用来区分群体中个体好坏的工具，是算法演化过程的驱动力，是进行自然选择的唯一依据。改变群体内部结构的操作都是通过适应度加以控制。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。3.3.1 目标函数映射成适应度函数遗传算法适应度函数值作为染色体的性能指标，以及利用繁殖概率的大小来评估各染色体的优劣程度，多半以最大化为目标(亦即越大越好)；但是许多优化问题(比如物流配送VSP问题)是求取费用函数的最小值，必须将目标函数转化为求最大值形式己得到适应度函数，而且保证适应度函数非负。一般可采用以下的方法进行转换：其中MAX为一常数，最好与群体无关，一般可以由下列四种方式决定:1、任意足够大的正数。2、目前所出现最大的目标函数值。3、目前操作的群体中，最大的目标函数值。4、目前遗传世代中，最后n代出现的最大的目标函数值。适应度函数一般要求非负，上述适应度函数的转换方法并不能保证后代的适应度函数值为正数，一旦在遗传过程中出现了比MAX更大的适应度函数值，就可能出现负的适应度，使复制算子失效。为了保证适应度函数为非负，可以采用如下的转化形式：3.3.2 适应度定标在设计遗传算法时，群体的规模一般在几十至几百，与实际物种的规模相差很远。因此，个体繁殖数量的调节在遗传操作中就显得比较重要。如果群体中出现了超级个体，即该个体的适应度大大超过了群体的平均适应度，则按照适应度比例选择时，该个体很快在群体中占有绝对优势，从而导致算法较早的收敛到一个局部最优点。这种现象称为过早收敛。在这种情况下，应该缩小这个个体的适应度，以降低这些超级个体的竞争力，防止过早收敛。在另一方面，在搜索过程的后期，虽然群体中存在足够的多样性，但群体的平均适应度可能会接近群体的最优适应度。在这种情况下，群体中实际上已不存在竞争，从而搜索目标难以得到改善，出现了停滞现象。在这种情况下，应该放大个体的适应度，以提