Sep, 2022

NP 难问题中启发式近似算法的（不）可扩展性

PDF
TL;DR本文探讨利用神经网络逼近完全信息启发式函数的可行性，发现对于 NP 难问题，其网络规模可能呈指数级上升，并建议研究方向转向寻找其他机器学习与启发式搜索相结合的方法。
a* algorithmcombinatorial optimizationheuristic functionneural networkmachine learning
发现论文，激发创造
  • 学习 A * 启发式算法

    本文利用神经演算法推导出高效的启发式路径搜索算法，结合 Dijkstra 算法和 A * 算法中的一致的启发函数，并将其推广应用于图形中的路径搜索问题，结果表明相较于 Dijkstra 算法，应用基于学习到的 A * 算法中的启发函数的改进搜索在无损质量的情况下，实现了大幅的速度提升。

    Apr, 2022

  • 图神经网络启发式算法无法在解决如 Max-Cut 等组合优化问题中超越贪婪算法

    Schuetz 等人提出了一种使用图神经网络作为启发式方法来解决各种组合优化问题的方案，该方法通过样例实例对网络进行训练，并应用广泛使用的技术来评估其成功的能力，尽管报告的结果只比梯度下降略有改善，但该方法承诺具有高度可伸缩性和计算成本线性。

    Oct, 2022

  • 使用神经网络学习特定搜索空间启发式算法

    建议并评估了一种系统，该系统学习了一种用于基于正向搜索的满足经典规划的神经网络启发式函数。我们的系统从头开始学习目标估计器，并生成训练数据。通过反向回归搜索或通过反向搜索从给定或猜测的目标状态生成培训数据。

    Jun, 2023

  • 用神经算法进行组合优化的推理

    本研究针对组合优化问题，提出了在深度学习模型训练前进行预训练以利用相关算法对于解决 TSP 问题具有提升作用的算法推理方法，并证明该方法能够优于传统深度学习模型。

    May, 2023

  • 在神经网络中将最优路径搜索与任务相关的学习结合

    使用神经网络表示寻径问题并将路径的成本值转化为神经元的连接权重，结合网络学习机制，在线自适应更新权重以解决具有不同要求的任务。该算法复杂度与 Bellman Ford 算法相同，可用于寻找最优路径和路径增强。

    Jan, 2022

  • 优化规划启发式算法，以排序而非估算目标开销

    本论文重新审视了启发式函数在规划中的模仿学习中的必要和充分条件，并针对给定的前向搜索算法的变体提出了一族基于排名的损失函数。另外，从学习理论的角度讨论了为什么优化成本 - 目标 h * 是不必要困难的。实验比较在多样化的问题集上明确地支持了得出的理论。

    Oct, 2023

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

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

    Apr, 2017

  • 非阻塞批处理 A*（技术报告）

    使用神经网络进行启发式搜索的研究中，Non-Blocking Batch A* 提出了一种新的边界次优方法，该方法可以懒惰地以批处理方式计算神经网络启发式搜索结果，同时使用非神经网络启发式搜索算法进行扩展。在实验中发现，相较于当前阻塞式替代方法，这种微妙但重要的变化可以显著减少扩展次数，而性能与批处理计算的神经网络和快速的非神经网络启发式算法之间的信息差有关。

    Aug, 2022

  • 学习图搜索启发式

    PHIL (Path Heuristic with Imitation Learning) is a neural architecture and training algorithm that uses imitation learning and graph representation learning to discover graph search and navigation heuristics from data, reducing the number of explored nodes by 58.5% compared to state-of-the-art methods on benchmark datasets and allowing for fast planning in time-critical robotics domains.

    Dec, 2022

  • 图卷积网络与引导树搜索的组合优化

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些 NP 困难问题，并在四个 NP 困难问题和五个数据集上进行了评估，结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018