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

What is evolution?

When we look at the world around us, we sometimes wonder how everything we see and interact with came to be. One way to explain this is the theory of evolution. The theory of evolution suggests that the living organisms that we see today did not suddenly exist that way, but evolved through millions of years of subtle changes, with each generation adapting to its environment. This implies that the physical and cognitive characteristics of each living organism are a result of best fitting to its environment for survival. Evolution suggests that organisms evolve through reproduction by producing children of mixed genes from their parents. Given the fitness of these individuals in their environment, stronger individuals have a higher likelihood of survival.

Problems applicable to evolutionary algorithms

Genetic algorithm: Life cycle

Encoding the solution spaces

Binary encoding: Representing possible solutions with zeros and ones

Creating a population of solutions

Measuring fitness of individuals in a population

Selecting parents based on their fitness

Steady state: Replacing a portion of the population each generation

Generational: Replacing the entire population each generation

Roulette wheel: Selecting parents and surviving individuals

Reproducing individuals from parents

Single-point crossover: Inheriting one part from each parent

Two-point crossover: Inheriting more parts from each parent

Uniform crossover: Inheriting many parts from each parent

Bit-string mutation for binary encoding

Flip-bit mutation for binary encoding

Populating the next generation

Exploration vs. exploitation

Stopping conditions

Configuring the parameters of a genetic algorithm

Use cases for evolutionary algorithms

Summary of evolutionary algorithms