Local search algorithm

hill climbing and simulated annealing algorithm.

1. ARTIFICIAL INTELLIGENCE LOCAL search ALGORITHMS 13 OMega TechEd Hill-climbing search Simulated Annealing

2. Local Search Algorithms OMega TechEd Subscribe

3. Hill climbing algorithm is a local search algorithm which continuously moves in the direction of increasing elevation/value to find the peak of the mountain or best solution to the problem. It terminates when it reaches a peak value where no neighbor has a higher value. Hill climbing is sometimes called greedy local search because it grabs a good neighbor state- without thinking ahead about where to go next. Subscribe Hill-climbing search OMega TechEd

4. Limitations: Hill climbing cannot reach the optimal/best state(global maximum) if it enters any of the following regions : OMega TechEd Subscribe

5. OMega TechEd Subscribe A Ridges is shown in figure result in a sequence of local maxima that is very difficult for greedy algorithm to navigate.

6. Variations of Hill Climbing In Steepest Ascent hill climbing all successors are compared and the closest to the solution is chosen. Steepest ascent hill climbing  is like best-first search, which tries all possible extensions  of the  current path instead of only one. It gives optimal solution but time consuming. Also known as Gradient search. OMega TechEd Subscribe Current node Successor node Jump Local Maxima Global Maxima

7. Simulated Annealing Annealing  is the process used to temper or harden metals and glass by heating them to a high temperature and then gradually cooling them, thus allowing the material to reach a low energy crystalline state. The simulated annealing algorithm is quite similar to hill-climbing. Instead of picking the best move, however, it picks a random move. If the move improves the situation , it is always accepted. Otherwise the algorithm accepts the move with some probability less than 1. Checks all the neighbors. Moves to worst state may be accepted. Subscribe OMega TechEd

8. Thanks For Watching Next Topic: Genetic algorithms Reference: Artificial Intelligence A Modern Approach Third Edition Peter Norvig and Stuart J. Russell Subscribe Like Share OMega TechEd

9. OMega TechEd About the Channel This channel helps you to prepare for BSc IT and BSc computer science subjects. In this channel we will learn Business Intelligence ,Artificial Intelligence, Digital Electronics, Internet OF Things Python programming , Data-Structure etc. Which is useful for upcoming university exams. Gmail: [email protected] Social Media Handles: omega.teched megha_with Subscribe