Does first-choice hill climbing always choose uniformly among improving moves?

No. It samples candidates until it finds an improvement. The resulting selection depends on the proposal distribution and sampling policy; it need not examine all improving moves.

Can it accept a worse move?

Not in the strict first-improvement version described here. Methods that sometimes accept worsening moves use an additional rule.

Why might it stop too early?

A limited proposal budget may miss an improvement, or the neighborhood may offer none even though better distant solutions exist.

AI Glossary / Graphs and symbolic AI / Intermediate

First-choice hill climbing

Definition

First-choice hill climbing is a local-search method that samples neighboring solutions and moves to the first one that improves the current objective. It avoids evaluating every neighbor before choosing a move. This can be useful when each solution has many possible modifications, but it does not guarantee a globally best result.

What it means

Hill climbing improves a current candidate through local changes. For maximization, an improvement means a higher score; for minimization, it means a lower cost. First-choice hill climbing finds an acceptable improvement without necessarily finding the largest available improvement.

The neighborhood definition is crucial. Swapping two assignments, changing one parameter or moving one object can create different neighborhoods and local optima. The first improving candidate depends on how neighbors are sampled. Random sampling is the usual first-choice formulation, and a reproducible experiment should record how that randomness is controlled.

How it works

Start with a candidate and evaluate it. Generate a neighbor, check required feasibility conditions and calculate its objective. If it improves on the current candidate, accept it immediately and search around the new solution. Otherwise, reject that proposal and sample another neighbor.

A practical implementation needs a stopping policy. It might exhaust a finite neighborhood without replacement, stop after a specified number of unsuccessful samples or use a total evaluation budget. These choices have different implications. Failing to find an improvement in a limited random sample does not prove that no improving neighbor exists.

The strict-improvement version rejects equal-valued moves. Allowing sideways moves, occasional worsening moves or random restarts changes the behavior and should be stated separately. The basic method can become trapped at a local optimum or fail to cross a plateau even when much better solutions exist elsewhere.

Three practical examples

1. A scheduling prototype samples permitted task swaps and accepts the first one that reduces its penalty score. It avoids comparing every possible swap at each step.

2. A layout experiment proposes small changes to object positions. It accepts an improvement only after checking that the proposed layout still satisfies required placement constraints.

3. A parameter-tuning exercise samples nearby settings and keeps the first one that improves its validation objective. Its evaluation design must avoid mistaking random score noise for dependable progress.

Think of it this way

Think of adjusting a chair until it feels more comfortable: try a small change, keep it if it helps, and continue from there. You do not test every possible adjustment before moving. The analogy explains first improvement, but an algorithm needs a precise score, neighborhood and stopping rule. Comfort can vary over time, whereas a deterministic objective gives the same score for the same candidate.

Worked example

Suppose a minimization problem starts at candidate S with cost 20. Its four possible neighbors have costs 22, 19, 15 and 21. A random sampling order happens to inspect the cost-22 neighbor first, then the cost-19 neighbor, followed by the others if needed.

First-choice hill climbing rejects 22 and accepts 19 immediately. It makes two neighbor evaluations for this move and does not inspect the cost-15 option at this stage. A best-improvement version examining all four neighbors would choose 15, at the cost of four evaluations.

Neither fact establishes which method will be better over the entire run: the new candidates can have different neighborhoods and lead toward different local optima. If the cost-19 candidate later has neighbors costing 20, 19 and 23, strict improvement accepts none. Exhaustively checking those three would establish a local minimum under that neighborhood, whereas checking only one random proposal would not. This hand example compares selection behavior, not a measured optimization benchmark.

Illustrative case study

Fictional case study: Ash Planning experiments with thousands of possible timetable swaps. Its first-choice method finds improvements without scoring the full neighborhood each time, but different random seeds produce different final schedules. The team records the best feasible result and the evaluation budget for each run.

Reviewers compare distributions across repeated trials rather than highlighting only the most favorable run. They inspect constraints separately from the soft penalty score. The case illustrates a fair evaluation approach, without claiming that first-choice search outperforms exhaustive neighborhood evaluation on every timetable.

Common misconceptions and mistakes

First-choice does not mean accepting the first generated neighbor regardless of quality. It means the first improving one. It is not best-improvement hill climbing, because a better neighbor may remain unexamined when a move is accepted.

An unsuccessful sampling budget is not a proof of local optimality. Even a genuine local optimum is not necessarily global. Equal-value proposals need an explicit policy, and noisy evaluations can make apparent improvements unreliable. Finally, feasibility should not be assumed merely because the objective improves: a lower penalty can hide a violated hard constraint if the scoring design allows it.

Business use

This method is attractive when candidate generation is cheap relative to evaluating every neighbor and useful solutions matter more than a proof of optimality. Define the allowed changes and evaluation budget so comparisons with alternatives are meaningful.

Report solution quality, constraint satisfaction, evaluation count and variability across runs. Keep a reproducible record of random seeds and objective versions. Consider whether restarts or a different neighborhood address observed local traps, documenting those additions as part of the actual method. A fast initial improvement is useful evidence, but it does not establish the quality of the final business decision.

Check your understanding

Why does the worked method choose cost 19 rather than cost 15?

Answer: The cost-19 neighbor is the first sampled candidate better than the current cost 20. Once accepted, the algorithm moves without completing the remaining comparisons.

Related terms

Hill climbing
Local search
Neighborhood
Objective function
Simulated annealing
local optimum
stochastic search
random restart
plateau

Learn next

Compare first-improvement and best-improvement traces on the same small landscape. Then change the neighborhood and stopping budget, distinguishing demonstrated local optimality from a search that merely ran out of trials.

Neighborhood

Sources

Primary teaching source: Carnegie Mellon, “Local Search,” first-choice hill-climbing discussion: https://www.cs.cmu.edu/~15281/coursenotes/localsearch/ . The cost trace and fictional scheduling case are original explanations. They illustrate the selection rule without claiming a general performance advantage.

Previous: Firmographics Next: First difference