Dec, 2023

基于交换的网络设施位置问题深度强化学习

PDF
TL;DR该研究论文提出了一个基于交换的框架和一种新颖的深度强化学习模型，用于解决图上的设施位置问题和设施重新定位问题。与手工启发式方法相比，该方法在复杂图数据集上表现出更好的解决方案质量和运行时间，同时引入了一种图生成过程，以模拟带有需求的现实世界城市道路网络，为经典问题的大规模数据集构建提供了便利。这一综合了交换法和深度强化学习的方法对于解决图上设施位置问题的实际挑战具有重要意义。
facility location problemsmachine learning methodsp-median problemfacility relocation problemreinforcement learning model
发现论文，激发创造
  • 演化度量下的设施定位

    使用时间依赖动态设施定位问题来研究不断演变的网络，该模型强调主体关系的突发变化，而不是持续演变的基础网络。我们提供的近似算法可获得更好的拟合解。

    Mar, 2014

  • 资源受限的深度强化学习

    为了优化城市资源分配，本文研究了基于 Deep RL 方法对于资源分配的约束条件以及对模拟器的表现

    Dec, 2018

  • 设施选址问题中局部搜索算法的简化分析

    本文研究了度量实例的本地搜索算法，针对设备位置问题：无容量设备位置问题（UFL），以及 $k$-median，$k$-center 和 $k$-means 的无容量版本。

    Sep, 2008

  • 利用深度强化学习解决二次分配问题

    通过深度强化学习的方法解决 Quadratic Assignment Problem（QAP）的 Koopmans-Beckman 公式，使用双指针网络（double pointer network）在选择下一个设施放置位置和上一个位置放置设施之间交替，并通过 A2C 算法在一系列合成实例上进行模型训练。在样本外测试中，我们的解决方案与高质量的局部搜索基线相比，平均准确率达到了 97.5%，在 1.2% 的实例中表现优于基线。

    Oct, 2023

  • 旅行商问题学习范式

    探讨学习典范对旅行推销员问题的深度神经网络训练的影响，研究发现相较于受控实验的有标记数据的 SL 模型，强化学习（RL）模型对于变量大小的图形具有更好的紧急普遍性并是学习新组合问题的规模无关解算器的重要组成部分。

    Oct, 2019

  • 基于局部搜索的移动设施定位问题的近似算法

    探讨 “移动设施位置” 问题，在公共度量空间中移动设施以减少总体成本，并使用一种基于局部搜索的近似算法，实现任意常数 ε>0 的（3+ε）- 近似度。

    Jan, 2013

  • 设施定位问题的机制设计：一份调查报告

    综述了近几十年来在人工智能和经济学交叉领域中解决设施选址问题的近似机制设计研究，包括问题的各种变体和方法以及未来研究的方向。

    Jun, 2021

  • 基于深度强化学习和图神经网络的光可组合数据中心网络感知计算和内存分配

    采用深度强化学习方法，通过图神经网络模型实现网络资源的分配，该方法比现有的最佳启发式算法达到更高的接受率；即使在未适当训练的情况下，可以在规模比训练时大 $10^2$ 倍的数据中心网络中保持高性能。

    Oct, 2022

  • 生产线上的设备重新分配

    研究多阶段设施重新分配问题，包括在离线和在线两种情况下算法的设计和性能证明，提出了一种可实行的策略证明机制并给出最优性证明。

    Mar, 2021

  • 学习增强的在线设施选址

    本文研究使用学习增强算法解决在线设施定位问题，在实际数据上验证该算法的性能并与当前最佳在线算法进行比较，结果表明该算法具有不错的竞争比率和适用性。

    Jul, 2021