Towards the Inferrence of Structural Similarity of Combinatorial Landscapes
This work addresses the challenge of applying analogy-based heuristics in combinatorial optimization, though it is incremental in leveraging existing graph mining techniques.
The paper tackled the problem of inferring structural similarity between combinatorial optimization landscapes to predict solver effectiveness, and found concrete evidence of similarity within the same problem classes across neighboring dimensions.
One of the most common problem-solving heuristics is by analogy. For a given problem, a solver can be viewed as a strategic walk on its fitness landscape. Thus if a solver works for one problem instance, we expect it will also be effective for other instances whose fitness landscapes essentially share structural similarities with each other. However, due to the black-box nature of combinatorial optimization, it is far from trivial to infer such similarity in real-world scenarios. To bridge this gap, by using local optima network as a proxy of fitness landscapes, this paper proposed to leverage graph data mining techniques to conduct qualitative and quantitative analyses to explore the latent topological structural information embedded in those landscapes. By conducting large-scale empirical experiments on three classic combinatorial optimization problems, we gain concrete evidence to support the existence of structural similarity between landscapes of the same classes within neighboring dimensions. We also interrogated the relationship between landscapes of different problem classes.