VRP-TSP系列论文4 2023-06-29 组合优化 暂无评论 226 次阅读 # 前置知识 ## 多目标优化问题（Multiobjective Optimization Problems） 对于大多数多目标优化问题，其各个目标往往是相互冲突的，因此不可能使得所有的目标同时达到最优，而是一组各个目标值所折衷的解集，称之为Pareto最优集。以下为一些基本定义(以最小化优化问题为例)：  ## 分解方法解决MOP 在许多多目标优化的实际应用中，决策者需要近似PF来选择最终的优选解。 基于分解的方法是一类求解PF的方法，该方法第一次系统地被提出是在2007年由Qingfu Zhang等人提出(MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition) PF的近似可以分解为若干个标量目标优化子问题。这是许多用于逼近PF的传统数学规划方法背后的基本思想。有许多的聚合方法，最流行的是加权法、切比雪夫法和边界交叉聚合方法。 以权重求和法为例，每个子问题λ，由一组权重向量λ =(λ1，λ2，⋯，λm) 表示，每个权值分量λi 分别对应第i个目标向量，λi>=0且λi之和为1。这样一个子问题是单目标优化问题。  假设目标有两个 f1 和 f2，子问题λ的最优解的目标向量是A，对应图中的A点，A在PF上。 以此类推，求解不同的子问题得到它们的帕累托最优向量，就可以组成近似PF。  >[多目标进化算法(MOEA)概述_subtask的博客-CSDN博客](https://blog.csdn.net/qithon/article/details/72885053#comments) >[多目标优化--MOEAD算法笔记_研行笔录的博客-CSDN博客](https://blog.csdn.net/qq_36317312/article/details/107245961) --- # Deep Reinforcement Learning for Multiobjective Optimization 《用于多目标优化的深度强化学习》 IEEE transactions on cybernetics, 2020, 51(6): 3103-3114. 期刊 中科院1区 JCR1区  ## Abstract: + 本文提出了一种使用深度强化学习（DRL）解决多目标优化问题（MOP）的端到端框架，我们将其称为基于 DRL 的多目标优化算法（DRL-MOA）。 + 采用分解的思想将MOP分解为一组标量优化子问题。然后，每个子问题都被建模为神经网络。 + 所有子问题的模型参数根据基于邻域的参数传递策略和DRL训练算法协同优化。通过训练的神经网络模型可以直接获得帕累托最优解。 + 具体来说，本文使用 DRL-MOA 方法通过将子问题建模为指针网络来解决多目标旅行商问题 (MOTSP)。 ## DRL-MOA总体框架 + 分解方法：加权求和法 通过加权和方法将原始MOP转化为N个标量优化子问题。   + 子问题的求解 子问题被建模为神经网络。 但如果每个子问题都单独训练，费时，所以作者的方法：通过基于邻域的参数传递策略以协作方式求解N个标量优化子问题 通过权重向量划分子问题的过程，可以观察到两个相邻的子问题可能具有非常接近的最优解，因为它们的权向量是相邻的。因此，子问题可以通过其邻近子问题的知识来解决和帮助。   然后，将第 (i − 1) 个子问题中获得的最佳网络参数 [ω* λi−1 , b* λi−1 ] 设置为第 i 个子问题的网络训练。  + 整体流程： 每个子问题都通过DRL算法进行建模和求解，并且所有子问题都可以通过传递网络权值来依次求解。这样，最终就可以根据得到的模型来近似PF。  ## 解决MOTSP 我们发现这个框架可以用在很多问题上，把子问题求解器替换成相应的基于学习的方法即可。因此，作者以MOTSP为例，介绍如何建模和求解MOTSP的子问题。 Formulation:  Model: 修改后的Pointer Network  Train: Actor–Critic  一旦子问题的所有模型都训练完毕，就可以通过模型的简单前向传播直接输出帕累托最优解。 ## 实验 在双目标 TSP 上进行了测试，双目标的设定有两种： + Euclidean Instances：两个成本函数均由欧几里德距离定义。 + Mixed Instances：第一个成本函数仍然由代表真实城市位置的两点之间的欧几里德距离定义，该距离是具有 x 坐标和 y 坐标的二维输入。第二个旅行成本由一维输入定义。城市 i 的一维输入可以解释为城市 i 的海拔高度。 训练数据：由 [0, 1] 的均匀分布生成 测试数据：随机生成以及TSPLIB库中的 kroA and kroB。模型在 40 个城市的 MOTSP 实例上进行训练，并用于近似 40、70、100、150 和 200 个城市测试实例的 PF。 对比方法：与 NSGA-II 和 MOEA/D 的经典 MOEA 进行比较。 ### 混合型双目标 TSP 的结果 HV:“hypervolume (HV)”一个性能指标   可以有效地扩展到具有不同数量城市的双目标 TSP。 如图 6-8 所示，随着城市数量的增加，NSGA-II 和 MOEA/D 的竞争对手难以收敛，而 DRL-MOA 则表现出更好的收敛能力。 通过增加迭代次数，NSGA-II和MOEA/D甚至表现出更好的收敛能力。然而，大量的迭代会导致大量的计算时间。 ### 欧几里得型双目标 TSP 的结果   ### 扩展到具有更多目标的 MOTSP  还有其它实验暂略： 与基于Local search的方法的比较 参数传递策略的有效性 不同数量城市对训练的影响 ## 总结 + 分解方法求解MOP，用DRL改进 + 迁移学习，减少子问题求解器的训练量 + 泛化能力强、求解速度快，优于经典方法。 ---- # Meta-Learning-Based Deep Reinforcement Learning for Multiobjective Optimization Problems 《基于元学习的多目标优化问题深度强化学习》 IEEE Transactions on Neural Networks and Learning Systems, 2022. 期刊 中科院1区 JCR1区  ## Abstract: + 本文提出了一种简洁的基于元学习的 DRL 方法。它首先通过元学习训练元模型。元模型通过一些更新步骤进行微调，以导出相应子问题的子模型。然后相应地构建帕累托前沿。 + 与其他基于学习的方法相比，我们的方法可以大大缩短多个子模型的训练时间。由于元模型的快速和良好的适应性，可以派生出更多的子模型，从而提高找到的解决方案的质量和多样性。 + 多目标旅行商问题和带时间窗的多目标车辆路径问题的计算实验证明了我们的方法相对于大多数基于学习和基于迭代的方法的优越性。 ## Motivation: 迁移学习策略的缺点在于灵活性。它仅适合训练权重向量彼此紧密相邻的子模型。而且，子模型的所有参数都需要保存。当出现大量新子问题或目标数量很大时，它不太适用。在后一种情况下，任何两个子问题的目标权重向量可能彼此远离。因此，这种缺点促使我们提出一种新的 MOP 学习范式。  所提出的用于求解 MOP 的 MLDRL 的想法是训练一个元模型，该模型可以快速适应优化与新权重相对应的看不见的目标函数。元模型一旦经过有效训练，本身就不会有助于 PF 的构建。相反，它被用作最佳初始策略，通过更多的梯度更新来微调不同的子模型。 PF 是通过聚合子模型生成的解来构建的。 ## 总体框架  由元学习过程、微调过程和推理过程组成 + 元学习过程 元学习算法：Reptile Reptile是openai在FOMAML(The first-order MAML)基础上提出的一种一阶MAML，reptile不再计算梯度，而是采用一种soft的方式利用 $\theta_i$来求 $\theta$  本文元学习训练流程  + 子问题求解方法 AM模型，Actor-critic训练  + 微调和推理的流程 使用分解策略，生成 N 个权重向量来定义 N 个单目标问题。对于每个权重向量，经过算法2的一些更新步骤后，获得最终的子模型。第 5-11 行对应于推理阶段。对于 K 个测试用例，每种情况都会找到其对应的 PF。通过使用贪婪策略生成相对的近似帕累托最优向量。然后更新PF。  ## 实验 MOTSP实验 数据：随机生成 对比方法：  分解数量：We set the number of weight vectors N in PF construction to 100. 指标：HV是综合评价PF收敛性和多样性的重要指标，而NDS在HV值接近时反映了PF的多样性。一般来说，HV或NDS越大，表明相应算法的性能越好。 + 对比实验  + 泛化实验  + 子模型处理不同规模实例的泛化能力 使用 MOTSP50 训练和微调 T 步骤的元模型派生的子模型应用于三个常用的基准 MOTSP 实例：kroAB100、kroAB150 和 kroAB200    ML-AM获得的子模型在应对大规模实例方面表现出出色的泛化能力。即使 T 很小，MLAM 也优于大多数竞争对手，尤其是那些经典的 MOEA。 ML-AM得到的子模型可以生成具有良好多样性的PF。图 7 说明了所得的非支配解构成了 PF 的广泛分布。 ML-AM（推理阶段）的运行时间比所有 MOEA 快得多。 关于MOVRPTW的实验略，结果差不多，与baseline比又快又好。 ## 总结 + 分解方法求解MOP，DRL求解子问题，和上一篇李凯文的套路类似 + 元学习，减少子问题求解器的训练量，同时提高泛化性和快速收敛，这个比李凯文的迁移学习好，也是本文的主要贡献吧。 + 与经典方法和基于学习的方法（包括上一篇方法）相比，表现更好。 --- # PARETO SET LEARNING FOR NEURAL MULTI-OBJECTIVE COMBINATORIAL OPTIMIZATION 《神经多目标组合优化的帕累托集学习》 ICLR 2022  ## Abstract: 在这项工作中，我们概括了神经组合优化的思想，并开发了一种基于学习的方法来近似给定 MOCO 问题的整个 Pareto 集，而无需进一步的搜索过程。我们提出了一个单一的偏好条件模型来直接生成任何权衡偏好的近似帕累托解，并设计一种有效的多目标强化学习算法来训练该模型。我们提出的方法可以被视为广泛使用的基于分解的多目标进化算法（MOEA/D）的基于学习的扩展。它使用单个模型来适应所有可能的偏好，而其他方法则使用有限数量的解来近似帕累托集。实验结果表明，我们提出的方法在多目标旅行商问题、多目标车辆路径问题和多目标背包问题上在解决质量、速度和模型效率方面显着优于其他方法。 contributions: + 我们提出了一种新颖的神经多目标组合优化方法，通过单个偏好条件模型来近似整个帕累托集。它允许决策者无需任何搜索工作即可获得任何首选的权衡解决方案。 + 我们开发了一种高效的端到端强化学习算法，可以同时针对所有不同的偏好训练单一模型，并开发了一种简单而强大的主动适应方法来处理分布外问题实例。 + 我们对不同设置的MOTSP、MOVR和MOKP进行了综合实验。结果表明，我们提出的方法可以有效地成功逼近不同问题的帕累托集。它在解决方案质量、速度和模型效率方面也显着优于其他方法。 >自己的理解： 仍然是基于分解的方法求解MOP 所谓的偏好是分解时的权重向量，就是这个 $\lambda_i$  不过不再像其它方法一样，每个权重向量对应一个子问题，子问题单独求出最优解去近似PF。 而是当作一个问题，就是输入权重向量和问题实例，输出最优解。这样一个模型训练好之后，我们可以认为它拟合了PF。 另一角度，我们可以把它理解成一个超级强的子问题求解器，就是不同权重向量分成的子问题，它都可以求解。 ## 总体架构： 图 1：偏好条件神经多目标组合优化： a) 该模型将问题实例作为输入。 b) 决策者将他们对不同目标的偏好分配给模型。 c）模型通过快进推理直接生成具有不同权衡的近似帕累托解。在此示例中，问题是具有两个要最小化的成本目标的 MOTSP。生成的解决方案P1、P2和P3是两个成本目标之间不同的最优权衡。理想的模型可以为 Pareto 前沿上所有可能的最优权衡生成解决方案，并且不会生成诸如 P4 之类的较差解决方案。  ## Neuro MOCO Model AM作为基础的encoder-decoder model， 在decoder部分，参数会以$\lambda$ 为条件进行调整 自回归方式输出解  图 3：偏好条件神经 MOCO 模型： a) 输入是问题实例 s（例如graph）。 b) 共享注意力编码器将实例 s 转移到一组嵌入中。 c）所有节点的嵌入将被解码器以不同的偏好多次使用。 d) MLP 将偏好 λ 作为输入，并生成解码器的参数。 e) 偏好条件注意解码器针对不同的偏好直接生成不同的近似帕累托解。 可训练参数位于注意力编码器和 MLP 模型中。  ## 训练 + Loss 我们可以为每个偏好λ定义一个加权切比雪夫标量成本  对于给定的实例 s，我们的目标是最小化所有偏好的预期成本：  + RL 对于给定的实例 s 和特定的偏好 λ，我们使用 REINFORCE来估计偏好条件标量成本的梯度：  该梯度可以通过蒙特卡罗采样来估计。  训练流程：  ## 实验 + 对比方法 遗传算法： MOGLS（Jaszkiewicz，2002）是一种多目标遗传局部搜索算法 NSGAII（Deb 等人，2002）是一种基于 Pareto 优势的多目标遗传算法 MOEA/ D (Zhang & Li, 2007) 是一种基于分解的多目标进化算法。 两种基于学习的方法： DRL-MOA（Li et al., 2020）分解具有不同偏好的 MOCO 并构建指针网络（Vinyals et al., 2015；Bello et al., 2017） ）来解决每个子问题 AM-MOCO 是我们提出的模型的多模型变体，它为每个子问题构建注意力模型（Kool et al., 2019）。 + 双目标优化  + 三目标优化  ## 结论 + 分解方法求解MOP，大的策略上和前两篇文章一样。 + 把所有子问题用一个求解器来解决，文章的说法是通过单个偏好条件模型来近似整个帕累托集 + encoder-decoder，基于AM，自回归 + REFINFORCE优化定义的loss 标签: 组合优化 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