We present a memetic algorithm (\maa) approach for finding a Hamiltonian
cycle in a Hamiltonian graph. The \ma is based on a proven approach to the
Asymmetric Travelling Salesman Problem (\atspp) that, in this contribution, is
boosted by the introduction of more powerful local searches. Our approach also
introduces a novel technique that sparsifies the input graph under
consideration for Hamiltonicity and dynamically augments it during the search.
Such a combined heuristic approach helps to prove Hamiltonicity by finding a
Hamiltonian cycle in less time. In addition, we also employ a recently
introduced polynomial-time reduction from the \hamcyc to the Symmetric \tsp,
which is based on computing the transitive closure of the graph. Although our
approach is a metaheuristic, i.e., it does not give a theoretical guarantee for
finding a Hamiltonian cycle, we have observed that the method is successful in
practice in verifying the Hamiltonicity of a larger number of instances from
the \textit{Flinder University Hamiltonian Cycle Problem Challenge Set}
(\fhcpsc), even for the graphs that have large treewidth. The experiments on
the \fhcpscc instances and a computational comparison with five recent
state-of-the-art baseline approaches show that the proposed method outperforms
those for the majority of the instances in the \fhcpsc.

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

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

A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph

In the field of derivative-free optimization, both of its main branches, the
deterministic and nature-inspired techniques, experienced in recent years
substantial advancement. In this paper, we provide an extensive computational
comparison of selected methods from each of these branches. The chosen
representatives were either standard and well-utilized methods, or the
best-performing methods from recent numerical comparisons. The computational
comparison was performed on five different benchmark sets and the results were
analyzed in terms of performance, time complexity, and convergence properties
of the selected methods. The results showed that, when dealing with situations
where the objective function evaluations are relatively cheap, the
nature-inspired methods have a significantly better performance than their
deterministic counterparts. However, in situations when the function
evaluations are costly or otherwise prohibited, the deterministic methods might
provide more consistent and overall better results.

本文对无导数优化的确定性技术和基于自然启发的技术进行了计算比较，并通过对五个基准测试集的结果分析表明，在目标函数评估相对较便宜的情况下，基于自然启发的方法比确定性方法具有更好的性能，然而，在目标函数评估昂贵或被禁止的情况下，确定性方法可能提供更为一致和总体更好的结果。