이전까지는 탐색공간을 체계적으로 탐색했다. 따라서 문제의 solution까지 도달하는 경로까지도 구할 수 있었다.
하지만 경로가 필요없는 문제도 존재한다. 이럴 때는 다른 알고리즘을 사용할 수 있는데 여기선 Local Search의 Hill-climbing 방식을 알아보도록 하겠다.
Local Search and Optimization
Local Search는 다음과 같은 특성을 가진다.
- 다른 state를 기억하지 않고 오직 현재 state만 알고있다. 따라서 stack, queue와 같은 다른 자료구조를 사용하지 않는다.
- 그리고 위와 같은 특성때문에 Memoryless Search라고 불린다.
- 인접 state로만 움직인다.
- 경로를 무시한다.
Local Search의 장점
- 메모리 사용량이 적다.
- 탐색공간이 무한하거나 매우클때에도 합리적으로 goal state를 찾을 수 있다.
Local Search는 다음 속성을 가지는 optimization 문제에 사용된다.
- 모든 state들은 heuristic or objective 함수를 가진다.
- Goal은 최대가 되는 objective value를 찾아가는것이다. (objective value는 objective function에서 도출되는 값)
- goal과 경로를 함께 찾아가는 문제에는 적합하지않다.
- 위와 같은 문제에 적합하다.
Hill climbing Search
Hill climbing Search의 특성
- value의 값이 증가하는 방향으로 움진인다.
- peak에 도달했을 때 종료한다.
- 현재 상태에서 좀 더 좋은쪽으로 움직이기 때문에 hill climbing search를 greedy local best search의 한 종류라고 한다.
value값은 objective function이나 heuristic funtion의 값이다.
만약 best value가 여러개 있다면 그중 임의로 선택해 탐색할 수 있다.
Local Maxima
local maxima에 존재하면 hill climbing은 suboptimal을 만족한것이다. 따라서 hill climbing은 global optimal을 보장하지 않는다.
따라서 global optimal을 보장하기 위해 임의로 시작지점을 정해 restart하여 global optimal을 찾는다. 하지만 100% 보장할수는 없다.
Hill climbing의 예제
8 queens problem을 이용해 hill climbing 방법으로 탐색해 볼것이다.
Successor function : 같은 column 내에서 다른 위치로 옮기는 것
heuristic function h(n)은 각 queen들이 잡아 먹을 수 있는 pair의 수라고 하자.
이 상태일때 h = 17이다. 따라서 successor function을 이용해 각 column마다 queen을 움직여 h가 작아지는 방향으로 이동시킨다.
Performance of hill climbing
임의로 8 queen을 생성해 시작한다고 했을 때 14%만 문제를 해결할 수 있고 86%는 local minimum에 도달해 global minimum을 찾지 못한다.
임의로 8queen을 놓고 시작하고 이게 성공으로 움직일때는 평균적으로 4번만 queen을 움직이면 된다.
또한 평균적으로 3번만에 global minimum으로 도달하지 않는다는것이 나온다.
Hill climbing with random restarts
그렇다면 얼마나 restart한다면 global minimum으로 도달 할 수 있을까?
N번 restart하고 global minimum을 찾을 때까지 반복한다.
성공할 확률 p = 0.14이고 정답률이 99%가 되기위해 몇번의 restart를 진행해야하나? 라는 물음에 대한 식은 다음과같다.
= ( 0.86 )^n < 0.01
n =30.53...
최소 31번을수행하면 99% 답이 도출된다.
평균적으로 4번만에 성공한다고 했기 때문에 최대 4 * 31 = 124 step만 움직여 보면 성공인지 실패인지 알 수 있다. (여기서 실패했을 때의 3 step 보다 더 큰 4를 곱해준 이유는 최대 step을 구하려고 했기 때문이다)