均匀克隆选择算法在城市配送中心选址中的应用

孙 欣，王宇嘉，林炜星

(上海工程技术大学 电子电气工程学院，上海 201620)

0 引言

随着中国互联网经济的快速发展，在一定的程度上带动了中国电子商务的行进脚步。现在，不论是“六一八年中购物节” 还是“双十一全球购物节”等一些电商购物促销活动，城市物流配送的时效性变得非常重要，尤其是一些大城市的消费者们，需求量和购买力都非常大，此时城市配送中心的选址就成为提高时效性的关键[1]。城市配送中心是物流配送系统的重要支撑，也是面向客户的主要战略部署，更是城市配送中心点和需求点之间的重要纽带。一个合适的城市配送中心选址方案可以很大程度上减少物流运输费用、提高经济效益、减少环境污染等[2]。

城市配送中心选址问题是指在某些约束条件下，使运营成本最低、总运输的时间最短、总运输的距离最短等目标达到最优，属于NP-hard问题[3]。沈默等[4]分析了重心法的优缺点，并将重心法应用在电商苏宁的物流配送中心选址问题上。刘倩等[5]提出了一种物流运筹学的方法解决物流配送中心选址问题，并在实例中验证了该方法的有效性。但是，传统的数学方法计算得出的理论结果，会与实际位置产生一定的偏差，而且计算时间长，所占内存空间也非常大，从而给求解带来了困难。

近年来，启发式选址算法成为众多学者研究选址问题的有效工具[6]。文献[7]中引入一种领域均值和边界缓冲墙的粒子群优化算法求解物流配送中心选址问题，当需求量越大，算法效果越佳。文献[8]中引入博弈的思想，将物流配送与客户利益放在一起考虑，建立双层规划模型。文献[9]中使用一种Logistic混沌系统方法，将其与果蝇优化算法相结合，实现配送路径达到最优，节约运输成本。文献[10]中提出了一种Laplace分布伪反向新的搜索机制来改善蜘蛛猴优化算法，增强算法的收敛性和可行性。但是，上述的启发式算法自身存在一定缺陷。在寻找最优解的过程中，会出现搜索精度不高，优化结果不理想的情况。在城市配送中心选址问题上，会搜索出一些局部最优解,不容易得到最好的中心选址配送方案。因此，能够寻找一种全局优化的启发式算法就特别关键。

人工免疫优化算法启发于生物的免疫系统机制，是在众多国内外学者们研究中逐渐发展起来的一种进化算法，利用免疫系统防护策略让抗体种群的多样性得到保障。人工免疫优化算法具有强大的自我调节能力，能够摆脱一些实际优化问题中出现的陷入局部最优，能够得到全局的最优解，因而被众多学者广泛应用[11]。文献[12]中引入配送时间和与需求量共同决定综合权值的免疫优化算法来验证配送时间对物流配送中心选址问题的实际影响。文献[13]中引用了一种免疫疫苗接种的方法，对克隆选择算进行一些改进，并将该方法应用于仓储布局优化设计中。Dou等[14]提出了一种免疫wolf-column混合算法来求冷藏食品的配送中心选址问题。Ping等[15]提出一种基于相似性向量距离选择的方法改善人工免疫算法解决物流配送中心位置问题的收敛性。

但是，求解城市配送中心选址问题上的免疫优化算法仍然会存在“早熟”现象，会导致收敛的效果不理想，收敛速度比较慢等一些问题。针对上述问题，本文提出了一种均匀克隆选择算法（Uniform Clone Selection Algorithm，UCSA）。通过均匀克隆选择策略减少计算量，加快收敛速度，克隆后的抗体采用全局变异策略增加了种群多样性。同时，本文引入基因清除策略，避免抗体种群早熟，提高抗体种群的收敛性。最终，使用该算法解决实际的城市配送中心选址问题。

1 选址问题描述

城市配送中心选址问题可以归结为一个好的配送中心选址方案能够使物流运输的费用最小化，并且配送的效率最大化。本文对城市配送中心选址数学模型做出以下假设：

1）城市配送中心存储的商品规模可以实现其在配送范围内所有需求点的商品需求量；

