METAHEURISTICS:SIMULATED ANNEALING

SIMULATED ANNEALING

Simulated annealing is another widely used metaheuristic that enables the search process to escape from a local optimum. To better compare and contrast it with tabu search, we will apply it to the same traveling salesman problem example before returning to the non- linear programming example introduced in Sec. 14.1. But first, let us examine the basic concepts of simulated annealing.

Basic Concepts

Figure 14.1 in Sec. 14.1 introduced the concept that finding the global optimum of a complicated maximization problem is analogous to determining which of a number of hills is the tallest hill and then climbing to the top of that particular hill. Unfortunately, a mathematical search process does not have the benefit of keen eyesight that would enable spotting a tall hill in the distance. Instead, it is like hiking in a dense fog where the only clue for the direction to take next is how much the next step in any direction would take you up or down.

One approach, adopted into tabu search, is to climb the current hill in the steepest direction until reaching its top and then start climbing slowly downward while searching for another hill to climb. The drawback is that a lot of time (iterations) is spent climbing each hill encountered rather than searching for the tallest hill.

Instead, the approach used in simulated annealing is to focus mainly on searching for the tallest hill. Since the tallest hill can be anywhere in the feasible region, the early emphasis is on taking steps in random directions (except for rejecting some, but not all, steps that would go downward rather than upward) in order to explore as much of the feasible region as possible. Because most of the accepted steps are upward, the search will gradually gravitate toward those parts of the feasible region containing the tallest hills. Therefore, the search process gradually increases the emphasis on climbing upward by rejecting an increasing proportion of steps that go downward. Given enough time, the process often will reach and climb to the top of the tallest hill.

To be more specific, each iteration of the simulated annealing search process moves from the current trial solution to an immediate neighbor in the local neighborhood of this

solution, just as for tabu search. However, the difference from tabu search lies in how an immediate neighbor is selected to be the next trial solution. Let

Zc = objective function value for the current trial solution,

Zn = objective function value for the current candidate to be the next trial solution,

T = a parameter that measures the tendency to accept the current candidate to be the next trial solution if this candidate is not an improvement on the current trial solution.

The rule for selecting which immediate neighbor will be the next trial solution follows:

Move selection rule: Among all the immediate neighbors of the current trial solution, select one randomly to become the current candidate to be the next trial solution. Assuming the objective is maximization of the objective function, accept or reject this candidate to be the next trial solution as follows:

(If the objective is minimization instead, reverse Zn and Zc in the above formulas.) If this candidate is rejected, repeat this process with a new randomly selected immediate neighbor of the current trial solution. (If no immediate neighbors remain, terminate the algorithm.)

Thus, if the current candidate under consideration is better than the current trial solution, it always is accepted to be the next trial solution. If it is worse, the probability of acceptance depends on how much worse it is (and on the size of T). Table 14.4 shows a sampling of these probability values, ranging from a very high probability when the current candidate is only slightly worse (relative to T) than the current trial solution to an ex- tremely small probability when it is much worse. In other words, the move selection rule usually will accept a step that is only slightly downhill, but seldom will accept a steep downward step. Starting with a relatively large value of T (as simulated annealing does) makes the probability of acceptance relatively large, which enables the search to proceed in almost random directions. Gradually decreasing the value of T as the search continues (as simulated annealing does) gradually decreases the probability of acceptance, which increases the emphasis on mostly climbing upward. Thus, the choice of the values of T over time controls the degree of randomness in the process for allowing downward steps.

This random component, not present in basic tabu search, provides more flexibility for moving toward another part of the feasible region in the hope of finding a taller hill.

The usual method of implementing the move selection rule to determine whether a particular downward step will be accepted is to compare a random number between 0 and 1 to the probability of acceptance. Such a random number can be thought of as a random observation from a uniform distribution between 0 and 1. (All references to random numbers throughout the chapter will be to such random numbers.) There are a number of methods of generating these random numbers (as will be described in Sec. 20.3). For example, the Excel function RAND() generates such random numbers upon request. (The beginning of the Prob- lems section also describes how you can use the random digits given in Table 20.3 to obtain the random numbers you will need for some of your homework problems.) After generating a random number, it is used as follows to determine whether to accept a downward step:

If random number < Prob{acceptance}, accept a downward step. Otherwise, reject the step.

Why does simulated annealing use the particular formula for Prob{acceptance} specified by the move selection rule? The reason is that simulated annealing is based on the analogy to a physical annealing process. This process initially involves melting a metal or glass at a high temperature and then slowly cooling the substance until it reaches a low-energy stable state with desirable physical properties. At any given temperature T dur- ing this process, the energy level of the atoms in the substance is fluctuating but tending to decrease. A mathematical model of how the energy level fluctuates assumes that changes occur randomly except that only some of the increases are accepted. In particular, the probability of accepting an increase when the temperature is T has the same form as for Prob{acceptance} in the move selection rule for simulated annealing.

