Local Search and Simulated Annealing › Implementation in NumPy
Machine Learning from ScratchAll chapters Local Search and Simulated Annealing › Implementation in NumPySection view · Sections in this chapter7 / 10 ↓
Reading tools Definitions, links & notes
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
The design center is a tiny Budget object that counts every objective evaluation and remembers the best permutation it has scored. This centralizes the accounting, so that hill climbing, annealing, and random search all spend budget by the same rule.
We now package the pieces into runnable algorithms. The search implementation uses NumPy and standard Python; figures use Matplotlib and the shared book style. We implement the acceptance and budgeting rules directly so their behavior is inspectable. The budget accounting, the fact that a scoring call is the currency of comparison, is what we want to control ourselves. It also makes the comparison honest: a method cannot quietly spend extra evaluations on rejected proposals or on restart initialization without those calls showing up in the trace.
PythonIn [21]Expand
class Budget:
def __init__(self, limit):
if (
isinstance(limit, (bool, np.bool_))
or not isinstance(limit, (int, np.integer))
or limit < 1
):
raise ValueError("limit must be a positive integer")
self.limit = int(limit)
self.evals = 0
self.scores = []
self.best_score = np.inf
self.best_perm = None
def score(self, perm):
if self.evals >= self.limit:
raise RuntimeError("budget exceeded")
s = objective(perm)
self.evals += 1
self.scores.append(s)
if s < self.best_score:
self.best_score = s
self.best_perm = perm
return s
def trace(self):
return np.minimum.accumulate(np.array(self.scores))The trace method returns the running best-so-far length after every evaluation, which is the incumbent curve we will plot. When we call it at the end of a run, it captures the entire trajectory rather than just the final number. That distinction matters: two methods can end at the same objective while one found it early and the other found it only at the last evaluation.
Key Methods
Hill climbing scans the reversals in the order shown, retaining a candidate through the tolerance-aware update described above. After a completed scan, it steps to that candidate only if the candidate beats the current length by more than ; otherwise it restarts from a fresh random permutation if budget remains. Equal-cost neighbors still consume budget and the scan continues; they do not themselves authorize an installed step. If the budget interrupts a partial scan, the function returns the best permutation scored so far without spending another evaluation.
Simulated annealing proposes a uniformly random reversal, accepts it by the Metropolis rule, and updates the running best. Nothing about the acceptance uses the budget structures differently from hill climbing: every accepted and every rejected proposal costs one evaluation. Random search uses the same budget object but proposes uniformly random permutations, which makes it a baseline for how much structure the local moves add.
The implementation also rejects a zero or subnormal ratio in the quotient's floating-point type. This range check leaves equal positive temperatures valid, even when their absolute values are subnormal. The executable schedule is a floating-point approximation to the ideal geometric sequence.
PythonIn [22]Expand
def reverse_segment(perm, i, j):
p = list(perm)
p[i : j + 1] = p[i : j + 1][::-1]
return tuple(p)
def hill_climb(limit, seed):
rng = np.random.default_rng(seed)
b = Budget(limit)
current = nearest_neighbor()
current_score = b.score(current)
while b.evals < limit:
best_local, best_local_score = None, np.inf
for i in range(8):
for j in range(i + 1, 8):
if b.evals >= limit:
return b.best_perm, b.best_score, b.trace()
n = reverse_segment(current, i, j)
s = b.score(n)
if best_local is None or s < best_local_score - 1e-12:
best_local, best_local_score = n, s
if best_local_score < current_score - 1e-12:
current, current_score = best_local, best_local_score
else:
if b.evals >= limit:
break
current = tuple(rng.permutation(np.arange(1, 9)))
current_score = b.score(current)
return b.best_perm, b.best_score, b.trace()
def simulated_annealing(limit, seed, T0=2.0, T1=0.01):
if not (np.isfinite(T0) and np.isfinite(T1) and 0 < T1 <= T0):
raise ValueError("temperatures must be finite with 0 < T1 <= T0")
temperature_ratio = T1 / T0
if temperature_ratio < np.finfo(np.asarray(temperature_ratio).dtype).tiny:
raise ValueError(
"temperature ratio must be normal in its floating-point dtype"
)
rng = np.random.default_rng(seed)
b = Budget(limit)
current = nearest_neighbor()
current_score = b.score(current)
while b.evals < limit:
progress = b.evals / (limit - 1)
temp = T0 * (T1 / T0) ** progress
i, j = sorted(rng.choice(8, size=2, replace=False))
n = reverse_segment(current, i, j)
s = b.score(n)
delta = s - current_score
if delta < 0 or rng.random() < np.exp(-delta / temp):
current, current_score = n, s
return b.best_perm, b.best_score, b.trace()
def random_search(limit, seed):
rng = np.random.default_rng(seed)
b = Budget(limit)
b.score(nearest_neighbor())
while b.evals < limit:
p = tuple(rng.permutation(np.arange(1, 9)))
b.score(p)
return b.best_perm, b.best_score, b.trace()Budgeted Comparisons and Repeated-Run Uncertainty
We now run each method on each of seeds with the same -evaluation budget, and record both the final incumbent and the full incumbent trace. We also check every reported final solution: its identifiers must form the required permutation, it must pass the feasibility checks, and its recomputed objective must match the reported best score within tolerance. These assertions are part of the experiment, not decoration; they catch accounting mistakes before those mistakes become a figure.
PythonIn [23]Expand
SEEDS = list(range(20))
BUDGET = 300
METHODS = {
"Hill climbing": hill_climb,
"Simulated annealing": simulated_annealing,
"NN-seeded random search": random_search,
}
results = {name: {"final": [], "traces": []} for name in METHODS}
for seed in SEEDS:
for name, fn in METHODS.items():
perm, best, trace = fn(BUDGET, seed)
assert is_feasible(perm), (
f"infeasible final perm for {name}, seed {seed}"
)
assert np.isclose(objective(perm), best, rtol=0, atol=1e-12)
assert len(trace) == BUDGET
assert np.all(np.isfinite(trace))
assert np.all(np.diff(trace) <= 0)
assert np.isclose(trace[-1], best, rtol=0, atol=1e-12)
results[name]["final"].append(best)
results[name]["traces"].append(trace)ConsoleOut [24]Expand
Method mean std min max Hill climbing 37.8378 0.4567 37.3560 38.3926 Simulated annealing 37.8173 0.6258 37.3560 38.9898 NN-seeded random search 39.2541 0.8956 38.0002 40.7200 Exact optimum: 37.3560
The recorded traces show how quickly each run finds its incumbent. Compare the full distributions and repeated-run summaries rather than claiming universal superiority from this tiny instance. NN-seeded random search reports the best of its starting score and 299 random draws, so its final values do not have the distribution of one uniformly random permutation. The fixed instance, neighborhood, initialization, and temperature schedule all limit how these results generalize.
PythonIn [25]Expand
trajectory_data = {}
for name in METHODS:
traces = np.asarray(results[name]["traces"])
trajectory_data[name] = (
traces.mean(axis=0),
*np.quantile(traces, [0.1, 0.9], axis=0),
)
plot_positions = np.arange(1, BUDGET + 1)
rng_jitter = np.random.default_rng(0)
final_plot_data = {
name: (
np.asarray(results[name]["final"]),
rng_jitter.uniform(-0.08, 0.08, len(SEEDS)),
)
for name in METHODS
}VisualizationOut [26]Expand
The final distribution is the honest summary of quality. It shows not only how good each method is on average, but how much its answer depends on the seed. On this instance the exact optimum is attained by some seeds and missed by others; the spread of a method's final values is the practical price of stochasticity, and it is what we should report when we compare search heuristics.
VisualizationOut [27]Expand
Key takeaways from the implementation:
- The methods receive the same number of complete objective evaluations; this does not equalize runtime, construction work, or memory.
- On these 20seeds, annealing has a slightly lower mean than hill climbing and a larger descriptive standard deviation. This is an observation about one instance and schedule.
- NN-seeded random search has a higher final mean here, while providing a baseline with the same nearest-neighbor initial score.
- Report seed variation and the experimental configuration alongside the mean.
Comments
Add to the conversation
A question, a correction, or an example from your own work.
No comments yet. Be the first to share your thoughts!