No.12
智源社区
强化学习组
强
化
学
习
研究
观点
资源
活动
关于周刊
强化学习作为人工智能领域研究热点之一，它在组合优化领域中的应用研究进展与成果也引发了众多关注。为帮助研究与工程人员了解该领域的相关进展和资讯，智源社区结合领域内容，撰写为第12 期《强化学习周刊》。本期周刊整理了近期强化学习在组合优化领域相关的最新论文推荐、研究综述、学术讲座等，以飨诸位。
周刊采用社区协作的模式产生，欢迎感兴趣的朋友们参与我们的工作，一起来推动强化学习社群的分享、学习和交流活动。可以扫描文末的二维码加入强化学习社区群。
本期贡献者：李明，陈斌
论文推荐
强化学习近年来取得了令人瞩目的成就，将其应用于组合优化领域也取得较大的进步。强化学习中，通过状态变化进行组合优化问题的策略选择，以使长期累积的奖励和最大。近年来，该方向已经取得了一系列瞩目的进展，比如多目标优化问题及在线离线组合优化等。故将强化学习应用于组合优化领域具有较大的优势。
强化学习在组合优化领域中的应用越来越多，其在多目标优化、组合优化等方面都有了深入的研究。本次推荐了7篇强化学习在组合优化领域应用的相关论文，主要涉及多目标优化、组合优化、组合优化的实际应用及不确定条件下的组合优化等。
标题：Meta-Learning-based Deep Reinforcement Learning for Multiobjective Optimization Problems（基于元学习深度强化学习的多目标优化问题）了解详情
简介：深度强化学习 (DRL) 最近在解决复杂的组合优化问题方面取得了显著的成效。当这些问题扩展到多目标问题时，现有的 DRL 方法存在训练速度慢、很难灵活有效地适用及处理由目标权重分解确定的多个子问题。基于此，本文提出了一种简洁的基于元学习的 深度强化学习方法。它首先通过元学习训练元模型，并将子模型的直接训练过程修改为元模型的微调过程，从而大大减少了求解子问题所需的梯度更新步骤，增强了基于学习的方法的灵活性和通用性。具体来说，将注意力模型纳入了MOTSP的MLDRL框架中。再构建帕累托模型以解决多目标组合优化问题。通过多目标旅行商问题的计算实验表明该方法优于大多数基于学习和基于迭代的方法，而且在处理不同尺度的问题时具有良好的泛化能力。
论文地址：/pdf/2105.02741.pdf
标题：Efficient Active Search for Combinatorial Optimization Problems（组合优化问题的高效主动搜索）了解详情
简介：近年来，已经提出了许多用于解决组合优化问题的基于机器学习的方法，它们通过强化学习在顺序决策过程中构建解决方案。虽然这些方法可以很容易地与采样和波束搜索等搜索策略相结合，但将它们集成到提供强大搜索指导的高级搜索过程中并不容易。Bello et al.（）提出了主动搜索，它在测试时使用强化学习来调整（训练）模型相对于单个实例的权重。虽然主动搜索很容易实现，但它与最先进的方法相比并不具有竞争力，因为调整每个测试实例的所有模型权重是非常耗时和内存密集的。本文提出并评估了三种在运行时微调组合优化求解技术，用于调整嵌入、增加网络层和调整输出概率的EAS方法以进行有效主动的搜索策略，在搜索过程中只更新一部分参数，而不是更新所有的模型权重。所提出的方法提供了一种简单的方法来显着提高给定模型的搜索性能，并在组合问题上优于最先进的基于机器学习的方法，甚至在车辆路径问题上超过了著名的启发式求解器 LKH3。最后，本文证明了（有效的）主动搜索使学习模型性能得到显著改善。
论文地址：/pdf/2106.05126.pdf
标题：SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems（SOLO：在线搜索，离线学习组合优化问题）了解详情
简介：本文研究组合问题及其在现实世界中的应用，如机器调度，路由和分配。其提出了一种组合强化学习和规划的方法。这种方法同样适用于组合问题的离线和在线变体，其中问题组件（例如调度问题中的作业）不是预先知道的，而是在决策过程中得到的。本文的解决方案非常通用、可扩展，并且利用了问题参数的分布知识。本文将解决方案过程构建为马尔科夫决策过程，并采用深度Q-学习方法，其中状态表示为图形，从而允许训练有素的策略以有原则的方式处理任意变化。虽然学习到的策略在预期中可以很好地工作，但在组合环境中，小的偏差可能会产生重大的负面影响。本文通过在兼容的搜索算法蒙特卡洛树搜索中使用其构建的图卷积策略作为非最优启发式来减轻这些缺点，从而显著提高整体性能。最后，在机器调度和有容量的车辆路径问题上验证了该方法，结果表明，纯Q网络代理提供了近乎实时的动作选择，该组合方法SOLO充分利用了任何可用的时间进行讨论，其得益于其实时的特性，有效地减少了与专用组合优化求解器的差距。最终表明了该方法在计算时间和性能上都优于定制的数学求解器、最新的基于学习的算法和常见的启发式算法。
论文地址：/pdf/2104.01646.pdf
标题：Behavior-based Neuroevolutionary Training in Reinforcement Learning（强化学习中基于行为的神经进化训练）了解详情
简介：神经进化和基于群体的算法在解决经典优化问题方面应用极为成熟并且已成为标准强化学习方法的替代方案。然而，进化方法通常未充分利用收集的状态和价值经验。如果考虑针对具有大量资源成本的现实问题的强化学习，则样本效率至关重要。因此，需要通过经验利用方法来增强进化算法，并有望提供有价值的见解。故本文提出了一种将拓扑变化的神经进化优化与基于价值的强化学习相结合的算法。目标是利用收集到的经验，创建一个样本有效的RL算法适用于现实世界的问题。其通过策略的行为来创建距离和损失函数，并受益于存储的经验和计算的状态值。此外，该方法允许通过无梯度进化算法和基于代理的优化对行为进行建模并在行为空间中执行定向搜索。以整合不同的方法来生成和优化代理策略，从而创造出多样化的人口。在标准基准和定制化构建的现实世界问题中的研究结果表明，组合方法可以提高进化方法的样本效率和学习速度。
论文地址：/pdf/2105.07960.pdf
标题: Learning Heuristics for the TSP by Policy Gradient (用策略梯度启发式解决旅行推销员问题)了解详情
简介:该研究的目的是提供一个很有趣的见解，即如何将高效的机器学习算法与现有的启发式程序相结合来解决组合优化问题。更具体地说，他们扩展了神经组合优化框架来解决旅行推销员问题（TSP）。在这个框架中，城市坐标被用作输入，神经网络通过强化学习来预测城市排列组合的分布。他们提出的框架与上述框架的不同之处在于 因为他们没有使用长短期记忆（LSTM）架构，他们选择设计自己的评价网络来计算旅游长度的基线，从而使学习更有效率。更重要的是，他们用著名的2-opt启发式进一步加强了解决方法。结果表明，本文所提出的框架本身的性能通常与高性能启发式方法（ORTools)一样好。当该框架配备了一个简单的2-opt程序时。它可以超越这些启发式方法，并在二维欧几里得图上取得接近最优的结果。在二维欧几里得图上达到接近最优的结果。这表明他们的方法基于机器学习技术可以学习到好的启发式方法，一旦用简单的局部搜索来加强这些启发式方法就会产生很好的结果。
论文地址：https://hanalog.polymtl.ca/wp-content/uploads//11/cpaior-learning-heuristics-6.pdf
标题: Reversible Action Design for Combinatorial Optimization with Reinforcement Learning（具有强化学习的组合优化的可逆动作设计）了解详情
简介：图上的组合优化问题 (COP) 是最优化中的一个基本挑战。强化学习 (RL) 近年来已成为解决这些问题的新框架，并取得了良好的效果。然而，大多数 RL 解决方案采用贪婪的方式逐步构建解决方案，因此不可避免地对动作序列产生不必要的依赖，并且需要大量针对特定问题的设计。本文提出了一个通用的 RL 框架，它不仅展示了最先进的经验性能，而且还可以推广到各种类型的 COP。具体来说，本文将状态定义为问题实例的解决方案，将动作定义为对该解决方案的扰动。并利用图神经网络 (GNN) 来提取给定问题实例的潜在表示以进行状态动作编码，然后应用深度 Q-learning 来获得一个策略，通过翻转或交换顶点标签来逐步优化解决方案。在最大值k-Cut 和旅行社问题中的实证研究表明，其性能改进通过一组基于学习和启发式基线实现。
论文地址：/pdf/2102.07210.pdf
标题: Contingency-Aware Influence Maximization: A Reinforcement Learning Approach（应急感知影响最大化：强化学习方法）了解详情
简介：影响力最大化 (IM) 问题旨在在社交网络中寻找使影响力传播最大化的种子节点子集。本研究关注 IM 问题的一个子类，其中节点在被邀请时是否愿意成为种子是不确定的，称为应急感知影响最大化。这种应急意识 IM 对于资源匮乏社区的非营利组织的应用至关重要（例如，传播疾病预防意识）。尽管取得了初步成功，但将解决方案推广到更多社区的一个主要实际障碍是贪婪算法的巨大运行时间以及该领域非营利组织缺乏高性能计算（HPC）——每当有新的社交媒体出现时网络，非营利组织通常没有 HPC 来重新计算解决方案。受此启发并受到使用强化学习 (RL) 解决图组合优化的一系列工作的启发，本文将问题形式化为马尔可夫决策过程 (MDP)，并使用 RL 在历史上看到的网络上学习 IM 策略，并推广到在测试阶段运行时间可以忽略不计的看不见的网络。为了充分利用提出目标问题的特性，本文提出了两项技术创新来改进现有方法，包括状态抽象和基于理论的奖励塑造。实证结果表明，该方法在测试阶段的运行时间可以忽略不计的情况下，对突发事件感知 IM 的影响与最先进的方法一样高。
论文地址：/pdf/2106.07309.pdf
综述
基于深度强化学习的组合优化研究进展了解详情
简介：组合优化问题广泛存在于国防、交通、工业、生活等各个领域,但随着实际应用中问题规模的不断扩大、求解实时性的要求越来越高，传统运筹优化方法在组合优化问题的在线求解上面临很大的计算压力。近年来随着深度强化学习的迅猛发展及其在围棋、机器人等领域所展现出的强大的学习能力与序贯决策能力，基于深度强化学习的组合优化方法成为近年来的研究热点，涌现出了一系列相关研究。鉴于此，本文对近年来基于深度强化学习的组合优化方法的研究进展进行了综述介绍。其对当前该领域的研究进行了分类研究和分析总结，列举了基于Pointer Network的端到端方法、基于图神经网络的端到端方法、多目标优化方法、深度强化学习改进的局部搜索方法等基于深度强化学习解决组合优化问题的代表性算法，对其算法原理、优化性能、优缺点进行了对比和介绍,并对各类方法未来的研究方向进行了分析。
论文地址：
.cn/cn/article/doi/10.16383/j.aas.c51
用图网络解决组合优化: 运用和网络建构的综述了解详情
简介:本文是由瑞典研究院和瑞典皇家理工合作完成。现有的解决图上组合优化问题的方法存在很多问题，尤其是需要对每个问题进行算法设计，实际问题在很多情况下都会出现。因此在理论计算机科学的实践方面，如计算复杂性，需要得到解决。为此，此文调查了机器学习解决组合优化问题研究的相关发展。此文还组织并比较了与学习解决组合优化问题有关的结构。特别关注电信领域及其不断发展的真实网络和研究网络。本文还指出未来的研究必须全面解决几个相关方面的问题：可扩展性、适应性、通用性、运行时间和自动化。
论文地址：
/pdf/.11081.pdf
组合优化中的强化学习研究综述了解详情
简介：许多用于解决组合优化问题的传统算法都涉及使用手工设计的启发式方法，以依次构建解决方案。这类启发式算法是由领域专家设计的，由于问题的困难性，此类方法往往是次优的。强化学习（RL）提出了一个很好的替代方法，通过训练一个代理在监督或自我监督的方式来自动搜索这些启发式算法。在这篇综述探讨了最近的进展，应用RL框架的硬组合问题。本研究综述为运筹学和机器学习社区提供了必要的背景，并展示了推动该领域向前发展的工作。在文中展现了最近提出的RL方法，列出了每个问题的改进时间表，并与传统算法进行了比较，研究表明RL模型可以成为解决组合优化问题的一个很有希望的方向。
论文地址：
/pdf/.03600.pdf
学术讲座
港科大&西南财经 | 鲁棒鲁棒与随机优化系列讲座第12期（7月8日 14:00~15:00 腾讯会议）了解详情
简介：本系列讲座由西南财经大学工商管理学院主办，此次讲座主题为“Supermodularity in Two-Stage Distributionally Robust Optimization"，由香港科技大学助理教授戚瑾做主题演讲。
如果你正在从事或关注 强化学习研究、实现与应用，欢迎加入“智源社区-强化学习-交流群”。在这里，你可以：
学习前沿知识、求解疑难困惑
分享经验心得、展示风貌才华
参与专属活动、结识研究伙伴
扫描下方二维码，加入强化学习兴趣群。
