基于元学习的深度强化学习求解多目标旅行商问题的方法

摘要

本发明公开了一种基于元学习的深度强化学习求解多目标旅行商问题的方法，包括以下步骤：S1：定义多目标旅行商问题；S2：将多目标旅行商问题按照权重加和的方式分解为一组单目标优化的子问题；S3：构建基于元学习的深度强化学习算法框架并对深度强化学习算法框架中的元模型进行训练；S4：对于步骤S2中得到的每一组单目标优化的子问题，所述元模型进行步数的参数微调得到对应的子模型；S5：利用子模型求解子问题；S6：所有子问题的解的集合为多目标旅行商问题的解。本发明方法只需要训练好一个元模型，便能对任意给定的权重只需要对该元模型做少量的参数更新便能快速微调出该权重对应的模型并得到令人满意的解。

说明书

技术领域

本发明涉及运筹学领域中的多目标优化领域，更具体地，涉及一种基于元学习的深度强化学习求解多目标旅行商问题的方法。

背景技术

旅行商问题是一种经典的NP-hard组合优化问题，在物流调度行业中有着广泛的应用。根据现实生活中实际约束和优化目标的不同，又有多种不同的变种，如带容量约束或时间窗约束的车辆路径规划问题，需路径平衡优化的车辆路径规划问题等等。而本发明研究的是旅行商问题的一个经典变种：多目标旅行商问题(MOTSP)。

目前解决多目标旅行商问题的传统解法以基于迭代的启发式及演化计算的方法为主，如NSGA-II、MOEA/D、PLS、MOGLS及它们的变种方法等。这类方法的优点在于能够通过利用专家知识精心设计较好的算子并经过大量迭代得到较优的解，而缺点在于迭代所需运行时间往往较长。

近年来深度强化学习在求解单目标NP-hard组合优化问题上有了突破性的发展，利用这种方法只需要训练一个神经网络模型便能对任意给定的算例利用该模型构造出令人满意的解且这种模型对不同规模算例还具有很好的泛化能力，在求解时间上具有极大的优势。于是便有研究者对多目标旅行商问题利用权重分解的方法先将该多目标优化问题转化为多个单目标优化子问题再使用近年来的深度强化学习方法分别对每个单目标优化子问题训练对应的子模型用于求解，最后所有这些子问题通过对应的子模型得到的解能构成多目标优化的帕累托前沿解集。然而，这类方法的劣势在于整体训练强烈依赖于在训练所有子模型之前预先给定的权重，获得的解的质量也依赖于预先给定的权重，对每个权重都无法灵活地适应之前未给出的权重，当新的权重出现时又需要对每个权重对应的新子问题分别训练对应的子模型，这往往需要耗费大量的训练。虽然迁移学习被研究者提出用于加速训练，但是迁移学习要求每次训练求解的子问题的权重足够接近，因此这种方法依然灵活性不足，仅适用于优化求解连续相邻且很接近的子问题的训练。

公开日为2016年04月20日，公开号为CN105512755A的中国专利公开了一种基于分解的多目标分布估计优化方法，其特征在于包括以下内容：1)初始化外部种群EP为空；2)初始化一组权重向量；3)利用权重向量将原多目标优化问题分解为多个单目标优化子问题；4)利用概率向量对每个分解后的子问题建模；5)通过随机采样概率向量分别优化每个单目标问题产生新解；6)保存计算所有的新解到EP中，判断是否满足终止条件如果否则返回步骤3)，如果是则停止，得到所有子问题中的优化解。该专利同样无法灵活地适应之前从未给出的子问题。

发明内容

本发明提供一种基于元学习的深度强化学习求解多目标旅行商问题的方法，从不同学习任务的经验中学习，以更快地学习新任务。

为解决上述技术问题，本发明的技术方案如下：

一种基于元学习的深度强化学习求解多目标旅行商问题的方法，包括以下步骤：

S1：定义多目标旅行商问题；

S2：将多目标旅行商问题按照权重加和的方式分解为一组单目标优化的子问题；

S3：构建基于元学习的深度强化学习算法框架并对深度强化学习算法框架中的元模型进行训练；

S4：对于步骤S2中得到的每一组单目标优化的子问题，所述元模型进行步数的参数微调得到对应的子模型；

S5：利用子模型求解对应的子问题；

S6：所有子问题的解的集合为多目标旅行商问题的解。

本发明在已有的深度强化学习方法基础上引入一种基于元学习的方法，训练一个元模型用于快速适应所有潜在的权重。元学习，也称学会如何学习，是一门系统地观察机器学习方法如何在广泛的不同学习任务中执行的科学，并从不同学习任务的经验中学习，以更快地学习新任务。

优选地，所述步骤S1中：

