TY - GEN
T1 - Unpacking and understanding evolutionary algorithms
AU - YAO, Xin
PY - 2012
Y1 - 2012
N2 - 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 chapter 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 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. © 2012 Springer-Verlag.
AB - 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 chapter 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 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. © 2012 Springer-Verlag.
KW - IEEE Transaction
KW - Evolutionary Algorithm
KW - Problem Size
KW - Evolutionary Computation
KW - Memetic Algorithm
UR - http://www.scopus.com/inward/record.url?scp=84865041579&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-30687-7_4
DO - 10.1007/978-3-642-30687-7_4
M3 - Conference paper (refereed)
SN - 9783642306860
T3 - Lecture Notes in Computer Science
SP - 60
EP - 76
BT - Advances in Computational Intelligence : IEEE World Congress on Computational Intelligence, WCCI 2012, Brisbane, Australia, June 10-15, 2012. Plenary/Invited Lectures
A2 - LIU, Jing
A2 - ALIPPI, Cesare
A2 - BOUCHON-MEUNIER, Bernadette
A2 - GREENWOOD, Garrison W.
A2 - ABBASS, Hussein A.
PB - Springer Berlin Heidelberg
T2 - 2012 IEEE World Congress on Computational Intelligence, WCCI 2012
Y2 - 10 June 2012 through 15 June 2012
ER -