
Resources for Teaching Stochastic Local Search

 Paper: Teaching
Stochastic Local Search, in Proceedings of the 18th
International FLAIRS Conference (FLAIRS2005), Clearwater Beach,
Florida, May 1517, 2005, AAAI Press.
 Code described in paper above
 Simulated annealing demonstration applets:
 (Clustered) Traveling Salesman
Problem

Modern browsers do not support the Java applet embedded in this page.
However, one can install a Java Development Kit (JDK) and run the following
appletviewer command to see the demo:
appletviewer http://cs.gettysburg.edu/~tneller/resources/sls/tsp/index.html
 Class Scheduling Problem
(see paper for description)

Modern browsers do not support the Java applet embedded in this page.
However, one can install a Java Development Kit (JDK) and run the following
appletviewer command to see the demo:
appletviewer http://cs.gettysburg.edu/~tneller/resources/sls/scheduling/index.html
 Readings:
 Stochastic Local Search:
 Russell, S. & Norvig, P.. Artificial Intelligence: a
modern approach, section 4.3, pp. 110115 (through "Simulated annealing
search").
 Hoos, H. H., and Stützle,
T. 2005. Stochastic Local Search: foundations and applications.
San Francisco: Morgan Kaufmann. (an excellent textbook for an advanced
undergraduate or graduate course on stochastic local search)
 Simulated Annealing:
 Kirkpatrick, S.; Gelatt, C.; and Vecchi, M. 1983.
Optimization by simulated annealing. Science 220:671–680.
 Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; and
Flannery, B. P. 1992. Numerical Recipes in C: the art of scientific
computing  2nd Ed. Cambridge: Cambridge University Press, section
10.9, pp. 444  451.
 Suggested Syllabus
 Preparatory reading: Russell and Norvig reading
listed above
 Class 1: Define problem, terminology, cover and
collectively implement simple hill climbing (through "Hill Descent" in
Teaching Stochastic Local Search)
 Class 2: Observe local minima, add random uphill
steps, add simulated annealing step, play with demo applets above
(remainder of
Teaching Stochastic Local Search)
 Homework: Assign one or more challenge problems (see
"Challenge Problems" of Teaching
Stochastic Local Search)
 Optional Laboratories: Give a simple, engaging
combinatorial optimization problem, and have students (1) formalize the
problem (clearly stating assumptions, constraints, etc.), (2) implement
the associated annealing State, and (3) apply the stochastic local
search method of their choice. Have students justify their
choices of optimization measures, discussing advantages and
disadvantages to their problem formalizations. Also, given time,
have students demonstrate their software. Here are two suggested
challenge problems:
 Forming teams: Forming project teams is a
difficult task for faculty. While some choose to form teams
randomly, others seek to optimize various subjective/objective
measures. Write software that will optimize course project teams
according to objective measures of your choice (e.g. maximizing
students working with those they prefer, balancing group sizes,
balancing abilities, etc.). Justify your choice of measures,
discussing advantages and disadvantages to your problem
formalization.
 Ordering pizza: Pizza is an important food group
of computer science departments everywhere. Write software that
will optimize pizza ordering according to objective measures of your
choice (e.g. maximizing diners getting preferred toppings, minimizing
waste, etc.). Justify your choice of measures, discussing
advantages and disadvantages to your problem formalization.
 Video Tutorial
Tiny URL: http://tinyurl.com/gburgsls
Note: These software resources are provided under the
GNU General Public
License (GNU GPL).
Please responsibly cite the author's contribution when using these
resources.
Although feedback/suggestions are much appreciated, this material will
be updated infrequently as time permits.
Last updated 17 January 2017
Todd Neller