Does guided mean a human chooses each move?

No. The standard method uses an automated feature-penalty mechanism.

Are penalized features forbidden?

No. They become less attractive in the augmented objective but can still appear in solutions.

Which score determines the final best solution?

The original objective g, not the changing augmented score h.

AI Glossary / Mathematics and optimization / Intermediate

Guided local search

Definition

Guided local search (GLS) is a metaheuristic that helps a local-search algorithm escape local minima by adding adaptive penalties to selected solution features. The underlying search minimizes an augmented objective, while the best solution is still judged by the original objective. Its guidance comes from feature costs and accumulated penalties, not necessarily from a trained machine-learning model.

What it means

Ordinary local search repeatedly takes improvements until its available neighborhood offers none. That point can be a local minimum rather than the globally best solution. GLS changes the landscape seen by the search, making some features of the current local minimum less attractive.
A feature is a recognizable part or property of a solution. For a route, a feature might be the presence of a particular edge. A penalty records how often that feature has been selected for discouragement. The penalty is search memory, not automatically a real-world monetary cost or a violation of a mandatory constraint.

How it works

Let g(s) be the original cost, I_i(s) indicate whether feature i appears, p_i its accumulated penalty, and lambda a positive penalty strength. A standard augmented objective is h(s)=g(s)+lambda times the sum of p_i I_i(s).
At an augmented local minimum, compute feature utility I_i(s)c_i/(1+p_i), where c_i is a nonnegative feature cost. Increment penalties for present features with maximum utility and restart local search from the current solution. Keep the best encountered solution under g. The denominator reduces the repeated priority of an already heavily penalized feature.

Three practical examples

A routing experiment can penalize selected expensive edges that persist in locally optimal tours, encouraging alternatives.
A scheduling prototype can define costly recurring assignment features and test whether adaptive penalties improve exploration.
An optimization study can combine the same GLS mechanism with different neighborhood searches to compare quality and computational effort.

Think of it this way

Think of temporarily adding warning stickers to choices that repeatedly keep a plan stuck. The stickers influence which plan the search explores next, but the final plan is still evaluated using the original business objective. The analogy is limited because GLS uses a precise numerical penalty rule; a sticker is not evidence that a feature is always bad or should be permanently forbidden.

Worked example

Consider an original miniature minimization problem with solutions A, B, and C arranged in a line: A neighbors B, B neighbors both A and C, and C neighbors B. Their original costs are g(A)=10, g(B)=12, and g(C)=8. Starting at A, an improvement-only local search stops because its only neighbor B costs more. A is a local minimum under this neighborhood, even though C is better.
Define two features. A contains feature f1 with feature cost c1=10, B contains f2 with c2=12, and C contains neither. These feature costs are stipulated guidance values; the example does not require them to decompose every solution's original cost. Initially p1=p2=0, and choose lambda=3. The augmented costs initially equal the original costs.
At local minimum A, f1 is the only present feature, so its utility is 10/(1+0)=10. Increment p1 to one. Now h(A)=10+3=13, while h(B)=12 and h(C)=8. Local search can move from A to B because 12 is lower than 13, even though B is worse under the original objective. From B it can move to C because 8 is lower than 12. The best original cost improves from 10 to 8.
This trace explains the purpose of modifying h: the temporary penalty removes A's local-minimum status in the augmented landscape. It does not redefine B as a better real-world solution than A. If the search stopped immediately after reaching B, the saved best original solution would still be A.
The penalty-strength choice matters. With lambda=1, a single penalty gives h(A)=11, so moving to B at 12 is still unattractive. If the algorithm revisits the same local minimum and penalizes f1 repeatedly, three accumulated penalties give h(A)=13 and allow the move under a strict-improvement rule. At two penalties h(A)=12 ties B, so tie handling matters.

Illustrative case study

Fictional case: a delivery planner repeatedly finds routes that contain one expensive connecting edge. A team adds GLS with route edges as features and tests several penalty strengths.
It stores the best route by actual distance separately from the augmented search score. Reviewers compare feasible routes across repeated runs and inspect whether the neighborhood offers realistic alternatives. The team does not remove an edge permanently merely because it receives penalties; penalties are a device for exploration, not a new operational prohibition.

Common misconceptions and mistakes

Do not report the augmented objective as though it were the original business cost. Its penalties change over time, so values from different penalty states are not directly comparable as objective quality.
Do not assume every feature should be penalized equally or that a large original cost always deserves another penalty immediately. The utility rule includes existing penalties and presence in the current solution. GLS also does not repair a poor neighborhood automatically: if useful alternatives cannot be reached through allowed moves, changing scores alone may not solve the problem.

Business use

GLS is useful when a local-search implementation already exists and persistent local minima limit solution quality. Its success depends on meaningful features, efficient move evaluation, and a penalty scale appropriate to the original objective.
Compare against the underlying local search using equal effort and representative instances. Preserve feasibility requirements and report the best original objective, runtime, and variation across runs. Document feature definitions and tie rules. Avoid treating published success on one problem family as evidence that the same feature design or penalty strength will work unchanged on another.

Check your understanding

Why can GLS move from A with original cost 10 to B with original cost 12?

Answer: After penalizing A's feature, its augmented cost becomes 13. Moving to B improves the temporary search objective and can open a path to C, whose original cost is 8.

Related terms

Local search
Neighborhood
Metaheuristic
Local minimum
Augmented objective
Feature penalty
Diversification
Traveling salesman problem
Incumbent

Learn next

Repeat the three-solution example with lambda=2 and strict-improvement moves. Determine how many penalties on f1 are needed before A can move to B. Then explain why saving only the current solution would be insufficient if the search stops while visiting B.

Sources

Primary research source: Voudouris and Tsang, Guided Local Search and its application to the Travelling Salesman Problem, sections 3.2–3.3: https://bracil.net/CSP/papers/VouTsa-GlsTsP-Ejor99.pdf . The three-solution landscape and penalty calculations are original illustrations of the published objective and utility rule.

Previous: Guided filter Next: Guttman scale