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.
翻译:在图表中预测和比较算法性能由于多种原因具有挑战性。 首先,通常没有标准基准性能实例。 其次,利用现有的图形生成器导致的难度范围有限,因此产生的图表通常不够多样化,无法得出正确的结论。 这就是为什么最近的工作提出了一个新方法,通过使用进化算法产生多种实例。 然后,我们可以分析所产生的图表,并获得关键洞察力,了解哪些属性与算法性能关系最密切。 我们还可以填补在实例空间中观察到的差距,以便生成与先前看不见的特征组合有关的图表。 这种方法将使用两个不同的解算器,即Concorde TSP Solveer和多启动的本地搜索算法,用于汉密尔顿完成问题的示例空间。