Iterated local search
Algorithms AIMech:IteratedLocalSearch DRAFT
Aliases: ILS
A metaheuristic that builds a single search trajectory among solutions returned by an embedded optimizer by perturbing the current accepted solution, rerunning that optimizer, and applying an acceptance criterion to the resulting candidate.
Identity Notes & Concept Scope
The ILS framework includes the common local-minimum formulation but permits a more general, possibly stochastic or history-dependent embedded optimizer. Historical names such as iterated Lin–Kernighan and large-step Markov chains denote particular developments, not exact aliases of every ILS configuration. Single-chain search distinguishes the framework from population selection and distribution refitting; optional restarts and hybrids require their own declared choices. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 301 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 37 and 37 lines respectively. All 13 unique hit contents were inspected: prior local-search candidate leads, Ant System’s feasibility-list distinction, and their saved reports/reviews. These were references to methods rather than existing candidate records. Six exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and seven native neighboring mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Generate an initial solution and apply the embedded LocalSearch routine to obtain a current optimized solution. Repeat: perturb that current solution, apply LocalSearch to the perturbed intermediate point, then use an acceptance criterion comparing the current and candidate optimized solutions, potentially with search history, to choose the next current solution. Repeat until the declared termination condition. In the simplified deterministic memoryless setting, LocalSearch maps candidates into a reduced set of local optima, and perturbation followed by local search induces transitions among them. The general framework need not explicitly enumerate neighborhoods in that reduced space. Accepted variants include retaining only strict improvements, always accepting the newly optimized candidate, or temperature-dependent acceptance; improvement-only selection is not a universal requirement. Perturbation and acceptance may use history, and the embedded procedure can itself be stochastic or use memory.
⚠️ Curated Limitations & Negative Results
- Perturbations that are too weak can return repeatedly to the same optimizer output; independent large perturbations remove the current solution’s influence from proposed starts and approach random-restart behavior. The full behavior still depends on the acceptance rule and the embedded optimizer.
- A deterministic memoryless embedded routine supports the simplified basin-of-attraction picture. General stochastic or history-dependent routines need not define the same fixed partition; history-free transition descriptions cannot be assumed for every ILS variant.
- Transitions between optimized solutions need not be reversible, and deterministic perturbations can produce short cycles. The framework alone is neither a target-invariant MCMC sampler nor a global-optimality or cycle-freedom guarantee.
- Initialization, perturbation, local-search termination, acceptance, best-so-far bookkeeping and restart conventions must be declared for an executable instance. The source reports sensitivity to module interactions, including settings worse than random restart; no universal performance ranking or empirical result is curated.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable AIO target was found for this general optimization framework in the inspected snapshot and semantic neighborhood. Search memory, local costs and optional machine-learning applications do not by themselves identify a learning task or model class.
Search Scope: All 442 pinned AIO CLASS identities and scoped synonyms, all 301 preceding maintained identities, ignored/hidden full-checkout text, six exact AIO targets and seven native neighboring methods.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:TrainingStrategy
|
The definition concerns preprocessing or training machine-learning models. General local-search optimization is not restricted to such training. |
AIO:MachineLearningTask
|
The target concerns learning methods from data; minimizing a supplied combinatorial objective is not necessarily that task. |
AIO:ReinforcementLearning
|
Memory, adaptive penalties or an acceptance criterion do not themselves define a policy/environment learning problem. Exploration terminology is insufficient for a forced mapping. |
AIO:ReinforcementLearningLLM
|
The method is not a language model fine-tuned through reward feedback. |
AIO:EvolutionaryLLM
|
The target is a large language model. Its related evolutionary-algorithms synonym does not identify all optimizers or convert a single-trajectory method into a model. |
AIO:MarkovChain
|
Some memoryless configurations admit a Markov description, while others use search history. That mathematical representation alone does not identify the optimization framework with the pinned network/model class or its semantic parent. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Helena R. Lourenço, Olivier C. Martin, Thomas Stützle
|
primary paper
full_text
|
ID: arXiv:math/0102188v1
sha256:6e60a8114c7d…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T14:13:40Z
Updated: 2026-10-11T14:13:40Z
Source File:
data/curated/IteratedLocalSearch.yaml