Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features
Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features
复制标题
从实验数据、算法设置和实例特征中自动发现算法和问题实例行为的集群及其原因
DOI：
10.1016/j.asoc.2018.08.030
复制
发表时间：
2018-12
影响因子：
8.7
通讯作者：
Ke Tang
中科院分区：
文献类型：
--
作者：
Thomas Weise;Xiaofeng Wang;Qi Qi;Bin Li;Ke Tang
在启发式优化和机器学习领域，实验是评估算法设置性能和问题难度的方法。域中的大多数算法都是随时算法，这意味着它们可以随着时间的推移提高近似质量。这意味着一个算法最初可能比另一个算法表现得更好，但最终会收敛到更差的解决方案。而不是单一的最终结果，算法的整个运行时行为需要进行比较。此外，研究人员不仅仅想知道哪种算法性能最好，哪种问题最难-她/他想知道为什么。本文介绍了一个过程，该过程可以：1）根据实验中收集的数据，自动对不同问题实例的算法设置过程进行建模; 2）使用这些模型发现算法（或问题实例）行为簇; 3）提出某个算法设置（或问题实例）属于某个算法（或问题实例）行为簇的原因。这些高级结论以决策树的形式呈现，将算法参数（或实例特征）与集群id相关联。我们强调分析算法设置和问题实例的双重性。我们的过程是作为开源软件实现的，并在两个案例研究中进行了测试，最大可满足性问题和旅行商问题。除了它的基本应用程序的原始实验数据，产生集群和“定量”的算法行为的解释，我们的过程还允许“定性”的结论，通过喂养它的数据是标准化的基础上的问题特征或算法参数。它也可以递归地应用，例如，以进一步研究在具有属于最难实例的集群的问题实例上的最佳性能设置的集群中的算法的行为。这两个用例都在案例研究中进行了研究。最后，我们全面分析了我们的方法的缺点，并就如何改进它提出了建议。
In the fields of heuristic optimization and machine learning, experimentation is the way to assess the performance of an algorithm setup and the hardness of problems. Most algorithms in the domain are anytime algorithms, meaning that they can improve their approximation quality over time. This means that one algorithm may initially perform better than another one, but converge to worse solutions in the end. Instead of single final results, the whole runtime behavior of algorithms needs to be compared. Moreover, a researcher does not just want to know which algorithm performs best and which problem is the hardest – she/he wants to knowwhy. In this paper, we introduce a process which can1)automatically model the progress of algorithm setups on different problem instances based on data collected in experiments,2)use these models to discover clusters of algorithm (or problem instance) behaviors, and3)propose causes why a certain algorithm setup (or problem instance) belongs to a certain algorithm (or problem instance) behavior cluster. These high-level conclusions are presented in form of decision trees relating algorithm parameters (or instance features) to cluster ids. We emphasize the duality of analyzing algorithm setups and problem instances. Our process is implemented as open source software and tested in two case studies, on the Maximum Satisfiability Problem and the Traveling Salesman Problem. Besides its basic application to raw experimental data, yielding clusters and explanations of “quantitative” algorithm behavior, our process also allows for “qualitative” conclusions by feeding it with data which is normalized based on problem features or algorithm parameters. It can also be applied recursively, e.g., to further investigate the behavior of the algorithms in the cluster with the best-performing setups on the problem instances belonging to the cluster of hardest instances. Both use cases are investigated in the case studies. We conclude our article by a comprehensive analysis of the drawbacks of our method and with suggestions on how it can be improved.
登录
查看更多内容
DOI：
--
发表时间：
1998-07
期刊：
--
影响因子：
--
作者：
Eugene Fink
通讯作者：
Eugene Fink
一种特征子集选择算法自动推荐方法
影响因子：
5
作者：
Heli Sun;Xueying Zhang;Baowen Xu;Yuming Zhou
通讯作者：
Yuming Zhou
DOI：
10.1007/978-3-642-01020-0_2
发表时间：
2009-04
期刊：
--
影响因子：
--
作者：
T. Stützle
通讯作者：
T. Stützle
DOI：
10.1007/978-1-4757-7107-7
发表时间：
1997-06
期刊：
--
影响因子：
--
作者：
J. Ramsay;Bernard Walter Silverman
通讯作者：
J. Ramsay;Bernard Walter Silverman
DOI：
10.1007/978-1-4899-7687-1_22
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Marco Dorigo;M. Birattari
通讯作者：
Marco Dorigo;M. Birattari