2）某个区域内的需求点有且只由一个城市配送中心提供所需要的商品，不允许交叉供货；

3）一个城市配送中心可以同时供应其配送区域范围内的多个需求点；

4）在城市配送中心选址问题中，城市配送中心的地址是从各个需求点中产生，而且城市配送中心的数量是固定的；

5）忽略城市配送中心与生产厂商之间的物流运费；

6）不考虑时间因素。

基于上述假设，本文建立以城市配送范围内的各个需求点的需求量与城市配送中心到需求点的距离乘积最小化为优化目标的数学模型。该数学模型需要在满足上述约束条件下，能够从规定城市配送区域内的n个需求点里面找到m个作为整个城市的配送中心来配送商品，如式(1)～式(6)所示。该模型的目标函数及约束条件为：

其中，N={1,2,L,n}是城市配送范围内的所有需求点序号集合；Ci为到城市内的各个需求点i的物流配送距离小于S的城市配送中心选址备选方案集合（其中，S为被选择为城市配送中心服务各个需求点的最大配送距离），i∈N,Ci⊆N；Ri表示需求点i的需求量；Dij是中心j与需求点i的最近距离；Zij为0～1的一个变量，它表示区域内需求点i和城市配送中心j的供求关系，当Zij=1时，意味着城市配送中心j给城市所在区域内的需求点i提供配送服务,否则Zij=0；hj是0～1的一个变量，当hj=1时，意味着城市所在区域内的需求点j被选择作为城市配送中心，否则hj=0；p表示城市配送中心数。

2 均匀克隆选择算法

2.1 克隆选择算法

Burnet等[16]在1959年提出生物免疫系统中识别抗原的细胞会被保留下来并进行细胞增殖活动，否则会被淘汰，克隆选择学说类似于达尔文的进化论，也就是所谓的“物竞天择，适者生存”进化法则。生物免疫系统会产生很多抗体细胞，这一过程被称作克隆扩增。De Castro等[17]在2002受到免疫系统克隆选择理论的启发，提出了克隆选择算法。其中，克隆选择过程与达尔文的进化思想类似,不同的是它应用于生物免疫系统内识别抗原的细胞群体，是一种基于免疫系统自身的进化算法。

在基本的克隆选择算法（Clone Selection Algorithm,CSA）中，主要涉及三种操作，即克隆、超突变和选择。基本的一个CSA流程描述如图1所示。

图1 CSA流程图

2.2 均匀克隆选择策略

在求解城市配送中心选址问题中，抗原识别表示为城市配送中心选址的问题识别，抗原表示为待优化目标函数和约束条件，抗体表示为每一个城市配送中心选址的备选方案。克隆表示为利用均匀选择策略产生新的子代抗体。抗体选择表示为利用全局变异策略和基因清除策略去除多余抗体。

现举例说明如下：本文采用的是实数编码方式，在城市配送中心选址问题中存在31个需求点，编号为1～31，从中选择其中6个作为整个城市的配送中心地址，假设被选中的候选方案中的一个编号为[1,2,3,4,5,6]，那么它就构成一个抗体xi，记作xi=[1,2,3,4,5,6]，i=[1,2,L,n]，抗体长度记为L，L表示城市配送中心选址的数量，所有的抗体xi构成了的抗体种群记为x={x1,x2,L,xn}。

在UCSA中，抗体与抗原之间的亲和度，通常作为适应度评估，表示抗体的优劣性，如式(7)所示：

F(xi)为抗体xi对应的目标函数值，Fmin、Fmax分别表示目标函数最大、最小值，A(xi)是亲和度。亲和度计算公式可根据实际问题进行设计。按照式(7)计算得出的目标函数值越小，则亲和度越高。

在UCSA中，抗体之间的亲和度,区别于上述的适应性评估，它是为评估抗体种群中抗体xi与抗体xj之间的相似度S(xi,xj)。计算公式如式(8)所示：

式(8)中，β表示抗体xi与抗体xj相同的位数，L为抗体长度,(i,j=1,2,L,n)。

