AI — Hill Climbing to find Quadratic Equation’s minima

Are you wondering about Hill Climbing algorithm? We got you covered . It’s concept with state space diagram, implementation in python code and drawbacks are covered.

Hill Climbing (edited on photoshop)

Introduction

• Hill Climbing is a local search algorithm and not a classical search algorithm like bfs, dfs, A* search etc.
• Local search algorithms should be used when the final goal is to find the best solution state and not the cost to reach there.
• Local search algorithms use small amount of memory and can often find reasonable solution in very large state space, where classical symmetric algorithms are not feasible to use.

Hill Climbing

Pseudocode for Hill Climbing Algorithm ( made on carbon)

• It is basically a loop where it compares present state values with neighboring state values , if the neighboring state value is higher than the present state it moves to new state without thinking about where to go next.

Disadvantages It gets stuck at-

• local maxima as there is no point greater than local maxima in it’s vicinity as neighbors are lesser than present . Solution: Use backtracking to maintain a list of visited state
• ridges as it is a sequence of indirectly connected local maxima. Solution: Apply evaluation rules like travelling in all possible directions at a time
• plateau or shoulder as equal neighbors in the vicinity. Solution: Make a big jump far away from current state away from present state to land in non plateau region.

Fig 1: 2D State space diagram (drawn on diagram software)

Implementation: To find the minimum value of a quadratic equation within a range . Quadratic function has only one global minima.

Hill Climbing Algorithm to get minimum value of a quadratic equation. ( made on carbon)

expected output=“ f([0.2499508]) = 0.875000”.

The number inside f can vary but should be close to 0.25 as minimum value of this quadratic will be at 0.25 (-b/2a from ax2+bx+c)

Understanding the above code

• First define objective function, here we return the value of equation as we need this value for comparison in successive steps.
• In the hill climbing algorithm, we first generate a random number within a range as possible solution (‘solution’ variable), then we evaluate the equation for that number by calling objective function and store in ‘solution_eval’ variable.
• The ‘n_iterations’ tells us how long should the hill algorithm try to reach the minima, if ‘n_iterations’ is low then the algorithm may terminate before reaching the minima but if it is too high then the algorithm will take long time to evaluate.
• Within each iteration, we generate a new number ,which differs from the old random number by maximum difference of a number defined by “step_size” .
• We evaluate the equation for this new number, if the result obtained is lesser than that for previous number ( since we are finding minima) we store the result and proceed for next iteration.
• Iterations continue till the new result is lesser than the previous result else they will terminate.
• Conclusion: Quadratic equation has only one minima , so hill climbing algorithm works well but a polynomial of degree n , where n>2, can have multiple minima , in that, case you may not always reach global minima.

In my next blog, I’ll cover simulated annealing technique and then genetic algorithm ,which will overcome some of the disadvantages of hill climbing algorithm.

Tell us in the comment on what topics would you like to see articles.

End of blog…