chapter four

4 Evolutionary algorithms

 

This chapter covers

  • The inspiration for evolutionary algorithms
  • Solving problems with evolutionary algorithms
  • Understanding the life cycle of a genetic algorithm
  • Designing and developing a genetic algorithm to solve optimization problems

4.1 What is evolution?

When you look around at life on Earth, nothing popped into existence fully formed. Everything alive today is the result of a long chain of tiny changes that accumulated over millions of years. This implies that the physical and cognitive characteristics of every living organism are a result of fitting to its environment for survival.

We often make the mistake of thinking evolution is a neat line from “primitive ancestor” to “modern form”. In reality, evolution is messy and branching. Offspring are not perfect clones of their parents; they inherit a mix of genes with small random changes (mutations). At any moment, a species is actually a cloud of variants, not one single clean shape. You only see big, obvious differences when you zoom far out in time and compare averages across thousands of generations.

Figure 4.1 depicts this reality of actual evolution versus the commonly mistaken linear version.

So, evolution is both simple and wild: variation is constantly produced, most variants disappear, and some variants thrive. In doing so, nature essentially “searches” enormous spaces of possibility for the best fit.

4.2 Problems applicable to evolutionary algorithms

4.3 Genetic algorithm: Life cycle

4.4 Encoding the solution spaces

4.4.1 Binary encoding: Representing possible solutions with zeros and ones

4.5 Creating a population of solutions

4.6 Measuring fitness of individuals in a population

4.7 Selecting parents based on their fitness

4.7.1 Steady state: Replacing a portion of the population each generation

4.7.2 Generational: Replacing the entire population each generation

4.7.3 Roulette wheel: Selecting parents and surviving individuals

4.8 Reproducing individuals from parents

4.8.1 Single-point crossover: Inheriting one part from each parent

4.8.2 Two-point crossover: Inheriting more parts from each parent

4.8.3 Uniform crossover: Inheriting many parts from each parent

4.8.4 Bit-string mutation for binary encoding

4.8.5 Flip-bit mutation for binary encoding

4.9 Populating the next generation

4.9.1 Exploration vs. exploitation

4.9.2 Stopping conditions

4.10 Configuring the parameters of a genetic algorithm

4.11 Use cases for evolutionary algorithms

4.12 Summary of evolutionary algorithms