在UCSA中，抗体在整个种群中的浓度大小可以表示种群多样性的好坏，抗体的浓度越大，抗体种群的多样性就越差。抗体xi在所有抗体中所占的相似度来表示抗体浓度C(xi)。计算公式如式(9)所示：

在UCSA中，采用均匀克隆选择策略进行抗体增殖，每一次只选择亲和度排在前m抗体作为父代，之后按照浓度的高低来决定每一个被选择的父代抗体的克隆数目是多少。计算公式如式(10)所示：

2.3 全局变异策略

克隆后的每一个抗体实行单一变异方式，不能满足抗体种群多样性和抗体分布均匀的需求，基于此类不足，对免疫克隆操作后的抗体进行全局变异，将被克隆后的抗体基因一分为二，前半段基因进行高斯变异，后半段基因进行柯西变异。变异过后的抗体，仍然需要与原抗体按照亲和度进行更新，保留亲和度更高的抗体。

高斯变异之所以被大家如此喜欢，是因为它能够在很小范围内具有良好的搜索能力，并且它在处理城市配送中心选址优化问题中，能够在抗体种群中以较大的概率产生较小的变异值。高斯变异形式如式(12)所示：

其中N(0,1)表示的是均值为0，方差为1的一维正态分布随机数。高斯变异的本质是充分利用当前抗体种群的信息进行扰动，这样就有利于跳出局部最优，从而使均匀克隆选择算法进行全局搜索，达到收敛的目的。

柯西变异与高斯变异不同，它能够产生一个远离原点的随机数，所以搜索范围要比高斯变异更大一些。柯西变异的形式如式(13)所示：

其中C(0,1)表示以0为中心，尺度参数为1的Cauchy分布随机数。柯西变异之后的抗体产生的变化更大，这样就可以使均匀克隆选择算法能够跳出局部最优，同时也能够提高了搜索的速度。

2.4 抗体种群的补充与更新

本文提出的均匀克隆选择算法中，如果抗体种群在进行克隆前抗体数量少于预期或者亲和度较差，或者克隆后抗体数量较少，这时利用MATLAB中的随机函数，产生一些候选抗体补充抗体种群。在处理复杂约束条件下的非线性优化问题时，往往存在早熟收敛问题，停滞是一种常见且难以避免的情况。在种群进化前期设置一个自我更新检测机制，如果迭代前T次，抗体xi没有变化，那么它将被亲和度值排在它前面的抗体随机替换。计算公式如式(14)所示：

当抗体种群中的抗体数量超过设定值的时候，则按照基于归一化目标函数值的欧几里德距离进行删减，直到不再超出设定值为止，那些亲和度高且分布均匀的抗体会被保留下来，这样就可以保证了种群的多样性，防止均匀克隆选择算法出现收敛速度非常慢，甚至抗体退化的现象。计算公式如式(15)所示：

地方政府应注重推动本地产业与技术创新的融合发展。通过产业的发展和承接以及产业集聚的溢出效应促进各地区技术创新能力的提高，并利用知识、技术的创新带动产业发展，吸引更多的产业集聚。此外，政府在产业集聚的成长与持续过程中，要鼓励建立资源信息共享、人才技术等方面的长期有效的合作机制，从而降低企业的学习成本，提高集聚区域内各企业之间的信任程度，为集聚企业的创新行为创造良好的氛围。

综上所述，本文提出的UCSA流程如图2所示，UCSA步骤如下：

图2 UCSA流程图

1）设置均匀克隆选择算法的基本参数。

2）初始抗体种群生成，记为x={x1,x2,L,xn}。

3）计算抗体与抗原的亲和度，利用式(7)，计算抗体种群中每一个抗体的A(xi)值，将所有抗体按照亲和度降序排列，取前m名抗体作为父代抗体，记为Xc={x1,x2,L,xm}。

4）使用均匀克隆选择策略决定克隆数量，利用式(8)计算抗体xi与抗体xj之间的相似度B(xi,xj)，利用式(9)计算抗体浓度C(xi)，利用式(10)计算父代抗体的克隆数量Qxi。克隆后生成的抗体种群记为

5）对克隆后的抗体采用全局变异策略，按照式(12)，式(13)进行高斯变异和柯西变异，得到新的抗体子代，变异后记为，xi与需要再一次评估亲和度。

