To illustrate simulated annealing, we will look at the optimization of a simple program, a four-bit ripple carry adder, as follows:
/* return two bit result of x+y+c */
ADDSTAGE(x<1>, y<1>, c<1>)
{
DECL sum<1>, carry<1>, sum2<1>, carry2<1>, carryout<1>;
sum, carry = ADD(x, y);
sum2, carry2 = ADD(sum, c);
carryout = OR(carry, carry2);
RETURN sum2, carryout;
}
/* add 4bits+4bits -> 5 bits */
ADD4(x<4>, y<4>)
{
DECL sum<5>, c<1>;
sum<0>, c = ADD(x<0>, b<0>);
sum<1>, c = ADDSTAGE(x<1>, y<1>, c);
sum<2>, c = ADDSTAGE(x<2>, y<2>, c);
sum<3>, c = ADDSTAGE(x<3>, y<3>, c);
sum<4> = c;
RETURN sum;
}
INPUT a<4>@4, b<4>@0;
OUTPUT sum<5>@2;
sum = ADD4(a, b);
This program was optimized with a variety of annealing
schedules. The schedules are listed in Table 4.1.
For each schedule, the graph of iteration number vs. cost is plotted
in the following figures. Trial 0 was performed with no optimization,
to provide a base case, and produced an array with 275 processors as
shown in the left hand diagram of Figure 4.1.
The other six trials were performed with increasingly large starting
temperatures and more iterations. The final trial produced an array
with 108 processors as shown in the right hand diagram of
Figure 4.1. The annealing temperature was
multiplied at each iteration by the multiplier in the table, causing
the temperature to follow a graph during the annealing
process. This annealing schedule is better than a simple linear
schedule since more time is spent at lower temperatures, when only
relatively good mutations are accepted.
One main conclusion can be drawn from these graphs. As the initial temperature increases, and the annealing is allowed to take place over more iterations, the resultant system is more optimized. The first annealing schedule, the results of which are shown in Figure 4.2, does not allow any shifts to a ``worse'' system, and thus the system cannot escape from the local minima it is initially placed in. However, as the system becomes more ``excited'' during the beginning of the annealing process, as in Figure 4.7, it can escape from local minima and fall into a better local minima or, with some luck, a global minima. This illustrates the primary feature of simulated annealing, the ability to avoid local minima by exciting the system and then allowing it to ``cool'' gradually over a long period of time.
