Fitness Landscapes and Problem Difficulty in Evolutionary Algorithms: From Theory to Applications

Above many successes of evolutionary algorithms in solving computationally hard optimisations problems, a major challenge in practice remains how to select/construct the best suited algorithm when solving a problem. The well-known no free lunch theorem rules out the possibility of developing one best algorithmgenerally suitable for solving all problems. Within the realm of algorithm selection in general, the problem becomes how can we characterise problem hardness with reference to evolutionary algorithms (EAs). For the first time, this chapter rigorously derives a problem hardness measure from a theoretical difficulty measure widely used in complexity theory of EAs. Furthermore, the proposed measure is applied to construct an offline optimisation algorithm and an online optimisation algorithm. On one hand, the measure is incorporated with a machine learning algorithm for parameter tuning and achieves powerful performance. On the other hand, an adaptive algorithm framework is proposed and shows promising results. We argue that the proposed measure is general, yet powerful as an indicator of EA-hardness, and contribute to the goal of constructing better suited algorithms for solving problems.