陈林,姚宏亮

（1.安徽财贸职业学院电子信息系,安徽合肥230601；2.合肥工业大学计算机与信息学院,安徽合肥230009）

免疫克隆遗传算法在物流配送中的应用

陈林1,姚宏亮2

（1.安徽财贸职业学院电子信息系,安徽合肥230601；2.合肥工业大学计算机与信息学院,安徽合肥230009）

针对免疫遗传算法在解决物流配送出现局部搜索能力不足和算法过早的收敛问题,提出了基于克隆选择的改进算法,通过引入克隆增殖算子、高频变异和克隆选择算子,有效增加了种群的多样性和提高了局部搜索能力,避免了算法过早的收敛.针对物流配送的实例论证和分析,显示算法的有效性.

物流配送；克隆增殖；克隆选择；免疫遗传算法

现阶段,我国的物流迅速发展,物流市场对配送的需求十分旺盛.而在物流的各项成本当中,配送成本占了相当高的比例.因此物流配送中合理调度车辆对降低物流成本有着重要的意义[1],车辆调度问题（Vehicle Routing Problem,VRP）也成为众多学者研究的热门话题.

目前研究VRP问题的算法有很多,主要分成两大类：精确算法和启发式算法.精确算法主要有：分支定界法（Branch and Bound Approach）、割平面法（Cutting Planes Approach）、网络流算法（Network Flow Approach）和动态规划方法（Dynamic Programming Approach）.然而,通过精确算法计算VRP问题,计算量很大,因此实用性很有限.所以大部分学者都将研究方向定位于启发式算法[2-6].

对VRP问题,许多研究者进行了大量的研究.李大卫等求解了有时间窗约束的VSP问题[7].张震优化了有行程约束的单车场满载问题[8].蔡延光等对满载问题使用了禁忌搜索算法和模拟退火算法进行了求解[9].刘浩等用模拟退火算法求解了两车型随机需求的VRP[10].张涛等用禁忌搜索算法和遗传算法的混合策略求解了VRP[11].王莉用启发式算法求解了有时限的VRP[12].袁健等用神经网络法求解了VRP[13].姜大立等分别用遗传算法求解了无时限和有时限的物流配送车辆调度问题[14].近年来,郭耀煌等对物流配送车辆调度问题进行了较为深入的研究,提出了多种求解算法[15].周双贵对物流配送车辆调度问题的模型和求解方法也进行了较为深入的研究[16].

免疫遗传算法是在遗传算法的基础上,加入了免疫算子,算法的关键就是疫苗的提取.至于疫苗的提取,根据生物免疫学原理,将求解优化问题的目标函数和约束条件看作是“抗原”,而把优化问题的解看成是“抗体”,那么免疫遗传算法就类似于产生大量抗体的过程.

不过免疫遗传算法也存在明显的不足,主要表现在以下几个方面：

（1）免疫遗传算法采用是随机全局搜索策略,忽视了局部搜索,对于复杂问题情形,难以获得满意的结果；

（2）单纯的接种疫苗会使种群朝着一个方向进化,失去了种群的多样性；

（3）种群的单一性,可能会使的算法过早的收敛.

针对免疫遗传算法上述不足,在疫苗选择的关键点上引入了克隆选择的机制.

1 基于克隆原理的免疫遗传算法

克隆选择机制指的是当未知抗原细胞入侵系统时,对抗体细胞进行克隆选择,描述了免疫应答的过程.抗体细胞被选择的可能性受制于亲和力,亲和力越大的细胞,被选择的可能性就越小.

克隆选择算法通过引入克隆增殖算子、高频变异和克隆选择算子,在保持免疫遗传算法全局搜索行的基础上,增强了局部搜索能力,并增加了种群的多样性；克隆选择是在交叉、变异等遗传算子和群体控制的基础上实现的,有效的改善了算法的过早收敛.

1.1 克隆选择算子

克隆选择主要经历增殖、变异和选择的过程,这三个过程被称之为克隆选择算子.

（1）克隆增殖TcC：克隆增殖是模拟生物进化过程,使得比较优秀的抗体能够得到复制,因此,需要对比较优秀的基因（用亲和力高低来衡量）按照一定规模进行复制,即对亲和力高的抗体细胞进行无性繁殖（即克隆）.

（2）克隆变异TmC：对种群细胞进行高频变异操作（主要是进行连续倒位操作）.可以使得变异后的群体里原始解较远的距离.

（3）克隆选择TsC：选择的依据是对变异前后的个体进行亲和力的比较,根据亲和力的大小决定选择变异后的个体还是变异前的个体.

1.2 免疫克隆算法的算法步骤

下面针对基于克隆选择的免疫遗传算法的算法思想,描述算法的步骤.

步骤1：抗原识别.将给定的目标函数和约束条件作为待求问题的抗原；

步骤2：初始化种群.搜寻记忆抗体,若无则随机产生；

步骤3：提取疫苗；

步骤4：计算抗体亲和力和适应度；

步骤5：判断终止条件.到了无法改善解的时候,终止；

步骤6：克隆增殖；

步骤7：克隆变异.多重高频变异；

步骤8：克隆选择.还是根据亲和力进行选择；

步骤9：接种疫苗；

步骤10：免疫选择；

步骤11：更新种群.

2 免疫遗传算法在物流配送问题中的应用

2.1 问题描述

本文所描述的VRP问题为：在各种能力约束的条件下,使得运输成本最小化.约束条件有：车辆的载重量一定,车辆的行驶距离一定,车辆只允许有一条行驶路线等.

研究无时间限制闭环式问题,该问题的可描述为

上述所用符号说明如下：

