Runtime Analysis on the (1+1) Memetic Algorithms

Abstract

A Memetic Algorithm is a population-based meta-heuristic algorithm that combines an Evolutionary Algorithm with a set of local search algorithms. The successful experimental results have verified the advantages of Memetic Algorithms, and also motivate the desire for a better understanding of Memetic Algorithms by using runtime analysis. In the last decade, theoretical studies of Memetic Algorithms have achieved remarkable progress, but still lag behind experiments. In particular, three approaches have been studied extensively in experiments, but few studies in theory can explain their successes. This research will provide theoretical evidences towards explaining why these approaches are successful. The main results of this thesis are: 1. Why using dynamic mutation probabilities in Memetic Algorithms gains success? We will show the benefits of hybridizing the dynamic mutation approach with one of two local searches, best-improvement and first-improvement, respectively. In detail, we will firstly show that the algorithm’s ability of escaping from a local optimal solution is crucial because it dominates the time complexity for the algorithm to find a global optimal solution. Then, we will show that hybridizing the dynamic mutation approach with any one of the two local searches greatly enhances the algorithm’s ability of escaping from a local optimal solution. 2. Why using multiple local searches in Memetic Algorithms gains success? We will show that the best local search for Memetic Algorithms to find a global optimal solution on the Clique Problem is instance-specific. Moreover, we will show cases that Memetic Algorithms applying multiple local searches outperform Memetic Algorithms applying a single local search on the Clique Problem. 3. Why changing to a different fitness function gains better results? We will show that a small change of the fitness function can result in a huge performance gap in terms of finding a global optimum solution. We will also show that the fitness function that gives the best results in a Memetic Algorithm on the Clique Problem is instance-specific. Furthermore, we will show that for a given instance, if the best fitness function is unknown, the approach that applies the Memetic Algorithms on different fitness functions iteratively may outperform the approach that applies Memetic Algorithms on a single fitness function.