Fitness landscape-based analysis of nature-inspired algorithms

Crossley, Matthew James (2014) Fitness landscape-based analysis of nature-inspired algorithms. Doctoral thesis (PhD), Manchester Metropolitan University.

Preview

Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (13MB) | Preview

Abstract

As the number of nature-inspired algorithms increases so does the need to characterise these algorithms. A rigorous process to characterise algorithms helps practitioners decide which algorithms may offer a good fit for their given problem. One approach is to relate the characteristics of a problem's associated fitness landscape with the performance of an algorithm. The aim of this thesis is to capitalise on the notion of fitness landscape characteristics as a technique for analysing algorithm performance, and to provide a novel algorithm- and problem-independent methodology that can be used to present the strengths and weaknesses of an algorithm. The methodology was tested by developing a portfolio of six nature-inspired algorithms commonly used to solve continuous optimisation problems. This portfolio includes the performance of these algorithms with parameters both “out of the box" and after they have been tuned using an automated tuning technique. Each of the algorithms shows a different “resilience" profile to the landscape characteristics, and responds differently to the tuning process. In order to provide a more practical way to utilise the portfolio an automated “ranking" methodology based on two machine learning techniques was developed. Using estimates of the fitness landscape characteristics on benchmark problems, the best algorithm to use is estimated, and compared with the actual performance of each algorithm. While results show that predicting algorithm performance is difficult, the results are promising, and show that this is an area worth exploring further. This methodology has significant advantages over the current practice of demonstrating novel algorithm performance on benchmark problems, most importantly offering a practical, generalised overview of the algorithm to a potential practitioner. Choosing to use a technique such as the one demonstrated here when presenting a novel algorithm could greatly ease the problem of algorithm selection.