Genetic Algorithm and its advances in embracing memetics

Abstract

A Genetic Algorithm (GA) is a stochastic search method that has been applied successfully for solving a variety of engineering optimization problems which are otherwise difficult to solve using classical, deterministic techniques. GAs are easier to implement as compared to many classical methods, and have thus attracted extensive attention over the last few decades. However, the inherent randomness of these algorithms often hinders convergence to the exact global optimum. In order to enhance their search capability, learning via memetics can be incorporated as an extra step in the genetic search procedure. This idea has been investigated in the literature, showing significant performance improvement. In this chapter, two research works that incorporate memes in distinctly different representations, are presented. In particular, the first work considers meme as a local search process, or an individual learning procedure, the intensity of which is governed by a theoretically derived upper bound. The second work treats meme as a building-block of structured knowledge, one that can be learned and transferred across problem instances for efficient and effective search. In order to showcase the enhancements achieved by incorporating learning via memetics into genetic search, case studies on solving the NP-hard capacitated arc routing problem are presented. Moreover, the application of the second meme representation concept to the emerging field of evolutionary bilevel optimization is briefly discussed.