2023/12/05 by Mingyu Huang, Ke Li, Huang, Mingyu +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Artificial Intelligence (cs.AI) #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #Data Visualization and Analytics #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2312.02720
openalex publication_date 2023/12/05 · openalex created_date 2023/12/08 · openalex updated_date 2026/07/28
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.