Heuristics and metaheuristics are optimization techniques that aim to find good solutions to complex problems in a reasonable amount of time. While heuristics are typically simple, problem-specific algorithms that are designed to quickly find good solutions, metaheuristics are more general-purpose optimization algorithms that are designed to explore the search space more thoroughly in order to find better solutions. In this chapter, we will discuss some of the commonly used heuristics and metaheuristics and how they can be implemented in Python.
7.1 Hill Climbing
Hill climbing is a simple heuristic algorithm that starts with an initial solution and then makes incremental changes to it in order to improve its objective function value. At each step, the algorithm moves to a neighboring solution that has a higher objective function value, and continues until it reaches a local maximum. Hill climbing is easy to implement and can be used to quickly find good solutions to simple problems. Here is an example implementation of hill climbing in Python:
def hill_climbing(initial_solution, neighbor_function, objective_function):
current_solution = initial_solution
current_score = objective_function(current_solution)
while True:
neighbors = neighbor_function(current_solution)
best_neighbor = max(neighbors, key=objective_function)
if objective_function(best_neighbor) <= current_score:
return current_solution
current_solution = best_neighbor
current_score = objective_function(current_solution)
In this implementation, initial_solution is the starting solution, neighbor_function is a function that generates neighboring solutions, and objective_function is a function that evaluates the quality of a solution. The hill_climbing function repeatedly generates neighboring solutions and selects the one with the highest objective function value until it reaches a local maximum.
To a 5 year old: Hill climbing is like trying to climb a big hill to get to the top. You start at the bottom and try to take steps that will get you higher up the hill. You keep going until you can't find any more steps that will take you higher, and then you stop. That's when you've reached the top of the hill! Hill climbing helps you find the best solution to a problem, just like climbing to the top of the hill helps you see everything around you.
The hill climbing algorithm starts at an initial point $x_0$ and repeatedly finds the best neighboring point $x'$ according to the objective function $f(x)$. If $f(x') \geq f(x)$, the algorithm terminates and returns the current point $x$ as the local maximum. Otherwise, the algorithm moves to $x'$ and repeats the process until a stopping criterion is met.
$$
\min f(x, y)
$$
$$
g_i(x, y) \leq 0 \quad \text{for } i = 1, 2, \ldots, m
$$
$$
h_j(x, y) = 0 \quad \text{for } j = 1, 2, \ldots, n
$$