Guaranteed Local Minimum

Simulated annealing is guaranteed to find a global optimal solution, a result in [AKvL97]. Unfortunately, to get that guarantee requires an exponentially long cooling schedule, and is therefore impractical. We'd settle for a local minimum, where no better moves exist in the neighborhood, but reasonable length annealing schedules do not even promise that! So in the DAO, we follow our five schemes with a deterministic hillclimber that guarantees a local minimum at some additional expense.

This iterated next-descent hillclimbing algorithm [Ack87b] considers the students one-by-one, either in arbitrary order from a random start (mr) or in seniority order (m), depending on the configuration, and tries placing each student in every other available bed looking for lower scores. Any bed switch that improves the overall grade is accepted, and the student index is saved. From there we continue until we reach the last student and last bed choice. If we had any improvements, we start over until we have looped to the student index last changed. We end up with the best grade such that there is no better state one move away -- a local minimum. The landscape of the results of a complete DAO run (page ) shows no single move improves the overall grade.

This minimization step can be configured to take place once on the best solution ever seen, or after each round. The ramifications are discussed in Section 4.3.7.

download thesis