论文标题
哈密顿完成问题的不断发展的测试实例
Evolving test instances of the Hamiltonian completion problem
论文作者
论文摘要
由于多种原因，预测和比较图实例上的算法性能是具有挑战性的。首先，通常没有标准的实例来基准性能。其次，使用现有的图生成器会导致难度限制，并且所得图通常不足以得出合理的结论。这就是为什么最近的工作提出了一种新方法，以使用进化算法来生成各种实例。然后，我们可以分析结果图，并获得关键见解，以了解哪些属性与算法性能最相关。我们还可以填补实例空间中观察到的空白，以生成具有以前看不见的功能组合的图形。使用两个不同的求解器，即Concorde TSP求解器和多开始的本地搜索算法，将此方法应用于哈密顿完成问题的实例空间。
Predicting and comparing algorithm performance on graph instances is challenging for multiple reasons. First, there is usually no standard set of instances to benchmark performance. Second, using existing graph generators results in a restricted spectrum of difficulty and the resulting graphs are usually not diverse enough to draw sound conclusions. That is why recent work proposes a new methodology to generate a diverse set of instances by using an evolutionary algorithm. We can then analyze the resulting graphs and get key insights into which attributes are most related to algorithm performance. We can also fill observed gaps in the instance space in order to generate graphs with previously unseen combinations of features. This methodology is applied to the instance space of the Hamiltonian completion problem using two different solvers, namely the Concorde TSP Solver and a multi-start local search algorithm.
