Feature-Based Diversity Optimization for Problem Instance Classification
This work addresses the problem of analyzing heuristic performance for researchers in optimization, though it is incremental as it builds on existing evolutionary and feature-based methods.
The paper tackles the challenge of understanding heuristic search behavior by developing a framework to generate diverse sets of hard or easy problem instances for a given heuristic, specifically showing that combinations of two or three features effectively classify TSP instances for 2-OPT.
Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Traveling Salesperson problem. In this paper, we present a general framework that is able to construct a diverse set of instances that are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances that are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.