《遗传算法及在物流配送路径优化中的应用概要(共10页).doc》由会员分享，可在线阅读，更多相关《遗传算法及在物流配送路径优化中的应用概要(共10页).doc（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上遗传算法及在物流配送路径优化中的应用一、 遗传算法1.1遗传算法定义遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，
2、而一个种群则由经过基因（gene）编码的一定数目的个体(individual组成。每个个体实际上是染色体(chromosome带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择
3、（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。1.2遗传算法特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的
4、概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。3、 遗传算法使用多个点的搜索信息，具有隐含并行性。4、 遗传算法使用概率搜索技术，而非确定性规则。1.3遗传算法的一般算法遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。评估适应度对每一个解(染色体指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解
5、问题的答案。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。繁殖(包括子代突变带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。下一代如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。并行计算非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移
6、到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。1.4术语说明由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：一、染色体(Chronmosome染色体又可以叫做基因型个体(individuals,一定数量的个体组成了群体(population,群体中个体的数量叫做群体大小。二、基因(Gene基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元
7、素分别称为基因。它们的值称为等位基因(Alletes。三、基因地点(Locus基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position，有时也简称基因位。基因位置由串的左向右计算，例如在串 S1101 中，0的基因位置是3。四、基因特征值(Gene Feature在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。五、适应度(Fitness各个个体对环境的适应程度叫做适应度(fitness。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应
8、度函数. 这个函数是计算个体在群体中被使用的概率。1.5遗传算法的应用由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：1、 函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、
9、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2、 组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。二、遗传算法在物流配送路径优化中的运用随着市场经济的
10、发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。物流配送是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人。在物流配送业务中，存在许多优化决策问题，通过制定合理的配送路径，快速而经济地将货物送达用户手中。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。物流配送路径优化问题可以描述为：从配送中心（或称物流据点）用多辆汽车向多个需求点（或称顾客）送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合理安排汽车路线，使总运距最短，并满足以下条件：（1）每条配送路径上各需求点的需求量之和不超过汽车载重量；（2）
11、每条配送路径的长度不超过汽车一次配送的最大行驶距离；（3）每个需求点的需求必须满足，且只能由一辆汽车送货。本文借鉴文献3建立的车辆路径问题的数学模型，并通过考虑上述物流配路径优化问题的约束条件和优化目标，建立了物流配送路径优化问题的数学模型。设配送中心有K辆汽车，每辆汽车的载重量为Qk（k=1，2，K），其一次配送的最大行驶距离为Dk，需要向L个需求点送货，每个需求点的需求量为qi（i=1，2，L），需求点i到j的运距为dij，配送中心到各需求点的距离为d0j（i、j=1，2，L），再设nk为第k辆汽车配送的需求点数（nk=0表示未使用第k辆汽车），用集合Rk表示第k条路径，其中的元素rki表
12、示需求点rki在路径k中的顺序为i（不包括配送中心），令rk0=0表示配送中心，则可建立如下物流配送路径优化问题的数学模型： （1）s.t. （2） （3） （4） （5） （6） （7） （8）上述模型中，（1）式为目标函数；（2）式保证每条路径上各需求点的需求量之和不超过汽车的载重量；（3）式保证每条配送路径的长度不超过汽车一次配送的最大行驶距离；（4）式表明每条路径上的需求点数不超过总需求点数；（5）式表明每个需求点都得到配送服务；（6）式表示每条路径的需求点的组成；（7）式限制每个需求点仅能由一辆汽车送货；（8）式表示当第k辆汽车服务的客户数1时，说明该辆汽车参加了配送，则取sign(
13、nk=1，当第k辆汽车服务的客户数1时，表示未使用该辆汽车，因此取sign(nk=0。针对物流配送路径优化问题的特点，构造了求解该问题的遗传算法。（1）编码方法的确定。根据物流配送路径优化问题的特点，采用简单直观的自然数编码方法，用0表示配送中心，用1、2、L表示各需求点。由于在配送中心有K辆汽车，则最多存在K条配送路径，每条配送路径都始于配送中心，也终于配送中心，为了在编码中反映车辆配送的路径，作者巧妙地采用了增加K-1个虚拟配送中心的方法，分别用L+1、L+2、L+K-1表示。这样，1、2、L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体，并对应一种配送路径方案。例如，对于
14、一个有7个需求点，用3辆汽车完成配送任务的问题，则可用1、2、9（8、9表示配送中心）这9个自然数的随机排列，表示物流配送路径方案。如个体表示的的配送路径方案为：路径1：0-1-2-9（0），路径2：9（0）-6-3-8（0），路径3：8（0）-5-4-7-0，共有3条配送路径；个体表示的配送路径方案为：路径1：0-5-7-3-8（0），路径2：9（0）-4-2-1-6-0，共有2条配送路径。（2）初始群体的确定。随机产生一种1L+K-1这L+K-1个互不重复的自然数的排列，即形成一个个体。设群体规模为N，则通过随机产生N个这样的个体，即形成初始群体。（3）适应度评估。对于某个个体所对应的配送
15、路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值（即各条配送路径的长度之和）。本文根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行
16、解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示：Fj=1/（Zj+MjG） （9）式中，G为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正数。（4）选择操作。将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用赌轮选择法4产生。具体地说，就是首先计算上代群体中所有个体适应度的总和（Fj），再计算每个个体的适应度所占的比例（Fj/Fj），以此作为其被选择的概率。这样选择方法既可保证最优个体生存至下一代，又能保证适应度较大的个体以较大的机
17、会进入下一代。（5）交叉操作。对通过选择操作产生的新群体，除排在第一位的最优个体外，另N-1个个体要按交叉概率Pc进行配对交叉重组。本文采用了一种类似OX法2的交叉方法，现举例说明之：随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：A=47|8563|921，B=83|4691|257；将B的交配区域加到A的前面，A的交配区域加到B的前面，得：A=4691|，B=8563|；在A、B中自交配区域后依次删除与交配区相同的自然数，得到最终的两个体为：A”=，B”=。与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果，这对维持群体的多样化特性有一定的作用。
18、（6）变异操作。由于在选择机制中采用了保留最佳样本的方式，为保持群体内个体的多样化，本文采用了连续多次对换的变异技术，使个体在排列顺序上的有较大变化。变异操作是以概率Pm发生的，一旦变异操作发生，则用随机方法产生交换次数J，对所需变异操作的个体的基因进行J次对换（对换基因的位置也是随机产生的）。根据上述遗传算法参考编制的C语言程序，并具体设一个某配送中心使用2辆汽车对8个需求点进行送货的物流配送路径优化问题实例进行了实验计算。设汽车的载重量为8t，每次配送的最大行驶距离为40km，配送中心与各需求点之间、各需求点相互之间的距离及各需求点的需求量见表1。表1 配送中心与需求点之间的距离及各需求点
19、的需求量表dij (km ji01234567800467.5920101681406.541057.51110266.507.510107.57.57.537.547.501059915491010100107.57.5105205105100797.56107.57.597.570710716117.597.59701088107.515107.510100qj (t-12121422根据上述实例的特点，在实验计算中采用了以下参数：群体规模取20，交叉概率和变异概率分别取0.95和0.05，进化代数取50，变异时基因换位次数取5，对不可行路径的惩罚权重取100km。对上述问题，利用计算机随
20、机求解10次，得到的计算结果见表2。表2 物流配送路径优化问题的遗传算法计算结果计算次序12345678910配送总距离Z /km727276.57067.57073.57571.569从表中数据可以看出，10次运行得到的结果均优于节约法所得的结果79.5km。而且第5次还得到了该问题的最优解67.5km，其对应的配送路径方案为：路径1：0-4-7-6-0；路径2：0-2-8-5-3-1-0。可见，利用遗传算法可以方便有效地求得物流配送路径优化问题的最优解或近似最优解（或称满意解）。三、遗传算法的现状进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其
21、是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算
22、法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化
23、计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概
24、率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子
25、比其余两个有更好的性能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产
26、生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。四、参考文献1蔡希贤，夏士智. 物流合理化的数量方法M. 武汉：华中工学院出版社，1985.2陈国良，王煦法，庄镇泉，王东生. 遗传算法及其应用M. 北京：人民邮电出版社，1996.3姜大立，杨西龙，杜文，周贤伟. 车辆路径问题的遗传算法研究J. 系统工程理论与实践，1999（6），p4044.4黄晓滨，皱书蓉，张洪伟 改进的遗传算法及在物流配送路径优化中的应用 西南民族大学学报自然科学版，2008（8）4Z. 米凯利维茨. 演化程序遗传算法和数据编码的结合M. 北京：科学出版社，2000.专心-专注-专业