인공지능개론 | Informed Search

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

Informed Search | 정보가 있는 검색 전략 - Local Search

들어가기 앞서서 아래 8 Queens 문제에 관해 간략하게 소개한다.

이러한 문제들은 여러 가지 알고리즘으로 푸는 것이 가능하나, 이와 같이 경로가 필요없는, 오로지 문제 해결만 초점으로 둔 문제에 Local Search가 사용이 된다.
일단 필자가 이 부분에 관해서 외부 라이브러리 없이 코딩하는 과제가 있었는데, 코드에 관한 설명은 모든 단원이 끝나고 부록으로 첨부한다! (추후 링크 첨부 예정)

Hill Climbing | 언덕 오르기 검색

이번 시간에 소개할 국소 탐색 중 한 가지인 언덕 오르기 검색에 대해 소개하고 8-puzzle에 어떻게 적용이 되는지 소개하고 마친다.
언덕 오르기 알고리즘은 이전 알고리즘과 달리 이웃 상태 중 현재 상태에서 최선의 이득을 취할 수 있는 방향으로 나가기 때문에 체계적이지가 않는 편이다. (어찌보면 탐욕법과 동일해보인다.) 모든 알고리즘의 각각 장단점이 존재하듯, 언덕 오르기 검색의 장단점은 아래와 같다.

장점
- Fringe와 같은 방문 여부에 관한 정보를 담는 자료구조가 불필요하여 메모리를 적게 소비한다. 이를 memoryless search라고도 한다.
- 당장의 이득만 보기 때문에, 경로를 무시하고 가장 좋은 상태를 찾는 최적화 문제에 유용하다.
단점
- 경로를 무시하기 때문에 최소 경로 찾기 문제에는 부적합하다. (뒤에서 나오지만 optimal하지 않는 방법이기도 하다.)
- 책에서 서술되었듯, 전체적인 정보가 없기 때문에, 짙은 안개 속에서 산을 오르는 것과 동일하다고 한다. 이쯤되면 정보없이 무지성하게 값을 찾아가는게 아닌가 싶지만, 엄연히 informed search에 속하기 때문에 후에 서술되는 h-value 정보에 의해 action을 취한다.

위 그래프를 보면 HC 알고리즘의 전반적인 것을 이해하기 쉬울 것 같아 가져와 보았다.
HC 알고리즘의 순서는 아래와 같다.

random 한 위치에서 시작한다
현 상태(current state)에서 정상 도달에 유리한 방향으로 언덕을 오른다.
현 상태에서 최고점이라고 판단되면 종료한다.

여기서 짚어야할 점은 아까 단점에서 서술되었듯, 짙은 안개 속에서 산을 오르는 것과 같기 때문에 그래프에서 현 상태에서는 local maximum에 머무르게 되는 단점을 지니고 있다. 즉, global maximum과 같이 가장 좋은 해결책이 아니라는 것이다. 현 상태가 이와 같이 시작하였기 때문에 그나마 local maximum에 도달할 수 있었지만 아래와 같은 가정이라면 어떻게 되는 보자.

현 상태(current state)가 맨 오른쪽에 존재하게 된다면?: local maximum보다 낮은 flat local maximum에 도달하게 된다. 기본적으로 hill climbing은 이웃 정보를 토대로 나아가므로 더 이상 진척하기 불가능한 지점에서 무한으로 빙빙 돌 수 있다.

이처럼 무한으로 루프에 빠질 수 있기 때문에 최고점이 아니라고 판단되거나 몇 번 돌아봤을 때 진척이 불가능하다고 판단되면, 재시작을 하면 된다! 가장 무난한 방법이기도 하다.
물론 경사에 따라서 확률적으로 다음 state를 선택하거나 나대신 다른 후행자들을 먼저 보냄으로써 좋은 상태가 될때까지 등등 여러가지가 존재하나, 일단 내가 들은 강의에서는 무작위 재시작만 언급하여서 넘어가도록 한다. ([참고] 그 외 해결 방법은 인공지능 현대적접근 방식 p.151에 수록)

Solving 8-Queen with Hill Climbing

Analysis

만약 8-Queens 문제 성공률이 14%라고 가정하면 몇 번 재시작해야 성공(99%)이 나올까?
실패율을 아래와 같이 계산해보면 다음과 같다. $(0.86)^n < 0.01$ $n > log_{0.86}0.01$

대략 31번 중 상화좌우 4번 state space 탐색해야하므로 124번 안으로 문제가 해결이 가능하다는 것이다. 해당 문제 전체 state space가 17백만개인 것을 감안하면 상당히 빠르게 탐색하는 편.

Wrap up & Conclusion

이 부분은 직접 코딩 과제를 수행해봄으로써 이해가 잘 되었던 것 같다. 처음에는 체스보드에 적힌 수를 아무리 봐도 이해가 되지 않아서 책을 이 때 사서 꼼꼼하게 읽어보았던 것 같다.
시간상 코드 부분까지 뜯어서 포스팅을 못한 게 아쉽지만, 학기가 끝나면 코드 공개를 함으로써 간략하게 설명해보려고 한다.