Genetic algorithms (GAs) are inspired by biology where only the fittest genes survive. It is based on Charles Darwin’s Natural Selection theory. We start with 2 parent chromosomes that each contain an ordered set of genes. Each parent contributes some of their genes when they mate to create children chromosomes. There is a randomness to the mating process so that each child has a diverse set of genes. This diversity is created by the crossover and mutation processes. Over time and with sufficient genetic diversity, the fittest genes, representing optimal characteristics for the species to survive, be come dominant and are propagated. This is nature’s way of optimizing over genetic diversity and we can co-opt this approach for tackling other optimization problems.
Must Haves
A suitable optimization problem to solve – GAs can be good for non-smooth, non-convex, gradient-free optimization problems
Fitness function – quantitative way of evaluating solution candidates; what makes the solution good?
Way to represent the solution as a chromosome
Examples of optimization problems tackled with GA
Travelling Salesperson Problem – salesman must visit every city exactly once and cover the shortest distance starting and ending at the origin city (Link)
Learn Robot Behavior – used to teach robots how to walk (Link)
Build a 2D car – constructs a 2D car-like object (torso and 2 wheels) optimized to travel as far as possible (Link)
Design of water supply systems – optimize the water supply routes (Link)
Generative Art – reproduce an image with minimum number of triangles (Link)
