Feb, 2024

在哈密顿图中寻找哈密顿回路的记忆算法

PDF
TL;DR我们提出了一种基于变异算法的方法，用于在 Hamilton 图中找到 Hamilton 循环。该方法基于解决非对称旅行推销员问题的已有方法，通过引入更强大的局部搜索进行优化。我们的方法还引入了一种策略，对所考虑的 Hamilton 图进行稀疏化处理，并在搜索过程中进行动态增加。这种综合的启发式方法有助于在较短时间内找到 Hamilton 循环以证明 Hamiltonicity。此外，我们还使用了最近提出的从 Hamilton 循环到对称旅行推销员问题的多项式时间归约方法，基于计算图的传递闭包。尽管我们的方法是元启发式算法，即不能给出找到 Hamilton 循环的理论保证，但我们观察到该方法在实践中成功验证了 Flinder 大学 Hamilton 循环问题挑战集（FHCPSC）中更多实例的 Hamiltonicity，即使对于具有大树宽的图形也是如此。在 FHCPSC 实例上的实验证明以及与最近的五种最先进的基准方法的计算比较表明，所提出的方法在 FHCPSC 的大多数实例中优于其他方法。
memetic algorithmhamiltonian cyclehamiltonicityheuristic approachcomputational comparison
发现论文，激发创造
  • 使用图神经网络寻找哈密顿回路

    通过小型消息传递图神经网络在临界状态下预测 Erdos-Renyi 随机图上的哈密顿回路，相较于现有的手工启发式方法，训练单个 GPU 大约 2.5 小时后性能表现更好，这种训练方法相较于手工设计的启发式算法具有较快的训练速度和较少的问题特定知识要求，并且通过使用监督学习算法在人工构建的问题实例上进行训练，避免了使用现有求解器产生的监督信号干扰，最终模型在更大规模图形上具有良好的泛化表现。

    Jun, 2023

  • 循环突变：通过循环归纳进化排列

    研究演化算法在排列问题和映射问题上的应用，提出了一种新的变异算子 “cycle mutation”，并且利用新的排列距离度量方法进行问题特征分析和应用实验，结果表明 cycle mutation 适用于映射和分配问题，对于旅行商问题有一定局限性，并且相对于常用替代方案对局部最优解的稳健性更好。

    May, 2022

  • 高维空间哈密顿圈聚类

    本文提出了一种新的聚类框架，结合全局结构和局部结构解决聚类算法中伪标签生成和异常点检测问题，扩展了传统聚类方法的应用领域。实验证明，该方法表现优异。

    Apr, 2023

  • 使用适应等级遗传算法，通过 Hajós 构造法构建长度为 5 的对称环

    通过引入具有创新性的基于排名的遗传算法中的重新组合和变异运算符，将 Hajos Join 作为重新组合运算符，独立顶点的识别成为突变运算符，成功地解决了使用无非 Hajos 构造仅从阶数为 3 的完全对称有向图构造出对称 5 顶点的问题。

    Oct, 2022

  • 概率路径哈密顿蒙特卡罗

    本文提出了第一步: Probabilistic Path HMC，该算法可以在具有错综复杂结构的空间中进行采样分布，并使用该算法对一些结构复杂的空间（如 Phylogenetic Trees）进行了有效实现。

    Feb, 2017

  • MAA*: 解决分散式 POMDPs 的启发式搜索算法

    本文介绍了多智能体 A*（MAA*），这是第一种完整的和最优的启发式搜索算法，可用于解决具有有限时间视野的分散式部分可观测马尔可夫决策问题（DEC-POMDP）。该算法适用于在随机环境中操作的合作代理组的最优计划的计算，例如多机器人协调、网络流量控制或分布式资源分配。

    Jul, 2012

  • 多旅行商问题的有效迭代二阶段启发式算法

    本文研究了旅行商问题的扩展 —— 多旅行商问题（mTSP），并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明，该算法在多目标下均优于现有启发式算法。

    Jan, 2022

  • CITS：一种基于同步伊辛树搜索算法的组合优化问题求解算法

    本文提出了一种基于模拟退火的启发式搜索算法，在搜索空间上通过展开马尔可夫链到递归深度树来寻找最优解，利用连续表示的自旋状态和正则化项以及振荡子的动力学来探索选定的树节点周围的搜索空间，并在 NP - 困难问题（MAX-CUT）上验证了该算法与半定规划、模拟退火和相干 Ising 机的比较实验中能够在较少的迭代次数内获得更优解的优越性。

    Mar, 2022

  • 非对称旅行商问题的相变和骨架

    本文研究了 ATSP 中的相变现象，发现随着城市间距离精度的提高，问题的最优解成本和计算成本都会出现急剧的变化。这些结果有助于更好地生成 ATSP 问题实例。

    Jun, 2011

  • 模拟非稀疏哈密顿量的量子算法

    文中提出了一种基于量子随机存取存储器（qRAM）的算法，可以模拟不一定稀疏的哈密顿量动力学，并通过一种线性组合的量子行走实现了多项式对数精度，最后证明了该算法可以作为一个单元实现子程序，同时实现量子线性系统求解器，对于两种应用都具有 Θ(√𝑁) 的复杂度。

    Mar, 2018