Stochastic爬山算法与Random-restart爬山算法有何差异？

Great question—these two heuristic search algorithms are often confused, but they tackle optimization problems in fundamentally different ways. Let’s break down their key distinctions:

1. Run Logic: Single Path vs. Multi-Path Restarts #

Stochastic Hill Climbing (SHC) #

Think of SHC as a single hiker climbing a mountain:

• Starts at a random initial point in the search space.
• At each step, it randomly selects a neighboring state (no picking the "steepest" climb here—just a random adjacent option).
• Moves to that neighbor only if it’s better than the current state (some variants allow occasional moves to worse states, but vanilla SHC sticks to improvements).
• Stops when it hits a local optimum (no neighbors are better than the current state)—even if this isn’t the global best.

It’s a one-and-done search: once it gets stuck, it’s done.

Random-restart Hill Climbing (RRHC) #

RRHC is like sending multiple hikers to climb the mountain from random starting points:

• It runs a basic hill-climbing algorithm (could be SHC, steepest-ascent, etc.) multiple times, each with a brand-new random initial state.
• After each run, it saves the best solution found from that restart.
• Once all restarts are complete, it returns the best solution across all runs.

The core idea is to outrun local optima by trying different starting points—odds are, at least one restart will land near a global optimum.

2. Key Behavioral & Performance Distinctions #

• Local Optima Handling:
  • SHC is highly prone to getting trapped in local optima. If your initial point is near a subpar peak, that’s all you’ll get.
  • RRHC drastically reduces this risk: more restarts mean higher chances of hitting a starting point near the global optimum.
• Computational Cost:
  • SHC is cheap and fast—it only runs one search pass.
  • RRHC’s cost scales with the number of restarts: more restarts = better results, but more time/CPU usage.
• Result Consistency:
  • SHC results are heavily dependent on the initial random seed. Run it twice with different starts, and you might get wildly different solutions.
  • RRHC results are far more consistent: averaging across multiple restarts smooths out the luck of the initial draw.
• Memory Overhead:
  • SHC only needs to track the current state and its neighbors—minimal memory usage.
  • RRHC needs to store the best solution from each restart, but this is usually negligible unless you’re running hundreds of restarts.

3. Ideal Use Cases #

When to Choose Stochastic Hill Climbing #

• You need a fast, "good enough" solution rather than the absolute global optimum.
• Computational resources are tight (e.g., real-time systems where latency matters).
• The search space is relatively smooth with few local optima—so getting stuck isn’t a big risk.

When to Choose Random-restart Hill Climbing #

• The problem has many local optima (e.g., combinatorial optimization like TSP, or function optimization with multiple peaks).
• You need the best possible solution and can afford the extra compute time.
• You have no prior knowledge of good starting points—random restarts let you explore the search space broadly.

内容的提问来源于stack exchange，提问作者Ola Galal