Nov, 2022

领域无关的动态规划：组合优化通用状态空间搜索

PDF
TL;DR本研究提出了动态规划问题的一种新的模型化方法：基于动态规划描述语言（DyPDL）的领域无关动态规划（DIDP），并开发了基于状态空间搜索的成本代数 A * 求解器（CAASDy）。 通过实验比较 CAASDy 与商业混合整数规划和约束规划求解器，我们表明 CAASDy 在许多常见问题类上优于 MIP 和 CP 模型。
发现论文，激发创造
  • 领域无关动态规划

    基于动态规划 (DP) 的领域无关动态规划 (DIDP) 模型具有优于其他方法的性能，通过引入七种 DIDP 求解器和对 11 种组合优化问题类别的基准测试，实验证明 DIDP 在大部分问题类别中优于混合整数规划 (MIP) 和约束规划 (CP)。

    Jan, 2024

  • 离散与连续状态 MDP 的符号动态规划

    本文介绍了符号动态规划（SDP）技术的扩展，提供了一种能够处理离散和连续状态的马尔可夫决策过程（DC-MDP）的最优解决方案，在 XADD 中引入约束基剪枝以提高效率。SDP 与 XADD 用于声明性问题的自动规划，从而实现在 DC-MDP 的线性和非线性函数中生成最优解决方案。

    Feb, 2012

  • 一种新的动态分布式规划方法：应用于 DPDP 问题

    本研究提出了一种新的动态分布式规划方法，能够考虑智能体引入的动作变化，以适应环境中的变化。该方法使用遗传算法满足约束条件生成新的规划，每当智能体的动作集发生变化时，就会生成一个新的规划，使其考虑新引入的动作及旧规划中未执行的动作，以及新引入动作引起的新初始状态。通过具体案例展示并证明了该方法的实用性。

    Feb, 2024

  • 约束马尔可夫决策过程的原始对偶方法

    本文提出了一种基于采样的原始 - 对偶算法来解决带约束的马尔科夫决策过程，通过应用正则化策略迭代来改善策略，应用次梯度上升来保持约束。在弱耦合结构的情况下，通过嵌入式分解方法，能够显著减少问题的维度。将算法应用于多产品库存管理和多类队列调度，并表明它产生优于现有启发式算法的控制。

    Jan, 2021

  • 结合强化学习和约束编程用于组合优化

    本文介绍了一种基于深度强化学习和约束编程的混合算法，应用于复杂的组合优化问题，并在实验中成功运用于旅行商问题和投资组合优化问题，表现优于单独的深度强化学习和约束编程算法，同时也达到了与工业级求解器相竞争的水平。

    Jun, 2020

  • 通过线性规划对偶解决大规模马尔可夫决策问题

    本文提出了一种针对状态空间较大的 MDP 问题进行优化的方法，该方法基于一小组策略的占用度量的低维度逼近，并提出了一个有效的算法，可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失，并在队列应用中展示了该方法的有效性。

    Jan, 2019

  • SPUDD：使用决策图的随机计划

    本研究提出了一种基于代数决策图来表示价值函数和策略的 Markov 决策过程的值迭代算法，并将其应用于波西网络和 ADDs 表示的大规模 MDPs 中，相较于树形结构表示方式大幅降低了节点数量。

    Jan, 2013

  • DPMS：基于 ADD 的符号化方法解决广义 MaxSAT 问题

    通过代数决策图和级联项目 - 加入树生成器，我们提出了动态规划最大可满足性（DPMS），一种解决广义 MaxSAT 问题的新方法。实证结果表明，DPMS 能够快速解决某些问题，由此开辟了未来更多研究的新方向。

    May, 2022

  • 大规模马尔可夫决策问题的线性规划

    本文考虑了控制具有大状态空间的马尔可夫决策过程以最小化平均成本的问题，并使用线性规划和两种方法，即基于随机凸优化和基于约束采样的方法，将性能提高到与在低维策略类中的任何策略相比的最佳水平。

    Feb, 2014

  • 线性规划方法求解约束部分可观测的马尔可夫决策过程

    使用 LP 模型结合基于网格的近似方法生成近似策略，研究了解决限制观测 Markov 决策过程的效果。结果表明，LP 模型可有效地生成有限和无限时间段问题的近似策略，同时提供将各种附加约束集成到模型中的灵活性。

    Jun, 2022