Inspired from nature, evolutionary algorithms have been proven effective and unique in different real world applications. Comparing to traditional algorithms, its parallel search capability and stochastic nature enable it to excel in search performance in a unique way. In this chapter, evolutionary algorithms are reviewed and discussed from concepts and designs to applications in bioinformatics. The history of evolutionary algorithms is first discussed at the beginning. An overview on the state-of-the-art evolutionary algorithm concepts is then provided. Following that, the related design and implementation details are discussed on different aspects: representation, parent selection, reproductive operators, survival selection, and fitness function. At the end of this chapter, real world evolutionary algorithm applications in bioinformatics are reviewed and discussed.
Evolutionary algorithms draw inspiration from nature. An evolutionary algorithm starts with a randomly initialized population. The population then evolves across several generations. In each generation, fit individuals are selected to become parent individuals. They cross-over with each other to generate new individuals, which are subsequently called offspring individuals. Randomly selected offspring individuals then undergo certain mutations. After that, the algorithm selects the optimal individuals for survival to the next generation according to the survival selection scheme designed in advance. For instance, if the algorithm is overlapping (De Jong, 2006), then both parent and offspring populations will participate in the survival selection. Otherwise, only the offspring population will participate in the survival selection. The selected individuals then survive to the next generation. Such a procedure is repeated again and again until a certain termination condition is met (Wong, Leung, & Wong, 2010). Figure 1 outlines a typical evolutionary algorithm.
Major components of a typical evolutionary algorithm
In this book chapter, we follow the unified approach proposed by De Jong (De Jong, 2006). The design of evolutionary algorithm can be divided into several components: representation, parent selection, crossover operators, mutation operators, survival selection, and termination condition. Details can be found in the following sections.