ChapterZero

This semester, since I was working on a computer vision project, I downloaded a bunch of articles on shape recognition, tracking, color correction, and such. A lot of the algorithms in these papers depend on some optimization algorithm, and these optimization algorithms are assumed to be known to the reader. It seems that simulated annealing, a method of optimization based on the simulation of certain physical mechanisms, can be used as a simple equivalent replacement algorithm for the more esoteric ones.

Here’s how simulated annealing works, as per “The Annealing Algorithm” by Otten and van Ginneken: we are given an instance of the problem, a pair consisting of a set of feasible configurations (aka configuration space) , and a score (aka objective) function , and our aim is to find an optimum state , satisfying

There are several ways to conduct this search: blind random searching, in which random configurations are generated and evaluated until some stopping condition is reached; iterative refinement, in which random configurations are generated and evaluated, then tested against their neighbors; in this method, a new starting random configuration considered when all the current one’s neighbors have been tested, and is switched to only if its score is lower than the current low score. Then there are probabilistic hill climbing methods, which keep the testing of neighbors present in the iterative refinement algorithm, but use an acceptance function to determine whether to switch to a new random starting point; this acceptance function has a nonzero probability of allowing a switch to a starting configuration with a higher score. By visualizing the score vs. configuration surface, you can see why probabilistic hill climbing methods are appropriately named: while iterative refinement algorithms can only move down the surface, these methods allow moving up hills; the advantage of allowing this is that it makes the algorithm less sensitive to local minima.

Simulated annealing is a probabilistic hill climbing optimization method motivated by physical principles– I won’t go into the details, because they’re not too important: the method is straightforward enough by itself. To use this method, you need a single parameter