Project Nayuki


Simulated annealing demo

Scenario

Simulated annealing is a powerful technique to optimize variables, especially in high dimensional spaces with thousands of variables. Just for fun, I wrote a program to experiment with annealing the pixels in a random image.

My program begins by generating a 256×256 image with uniformly random pixel values in RGB24 (i.e. rainbow noise). The simulated annealing process seeks to reduce the total “energy” in the entire image by swapping random adjacent pixels.

The energy in the image is defined as the sum of absolute differences between all horizontally and vertically adjacent pixels in all 3 color channels. For example, between two adjacent pixels with the colors (255,128,0) and (31,178,99), the energy is 373.

At each iteration, a random pixel in the image is picked, and it is swapped with either its right neighbor or bottom neighbor. The energy of the new image is calculated. The difference in energy, along with the current temperature, determines the probability that the swap is accepted. If rejected, the pixels are swapped back and the energy remains unchanged.

The current implementation has a simple cooling schedule where the temperature goes from startTemperature down to zero linearly. The probability of accepting a swap is the standard formula 2energyDiff / currentTemperature; this implies that reducing energy is always accepted.

(Note that because Math.exp() is rather slow (about 5 million calls per second on my desktop computer), I implemented a custom 2-to-the-power-of function which is reasonably accurate and much faster (~300 million per second). This does not affect the overall behavior of simulated annealing, because exp and 2-pow can be made equivalent by scaling the temperature by a constant factor.)

Resulting images

Starting temperature
20 50 70 100 200 400 1000
Num iters Initial (zero) Original image
10 million Image Image Image Image Image Image Image
100 million Image Image Image Image Image Image Image
1 000 million Image Image Image Image Image Image Image
10 000 million Image Image Image Image Image Image Image
100 000 million Image Image Image Image Image Image Image
1 000 000 million Image Image Image Image Image Image Image

Discussion of results: We can see that as the number of iterations is increased, the annealed image becomes smoother and smoother. The starting temperature makes a big difference on the effectiveness of simulated annealing, however – too low and the process gets trapped in a local minimum early on, too high and the process doesn’t pursue the energy reduction aggressively enough. I empirically determined that a starting temperature of 100 seems to yield the best results.

Live demo (JavaScript)

squared
million
Current iterations:
Current temperature:
Current energy:

Source code

Download:

Notes: