Is iterated local search just random restart?

No. Its perturbations typically build on previously optimized solutions; complete restarts can be included as one strategy.

Must every accepted solution improve?

No. That depends on the acceptance rule.

Does reaching a local optimum prove completion?

It completes one local-search phase, but generally does not prove global optimality.

AI Glossary / Mathematics and optimization / Intermediate

Iterated local search

Definition

Iterated local search is an optimization framework that repeatedly improves a solution locally, perturbs it, improves the perturbed solution, and decides whether to adopt the resulting local optimum. It searches among locally optimized solutions rather than relying on one uninterrupted descent. Its effectiveness depends on how local search, perturbation, and acceptance work together.

What it means

A local search examines permitted small changes and takes an improving one until none remains. That endpoint can be a local optimum even when better solutions exist elsewhere. Iterated local search creates opportunities to leave the endpoint's surrounding basin and reach another.
The perturbation is more than simply continuing ordinary improvement: it can temporarily worsen the solution or change several components together. Afterward, local search restores local quality. The acceptance rule decides which locally improved solution becomes the starting point for the next perturbation. Keeping a separate best-so-far record protects useful discoveries.

How it works

Begin with an initial feasible solution and apply a specified local search. Perturb the current local optimum, repair feasibility if necessary, and run local search again. Compare the resulting candidate with the current solution using an explicit acceptance policy. Update the best recorded feasible solution whenever warranted, and repeat until the computation budget or another stopping condition is reached.
Possible acceptance policies retain only improvements, accept every new local optimum, or sometimes accept a worse one. Perturbations can also adapt to search history. There is no single universally best combination; changing one component can alter what is effective for the others.

Three practical examples

A delivery-routing experiment can perturb a tour with several coordinated edge changes and then apply a local route-improvement procedure.
A production scheduler can disturb part of a feasible job order, repair any conflicts, and optimize the revised schedule locally.
A graph-partitioning study can modify an assignment of vertices to groups and then improve the cut objective, comparing several acceptance strategies under equal budgets.

Think of it this way

Imagine hiking downhill into a valley, taking a deliberate excursion over a ridge, and descending again. You compare the new valley with the old one before deciding where to explore next. The analogy does not imply a geographic surface: solutions may be discrete schedules or assignments, and the permitted moves define their neighborhoods.

Worked example

Consider an original five-state minimization problem. The states form a chain A-B-C-D-E, and ordinary local-search moves connect only adjacent states. Their costs are A=5, B=8, C=4, D=7, and E=1. Use steepest descent: select the adjacent state with the lowest strictly smaller cost, stopping if none exists.
Starting at A, local search stops immediately because its only neighbor, B, costs 8. Therefore A is a local optimum with cost 5. It is not the global optimum because E costs 1.
The first stipulated perturbation moves from A to B, temporarily increasing the cost from 5 to 8. Running local search from B compares A at 5 with C at 4, chooses C, and stops there: C's neighbors B and D cost 8 and 7. Under an improvement-only acceptance rule, adopt C because its locally optimized cost 4 is better than the current cost 5. Update the best record to C.
Now suppose a weak perturbation sends C back to B. Local search again returns to C, so the completed iteration makes no progress. Repeating this same perturbation indefinitely would keep revisiting C. The mere presence of a perturbation step does not guarantee useful exploration.
Instead, stipulate a perturbation from C to D. Local search at D compares C at 4 with E at 1 and chooses E. Since E's only neighbor D costs 7, E is a local optimum. Accept it and update the best cost to 1. Enumerating the five supplied costs independently confirms that this particular endpoint is globally optimal in the toy problem.
Finally, a larger perturbation from E to B would descend to C, with cost 4. The improvement-only rule rejects that locally optimized candidate and keeps E. An always-accept rule would move the current state to C while a separate best record could still retain E. This difference explains why current solution, proposed candidate, and best found solution should be recorded separately. The trace prescribes perturbations rather than sampling randomly.

Illustrative case study

In a fictional dispatch-planning study, Cedar Lane Couriers tests an iterated local search on a fixed set of route instances. It starts with feasible routes, records the results of its ordinary improvement procedure, and compares several perturbation strengths under the same time limit.
The analysts discover that one small perturbation frequently returns to the same local optimum. They revise the experiment to measure repeated endpoints and compare acceptance rules. They retain feasible best routes but do not describe them as proven global optima. This is an illustrative evaluation process, not evidence of a particular commercial improvement.

Common misconceptions and mistakes

Repeating local search from exactly the same state with identical deterministic rules does not create meaningful exploration. A stronger perturbation is not automatically better: it can discard useful structure and make each local-improvement phase expensive. A weak perturbation may simply be undone.
Do not confuse accepting a worse candidate with losing the best known answer; a separate record avoids that. Also distinguish an algorithm that maintains feasibility from one that uses penalties or repairs. The treatment of infeasible candidates must be explicit before costs are compared.

Business use

Business teams can use this framework when good feasible solutions are valuable and exact optimization is too costly for their instances. Evaluation should include feasibility checks, a baseline, equivalent runtime budgets, repeated runs when randomness is used, and the distribution of solution quality. Report whether any optimality bound is available. A promising best run alone says little about the reliability of a time-limited planning process.

Check your understanding

Why does perturbing C to B fail to improve the toy solution?

Answer: Steepest descent from B selects C again, returning to the same local optimum and cost.

Related terms

Local search
Neighborhood
Variable neighborhood search
Local optimum
Perturbation
Acceptance criterion
Metaheuristic
Random restart
Best-so-far solution

Learn next

Change D's cost from 7 to 0.5 and repeat the trace. Identify which states remain local optima and explain why E is no longer one. Then compare improvement-only and always-accept policies while keeping the same perturbation sequence.

Sources

Primary source: Lourenco, Martin, and Stutzle, Iterated Local Search, original author survey: https://econ-papers.upf.edu/papers/513.pdf . The five-state landscape, deterministic trace, and fictional dispatch study are original.

Previous: Iterated extended Kalman filter Next: Iteration