Identifying Features of Fitness Landscapes and Relating Them to Problem Difficulty

I Moser, M Gheorghita, A Aleti

    Research output: Contribution to journalArticleResearchpeer-review

    12 Citations (Scopus)

    Abstract

    Complex combinatorial problems are most often optimised with heuristic solvers, which usually deliver acceptable results without any indication of the quality obtained. Recently, predictive diagnostic optimisation was proposed as a means of characterising the fitness landscape while optimising a combinatorial problem. The scalars produced by predictive diagnostic optimisation appear to describe the difficulty of the problem with relative reliability. In this study, we record more scalars that may be helpful in determining problem difficulty during the optimisation process and analyse these in combination with other well-known landscape descriptors by using exploratory factor analysis on four landscapes that arise from different search operators, applied to a varied set of quadratic assignment problem instances. Factors are designed to capture properties by combining the collinear variances of several variables. The extracted factors can be interpreted as the features of landscapes detected by the variables, but disappoint in their weak correlations with the result quality achieved by the optimiser, which we regard as the most reliable indicator of difficulty available. It appears that only the prediction error of predictive diagnostic optimisation has a strong correlation with the quality of the results produced, followed by a medium correlation of the fitness distance correlation of the local optima.

    Original languageEnglish
    Pages (from-to)407-437
    Number of pages31
    JournalEvolutionary Computation
    Volume25
    Issue number3
    DOIs
    Publication statusPublished - 1 Sep 2017

    Keywords

    • combinatorial optimisation
    • fitness landscapes
    • local search
    • Search space characterisation

    Cite this