基于自适应大领域搜索的GTSP求解算法

摘要

本发明公开了一种基于自适应大领域搜索的GTSP求解算法，包括ALFG算法；ALFG算法将蚁群算法求解中的群内点更新策略融合至自适应大邻域搜索中，从而使得解的结构适应启发式算法求解的需求；在E‑GTSP基础上，提出了更新‑最差移除、更新‑最优插入、动态多点移除新的启发式，并且针对算法迭代过程中权重存在的尺度变化的问题，提出了一种新的自适应策略。本发明提供一种基于自适应大领域搜索的GTSP求解算法能有效提高更大规模的问题的求解效率的效果。

说明书

技术领域

本发明涉及广义旅行商问题领域。

背景技术

在求解MDCSP问题时，通过图的转换算法将其构建为E-GTSP模型进行求解，这种方法在更大规模的问题上效率不高，因为随着充电点和UGV工作点的增多，转换后图中顶点的数量将会随着虚拟顶点的存在而增多。因此，本文将提出一个基于自适应大邻域搜索(ALNS)的广义旅行商问题(非等价)直接求解算法：ALFG(ALNS for GTSP)。该算法使用群内点权重更新从而适应ALNS中解的结构表示需求，并通过开发新的基于贪心策略的启发式和动态多点移除启发式从而提高算法的收敛性能。

发明内容

发明目的：为了克服现有技术中存在的不足，本发明提供一种基于自适应大领域搜索的GTSP求解算法能有效提高更大规模的问题的求解效率的效果。

技术方案：为实现上述目的，本发明的技术方案如下：

基于自适应大领域搜索的GTSP求解算法，包括ALFG算法；ALFG算法将蚁群算法求解中的群内点更新策略融合至自适应大邻域搜索中，从而使得解的结构适应启发式算法求解的需求；在E-GTSP基础上，提出了更新-最差移除、更新-最优插入、动态多点移除新的启发式，并且针对算法迭代过程中权重存在的尺度变化的问题，提出了一种新的自适应策略。

进一步的，所述ALFG算法的算法框架：通过权重自适应在每次迭代中可动态选择某一个插入和移除启发式；将该自适应大邻域搜索算法实现在一个具有回火的模拟退火算法上；

所述ALFG算法中群内点权重更新：使用蚁群算法对GTSP进行求解时，提出一个群内点权重更新方法，将该方法扩展至启发式求解算法中从而首次实现启发式算法解；

进一步的，所述ALFG算法包括解的结构和启发式；所述启发式包括移除启发式和插入启发式；

所述移除启发式包括更新-最差移除：首先，找到从点

所述移除启发式还包括随机移除：在该种移除启发式中，算法每次选择一个随机的点，并将其从解中移除；

所述移除启发式还包括动态多点移除：首先将多点移除分为n

随机选择一个扇区B

进一步的，所述插入启发式包括待插入群的选择方法：首先待插入群的集合为V

所述插入启发式还包括插入代价计算方法：提出一个基于局部点更新的插入代价计算方法；在计算每个位置的插入代价之前，首先构建一个局部优化网络，设定

进一步的，所述ALFG算法包括接受和停止准则：采用线性模拟退火算法来作为ALNS的搜索框架；采用常规退火阶段和重加热阶段相结合的方式，在常规阶段，当解的连续无提升次数达到k

进一步的，所述ALFG算法包括权重更新；提出一个基于动态选择策略的权重更新机制，在每次迭代后，计算每个启发式的得分；引入了两个参数α

启发式的权重的更新在每个子段的开始进行，其更新公式如式(3.16)所示，其中M

进一步的，所述ALFG算法包括局部网络优化：首先将每个群内的点复制组成两层子网络，再按照解的顺序将所有的群的自网络排列组成一个含有2m层的网络，最后将第一个群的子网络复制到网络的最后，形成最终的层级网络。

进一步的，还包括实验参数设置；将ALFG算法与GLNS算法和ALFG-noMP算法进行比较；

