Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

Discovering simulated annealing

At a certain point in the search, if your objective function stops giving you the 

right indications, you can use another heuristic to control the situation and try to 

find a better path to a better task solution. This is how both simulated annealing 

and Tabu Search work: They provide you with an emergency exit when needed.

Simulated  annealing  take  its  name  from  a  technique  in  metallurgy,  which 

heats the metal to a high temperature and then slowly cools it to soften the metal 

for  cold  working  and  to  remove  internal  crystalline  defects  (see 

http://www.

brighthubengineering.com/manufacturing-technology/30476-what-is- 

heat-treatment/

 for details on this metal-working process). Local search repli-

cates this idea by viewing the solution search as an atomic structure that changes 

to improve its workability. The temperature is the game changer in the optimiza-

tion  process.  Just  as  high  temperatures  make  the  structure  of  a  material  relax 

(solids melt and liquid evaporate at high temperatures), so high temperatures in 

a local search algorithm induce relaxation of the objective function, allowing it to 

prefer  worse  solutions  to  better  ones.  Simulated  annealing  modifies  the  hill-

climbing procedure, keeping the objective function for neighbor solution evalua-

tion but allowing it to determine the search solution choice in a different way:

1. 

Obtain a temperature expressed as probability. (The Gibbs-Boltzmann physics 

function is a formula that converts temperature to probability. An explanation 

of this function is beyond the scope of this book, but you can explore it at: 

http://www.iue.tuwien.ac.at/phd/binder/node87.html

.)

2. 

Set a temperature schedule. The temperature decreases at a certain rate as 

time passes and the search runs.

FIGURE 18-3: 

An 8-queen 

puzzle solved.

---

CHAPTER 18