 |
Resources for Teaching Stochastic Local Search
|
- Paper: Teaching Stochastic Local
Search, in Proceedings of the 18th International FLAIRS Conference
(FLAIRS-2005), Clearwater Beach, Florida, May 15-17, 2005, AAAI Press.
- Code described in paper above
- Simulated annealing demonstration applets:
- Readings:
- Stochastic Local Search:
- Russell, S. & Norvig, P.. Artificial Intelligence: a modern approach,
section 4.3, pp. 110-115 (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.
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 2 May 2005
Todd Neller