Simulated Annealing in Motion

Animated GIF89 image of the simulated-annealing algorithm.

The initial state is again the output of the greedy algorithm. During each iteration, the program chooses a county at random and attempts to transfer it to an adjacent district (if there is one). The move is always accepted if it reduces the population difference between the two districts; in addition, the move may be accepted even if it exacerbates a population imbalance. The probability of accepting such a detrimental move is an exponential function of a temperature parameter. The simulation starts at a high temperature, where even highly unfavorable moves are likely to be accepted, and its is gradually cooled until only beneficial moves have any chance of success. The run shown here is not the same one that produced the final state of Figure 5. To reduce the size of the animation file, the program was run with a much briefer annealing schedule. Out of some 5,700 iterations, or attempted moves, 156 moves were accepted. The mean deviation of the final state is 1.86 percent.