遗传算法及在物流配送路径优化中的应用

遗传算法及在物流配送路径优化中的应用

一、遗传算法

1.1遗传算法定义

遗传算法(GeneticAlgorithm)是模拟达尔文的遗传选择和自然淘汰的生物进

化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国

Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著

(AdaptationinNaturalandArtificialSystems》,GA这个名称才逐渐为人所知,

J.Holland教授所提出的GA通常为简单遗传算法(SGA)。

遗传算法是从代表问题可能潜在的解集的一个种群

(population)开始的，而一个种群则由经过基因

(gene)编码的一定数目的个体(individual)组成。每个

个体实际上是染色体(chromosome)带有特征的实体。染

色体作为遗传物质的主要载体，即多个基因的集合，其内

部表现(即基因型)是某种基因组合，它决定了个体的形

状的外部表现，如黑头发的特征是由染色体中控制这一

特征的某种基因组合决定的。因此，在一开始需要实现从

表现型到基因型的映射即编码工作。由于仿照基因编码的

工作很复杂，我们往往进行简化，如二进制编码，初代种

群产生之后，按照适者生存和优胜劣汰的原理，逐代

(generation)演化产生出越来越好的近似解，在每一代,

根据问题域中个体的适应度(fitness)大小选择

(selection)个体，并借助于自然遗传学的遗传算子

(geneticoperators)进行组合交叉(crossover)和变

异(mutation),产生出代表新的解集的种群。这个过程

将导致种群像自然进化一样的后生代种群比前代更加适

应于环境，末代种群中的最优个体经过解码(decoding),

可以作为问题近似最优解。

1.2遗传算法特点

遗传算法是•类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法

相比，主要有以下特点：

1.遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变

量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物

学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能

够方便的应用遗传操作算子。

2.遗传算法直接以适应度作为搜索信息，无需导数

等其它辅助信息。

3、遗传算法使用多个点的搜索信息，具有隐含并行

性。

4、遗传算法使用概率搜索技术，而非确定性规则。

1.3遗传算法的一般算法

遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：

创建一个随机的初始状态

初始种群是从解中随机选择出来的，将这些解比喻为奥色体或基因，该种群被称

为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定

了。

评估适应度

对每一个解（染色体）指定一个适应度的值，根据问题求解的实际接近程度来指定

（以便逼近求解问题的答案）＜不要把这些“解”与问题的“答案”混为一谈，可以把

它理解成为要得到答案，系统可能需要利用的那些特性。

繁殖（包括子代突变）

带有较高适应度值的那些染色体更可能产生后代（后代产生后也将发生突变）。后

代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。

下一代

如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么

问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程,

代代演化下去，直到达到期望的解为止。

并行计算

非常容易将遗传算法用到并行计算和群集环境中。一

种方法是直接把每个节点当成一个并行的种群看待。然后

有机体根据不同的繁殖方法从一个节点迁移到另一个节

点。另一种方法是“农场主/劳工”体系结构，指定一个节

点为“农场主”节点，负责选择有机体和分派适应度的值,

另外的节点作为“劳工”节点，负责重新组合、变异和适

应度函数的评估。

1.4术语说明

由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中

公用到很多生物遗传学知识，下面是我们将公用来的些术语说明：

一、染色体(Chronmosome)

染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体

(population),群体中个体的数量叫做群体大小。

二、基因(Gene)

基因是串中的元素，基因用于表示个体的特征。例如有一个串S=1011,则其中

的1,0,1,1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

三、基因地点(Locus)

基因地点在算法中表示一个基因在串中的位置称为基因位置(GenePosition),

有时也简称基因位。基因位置由串的左向右计算，例如在串S=1101中，0的基因位

置是3。

四、基因特征值(GeneFeature)

在用串表示整数时，基因的特征值与二进制数的权一致：例如在串S=1011中,

基因位置3中的1,它的基因特征值为2；基因位置1中的1,它的基因特征值为8。

五、适应度(Fitness)

各个个体对环境的适应程度叫做适应度(fitness)。为

了体现染色体的适应能力，引入了对问题中的每一个染

色体都能进行度量的函数，叫适应度函数,这个函数是计

算个体在群体中被使用的概率。

1.5遗传算法的应用

由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其

它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法

提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种

类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要

应用领域：

1.函数优化。

函数优化是遗传和法的经她应用领域，也是遗传算法进行性能评价的常用算例，

许多人构造出r各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函

数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目

标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结

果。

2.组合优化

随着问题规模的增大，组合优化问题的搜索空间也

急剧增大，有时在目前的计算上用枚举法很难求出最优

解。对这类复杂的问题，人们已经意识到应把主要精力放

在寻求满意解上，而遗传算法是寻求这种满意解的最佳

工具之一。实践证明，遗传算法对于组合优化中的NP问

题非常有效。例如遗传算法已经在求解旅行商问题、背

包问题、装箱问题、图形划分问题等方面得到成功的应用。

此外，GA也在生产调度问题、自动控制、机器人学、图

象处理、人工生命、遗传编码和机器学习等方面获得了广

泛的运用。

二、遗传算法在物流配送路径优化中的运用

随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。物

流配送是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货

人。在物流配送业务中，存在许多优化决策问题，通过制定合理的配送路径，快速而经济地

将货物送达用户手中。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配

送成木及增加经济效益都有较大影响.

物流配送路径优化问题可以描述为：从配送中心（或称物流据点）用多辆汽车向多个需求点

（或称顾客）送货，每个需求点的位置和需求量•定，每辆汽车的载重量•定，要求合理安

排汽车路线，使总运距最短，并满足以下条件：（1）每条配送路径上各需求点的需求量之和

不超过汽车载重量；（2）每条配送路径的长度不超过汽车一次配送的最大行驶距离：（3）每

个需求点的需求必须满足，且只能由•辆汽车送货。本文借鉴文献⑶建立的车辆路径问题的

数学模型,并通过考虑上述物流配路径优化问题的约束条件和优化目标，建立r物流配送路

径优化问题的数学模型。

设配送中心有K辆汽车，每辆汽车的载重量为Qk（k=l,2,•••,K）,其•次配送的

最大行驶距离为Dk,需要向L个需求点送货，每个需求点的需求量为qi（i=l.2,•••,L）,

需求点i到j的运距为dij,配送中心到各需求点的距离为dOj（i、j=l,2,•••,L）,再设

nk为第k辆汽车配送的需求点数（nk=0表示未使用第k辆汽车），用集合Rk表示第k条路

径，其中的元素rki表示需求点rki在路径k中的顺序为i（不包括配送中心），令rk0=0表

示配送中心，则可建立如卜物流配送路径优化问题的数学模型：

minZ=〃(名)1(1)

*=lf=l

s.t.(2)

立…AJ•阚〃(〃”2⑶

1=1

0<nk<L(4)

»k=L(5)

k=l

=(rki|rkiGL}j=1,2,...,nk}(6)

人n"=。以产&⑺

1n>1

阚2D=|o其k他

上述模型中，（1）式为目标函数；（2）式保证每条路径上各需求点的需求量之和不超过汽

车的我.重量；（3）式保证每条配送路径的长度不超过汽车一次配送的最大行驶距离；（4）式

表明每条路径上的需求点数不超过总需求点数：（5）式表明每个需求点都得到配送服务：（6）

式表示每条路径的需求点的组成；（7）式限制每个需求点仅能由•辆汽车送货；（8）式表示

当第k辆汽车服务的客户数21时，说明该辆汽车参加了配送，则取sign（nk）=l.当第k辆汽

车服务的客户数＜1时，表示未使用该辆汽车，因此取sign（nk）=O。

针对物流配送路径优化问题的特点，构造了求解该问题的遗传算法。

（1）编码方法的确定。根据物流配送路径优化问题的特点，采用简单直观的自然数编码方

法，用0表示配送中心，用12・・・、L表示各需求点。由于在配送中心有K辆汽车，则最多

存在K条配送路径,每条配送路径都始于配送中心，也终于配送中心，为了在编码中反映车

辆配送的路径，作者巧妙地采用了增加K-1个虚拟配送中心的方法，分别用L+1.L+2.・・・、

L+K-1表示。这样，12・・・、L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个

体，并对应•种配送路径方案，例如，对于•个有7个需求点，用3辆汽车完成配送任务的

问题,则可用12・・・、9（8、9表示配送中心）这9个自然数的随机排列,表示物流配送路

径方案。如个体129638547表示的的配送路径方案为：路径1:0-1-2-9（0）,路径2:9（0）

-6-3-8（0）,路径3:8（0）-5-4-7-0,共有3条配送路径;个体573894216表示的配送路径

方案为：路径1:0-573-8（0）,路径2:9（0）-4-2-1-6-0,共有2条配送路径。

（2）初始群体的确定。随机产生一种1~L+K-1这L+K-1个互不重复的自然数的排列，即

形成一个个体。设群体规模为N,则通过随机产生N个这样的个体，即形成初始群体。

（3）适应度评估。对于某个个体所对应的配送路径方案,要判定其优劣.一是要看其是

否满足配送的约束条件：二是要讣算其目标函数值（即各条配送路径的长度之和）。本文根

据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务

及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量

之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束

条件。为此，对每个个体所对应的配送路径方案，要对各条路径逐•进行判断,看其是否满

足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。

对于某个个体j,设其对应的配送路径方案的不可行路径数为Mj（Mj=O表示该个体对应一

个可行解），其目标函数值为Zj,则该个体的适应度Fj可用下式表示：

Fj=l/（Zj+MjXG）（9）

式中，G为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的止

数。

（4）选择操作。将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体

性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要

根据前代群体的N个个体的适应度，采用赌轮选择法［4］产生。具体地说.就是苜先计算上代

群体中所有个体适应度的总和（EFi）,再计算每个个体的适应度所占的比例（Fi/XFi）,以

此作为其被选择的概率。这样选择方法既可保证最优个体生存至下一代，又能保证适应度较

大的个体以较大的机会进入下一代。

（5）交叉操作。对通过选择操作产生的新群体，除排在第一位的最优个体外，另NT

个个体要按交叉概率Pc进行配对交叉重组。木文采用了一种类似0X法［2］的交叉方法，现

举例说明之：①随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：

A=4785631921,B=83146911257：②将B的交配区域加到A的前面，A的交配区域加到B的

前面，得：A'=4691|478563921,B'=8563834691257；③在A'、B'中自交配区域后依次

删除与交配区相同的自然数,得到最终的两个体为：A”=469178532,B”=856349127。与其

他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果，这

对维持群体的多样化特性有一定的作用。

（6）变异操作。由于在选择机制中采用了保留最佳样本的方式，为保持群体内个体的

多样化，本文采用了连续多次对换的变异技术，使个体在排列I顺序上的有较大变化。变异操

作是以概率Pm发生的，一旦变异操作发生，则用随机方法产生交换次数J,对所需变异操作

的个体的基因进行J次对换（对换基因的位置也是随机产生的）。

根据上述遗传算法参考编制的C语言程序，并具体设一个某配送中心使用2辆汽车对8个需

求点进行送货的物流配送路在优化问题实例进行了实验计算。设汽车的载重量为8t,每次配

送的最大行驶距离为40km、配送中心与各需求点之间、各需求点相互之间的距离及各需求

点的需求量见表lo

表1配送中心与需求点之间的距离及各需求点的需求量表

dij(km)j012345678

00467.592()10168

1406.541057.51110

266.507.510107.57.57.5

37.547.501059915

491010100107.57.510

5205105100797.5

6107.57.597.570710

716117.597.597010

88107.515107.510100

qi(t)—12121422

根据上述实例的特点，在实验计兜中采用了以下参数：群体规模取20.交叉概率和变异概率

分别取095和0.05,进化代数取50,变异时基因换位次数取5,对不可行路径的惩罚权重取

100km。对上述问题，利用计算机随机求解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世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传和法的

研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体

系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域

正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物

的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会

发挥一定的作用，五是遗传算法和进化规划(EvolutionProgramming,EP)以及进化

策略(EvolutionStrategy,ES)等进化计算理论日益结合。EP和ES几乎是和遗传算

法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能

计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较

研究和彼此结合的探讨正形成热点。

1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子(Adjacency

basedcrossover),这个算子是特别针对用序号表示基因的个体的交叉，并将其应用

到TSP问题中，通过实验对其进行了验证。

D.H.Ackley等提出了随即迭代遗传爬山法(StochasticIteratedGenetic

Hill-climbing,SIGH)采用了一种复杂的概率