（交通运输规划与管理专业论文）基于免疫算法的物流配送VRP研究.pdf

摘要 物流配送的车辆路径安排问题( v e h i c l er o u t i n gp r o b l e m ， v r p ) 一真是优 化科学和现代物流领域研究中的一个前沿和热点问题，其理论涉及很多学科，很 多实际问题的理论抽象都可归结为这一类问题，已引起很多学者的极大关注。 本文仅研究装货和卸货一体化的物流配送v r p 问题，将免疫算法( i m m u n e a 1 9 0 r i t h m ，i a ) 应用到问题优化中，进行了寻优搜索计算。 本文的工作主要有以下几个方面： 首先概述了物流配送v r p 的相关理论，分析了一般v r p 问题研究的复杂性。 其次对免疫优化理论作以介绍，通过比较分析，得出免疫算法比遗传算法具 有更好的全局搜索能力和更好的收敛性。 然后建立v r p 问题的数学模型，将装货和卸货同时考虑在问题研究内。 最后将免疫算法应用到物流配送的v r p 研究中，通过算法在具体实例中的应 用，实现了一种基于免疫算法来解决v r p 的寻优搜索过程，得到较好的测试结果。 结果证明免疫算法在收敛速度和优化结果上确实优于遗传算法和一般算法。 关键宇：物流配送；车辆路径安排问题；免疫算法 r e s e a r c ho nl o g i s t i c sd i s t r i b u t i o nv r pb a s e do ni m m u n e a l g o r i t h m a b s t r a c t v r ph a sa l w a y sb e e naf r o n ta n dh o tp r o b l e mi nm o d e r nl o g i s t i c sa n ds c i e n c e t h e v r p t h e o r yd e a l sw i t ht h ek n o w l e d g ef o r mm a n yb r a n c h e s m a n yp r o b l e m si nf a c tc a n b ei n d u c e di n t ot h i s i ti sa t t r a c t i n gt h ee y e so ft h em a n yl e a r n e r s t h i sa r t i c l eo n l yd e a l sw i t ht h ev r po fc o m b i n e dp i c ku pa n dd e l i v e r y t h e i m m u n ea l g o r i t h m ( t a ) i sa p p l i e do no p t i m i z i n gt h ep r o b l e m a n dt h es e e k i n ga n d c a l c u l a t i n g a r ec a r r i e do u t t h em a i nw o r kid oi nt h ep a p e ri sa sf o l l o w s ： f i r s t ，t h ec o o r r e s p o n d i n gt h e o r yo fl o g i s t i c sd i s t r i b u t i o na n dv r pi ss u m m a r i z e d a n dt h ec o m p l e x i t yo fr e s e a r c h i n gt h i sk i n do fp r o b l e mi sa n a l y z e d s e c o n d ，t h ei at h e o r yi si n t r o d u c e d a n db yc o m p a r e ，i tc a nb ec o n c l u d e dt h a tt h e i ah a sb e t t e rc o m p l e t es e e k i n ga n da s t r i n g e n c yc a p a c i t yt h e nt h eg e n ea l g o r i t h m t h e ni nt h ep a p e r , t h ev r pm a t h e m a t i c a lm o d e li ss e tu p i tc o n s i d e r sb o t hp i c ku p a n dd e l i v e r y a tl a s t ，t h ei ai sa p p l i e do nt h ev r po fl o g i s t i c sd i s t r i b u t i o n b yu s i n gi ti nt h e c o n c r e t ee x a m p l e ，w er e a l i z er e s o l v i n gt h ev r pb a s e do nt h ei a w es u c c e e di ng a i n i n g f i n er e s u l t s + a n dt h ec o n c l u s i o np r o v e st h a tt h ei ai sr a t h e rb e t t e rt h a nt h eg aa n da n y o t h e ra l g o r i t h ma tt h ea s t r i n g i n gs p e e da n d o p t i m i z i n gr e s u l t s k e yw o r d s ：l o g j i s t i e sd i s t r i b u t i o n ；v r p ；i m m u n ea l g o r i t h m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士，硕士学位论文：墨王鱼痤簋壁的物逋壁鲎迅班筮：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开 发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：絮乃? 狮多年月堋 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密口( 请在以上方框内打“”) 论文作者虢东南导师魏诺痨 日期：谚6 年弓月? 8 一日 第1 章引言 1 1 研究目的及意义 随着全球化信息网络和全球化市场技术变革的加快，全球物流市场上的竞争 日趋激烈。进入2 0 世纪9 0 年代以来，我国的经济一直处于快速发展的阶段，技 术进步和需求的多样化使得产品寿命周期不断缩短，我国物流企业面临着缩短交 货期、降低物流成本以及改进物流服务的压力。对于物流配送企业来说，提高运 输效率和有效地使用载运工具具有十分重要的实际意义。因此，对物流配送的优 化问题进行广泛和深入研究，并建立相应理论和方法，对改进运输管理水平、促 进物流配送和交通运输生产组织的发展具有重要作用。 物流配送问题的核心问题是车辆路径安排问题，要求确定哪些货物该由哪些 车辆、按何顺序、在何时运送，在满足诸如车辆装载能力和运送时间约束等条件 下，使得总费用最小。 本文引入免疫算法这种拟生态学的优化计算方法对v r p 问题进行研究。这种 自适应免疫算法可用于求解复杂优化问题，并能够随着抗体培养周期的延伸，自 适应地从免疫系统中学习，是求解v r p 问题的有效方法。免疫算法对遗传算法的 性能进行了一定的改进和提高，能够很好地保持抗体的多样性，因而能很好地防 止“早熟”现象。本文在后面章节中验证了这一算法的求解精度和收敛性都很好， 因此研究免疫算法及其理论并将其应用于物流配送线路选择问题上具有很好的实 际应用前景，它一方面对提高物流配送效率具有重要的指导意义，另一方面又可 以促进运筹学等学科的理论发展，值得进一步探索。 1 2 文献综述 1 2 1v r p 研究动态 国内外相关领域对物流配送v r p 问题的研究始于5 0 年代，在理论研究和实际 应用两方面都已取得了非常显著的成果。 国外对物流配送v r p 问题做了比较深入的研究，在1 9 8 3 年时b o d i n 、6 0 l d e n 等人在他们文章的文献综述中就列举了7 0 0 余篇相关研究文献。这些在 c h r i s t o f i d e s ( 1 9 8 5 ) 、g o l d e n 和a s s a d ( 1 9 9 8 ) 编辑的论文集以及a l t i n k e r n e r 和g a r i s h ( 1 9 9 1 ) 、l a p o r t e ( 1 9 9 2 ) 、s a l h i ( 1 9 9 3 ) 等的综述文章中也都进行 了详细的阐述。该领域的代表人物有o d i n ，c h r i s t n f i d e s ，g o l d e n ，h s s a d ，b a l l ， l a p o r t e ，r i n n o o yk a n ，d e s r o s i e r s 和d e s r o c h e r s 等人。 国内对物流配送v r p 的研究，首推西南交通大学郭耀煌教授和他的学生。1 9 9 4 年，郭耀煌同李军出版了国内第一部v r p 方面的专著车辆优化调度。2 0 0 1 年， 他们又在车辆优化调度的基础上出版了物流配送车辆优化调度理论与方法 一书，对物流配送v r p 的基本理论及基本问题作了初步介绍，对不同类型的车辆 优化调度问题以及求解问题的优化算法( 如c - w 节约启发式算法、遗传算法等) 进行了一定的研究，取得了一定的研究成果。2 0 0 3 年，郭耀煌教授的另一学生谢 秉磊在其博士论文中对随机车辆调度问题进行了初步研究。 122 优化算法研究综述 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。 优化技术作为科学的一个重要分支，一直受到人们的广泛重视，并在诸多工程领 域中得到迅速推广和应用。目前国内外用于解决v r p 问题的现代数学方法大致上 分为以下两大类： 1 精确式算法 精确式算法一般运用线性规划和非线性规划等数学规划技术求得问题的最优 解。主要有：分支定界法( b r a n c ha n db o u n da p p r o a c h ) ；割平面法( c u t t i n gp l a n e s a p p r o a c h ) ：网络流算法( n e t w o r kf l o wa p p o r a c h ) ；动态规划方法( d y n a m i c p r o g r a m m i n ga p p r o a c h ) 等。精确式算法随着运输系统的复杂性和调度目标的增 加，其计算量呈指数递增，这使得获取整个系统的精确最优解越来越困难，而用 计算机求解大型优化问题的时间和费用又太大，因此，此类优化方法和算法现在 一般仅用于求解运输调度的局部优化问题。本文对此类算法不做详细的介绍。 2 。启发式算法 分为经典启发式算法和通用启发式算法。大部分经典启发式算法是在 1 9 6 0 1 9 9 0 年闻提出的，大致上可分为三种类型：构解法、两阶段法和解改进法， 这些方法能在解空间中进行非常有限的搜索，一般能在较短的时间内求出满意解a 通用启发式算法是在1 9 9 0 年以后出现和发展的，强调对解空间进行全局搜索，特 通用启发式算法是在1 9 9 0 年以后出现和发展的，强调对解空间进行全局搜索，特 2 别是对富有希望的区域进行纵深试探。这类方法一般将高级的邻域搜索技术、记 忆结构以及解的重组结合起来，所求出的解的质量比经典启发式算法要高得多， 但所付出的代价是较长的运算时间。主要有构解法、两阶段法、解改进法、模拟 退火( s a ) 、禁忌搜索( t s ) 、蚁群算法( a s ) 、人工神经网络、遗传算法( g a ) 和免疫 算法( i a ) 。本文只对免疫算法的研究综述进行详细说明。 免疫算法是以生物免疫系统理论为基础的，在抽取和反映人工免疫理论的基 础上结合遗传算法而提出的用于求解组合搜索和优化问题的计算技术。 国外对于免疫算法的研究源于美国新墨西哥大学s f o r r e s t 和洛斯邓可拉莫 斯实验室的a p e r e l s o d 首先提出的免疫系统遗传建模方法。1 9 9 7 年，c h u n 等基 于体细胞理论和免疫网络理论提出了基本免疫算法，将抗原作为目标函数、抗体 作为解答、抗原和抗体之间的亲和力作为解答的联合强度。同年，t a z a w a 等提出 了一种结合免疫系统与遗传特性的免疫遗传算法，用于超大规模集成电路的设计， 其中主要利用了小生境技术。1 。1 9 9 8 年，j a n g - s u n g c h u n 等基于信息熵理论对免疫 优化算法进行设计，算法中变异概率提高了5 倍。k a z u y u k i 等将免疫优化算法应 用于解决自适应调度问题，抗体亲和力的计算使用了等位基因和信息熵，同时还 使用了传统遗传算法的交叉和变异算子生成新个体以保持抗体的多样性“1 。1 9 9 9 年，s h y h - j i e r 利用平均信息熵计算了抗体亲和力，再结合简单遗传算法的交叉和 变异算子设计了免疫算法优化燃料调配和热量生成问题。1 。2 0 0 0 年，g a o 等提出一 种基于免疫多样性的选择算子实验结果证明改进算法是有效的“1 。 在国内，最早开展免疫优化算法研究的是西安电子科技大学的王雷、焦李成 等人1 9 9 8 年设计的一种模拟自我免疫机制( s e lf - i m m u n i t y ) 的免疫遗传算法，应 用于求解t s p 问题，其中加入了最优保持操作”。1 9 9 9 年王煦法等叫模拟免疫行为 中的抗原识别、抗原记忆和抗体的抑止、促进等免疫行为设计出相应的免疫模块， 从而构成完整的免疫遗传算法并应用于t s p 优化，实验研究表明：该方法提高了 全局和局部搜索能力，并能够改善未成熟收敛的缺陷。同年，周伟良等提出了基 于浓度控制的免疫遗传算法并应用于b p 网络的辅助设计和解决x o r 问题。2 0 0 0 年， 刘克胜等模拟免疫行为中的浓度限制现象设计了融合熵以及抗体亲和力的免疫遗 传算法。 目前，优化领域中应用的免疫优化算法主要有以下几种： 基于克隆选择原理的免疫优化算法”1 ，这种算法利用免疫系统克隆选择的机 制来实现优秀抗体的扩展和增生，并利用了免疫系统中的记忆机制保证了算法能 够最终收敛到全局最优解； 基于免疫系统的抗体浓度调节原理的免疫优化算法睁”3 ，这种算法利用抗体 多样性保持机制改进传统的遗传算法，提高了算法的群体多样性，能有效地抑制 早熟现象，具有较好的全局收敛性； 基于免疫响应的免疫优化算法“”，这种算法引入了免疫记忆和抗体多样性 等免疫特性： 基于免疫抗体记忆的免疫优化算法”，这种算法将随机搜索过程中的局部 搜索和全局搜索采用不同的促进和抑制策略，有效保证了算法的收敛速度。 1 。3 本文研究内容及结构安排 文本主要研究现代物流配送的路径优化选择问题，同时对免疫算法理论在此 类问题中的应用进行了初步探索。文章通过定性和定量分析，对免疫算法给予了 肯定，并通过实例计算证明了其在解决v r p 实际问题中的有效性和可行性。 本文各章节的主要内容安排如下： 第2 章首先分别对路径选择问题中的t s p 和v r p 进行阐述和分析，然后分析 并总结了v r p 问题求解的复杂性，通过对v r p 实例的求解计算最及计算时间初步 估算，认为需求点数量较大的v r p 问题求解十分困难。 第3 章从生物学角度引入免疫算法的概念，对免疫算法的理论进行了叙述和 说明。本章通过将免疫算法与遗传算法作比较，分析得出免疫算法在以下方面优 于遗传算法：更能保持抗体的多样性、更能发现多优化解的机会而不会落入局部 优化解、搜索期望优化解速度更快。 第4 章首先建立v r p 问题的混合整数规划模型，然后通过一个具体实例将免 疫算法应用于物流配送v r p 研究中，并解出最优解，结果比较令人满意。 第5 章结束语，得出全文的结论，阐述了后续研究工作， 4 第2 章物流配送v r p 问题 2 i t s p 描述 旅行商问题( t s p ，t r a v e l i n gs a l e s m a np r o b l e m ) 一般可以描述如下：个 旅行者从出发地出发，经过所有要到达的城市后，返回到出发地。要求合理安排 其旅行路线，使得总旅行距离( 或旅行费用、旅行时间等) 最短。在实际应用中， t s p 可以分为一般t s p 和m t s p ( 多重旅行商问题) 两种情况。 2 1 1 一般t s p 般t s p 指一个旅行商访问所有城市。这里设城市0 为旅行商出发城市，需 要访问的f 个城市编号为l ，f 。 g i 旷，a ，c 】 其中，点集v 8 2 ，叼，表示旅行商需要经过的地点。 弧集a 一 ( f ，j ) i f ，j o ，1 ，z ，i 一，) 】表示旅行商可能走过的线路段集合。 费用矩阵c - c # i ( i ，j ) e a ，c 表示旅行商经过对应弧段( f ，j ) 所花的费用，如 时间、距离、花费等。 求解t s p 即要求在加权图g 中找到总费用最小的哈密尔顿( h a m i l t o n ) 回路。 f l 若弧( f ，j ) 在线路上 嘞1 仉否则 则得到以下模型： 幽扣轰羲。幽 轰z 目“，钏，1 ， 羲x # “一1 0 , 1 , - - ，2 x 一( 工目) s x = 0 或1 s 其中，c = m ( f - l j ) ，s 为支路消去约束( s u b t o u r b r e a k i n g 约束) ，即 消去构成不完整线路的解，如 图2 1 不完整的线路图 f i 9 2 1t h en o n c o m p l e t er o u t i n g 两条支路均满足分配约束，但没有构成一条完整的线路，因此不是v r p 问题 的解。 s 一般由几种表示法： ( d s - 似一1 荟磊铲l q c o 1 ， ? 该式说明，点的某一子集必须同解中其他点集相连。上图中 q 一 l 2 ，3 ) ，qt 4 5 ，6 ，则可以消去两条支路。 s - 慨i 善荟蜊铷c o 1 ，册， 该式说明，任一子集r 上的弧都不产生循环，因为点集r 上的循环至少含有陋i 条弧。上图中，r1 9 , 2 ，3 ，则可以排除产生循环支路1 2 _ - 3 1 。 2 1 2m t s p m t s p 是一般旅行商问题的推广和深化，也称为无容量约束的v s p 问题。m t s p 是指m 个旅行商访问所有城市，要求每个城市至少访问次，应如何安排旅行路 线，使m 个旅行商的总旅行费用最少。 将m t s p 通过附加虚拟城市的方法转化成f + m 个结点的单t s p ，方法如下： 将源点0 复制小1 个，m 个源点编号为0 ，f + 1 ，f + 1 一1 ，每一个同源 点0 样与其它点相连，而m 个源点互相不相连，这样在结点集 o ，1 ，f ，f + l ，+ m 一1 上，可以得到t s p 线路然后各源点合并成一个点。 这样t s p 线路就分解成m 个分线路。 f 1 ，弧( f ，) 在线路上 舭口2 1 0 ，否则 模型表示如下： 曲扣磊荟哪n i 酗以。枷，1 ，一 i r 5 j 善x 。2 l 1 lo ，1 ，r i x 一。或1 ，i ，j 一0 , 1 ，r 【 其中：r - m + f i ；d 4 表示增广费用，给。f 增加m - 1 行和m 一1 列，每一新 的行或列是c 。的最后以行或列的复制，增广矩阵的其他元素无穷大。 2 2v r p 描述 冲是对进行物流配送的车辆进行优化调度。该问题一般可以描述为：对一 系列的装货点和卸货点，组织适当的行车路线，使得车辆有序的通过这些结点， 并且在满足一定的约束条件( 如货物需求量、发送量、交发货时间、车辆最大行 驶里程、车辆容量限制等) 下，达到一定的目标( 如路程最短、费用最少、占用 车辆数最少等) 。 2 2 1v r p 线路的类型 物流配送y r p 有多种可供选择的行驶线路，运输工具按照不同的行驶线路完 成同样的物流配送任务时，利用车辆的情况以及物流配送效率、成本可能不同。 一般有如下几种基本线路： ( 1 ) 环形线路 配送车辆在由若干物流结点组成的封闭回路上做连续的单向运输。 ( 2 ) 往复式线路 由一个供应点对一个客户的专门送货。从优化的角度看，选择该线路的基本 条件是客户的需求量接近或者大于可用车辆的额定载重量，需专门派一辆或者多 辆车一次或多次送货。根据载运情况，配送车辆最好在回程中载货运输，这样里 程利用率比较大，比较经济。 ( 3 ) 汇集式线路 配送车辆分布于配送线路上的各个物流结点间，完成相应的装卸配送任务。 而且每一运次的货物装卸量均小于额定载重量，沿路装货或卸货，直到车辆装满 货物或者卸空货物，然后再返回到出发点。汇集式行驶线路可以分为直线型的和 环线型两种，实质上是往复式行驶线路的变形。 ( 4 ) 星型线路 以一个物流结点为中心，向其周围多个方向上的一个或多个结点行驶而形成 的辐射状的线路。如果就一个方向看，可以简化看成一个往复式线路，如果就一 个局部来看，又可以看成一个环形行驶线路；如果将各结点更广泛的连通，车辆 在多个结点之问运输则从整体上又形成了一个较复杂的汇集式线路。 2 2 2v r p 问题的分类 v r p 是t s p 的特别闯题，国内外各学科的学者从不同角度、不同方向对v r p 进行了研究，并按不同的标准对v r p 进行了分类，综合起来可分为以下几种： ( 1 ) 按任务目标区分，有纯装问题或纯卸问题( p u r ep i c ku po rp u r e d e l i v e r y ) 及装卸混合问题( c o m b i n e dp i c ku pa n dd e l i v e r y ) 。纯装问题或纯 卸问题是指车辆在所有任务点只装货或只卸货，即集货或送货问题；装卸混合问 题是指每项任务有不同的装货点和卸货点，即集货、送货一体化问题。 ( 2 ) 按车辆载货状况区分，有满载问题和非满载问题。满载问题是指货运量 不小于车辆容量时，完成一项任务需要的车辆数大于1 ；而非满载问题是指货运量 小于车辆容量的问题，一辆车可完成多项任务。 ( 3 ) 按车场( 或货场、配送中心等) 数目区分，有单车场问题和多车场问题。 ( 4 ) 按车辆类型区分，有单车型问题( 即所有车辆类型和容量相同) 和多车 型问题( 执行任务的各车辆的类型和容量不完全相同) 。 ( 5 ) 按车辆对车场的所属关系区分，有车辆开放问题( 车辆可以不返回其发 车场) 和车辆封闭问题( 车辆必须返回其发车场) 。 ( 6 ) 按照完成各项任务是否受时间限制，分为无时间限制的v r p 问题和带时 间窗的v r p 问题。其中时间窗又可分为硬时间窗、软时间窗和混合时间窗。硬时 间窗是指任务必须在给定的时间范围内完成，否则得到的解视为不可行解；软时 间窗指如果任务不能在给定的时间范围内完成，则给予一定的惩罚；混合时间窗 是指：配送车辆如果能在最佳时段【e ，z 】内将货物送至客户手中，则不受处罚：若 在陋，e ) 或( f ，b 】时段内才送达，则顾客的满意度降低，转化为惩罚函数：而且顾客 不接受上述两个时段以外时间即( 一。，口) 或p ，* ) 的服务。如图所示： 心) 口e fb t 图2 2 混合时间窗概念 f i 9 2 2t h ec o n c e p t i o no fm i x e dt i m ew i n d o w 2 2 2v r p 的一般模型表示 对于一般情况下的v r p 规划，设配送中心的车辆数为k ，第k 辆车的载重量 为q 。，需求点个数为厅，需求点f 的需求量为q 。，从结点f 到，的运距为d 口，且没 有复杂约束( 即纯送货、非满载、单车场、车辆封闭、无时间窗要求) ，则一般 模型可以表示为： 血n ，。薹【薹。一o o 】 9 差口* jq t 0s 以 n n k n r i 一 i r “ 1 ，2 ，1 ) ，i 一1 ，2 ，z 女) r t 。nr t ：ia ，vk 1 k2 巾 ) i l 。, ，n 其k 他- 1 其中， n 。为第k 辆车配送的需求点数( n 。= 0 时表示第k 辆车未被使用) ， r 。是第k 辆车的行驶路径，元素k 表示结点k 在路径r 。中的顺序为i 。 o5 “( 。+ 1 ) 20 表示配送中一t l , 。 2 3 问题分析 v r p 问题一直是学术界的n p - 难题，虽然一般来说给定约束条件，具体问题的 解空间有限( 从原则上可以找出问题的最优解的) ，但是此类问题的求解非常复 杂，特别是随着配送规模的增加，即配送结点的增加，计算量呈指数增长，求解 过程十分复杂，耗时大。 下面举个具体的例子来说明v r p 求解的难度之大。例如，在结点和车辆数较 少的情况中，车辆优化调度问题很容易求解。设现在给定的4 个城市分别为a ，b ， c 和d ，各城市之间的距离为已知数。从图2 4 中不难看出，可供选择的线路共有 6 条，从中很快可以选出一条总距离最短的线路。 图2 34 个城市的交通图 r i 9 2 3t h et r a f f i cc h a r to f4c i t i e s l o 可以通过一个组合的状态空间来表示所有的组合： 路径a b c d a ，总距离；1 3 路径a c b d a ，总距离：1 9 路径a d c b a ，总距离：1 3 路径a b d c a ，总距离：1 4 路径a c d b a ，总距离：1 4 路径a d b c a ，总距离：1 9 图2 4 组合路径图 f i 9 2 4c h a r to f a s s e m b l yr o u t e 由此推算，设城市数目为肛，那么组合路径数量则为伽一”! 。很显然，当城市 数目较少时我们不难找到最短距离的路径，但是随着城市数目的增大，组合线路 数量将成指数级数规律急剧增长，以至达到无法计算的程度，成为所谓的“组合 爆炸”问题。假设一- 2 0 ，其可行解的个数则为( 2 0 - 1 ) ! - 1 2 1 6 x 1 0 17 。如果采用枚 举法对其进行计算，假设某计算机运算速度为每秒一亿次，则该计算机解出结果 需要约3 8 5 6 年时间。因此，对v r p 问题的研究是一项难度较大的工作。 第3 章免疫算法理论 这些年，随着人类基因工程技术的发展，人们越来越注重生物系统诸多特性 在组合优化中的应用。随着计算机技术和网络技术的飞速发展，以计算智能和软 计算为代表的智能计算技术也迅速发展，其中有较早的人工神经网络、模糊系统、 进化计算，还有近几年刚刚发展起来的d n a 计算和人工免疫系统计算，与模式识 别和组合优化等领域的发展相得益彰。这些技术都是模拟生物体处理信息过程而 发展出来的计算方法，已经引起世界各地研究人员的极大关注。 人工免疫系统在显示其学习性、适应性、记忆机制以及高效率并行搜索等特 点时，给人们提供了丰富的灵感和启示，从人体免疫系统抽象出优化计算方法已 经引起许多不同领域研究人员的广泛兴趣。目前，免疫算法能够在物流配送路径 等优化研究应用中表现出较卓越的性能和效率。 3 1 免疫算法的生物学基础 3 1 免疫系统的形态空问 为了定量地描述免疫细胞分子和抗原之间的相互作用，p e r e l s o n 和o s t e r 于 1 9 7 9 年提出形态空间( s h a p e s p a c e ) 的模型概念。形态空间是指受体和与之结合 的分子之间的结合程度。假设它是l 维形态空间，如图所示，在形态空间s 内有一 个体积为y 的区域，其中含有抗体( 用来表示) 和抗原( 用表示) 的形状互补 区域。假设一个抗体能识别所有在其周围体积范围内的互补的抗原。 如果有一个大小为的指令系统，则该形态空间包含个点。这些点都位于 一个体积为y 的空间内，空间体积受长度、宽度、电荷等条件限制而有限。如果 抗体和抗原不能恰好互补，但仍然可以结合，此时亲和力较低。假设每一个抗体 能够特异地与所有抗甄在其周围较小的区域内相互作用，用表示作用半径，该区 域称为识别区，用旷表示。每一个抗体能够识别在识别区内的所有抗原。 7 7 国 夕 图3 1 免疫系统的形态空间 f i 9 3 1t h es h a p es p a c eo fi m m u n es y s t e m 抗体抗原表示法用于计算它们相互作用( 互补) 程度的距离测量。利用数学概 念定义一个分子m 的泛化形态，用一个实数坐标集合m 一( m 。，m ：，小。) 表示抗体 或抗原，看做l 维实数空间中的一个点，m s r ，其中s 表示形态空间，l 表示其维数。那么一个抗体和一个抗原之间的亲和力与它们之间距离有关，通过 两个字符串( 或向量) 之间的距离测量来估测抗体与抗原之间的亲和力。 3 1 2 免疫应答 免疫系统有两种免疫应答类型：一种是遇到病原体后首先并迅速起防卫作用 的固有性免疫应答；另一种是适应性免疫应答。前者在感染早期执行防卫功能， 后者是继固有性免疫应答之后发挥效应的，对最终清除病原体、促进疾病治愈及 防止再感染起主导作用。免疫算法主要是利用了适应性免疫应答的应答原理，因 此这里只对适应性免疫应答作以简介。 适应性免疫应答又分为两种类型：初次免疫应答和二次免疫应答。 初次免疫应答发生在免疫系统遭遇某种瘸原体第一次入侵时，此时免疫系统 产生大量抗体，帮助清除体内抗原。当一种抗原侵入免疫系统后，系统有一个产 生抗体的初始化过程。但是几天以后，抗体的浓度水平开始下降，直到再次遇到 抗原。自适应免疫系统能够学习和记忆特异种类的抗原。初次应答学习过程很慢， 发生在初次感染的前几天，要用几周的时间清除感染。 二次免疫应答是指在初次免疫应答后，免疫系统首次遭遇异物并将之清除体 外后，免疫系统中仍保留一定数量的免疫记忆细胞( i m m u n em e m o r yc e l l ) ，在 免疫系统再次遭遇类似抗原后，不再重新产生抗体，原免疫记忆细胞能快速反应 并清除抗原。 抗体 新抗原前面遇到过的抗原 图3 2 免疫应答过程 f i 9 3 2t h ec o u r s eo fi m m u n er e s p o n s e 3 1 3 多样性 免疫系统的多样性，本质就是抗体的多样性，即产生尽可能多的抗体对抗千 变万化的抗原。有机体能识别和抵抗各种抗原袭击的原因在于：免疫细胞表面的 受体不是一成不变的，在胚胎初期由于遗传和免疫细胞在增殖中发生基因突变和 重排，形成了免疫细胞的多样性，发挥更广泛的免疫功能。这些细胞不断增殖形 成无性繁殖系。 抗体变异增加与抗体对抗原的亲和力增加有关，假设高频变异机制完全是随 机的，则许多变异破坏对抗原的亲和力。免疫系统克服这个问题的一个方法是， 通过选择性增加高亲和力抗体群体。 1 4 免疫系统的多样性主要靠体细胞高频变异、受体编辑和随机产生新抗体来实 现。 ( 1 ) 体细胞高频变异 b 细胞与抗原结合后被激活，激活后的b 细胞就进入了克隆扩增阶段，在克隆 扩增期间b 细胞将会以极高的频率发生变异，该过程称为细胞高频变异。体细胞 高频变异是克隆扩增期间产生的的重要变异形式，对受体多样性的产生起重要作 用。体细胞高频变异的实质是抗体可变区的d n a 基因片段重新排列，从而改变了 可变区的结构，形成了一种新的抗体。 b 细胞在克隆选择与扩增过程中所进行的体细胞高频变异过程，是变异后的子 代b 细胞增加了具有不简于附带受体结构的抗体决定基，因此就会有不同的抗原 决定基亲和力。新的b 细胞具有与淋巴结构内捕获的抗原决定基发生结合的机会。 如果不结合会将很快凋亡，如果结合成功，则离开淋巴结，分化为浆细胞和记忆b 细胞。 变异的速度积累对于免疫应答的快速成熟时必须的，但是多数变化会导致更 弱。如果一个细胞刚刚采用一种有用的变异，并以同一速度在下一次免疫应答期 间继续变异，则衰弱变化的积累可能引起变异优点的损失。免疫系统为了避免这 种情况的发生，在体细胞高频变异爆发之后，进行克隆选择和扩增，给亲和力提 高了细胞得以呼吸的空间。同时选择机制也可以依靠亲和力来调节高频变异过程， 使具备低亲和力受体的细胞进一步变异，而且具备高亲和力受体的细胞则可以不 激活高频变异。 ( 2 ) 受体编辑 b 淋巴细胞被抗体激活进入了克隆扩增时，b 细胞抗原受体将会发生基因重组， 这个过程成为受体编辑。受体编辑发生时，现有b 细胞上抗体基因片段将会与遗 传基因库中的d n a 记忆片段进行重组，形成新的特异识别抗体，这样产生的子代b 细胞就有可能比父代b 细胞具有与特异抗原更高的亲和力。受体编辑时免疫系统 保持高度多样性的又一重要的机制。当b 细胞抗体经过变异和编辑后对于外部入 侵抗原的亲和力降低时，抗体将无法与抗原结合，这样b 细胞将会死亡，这就是 免疫系统的克隆删除功能。 最近的研究成果表明，在抗原结合部位的形态空间中，受体编辑具有在亲和 力域内避免局部优化的能力，而体细胞高频点变异对搜索局部区域有良好的作用 2 0 - 2 1 1 ( 3 ) 随机生成新抗体 虽然抗体编辑和高频变异能够使免疫系统保持一定的多样性，但一般的生物 免疫系统只同时存在1 0 8 种不同的蛋白质，但是自然界却潜在有1 0 ”种不同的外部 蛋白质或者模式及抗原决定基需要识别，按照数目比较，免疫系统的多样性显然 不够充分区结合每一个可能的抗原决定基。在这种情况下，可能会引起严重的问 题，生物体如何才能识别这些外部病原体呢? 免疫系统能够动态性地解决这个问 题。为了保持免疫系统的高度多样性，骨髓每天都要随机产生大量的新的抗体， 而大量免疫系统原有的没有与抗原结合的抗体将会凋亡，新产生的这些抗体进入 到免疫系统，虽然不一定能结合抗原而最终导致死亡，但是却能够增加并保持免 疫系统醣多样性，以应对那些可能从未碰到过的病原体。 3 1 4 克隆选择和扩增 克隆选择和扩增的基本思想是只有那些能够识别抗原的细胞才进行扩增，只 有这些细胞才能被免疫系统选择并保留下来，而那些不能识别抗原的细胞则不被 选择，也不能进行扩增。b u r n e t 于1 9 5 9 年提出的克隆选择学说。2 1 认为：免疫细胞 是随机形成的多样性的细胞克隆，每一克隆的细胞表达同一特异性的受体，当受 到抗原a g 刺激时，细胞表面受体特异识别并结合抗原以，导致细胞进行克隆扩 增，产生大量后代细胞，合成大量相同特异性抗体。 克隆选择与达尔文变异和自然选择过程类似：克隆竞争结合抗原，亲和力最 高的是最适应的，因此复制最多。 亲和力变异是克隆选择效率与进化的主要决定困素，变异由抗体高频变异实 现，选择由抗体对抗原的竞争实现。 当细胞进行克隆扩增时，它经历一个自我复制超变异随机过程，免疫系统此 时产生广泛抗体指令，从体内清除感染的抗原，并为抵制下次某个时候类似但不 同的感染做好准备。如c 是一个受到抗原刺激的抗体，如果刺激足够大的话，抗 体开始克隆。如图所示，抗体c 分化成许多克隆细胞，每一个克隆细胞受到刺激 1 6 后又开始克隆，这样，增加了免疫系统中清除异物的抗体的数量。抗原的亲和力 刺激了抗体，带有c 标志( 受抗原刺激) 的抗体克隆如图所示。免疫系统通过调 整特殊的变异机制产生抗体分子基因密码变异。通过产生不同的抗体集合，使得 免疫系统在以后可以对抗同样的或者类似的病原体( 抗原) 入侵感染。 3 2 免疫优化算法概述 图3 3 克隆扩增示意图 f i 9 3 3c l o n ee x p a n s i o ns k e t c hm a p 3 2 1 免疫算法与免疫系统的对应 免疫算法是借鉴了免疫系统学习性、适应性以及记忆机制等特点而发展起来 的一种优化组合方法，在使用免疫算法解决优化问题时，各个步骤都与免疫体统 有对应关系。如抗原对应要解决问题数据输入( 如目标、约束) ；抗体对应问题 的解；亲和力对应解的评估等。具体对应关系如下表所列： 表3 1 免疫算法与免疫系统对应关系表 t a b l e 3 1t h er e t a t i o n s h i po fi m m u n ea l g o r i t h ma n di m m u n es y s t e m 免疫系统免疫算法 抗原要解决的问题 抗体最佳解向量 抗原识别问题识别 从记忆细胞产生抗体联想过去的成功解 淋巴细胞分化优良解( 记忆) 的保持 细胞抑制剩余候选解消除 抗体增加( 细胞克隆) 利用免疫算子产生新抗体 3 2 2 免疫算法的基本概念 定义1 染色体( c h r o m o s o m e ) ：表示待求问题的一种解的形式( 位串) 。 定义2 基因( g e n e ) ：构成染色体的最基本单位，主要是指位串中的“位”。 定义3 个体( i n d i v i d u a l ) ：具有某染色体特点或结构的一种特例，如某一 种形式的位串。 定义4 抗原( a n t i g e n ，a g ) ：所有错误的基因。 定义5 疫苗( v a c c i n e ) ：根据求解问题的已知条件得到的可能的最佳个体基 因。 定义6 抗体( a n t i b o d y ，a b ) ：根据疫苗修正某个个体的基因后所得到的新 的个体。其中，根据疫苗修正个体基因的过程即为接种疫苗，其目的是消除抗原 在新个体产生时带来负面影响。 在实际操作中，在合理提取疫苗的基础上，通过接种疫苗和疫苗选择两个操 作步骤完成操作接种疫苗是为了提高适应度，疫苗选择是为了防止群体的退化。 设个体z ，接种疫苗是指按照先验知识来修改x 的某些基因位上的基因或其分 量，使所得个体以较大的概率具有更高的适应度。这一操作应该满足两点：若 个体y 的每一基因位上的信息都是错误的，即每一位码都与最佳个体不同，则对任 一个体x ，x 转移为y 的概率为0 ；若个体x 的每个基因位都是正确的，即x 已 经是最佳个体，则x 以概率1 转移为x 。设群体c ( z ，工：，x 。) ，对c 接 1 8 种疫苗是指在c 中按比例口随即抽取摊。；口托个个体而进行的操作。免疫操作指兔 疫检测，即对接种了疫苗的个体进行检测，若其适应度仍不如父代，说明在交叉、 变异的过程中出现了严重的退化现象。这时该个体将被父代中所对应的个体取代。 3 2 3 免疫算子说明 ( 1 ) 多样化 算法中为了表明群体中抗体的多样性，引入信息熵( i n f o r m a t i o ne n t r o p y ) 的 概念。在免疫算法中一个抗体就用一个位串( b i ts t r i n g ) 来表示。如图所示为n 个抗体( 即位串) ，每个抗体有m 位，每位可供选择的字母表中共有s 个字母： 七，七：，k ，则这个抗体的平均信息熵为： m 日( ) t 古何，( ) j i s 其中，圩( ) = 一p 口l o g p 口，其中，h ，( ) 为这个抗体第j 位的信息熵， p f 是第f 个等位基因( a l l e l e ) 为字母七，( 来自第j 个基因) 的概率。若在第j 个 基因的所有等位基因都是同样性质，则平均信息量等于0 。平均信息量由此可以看 作一种免疫系统中认知多样性的方法。 抗体1 抗体i 抗体n k 1 k 2 k 。 f i 9 3 4t h ec o n c e p t i o no fi n f o r m a t i o ne n t r o v y ( 2 ) 抗体抑制和促进 1 9 采用浓度概念来调节抗体的促进和抑制。在免疫系统中，当一种抗体受到抗 原刺激或其他抗体刺激或抑制肘，这种抗体的数量将发生变化。在群体更新中， 亲和力大的抗体浓度提高，高到一定值就要受到抑制，反之相应提高浓度低的抗 体的产生和选择概率。这与实际免疫系统中的抗体产生的促进和抑制是一致的。 这种机制确保了抗体群体更新的抗体多样性，避免未成熟收敛。 与抗体f 具有最大亲和力的抗体数 q 1 丽蕊甄r 一 ( 3 ) 抗体抗原编码方式 目前一般免疫算法中抗体抗原，即解和问题的编码方式主要有二进制编码、 实数编码和字符编码3 种，少数有灰度编码等。二进制编码因简单实用而得到广 泛应用。编码后亲和力的计算一般是比较抗体抗原字符串之间的异同。根据上述 亲和力计算方法计算。比如e u c l i d e a n 距离1 是每一维中的差的平方和的平方根。 抗体口1 ，口2 ，岛，b 2 之间的e u c l i d e a n 距离是： ；。( 口t b a ) 2 海明距离是抗体抗原中不同位置数的计算。字符编码a b d c c d a d d a 和 a b a c c d a d c a 的海明距离是2 ，因为有两个位置不同。 ( 4 ) 亲和力 免疫系统通过识别在抗原和抗体之间的独特型或者是抗体和抗体之间的独特 型产生多种抗体，结合强度用亲和力估计。 免疫算法中最复杂的计算就是亲和力计算，由于产生于确定克隆类型的抗体 分子独特型是一样的，抗原抗体的亲和力也是抗体之间亲和力的测量。一般计算 亲和力的公式有如下形式： 1 ) t 志 其中， 似g ) 。是抗原和抗体七之间的亲和力。t 。