Algorithms For Dummies

  Performing Local Search 

     347

3. 

Define a starting solution (using random sampling or another algorithm) and 

start a loop. As the loop proceeds, the temperature decreases.

4. 

Stop the optimization when the temperature is zero.

5. 

Propose the current result as the solution.

At this point, you must iterate the search for solutions. For each step in the previ-

ous iteration, between the preceding Steps 3 and 4, do the following:

1. 

List the neighboring solutions and choose one at random.

2. 

Set the neighboring solution as the current solution when the neighboring 

solution is better than the current one.

3. 

Otherwise, pick a random number between 0 and 1 based on a threshold 

probability associated with the actual temperature and determine whether it’s 

less than the threshold probability:

• 

If it’s less, set the neighboring solution as the current solution (even if it’s 

worse than the current solution, according to the objective function).

• 

If it’s more, keep the current solution.

Simulated  annealing  is  a  smart  way  to  improve  hill  climbing  because  it  avoids 

having  the  search  stopped  at  a  local  solution.  When  the  temperature  is  high 

enough, the search might use a random solution and find another way to a better 

optimization. Because the temperature is higher at the beginning of the search, 

the algorithm has a chance of injecting randomness into the optimization. As the 

temperature cools to zero, less and less chance exists for picking a random solu-

tion, and the local search proceeds as in hill climbing. In TSP, for instance, the 

algorithm  achieves  simulated  annealing  by  challenging  the  present  solution  at 

high temperatures by