将所述GLNS进行了扩展进行扩展，适用群内点更新来更新每个顶点集内各个顶点之间的权重，之后便使用同GLNS相同的算法框架和参数配置；主要参数为设置trial为3，num_iterations为60m，N

所述ALFG-noMP算法具体设置为采用同ALFG相同的算法框架，但在移除启发式中使用了GLNS中的Segment Removal来代替本文中提出的DMP移除；

所述ALFG算法参数设置表如下：

表3.2 ALFG算法主要参数设置表

进一步的，实验结果对比：在三种算法中，ALFG的收敛效果最好，在30个测试算例结果中，ALFG在其中27个算例上都取得了三个算法中的最优结果，其中在算例72rbg358上ALFG同ALFG-noMP结果相同，同时ALFG在30个算例上的结果全部都优于GLNS算法的收敛结果；ALFG-noMP的结果表现次之，在30个算例中，其获得了3个最好的收敛效果，并且，全部都优于GLNS；GLNS的收敛效果最差，但是由于其启发式的计算复杂度更低，故其平均运行时间最短，而ALFG和ALFG-noMP的平均运行时间相当。

进一步的，启发式有效性验证及分析；设计三组对比实验，分别是使用ALFG、ALFG-noMP以及ALFG-noIR，其中ALFG-noMP如上文所述，其使用GLNS中的Segment Removal替换本文中提出的DMP移除，ALFG-noIR使用了GLNS中的Unified Insertion和Unified Removal分别替换了ALFG中的更新-最优插入以及更新-最差移除；三个算法分别在30个算例中运行5次，得到箱线对比图；将30个算例根据收敛值的范围分成了6组，分别进行了显示。

有益效果：本发明针对求解MDCSP过程中，使用图的转换算法产生大量虚拟顶点的问题，提出一个基于自适应大邻域搜索的广义旅行商问题直接求解算法：ALFG。该算法将蚁群算法求解中的群内点更新策略融合至自适应大邻域搜索中，从而使得解的结构适应启发式算法求解的需求；在E-GTSP相关研究的基础上，提出了更新-最差移除、更新-最优插入、动态多点移除等新的启发式，并且针对算法迭代过程中权重存在的尺度变化的问题，提出了一种新的自适应策略。标准数据集上的实验结果表明ALFG相比GLNS的扩展，收敛性更优，同时，通过设计启发式对比实验，进一步验证了本文中启发式的有效性及更优性。

附图说明

附图1为群内点原始权重图；

附图2为群内点更新后权重图；

附图3为解的结构示意图；

附图4为原始最差移除示意图；

附图5为更行-最差移除示意图；

附图6为原始插入示意图；

附图7为更新-最优插入示意图；

附图8为一个待插入局部网格结构图；

附图9为一个层级网格示意图；

附图10为第一组算例箱线图；

附图11为第二组算例箱线图；

附图12为第三组算例箱线图；

附图13为第四组算例箱线图；

附图14为第五组算例箱线图；

附图15为第六组算例箱线图；

具体实施方式

下面结合附图对本发明作更进一步的说明。

如附图1-15：基于自适应大领域搜索的GTSP求解算法，包括ALFG算法；ALFG算法将蚁群算法求解中的群内点更新策略融合至自适应大邻域搜索中，从而使得解的结构适应启发式算法求解的需求；在E-GTSP基础上，提出了更新-最差移除、更新-最优插入、动态多点移除新的启发式，并且针对算法迭代过程中权重存在的尺度变化的问题，提出了一种新的自适应策略。

旅行商问题是一个组合优化问题，局部搜索技术(Local Search，LS)可以有效地求解该类问题。当前常见的局部搜索算法包括变邻域搜索(Variable NeighborhoodSearch，VNS)、大邻域搜索(Large Neighborhood Search，LNS)、自适应大邻域搜索(Adaptive Large Neighborhood Search，ALNS)、禁忌搜索(Tabu Search，TS)等。局部搜索的核心是解的邻域变化，其中VNS的领域产生是由扰动算子产生，而LNS是由一对移除-修复操作完成，即对一个解中的某些位置进行移除从而破坏该解，之后使用修复操作从而产生一个新的解。首次提出使用ALNS求解广义旅行商问题。自适应大邻域搜索算法的框架如算法3.1所示。

