基于免疫克隆选择算法的限量弧路由问题外文翻译资料

英语原文共 28 页，剩余内容已隐藏，支付完成后下载完整资料

英文翻译

英文题目 Immune clonal selection algorithm for

capacitated arc routing problem

中文题目 基于免疫克隆选择算法的限量弧路由问题

基于免疫克隆选择算法的限量弧路由问题

Ronghua Shang，Hongna Ma¹ ，Jia Wang²

，Licheng Jiao³，Rustam Stolkin⁴

1 Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China,

Xidian University, Xirsquo;an 710071, China e-mail: rhshang@mail.xidian.edu.cn

2 Xirsquo;an Institute of Huawei Technology Co. Ltd,Xirsquo;an 710075, China,e-mail: jsc88123@163.com

3 e-mail:lchjiao@mail.xidian.edu.cn

4 School of Computer Science, University of Birmingham,Edgbaston, Birmingham B15 2TT, UK

e-mail: R.Stolkin@cs.bham.ac.uk

摘要：在现有的启发式求限量弧路由问题中，遍历局部搜索算子经常用来探索当前解的邻域。该机制有利于寻找高质量的解；然而，它需要进行大量的目标函数评价，会使计算的复杂度变高；因此需要进一步提高此类算法的效率。对于复杂限量弧路由问题，本文提出了一种高效的免疫克隆选择算法求解限量弧路由问题，该方法使用的函数评价次数较少。首先，利用改进的建设性启发式来初始化抗体种群；这种通过启发式产生的初始抗体能够加速算法的收敛性。其次，我们展示了免疫克隆选择算法如何能够优先选择这些高质量抗体；通过对相同抗体的不同克隆采用各种不同的策略，不仅促进了抗体之间的合作和信息交换，而且还增加了多样性，加快了收敛速度。第三，针对不同类型的不可行解，提出了两种不同的抗体修复操作；这些操作使不可行的解向着全局最优的方向移动。实验研究表明，本文算法与目前已有的先进算法相比，性能得到了提高，特别是在中等规模的问题中。

关键词：免疫克隆选择；限量弧路由问题；抗体修复；元启发式算法

1.概述

著名的限量弧路由问题^[1](ARP)属于经典组合优化问题。该问题可描述如下:给定一个连通图及其任务集合,存在一组车辆停留于图中一被称为仓库点(depot)的特殊点。ARP的目的是在各种因素的制约下找到成本最低的路径。本文有一个重要的容量约束和一个特定版本的ARP协议的模型，称为限量弧路由问题。在限量弧路由问题中，每个边缘（或圆弧）需要服务有一个特定的需求d，而每个车辆具有相同的容量Q。容量约束是指总需求量每辆车的任务，不超过其容量Q；在这里一个边缘是无向的而一个圆弧是定向的^[2]。

限量弧路由问题可以描述如下：有限的容量Q（基于预定义的顶点，称为仓库）内，给定一个表示道路网络的连通图G(V,E,A),其中V,E和A分别表示顶点集合,边集合与弧集合。每一个边（或弧）与一个非负的旅行成本和一个非负的需求相关联。边缘（或弧）需要服务有正的要求，而其他的边缘（弧）可以走过任何数量的时间，而不会产生任何服务成本，因此是零需求。求解限量弧路由问题被定义为为车辆在下列条件下找到一个最佳的路径：

1. 每一条回路必须由仓库点出发并最终回到仓库点；
2. 每一个任务必须在一条且仅一条回路中被服务；
3. 对于每条回路,其服务的任务总需求量不能超过其容量Q，问题目标为最小化所有回路中经过消耗与服务消耗的总和。

在过去的20年里，人们对限量弧路由问题的兴趣越来越大。由于限量弧路由问题是一个NP难题，启发和启发式通常被研究者考虑。众所周知的启发式算法包括增强合并和路径扫描、旅游分裂算法和循环任务。这些流行的启发式，最常用的是“路径扫描”，它是指扫描的概念剩余的服务任务，以确定哪一个应该是在当前路径下。最近，Santos^[3]等介绍了一种改进的启发式算法求解路径扫描，其中包括一种新的“椭圆规则”。当车辆的负载接近其容量时，路径扫描将只专注于在椭圆范围内的那些任务。在一定的处理时间内，椭圆规则启发式算法可以得到比传统路径扫描方法更好的结果；然而，当它应用到大规模的情况下，结果可能是次优。由于限量弧路由问题的实际应用往往是大型的，研究人员把他们的注意力转向启发式，以高成本的代价产生更好的解。随着智能优化方法的出现，如进化算法、禁忌搜索算法和模拟退火算法，在解决限量弧路由问题上启发式开始扮演着越来越重要的作用。在2000，Hertz等为CARP^[4]提出了一种禁忌搜索算法称为CARPET；在CARPET中，解决方案被表示为一组通过点组成的编码。由于禁忌搜索和一些新的本地搜索算子的框架， CARPET能够产生更好的解相比于以前的启发式。然而，CARPET顶点编码的使用使计算复杂度增加，并且导致了非常低的搜索效率。随后在2001年，Hertz and Mittaz提出了变邻域搜索算法来解决CARP，该算法的最大贡献是它用变邻域搜索算法的框架取代了禁忌搜索算法的框架，并得到了较好的解决方案。在2003年，Beullens^[5]等提出了局部搜索(GLS)制导方法，它使用2-opt作为局部搜索策略。在同一年，Greistorfer^[6]在禁忌搜索算法和分布式搜索相结合搜索的基础上提出了禁忌的分布式搜索。然后，在2004，Lacomme^[7]等人提出了 Lacomme Memetic算法(LMA)来解决CARP，它用各种本地搜索方法和任务的编码方案综合遗传算法令解被表示为一个有序的任务列表。在Greistorfer， Lacomme扩展LMA求解双目标CARP，以产生高质量的解。在2006年Handa^[8]等人提出了一种稳健的路由优化算法来优化盐车路径规划。在2008年Eglese提出了确定性的禁忌搜索算法解决CARP。最近，2009年，Tanget等提出了一种扩展邻域搜索的Memetic算法（MAENS）。这项工作提出了一种新的本地搜索算子，这是能够搜索使用大的步长，并且是不太可能陷入局部最优解。后来，在2011年，Meiet^[9]等结合MAENS与其他策略手段处理各种CARP的扩展模型，如周期性的Memetic^[10]算法、基于多目标分解的CARP和为大型CARP服务的路由距离分组协同进化。虽然MAENS和它的变体在大型的情况下显示性能优良，但它需要大量的功能评估。函数评价是许多CARP应用的重要标准，特别是在那些的边缘需求是不确定的或可变的。

