Simple hill climbing, Steepest hill climbing (쉬운 언덕 등반과 가파른 언덕 등반)

- hill climbing 기법은 DFS(depth-first search)를 기초로 하여 heuristic을 적용한 탐색 기법으로 현재 상태와 자식 노드와의 거리(혹은 비용)에 따라 정렬(sort)한 후 각 단계(step)의 선택이 이전 단계의 상태보다 나은지를 평가함

- 작은언덕(foothilll) : 작은 언덕에서 시작할 경우 시간을 소모 할 수 있음

- 고원(plateaus) : 고원이 계속될 경우 비교대상을 찾지 못함

- 산등성이(ridge) : 산등성이인 경우 최적해로 알 수도 있음(local solution)

Fig. 1. (ref. Artificial Intelligence A Modern Approach Third Edition)

Fig. 2. (ref. http://www.cs.iusb.edu/~danav/teach/c463/6_local_search.html)

- 지역 최대치(local maxima; 극댓값) 문제 (작은 언덕; foothills) 

정상 주변에 정상 보다 낮은 봉우리들이 있을 때, 그 주변 봉우리에 오를 경우 그 곳이 정상인 것으로 판단 할 수 있다.

- 방안 : 백트랙킹을 통해 다른 가능한 경로를 탐색

- Steepest hill climbing이 제안됨

- 능선(ridge) 문제 

날카로운 능선 상에 위치해 있을 때 정해진 동, 서, 남, 북 어느 방향으로 이동하더라도 고도가 낮아져서 정상으로 오판하게 되는 문제이다.

이동 방향의 해상도와 관련된 문제이다.

지역 최대치가 연이어 있는 상황에 해당한다.

- 방안 : 검사 방향을 늘리거나 연산자들을 조합하여 적용한 결과를 사용

- 고원(plateau; 대지; shoulder) 문제 

산 중턱에 존재하는 평평한 영역(모두 동일해서 판단 할 수 없음)에 도달했을 경우 어느 방향으로 이동해도 현재 상황을 개선할 수 없다.

- 방안 : 동일 연산자를 반복 적용한 결과를 토대로 진행 방향을 결정

- 비교를 하자면, 

- 지역 최대치의 경우 주변 탐색 범위를 살펴 보아도 현재 상태가 최대치인 것으로 확인되어 다른 곳을 더 찾을 수 없게 되는 것이고 (탐색 범위를 넓이면 해결 됨)

- 능선의 경우에는 현재 찾은 곳보다 바로 옆에 더 좋은 해가 있고, 그 옆에 또 바로 더 좋은 해가 있고, 이런 식으로 전역 최대치가 아닌 방향으로 계속 유도되는 것이고, (탐욕적 알고리즘(greedy algorithm)은 이것을 회피 할 수 없음)

- 고원은 주변 탐색 범위를 모두 살펴보아도 현재 지역 최대치와 같은 값을 얻어 내게 됨에 따라 현재 상황이 바뀔 수 없게 됨.

- simple hill climbing은 탐색 시 현재 노드를 자식 노드와 비교하여 목적 상태와 가장 가까운 노드를 선택할 때, 가장 먼저 찾은 노드를 선택함

- steepest hill climbing은 모든 자식 노드를 평가한 값을 비교해서 최선의 경로를 찾음

- last updated 2017-04-15