提出一个基于ALNS的第一类广义旅行商问题的求解算法(ALNS for resolvingGTSP，ALFG)，通过提出相应的移除和添加启发式、局部解优化、权重自适应机制，并将ALNS实现在一个带有回火的线性模拟退化算法框架下。

所述ALFG算法的算法框架：ALFG的算法框架如算法3.2所示，在算法中，首先实现了多个移除和插入启发式，算法通过权重自适应在每次迭代中可动态选择某一个插入和移除启发式；并且将该自适应大邻域搜索算法是现在一个具有回火的模拟退火算法上。可以看到，ALFG的主要流程包括：初始化个体、选择启发式、生成新解、解的接收判定、更新启发式的得分及权重等。

所述ALFG算法中群内点权重更新：同E-GTSP相比，在求解GTSP的过程中，其难点在于每个群C

如图1和2所示为内点权重更新的过程，其中图1为群C

为了实现上述过程，对每个群C

通过上述群内点权重更新之后，可以使得在一个GTSP实例中，最优解中机器人在每个群中至多访问两个顶点。

所述ALFG算法包括解的结构和启发式；

如图3所示的解的结构；图3中，每个圆圈代表一个顶点，

所述启发式包括移除启发式和插入启发式；

所述移除启发式包括更新-最差移除：算法倾向于去移除拥有最大移除代价的点，基于该思想，可将其扩展至求解GTSP中，其工作示意图如图4所示，并且移除代价可通过式(3.6)计算获得，其中

但是上述移除操作在实际算法运行当中很难达到最差移除所需要的效果，这是由于

所述移除启发式还包括随机移除：在该种移除启发式中，算法每次选择一个随机的点，并将其从解中移除；

所述移除启发式还包括动态多点移除：在单点最差移除中，每次只移除一个最差的点，依次循环，知道移除N

多点移除的思想最早可在很多个算法中体现，将其用在了求解E-GTSP中，并称其为Segment Removal，但是其并没有考虑到移除的有效策略问题，只是简单地扩展了将随机移除，即每次从解中随机移除一段，并且该段的大小等于N

动态多点移除的核心是移除点个数的动态选择，首先，确定一个参数n

上述移除代价的引入可以使得动态多点移除启发式在移除时在一定程度上保留当前解的一些优质基因，从而避免完全随机性，加快收敛速度；对于每次移除群数n

基于上述分析，提出一种动态机制来控制n

表3.1群的数量于等级n

随机选择一个扇区B

使用分区移除机制的优势在于对搜索的阶段不同特点做出了权衡。在算法运行过程中，随着连续无提升次数x的不断提升，当选定一个扇区B

所述插入启发式包括待插入群的选择方法：对于待插入群的选择方法，常见的做法是将根据各待插入群与解的距离来确定，但由于本文中采用的解的表达形式不同，故将其进行了扩展。首先待插入群的集合为V

所述插入启发式还包括插入代价计算方法：对于E-GTSP，插入代价可以被简单地计算为：c＝w(x，y)+w(v，y)-w(x，y)，其中e(x，y)∈E

可以看到上述公式中只考虑到了前一个群的“出点”和后一个群的“入点”，这导致其无法在两个群之间实现局部最优，为了克服这个缺陷，提出一个基于局部点更新的插入代价计算方法，该方法的过程如图7所示。在计算每个位置的插入代价之前，首先构建一个如图8所示的局部优化网络，设定

所述ALFG算法包括接受和停止准则：采用线性模拟退火算法来作为ALNS的搜索框架；在模拟退火算法中，一个新的解S

在ALFG中，温度T被初始化为T

