This chapter covers
- Introducing the genetic algorithm
- Exploring whether genetic algorithms are better than simulated annealing
- Solving the “Packing to Mars” problem with genetic algorithms
- Solving TSP and assigning deliveries to trucks with genetic 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 is fast but has a tendency to get stuck in local minima and needs the cost function to be differentiable, while 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: