Contents

• Introduction
• Simulated Annealing Function Description
  • @SIMANNEAL
• An Example: Finding the Minimum of a Bumpy Function
• Conclusion

Introduction

Simulated annealing (SA) solves optimization problems by modeling potential solutions as electron spins which flip into a configuration that lowers the total energy of a system. Each solution is made up of individual spins which are either one or zero. The energy rating of a solution is determined by plugging the values of its spins into a function that returns a numerical energy score. SA proceeds by randomly selecting and flipping it to its opposite value. If the energy of the new configuration is improved, it will be accepted as the new solution. If the energy increases, however, the new solution may be accepted if the increase in the energy satisfies the following equation:

where URANDOM is a uniformly distributed random number and T is a parameter referred to as the temperature. When T is high, it is possible for the system to make jumps to higher energy states. This prevents the solutions from becoming stuck in a local optimum. As T is decreased, the chance of the system increasing its energy is also decreased. Thus, the cooling created by lowering T will eventually force the solution into a low energy state.

The sa plug-in lets you solve 1/0 combinatorial problems using SA in concert with the NExS spreadsheet. sa adds one new function to your spreadsheet: @SIMANNEAL for specifying the locations of your adjustable variables and the objective function you are trying to minimize or maximize.

Simulated Annealing Function Description

@SIMANNEAL

Syntax: @SIMANNEAL(M,F,V)

M = either of the strings ``MIN'' or ``MAX'' depending upon whether the energy function is to be minimized or maximized, respectively.

F = any valid NExS cell expression that returns a numerical result which we will term the energy. The expression can be linear or nonlinear in nature.

V = a range of cells containing ones or zeroes whose values affect the value of the F energy expression.

The @SIMANNEAL function always returns 1. As @SIMANNEAL operates, it places status information in the three cells immediately below it:

1. the current temperature,
2. the average energy of the solution at that temperature,
3. the energy of the best solution seen so far.

An Example: Finding the Minimum of a Bumpy Function

The use of sa is best shown by example. The spreadsheet for this problem can be found in ex2.xs3. You can view the spreadsheet using the command nexs &. Once the spreadsheet is active, you must go under the Connections menu and allow NExS to Accept Connections. Then you must issue the command sa & to start the SA plug-in which will connect itself to your NExS spreadsheet. Finally, use the File -> Open... dialog to read in the contents of the ex1.xs3 sheet.

ex1.xs3 describes the following function:

@COS(@PI/2*X/1000) - 0.1*@SIN(@PI/2*X/100)

which looks like this:

Standard gradient-ascent optimization algorithms will usually get stuck on one of the peaks on the sides of the large mountain. The hope is that a SA can anneal into a solution that will pin-point the highest peak at the top of the mountain.

But how do we represent a real variable like X using a set of 1/0 variables? That's simply done by using the 1/0 variables as a binary representation of X. The 1/0 variables in A1..K1 are used to calculate the signed integer value in cell L1:

L1 = -A1*2**10 + B1*2**9 + C1*2**8 + D1*2**7 + E1*2**6 +
      F1*2**5  + G1*2**4 + H1*2**3 + I1*2**2 + J1*2**1 + K1

The value in L1 is used in the fitness function in cell M1:

@COS(@PI/2*L1/1000) - 0.1*@SIN(@PI/2*L1/100)

The SA function for solving this problem is written in cell N1 as follows:

@SIMANNEAL("MAX",M1,A1..K1)

This will attempt to maximize the energy given by the function in cell M1 as it is affected by the 1/0 variables in range A1..K1. After @SIMANNEAL iterates, the final answer given is X = -91 with a fitness value of 1.0888035. This is close to optimal.

You can't really play with the various control parameters for the @SIMANNEAL function since they are all initialized and adjusted internally. Therefore, you are pretty much stuck with what you get.

You will probably find SA finds solutions more slowly than the genetic algorithms (GA) we discussed previously. That's just the way it is. You'll have to choose the technique that suits you best.

Conclusion

We discussed the principles of simulated annealing, the format of the @SIMANNEAL function provided by the sa NExS plug-in, and gave an example of its use. Quite frankly, the example is kind of cheesy. You can probably find better ones. Get any recent book on numerical optimization and it will have a section on SA. Try some of them using @SIMANNEAL. If @SIMANNEAL won't work, you can modify the code to provide what you need.