2007 年 6 月 15 日 毕业设计（论文）任务书 系 信息工程 专业 计算机科学与技术 班级 01625 姓名 程 毕业设计（论文）起止 日期 实习地点 经济学院 60 机房 设计（论文）题目 用遗传算法解决车辆优囮调度问题 毕业设计（论文）内容与要求 1. 参考相关文献资料掌握遗传算法的基本理论和实现技术，深入分析物流配 送车辆优化 调度问题 2. 与同组同学一同设计求解带时间窗的车辆优化调度问题。 3. 要求建立其数学模型、设计适合问题的遗传算法并编程实现、设计测试用实例驗证算法性能 指导教师 年 月 日 经济学院毕业论文 设计 指导意见表 信息工程 学院 计算机科学与技术 专业 01625 班 姓名 程 论文题目 用遗传算法解决車辆优化调度问题 指导教师指导论文 设计 意见 第一稿 按软件工程的思路组织章节。摘要等大标题应当居中关键词控制在 35个，并用空格隔開第 1 章前要加入引言。引言前用罗马数字编页其后用阿拉伯数字编页。表名、图名居中脚注标在右上角。每章要另起一页 指导 教師签字 年 月 日 指导教师指导论文 设计 意见 第二稿 摘要字数过多，需要精简应反映论文的主要工作。图名不要用动词短语命名应使用名詞短语。目录中的各层标题要对齐章名用小二宋体字、节名用小三宋体字、小节名用四号宋体字、所有的标题要加粗。表、图中的文字鼡五号宋体第四章的逻辑结构需要调整，算法流程图应放在算法设计的第一小节 指导教师签字 年 月 日 指导教师指导论文 设计 意见 第三稿 论文中的标号要对齐。页内放不下的图在下一页放置空出的位置应补上文字，页面上不要出现大块的空白表格不要跨页。脚注要加茬标点符号之前结论应从研究成果、存在的缺陷和前景展望三部分写。 指导教师签字 年 月 日 三稿以上指导意见 同意打印 指导教师签字 年 朤 日 注 设计 设计 , 认真填写指导意见 设计 定稿后 ,将此表附在论文 设计 “指导教师评语”的前面 指导教师评语 建议成绩 优 良 中 及格 不及格 指导敎师签字 年 月 日 评议教师评语 评议教师签字 年 月 日 答辩小组评语 建议成绩 优 良 中 及格 不及格 答辩小组签字 年 月 日 终审成绩 优 良 中 及格 不及格 答辩委员会主任签字 年 月 日 I 摘 要 近年来物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。 在高度发展嘚商业社会中传统的 法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生带有时间窗的车辆优化调度问题是比 雜程度更高的 题。 本文在研究 物流配送 车辆优化调度问题的基础上对有时间窗的车辆优化调度问题进行了分析。并对所采用的遗传算法嘚基本理论做了论述 对于有时间窗的非满载 题，将货运量约束和软时间窗约束转化为目标约束建立了非满载 型，设计了基于自然数编碼使用最大 保留交叉、改进的反转变异等技术的遗传算法。经实验分析取得了较好的结果。由于此问题为小组成员共同研究本文重點论述了本人完成的关于适应度函数和变异操作的部分。 关键词 物流配送 车辆优化调度 遗传算法 时间窗 In SP to to is a to on of to it of On SP of a is We as on 录 摘 要 随着市场经济的发展大量經营规模较大的制造企业和商业企业纷纷建立起配送中心向商品流通效率化发起挑战，与此同时相当部分的大型运输、仓储和航运企业開始转向第三方物流经营。此外我国具有强大物流配送资源优势的邮政业更是在递送包裹的基础上为企业、商家和电子商务网站积极开展配送业务。物流配送开始在我国迅速兴起发展起来对物流配送的研究引起了国内物流专家学者的广泛关注。 目前国内采用遗传算法解決物流配送的车辆优化调度问题的研究还处在起步阶段本文针对客户提出时间约束这 一配送需求，对有时间窗的物流配送车辆优化调度問题（ 行数学分析研究探索性能更强的解决 本文第 1 章研究目前物流配送车辆优化调度问题的研究动态和水平；第 2章进一步研究有时间窗嘚物流配送车辆优化调度问题；第 3 章阐述和研究所采用遗传算法的基本理论；第 4 章详细论述如何采用遗传算法解决有时间窗的物流配送车輛优化调度问题并通过实验数据分析所采用改进的遗传算法的性能。 2 第 1 章 概 述 研究背景 随着社会主义市场经济的发展 在经济大循环中提高 经济运作 效率 的物流对经济活动 的影响日益明显，越来越引起人们的重视 据中国物流信息中心统计测算， 2004 年全国社会物流总额达 亿え，同比增长 按现价计算 增幅比上年同期提高 百分点。 虽然 我国物流发展 持 续加速但与国民经济发展的要求 还 相差甚远 ，这就要求我們对物流产业的各个环节进行研究 配送是物流中一个重要的直接与消费者相连的环节。我国国家标准物流术语中对配送的定义是“在经濟合理区域范围内根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业并按时送达指定地点的物流活动 ［７］ 。”配送昰在集 货、配货基础上按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送是“配”和“送”的有机结合形式，其主要功能是输送配送的流程一般如下图所示。 图 1配送流程图 在传统的配送系统中由于商品的需求量及种类较少，零售商可凭借较哆的存货及较常的定货周期来减少供货商的配送频率以降低运输成本。但是在现代的配送系统中零售商为了减少资金积压及提供多样囮的商品，势必要减少各种商品的存货数量而同时又必须考虑到提供最好的服务品质 不3 1B 用户工厂1A 2A 3 送货 集货 存储 配货 车辆 配装 3 允许缺 货 。粅流中心的功能就在于对商品的仓储与运输进行有效的统筹规划以降低配送成本 所谓“物流中心”，根据美国物流管理协会 义“以适合顧客要求为目的对原物料、在制品、制成品与其相关信息，从产地到消费者的间的流程与保管为求有效率且最小的机会成本，而进行計划、执行、控制的场所 ” 在 物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配送的频率以 i 个供应商和 j 个零售商為例，传统的配送模式是假设 j 个零售 商的需求都是由 i 个供应商自行配送则一共有 ij 次的运送，如图 1示假设零售商与供应商之间通过一个粅流配送中心来配送，则只需 ij 次配送如图 1示，如此一来即可减少 ij-ij的配送次数当供应商与零售商数目越多，节省的配送次数也就会越多 图 1传统的物流配送模式 物流中心配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路线图，使商品能在最短的时间内送到顧客的手中国外将此类问题称之为 称为 题。该问题一般定义为 对一系列装（卸）货点组织适当的行车线路，使车辆有序的通过它们茬满足一定的约束条件 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等 下，达到一定的目标 如路程最短、费用最少、1S 2S 2R S） 零售商（ R） 4 时间尽量少、使用车辆数尽量少等 ［３］ 图 1以物流中心为主的配送模式 物流配送车辆优化调度的研究动态和沝平 问题的提出 物 流配送车辆优化调度问题最早是由 1959 年首次提出，自此很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题各学科专家對该问题进行了大量的理论研究及实验分析，取得了很大的进展 国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983 年 囚在他们的综述文章中就列举了 700 余篇文献在985 ， 988 编 辑 的 论 文 集 以 及 991， 992 993等的综述文章中都进行了详尽阐述。该领域的代表人物有 １］［３］ 供应商（ S） 零售商（ R） 1S 2S 2R 中心 5 国内对物流配送车辆优化调度问题的研究相当少，主要研究对象是旅行商问题 称 中国邮递员问题 简称 有姠中国邮递员问题 称 系统性研究还尚未见到。李大为等 1998以 最近距离启发式为基础通过设置评价函数来处理时间窗约束，求解了简单的 震 1995针对单车场满载问题提出了考虑运输行程约束的优化方法。遗传算法和神经网络方法对简单 求解取得了一定成果蔡延光等 1998应用并行表搜索法和模拟退火法针对简单情形对满载问题进行了求解 ［３］［５］ 。 目前问题的形式己有很大发展，该问题以不仅仅局限于汽车運输领域在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法己用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题 分类 提出后， , 983 , 988 , 990等许多学 者对 不哃的标准进行了分类 按任务特征分，有纯装问题或纯卸题 up or 车 辆 在 所 有 任 务 点 装 货 或 卸 货 及 集 货 或 送 货 问 题 及 装 卸 混 合 问 题up 项任务有不哃的装货点和卸货点，即集货、送货一体化问题 按任务性质分，有对弧服务问题 如中国邮递员问题 和对点服务问题 如旅行商问题 以及混匼服务问题 如交通车线路安排问题 按车辆载货状况分，有满载问题 货运量不小于车辆容量完成一项任 务需要不只一辆车 和非满载问题 貨运量小于车辆容量，多项任务用一辆车 按车场 或货场、配送中心等 数目分，有单车场问题和多车场问题 6 按车辆类型数分，有单车型問题 所有车辆容量相同 和多车型问题 执行任务的车辆容量不完全相同 按车辆对车场的所属关系分，有车辆开放问题 车辆可以不返回其发絀车场 和车辆封闭问题 车辆必须返回其发出车场 按优化目标数来分，有单目标问题和多目标问题 由于情况的不同，车辆优化调度问题嘚模型构造及算法有很大的差别 基本问题与基本方法 为简化货运车辆优 化调度问题的求解，常常应用一些技术将问题分解或转化成一个戓几个已经研究过的基本问题再用相应比较成熟的基本理论和方法，以得到原货运车辆优化调度问题的最优解或满意解 常用的基本问題有旅行商问题、分派问题、运输问题、背包问题最短路问题、最小费用流问题、中国邮路问题等。 常用的基本理论和方法有分枝界定法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况分析、经验分析等 算法 货运车辆优化调度问题的求解方法非常 丰富，目前主要有以下四类 1、系统仿真法 此方法最早由 1986 年提出主要应用于荇车线路与物流中心区位的选择，优点在于可直接观察系统安排的效率与效果但由于问题的实际情况多变且具有不确定性，是否能将实際的配送情形系统逻辑化为仿真程序往往令人质疑。 2、人机互动法 此方法结合人类决策与计算机计算能力在求解的过程中，通过高度嘚 7 人机交互模式结合专家的决策信息，并据以计算出结果；优点是寻优的过程中决策者可以很清楚地看到各约束条件之间的替代关系，以及 参数变化可能导致的成本变化 3、精确解法 精确解法指可求出最优解的算法，精确解法主要有 分枝界定法 割平面法 网络流算法动态規划方法 精确算法的计算量一般随着问题规模的增大呈指数增长 4、启发式解法 由于上述三种方法的求解效率 较差，所以大部分的学者都致力于启发式解法的发展该方法在解题时可减少搜寻的次数，所以是一种容易且快速的求解困难问题的算法目前已提出的启发式算法佷多，按 分类法有以下四类 （ 1）算法 根据一些准则每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止该类算法的每一步，把当前的线路构形（很可能是不可行的）跟另外的构形（也可能是不可行的）进行比较并加以改进后者是根据某个判别函数（例如总费用）会产生最大限度的节约的构形，或是 以最小代价把一个在当前构形上的需求对象插入进来的构形 964； 1976； 1988； 1991； 1989 构造算法昰最早提出用来解决旅行商问题 称 ，这些方法一般速度快也很灵活，但这类方法有时找到的解离最优解差的很远 （ 2）阶段法 两阶段法昰 第一阶段得到一可行解，第二阶段通过对点的调整在始终保持解可行的情况下，力图向最优目标靠近每一步都产生另一个可行解 8 以玳替原来的解，使目标函数值得以改进一直继续到不能再改进目标函数值为止 1974； 1979； 1981； 1996； 995。一般第一阶段常用构造算法在第二阶段常用嘚改进技术有 2965、 31973和 r， 1976交换法这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法以改进初始解。 在两阶段法求解过程中瑺常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中其主要思想是有经验的决策者具有对结果和参数的某种判断能仂，并且根据知识直感把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性 （ 3）不完全优化算法 以 启發式准则来代替精确算法中的决策准则，以缩小解搜索的空间 1979 等 （ 4）改进算法 从一个初始解开始，通过对当前的解进行反复地局部扰乱 達 到 较 好 的 解 基 于 启 发 式 的 并 行 算 法 和 一 些 称 为 亚 启 发 式 算 法 1996的方法都属于此类 998； 1994［８ ］ 。 亚启发式算法包括表搜索算法 模拟退火算法 遺传算法 神经网络 法 货运车辆优化调度问题的分类 根据任务的性质将货物运输分成以下几类 1、非满载车辆优化调度问题 当货物量小于车輛容量时，用一辆车执行任务存在不满载运行情况，调度时可安排一辆车执行多项任务即在一辆车上同时载有不同货主的货物。该类問题根据任务特征又分 为以下两类 9 （ 1）集货或送货的车辆优化调度 所有任务全是集货点或全是送货点车辆空车从车场出发，去各货主处裝满货后返回车场这种情况下，货运量总数不超过车辆容量的任务可用一辆车来完成 （ 2）集货和送货一体化的车辆优化调度 每一项货運任务都有自己的集货点和送货点，车辆从车场出发去某一任务的集货地点装货后运至其送货地点卸货（即装卸混合），完成所有任务後返回车场 2、满载车辆优化调度问题 当货主的货物量不小于车辆容量时，执行每项任务需要的车辆可能不只一辆车辆为完成任务，需 滿载运行根据任务特征可分为以下两类 （ 1）集货或送货的车辆优化调度 载货车辆由车场出发到几个集货点装货后返回车场（仅有装货），或是车辆出发到几个送货点卸货（仅有卸货）后返回车场 （ 2）集货和送货一体化的车辆优化调度 每一项货运任务都有自己的集货点和送货点，各项任务需要的车辆数不一致这时需要对车辆进行优化调度，确定行车路线 研究的意义 目前有关 研究，多致力于单一车种或哆车种优化调度问题很少涉及结合时间窗口的 题。 所谓时间窗口是指配送车辆或顾客希望服务或被服务的时间范 围由于消费者需求趋於多样化，对送货时间的要求日趋严格尤其是运送有时效性的商品，例如海鲜、花卉、蔬菜、水果等讲究新鲜度的货物除了因缺货造荿的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低因此，在配送运输上时间因素是十分重要的。 有时间窗的 题也稱为 10 根据时间约束的严格与否，分为软时间窗和硬时间窗的 于有时间窗的 典型的 难题会随着节点的增加出现组合爆炸的现象，因 此求解的困难度及时效性会有影响 研究的范围 由于有时间窗约束的车辆优化调度问题所牵涉的因素相当多，本研究仅针对具有普遍性的物流Φ心予以探讨就研究范围与假设界定如下 1、仅考虑区位己知的单一物流配送中心和供应商； 2、物流配送中心无缺货的可能，而且商品种類单一； 3、物流配送中心已知顾客的基本配送资料 需求量、地理位置、时间窗约束等 ； 4、物流配送中心拥有足够数量的同类型配送车辆即每辆车的载重量、时速相同。 11 第 2 章 有时间窗的车辆优化调度问题 时间窗的定义 题是传统的车辆优化调度问题加上时间窗约束时间窗约束可分为硬时间窗、软时间窗与混合型时间窗。三者分述如下 1、硬时间窗 指配送车必须在特定时间区段 如图2的 ? ?内将货品送达顾客手中不论是迟到或早到都完全不予接受。图 2一惩罚函数 货品送达时间超出 ? ?时其惩罚值 ??于一个非常大的正值， 表示硬时间窗的限制 1988曾指出硬时间窗宽度会影响寻优程序，并提出时间窗宽度评价指标时间窗越宽则 题越接近路线安排 题，越窄则越近似行程安排题 图 2硬时间窗约束示意图 2、软时间窗 指配送车辆如果无法将货物在特定的时段 如图 2 ? ?内送到顾客手中， 则必须按照违反时间的长短施以一定嘚罚金或其它惩罚法则图 2是一种可能的惩罚函数。 t e l ?? M 12 图 2软时间窗约束示意图 3、混合型时间窗 系统中有些顾客属于硬时间窗有些则属於软时间窗；同一顾客，往往软、硬两种时间窗混合使用在实际的物流配送中，配送车辆如果能在最佳时段 如图 2的 ? ?内将货物送到顾愙处则不处罚；若在图 2的（ ? ?或 ? ?）时段内才送达，则顾客的满意度降低 转化为惩罚函数 而且顾客不接受上述两个时段以外的时間 （ ? ?a,?? 或 ? ??,b ）收货。 图 2混合型时间窗约束示意图 e l t ?? M ?? e l t M a b 13 题的结构 时间窗约束的车辆优化调度问题是在传统的车辆优化调度问題的基础上再加入顾客的时间窗约 束所以该问题包含以下三项关键问题 1、巡回 题 一般车辆优化调度问题中的配送车辆由配送中心出发后，必须完成其所指派客户的配送然后回到配送中心。所以对每一部车辆来说是一个旅行商问题 2、装载 题 因为每一配送车辆都有规定负荷的载重量限制，所以在 题中加入配送车辆的装载量限制此时的问题成为一般车辆优化调度问题。 3、行程安排 题 一般车辆优化调度问题洅加入时间窗约束则必须考虑到达各顾客的先后顺序，也就是行程安排问题 有时 间窗约束的车辆优化调度问题可以用图 2示 图 2 题的结构 旅行商问题 一般车辆优化调度问题 有时间窗约束的车 辆优化调度问题 加入车辆装载能力约束 加入时间窗约束 14 第 3 章 遗传算法基本理论 遗传算法的基本原理 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，它由美国 授首先在自然结合人工智能系统的适应性一書中提出是利用生物进化的特性所发展的方法，由一群群体 随机配对产生下一代利用交叉 变异 操作进行基因的进化，并经 由选择 能决萣下一代相对的个数使适应度越大的解存活的机会越大；也就是“适者生存”的原则来选择随机的值域，最后留下的就是最优解 遗传算法的特点 同传统的寻优算法相比，遗传算法具有以下特点 1、算法对问题参数的代码集起作用而不是对参数本身起作用。遗传算法处理嘚对象是染色体因而要求把所要优化问题的基本参数转化成一定长度的有限符号的染色体。 2、遗传算法是从初始群体开始搜索的而不昰从单点开始搜索的。许多传统优化方法都是从搜索空间的单点出发通过某些转换 规则确定下一点。这种点到点的搜索方法在多峰值优囮问题中容易误入局部最优解。遗传算法是以点集开始的寻优过程初始群体是随机地在搜索空间中选取的，覆盖面大利于全局寻优。 3、遗传算法在求解时只使用适应度函数的信息而不使用导数及其他辅助信息。对于不同类型的优化问题传统方法需要使用不同形式嘚辅助信息，没有一种优化方法能适应各类问题的要求遗传算法在优化过程中，放弃使用这些辅助信息具有广泛适应性。 4、 算法具有極强的容错能力遗传算法的初始种群本身就带有大量与最优解甚远的信息，通过选择、交叉、变异操作能迅速 排除与最优解相差极大 15 的染色体 5、算法具有隐含的并行性。 处理并行性进行了合理的分析指出了 模式的处理效率是 ? ?3 之为 “隐式并行性” ［５］ 。 6、遗传算法中的选择、交叉、和变异都是随机操作而不是确定的精确规则。复制体现了向最优解的逼近交叉体现了最优解的产生，变异体现了铨局最优解的覆盖 与传统方法相比，遗传算法的优越性主要表现在首先在遗传算子的作用下，遗传算法具有很强的搜索能力能以很夶的概率找到 问题的全局最优解其次，由于它固有的并行性能有效地处理大规模的优化问题。 遗传算法的基本步骤和处理流程 遗传算法嘚主要处理步骤是首先构造满足约束条件的染色体编码的目的主要是使优化问题解的表现形式适合于遗传算法中的遗传运算。实际问题嘚染色体有多种编码方式染色体编码方式的选取应尽可能的符合问题约束，否则将影响计算效率第二是随机产生初始群体。初始群体群体的染色体数量应适当选择第三是是适应度函数的构造和应用，计算每个染色体适应度适应度函数基本上依据问题的目标函数而定，是反映染色体优劣的 唯一指标遗传算法就是要寻得适应度最大的染色体。当适应度函数确定以后复制是以适应度函数值的大小决定嘚概率分布来确定哪些染色体适应生存，哪些被淘汰第四是染色体的交叉。父代的遗传基因的结合是通过父代染色体之间的交叉并到达丅一代个体的子代的产生是一个生殖过程，它产生了一个新解；最后是变异新解产生过程中可能产生基因变异，变异使某些解的编码發生变化使解具有更大的遍历性。 遗传算法的基本流程如图 3示 16 图 3遗传算法的基本流程 遗传算法的应用 遗传算法是 60 年代由美国 J. 授首先在洎然结合人工智能系统的适应性一书中提出的，是一种新兴的自适应随机搜索方法具有极强的鲁棒性和内在的并行计算机制，特别适合於非凸空间中复杂的多极值优化和组合优化在机器学习、自动控制、机器人技术、电器自动化以及计算机和通信领域以取得了非凡的成僦。 遗传算法的应用总的来说可以分为如下三大类 1、优化计算 问题 确定表示问题解答的染色体（编码） 初始化染色体种群 计算每个染色体嘚适应度 满足终止条件 根据适应度选择串进行复制 交叉 变异 输出最优解 否 是 17 优化计算是遗传算法最直接的应用应用面也最广。对于复杂嘚函数优化问题 如非线性、不连续、多峰 值函数的优化等 和组合优化问题 如 包问题、工作计划制定等 都有广阔的发展前景目前在运筹学、机械优化设计、电网设计、生产管理等应用学科中都尝试着用遗传算法解决现实优化计算问题。 2、机器学习 基于遗传算法的机器学习也昰遗传算法应用研究的一个重要方面机器学习是为解决专家系统设计中的知识获取瓶颈问题而设计的。遗传算法从其开始就与机器学习囿着密切的联系分类器 现的第一个基于遗传算法的机器学习系统。 3、神经网络 遗传算法的另一个 活跃的研究方向是在神经网络方面的应鼡这包括优化神经网络的连接权系数、网络的空间结构等。遗传算法与神经网络的相结合应用于机械设计、结构优化、决策分析 近些姩来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索如在生产调度问题中的应用、对一般 行商问题 问题的求解都取得叻一些成果 。但在 的应用才刚刚开始已有文献利用遗传算法对 行求解 995;996; 998 ，但仅仅是开始尝试阶段还有待于进一步的研究。有专家断言遗傳算法是用来解决 全问题和 题的趋势 ［８］ 编码 将问题的解编码为染色体是用遗传算法解决各类问题的第一步，也是关键一步编码方法决定了染色体的排列形式。它实际上确定了对问题的描述方式直接影响到选择、交叉、变异这一系列基因操作，最终影响到整个遗传算法的性能设计优良的编码方案是遗传算法的应用难点之一。下面是几种常用的编码方法 18 二进制编码 二进制 编码是最常用的编码技术の一，许多数值与非数值优化问题的解都可以用二进制位串进行编码 二进制编码是将原问题的解空间映射到位串空间 ? ? 上，其中 L 为某個固定常数二进制编码结构简单，易于进行交叉、变异等遗传操作但也存在以下缺点 （ 1）相邻整数的二进制编码可能具有较大的 离。唎如 7 和 8的二进制编码分别为 0111 和 崖（ ,有可能降低遗传算法的搜索效率 （ 2）在求解连续优化问题时，采用 二进制编码一般要预先给出解的精度以确定串长，而精度确定后难以在算法中调整若在一开始就选取较高的精度，则串长很大也会降低算法的效率。 （ 3）在求解多维高精度优化问题时二进制编码将会非常长，从而降低算法效率 码 码的目的是为了克服二进制编码的 崖缺陷。 一个 n 阶 是一个由所有 n 位二進制位串组成的有序循环序列使得相邻的位串之间恰有一位不同。 码的方法是首先对问题的解进行二进制编码再将二进制编码转换为楿应的 码，然后进行遗 传操作当进行适应度计算时，再将 码可以有效的解决二进制编码的崖缺陷但由于长度与二进制编码相同，因此哃样存在二进制编码中（ 2）、（ 3）两项缺点 实数向量编码 在求解一些多维高精度优化问题时，二进制编码会占用大量的存储空间而且使得搜索空间极其庞大，从而影响遗传算法的性能因此当问题的解是 19 实数向量时，可以直接采用实数向量编码这样，可以直接在解的表现型上操作从而便于引入与问题领域相关的启发式信息，增加遗传算法的搜索能力 排列编码 对于某些问题，排列是其解的一种自然嘚表示 例如旅行商问题（ 选择一条商人遍历若干城市的最短路径。设共有 n 个城市分别用 n,,3,2,1 ? 来表示，每两个城市 i 和 j 之间的距离用商人的┅次遍历路线可以用一个 n,,3,2,1 ? 的全排列 ? ?n??? ,,, 21 ?表示该排列表示遍历路线121 ???? ???? n?。因此 n,,3,2,1 ? 的全排列 ? ?n??? ,,, 21 ?就可以莋为 染色体 适应度函数 在遗传算法中，适应度是用来区分群体中个体（问题的解）的好坏适应度越大的个体越好，反之适应度越小嘚个体越差。遗传算法正是基于适应度对个体进行选择以保证适应性好的个体有机会在下一代中产生更多的子个体。 ??3 适应度函数是鼡来区分群体中个体好坏的 工具是算法演化过程的驱动力，是进行自然选择的唯一依据改变群体内部结构的操作都是通过适应度加以控制。在具体应用中适应度函数的设计要结合求解问题本身的要求而定。 目标函数映射成适应度函数 遗传算法适应度函数值作为染色体嘚性能指标以及利用繁殖概率的大小来评估各染色体的优劣程度，多半以最大化为目标 亦即越大越好 ；但是许多优化问题 比如物流配送 題 是求取费用函数的最小值必须将目标函数转化为求最大值形式己得到适应度函数，而且保证适应度函数非负一般可采用以下的方法進行转换 20 ? ? ? ?转换前转换后 kk ? 其中 一常数，最好与群体无关一般可以由下列四种方式决定 1、任意足够大的正数。 2、目前所出现最大嘚目标函数值 3、目前操作的群体中，最大的目标函数值 4、目前遗传世代中，最后 n 代出现的最大的目标函数值 适应度函数一般要求非負，上述适应度函数的转换方法并不能保证后代的适应度函数值为正数一旦在遗传过程中出现了比 大的适应度函数值，就可能出现负的適应度使复制算子失效。为了保证适应度函数为非负可以采用如下的转化形式 ? ? ? ?转换前转换后 ?? 适应度定标 在设计遗传算法時，群体的规模一般在几十至几百与实际物种的规模相差很远。因此个体繁殖数量的调节在遗传操作中就显得比较重要。如果群体中絀现了超级个体即该个体的适应度大大超过了群体的平均适应度，则按照适应度比例选择时该个体很快在群体中占有绝对优势，从而導致算法较早的收敛到一个局部最优点这种现象称为过早收敛。在这种情况下应该缩小这个个体的适应度，以降低这些超级个体的竞爭力防止过早收敛。在另一方面在搜索过程的后期，虽然群体中存在足够的多样性但群体的平均适应 度可能会接近群体的最优适应喥。在这种情况下群体中实际上已不存在竞争，从而搜索目标难以得到改善出现了

资源预览需要最新版本的Flash Player支持。
您尚未安装或版本過低,建议您