Informed Search: Brief Study of Hill Climbing
Local Search and Types of Hill Climbing Search in AI
Abstract
The problem requires a solution or the goal from its initial state. Informed Search(Heuristic Search) is a type of searching technique that uses additional information(heuristics) to explore, make decisions, and reach the goal. This article aims to study, understand, and highlight the Hill Climbing Search Algorithms. Exploring unknown search space is challenging which can be mitigated by Hill Climbing Algorithm. The variants of the hill climbing algorithm can help to navigate agents or find the optimal path using a greedy or stochastic approach. Although there are always continuous(infinite) and unpredictable environments to reach the goal.
1. Introduction
Inspired by Simulated Annealing(physics) and genetic algorithms (biology), local Search Algorithms focus on exploring and manipulating only a few local states rather than the whole state space. What happens when the parameters in a controlled, free, or observed environment are not tied or restricted? Moving away from traditional searching like DFS, BFS, and DLS we have Hill Climbing Search which shares similar concepts to advanced optimization algorithms like Gradient Descent, SGD, Adam, and so on.
2. When to use Local Search?
When we do not care about the path we choose to reach the goal. Instead of exploring all the possible paths we start with a single node and move forward as the conditions are satisfied to reach the goal.
3. State-Space Landscape
State spaces (the set of all possible states). State can be defined as the situations of the environment or problem.
In the state-space landscape, locations are the state. Elevation is the value of the heuristic cost function (estimate cost of reaching a goal from a given state) or objective function.
3.1 Cases:
Elevation ≈ Cost: Find the Global Minimum (Lowest Valley)
Elevation ≈ Objective Function: Find the Global Maximum (Highest Peak)
If there is a goal then a complete local search algorithm will always find it.
The optimal Algorithm always finds a global solution. In our case, it is the highest peak or lowest valley.
4. Hill Climbing Search(Greedy Local Search)
This algorithm is like a while loop that moves or ascends uphill until it finds the highest peak among all of its neighbor peaks. It does not keep track of the previously visited states and only considers current immediate neighbors of the current state. It does not know what lies beyond the immediate neighbors.
5. Key Components in Local Search
5.1 Local Maxima and Local Minima
Among all the Local neighboring states, the highest peak can be considered as Local Maxima. It can be a value or the state itself. In contrast, the lowest valley among the neighboring states in a local scope can be considered a Local Minima(although it is irrelevant in hill climbing). These two points can be Stuck places for searching problems.
5.2 Ridges
Ridges are produced by a sequence of local maxima. These are areas in the search space where there is a narrow, elongated path that slopes upward (like a mountain ridge). As Shown in Figure It follows the gradient or “hill” upward, trying to reach the highest point (maximization problem) or lowest point (minimization problem).
5.3 Plateaux
A flat area in the search space where there are no changes or variations in the values of the neighboring states. It is one of the most dangerous places for hill climbing algorithms. Because there is no clear “upward” or “downward” direction to follow because the slope is effectively zero.
6. Possible Solutions for Plateaux
There are possible ways to mitigate the plateaux problem. Whenever algorithms get stuck in such area in the search state possible solutions are:
领英推荐
3. Simulated Annealing
7. Types of Hill Climbing
We’ll be discussing some of the types. They are:
7.1 Simple Hill Climbing
It is the simplest hill climbing that only evaluates the neighbor node state at a time and selects the first one, which optimizes the current cost and sets it as a current state. Affected by Plateau, Ridges, and Local Maxima.
7.2 Steepest-Ascent Hill Climbing
Variation of Simple Hill Climbing that evaluates all the possible neighbor nodes of the current state and selects the optimal ones (the steepest ones) making it computationally expensive.
7.3 Stochastic Hill Climbing
Selects an uphill move at random, with a probability that may depend on the steepness of the move. It’s slower than choosing the steepest path, but can find better solutions in tricky search spaces. It is slower because it picks from all possible uphill moves
7.4 First-Choice Hill Climbing
A variant of stochastic hill climbing that randomly generates successors until it finds one that is better than the current state. Randomly generates moves one at a time until it finds one that’s better than the current state. It is used when there are many possible moves (thousands), making it impractical to check them all.
7.5 Random-Restart Approach
“If at first you don’t succeed, try again.”[1] is the strategy of Random-Restart Appoarch. It starts from random initial states and performs hill climbing until it finds a solution. By restarting many times, it increases the chances of finding the global optimum. It may even find the goal state itself.
8. Simulated Annealing
Simulated Annealing is inspired by the process of annealing in metallurgy, where metals are heated and then cooled to become stable. The objective is to find the global minimum in an optimization problem. We can explain this by thinking like Imaging a ping-pong ball on a bumpy surface: if left alone, it will settle in the nearest dip (local minimum). Shaking the surface helps the ball escape local minima and potentially reach the global minimum. Initially, shaking is strong (high temperature), allowing exploration of different areas. Over time, the shaking reduces (temperature lowers), and the algorithm gradually focuses on finding the best solution.
This balance of exploration (shaking) and exploitation (settling into the best solution) helps avoid local minima and increases the chance of finding the optimal solution.
Basic Hill Climbing may get stuck in local maxima, and taking random walks may find the solution, but it is slower convergence. So, there is another method inspired by metallurgy called Simulated Annealing. Intuitively, to make an algorithm both fast and complete, a good approach is to combine hill climbing with random moves. This way, the algorithm can explore different areas and still make progress toward finding the solution.
9. Implementation of Discrete and Continuous Hill
import numpy as np
from typing import Callable, List, Union, Tuple
class DiscreteHillClimbing:
def __init__(self, eval_func: Callable, get_neighbors: Callable):
"""
Initialize Discrete Space Hill Climbing algorithm
Args:
eval_func: Function that evaluates a node and returns a score
get_neighbors: Function that returns list of neighboring nodes for a given node
"""
self.eval_func = eval_func
self.get_neighbors = get_neighbors
def optimize(self, start_node) -> Tuple[any, float]:
"""
Execute hill climbing optimization
Args:
start_node: Initial node to start optimization from
Returns:
Tuple of (best node found, score of best node)
"""
current_node = start_node
current_eval = self.eval_func(current_node)
while True:
# Get all neighbors
neighbors = self.get_neighbors(current_node)
# Find the best neighbor
next_eval = float('-inf')
next_node = None
for neighbor in neighbors:
neighbor_eval = self.eval_func(neighbor)
if neighbor_eval > next_eval:
next_node = neighbor
next_eval = neighbor_eval
# If no better neighbor exists, return current node
if next_eval <= current_eval:
return current_node, current_eval
current_node = next_node
current_eval = next_eval
class ContinuousHillClimbing:
def __init__(self,
eval_func: Callable,
acceleration: float = 1.2,
epsilon: float = 1e-8):
"""
Initialize Continuous Space Hill Climbing algorithm
Args:
eval_func: Function that evaluates a point and returns a score
acceleration: Acceleration factor for step sizes (typically 1.2)
epsilon: Convergence threshold
"""
self.eval_func = eval_func
self.acceleration = acceleration
self.epsilon = epsilon
self.candidates = np.array([
-acceleration,
-1/acceleration,
1/acceleration,
acceleration
])
def optimize(self,
initial_point: np.ndarray,
initial_step_sizes: Union[np.ndarray, None] = None) -> Tuple[np.ndarray, float]:
"""
Execute hill climbing optimization
Args:
initial_point: Starting point for optimization
initial_step_sizes: Initial step sizes for each dimension (defaults to ones)
Returns:
Tuple of (best point found, score of best point)
"""
current_point = np.array(initial_point, dtype=float)
if initial_step_sizes is None:
step_sizes = np.ones_like(current_point)
else:
step_sizes = np.array(initial_step_sizes)
best_score = self.eval_func(current_point)
while True:
before_score = best_score
# Try improving each dimension
for i in range(len(current_point)):
before_point_i = current_point[i]
best_step = 0
# Try each candidate step
for candidate in self.candidates:
step = step_sizes[i] * candidate
current_point[i] = before_point_i + step
score = self.eval_func(current_point)
if score > best_score:
best_score = score
best_step = step
# Update point and step size based on results
if best_step == 0:
current_point[i] = before_point_i
step_sizes[i] /= self.acceleration
else:
current_point[i] = before_point_i + best_step
step_sizes[i] = best_step # Could multiply by acceleration here
# Check for convergence
if (best_score - before_score) < self.epsilon:
return current_point, best_score
# Example usage
if __name__ == "__main__":
# Example for Discrete Hill Climbing
def discrete_eval(x: int) -> float:
return -(x * x) # Simple quadratic function
def get_neighbors(x: int) -> List[int]:
return [x-1, x+1] # Simple integer neighbors
discrete_hc = DiscreteHillClimbing(discrete_eval, get_neighbors)
best_discrete, score = discrete_hc.optimize(start_node=10)
print(f"Discrete HC result: {best_discrete} with score {score}")
# Example for Continuous Hill Climbing
def continuous_eval(x: np.ndarray) -> float:
return -np.sum(x * x) # Simple quadratic function
continuous_hc = ContinuousHillClimbing(continuous_eval)
best_continuous, score = continuous_hc.optimize(
initial_point=np.array([10.0, 10.0])
)
print(f"Continuous HC result: {best_continuous} with score {score}")
Code snippet generated by ChatGPT, a large language model developed by OpenAI. For more information, please refer to https://openai.com/chatgpt.
10. Conclusion
The effectiveness of hill climbing largely depends on the structure of the state-space landscape. If there are few local maxima and plateaux, any variant or random-restart hill climbing can quickly find a good solution.
However, in NP-hard problems, the landscape is often filled with numerous local maxima, making it easy to get stuck. Nevertheless, random-restart hill climbing can still discover a reasonably good solution after several restarts. Understanding the hill-climbing algorithm or search is very important in AI, Machine Learning, and Deep Learning. Because it shares a similar concept with the gradient descent algorithm which is the loss optimization algorithm. Also, Hill Climbing is directly related and applied to real-world problems. as well as scenarios.
References
Appendix