为了降低算法在求解较大尺寸问题时陷入局部最优的概率，在标准模拟退火算法的基础上，还实现了一个重加热的策略，这种方法已被提出，并称之为带有重加热的模拟退火算法。在本算法设计中，采用常规退火阶段和重加热阶段相结合的方式，在常规阶段，当解的连续无提升次数达到k

采用常规退火阶段和重加热阶段相结合的方式，在常规阶段，当解的连续无提升次数达到k

所述ALFG算法包括权重更新；相比于大领域搜索(LNS)，使用ALNS的最大优势是可以将多个不同的移除和插入启发式同时实现在算法中，从而增加算法的搜索能力，在每次迭代中，移除启发式和插入启发式的选择都是根据他们各自的权重来进行选择的，即，拥有更高权重的启发式将有更大的概率被选择，故而启发式的权重更新是ALNS的重要组成步骤。针对传统的更新策略无法顾及搜索阶段的问题，提出一个基于动态选择策略的权重更新机制。

在每次迭代后，计算每个启发式的得分，一般的方法为计算当前解与上次解的差值，并除去上次解的值，并且限制分数的最小值为0，本算法中采用的分数计算方式略有不同，在本算法中，引入了两个参数α

在上式中，α

启发式的权重的更新在每个子段的开始进行，其更新公式如式(3.16)所示，其中M

所述ALFG算法包括局部网络优化：首先将每个群内的点复制组成两层子网络，再按照解的顺序将所有的群的自网络排列组成一个含有2m层的网络，最后将第一个群的子网络复制到网络的最后，形成最终的层级网络。

