Predicting Metaheuristic Performance on Graph Coloring Problems Using Data Mining
Predicting Metaheuristic Performance on Graph Coloring Problems Using Data Mining
复制标题
使用数据挖掘预测图着色问题的元启发式性能
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
N. Insani
中科院分区：
文献类型：
--
作者：
K. Smith‐Miles;Brendan Wreford;Leo Lopes;N. Insani
本章说明了使用数据挖掘方法在整个实例空间中更好地理解元启发式的优点和缺点的好处。以图着色为例，我们演示了如何学习和可视化实例特征与算法性能之间的关系。实例空间(在这种情况下是所有图着色实例的集合)被表征为高维特征空间，每个实例由被选择作为实例硬度指示的一组度量来概括。我们展示了不同的实例生成器如何生成具有各种属性的实例，以及算法的性能如何依赖于这些属性。基于一组测试实例，我们揭示了实例空间中的广义边界，在该边界下，算法可以很好地执行。该边界称为实例空间中的算法足迹。我们展示了如何使用数据挖掘方法来可视化足迹并将其边界与实例的属性相关联。通过这种方式，我们可以开始很好地理解一组算法的优缺点，并确定开发新的混合方法的机会，这些方法利用组合的优势并提高广泛的实例空间的性能。
This chapter illustrates the benefits of using data mining methods to gain greater understanding of the strengths and weaknesses of a metaheuristic across the whole of instance space. Using graph coloring as a case study, we demonstrate how the relationships between the features of instances and the performance of algorithms can be learned and visualized. The instance space (in this case, the set of all graph coloring instances) is characterized as a high-dimensional feature space, with each instance summarized by a set of metrics selected as indicative of instance hardness. We show how different instance generators produce instances with various properties, and how the performance of algorithms depends on these properties. Based on a set of tested instances, we reveal the generalized boundary in instance space where an algorithm can be expected to perform well. This boundary is called the algorithm footprint in instance space. We show how data mining methods can be used to visualize the footprint and relate its boundary to properties of the instances. In this manner, we can begin to develop a good understanding of the strengths and weaknesses of a set of algorithms, and identify opportunities to develop new hybrid approaches that exploit the combined strength and improve the performance across a broad instance space.