Exploring Structural Similarity in Fitness Landscapes via Graph Data Mining: A Case Study on Number Partitioning Problems

Mingyu Huang, Ke LiIJCAI 2023 · DOI

Abstract: This study investigates the structural consistency of fitness landscapes in optimization problems by modeling them as Local Optima Networks (LONs). Using graph data mining and network representation learning, we demonstrate that landscapes of the Number Partitioning Problem (NPP) exhibit predictable topological patterns across different dimensions. These structural similarities are shown to be strong predictors of meta-heuristic solver performance, offering a formal basis for solving complex optimization problems by analogy.

Introduction

In black-box optimization, a common heuristic is "solving by analogy": if an algorithm performs well on a small-scale problem, it is expected to scale to larger versions. However, formally quantifying the similarity between fitness landscapes of different dimensions is challenging. This paper addresses this gap by applying graph data mining to Local Optima Networks (LONs) to measure structural closeness and predict solver performance.

Modeling Fitness Landscapes as Networks

The search space of a Number Partitioning Problem (NPP) is transformed into a concrete graph where nodes represent local optima and edges represent transitions between them. This LON construction allows for the application of traditional network science metrics.

Figure 1: Comprehensive overview of LON structural metrics across problem dimensions (n), including node/edge counts, density, clustering coefficients, search steps, and basin sizes.

As shown in Figure 1, high-level graph features such as density, clustering coefficients, and assortativity exhibit monotonic variations as the problem dimensionality increases. This suggests that the underlying "search logic" of the landscape is preserved even as the problem scales.

Structural Consistency Across Dimensions

A key finding is that fitness landscapes are not chaotic; they maintain deep topological patterns. By using Network Representation Learning (NRL) techniques like HOPE and Feather, the authors compressed these complex graphs into high-dimensional vectors to calculate a formal similarity metric (Sim).

Figure 2: Evolution of the RCC metric across different problem dimensions (d), demonstrating the structural shift and consistency as dimensionality increases.

Figure 2 illustrates how specific network features (like RCC) evolve predictably with dimension $d$. The similarity between neighboring dimensions (e.g., $n=27$ and $n=30$) reached as high as 0.96, while disparate dimensions showed significantly lower correlation. This confirms that structural "closeness" in the latent space reflects the physical similarity of the optimization challenges.

Predicting Solver Performance

The study validated these structural findings by testing Simulated Annealing (SA) on the generated instances. The results indicated that structural closeness directly predicts performance closeness. Using quadratic regression, the structural similarity metric explained the relative performance of SA with an $R^2$ score between 0.84 and 0.90. Furthermore, low-level node features like PageRank and Betweenness Centrality showed a Spearman's correlation ($\rho > 0.8$) with the actual fitness of local optima, meaning the network's topology effectively maps the location of high-quality solutions.

Conclusion

By bridging fitness landscape analysis with graph data mining, this research provides a quantitative framework for understanding problem similarity. While currently focused on Number Partitioning Problems, the methodology offers a path toward automatic algorithm selection by "reading" the graph structure of unseen problem instances to predict the most effective solver.

Summary updated

BibTeX
@inproceedings{huang2023exploring,
  author = {Mingyu Huang and Ke Li},
  title = {{Exploring Structural Similarity in Fitness Landscapes via Graph Data Mining: A Case Study on Number Partitioning Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/621},
}
Figure