Local Search: of Hill Climbing With random Walk & Random Restart Part-5

[@spidermanhomecoming001]

SUMMARY OF THIS VIDEO: The problem with sideways move is it might get stuck in a loop. From A it might move to its neighbor B. Since A is also a neighbor of B. It might again move back to A. So this the main issue in sideways move. Since all neighbors have same obj fn value.....it might get stuck in a loop and not terminate at all. So how do we solve this issue? Thats why we limit the number of states in sideways moves. Another way to prevent looping is to have a list of states that was already visited and prevent the search from visiting those again. Here that list is called TABU SEARCH. Its a queue. Queue that contains the list of last 100 states that was visited. New state is added to the QUEUE. OLDEST STATE is dropped from the QUEUE. Never visit a state that's already in the TABU. Usually TABU LIST size is 100. But if the TABU LIST has a huge size.....it completely becomes non redundant. Kind of like systematic search. No repetitive actions. So once u reach local optimum. U can switch on the breadth first search button. Which searches for the next best state score in all directions. Then the moment u see a state with better score than the current local optimum, u switch off the BFS and switch on the hill climbing button. Keep doing this whenever u hit a local optimum. So that u end up at a GLOBAL OPTIMUM. This is called enforced hill climbing. The moment u discover a state that is better using BFS. U directly jump to that state and continue with ur HILL CLIMBING. So this is a combo of BFS + HILL CLIMBING. Step1---U reach a local optima top thru quickie hill climbing. Step2--- u stagnate at local optimum Step3--- u do a prolonged period of BFS. Till u find something better. Step4--- u jump to that state from thr current state. Then again u reach local optimum top thru HILL CLIMBING(QUICKIE). Its a middle ground between local search n systematic(UNINFORMED) search In systematic search, search space becomes so large and memory requirements will be very high. Whereas In LOCAL SEARCH, there is no memory requirment. So its a sweet spot inbetween. Not as much memory n time like a systematic search This algorithm was used in an Al planner called the FF planner. It comes up with a path as a solution, if given a start state and end state. So u ll be doing LOCAL SEARCH in the path space. Each state in the path space.......will be a full path from the start to the goal But once upon a time there was a lot of local optimas in this path space......thats when researchers came up with ENFORCED HILL CLIMBING. And thats how FF planner became more fast n memory efficient in finding global optimum All this is fine. But what happens once GLOBAL OPTIMUM is reached. Algorithm isn’t even aware that its global optima.......it treats that point just like any other LOCAL OPTIMA.....it switched on BFS. But wont it waste a lot of time and memory doing BFS, since there isnt actually a better solution? Yes it will. But there should be a time limit set. Within 2 mins come up with the best solution. So it is in such time frames ENFORCED LOCAL SEARCH SHINES. (local search + tricks) Earlier we saw asymptotically complete algos like random walk and random sampling. Given enough time n memory both will surely come up with some solution. But Greedy local search is asymptotically incomplete. There is a high chance that it might get stuck in a loop. And u may never endup getting a solution. So we need to come up with some algorithm that combines the benefits of being asymptotically complete + the speediness of greedy local search. And these are called STOCHASTIC HILL CLIMBING ALGORITHMS. The goal is to avoid getting stuck in local optimum. So whenvr u r stuck in a local optimum randomly sample a new neighbor So this is like a hybrid of: GREEDY LOCAL SEARCH + RANDOM WALK Or u can use another hybrid: GREEDY LOCAL SEARCH + RANDOM SAMPLING (not choosing from neighbor but from a completely different sample). Compared to all other algos u learned till now. Hill climbing with random restarts is the best. 1. Do hill climbing. 2. If u get stuck at local optima. Randomly sample a new state. Then again do hill climbing. 3. Always remember the best state so far

[@sidflank301]

really appreciating work done👍

[@arunjithr5984]

Can anyone say why n queens problem can be solved in 6×3=18+4=22 steps......17:40 video time

[@ukanivedant1793]

As mentioned in the previous video at 6:30, the number of steps in a successful iteration is s = 4 the number of steps in a failed iteration is f = 3. By the formula, we can calculate the expected number of steps in a random restart: s + ((1/p)-1)*f Where, s=4, f=3, p=0.14 Hope it helps 👍

[@arunjithr5984]

​@@ukanivedant1793 thanks for your reply but how this formula holds true ....(1/p)=(1/0.14)=7.14 , why are we subtracting 1 from this ?

[@spidermanhomecoming001]

Hi arun. I have posted a comment on this video. Hope it clears ur doubt.

[@gowthamgangaraju2881]

@@arunjithr5984 in 7 restarts 1 restart is going to take us to the solution. It takes 3 steps for failure and 4 for success. So in 7, 6 are failure and one is successful. So 6*3 + 4

[@AmeyaUppinaBCE]

Bro teaches better than the faculty I paid for 🥲