Simulated annealing
Simulated annealing is a global optimization method that distinguishes between different local optima. Starting from an initial point, the algorithm takes a step in a random direction and the function is evaluated. When minimizing a function, any downhill step is accepted and the process repeats from this new point. The step size starts out large and is gradually reduced as the solution to the problem crystallises.
The name comes from the fact that the method has similarities with annealing of metals where the step size is analogous to the temperature. For simulated annealing to work the function must be possible to evaluate in a short amount of time and it must be clear if the new solution actually is better than the old one. Smooth functions usually are solved very efficiently.
Instead of page upon page of math and dubious theorems that no one understands we will use an example from the real world.
An elderly gentleman named John Walker has made a sentience test to protect himself against the innumerate among us. This involves solving a linear equation to be able to send him feedback on his website. He is convinced that this will protect him from the fat, stupid and innumerate masses that he finds intolerable.
From his website:
Sentience Test Enter the correct value for x in the box. 75x + 37 = 5437 x = | |
Armed with the powerful knowledge of simulated annealing and a computer we go to work to defeat this elderly eccentric...
t = 100 x = 0 do g = x + rnd * t - rnd * t a1 = (75 * x + 37) a2 = (75 * g + 37) if abs(a2 - 5437) < abs(a1 - 5437) then x = g t = t * 0.999 loop until a1 = 5437 print "x = ";x
After glorious eight thousand and eighty iterations when run in VBDOS we get the result: x = 72, by substituting for x in the original equation we find that 75 * 72 + 37 really is 5437 and we have free access to amuse Mr. Walker with our thoughts.
Now that we have grasped the basic idea of simulated annealing we can extend it to solve equations that no human is able to solve without the help of a computer.
