On the Analysis, Classification and Prediction of Metaheuristic Algorithm Behavior For Combinatorial Optimization Problems

Metaheuristics are successfully applied in many different application domains as they provide a reasonable tradeoff between computation time and achievable solution quality. However, choosing an appropriate algorithm for a certain problem is not trivial, as problem characteristics can change remarkably for different instances and the performance of a metaheuristic may vary considerably for different parameter settings. Therefore it always takes qualified algorithm experts to select and tune a metaheuristic algorithm for a specific application. This process of algorithm selection and parameter tuning is frequently done manually and intuitively and requires a large number of empirical tests. In this contribution the authors propose several measurement values to characterize the search behavior of different metaheuristics for solving combinatorial optimization problems. Based on these measurements algorithms can be classified and models can be learnt to predict the algorithms behavior for new parameter settings. This helps to understand the interdependencies and impacts of parameters, to identify promising parameter values, to formalize the parameter tuning process, and to reduce the number of required test cases.