Increasing The Efficiency of Simulated Annealing Search by Learning to Recognize (Un)Promising Runs

Yoichiro Nakakuki, Norman M. SadehAAAI 1994

Introduction

Simulated Annealing (SA) is a robust, general-purpose metaheuristic for solving NP-complete combinatorial optimization problems. Despite its versatility, SA suffers from significant stochasticity. Because it relies on random moves to escape local minima, a single run may frequently converge to a suboptimal solution. Consequently, practitioners often perform dozens or hundreds of independent runs to ensure a near-optimal result.

This repetition represents a substantial waste of computational resources. Most runs are "unpromising," consuming CPU time exploring regions of the search space that will never yield top-tier results. This paper addresses the challenge of identifying "bad" runs in real-time and leveraging knowledge from previous runs to guide future search trajectories.

Methods: Learning from Search Performance

The central innovation is the Expected Cost Improvement Distribution (ECID). Rather than treating each SA run in isolation, the proposed system aggregates data from completed runs to construct a statistical profile of performance at specific checkpoints, defined by the temperature parameter $T$.

Illustration of the Expected Cost Improvement Distribution (ECID) and cutoff points at different temperatures.

The authors implement two primary mechanisms based on this statistical model:

  1. Cutoff Criterion: At predefined checkpoints, the current run's progress is compared against the learned ECID. If the probability of the run eventually surpassing the best solution found so far falls below a threshold (e.g., 1%), the run is aborted immediately.
  2. Restart Criteria: Upon completion or abortion of a run, the system decides the next starting point. Strategies include a greedy approach (Maximum Cost Reduction Rate), a randomized approach for diversity, and a Hybrid Criterion that uses a Boltzmann distribution to balance exploitation of known good points with exploration of new paths.

Datasets and Evaluation

The methodology was evaluated using a suite of 40 benchmark Job Shop Scheduling (JSS) problems. Each problem involved 20 jobs and 5 resources, totaling 100 operations. The objective was to minimize a "Just-In-Time" cost function (sum of tardiness and inventory costs). These benchmarks covered diverse scheduling conditions, including varying due-date tightness and the presence of bottlenecks.

Key Insights

  • Predictable Search Behavior: While the search space itself is chaotic, the statistical behavior of the SA algorithm on that space is learnable and predictable.
  • Normal Distribution Assumption: Cost improvements below certain temperatures can be effectively modeled using a Normal Distribution, enabling computationally efficient statistical testing during search.
  • The Power of Hybridization: The Hybrid restart criterion consistently outperformed purely greedy methods, highlighting the importance of maintaining non-determinism to avoid "meta-local-minima" in the learning process.

Key Results

The experimental results demonstrate significant efficiency gains. The Hybrid SA (H-SA) achieved speedups of 25% to 70% compared to standard SA while maintaining equivalent solution quality.

Speedup percentages for various learned SA strategies across eight problem sets.

Furthermore, versions incorporating learning (P-SA, B-SA, R-SA, H-SA) consistently outperformed standard SA (N-SA) in fixed-time comparisons. The computational overhead for maintaining the ECID was negligible, accounting for less than 1% of total CPU time.

Limitations and Future Work

The system requires a "burn-in" phase of approximately 5 full runs to establish meaningful distributions, limiting its utility for very short search tasks. Additionally, the assumption of a normal distribution for improvements may not generalize to all optimization domains. Future research could explore extending this "meta-learning" framework to other neighborhood search techniques beyond Simulated Annealing.

Summary updated

BibTeX
@inproceedings{nakakuki1994increasing,
  author = {Yoichiro Nakakuki and Norman M. Sadeh},
  title = {{Increasing The Efficiency of Simulated Annealing Search by Learning to Recognize (Un)Promising Runs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure