《免疫优化算法及其在物流配送车辆调度问题上的应用》由会员分享，可在线阅读，更多相关《免疫优化算法及其在物流配送车辆调度问题上的应用（10页珍藏版）》请在金锄头文库上搜索。
1、免疫优化算法及其在物流配送车辆调度问题上的应用杨争争1（上海海洋大学 信息学院 ,上海 200136）摘要：遗传算法是目前最为广泛使用的可以用于优化问题的寻优方法之一。针对其容易陷入 局部极值点等弱点，目前已提出了一些基于免疫概念的优化算法。本文详细讨论多种基于免 疫概念的优化算法，最后给出一个免疫优化算法在物流配送车辆调度问题上应用的例子 关键字：免疫优化算法， 配送车辆调度Abstract: Genetic algorithm is one of the most widely used optimization methods applied to optimization proble
2、ms so far. However, it has such weaknesses as easy to get trapped into local optimal. Several optimal algorithms based on immune system have been proposed. This paper discusses some immune-based optimization algorithms in detail, finally gives an example in vehicle scheduling problem based on immune
3、 algorithm.Keywords: Immune Optimization Algorithm; Vehicle Scheduling ProblemImmune Optimization Algorithm and Application on Vehicle Scheduling ProblemYang Zhengzheng1（Information College, Shanghai Ocean University, Shanghai 200136, China）1. 引言 遗传算法是基于遗传学理论和生物进化论而建立的一类相对完善的算法体系。遗传算法 在群体优化的过程中通过不同的
4、操作算子不断地优化种群，达到寻找最优解或满意解的目 的，尤其适用于非线性优化问题。因而是目前使用最为广泛的一类可以用于优化问题的寻优 方法之一。然而实验和实际应用表明，该类算法仍存在许多不足，例如：对于多目标函数优 化问题，它容易出现过早陷于局部极值点的问题。另一方面，自然生物系统的许多其他机制为进一步的研究提供了依据。生物免疫系统正 满足了这种需求。免疫系统是一个高度分布、高度并行的大规模自适应系统。2. 生物免疫系统概述： 免疫系统对侵入机体的非己成分（如细胞、病毒和各种病原体）以及发生了突变的自身 细胞（如癌细胞）具有精确地识别、适度地应答和有效地排除的能力。免疫系统的功能主要 由免疫细
5、胞完成，免疫细胞主要有淋巴细胞（包括T淋巴细胞、B淋巴细胞）和巨噬细胞。免疫系统可分为先天性免疫系统和适应性免疫系统、先天性免疫系统是生物在种系发育 和进化过程中逐渐建立起来的一系列天然防御功能，其特点是与生俱有，能传给下一代，无 特异性，对各种病原体都有一定的防御功能。适应性免疫系统则是在个体生命过程中慢慢建 立起来的，当免疫系统与某种病原体产生“免疫初次相应”之后，能记住该病原体，当再次 遇到它时，会产生“免疫再次响应”，迅速而有效地消除该病原体从生物信息处理的角度来看，免疫系统具有以下的特征： 多样性多样性是免疫系统的重要特征之一。免疫学的初步研究表明，通过细胞的分裂和分化作 用，体细胞
6、超变异，抗体的可变区与不变区的基因重组等方式，免疫系统可产生大量的不同 抗体来抵御各种抗原从而使免疫抗体库具有丰富的多样性。免疫自我调节免疫系统具有维持免疫平衡的机制，能将免疫响应的强度限定在一定水平上。通过对抗 体的抑制和促进作用，能自我调节产生适当数量的必要抗体。免疫记忆特性产生抗体的小部分细胞会作为长寿的记忆细胞而被保存下来，当再次遇到同类抗原，相 应的记忆细胞会迅速激发而产生大量的抗体。这一特性在医学临床中应用为接种疫苗，将某 些传染病的低活性疫苗注射到未感染者身上，刺激接受者产生抗体，从而产生对此类传染病 的抵抗能力。分布式系统免疫系统是一个典型的分布式系统，由许多局部相互作用的免疫
7、细胞组成来完成对全局 免疫保护功能，并没有一个集中控制中心，因而也具有容错功能，不会象集中控制系统那样 因为控制中心的小失误，造成全局功能的瘫痪。动态适应特性 几百万年以来，免疫系统都在与病原体不断竞争的过程中逐渐进化，这种免疫系统与病 原体的相互适应的过程具有明显的动态特性，两者相互竞争共同进化。多时间尺度进化系统免疫系统的变化包括从只有几毫秒的亚分子事件到几分钟、几年的细胞群体变化，以及 需要无数代才能完成的改变，免疫系统实际上是一个随环境改变而不断完善的多事件尺度优 化系统。3. 免疫优化算法基于生物免疫系统信息处理的机制和特性，人工免疫系统是继人工神经网络和进化计算 之后受自然生物系统
8、启发的又一个新型的生物计算智能系统，它是免疫系统和人工智能技术 结合的产物。目前，已经发展了以下的免疫优化算法3.1 基于免疫自我调节机制的免疫优化算法在遗传算法中，如果根据适应度函数选择出的双亲基因非常接近，那么所产生的后代相 对双亲也必然比较接近，所期待的改善就比较小，这样基因模式的单一性不仅减慢进化历程， 而且可能导致进化停止，过早收敛于局部最优点。抗体多样性是免疫系统的一个重要特性，这种多样性可用来提高遗传算法的全局搜索能 力而不至于陷于局部解。在免疫调节中，那些与抗原亲和力大并且浓度较低的抗体会受到促 进，而与抗原亲和力小或浓度较高的抗体会受到抑制，以此保证抗体的多样性。将这一概念
9、应用到标准的遗传算法中，保持群里多样性，改善未成熟收敛，提高遗传算法的性能。个体 浓度越小，选择概率越大，然而个体浓度越大，则选择概率越小。这样，在保持高适应度个 体的同时，进一步确保个体多样性，能避免早熟现象。 这种类型的免疫优化算法从提高种 群的多样性角度确保收敛到最优点。3.2 基于免疫响应的免疫优化算法这类免疫优化算法是从体细胞理论和免疫网络理论中得到启发，实现了类似于免疫系统 的自我调节功能和生成不同抗体的功能。具有以下特点它在记忆单元基础上运行，对于曾经出现过的抗原，免疫算法产生相应抗体的速度比以前更快，提高了算法的总体搜索能力，确保了快速收敛于全局最优解 它有计算亲和力的程序，体
10、现了抗体的多样性 它通过促进或抑制抗体的产生，体现了免疫反应的自我调节功能。图一 基于免疫响应的免疫优化算法框图3.3 基于疫苗接种的免疫优化算法 疫苗接种时免疫记忆临床应用的一个重要方面，疫苗的预防免疫已在世界范围内消灭了 天花、麻疹、小儿麻痹等重大流行病，这是在对这些流行病病毒的充分了解的基础上，研制 出疫苗来有针对性地防止这些流行病。将这一免疫概念用于遗传算法，有效地利用求解问题 的一些基本的、显而易见的特征信息或知识、提取“疫苗”，使问题求解更具有针对性。在标准的遗传算法中引入免疫概念，有效地利用问题的先验知识，提出了基于疫苗接种 的免疫优化算法，在保留原算法的优良特性的前提下，引入了
11、一个新的算子免疫算子， 有选择、有目的地利用待求问题中的一些特征信息或知识，提取“疫苗”来抑制其优化过程 中出现的退还现象。在进化选择过程中，通过“疫苗接种”和“免疫选择”来指导搜索过程， 获得更好的优化性能。初始化抽収疫苗适应度计算交叉和变异I I挂种k苗I占免疫算子郡体更新图二 基于疫苗接种的免疫优化算法框图免疫算子的关键是合理提取疫苗。一般说来，选取疫苗时既可以根据问题的特征信息来 制作免疫疫苗，也可以在具体分析的基础上，考虑降低原问题的规模，增设一些局部条件来 简化问题。其实这是对求解的问题先验知识充分了解之后，提取合理疫苗，使算法更具有针 对性而换取计算时间的节省。3.4 基于免疫抗
12、体记忆的免疫优化算法在适应性免疫调节过程中，对特殊抗体的记忆起着重要作用。基于免疫抗体记忆的免疫 优化算法是对传统GA的改进，与GA相比，增加了两个新算子：一个是记忆细胞，一个是 抑制细胞。这两种算子都是对重要抗体的记忆，用于全局搜索过程中促进优良个体的搜索， 而抑制细胞则是对高浓度抗体的记忆，在局部搜索过程中抑制相似解的搜索。算法框图如图 所示：开始GA!*将从仃娠人浓度 的抗体记忆丸 -节抑制細胞计算这 髙亲和力抗体Ki机产主新的抗体群将这嫌体记忆到 个记忆细腔返冋一盘搜索 （将阙值降为 皿来世D从这抗体中产 化一个具有岛度 和似性的新靜体抑制和似抗体的搜遥转向喝册搜囁f堆加1阚值抑制细胞
13、t再次记忆）记忆鲫胞 初味记忆丿图二 基于免疫抗体记忆的免疫优化算法框图3.5 免疫优化算法小结上述几种免疫优化算法都是针对传统遗传算法存在的问题，如局部搜索能力差，存在未 成熟收敛和随机漫游等现象，从而导致算法的收敛性能差，需要很长时间才能找到最优解， 结合不同的免疫信息处理机制发展而来第一种方法是利用抗体多样性保持机制，改进传统的遗传算法，提高了算法的群里多样 性，能有效地抑制早熟现象，使免疫遗传算法具有较好地全局收敛性；第二种方法引入了免 疫记忆和抗体多样性等免疫特性；第三种方法在传统的GA中引入疫苗接种的概念，能充分 利用问题的先验知识，改善算法的性能，在优化问题中获得了很好的效果；第
14、四种方法则将 随机搜索过程中的局部搜索和全局搜索采用不同的促进和抑制策略，有效保证了算法的收敛 速度。4. 车辆调度问题概述：车辆调度问题（VSP）主要探讨组织的行车路线，能否使车辆在满足一定的约束条件下， 有序地通过一系列装货点或卸货点，达到诸如路程最短，费用最小，耗费时间尽量少等目的。 物流配送的路径优化问题是指从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆车的载重量一定，要求合理安排汽车路线，使总运距最短或总运费最低， 并满足以下条件：（1）每条配送路径上各需求点的需求量之和不超过汽车载重量；（2）每条 配送路径的长度不超过汽车一次配送的最大行驶距离；（3）每个
15、需求点的需求不许满足，且 只能由一辆汽车送货。5. 用免疫优化算法求解车辆调度问题5.1 抗体产生VSP 问题用二进制处理具有先天性不足，因此抗体采用自然数编码。一条行驶路线可 形成一个长度为n的抗体，如当n=6时，有抗体（2, 4, 3, 1, 6, 5）。抗体的编码表示可 理解为：车辆从车场0出发，经过任务2， 4， 3， 1， 6， 5后，回到车场0，形成一条路线。 对于车辆数,如有两辆车,则最好存在2条配送路径,每条配送路径都始于配送中心。为了 在编码中反映车辆配送的路径,采用了增加2-1=1个虚拟配送中心的方法,用自然数9表示。 于是1, 2, 9 个自然数的互不重复的排列就表示着相应的配送方案。如抗体246891357 表示配送路径的方案为：路径1（024680）；路径 2（013570）。5.2 初始抗体的产生按照上述的编码方式，随机产生n个编码长度为m的抗体,m=结点数+车辆数-l=8+2-l=9. 在第一次迭代时,抗体通常是在解空间中用随机的方法产生的。例如,随机产生10 个抗体 的形式如下：Abl = 4l6589327 Ab2 = 236l59847Ab3 = 4723956l8Ab4 = 87495632lAb5 = l87964325Ab7 = 287l59436Ab6 = 752496l83Ab8 = 42739l865Ab9 = 28
