Runtime analysis of evolutionary algorithms with complex fitness evaluation mechanisms

Evolutionary algorithms (EAs) are bio-inspired general purpose optimisation methods which are applicable to a wide range of problems. The performance of an EA can vary considerably according to the problem it tackles. Runtime analyses of EAs rigorously prove bounds on the expected computational resources required by the EA to solve a given problem. A crucial component of an EA is the way it evaluates the quality (i.e. fitness) of candidate solutions. Different fitness evaluation methods may drastically change the efficiency of a given EA. In this thesis, the effects of different fitness evaluation methods on the performance of evolutionary algorithms are investigated. A major contribution of this thesis is the first runtime analyses of EAs on bi-level optimisation problems. The performances of different EAs on The Generalised Minimum Spanning Tree Problem and The Generalised Travelling Salesperson Problem are analysed to illustrate how bi-level problem structures can be exploited to delegate part of the optimisation effort to problem-specific deterministic algorithms. Different bi-level representations are considered and it is proved that one of them leads to fixed-parameter evolutionary algorithms for both problems with respect to the number of clusters. Secondly, a new mathematical tool called the level-based theorem is presented. The theorem is a high level analytical tool which provides upper bounds on the runtime of a wide range of non-elitist population-based algorithms with independent sampling and using sophisticated high arity variation operators such as crossover. The independence of this new tool from the objective function allows runtime analyses of EAs which use complicated fitness evaluation methods. As an application of the level-based theorem, we conduct, for the first time, runtime analyses of non-elitist genetic algorithms on pseudo-Boolean test functions and also on three classical combinatorial optimisation problems. The last major contribution of this thesis is the illustration of how the level-based theorem can be used to design genetic algorithms with guaranteed runtime bounds. The well-known graph problems Single Source Shortest Path and All-Pairs Shortest Path are used as test beds. The used fitness evaluation method is tailored to incorporate the optimisation approach of a well known problem-specific algorithm and it is rigorously proved that the presented EA optimises both problems efficiently. The thesis is concluded with a discussion of the wider implications of the presented work and future work directions are explored