Hill climbing

In <a href="/facts/Numerical_analysis/QT9cYa9z">numerical analysis</a>, hill climbing is a <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">mathematical optimization</a> technique which belongs to the family of <a href="/facts/Local_search_(optimization)/G1D2aHBz">local search</a>. 
It is an <a href="/facts/Iterative_algorithm/uKMAJhEh">iterative algorithm</a> that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an <a href="/facts/Incremental_heuristic_search/IGJCqRrl">incremental</a> change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.
For example, hill climbing can be applied to the <a href="/facts/Travelling_salesman_problem/2WEKVLnV">travelling salesman problem</a>. It is easy to find an initial solution that visits all the cities but will likely be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much shorter route is likely to be obtained.
Hill climbing finds optimal solutions for <a href="/facts/Convex_optimization/7D6U4MTN">convex</a> problems – for other problems it will find only <a href="/facts/Local_optimum/f40GlzAw">local optima</a> (solutions that cannot be improved upon by any neighboring configurations), which are not necessarily the best possible solution (the <a href="/facts/Global_optimum/ADlgnyzV">global optimum</a>) out of all possible solutions (the <a href="/facts/Candidate_solution/cJUKNCmM">search space</a>). 
Examples of algorithms that solve <a href="/facts/Convex_optimization/7D6U4MTN">convex problems</a> by hill-climbing include the <a href="/facts/Simplex_algorithm/9fndF6cq">simplex algorithm</a> for <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> and <a href="/facts/Binary_search/FFmQzunc">binary search</a>.: 253  
To attempt to avoid getting stuck in local optima, one could use restarts (i.e. repeated local search), or more complex schemes based on iterations (like <a href="/facts/Iterated_local_search/UlDpJQtc">iterated local search</a>), or on memory (like reactive search optimization and <a href="/facts/Tabu_search/olw8qTSl">tabu search</a>), or on memory-less stochastic modifications (like <a href="/facts/Simulated_annealing/JCmHqd3t">simulated annealing</a>).
The relative simplicity of the algorithm makes it a popular first choice amongst optimizing algorithms. It is used widely in <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a>, for reaching a goal state from a starting node. Different choices for next <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">nodes</a> and starting nodes are used in related algorithms. Although more advanced algorithms such as <a href="/facts/Simulated_annealing/JCmHqd3t">simulated annealing</a> or <a href="/facts/Tabu_search/olw8qTSl">tabu search</a> may give better results, in some situations hill climbing works just as well. Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real-time systems, so long as a small number of increments typically converges on a good solution (the optimal solution or a close approximation). At the other extreme, <a href="/facts/Bubble_sort/Go9JnLk2">bubble sort</a> can be viewed as a hill climbing algorithm (every adjacent element exchange decreases the number of disordered element pairs), yet this approach is far from efficient for even modest N, as the number of exchanges required grows quadratically. 
Hill climbing is an <a href="/facts/Anytime_algorithm/9yftLJng">anytime algorithm</a>: it can return a valid solution even if it's interrupted at any time before it ends.

Hill climbing open-in-new

Hill climbing