Iterated Local Search

You are an expert in iterated local search (ILS) and single-solution metaheuristics for combinatorial optimization. This skill covers the ILS loop — embedded local search, perturbation ("kick") design, and acceptance criteria — plus perturbation-strength tuning, adaptive variants, and the use of ILS as the strong simple baseline that any proposed metaheuristic must beat. Use the framework below to assemble an ILS from a problem-specific descent and a well-matched kick, to tune its three or four parameters, and to diagnose stagnation in an existing implementation.

Initial Assessment

Establish the following before writing any code or recommending parameters:

• Problem class and representation. Permutation (tours, schedules), binary selection, assignment, or mixed? The representation fixes which local searches and kicks are available.
• Existing local search. Is there already a descent procedure? How long does one full descent take on a realistic instance? ILS runs the local search hundreds to thousands of times; a descent that takes minutes makes plain ILS impractical without truncation.
• Evaluation cost. Is the objective cheap to evaluate? Is delta (incremental) evaluation available for the neighborhood moves? Without delta evaluation, the embedded local search usually dominates runtime by 95%+.
• Time budget. Wall-clock seconds per run, and number of runs (seeds × instances). ILS parameters that win at 10 seconds differ from those that win at 10 minutes.
• Quality requirement. Gap to best-known solutions, "beat the current heuristic," or "good feasible fast"? This decides acceptance criterion aggressiveness and restart policy.
• Hard vs soft constraints. Must every visited solution stay feasible, or may a kick pass through infeasibility as long as the local search repairs it?
• Role in the study. Is ILS the proposed method or the baseline in a comparison? As a baseline it must be implemented competently (good kick, tuned strength), otherwise the comparison is meaningless.
• Instance size now and later. An O(n^2) neighborhood scan per descent is fine at n = 100 and hopeless at n = 100,000 without candidate lists.
• Software context. Pure numpy acceptable? Is numba/Cython available for inner loops? Reproducibility requirements (seed policy, deterministic ordering)?

Algorithm Anatomy

ILS searches the set of local optima instead of the set of all solutions. The embedded local search LS maps any solution to a local optimum, so the reachable set collapses to $\mathcal{S}^* = {\mathrm{LS}(s) : s \in \mathcal{S}}$, which is dramatically smaller and has much better average quality than $\mathcal{S}$. ILS is a biased walk on $\mathcal{S}^*$ (Lourenço, Martin & Stützle 2003, "Iterated Local Search", Handbook of Metaheuristics):

