Local search and optimization
이전까지의 search : 탐색공간의 체계적인 탐색
Local search : 한개 또는 그 이상의 현재상태를 평가하고 수정함 고려해야 할 건 cost가 아니라 solution state이다
local search는 최적화 문제를 풀기에 적합하다
state space는 완전한 구성의 집합
e.g. 8개의 퀸이 전부 올려진 체스판
objective function h(s)에 따라 best state를 찾는다
e.g. h(s) = number of conflicts
많은 최적화 문제는 standard search model에 적합하지 않다
local search = 현재상태를 킵하고 퀄리티를 높이는 쪽으로 갈 수 있는 이웃 상태를 찾아본다
장점
적은 메모리 사용량
엄청나게 크거나 무한대인 state spaces 안에서 합리적인 solution을 찾기 좋다
↔ systematic algorithm
Hill-climbing search
값을 증가시키는 쪽으로 연속적으로 움직이는 루프
동률이면 아무거나 고름
더 높은 값의 이웃이 없는 peak에 도달했을 때 끝남
(기억력은 떨어지는데) 안개 자욱한 에베레스트를 올라가는 것과 비슷하다
a.k.a. greedy local search, steepest ascent/descent
Drawbacks
초기 상태에 따라 local maxima, plateaux(flat)에서 끝날 수 있다.
sideways move는 plateau가 진짜 shoulder라는 희망을 가지는 것을 허용한다 (?)
Hill-climbing variations
Stochastic HC
퀄리티가 좋아히는 move가 있으면 경사도에 비례하는 확률로 걔를 골라줘라 (tie-break X)