一个构建好的层级网络模型如图9所示，分别以第一个群的每一个点位起点，以相应的镜像为终点，进行最短路径查找，可以看到该模型为一个有向无环图(DAG)，对于一个DAG来说，找到一条最短路径的算法时间复杂度为O(V+E)，其中V和E分别为图中点和边的数量，在建立的层级网络中，含有2(m+1)层网络，求解该网络，只需要对相邻层中点进行松弛操作即可，在进行松弛前，可以将解进行旋转，使得含有最小数量点的群放在第一层的位置，从而减少寻找最短路径的次数。基于此，算法在最差情况下将需要O(n+m

还包括实验参数设置；对于算法的测试实验，在实现ALFG的基础上，还实现了无多点移除的ALFG以及GLNS的扩展版本。

算例生成：由于目前的研究大都针对于EGTSP进行研究，故现有的相关标准数据集都是针对E-GTSP的，其中，GTSP-Lib数据集被广泛使用，为了更好地测试本算法，提出一个标准的GTSP算例生成方法，通过该方法，可将一个的E-GTSP转换为一个标准的GTSP问题，从而使得数据集具有确定性。该方法如算法3.3所示。

已知一个转换方法，其方法是通过将算例的邻接矩阵与相同维度的(0，1)随机数相乘，从而完成转换，但是由于随机数的不确定性，该方法是不具备标准性的，故而不利于问题的广泛研究。而本算法3.3的核心思想是一个算例的邻接矩阵C，C的每个元素的最后一位或最后两位是没有规律但唯一确定的，通过将每个元素与其最后以为或最后两位相乘，则会使得新的矩阵C

实验参数设置：将ALFG算法与GLNS算法和ALFG-noMP算法进行比较；

GLNS算法是目前求解E-GTSP问题最有效的求解器，其并不能用来直接求解非等价的GTSP，将GLNS进行了扩展进行扩展，适用群内点更新来更新每个顶点集内各个顶点之间的权重，之后便使用同GLNS相同的算法框架和参数配置；主要参数为设置trial为3，num_iterations为60m，N

该对比算法是在本文提出的算法ALFG上进行一些改动得到的，主要目的是完成对ALFG算法相关设计有效性的验证。所述ALFG-noMP算法具体设置为采用同ALFG相同的算法框架，但在移除启发式中使用了GLNS中的Segment Removal来代替本文中提出的DMP移除；

所述ALFG算法参数设置表3.2如下：

表3.2 ALFG算法主要参数设置表

实验结果对比：实验的最终结果如表3.3所示，所有的算例都是将GTSP-Lib中的标准算例经算法3.3转换得到的，其中最小的算例包含20个群和100个顶点，最大的算例中包含99个群和493个顶点。从表3.3中可以看到，ALFG算法的表现优于其他两个算法，因为ALFG在大部分的算例上的收敛效果好于其他两个算法。

在三种算法中，ALFG的收敛效果最好，从表3.3可以看到，在30个测试算例结果中，ALFG在其中27个算例上都取得了三个算法中的最优结果，其中在算例72rbg358上ALFG同ALFG-noMP结果相同，同时ALFG在30个算例上的结果全部都优于GLNS算法的收敛结果；ALFG-noMP的结果表现次之，在30个算例中，其获得了3个最好的收敛效果，并且，全部都优于GLNS；GLNS的收敛效果最差，但是由于其启发式的计算复杂度更低，故其平均运行时间最短，而ALFG和ALFG-noMP的平均运行时间相当。

对上表中的数据进行进一步统计可以得到如下结果：ALFG的收敛效果相比ALFG-noMP平均提升了2.2％，同时，ALFG相比GLNS算法的提升更为显著，达到14.9％。该结果同时也表明本文中的移除及插入启发式相比GLNS中的启发式具备较大的提升效果，为了进一步量化该提升效果，接下来对提出的启发式有效性进行验证及分析。

表3.3算法在30个算例上的平均结果对比表

启发式有效性验证及分析；

将对ALFG中的更新-最差移除、更新-最优插入以及多点移除启发式的效果进行分析。首先，为了实现对上述内容的分析，设计三组对比实验，分别是使用ALFG、ALFG-noMP以及ALFG-noIR，其中ALFG-noMP如上文所述，其使用GLNS中的Segment Removal替换本文中提出的DMP移除，ALFG-noIR使用了GLNS中的Unified Insertion和Unified Removal分别替换了ALFG中的更新-最优插入以及更新-最差移除；

上述三个算法分别在30个算例中运行5次，得到如图10、11、12、13、14、15所示的箱线对比图，并且为了保证显示效果，将30个算例根据收敛值的范围分成了6组，分别进行了显示。从图10、11、12、13、14、15中可以看到，在所有的30个算例运行结果上，ALFG取得了26个平均值最低的成绩，并且在剩余4个算例中，ALFG均拥有更小的最高值或最低值，这表明相比于ALFG-noMP和ALFG-noIR，ALFG具有更好的收敛性。

更进一步地，通过统计发现，在所有的算例结果中，ALFG相比ALFG-noMP和ALFG-noIR，其收敛效果分别平均提升了2.2％以及8.1％；上述提升分别对应：MP移除相比GLNS中Segment Removal的提升效果，以及更新－最优插入和更新－最差移除相比GLNS中UnifiedInsertion和Unified Removal的提升效果。

针对求解MDCSP过程中，使用图的转换算法产生大量虚拟顶点的问题，提出一个基于自适应大邻域搜索的广义旅行商问题直接求解算法：ALFG。该算法将蚁群算法求解中的群内点更新策略融合至自适应大邻域搜索中，从而使得解的结构适应启发式算法求解的需求；在E-GTSP相关研究的基础上，提出了更新-最差移除、更新-最优插入、动态多点移除等新的启发式，并且针对算法迭代过程中权重存在的尺度变化的问题，提出了一种新的自适应策略。标准数据集上的实验结果表明ALFG相比GLNS的扩展，收敛性更优，同时，通过设计启发式对比实验，进一步验证了本文中启发式的有效性及更优性。

以上是本发明的优选实施方案，对于本技术领域普通技术人员来说，在不脱离本发明原理前提的情况下，还可以做出若干改进和润色，这些改进和润色同样视为本发明的保护范围。