$$ s_0 = \mathrm{LS}(s_{\mathrm{init}}), \qquad s't = \mathrm{LS}\big(\mathrm{Perturb}(s_t)\big), \qquad s{t+1} = \begin{cases} s'_t & \text{if } \mathrm{Accept}\big(f(s_t), f(s'_t)\big)\[2pt] s_t & \text{otherwise.} \end{cases} $$

Why this beats independent random restarts: in many landscapes good local optima cluster — the "big valley" structure observed for the TSP by Boese, Kahng & Muddu (1994). A small kick from a good optimum lands in a nearby basin whose optimum is correlated with (and often as good as) the start, and the warm-started local search reaches it in a fraction of the moves a cold start needs. Random restart throws both advantages away.

The four components

Acceptance criteria

• Better: accept iff $f(s') < f(s)$. Strong intensification; the default first try.
• Random walk: always accept. Maximal diversification; useful only with strong kicks.
• Metropolis (fixed T): accept with probability $\min{1, e^{-(f(s') - f(s))/T}}$. Unlike simulated annealing the temperature is constant — ILS needs no cooling schedule because the local search, not the temperature, provides intensification.
• Epsilon-accept: accept iff $f(s') \le (1+\varepsilon) f(s)$, $\varepsilon \approx$ 0.02–0.05. Deterministic mild diversification.
• Restart: after $L$ consecutive non-improving kicks, reset the current solution to the best-so-far (intensifying) or to a fresh construction (diversifying).

When to choose ILS

• Use ILS when a strong, fast local search already exists for the problem. ILS adds roughly 20 lines on top of it and is the highest benefit-to-effort metaheuristic.
• Use ILS as the baseline in every metaheuristic study on permutation-like problems; iterated greedy (an ILS with construction-based kicks) is state of the art for the permutation flow shop (Ruiz & Stützle 2007).
• Prefer tabu search when the failure mode is cycling on plateaus inside one basin rather than basin escape.
• Prefer GRASP when randomized construction is more natural than perturbing a complete solution (e.g., set covering); GRASP is essentially restart-ILS with the randomness moved into construction.
• Prefer LNS/ALNS when tight constraints make small kicks useless and destroy-repair is the natural move (rich vehicle routing, complex scheduling).

Cost model

Per iteration: one kick, O(strength), plus one warm-started descent. A warm 2-opt descent after a double-bridge only needs to repair the region around the 4 changed edges — with don't-look bits and neighbor lists this is near O(n) instead of the O(n^2) cold-start scan. Total work = iterations × warm-descent cost; always report wall-clock alongside iteration counts, because LS truncation trades quality-per-iteration for kicks-per-second.

Parameter guidance

Reference Implementation

The framework separates the problem-independent loop from the four problem-specific callables. The incumbent update is deliberately independent of the acceptance decision: the walk may accept worse solutions, but the best-so-far is never lost.

ILS(construct, LocalSearch, Perturb, Accept, budget):
    s  <- LocalSearch(construct())        # initial local optimum
    s* <- s                               # incumbent
    while budget remains:
        s' <- Perturb(s)                  # kick: leave the current basin
        s' <- LocalSearch(s')             # descend into the neighboring basin
        if f(s') < f(s*):
            s* <- s'                      # incumbent update, independent of Accept
        if Accept(f(s), f(s')):
            s <- s'                       # walk step on the space of local optima
    return s*

Acceptance criteria as plain callables, so they can be swapped without touching the loop:

"""Acceptance criteria for ILS: callables (current_cost, candidate_cost, rng) -> bool."""
import math
from typing import Callable

import numpy as np

AcceptFn = Callable[[float, float, np.random.Generator], bool]


def accept_better(current: float, candidate: float, rng: np.random.Generator) -> bool:
    """Accept only strict improvements: the classic, most exploitative choice."""
    return candidate < current


def accept_always(current: float, candidate: float, rng: np.random.Generator) -> bool:
    """Random-walk acceptance: maximal diversification, rarely good on its own."""
    return True


def make_metropolis(temperature: float) -> AcceptFn:
    """Metropolis acceptance at a fixed temperature: accept worse candidates with
    probability exp(-delta / T). Interpolates between accept_better (T -> 0)
    and accept_always (T -> infinity); no cooling schedule is needed in ILS."""
    def accept(current: float, candidate: float, rng: np.random.Generator) -> bool:
        if candidate <= current:
            return True
        return float(rng.random()) < math.exp(-(candidate - current) / temperature)
    return accept


def make_epsilon_accept(epsilon: float) -> AcceptFn:
    """Accept candidates at most a factor (1 + epsilon) worse than the current
    cost. Deterministic mild diversification; epsilon in [0.02, 0.05] is typical."""
    def accept(current: float, candidate: float, rng: np.random.Generator) -> bool:
        return candidate <= (1.0 + epsilon) * current
    return accept

The loop itself, with restart acceptance handled via restart_after, plus a complete smoke test on number partitioning (a rugged landscape where plain hill climbing gets trapped immediately):

"""Problem-independent ILS loop. Plug in construct / local_search / perturb / accept.
Uses accept_better from the acceptance-criteria block above."""
from dataclasses import dataclass, field
from typing import Callable

import numpy as np


@dataclass
class ILSResult:
    """Best solution found plus the trace needed for convergence reporting."""
    best: np.ndarray
    best_cost: float
    n_iterations: int
    n_accepted: int
    history: list[tuple[int, float]] = field(default_factory=list)


def iterated_local_search(
    construct: Callable[[np.random.Generator], np.ndarray],
    local_search: Callable[[np.ndarray], tuple[np.ndarray, float]],
    perturb: Callable[[np.ndarray, np.random.Generator], np.ndarray],
    accept: Callable[[float, float, np.random.Generator], bool],
    n_iterations: int = 500,
    restart_after: int | None = None,
    seed: int = 0,
) -> ILSResult:
    """Run ILS for n_iterations kicks. `local_search` maps any solution to
    (local_optimum, cost). `restart_after` resets the current solution to the
    best-so-far after that many consecutive non-improving iterations."""
    rng = np.random.default_rng(seed)
    current, current_cost = local_search(construct(rng))
    best, best_cost = current.copy(), current_cost
    history = [(0, best_cost)]
    n_accepted, stall = 0, 0
    for it in range(1, n_iterations + 1):
        candidate, candidate_cost = local_search(perturb(current, rng))
        if accept(current_cost, candidate_cost, rng):
            current, current_cost = candidate, candidate_cost
            n_accepted += 1
        if candidate_cost < best_cost - 1e-12:
            best, best_cost = candidate.copy(), candidate_cost
            history.append((it, best_cost))
            stall = 0
        else:
            stall += 1
            if restart_after is not None and stall >= restart_after:
                current, current_cost = best.copy(), best_cost
                stall = 0
    return ILSResult(best, best_cost, n_iterations, n_accepted, history)


def make_partition_problem(weights: np.ndarray) -> tuple[Callable, Callable, Callable]:
    """Number partitioning: split items into two sets minimizing the absolute
    difference of their sums. Rugged landscape; a good ILS smoke test."""
    def construct(rng: np.random.Generator) -> np.ndarray:
        return rng.integers(0, 2, size=weights.size)

    def local_search(x: np.ndarray) -> tuple[np.ndarray, float]:
        x = x.copy()
        while True:
            s = float(weights @ (2 * x - 1))
            flip_costs = np.abs(s - 2 * (2 * x - 1) * weights)  # cost after each flip
            k = int(np.argmin(flip_costs))
            if flip_costs[k] < abs(s) - 1e-9:
                x[k] = 1 - x[k]
            else:
                return x, abs(s)

    def perturb(x: np.ndarray, rng: np.random.Generator) -> np.ndarray:
        y = x.copy()
        idx = rng.choice(x.size, size=3, replace=False)
        y[idx] = 1 - y[idx]
        return y

    return construct, local_search, perturb


rng = np.random.default_rng(7)
weights = rng.integers(1, 1000, size=24).astype(float)
construct, local_search, perturb = make_partition_problem(weights)
hill_cost = local_search(construct(np.random.default_rng(7)))[1]
result = iterated_local_search(construct, local_search, perturb, accept_better,
                               n_iterations=300, seed=7)
print(f"single descent: {hill_cost:.0f}   ILS best: {result.best_cost:.0f}")
# Expected: single descent: 2   ILS best: 0  (a perfect partition exists; ILS finds it)

Note the vectorized descent: all single-flip costs are computed in one numpy expression per pass instead of an inner Python loop. For deeper delta-evaluation patterns see local-search-and-neighborhoods.

Worked Example 1: TSP with Double-Bridge Kicks

The canonical ILS. Local search is 2-opt; the kick is the double-bridge: cut the tour into four segments A|B|C|D and reconnect them as A-C-B-D. This 4-opt move changes exactly four edges, keeps every segment's orientation, and — the key property — cannot be reversed by any single 2-opt move, so the descent cannot simply undo it. It was introduced as the kick of the large-step Markov chain method of Martin, Otto & Felten (1991), the direct ancestor of ILS.

Building blocks (instance, evaluation, construction, descent):

"""TSP building blocks: instance, evaluation, construction, vectorized 2-opt."""
import numpy as np


def random_euclidean_tsp(n: int, seed: int) -> np.ndarray:
    """n points uniform in the unit square; returns the (n, n) distance matrix."""
    rng = np.random.default_rng(seed)
    pts = rng.random((n, 2))
    diff = pts[:, None, :] - pts[None, :, :]
    return np.sqrt((diff ** 2).sum(axis=2))


def tour_length(tour: np.ndarray, dist: np.ndarray) -> float:
    """Length of the closed tour visiting cities in `tour` order."""
    return float(dist[tour, np.roll(tour, -1)].sum())


def nearest_neighbor_tour(dist: np.ndarray, start: int = 0) -> np.ndarray:
    """Greedy nearest-neighbor construction starting from city `start`."""
    n = dist.shape[0]
    visited = np.zeros(n, dtype=bool)
    tour = np.empty(n, dtype=np.int64)
    tour[0] = start
    visited[start] = True
    for i in range(1, n):
        row = np.where(visited, np.inf, dist[tour[i - 1]])
        tour[i] = int(np.argmin(row))
        visited[tour[i]] = True
    return tour


def two_opt(tour: np.ndarray, dist: np.ndarray) -> tuple[np.ndarray, float]:
    """2-opt descent to a local optimum. For each first edge, the deltas of all
    compatible second edges are evaluated in one vectorized pass; the reversal
    applies the best one. See local-search-and-neighborhoods for O(1) delta
    derivations and candidate-list accelerations."""
    tour = tour.copy()
    n = tour.size
    improved = True
    while improved:
        improved = False
        for i in range(n - 2):
            a, b = tour[i], tour[i + 1]
            hi = n - 1 if i > 0 else n - 2      # skip the edge sharing city tour[0]
            js = np.arange(i + 2, hi + 1)
            if js.size == 0:
                continue
            c = tour[js]
            d = tour[(js + 1) % n]
            deltas = dist[a, c] + dist[b, d] - dist[a, b] - dist[c, d]
            k = int(np.argmin(deltas))
            if deltas[k] < -1e-10:
                j = int(js[k])
                tour[i + 1:j + 1] = tour[i + 1:j + 1][::-1]
                improved = True
    return tour, tour_length(tour, dist)

The kick and the assembled solver. With accept-better and double-bridge, this is the textbook TSP ILS; for stronger machinery (Or-opt, Lin-Kernighan moves, TSPLIB instances) see traveling-salesman-problem.

"""Double-bridge kick and the assembled TSP ILS.
Uses iterated_local_search / accept_better (framework blocks) and
random_euclidean_tsp / nearest_neighbor_tour / two_opt (previous block)."""
import numpy as np


def double_bridge(tour: np.ndarray, rng: np.random.Generator) -> np.ndarray:
    """Cut the tour into four segments A|B|C|D and reconnect as A-C-B-D.
    No single 2-opt move can reverse this kick (Martin, Otto & Felten 1991)."""
    n = tour.size
    i, j, k = np.sort(rng.choice(np.arange(1, n), size=3, replace=False))
    return np.concatenate([tour[:i], tour[j:k], tour[i:j], tour[k:]])


def solve_tsp_ils(dist: np.ndarray, n_iterations: int = 300, seed: int = 0) -> "ILSResult":
    """TSP ILS: nearest-neighbor start, 2-opt descent, double-bridge kicks,
    accept-better. The strong simple baseline for any TSP heuristic study."""
    return iterated_local_search(
        construct=lambda rng: nearest_neighbor_tour(dist, start=0),
        local_search=lambda t: two_opt(t, dist),
        perturb=double_bridge,
        accept=accept_better,
        n_iterations=n_iterations,
        seed=seed,
    )


dist = random_euclidean_tsp(n=60, seed=3)
start_cost = two_opt(nearest_neighbor_tour(dist), dist)[1]
result = solve_tsp_ils(dist, n_iterations=300, seed=3)
print(f"2-opt local optimum: {start_cost:.4f}   ILS best: {result.best_cost:.4f}")
# Expected: 2-opt local optimum: 6.2630   ILS best: 6.0728  (~3% gained by kicking)

A single double-bridge per iteration is the right default strength: it relocates two segments while leaving most of the tour intact, so successive local optima stay correlated. Stacking several double-bridges is the standard way to increase strength (used in the adaptive variant under Advanced Techniques).

Worked Example 2: Permutation Flow-Shop with NEH Start

In the permutation flow-shop problem (PFSP), n jobs visit M machines in the same machine order, and all machines process jobs in the same job order, so a solution is one permutation $\pi$. With processing times $p_{j,m}$, completion times follow

$$ C_{\pi(i),m} = \max{C_{\pi(i-1),m},; C_{\pi(i),m-1}} + p_{\pi(i),m}, \qquad C_{\max}(\pi) = C_{\pi(n),M}, $$

with $C_{\pi(0),m} = C_{\pi(i),0} = 0$. The objective is to minimize the makespan $C_{\max}$.

Three classic ingredients make the ILS strong here:

• NEH construction (Nawaz, Enscore & Ham 1983): sort jobs by decreasing total processing time, insert each at its best position in the partial sequence.
• Taillard acceleration (Taillard 1990): evaluating all $k{+}1$ insertion positions of one job into a length-$k$ sequence costs $O(kM)$ total — not $O(k^2 M)$ — using head matrix $e$ (prefix completion times), tail matrix $q$ (time from each job's start to the end of the schedule), and $f$ (completion times of the inserted job at every position): the makespan after inserting at position $i$ is $\max_m (f_{i,m} + q_{i,m})$.
• Destruction-construction kick: remove $d$ random jobs, greedily reinsert each at its best position. With this kick and a constant-temperature Metropolis acceptance, ILS is the iterated greedy (IG) algorithm of Ruiz & Stützle (2007) — still the reference method for the PFSP. The earlier ILS of Stützle (1998) used random insertion/swap kicks.

"""Permutation flow-shop: makespan, Taillard-accelerated insertion, NEH."""
import numpy as np


def makespan(seq: np.ndarray, p: np.ndarray) -> float:
    """Cmax of job sequence `seq`; p has shape (n_jobs, n_machines)."""
    c = np.zeros(p.shape[1])
    for j in seq:
        c[0] += p[j, 0]
        for m in range(1, p.shape[1]):
            c[m] = max(c[m], c[m - 1]) + p[j, m]
    return float(c[-1])


def best_insertion(seq: np.ndarray, job: int, p: np.ndarray) -> tuple[int, float]:
    """Best position and resulting Cmax for inserting `job` into `seq`,
    evaluated for all |seq|+1 positions in O(|seq| * M) total (Taillard 1990)."""
    k, m = seq.size, p.shape[1]
    e = np.zeros((k + 1, m))            # e[i]: completion times of the i-th prefix job
    for i in range(1, k + 1):
        t = p[seq[i - 1]]
        e[i, 0] = e[i - 1, 0] + t[0]
        for mm in range(1, m):
            e[i, mm] = max(e[i, mm - 1], e[i - 1, mm]) + t[mm]
    q = np.zeros((k + 1, m))            # q[i]: tail of seq[i]; q[k] = 0 covers appending
    for i in range(k - 1, -1, -1):
        t = p[seq[i]]
        q[i, m - 1] = q[i + 1, m - 1] + t[m - 1]
        for mm in range(m - 2, -1, -1):
            q[i, mm] = max(q[i, mm + 1], q[i + 1, mm]) + t[mm]
    f = np.empty((k + 1, m))            # f[i]: completions of `job` inserted at i
    f[:, 0] = e[:, 0] + p[job, 0]
    for mm in range(1, m):              # vectorized over all k+1 positions at once
        f[:, mm] = np.maximum(f[:, mm - 1], e[:, mm]) + p[job, mm]
    cmax = (f + q).max(axis=1)
    pos = int(np.argmin(cmax))
    return pos, float(cmax[pos])


def neh(p: np.ndarray) -> np.ndarray:
    """NEH construction (Nawaz, Enscore & Ham 1983): insert jobs in order of
    decreasing total processing time, each at its best position."""
    order = np.argsort(-p.sum(axis=1), kind="stable")
    seq = order[:1].copy()
    for job in order[1:]:
        pos, _ = best_insertion(seq, int(job), p)
        seq = np.insert(seq, pos, job)
    return seq


def random_pfsp_instance(n_jobs: int, n_machines: int, seed: int) -> np.ndarray:
    """Taillard-style instance: processing times uniform on [1, 99]."""
    rng = np.random.default_rng(seed)
    return rng.integers(1, 100, size=(n_jobs, n_machines)).astype(float)


p = random_pfsp_instance(n_jobs=20, n_machines=10, seed=5)
print(f"NEH makespan: {makespan(neh(p), p):.0f}")
# Expected: NEH makespan: 1707

The local search is a best-insertion descent (remove each job, reinsert it at its best position, repeat until no move improves), and the kick reuses best_insertion for greedy repair. Acceptance follows the Ruiz–Stützle constant temperature $T = \tau \cdot \bar{p}/10$ with $\tau = 0.4$.

"""Insertion local search, destruction kick, and the assembled flow-shop ILS.
Uses iterated_local_search / make_metropolis (framework blocks) and
makespan / best_insertion / neh / random_pfsp_instance (previous block)."""
import numpy as np


def insertion_local_search(seq: np.ndarray, p: np.ndarray) -> tuple[np.ndarray, float]:
    """Best-insertion descent: remove each job, reinsert at its best position;
    repeat full passes until no single-job move improves the makespan."""
    seq = seq.copy()
    current = makespan(seq, p)
    improved = True
    while improved:
        improved = False
        for job in list(seq):
            partial = seq[seq != job]
            pos, new_cmax = best_insertion(partial, int(job), p)
            if new_cmax < current - 1e-9:
                seq = np.insert(partial, pos, job)
                current = new_cmax
                improved = True
    return seq, current


def make_destruction_kick(p: np.ndarray, d: int):
    """Kick: remove d random jobs, greedily reinsert each at its best position.
    This construction-based kick turns ILS into iterated greedy (Ruiz & Stützle 2007)."""
    def kick(seq: np.ndarray, rng: np.random.Generator) -> np.ndarray:
        removed = rng.choice(seq, size=d, replace=False)
        partial = seq[~np.isin(seq, removed)]
        for job in rng.permutation(removed):
            pos, _ = best_insertion(partial, int(job), p)
            partial = np.insert(partial, pos, job)
        return partial
    return kick


def solve_pfsp_ils(p: np.ndarray, n_iterations: int = 150, d: int = 4,
                   tau: float = 0.4, seed: int = 0) -> "ILSResult":
    """Flow-shop ILS: NEH start, insertion descent, destruction kicks,
    constant-temperature Metropolis acceptance."""
    temperature = tau * float(p.mean()) / 10.0
    return iterated_local_search(
        construct=lambda rng: neh(p),
        local_search=lambda s: insertion_local_search(s, p),
        perturb=make_destruction_kick(p, d),
        accept=make_metropolis(temperature),
        n_iterations=n_iterations,
        seed=seed,
    )


p = random_pfsp_instance(n_jobs=20, n_machines=10, seed=5)
neh_cost = makespan(neh(p), p)
result = solve_pfsp_ils(p, n_iterations=150, d=4, tau=0.4, seed=5)
print(f"NEH: {neh_cost:.0f}   ILS best: {result.best_cost:.0f}")
# Expected: NEH: 1707   ILS best: 1611  (about 5.6% below the NEH start)

Default d = 4 removed jobs is robust across Taillard instance sizes from 20×5 to 500×20; the Metropolis acceptance matters more than d once d is in the 2–8 range (Ruiz & Stützle 2007). For NEH tie-breaking variants, IG refinements, and Taillard benchmark protocol, see flow-shop-scheduling.

Advanced Techniques

Adaptive perturbation strength

Fixed-strength kicks are a compromise. The standard adaptive rule mirrors VNS shaking: reset strength to the minimum whenever a new best is found, and grow it after every block of non-improving iterations. This keeps kicks minimal inside a productive big-valley region and escalates them only when the region is exhausted.

"""ILS with stagnation-driven kick strength.
Uses accept_better plus the TSP blocks (random_euclidean_tsp, nearest_neighbor_tour,
two_opt, double_bridge) defined above."""
import numpy as np
from typing import Callable


def adaptive_ils(construct: Callable, local_search: Callable, perturb: Callable,
                 accept: Callable, n_iterations: int = 500, s_min: int = 1,
                 s_max: int = 8, grow_after: int = 15, seed: int = 0
                 ) -> tuple[np.ndarray, float]:
    """ILS where `perturb(solution, strength, rng)` takes an explicit strength:
    reset to s_min on a new best, grow by one every `grow_after` stalls."""
    rng = np.random.default_rng(seed)
    current, current_cost = local_search(construct(rng))
    best, best_cost = current.copy(), current_cost
    strength, stall = s_min, 0
    for _ in range(n_iterations):
        candidate, candidate_cost = local_search(perturb(current, strength, rng))
        if accept(current_cost, candidate_cost, rng):
            current, current_cost = candidate, candidate_cost
        if candidate_cost < best_cost - 1e-12:
            best, best_cost = candidate.copy(), candidate_cost
            strength, stall = s_min, 0
        else:
            stall += 1
            if stall % grow_after == 0:
                strength = min(strength + 1, s_max)
    return best, best_cost


def multi_bridge(tour: np.ndarray, strength: int, rng: np.random.Generator) -> np.ndarray:
    """Apply `strength` consecutive double-bridge kicks."""
    for _ in range(strength):
        tour = double_bridge(tour, rng)
    return tour


dist = random_euclidean_tsp(n=80, seed=5)
best, cost = adaptive_ils(
    construct=lambda rng: nearest_neighbor_tour(dist),
    local_search=lambda t: two_opt(t, dist),
    perturb=multi_bridge,
    accept=accept_better,
    n_iterations=400, seed=5,
)
print(f"adaptive ILS best: {cost:.4f}")
# Expected: adaptive ILS best: 7.1109  (ties fixed-strength ILS on this instance;
# the gain appears on instances where strength-1 kicks stagnate)

Calibrating the Metropolis temperature

Do not guess T. Sample 50–200 kicks from a few local optima of a representative instance, record the worsening deltas $\Delta > 0$ of the resulting local optima, and set $T = -\Delta_{\mathrm{med}} / \ln(p_{\mathrm{acc}})$ for a target acceptance probability $p_{\mathrm{acc}}$ of the median-worsening move (0.02–0.05 is a good target). This is the same calibration logic used for initial temperatures in simulated annealing, applied once to a constant T. Problem-normalized rules like $T = \tau,\bar{p}/10$ for the PFSP encode the same idea when the objective scale is known in advance.

Restarts, multistart, and elite-guided kicks

Restart acceptance (jump back to the incumbent after L stalls) intensifies; restarting from a fresh construction diversifies — combine both by alternating. Independent ILS runs are embarrassingly parallel: one process per seed, keep the best. When single runs stagnate early, maintain a small elite pool (5–10 best distinct solutions) and kick from a random elite member instead of the current solution; this is the cheapest population-flavored upgrade before moving to a full memetic algorithm. If construction-side randomness fits the problem better than solution-side kicks, that design point is GRASP — see grasp.

Truncated and time-boxed local search

Inside ILS the local search does not need to reach a true local optimum every iteration. A single first-improvement pass, a descent capped at a move budget, or 2-opt restricted to the neighborhood of the kicked components ("don't-look bits" set everywhere except the four changed edges) often triples the number of iterations within the same wall-clock with little quality loss per iteration. Tune the depth/iterations trade-off on a small instance grid before the main experiments; for kick-operator design options beyond those used here, see mutation-and-perturbation-operators.

Practical Challenges

The local search immediately undoes the kick. Symptom: consecutive local optima are identical. The kick lives inside the local search's own neighborhood (e.g., a single 2-opt kick under a 2-opt descent). Use a structurally different move — double-bridge under 2-opt, segment insertion under swap descent — or stack several moves. Measure it: hash each local optimum and track the fraction of iterations returning the previous hash; above ~30%, strengthen the kick.

ILS behaves like random restart. Symptom: quality no better than independent multi-start under the same budget. The kick is too strong, destroying the correlation between successive optima. Compare the average distance (e.g., differing edges or positions) between consecutive local optima against the distance between independent ones; consecutive should be markedly smaller. Reduce strength until it is.

The embedded local search consumes the whole budget. Profile first — the descent is almost always >90% of runtime. Add delta evaluation, candidate lists, and don't-look bits; re-optimize only the region the kick touched; or truncate the descent. Only then consider numba/Cython for the scan loop.

Accept-better stalls after a few hundred iterations. The walk is stuck in one big-valley region. Soften acceptance (epsilon or Metropolis), add restart_after, or enable adaptive strength. If none of this helps, the landscape may lack global structure — check fitness-distance correlation before investing more in ILS.

Objective drift from incremental evaluation. Delta-evaluated costs accumulate floating-point error or hide bugs. Recompute the objective from scratch every few hundred iterations and assert agreement within 1e-6 of the incremental value; on integer-valued objectives demand exact equality.

Large run-to-run variance. Report at least 10 seeds per instance with mean, standard deviation, and best; high variance usually means too-strong kicks or an acceptance criterion close to random walk. Equal wall-clock budgets — never equal iteration counts — are the only fair basis for comparing against other methods.

Kicks break feasibility. Three orderly options: design feasibility-preserving kicks (relocate within feasible slots only); let the kick destroy and a greedy repair restore feasibility, as in the flow-shop destruction kick; or accept transient infeasibility with a penalty the local search can pay down. Pick one mechanism and validate every accepted solution with an independent checker.

"ILS is too simple to publish." Simplicity is the point: Lourenço, Martin & Stützle (2003) position ILS as the baseline every new method must beat, and a competently tuned IG remains state of the art for the PFSP (Ruiz & Stützle 2007). A paper whose proposed method loses to 60 lines of ILS under equal budget has its answer; include the comparison with proper statistical testing.

Tools & Libraries

Output Format

A complete ILS deliverable contains:

1. Configuration summary — one table, so the run is reproducible from the report alone:

   Component	Choice
   Construction	NEH (total-processing-time order)
   Local search	best-insertion descent, full passes
   Kick	destruction-construction, d = 4
   Acceptance	Metropolis, T = 0.4 · mean(p)/10
   Budget	150 iterations ≈ 2.1 s; seeds 0–9

2. Convergence evidence — the history trace (iteration, best cost) per seed, plotted as best-so-far curves with a min-max or quartile band across seeds.
3. Solution quality table — per instance: best, mean, standard deviation over seeds, and percentage gap to the best-known solution or to the construction heuristic when no reference value exists.
4. Runtime breakdown — share of time in the local search vs kicks vs evaluation, and iterations per second; this justifies (or motivates) truncation choices.
5. Code artifacts — the four callables plus the framework loop, an instance generator/parser with explicit seeds, and an independent feasibility-and-objective checker applied to every reported solution.
6. Baseline comparison — when ILS is the baseline: identical budgets, identical instances and seeds, and a paired statistical test on per-instance results.

Questions to Ask

• What problem and representation — permutation, binary, assignment, something mixed?
• Does a local search already exist, and how long is one descent on a full-size instance?
• Is delta evaluation available for the neighborhood moves, or only full recomputation?
• What is the wall-clock budget per run, and how many runs are planned?
• What is the quality target — gap to best-known, beat a current heuristic, or feasible-fast?
• Must every visited solution be feasible, or may kicks pass through infeasibility?
• Is ILS the proposed method or the baseline, and what comparison protocol is required?
• How large are the instances now, and how large will they get in deployment?
• Are numba/Cython acceptable if the descent needs more speed than numpy gives?

Related Skills

• local-search-and-neighborhoods — when the embedded descent needs better neighborhood design, delta evaluation, or scanning-order decisions.
• mutation-and-perturbation-operators — when designing or strengthening kick moves beyond double-bridge and destruction-reinsertion.
• grasp — when randomized construction restarts fit the problem better than perturbing one incumbent solution.
• traveling-salesman-problem — when the TSP application needs formulations, stronger local searches, or TSPLIB benchmark workflows.
• flow-shop-scheduling — when the flow-shop application needs NEH variants, iterated greedy refinements, or Taillard benchmark protocol.