The analogy for an optimization problem in minimization form is that the energy level of the substance at the current state of the system corresponds to the objective function value at the current feasible solution of the problem. The objective of having the substance reach a stable state with an energy level that is as small as possible corresponds to having the prob- lem reach a feasible solution with an objective function value that is as small as possible.

Just as for a physical annealing process, a key question when designing a simulated annealing algorithm for an optimization problem is to select an appropriate temperature schedule to use. (Because of the analogy to physical annealing, we now are referring to T in a simulated annealing algorithm as the temperature.) This schedule needs to specify the initial, relatively large value of T, as well as the subsequent progressively smaller val- ues. It also needs to specify how many moves (iterations) should be made at each value of T. The selection of these parameters to fit the problem under consideration is a key fac- tor in the effectiveness of the algorithm. Some preliminary experimentation can be used to guide this selection of the parameters of the algorithm. We later will specify one spe- cific temperature schedule that seems reasonable for the two examples considered in this section, but many others could be considered as well.

With this background, we now can provide an outline of a basic simulated annealing algorithm.

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 sched- ule 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 neigh- bors 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 neigh- bors (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?

We will illustrate some reasonable ways of addressing these questions in the context of applying the simulated annealing algorithm to the following two examples.

The Traveling Salesman Problem Example

We now return to the particular traveling salesman problem that was introduced in Sec. 14.1 and displayed in Fig. 14.4.

The metaheuristics area in your IOR Tutorial includes a procedure for applying the basic simulated annealing algorithm to small traveling salesman problems like this ex- ample. This procedure answers the four questions in the following way:

1. Initial trial solution: You may enter any feasible solution (sequence of cities on the tour), perhaps by randomly generating the sequence, but it is helpful to enter one that appears to be a good feasible solution. For the example, the feasible solution 1-2-3-4- 5-6-7-1 is a reasonable choice.

2. Neighborhood structure: An immediate neighbor of the current trial solution is one that is reached by making a sub-tour reversal, as described in Sec. 14.1 and illustrated in Fig. 14.5. (However, the sub-tour reversal that simply reverses the direction of the tour provided by the current trial solution is ruled out.)

3. Random selection of an immediate neighbor: Selecting a sub-tour to be reversed re- quires selecting the slot in the current sequence of cities where the sub-tour currently begins and then the slot where the sub-tour currently ends. The beginning slot can be anywhere except the first and last slots (reserved for the home city) and the next-to-last slot. The ending slot must be somewhere after the beginning slot, excluding the last slot. (Both beginning in the second slot and ending in the next-to-last slot also is ruled out since this would simply reverse the direction of the tour.) As will be illustrated shortly, random numbers are used to give equal probabilities to selecting any of the eligible be- ginning slots and then any of the eligible ending slots. If this selection of the beginning and ending slots turns out to be infeasible (because the links needed to complete the sub- tour reversal are not available), this process is repeated until a feasible selection is made.

4. Temperature schedule: Five iterations are performed at each of five values of T (T1, T2, T3, T4, T5) in turn, where

This particular temperature schedule is only illustrative of what could be used. T1 = 0.2Zc is a reasonable choice because T1 should tend to be fairly large compared to typical values of ⏐Zn - Zc⏐, which will encourage an almost random search through the feasible region to find where the search should be focused. However, by the time the value of T is reduced to T5, almost no nonimproving moves will be accepted, so the emphasis will be on improving the value of the objective function.

When dealing with larger problems, more than five iterations probably would be per- formed at each value of T. Furthermore, the values of T would probably be reduced more slowly than with the temperature schedule prescribed above.

Now let us elaborate on how the random selection of an immediate neighbor is made. Suppose we are dealing with the initial trial solution of 1-2-3-4-5-6-7-1 in our example.

Suppose that the random number generated for this purpose happens to be 0.0461. 0.0461: Choose to end the sub-tour in slot 4.

Since slots 3 and 4 currently designate that cities 3 and 4 are the third and fourth cities visited in the tour, the sub-tour of cities 3-4 will be reversed.

Reverse 3-4 (see Fig. 14.5): 1-2-4-3-5-6-7-1 Zn = 65

This immediate neighbor of the current (initial) trial solution becomes the current candi- date to be the next trial solution. Since

Zn = 65 < Zc = 69, this candidate is better than the current trial solution (remember that the objective here is to minimize the total distance of the tour), so this candidate is automatically accepted to be next trial solution.

This choice of a sub-tour reversal was a fortunate one because it led to a feasible so- lution. This does not always happen in traveling salesman problems like our example where certain pairs of cities are not directly connected by a link. For example, if the ran- dom numbers had called for reversing 2-3-4-5 to obtain the tour 1-5-4-3-2-6-7-1, Fig. 14.4

shows that this is an infeasible solution because there is no link between cities 1 and 5 as well as no link between cities 2 and 6. When this happens, new pairs of random numbers would need to be generated until a feasible solution is obtained. (A more sophisticated procedure also can be constructed to generate random numbers only for relevant links.) To illustrate a case where the current candidate to be the next trial solution is worse than the current trial solution, suppose that the second iteration results in reversing 3-5-6 (as in Fig. 14.6) to obtain 1-2-4-6-5-3-7-1, which has a total distance of 64. Then suppose that the third iteration begins by reversing 3-7 (as in Fig. 14.9) to obtain 1-2-4-6-5-7-3-1 (which has a total distance of 66) as the current candidate to be the next trial solution. Since 1-2-4-6-5-3-7-1 (with a total distance of 64) is the current trial solution for iteration 3, we now have

 

trial solution, 1-3-5-7-6-4-2-1 (which happens to be the optimal solution along with the equivalent tour in the reverse direction, 1-2-4-6-7-5-3-1), so this solution is accepted as the final solution. You might find it interesting to apply this software to the same problem yourself. Due to the randomness built into the algorithm, the sequence of trial solutions obtained will be different each time. Because of this feature, practitioners sometimes will reapply a simulated annealing algorithm to the same problem several times to increase the chance of finding an optimal solution. (Problem 14.3-2 asks you to do this for this same example.) The initial trial solution also may be changed each time to help facilitate a more thorough exploration of the entire feasible region.

If you would like to see another example of how random numbers are used to per- form an iteration of the basic simulated annealing algorithm for a traveling salesman problem, one is provided in the Solved Examples section of the book’s website.

Before going on to the next example, we should pause at this point to mention a couple of ways in which advanced features of tabu search can be combined fruitfully with simulated annealing. One way is by applying the strategic oscillation feature of tabu search to the temperature schedule of simulated annealing. Strategic oscillation adjusts the tem- perature schedule by decreasing the temperatures more rapidly than usual but then strate- gically moving the temperatures back and forth across levels where the best solutions were found. Another way involves applying the candidate-list strategies of tabu search to the move selection rule of simulated annealing. The idea here is to scan multiple neighbors to see if an improving move is found before applying the randomized rule for accepting or rejecting the current candidate to be the next trial solution. These changes have some- times produced significant improvements.

As these ideas for applying features of tabu search to simulated annealing suggest, a hybrid algorithm that combines the ideas of different metaheuristics can sometimes per- form better than an algorithm that is based solely on a single metaheuristic. Although we are presenting three commonly used metaheuristics separately in this chapter, experienced practitioners occasionally will pick and choose among the ideas of these and other meta- heuristics in designing their heuristic methods.

The Nonlinear Programming Example

Now reconsider the example of a small nonlinear programming problem (only a single variable) that was introduced in Sec. 14.1. The problem is to

The reason for setting crj = (Uj - Lj)/6 when selecting an immediate neighbor is that when the variable xj is midway between Lj and Uj, any new feasible value of the variable is within three standard deviations of the current value. This gives a significant probabil- ity that the new value will move most of the way to one of its bounds even though there is a much higher probability that the new value will be relatively close to the current value. There are a number of methods for generating a random observation N(0, crj) from a normal distribution (as will be discussed briefly in Sec. 20.4). For example, the Excel function, NORMINV(RAND(),0,crj), generates such a random observation. For your homework, here is a straightforward way of generating the random observations you need. Obtain a ran- dom number r and then use the normal table in Appendix 5 to find the value of N(0, crj) such that P{X N(0, crj)} = r when X is a normal random variable with mean 0 and stan- dard deviation crj.

To illustrate how the algorithm designed in this way would be applied to the example,

let us start with x = 15.5 as the initial trial solution. Thus,

Therefore, x = 8 will be accepted only if the corresponding random number between 0 and 1 happens to be less than 0.400. Thus, x = 8 is fairly likely to be rejected. (In somewhat later iterations when T is much smaller, x = 8 would almost certainly be re- jected.) This is fortunate since Fig. 14.1 reveals that the search should focus on the portion of the feasible region between x = 10 and x = 30 in order to start climbing the tallest hill.

Table 14.6 provides the results that were obtained by using IOR Tutorial to apply the complete simulated annealing algorithm to this nonlinear programming problem. Note how the trial solutions obtained vary fairly widely over the feasible region during the early iterations, but then start approaching the top of the tallest hill more consistently during the later iterations when T has been reduced to much smaller values. Therefore, of the 25 iterations, the best trial solution of x = 20.031 (as compared to the optimal solution of x = 20) was not obtained until iteration 21.

Once again, you might find it interesting to apply this software to the same problem yourself to see what is yielded by new sequences of random numbers and random observations from normal distributions. (Problem 14.3-6 asks you to do this several times.)