Hill-Climbing Algorithm

Context:
- It can range from being a Local Hill-Climbing Algorithm to being a Stochastic Hill-Climbing Algorithm.
- …
Counter-Example(s):
- an Exhaustive Search Algorithm.
See: Gradient Descent Algorithm, Approximate Optimization Algorithm.

References

http://en.wikipedia.org/wiki/Hill_climbing
- In computer science, hill climbing is an mathematical optimization technique which belongs to the family of local search. It is relatively simple to implement, making it a popular first choice. Although more advanced algorithms, e.g., Simulated annealing or tabu search, may give better results, in some situations hill climbing works just as well.
  Hill climbing can be used to solve problems that have many solutions, some of which are better than others. It starts with a random (potentially poor) solution, and iteratively makes small changes to the solution, each time improving it a little. When the algorithm cannot see any improvement anymore, it terminates. Ideally, at that point the current solution is close to optimal, but it is not guaranteed that hill climbing will ever come close to the optimal solution.
  For example, hill climbing can be applied to the traveling salesman problem. It is easy to find a solution that visits all the cities but will 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 better route is obtained.
  Hill climbing is used widely in artificial intelligence, for reaching a goal state from a starting node. Choice of next node and starting node can be varied to give a list of related algorithms.