1


2

 Intro AI course has many topics, little time
 Best learning is experiential, but experience takes time!
 "One must learn by doing the thing; for though you think you know
it, you have no certainty, until you try." Sophocles
 How to introduce stochastic local search
 Simply
 Concisely
 Experientially

3

 Drunken Topographer Analogy
 Formalize the problem
 Longitude, latitude ® state
 Altitude ® energy (objective
function)
 Random step ® next state
generation
 Goal: Find the lowest energy!

4

 step – take a stochastic local step in the state space
 undo – revert one step (never two!)
 energy – measure state “badness”
 clone – copy state for future reference

5


6

 For a fixed number of iterations:
 [Report state every 100000 iterations]
 Step to next state.
 If step is not uphill,
 check if it is the best (minimal energy) yet,
 Otherwise reject (undo) the step.
 Return best state

7

 The Rastrigin Function
 sinusoidally perturbed parabolic bowl
 energy(x, y)
= x^{2} + y^{2} − cos(18x)
− cos(18y) + 2
 Initialize at (10,10)
 x, y Gaussian step distribution with σ = .05
 Apply simple hill descent

8

 Allow uphill steps with some probability
 Experiment with acceptance rate:
 0.0 = hill descent
 1.0 = random walk
 0.1 à close approximation
 0.01 à closer
approximation
 0.001 à local minima

9

 Not all uphill steps are equal
 Introduce Boltzmann distribution
 What is the behavior at temperature extremes?
 High temperature: random walk (“super drunk”)
 Low temperature: hill descent (“deadtired drunk”)
 Vary from high to low temperature…

10

 Why simulated annealing?
 However, annealing (cooling) schedules are a “black art”.
 Side note: decisiontheoretic simulated annealing
 There is no substitute for experience.

11


12

 Homework: Assign one or more simple combinatorial optimization problems
(e.g. TSP, nqueens, etc.)
 Optional Labs:
 Project group formation problem
 Pizza ordering problem

13

 http://cs.gettysburg.edu/~tneller/resources/sls/index.html
 FLAIRS’05 paper
 Relevant code
 Links to demo applets
 Readings on SA and SLS in general
 Suggested Syllabus

14

 “We can only possess what we experience.
Truth, to be understood, must be lived.” – Charlie Peacock
 Further exploration: Hoos and Stutzle text
 Other SLS distillations are possible.
May you and your students benefit from our good experiences!