K为配送车辆数目；L为需求点总数；Dk为第k辆车的最大行驶距离；Qk为第k辆车的最大载重量（k=1,2,…,K）；qi为需求点i的货物需求量（i=1,2,…,L）；dij为需求点i到j的距离（i=1,2,…,L；j=1,2,…, L）；d0j为配送中心到各需求点的距离（j=1,2,…,L）；nk为第k辆汽车配送的需求点数（nk=0表示未使用第k辆汽车）；Rk为第k条路径；rki为需求点在路径k中的顺序为i（不包括配送中心）,令rk0=0表示配送中心.

式（1）至（8）为目标函数和各种能力约束条件.

2.2 克隆选择在问题中的应用

在免疫遗传算法的基础上加上了克隆算子,增加了局部搜索能力、有效保证了种群的多样性,并避免了算法过早的收敛.下面就物流配送问题,给出了克隆算子的构造方法.

2.2.1 克隆增殖下面是克隆增殖的表达式：

Θ反映了抗体i与其他抗体的亲和力,这里将其简单定义为：

Nc是抗体群总的克隆规模,显然,in（tx）表示取大于x的最小的整数.克隆过后,种群变为：

其中：

这里采取的变异,主要是为了保留抗体的原始信息,而不是作用到A∈ A'

多重高频变异.例如抗体123456789,对被选择的基因段进行倒位操作,得到了128765439,并对此倒位操作进行多次.

2.2.3 克隆选择克隆操作之后,在子种群中选择基因比较好的,保留下来.

则表明变异后的抗体Bi基因比较好,从而用此抗体来更新,否则,保留变异前的抗体Ai.

2.3 数值实验与分析

假设有8个需求点和一个配送中心的配送系统,各个需求点的需求为di（i=l,2,…,8）,配送中心用两辆车（载重量为8）配送,需求点与配送中心的距离如表1所示.要求优化配送线路,使得配送成本最小化.

用基于克隆选择的免疫遗传算法对上述问题进行求解,变异率如果太小,则产生新的染色体概率小,导致不成熟的收敛；太大,可能使优秀染色体的破坏机会增加,甚至不能收敛,应多次实验调整或者采用自适应方法调整变异率通过上机运算,得到的线路有：

路线1：0-＞4-＞2-＞6-＞0

路线2：0-＞3-＞7-＞5-＞8-＞1-＞0

运输总距离=83.5

通过分析,此方案是此问题的一个可行解.

表1 顾客间距离以及顾客需求Tab.1 Distance between the customerand Customerneeds

3 结论

本文针对物流配送中的路径最优化问题,提出了利用免疫算法求解该问题时存在的一些不足,通过改进此算法,增加了克隆选择的机制,有效的弥补了免疫遗传算法的不足.并通过较小规模的物流配送问题的仿真分析,得到了较好的效果.

[1]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社,2001.

[2]郎茂样.流配送车辆调度问题的模型和算法研究[D].北京：北方交通大学,2001.

[3]蔡希贤,夏士智.物流合理化的数量方法[M].武汉：华中工学院出版社,1985.

[4]刘朝晖,范荣华,万毅.物资管理系统工程[M].北京：中国物资出版社,1997.

[5]马力强.关于我国现代物流发展的思考[J].交通运输系统工程与信息,2000（1）：13-15.

[6]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社,2001.

[7]李大卫,王莉,王梦光.一个求解带有时间窗口约束的车辆路径问题的启发式算法[J].系统工程,1998（4）：20-24.

[8]张震.城市货运汽车营运组织最优化的理论与方法[J].管理工程学报,1995,9（3）：143-152.

[9]蔡延光,钱积新,孙优贤.多重运输调度问题基于双表的并行表搜索算法[J].系统工程理论与实践,1998,18（1l）：20-26.

[10]蔡延光,钱积新,孙优贤.多重运输调度问题的模拟退火算法[J].系统工程理论与实践,1995,18（10）：11-15.

[11]刘浩,袁健,卢厚清.两种类型车辆随机需求路由问题[J].南京航空航天大学学报,2001,33（2）：155-158.

[12]张涛,王梦光,杨建夏.不确定计划数的轧制批量计划的模型和算法[J].系统工程学报,2000,15（1）：54-60.

[13]王莉.CIMS下的热轧生产批量计划的数学模型及解法[J].鞍山师范学院学报,1999,1（3）：17-22.

[14]袁健,刘晋.随机需求情形VRP的Hopfield神经网络解法[J].南京航空航天大学学报,2000,32（5）：579-585.

[15]郭耀煌,李军.车辆优化调度[M].成都：成都科技大学出版社,1994.

[16]周双贵.基于MATLAB的车辆路径系统研究[D].北京：北方交通大学,2001.

（责任编辑：卢奇）

Application of immune clonal genetic algorithm on logistics and distribution

Chen Lin1,Yao Hongliang2
（1.DepartmentofElectronic Information,AnhuiFinance&Trade VocationalCollege,Hefei230601, China；2.College ofComputer Science and Information Technology,HefeiUniversity ofTechnology, Hefei230009,China）

This paper puts forward to an improved algorithm based on clonal selection to solve the local search ability inadequacy of Immune Genetic Algorithm appeared in the Physical distribution and algorithm of convergence problem early．The introduction of cloning proliferation operator,the high frequency variation and clonal selection operator increase the diversity of population and improve the local search ability effectively as well as avoiding the algorithm convergence．The efficiency of the algorithm will be proved by demonstration and analysis of logistics and distribution．

physical distribution；clonal proliferation；clonal selection；immune genetic algorithm

TP18

A

1008-7516（2012）05-0070-05

10．3969/j．issn．1008-7516．2012．05．017

2012-07-16

陈林（1980-）,男,安徽合肥人,硕士,助教．主要从事软件开发和数据挖掘研究．