|
Ant Colony System
서상원 smiler82@naver.com
고전적인 TSP(Traveling Sales Person) 문제를 해결할 때 n개의 노드가 있다고 하면 (n-1)!의 공간복잡도가 필요하다. 즉, 노드를 도시라고 할 때, 10개의 도시를 모두 방문하고 출발지로 다시 돌아오는 최적의 경로를 구하려면 9!의 방문 경로가 존재한다는 의미이다. 노드가 100개, 1000개이면 아무리 슈퍼컴퓨터라 해도 수십 년의 시간이 소요된다. 이와 같은 종류의 문제를 일컬어 ‘최적화 문제’라고 한다. 실제로 이는 네트워크 라우팅, 네비게이션 알고리즘 등 다양한 분야에 활용되고 있다. 보통 이를 해결하기 위한 방법론으로 휴리스틱에 기반을 둔 알고리즘을 사용하는데, 휴리스틱이란 경험과 평가함수를 이용해 탐색의 범위를 축소, 빠르게 최적의 답을 찾는 인공지능적인 탐색 방법이다. Hill-Climb, BFS(Best First Search), A, A* 알고리즘 모두 휴리스틱에 기반을 두고 있다.
하지만 놀랍게도 MIT 연구진에 의해 곤충의 습성을 이용해 이러한 문제를 해결하려는 시도가 있어왔다. 그 곤충은 다름 아닌 개미다. 국내에도 경희대학교의 이승관 교수님을 비롯한 일부 학교에서 연구가 진행 중이다.
ACS(Ant Colony System)에서 개미는 하나의 에이전트가 된다. 일상 속의 개미를 관찰해 보자. 과자 부스러기만 있어도 어디선가 수많은 개미떼가 몰려든다. 여기서 착안한 시스템이 바로 ACS다. 30평 아파트는 우리에겐 다소 좁을 수 있는 공간이지만 개미에게는 엄청나게 큰 망망대해와 같다. 하지만 개미는 용케 최적의 길을 찾아내 일사분란하게 이동한다. 개미는 이동할 때마다 페르몬이라는 호르몬을 뿌리고 다니는데, 이것은 시간이 지남에 따라 공기 중으로 사라지며 눈으로 식별은 불가능하다. 즉, 개미들은 저마다의 빠른 길을 탐색하며 자주 다니는 길에는 페르몬의 양이 많아진다는 것을 학습한다. 결국 어느 시점이 되면 페르몬의 양이 많은 길로만 다니게 되는데, 이 길이 개미가 찾은 최적의 답이며 수많은 연구 결과에서 실제로 최적의 길임을 증명하고 있다. <그림 1>은 A->B->C->D의 과정을 거쳐 페르몬의 양이 증가함을 보여준다. 결과적으로 아랫길로 이어지는 최적의 경로를 찾았다. 단순하지만 과학적인 원리임을 알 수 있다. 이를 상태 천이규칙으로 표현한 것이 <그림 2>이다.
.jpg)
여기서 τ(r,s)는 노드(r)과 노드(s)사이의 간선의 페로몬 양, η=1/δ은 δ(r,s) (노드(r)과 노드(s)의 길이)의 역수이고 Jk(r)은 노드(r)에 있는 에이전트k가 방문할 수 있는 남아있는 노드들의 집합이다. 그리고 β는 페로몬과 간선 길이의 상대적인 중요도를 결정하는 파라미터이다(β>0). 즉, 거리의 역수와 페르몬의 양에 비례해 다음 선택할 노드를 결정한다. 거리가 짧고 페르몬의 양이 많은 곳이 좋은 경로임은 자명하다.
이러한 개념으로 개미 집단을 형성한 것이 ACS다. ACS는 ‘개미 군중 시스템’이라 한다. 여러 개미 집단에서 최적의 답을 얻는다면 당연히 더 좋은 결과를 얻게 된다.
최적화 문제가 다 그렇듯이 ACS도 최적의 답을 찾을 뿐 그것이 정확하다고 보장할 수는 없다. 하지만 최근에 영상처리나 네트워크의 라우팅 문제, 로봇 주행 알고리즘에 ACS를 응용하려는 연구가 한창인 것을 봤을 때, 살아있는 곤충을 모델로 고안된 과학적인 알고리즘이라는 점에서 분명 놀라운 시도이다. 이러한 노력은 인공지능의 발전에 큰 도움이 되고 있다.
