FITNESS LANDSCAPE MEASURES FOR ANALYSING THE TOPOLOGY OF THE FEASIBLE REGION OF AN OPTIMISATION PROBLEM

• Nathan van der Westhuyzen Stellenbosch Unit for Operations Research in Engineering, Department of Industrial Engineering, Stellenbosch University, Stellenbosch, South Africa https://orcid.org/0009-0007-5298-109X
• Jan van Vuuren Stellenbosch Unit for Operations Research in Engineering, Department of Industrial Engineering, Stellenbosch University, Stellenbosch, South Africa https://orcid.org/0000-0003-4757-5832

DOI:

https://doi.org/10.7166/34-3-2945

Abstract

Fitness landscape analysis has found numerous applications in industrial engineering, such as estimating optimisation problem complexity, predicting metaheuristic performance, and automating algorithm selection. In these applications, relationships between properties of the fitness landscape and metaheuristic algorithmic appropriateness are often analysed. The ability of a metaheuristic to traverse diverse areas of the feasible region is, however, typically overlooked when analysing algorithmic performance by invoking traditional measures of fitness landscape characteristics. In this paper, we propose three novel fitness landscape measures that are tailored to analyse the structure and degree of connectedness of the feasible region. These measures are related to the degree of neighbourhood feasibility, the size of the feasible region relative to that of the entire search space, and the tightness of the constraints. The significance of these measures is demonstrated in a suite of fitness-landscape analyses. When incorporated into a metaheuristic configuration machine-learning model, the measures yield accuracy improvements up to 6.4%.