Guided local search
Algorithms AIMech:GuidedLocalSearch DRAFT
Aliases: GLS
A local-search metaheuristic that repeatedly minimizes an objective augmented by feature penalties, increasing selected penalties at local minima to alter subsequent search while retaining solutions according to the original objective.
Identity Notes & Concept Scope
GLS is the named feature-penalty procedure, not all tabu search, a hard prohibition of recently visited moves, or Fast Local Search (FLS), which is a separately combinable neighborhood-reduction technique. The authors relate GLS to the broader tabu-search framework; that relationship does not make every tabu algorithm and the specified GLS update identical. 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
Choose binary indicators I_i(s) for nontrivial solution features, feature costs c_i, a local-search procedure and penalty scale lambda. In the inspected basic formulation the c_i are fixed and nonnegative, and penalties p_i start at zero. Repeatedly run local search from the current solution using h(s)=g(s)+lambda*sum_i p_i*I_i(s), where g is the original cost. At an h-local minimum s_star, compute u_i=I_i(s_star)*c_i/(1+p_i). In the nondegenerate case of positive maximum utility, increment p_i by one for every feature tied at that maximum, then resume local search from the same solution under the modified h. Penalization can repeat without an intervening move. Feature costs enter the utility ranking, not as extra multipliers in the displayed penalty sum. Retain and return the best solution found according to g, rather than choosing it by the changing augmented objective. FLS and other accelerations may be combined with the local-search subroutine but are not required by this baseline.
⚠️ Curated Limitations & Negative Results
- The source allows zero feature costs. If every utility is zero, the all-feature pseudocode makes absent features tie with present ones, whereas the prose says only local-minimum features are penalized. A concrete implementation must declare its zero-utility and eligible-feature convention; the record’s stated update is restricted to the positive-maximum case.
- Curator qualification of Equation 1: equal penalties contribute lambda*p times the number of active features. They cancel from move-cost differences only when that feature count is unchanged. The source’s equal-penalty cancellation statement is therefore not universal for variable-cardinality feature sets.
- Penalties are finite soft costs, not hard prohibitions. Their effect depends on lambda, objective scale, feature definition, move set and stopping. At lambda=0 the guidance vanishes; increasing penalties does not prove escape from every basin or convergence to a global optimum.
- Local minima are relative to h and the chosen neighborhood, not necessarily g. A deterministic penalty update does not make an entire implementation deterministic if its initial solution or local-search routine is randomized. The manuscript’s TSP comparisons do not establish universal superiority, and no benchmark results are 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
|
Christos Voudouris, Edward Tsang
|
primary paper
full_text
|
ID: doi:10.1016/S0377-2217(98)00099-X
sha256:4550ebdad45d…
|
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/GuidedLocalSearch.yaml