KDDJun, 2022

学习控制组合优化中的局部搜索

PDF
TL;DR本研究提出了一种名为 NeuroLS 的本地搜索算法控制器，采用深度图神经网络作为策略模型，通过计算机学习方法，能够优于已知常规搜索控制器和最新的机器学习方法，在求解 NP 困难度的组合优化问题中，取得了比较理想的结果。
combinatorial optimization problemslocal search algorithmsmarkov decision processgraph neural networkmachine learning
发现论文，激发创造
  • RELS-DQN: 一种用于组合优化的稳健高效的局部搜索框架

    本文介绍了一种名为 RELS-DQN 的深度强化学习（DQN）框架，其利用消息传递神经网络（MPNN）实现局部搜索行为，且在保证运行时和内存效率的同时，在各种应用中实现比本地搜索算法和现有 DQN 模型更高的解值。

    Apr, 2023

  • 在图上学习组合优化算法

    本文介绍了结合强化学习和图嵌入的方法，使用元算法来解决 NP-hard 组合优化问题和图上的最小点集覆盖、最大割和旅行商问题等优化问题。

    Apr, 2017

  • 迭代局部搜索

    这是一篇关于 Iterated Local Search 的综述论文，介绍了该通用元启发式算法在求解组合优化问题中的应用，通过构建本地最优解的序列来获得较好的解决方案，并实现了问题特定属性的详细利用。

    Feb, 2001

  • 混合整数规划的大邻域搜索算法学习

    该论文提出了一种基于学习的大邻域搜索 (LNS) 方法来解决混合整数规划 (MIP)，该方法使用神经潜水模型来表示变量分配的可能性分布，并使用非自用 MIP 求解器生成初始分配，并使用诱导学习来训练神经网络选择在每个步骤中寻找下一个分配的邻域。

    Jul, 2021

  • 线性时间内学习在实际图中求解组合优化问题

    本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架，可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题，该方法可在线性运行时间内输出近似解，并且能够推广到多种情况，包括 NP 困难的问题和真实世界的图。

    Jun, 2020

  • 使用贝叶斯优化的本地政策搜索

    提出了一种基于概率模型的算法，结合了强化学习中的政策梯度方法和贝叶斯优化中的权衡充分利用已知信息选取样本的方法，实现了通过主动挑选样本来提高梯度估计的效果和减少样本复杂度，具有广泛的应用前景。

    Jun, 2021

  • 揭示学习式局部搜索启发式的界限：你是否最强大的弱者？

    我们对神经网络与组合优化中的局部搜索算法进行了综合研究，结果表明基于禁忌搜索的简单学习启发式方法在性能和泛化性方面超过了最先进的学习启发式方法，挑战了现有假设，并为组合优化的未来研究和创新开辟了新的方向。

    Oct, 2023

  • 利用潜在空间搜索的组合优化与策略适应

    使用强化学习构建基于启发式方法的优化算法，通过预训练具有多样性的策略分布来优化搜索过程，在三个经典问题上实现了更好的性能和泛化能力。

    Nov, 2023

  • 如何评估机器学习方法在组合优化中的应用：以旅行商问题为例

    本文研究基于深度学习和强化学习的旅行商问题的新模型和架构，强调机器学习在解决组合优化问题方面的限制，并提出了一种新的度量标准 ROD 以回答两个基本问题。

    Sep, 2019

  • 局部搜索是神经架构搜索的一个极强的基准

    本文介绍一种新增的局部搜索 (Local Search) 算法，用于在多目标 (网络精度与复杂度) 条件下，对神经网络进行结构搜索。同时，本文提供两种基准数据集 MacrosNAS-C10 和 MacrosNAS-C100，并将所提出的算法与随机搜索 (RS) 和进化算法 (EAs) 进行了比较，发现局部搜索算法在相同数据集下具备比随机搜索更高的性能。

    Apr, 2020