多目标旅行商问题定义在完全图G＝(V，E)上，其中V代表点集，包含n个要访问的点；E代表边集，包含m个n×n的代价矩阵，即任意两点i，j之间都存在m个不同的代价，如：时间、花费、海拔高度差等，这m个不同代价对应m个不同的优化目标，需要访问图中的所有点且保证每个点仅被访问一次，最终需要找到n个点的排列π并同时优化m个不同的目标函数，其中第k个目标函数如下：

其中

优选地，所述多目标旅行商问题属于多目标优化问题，多目标优化问题的定义：

最优化f(x)＝(f

其中f(x)为由m个不同的目标函数组成的向量，

给定两个m维的目标值向量u，v∈R

优选地，步骤S2中，运用深度强化学习方法求解多目标优化问题的准备工作是使用分解策略将多目标优化问题分解为一组单目标优化的子问题，便可对每个子问题采用深度强化学习方法训练一个模型用于求解，分解策略是一种简单而有效的多目标优化处理策略，MOEA/D算法便是使用分解策略的典型代表算法，对多目标优化问题分解为一组单目标优化的子问题，通过设立N个权重将多目标优化问题分解为N个标量优化子问题。

优选地，所述的分解策略包括线性加权法、切比雪夫分解法和PBI方法。

优选地，所述线性加权法具体为：

对每个权重

最优化

g

因此，可将每个子问题看作一个单目标优化问题。

优选地，使用AM模型作为提取多目标旅行商问题算例特征的深度学习模型，使用Actor-critic算法作为强化学习更新模型参数的算法。AM模型是论文“Attention,learnto solve routing problems！”中提出的可用于求解旅行商问题的深度强化学习模型。

优选地，步骤S3中采用Reptile算法作为元学习算法，目的是为了通过元学习得到能够快速适应任意给定权重得到该子问题对应的子模型。

优选地，步骤S3中训练元模型，具体为：

S3.1：随机初始化元模型的所有参数θ，对该元模型做T

S3.2：，每一步迭代中，根据一个给定的分布Λ采样

S3.3：对每个子模型计算其与元模型的所有参数差值，对所有子模型计算得到的差值取平均得到一个平均差值，用该平均差值乘一个步长∈，得到的值用于更新当前元模型的所有参数，更新后完成元模型的一步迭代；

S3.4：T

优选地，所述分布Λ为均匀分布。

得到具备了快速适应能力的元模型后，给定任意权重，只需要对元模型做少量步数的参数微调即可得到求解该权重的子问题所对应的子模型。微调的过程即把该元模型作为深度强化学习参数更新的初始模型并只需做少量步数的参数更新。微调后得到所有给定权重对应的所有子模型，最后将这些子模型用于推断。给定需要求解的多目标旅行商问题算例，用微调得到的子模型可快速推断出这些给定权重通过深度强化学习方法求解得到的帕累托解集和帕累托前沿。

与现有技术相比，本发明技术方案的有益效果是：

本发明提出了一种更加灵活的基于元学习的深度强化学习方法用于所有权重对应模型的快速适应，本发明方法只需要训练好一个元模型，便能对任意给定的权重只需要对该元模型做少量的参数更新便能快速微调出该权重对应的模型并得到令人满意的解，弥补了现有深度强化学习方法的不足。

附图说明

图1为本发明的方法流程图。

图2为本发明基于元学习的深度强化学习的整体框架示意图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；

对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。

下面结合附图和实施例对本发明的技术方案做进一步的说明。

实施例1

本实施例提供一种基于元学习的深度强化学习求解多目标旅行商问题的方法，如图1和图2，包括以下步骤：

S1：定义多目标旅行商问题；

S2：将多目标旅行商问题按照权重加和的方式分解为一组单目标优化的子问题；

S3：构建基于元学习的深度强化学习算法框架并对深度强化学习算法框架中的元模型进行训练；

S4：对于步骤S2中得到的每一组单目标优化的子问题，所述元模型进行步数的参数微调得到对应的子模型；

S5：利用子模型求解对应的子问题；

S6：所有子问题的解的集合为多目标旅行商问题的解。

所述步骤S1中：

多目标旅行商问题定义在完全图G＝(V，E)上，其中V代表点集，包含n个要访问的点；E代表边集，包含m个n×n的代价矩阵，即任意两点i，j之间都存在m个不同的代价，如时间、花费、海拔高度差等，这m个不同代价对应m个不同的优化目标，需要访问图中的所有点且保证每个点仅被访问一次，最终需要找到n个点的排列π并同时优化m个不同的目标函数，其中第k个目标函数如下：

其中

所述多目标旅行商问题属于多目标优化问题，多目标优化问题的定义：

最优化f(x)＝(f

其中f(x)为由m个不同的目标函数组成的向量，

给定两个m维的目标值向量u，v∈R

步骤S2中使用分解策略对多目标优化问题分解为一组单目标优化的子问题，通过设立N个权重将多目标优化问题分解为N个标量优化子问题。

所述的分解策略包括线性加权法、切比雪夫分解法和PBI方法。

所述线性加权法具体为：

对每个权重

最优化

g

使用AM模型作为提取多目标旅行商问题算例特征的深度学习模型，使用Actor-critic算法作为强化学习更新模型参数的算法。

步骤S3中采用Reptile算法作为元学习算法。

步骤S3中训练元模型，具体为：

S3.1：随机初始化元模型的所有参数θ，对该元模型做T

S3.2：，每一步迭代中，根据一个给定的分布Λ采样

S3.3：对每个子模型计算其与元模型的所有参数差值，对所有子模型计算得到的差值取平均得到一个平均差值，用该平均差值乘一个步长∈，得到的值用于更新当前元模型的所有参数，更新后完成元模型的一步迭代；

S3.4：T

在实际实施过程的元学习阶段中，

所述分布Λ为均匀分布。

在具体实施过程中，为了验证元模型的快速适应效果并测试其泛化能力，共设计了四组对比实验。实验在经典的两目标旅行商问题上进行，旅行商问题中每个点有两个欧式坐标分别对应两个代价矩阵的计算，点的欧式坐标值均从区间[0,1]之间采样或者由标准数据集将每个坐标值归一化到区间[0,1]。为了方便与已有的方法比较，所有实验结果的推断均来自于相同的100个均匀给定权重(即λ

第一组对比实验设计为ML-DAM分别与DAM和DAM(transfer)在MOTSP-20和MOTSP-50上对每个子模型分别做不同步数的参数更新的效果对比。这里的HV参考点均设置为(30,30)。实验结果如表1所示，更优的指标值加粗显示，从该对比结果可以看出ML-DAM的所有指标均为最优。ML-DAM的每个子模型只需要做10步的参数更新，效果便显著优于DAM的每个子模型做上千步的参数更新得到的效果，而与不够灵活的DAM(transfer)对比，ML-DAM不仅拥有随时快速适应任意权重的更好灵活性，而且在做相同步数的参数更新时(尤其在少量步数的参数更新时)依旧体现出了明显更优的效果。

表1

第二组对比实验为体现ML-DAM的元模型泛化能力，实验设计为将ML-DAM在MOTSP-50的算例上训练的元模型分别放在MOTSP-30、MOTSP-80、MOTSP-100的算例上进行微调，而与之对比的DAM和DAM(transfer)则直接分别在MOTSP-30、MOTSP-80、MOTSP-100的算例上进行训练。这里的HV参考点均设置为(60,60)。实验结果如表2所示，更优的指标值加粗显示，从该对比结果可以看出ML-DAM的元模型在快速适应不同规模的算例上具有非常强大的泛化能力，即使在MOTSP-50的算例上训练仍能在MOTSP-30、MOTSP-80、MOTSP-100上均体现出类似第一组对比实验体现的明显更优效果。

表2

第三组对比实验为体现ML-DAM的元模型微调得到的子模型在求解不同规模标准MOTSP算例上的泛化能力，实验设计为将ML-DAM在MOTSP-50的算例上训练的元模型也放在MOTSP-50的算例上进行微调得到的子模型与DAM和DAM(transfer)直接在MOTSP-50的算例上训练得到的子模型在TSPLIB中规模分别为100、150、200的标准测试算例kroAB100、kroAB150、kroAB200上推断得到的结果做对比。这里的HV参考点均设置为(90,90)。实验结果如表3所示，更优的指标值加粗显示，从该对比结果可以看出ML-DAM在MOTSP-50的算例上训练的元模型也在MOTSP-50微调得到的子模型在较大规模的MOTSP标准测试算例上仍相比DAM和DAM(transfer)表现出优秀的快速适应能力。

表3

第四组对比实验为体现ML-DAM的元模型微调得到的子模型在泛化到求解不同规模标准MOTSP算例上相比传统多目标演化算法的优势，实验设计为将第三组实验中ML-DAM对每个子模型微调10步得到的结果再与传统的NSGA-II、MOEA/D、MOGLS算法做对比。对于NSGA-II和MOEA/D，种群规模设为100(与权重分解的权重数目相同)，种群的演化迭代次数设为2000和4000。对于MOGLS，种群的演化迭代次数设为1000，其中每次迭代使用的2-opt算子的最大执行次数设为100。这里的测试算例kroAB100、kroAB150、kroAB200与第三组实验相同，HV参考点也均设置为(90,90)。实验结果如表4所示，更优的指标值加粗显示，从该对比结果可以看出即使ML-DAM在MOTSP-50算例上得到的元模型仅在MOTSP-50算例上对每个子模型仅仅只需微调10步，在求解较大的不同规模算例上的收敛性和计算时间上均显著优于传统的NSGA-II、MOEA/D、MOGLS算法。

表4

相同或相似的标号对应相同或相似的部件；

附图中描述位置关系的用语仅用于示例性说明，不能理解为对本专利的限制；

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。