其他启发式方法包括变邻域搜索算法、禁忌分散搜索、割平面算法、进化算法、禁忌搜索算法、带进化路径重新链接的GRASP、利用车辆路变换的CARP。这些算法通常在大规模实例解决方案的质量优于启发式算法，虽然他们的计算成本往往高于非metahueristic方法。

MAENS可以分为三个阶段：（1）传统的移动算子；（2）合并拆分操作；（3）进一步的传统移动算子。在移动算子（如单次插入，双插入和交换），所有相邻的算子根据遍历式搜索，可以从目前的解决方案检查了来找到最佳的改进。例如，给定n边的任务，一个插入操作将需要2n 2功能评估，对于合并分裂算子，p路线选择从可能的路线进行重建，这也会导致高的计算成本。我们需要根据需求的变化及时提供车辆安排。为了在有限数量的功能评价，获得一个可以接受的解决方案，本文提出了基于CARP的免疫克隆选择算法（ICSA-CARP）。在ICSA-CARP中，首先，我们使用了最近提出的国家的最先进的启发式产生初始的解决方案，它最有可能加速收敛；其次，通过克隆抗体的亲和力高，ICSA-CARP可以专注于最有价值的解决方案空间部分。通过对同样的抗体采采取不同的策略，它不仅促进合作和抗体之间的信息交流，但也增加了多样性和加快收敛速度。最后，使用不同的抗体修复操作，这导致不可行的解决方案往全局最佳的方向移动，进一步加快收敛。

本文的其余部分组织如下：第二部分介绍了基本的背景资料，包括CARP和人工免疫系统的数学处理方法；第三部分介绍了ICSA-CARP程序：抗体初始化，免疫克隆操作，免疫基因操作、维修操作和抗体的克隆选择操作。第四部分介绍了三公开可用的地面真实数据集用于评价在ICSA-CARP与MAENS的比较，以及他的两个重要变异；第五部分是结束语。

1. 相关概念

2.1 CARP问题的数学表示

对于一个算法的性能，适当的表述一个解对于进行有效的搜索是至关重要的，并且对解的质量有一个显着的影响。在Hertz的CARPET中^[11]，CARP的解是表示为一组的路线，其中每一个是基于顶点编码方案。每一个路径都与一个表示向量相对应，由一系列的二进制变量组成路线末端。对于每个搜索二进制变量，0意味着这条路线的任务只能是旅行，而不是被服务，反之1代表任务不仅要旅行，而且要服务；LMA代表解任务的有序列表。ICSA-CARP使用一个类似的简洁的任务编码方案。这些任务的序列可以被转化成一个序列的顶点，通过连接每一个随后的任务，得到它们之间的最短路径。CARP被定义在一个连通图上G=(V,E,A)，其中边缘,弧。每个所需的弧的图形被分配一个唯一的ID。每个所需的边缘被视为一对弧，代表一个方向。因此，每个边缘任务分配两个标识。为了方便，所有的入侵检测系统都设置为非负整数。每个ID、e有六个属性，我们把它命名为h(e),t(e),t_c(e),s_c(e),d(e)和i(e)，分别为头结点、尾节点、经过花费、服务花费、需求和相反任务序号。图2-1给出了相应的图解。

图2.1 任务ID编码的一个例子

图中包含5个边任务，1个弧任务，弧任务只有一个方向所以只有一个ID。由图中标注可知：h(4)=t(10),t(4)=h(10),d(4)=d(10),t_c(4)= t_c(10),s_c(4)= s_c(10),i(4)=10。特殊的如果a为弧任务ID,则i(a)= -1，表示a的反向序列不存在。我们把任务ID0定义如下：h(0)=t(0)=dep,d(0)= t_c(0) =s_c(0)=0,i(0)=0。

CARP的一个解x可以表示为m个回路(m个车辆)所构成的任务序列，x=(R₁,R₂, hellip; , R_k, hellip; , R_m)，其中R_k表示的就是第k个回路的车辆任务序列，R_k的第一个任务和最后的任务都为0任务。例如对于图2.1的编码实例，假设车辆数目为2，我们可以组成解x=(0,4,3,2,0,1,12,11,0)，其中R₁=(0,4,3,2,0),R₂=(0,1,12,11,0)。对回路R_k来说,其总花费TC(R_k)与总需求D(R_k)可计算如下：

（2.1）

（2.2）

其中m_c是一个二维数组,m_c[i][j]表示由顶点i到顶点j的最少中间路径花费，length(R_k)表示回路R_k的任务序列长度，R<sub

剩余内容已隐藏，支付完成后下载完整资料</sub

资料编号：[31247]，资料为PDF文档或Word文档，PDF文档可免费转换为Word