Section 4.3 Reference: Outline of a Basic Simulated Annealing Algorithm

Initialization: Start with a feasible initial trial solution.

Iteration: Use the move selection rule to select the next trial solution. (If none of the immediate neighbors of the current trial solution are accepted, the algorithm is terminated.)

Check the temperature schedule: When the desired number of iterations have been performed at the current value of T, decrease T to the next value in the temperature schedule and resume performing iterations at this next value

Stopping rule: When the desired number of iterations have been performed at the smallest value of T in the temperature schedule (or when none of the immediate neighbors of the current trial solution are accepted), stop. Accept the best trial solution found at any iteration (including for larger values of T) as the final solution.

Before applying this algorithm to any particular problem, a number of details need to be worked out to fit the structure of the problem.

1. How should the initial trial solution be selected?

2. What is the neighborhood structure that specifies which solutions are immediate neighbors (reachable in a single iteration) of any current trial solution?

3. What device should be used in the move selection rule to randomly select one of the immediate neighbors of the current trial solution to become the current candidate to be the next trial solution?

4. What is an appropriate temperature schedule?