Hill Climbing

Hill climbing is an optimization technique that is used to find a "local optimum" solution to a computational problem. It starts off with a solution that is very poor compared to the optimal solution and then iteratively improves from there. It does this by generating "neighbor" solutions which are relatively a step better than the current solution, picks the best and then repeats the process until it arrives at the most optimal solution because it can no longer find any improvements.

Variants:

• Simple — The first closest node or solution to be found is chosen.
• Steepest ascent — All available successor solutions are considered and then the closest one is selected.
• Stochastic — A neighbor solution is selected at random, and it is then decided whether or not to move on to that solution based on the amount of improvement over the current node.

Hill climbing is done iteratively — it goes through an entire procedure and the final solution is stored. If a different iteration finds a better final solution, the stored solution or state is replaced. This is also called shotgun hill climbing, as it simply tries out different paths until it hits the best one, just like how a shotgun is inaccurate but may still hit its target because of the wide spread of projectiles. This works very well in many cases because at it turns out, it is better to spend CPU resources exploring different paths than carefully optimizing from an initial condition.