인공지능개론 | Informed Search - Local 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 알고리즘의 순서는 아래와 같다.

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

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

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

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

Solving 8-Queen with Hill Climbing

이제 실질적인 문제를 해결해보자. 책에서는 아래와 같은 그림이 첨부되어 있는데, 이 숫자들이 의미하는 바가 뭔지 정확히 알아보자.

일단 먼저 우리의 목표는 여왕이 겹치지 않으면서 모두 배치하는 것이 목적이므로 informed search 답게 정보인 h-value를 반환하는 heuristic function을 서로 간 공격하는 Queen pair의 갯수로 정의한다. 이 때 모두 공격하지 않아야 문제가 해결이 되므로 h-value가 0이면 알고리즘이 종료가 된다.
따라서 위 체스보드에 적혀있는 숫자는 곧 현 상태에서 해당 열에 해당되는 체스 말을 해당 위치에 올려놓을 경우의 h-value 인 것이다. 예를 들어 가장 좌측 상단(1행 1열))에 18이라고 표현되어 있는 부분에 5행 1열이 있는 체스말이 18위치에 배치했을 경우의 Queen pair의 갯수가 18번 겹치게 된다는 의미이다. (물론 행으로 해도 되고, 열로 해결해도 되고 상관없다.)
이 모든 경우의 수를 체스보드에 갱신을 하고 이미지 상에서 가장 좋은 수인 12 위치로 임의의 말을 선택에서 옮기고 이런 식으로 계속해서 전체 h-value가 0인 방향으로 문제를 풀어나가면 된다.

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

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