18 Genetic Algorithms
Biologically-Inspired, Fast-Converging Optimization
This chapter covers
- Introducing the genetic algorithm
- Are genetic algorithms better than simulated annealing?
- Solving the “Packing to Mars” problem with genetic algorithms
- Solving TSP and assigning deliveries to trucks, with generic algorithms
- Creating a genetic algorithm to solve minimum vertex cover
- Discussing applications of genetic algorithms
While gradient descent and simulated annealing are great optimization techniques, they both have shortcomings: the former if fast but has a tendency to get stuck in local minima, and needs the cost function to be differentiable; the latter can be quite slow in converging.
In this chapter we are going to learn about the genetic algorithm, yet another optimization technique that uses an approach inspired by nature to overcome both issues, providing more resilience to local minima by evolving a pool of solutions, and at the same time speeding up convergence.
We will apply this technique to a few hard problems that can’t be solved efficiently with deterministic algorithms: we’ll start by using 0-1 knapsack, which we discovered in chapter 1, to explain the theory behind genetic algorithms; then we’ll briefly discuss a genetic algorithm for TSP[1], and show how (and why) it converges faster than simulated annealing; finally, we will also introduce two new problems: