Xin Yao - Unpacking and Understanding Evolutionary Algorithms

Abstract: Theoretical analysis of evolutionary algorithms (EAs) has made significant progresses in the last few years. There is an increased understanding of the computational time complexity of EAs on certain combinatorial optimisation problems. Complementary to the traditional time complexity analysis that focuses exclusively on the problem, e.g., the notion of NP-hardness, computational time complexity analysis of EAs emphasizes the relationship between algorithmic features and problem characteristics. The notion of EA-hardness tries to capture the essence of when and why a problem instance class is hard for what kind of EAs. Such an emphasis is motivated by the practical needs of insight and guidance for choosing different EAs for different problems. This talk first introduces some basic concepts in analysing EAs. Then the impact of different components of an EA will be studied in depth, including selection, mutation, crossover, parameter setting, and various interactions among them. Such theoretical analyses have revealed some interesting results, which might be counter-intuitive at the first sight. Finally, some future research directions of evolutionary computation will be discussed.