Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features

Weise, Thomas1; Wang, Xiaofeng2; Qi, Qi3; Li, Bin3,5; Tang, Ke4

2018-12

10.1016/j.asoc.2018.08.030

APPLIED SOFT COMPUTING   影响因子和分区

1568-4946

1872-9681

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 know why. In this paper, we introduce a process which can 1) 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, and 3) 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. (C) 2018 Elsevier B.V. All rights reserved.

Experimentation Benchmarking Optimization Runtime behavior Modeling Clustering Classification

SCI ; EI

英语

其他

Shenzhen Peacock Plan[KQTD2016112514355531]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Interdisciplinary Applications

WOS:000450124900027

ELSEVIER SCIENCE BV

20183805839396

Approximation algorithms ; Benchmarking ; Classification (of information) ; Decision trees ; Learning systems ; Models ; Open source software ; Open systems ; Optimization ; Parameter estimation ; Software testing ; Traveling salesman problem ; Trees (mathematics)

Computer Software, Data Handling and Applications:723 ; Computer Applications:723.5 ; Information Sources and Analysis:903.1 ; Mathematics:921

COMPUTER SCIENCE

Web of Science

1.Hefei Univ, Fac Comp Sci & Technol, Inst Appl Optimizat, Jinxiu Dadao 99, Hefei 230601, Anhui, Peoples R China
2.Hefei Univ, Jinxiu Dadao 99, Hefei 230601, Anhui, Peoples R China
3.Univ Sci & Technol China, Sch Comp Sci & Technol, USTC Birmingham Joint Res Inst Intelligent Comput, Hefei 230027, Anhui, Peoples R China
4.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen, Peoples R China
5.Univ Sci & Technol China, Sch Informat Sci & Technol, Dept Elect Engn & Informat Sci, Hefei 230027, Anhui, Peoples R China

Weise, Thomas,Wang, Xiaofeng,Qi, Qi,et al. Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features[J]. APPLIED SOFT COMPUTING,2018,73:366-382.

Weise, Thomas,Wang, Xiaofeng,Qi, Qi,Li, Bin,&Tang, Ke.(2018).Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features.APPLIED SOFT COMPUTING,73,366-382.

Weise, Thomas,et al."Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features".APPLIED SOFT COMPUTING 73(2018):366-382.