17 Simulated Annealing
Optimization Beyond Local Minima
This chapter covers
- Introducing simulated annealing
- Using simulated annealing to improve deliveries schedule
- A primer on the traveling salesman problem
- Using simulated annealing for minimum crossing embeddings
- An algorithm based on simulated annealing to draw graphs nicely
If you have read chapters 15 and 16, you should by now be familiar with graph embeddings and optimization problems; in the previous chapter, in particular, we have explained how to reformulate “graph embedding” as an optimization problem, and introduced gradient descent, an optimization technique that can be used to find (near)optimal solutions to this category of problems. In particular, we discussed two solutions of the problem, seen as crossing-number optimization and as a force-directed graph drawing; gradient descent is particularly suitable for the latter, while particularly bad for the former.
One issue we have seen with gradient descent is that it tends to get stuck in local minima, which is pretty much the last thing we would want, considering that we often have to deal with cost functions having lots of local peaks.
We have already discussed one workaround for this issue, running gradient descent several times using random-restart to choose a different starting point each time.