Hill climbing is a local greedy search algorithm that repeatedly replaces a candidate solution with a better neighboring solution. For maximization it increases the objective; for minimization it decreases it. The process stops when no neighbor improves the current state. section 4.1 section 4.3.1
A basic minimization procedure is:
- Start with an initial state or route. section 4.3.1
- Generate neighboring states or successor routes. section 4.3.1
- Evaluate the neighbors with a cost or heuristic function and select the best one. section 4.3.1
- Move to that neighbor only when it improves the current solution; otherwise terminate. section 4.3.1
Hill climbing uses little memory and avoids examining an entire search tree, so it can be fast. It is non-exhaustive, however: local optima can prevent a global optimum, while plateaus can stop progress. Larger search spaces create more opportunities for these failures. section 4.3.1 section 4.4.1
Solving the 8-puzzle
Each puzzle state expands to neighboring states, and the algorithm chooses the state with the fewest misplaced tiles. The implementation checks solvability, records costs, plots search progress with Matplotlib, and visualizes the resulting solution. section 4.3.1
Routing between points of interest
A route begins randomly, then generates up to n child routes and selects the shortest. Increasing n from 20 to 100 requires more processing but produces better and more consistent results; one run reaches 806.892 m. section 4.4.1
Listing 4.7 U of T routing using the hill climbing algorithm
def Hill_Climbing(G, origin, destination, n=20):
time_start = process_time() #1
costs = [] #1
current = randomized_search(G, origin.osmid, destination.osmid) #2
costs.append(cost(G, current))
neighbours = list(islice(get_child(G, current), n)) #3
space_required = getsizeof(neighbours)
shortest = min(neighbours, key=lambda route: cost(G, route))
while cost(G, shortest) < cost(G, current):
current = shortest
neighbours = list(islice(get_child(G, current), n))
shortest = min(neighbours, key=lambda route: cost(G, route))
costs.append(cost(G, current))
route = current
time_end = process_time()
return Solution(route, time_end - time_start, space_required, costs)
Inspect the routing implementation to see randomized initialization, bounded neighbor generation, cost comparison, and the processing-time trade-off. section 4.4.1
