Designing and characterising fitness landscapes with various operators

Stochastic optimisers such as Evolutionary Algorithms, Estimation of Distribution Algorithm are suitable methods when problems are highly complex and deterministic algorithms cannot be expected to produce acceptable results. Generally, when the search process produces the optimised solutions, there is no indication how successful the search has been. In previous work, we introduced Predictive Diagnostic Optimisation (PDO), a local-search-based solver which can predict with certain accuracy the quality of local optima and that can help decide which of the initial solutions is appropriate to optimise. The neighbourhood created by the swap operator was used in exploration of the search space and the number of predictors created is a metric for the homogeneity of the landscape. The advantage of PDO is that it provides information regarding the difficulty of the search landscape alongside the optimisation results. In this work we extend PDO by employing three more neighbourhood operators to allow a comparison between the performances of different types of local search. Each neighbourhood operator has its own group of predictors and the difficulty in predicting the local optima is quantified by a new metric, the prediction error. To provide an assessment of the characterisation ability for the algorithm, a set of landscapes with various degrees of difficulty has been designed by manipulating the matrices of the test problems instances. We show that the metric is able to identify the degree of difficulty that we expect the landscapes to pose for the employed local search operators.