6）抗体种群更新，按照式(15)，计算欧几里德距离，对抗体种群进行筛选，以此保证种群的多样性。

7）基因清除策略，按照式(14)，如果抗体xi迭代次数小于T次，而且xi迭代后没有变化，那么它将被亲和度值排在它前面的抗体中随机选择一位替换为。

8）记忆细胞更新，选择C个抗体存储到记忆细胞中，并且计算记忆细胞与抗原匹配度，并且计算记忆细胞与抗原匹配度。

9）满足终止条件，结果输出，否则重复步骤3）～8）。

3 实验结果

3.1 参数设置

为了证明均匀克隆选择算法在城市配送中心选址问题上的有效性，选择31个城市配送需求点的具体实例。城市位置坐标和需求量按照表1给出。本次实验是在win10操作系统，inter(R) Core(TM)，i5-8250U处理器的PC上操作完成，使用的仿真软件为MATLAB,版本为2019b。

表1 31个城市位置坐标和其对应的需求量

首先，设置均匀克隆选择算法的基本参数，抗体种群规模E=100、预设父代抗体个数m=20、克隆调节参数θ=2、最大迭代次数Itermax=100、迭代设定值T=10、配送中心数L=6、记忆细胞数C=10，Qxi取值范围为[1,10]，C(xi)取值范围为[0.2,1]。

本文采用MATLAB 2019b软件进行实验仿真，并对参考文献[7]中的改进粒子群算法，参考文献[9]中的改进果蝇优化算法，文献[13]中的改进克隆选择算法，以及本文提出的均匀克隆选择算法分别在6个城市配送中心选址问题上进行求解。在31个城市需求点中选出6个需求点作为城市配送中心共有种方案，每个算法各自运行30次，实验最后对4个算法的仿真结果进行对比，具体实验结果如表2所示。

表2 4种算法实验结果对比

3.2 实验对比分析

从表2 的实验结果可以看出，文献[7]最优值为592880，文献[9]最优值为568820，文献[13]最优值为550581，本文所提的均匀克隆选择算法最优值为549600，从实验结果可以看出，本文所提算法的最优值最小，收敛性最好。这就表示在城市配送中心选址问题中，本文算法提供的中心选址方案是所有算法中运输费用最低、配送效率最高的，优化效果也是最好的。从表2中还可以看出，文献[7]迭代次数为45,文献[9]迭代次数为38，文献[13]迭代次数为18，本文所提算法迭代次数为14，对比实验结果可知，本文所提算法比文献[7,9,13]所提算法收敛速度更快，运行时间最短，仅为9s。综上所述，均匀克隆选择算法在求解6个城市配送中心选址问题上优化效果最佳。四种算法的收敛曲线图如图3所示。

图3 4种算法收敛曲线对比图

在同等实验条件下，经过30次实验仿真后，本文所提的均匀克隆选择算法在城市配送中心选址问题上的最优实验结果的最优适应度值，平均适应度值收敛过程曲线如下图4所示，最优城市配送中心选址图如图5所示。

图4 均匀克隆选择算法收敛曲线图

图5 均匀克隆选择算法城市配送中心选址图

本文所提的均匀克隆选择算法在城市配送中心选址问题上的最优解决方案如表3所示，表3中城市配送中心对应的城市中心编号为[5,9,12,17,20,27]，该6个中心点为其他各个需求点提供配送服务的具体配送方案如表3所示。

表3 均匀克隆选择算法在城市配送中心选址上的最优解决方案

4 结语

以城市配送中心选址问题建立以城市配送范围内的各个需求点的需求量与城市配送中心到需求点的距离乘积最小化为优化目标的数学模型，并提出均匀克隆选择算法求解该模型。该算法采用一种均匀克隆选择策略，提高收敛速度，利用全局变异策略，增加了抗体种群的多样性。最后，引入基因清除策略，避免抗体种群出现“早熟”的现象。实验结果表明，与其它3种算法相比，本文所提算法的收敛速度更快，迭代次数更少，运输成本最小，配送效率最高，在求解多约束条件下的城市配送中心选址问题上取得令人满意的优化结果。