Hill Climbing (Local Search)

Simple Greedy Local Search Algorithm

← Back to Optimizer Competition
Hill Climbing in HumpDay is a (1+1)-Evolution Strategy with a deterministic σ decay schedule. Each iteration proposes one Gaussian-perturbed offspring; the offspring is accepted if it improves the objective. There is no 1/5-success rule (that's the Rechenberg variant) — σ decays geometrically from σinit = 0.1 to σfinal = 1e−3 over the budget. This matches the textbook "hill climbing with shrinking perturbations" intuition and what tests/test_reference_alignment.py compares against.

HumpDay's HillClimbing at a glance

  • Initial σ: 0.1.
  • Decay: geometric, computed so that σ ends at 1e-3 after n_trials − 1 iterations.
  • Acceptance: greedy (1+1) selection — accept only if fnew < f.
  • Proposal: componentwise Gaussian, xnew = clip(x + σ·z) with z ∼ N(0, I).

Interactive 3D Visualization

See Hill Climbing in action on 3D optimization surfaces:

Loading 3D visualization...

Requires WebGL support

Instructions: Choose a test function and algorithm, then click Start to watch the step-by-step optimization process.

Auto-selection metadata. Consulted by humpday.minimize() when picking a default algorithm.
  • Overhead tier 1: light (~100µs/iter). Eligible when measured eval_time ≥ 10 µs.
  • Dimensional cap: no cap — linear-in-dim or better.
  • Minimum trials: 10 — baseline minimum.

Implementation Details

Component Details Links
Algorithm Concept Classic Local Search
Greedy improvement of current solution
Move to best neighbor until local optimum reached
Concept: Ancient (1950s AI research) 		Wikipedia
Reference Implementation Custom Implementation
No standard package (simple to implement)
Various neighborhood definitions and strategies
Self-reference: Algorithm-specific implementation 		AI Textbook
HumpDay Python HumpDay HillClimbing
(1+1)-ES with geometric σ decay from 0.1 to 1e−3 over the budget. Greedy acceptance, componentwise Gaussian proposals.
Pure Python; no required dependencies.
File: humpday/optimizers/evolutionary_algorithms.py 		Source
HumpDay JavaScript Browser HillClimbing
Mirrors the Python port.
Class: HillClimbing 		JS Implementation

Performance Characteristics

  • Best for: Smooth basins where the geometric σ schedule lines up with the budget. One evaluation per iteration makes it cheap.
  • Worst for: Multimodal landscapes — HillClimbing has no escape mechanism. Once trapped in a local basin, it refines into it.
  • Per iteration: one Gaussian proposal, one evaluation, one greedy comparison.
  • Relative to its inline (1+1)-ES σ-decay reference at n_trials=200, n_dim=2: HumpDay matches across sphere, Rosenbrock, and Ackley — algorithmically identical. See SOTA status for the live numbers.

Educational Resources

Algorithm Variants

  • Simple Hill Climbing: Move to first improving neighbor
  • Steepest-Ascent: Evaluate all neighbors, choose best improvement
  • Stochastic Hill Climbing: Choose improving neighbor randomly
  • Random-Restart: Multiple runs from different starting points
  • Sideways Move: Allow plateau moves to escape flat regions

Neighborhood Definitions

  • Continuous: Small perturbations in real-valued variables
  • Discrete: Bit-flips, swaps, insertions for combinatorial problems
  • Gaussian: Normal distribution around current point
  • Uniform: Uniform sampling within fixed radius
  • Adaptive: Step size changes based on success rate

️ Algorithm Pseudocode

function hillClimbing(problem, initialSolution):
    current = initialSolution
    currentValue = evaluate(current)

    repeat:
        neighbor = generateNeighbor(current)
        neighborValue = evaluate(neighbor)

        if neighborValue > currentValue:  // for maximization
            current = neighbor
            currentValue = neighborValue
        else:
            break  // local optimum reached

    return current

When Hill Climbing Works Well

  • Unimodal Problems: Single global optimum with no local optima
  • Local Refinement: Polishing solutions from other algorithms
  • Quick Improvement: When rapid initial progress is needed
  • Simple Problems: Well-behaved objective functions
  • Component in Hybrids: Local search phase in metaheuristics

Hill Climbing Limitations

  • Local Optima: Cannot escape local minima
  • Plateaus: Gets stuck on flat regions
  • Ridges: Difficulty with narrow valleys
  • Starting Point Sensitive: Final result depends on initialization
  • No Global View: Purely greedy approach

Improvements and Extensions

  • Random Restart: Run multiple times with different starts
  • Simulated Annealing: Allow occasional uphill moves
  • Tabu Search: Maintain memory to avoid cycles
  • Variable Neighborhood: Use different neighborhood structures
  • Iterated Local Search: Perturb and restart periodically

Applications

  • Traveling Salesman: 2-opt, 3-opt local search moves
  • Scheduling: Local improvements to task assignments
  • Neural Networks: Fine-tuning network weights
  • Game Playing: Position evaluation and move refinement
  • Parameter Tuning: Local optimization of system parameters
  • Image Processing: Local enhancement operations