개미의 방문 1편
외판원 문제(TSP)와 개미최적화(ACO)
[#1 우글우글]
길에는 수많은 차들이 돌아다니고 있어. 사람이 정착한 곳에는 어김없이 빌딩이 자라나고 그 사이사이를 차들이 메꾸게 되어. 균이 자리잡은 빵 겉표면이 하얗게 정복당하고, 황량한 사막에 비가 내리면 꽃들이 그 땅을 서서히 잠식하듯이. 인간은 자라난 빌딩 번식지 사이에서 번성하고 개미처럼 우글거리며 돌아다닌다.
개미는 페로몬을 뿌려 대화한대. 냄새로 위험여부나 건강 등 다채로운 이야기를 할 수 있다는 사실은 꽤 흥미로워. 하지만, 개미가 페로몬으로 가장 많이 하는 이야기는 '나 여기 다녀감!'이래. 장소에 자기의 흔적을 남겨두는거지. 그런데 생각해보면 조금 이상하기도 해. 왜 흔적을 남길까? 동물의 왕국을 보면 사냥감이나 포식자나 둘 다 은신하기 바쁜데, '나 여기 있소'라니.
(출처 : NBC news)[#2 돌아다닌다는 것]
우리가 돌아다니는 이유는 어떤(유형이든 무형이든) 걸 옮기기 위함일거야. 물건을 가져다주기 위해, 살펴보러 가기 위해, 이야기를 전하기 위해, 만나기 위해 등등. 하지만 많은 경우 각자의 보따리에는 여러 개의 물건들이 들어있고 여러 곳을 찾아가야할 일이 생기곤 해. 우리가 기다리는 택배는 다른 택배상자들과 함께 커다란 택배차에 실려서 이곳저곳을 돌아다니고, 버스는 특정 순서대로 정류장을 지나치고, 기쁜 소식을 전하기 위해 여러 약속장소를 돌아다니는 것처럼.
이 목적 있는 무수한 출발지-목적지의 조합들은 우글거리는 모양을 만들어내는 원동력이 돼. 그런데 여기서 '목적 있다'는 말이 살짝 피곤해. 우리는 효율을 중시하게 될거란 말이어서 결국 어떻게 저곳들을 방문할지를 고민하게 될거란 뜻이 되겠지. 이 고민은 택배차의 '남은 배송 건수', 택시호출앱의 '배정 중', 우리 머리속에 '가는길이니까 들러볼까' 정도로 표현될 것이야.
여러 곳을 두고 방문순서를 결정하는 고민은 우리가 늘상 하는 것이다보니 크게 특별할 것 없어보인다. 하지만 재밌게도 이 문제는 수학이 해결할 수 없는 난제 중 하나래. 모든 경우를 다 찾아보는 것 말고는 딱히 수식 같은걸로 딱 답이 나올 수 없는 구조라는거지.(수학에서는 이걸 NP-hard하다고 해. 나도 무슨 말인지는 몰라.) 그래서인지 "다수의 방문점이 있고 이 점들을 최소한의 길이로 잇는 연결순서를 찾는 문제"는 이름까지 생겼어. 바로 TSP(Traveling Salesman Problem, 외판원문제). 이동으로 우글거리는 도시 속에서 풀어야만 하는 로지스틱스 문제가 풀 수 없는 문제라니.
TSP는 점들을 최단거리로 이을 수 있는 방문순서를 고민하는 문제다. (출처 : SCM DOJO)[#3 n!]
풀 방법이 아예 없는 건 아니야. 우리가 방문하는 모든 경우를 다 따져보고 그 중 제일 좋은 걸 고르면 되는거니까. 예를 들어 건대입구랑 합정을 다녀와야한다면, 건입-합정을 갈지, 합정-건입을 갈지 생각해보고 좋은 걸 고르는거지. 문제는, 방문해야하는 곳이 많을 때야. 3군데를 들러야한다면 경우의 수는 6개가 되어. 4군데라면 24개, 5군데면 120개, 6군데면 720개. 사실 4군데 고민할 때부터 이미 모든 경우를 다 따지는 건 말도 안되는 일이 되긴 해.
그럼 컴퓨터를 쓰면 되지 않을까 싶어져. 어차피 기계한테 24가지 정도야 숫자도 아니니까. 하지만 이 방법이 먹혔다면 난제 소리를 듣지 않았을거야. 위에서 적어놓지는 않았지만.. 방문할 곳이 10군데면 경우의 수는 무려 3628800가지가 돼. 이제 한 20군데 들러본다고 할까? 0이 18개나 붙는 어마어마한 숫자가 등장해. 이 정도면, 저 0 18개짜리 경우의 수를 보관하는 데만 컴퓨터의 저장공간을 거진 다 써야 해. 풀 수 없는거지.
실상은.. 순서를 결정하는 경우의 수, '조합수(n!)'는 가장 빠르게 증가하는 수라는 것이야. 그래서 누군가는 가장 저주스러운 수로 부른다고. 조금만 커져도 손대지도 못할 정도로 문제가 거대해져버리니까.
<공돌이 노트 #1>
모든 경우를 다 찾는 방법을 직접적 기법(Direct)이라고 부른다. 하지만 이 방법은 n!이라는 거대함 앞에 무력할 뿐... 실제로 대부분의 문헌들은 방문점 10개 이하에서만 이 기법이 실효성이 있다고 말하고 있다. 그 이상은 너무 시간이 오래걸린다는 것.
[#4 찍기]
아이러니한 건 이 난제가 굉장히 일상적인 문제라는 것이고, 재밌게도 수학을 안 쓰고도 우리는 퍽 잘 푼다는 사실일거야. 하루에 약속이 5가지 (쓰레기 버리기 - 학교 들르기 - 지수 만나기 - 수지 만나기 - 장보기) 정도 있어도 문제 없이 계획을 잘 세우곤 해. 우리가 120가지 경우의 수를 다 따져보고 이 계획을 세우는 건 아니니까, 우리는 훌륭한 '찍기' 방법을 익혔다고 볼 수 있을거야.
어림법(heuristics : 휴리스틱스)은 실제로 가장 활발하게 연구되는 분야래. 모든 경우를 다 찾아서 진짜 '최적'을 찾을 수 없으니 대충 찍어서라도 답을 찾아보자는거지. 가장 가까운 곳부터 순서대로 방문한다든가, 지그재그 순서로 방문하는 등 어림하는 방법에는 끝이 없어. 물론, 어림법의 가장 큰 한계는 이 답이 진짜 최적이라고 장담할 수 없다는 걸거야. 어디까지나 찍은 거니까.
하지만 가장 인간적, 혹은 자연적이라 볼 수도 있어. 이 문제는 인간만의 문제가 아니기 때문에 자연에 있는 벌, 철새, 곤충들도 위와 비슷한 고민을 한다고 해. 다들 이 문제를 진지하게 다 따져봐서 푼다기 보다는, 각자 적응한 풀이법으로 훌륭한 어림을 하며 '납득할 수준의 결과'를 낸다면 만족하는 것이지.
사실 대충 찍어서 견딜 수 있을(?) 정도의 결과만 낸다면 그냥 쓰고 살 수도 있는 일이야. 어떻게 모든게 다 최선이겠어. 하지만, 그래도 마음 한켠 해결되지 못한 무언가가 남아있어. 우리는 정녕 '진짜 최적'은 찾을 수 없는 걸까? 라는.. (왜 이런 비자연적인 고민을 해야하는 걸까 싶기도 하지만)
<공돌이의 노트 #2>
"가장 좋아!"라는 의미의 '최적'은 의심을 많이 받곤 한다. '가장'이라는 단어 때문일 것이다. 가장 높은 산을 찾는다 했을 때, 우리가 찾은 산꼭대기가 한라산인 것과 에베레스트인 것에는 차이가 있다. 이 때 한라산을 '좋지만 가장좋은 건 아닌 최적, 혹은 제주도에서 가장 높은 산(지역적 최적: local solution)'이라 부른다. 에베레스트는 '가장 좋은 최적, 지구에서 가장 높은 산(전역적 최적: global solution)'라고 부른다.
앞서 '잘 찍고 적당히 사는 것이 자연적인 것이다'라는 말을 했지만 생각해보면 그렇지도 않은 것 같아. 잘 찍어서 만족하는게 과연 자연일까? 자연은 경쟁으로 넘쳐나고, 경쟁은 적자생존을 허락하는 차가운 원리라 생각해본다면, 결국 찍기 경쟁도 '더 잘 찍는 개체가 승리한다'라는 말로 생각해볼 수 있을거야. 다른 말로 표현하면, '찍는 것 중에도 좀 더 좋은 답을 내는 찍기가 있다'겠다.
우리 주변의 자연은 수억년 시간의 산물이기도 해. 수억년 간 진행된 경쟁에서 살아남고 적응한 자연이라면, 그 자연이 내놓는 해답은 '굉장히 잘 찍는' 것이라는 뜻이 되지 않았을까? 수학적으로 말해본다면, 시간의 힘에 의해 '어림법 중에도 진짜 최적(global)에 가까운 해답을 내는 방법이 자연에 이미 있다'라는 희망적인 말로 들리기 시작해. 자연으로 시선이 향하게 된 것은 어쩌면 당연한 일이었을 수도 있어.
[#5 개미]
개미는 여러곳을 돌아다니며 일하는 대표적인 곤충이야. 하지만 어디를 가야하는지, 어떻게 가는게 가장 좋은지는 개미도 사실 알 길이 없어. 개미가 속으로 어떤 생각을 하고 있는지 알기는 힘들지만, 개미는 자기만의 방식대로 탐험을 하며 여기저기 돌아다니기 시작할거야. 그러다가 우연히 괜찮은 길을 만들게 되면 그 길을 계속 사용하게 되겠지.
여기까지는 사람이 돌아다니는 것과 크게 다르지 않아. 한 가지 다른게 있다면 개미는 몇날며칠이 지나며 자기 경험상 좋은길에 체취를 진하게 남기기 시작한다는 점일거야. 다른 개미들은 이 페로몬의 냄새를 맡고는 따라가기 시작해. 하지만 중요한건 무조건 페로몬을 모두 다 쫓아가지는 않는다는거야. 각 개미는 자신이 탐험을 할지(페로몬이 약한 쪽을 택할지) 페로몬을 쫓아갈지 결정을 한다고 하네. 그러니까 확률적인거야. 냄새가 진한 곳을 택할 확률은 높지만, 그렇다고 약한 곳을 택하는 개미가 아예 없다는건 아니라는거지.
페로몬이 진했던 길이 정말 좋은 선택지였다면, 탐험을 택한 개미는 자신이 탐험한 길이 상대적으로 별로였다는 사실을 알고는 딱히 페로몬을 남기러 다시 찾아가지 않게 돼. 그렇게 대부분의 개미들은 페로몬이 진한 길로 몰리고 그 길의 향은 더 강해지며 결국 절대적인 해답으로 자리매김할거야. 만약 탐험을 택한 개미가 더 괜찮은 길을 발견했다면, 그 길을 재방문하며 페로몬을 점점 더 진하게 남길 것이고 그 길로 빠져드는 개미가 점점 늘어나게 될거야. 다시금 시간이 흐르면서, 새로운 해답이 기존의 해답을 뒤집기 시작하게 되겠지.
개미의 이야기를 이렇게 길게 한 이유는, 바로 수학적 난제라는 저 문제를 개미가 풀어내고 있기 때문이야. 엔지니어들은 컴퓨터에 가상의 개미들을 만들고, 아주 간단한 행동규칙만 만들어 놓았다. 규칙은 딱 세 개.
1. 매 점에서 다음 점을 택할 때는 페로몬의 진하기에 따라 확률적으로 선택한다.
2. 모든 점을 방문하면 돌아온다. (= 남은 점이 없다면 돌아온다)
3. 한 번 다 돌았다면, 그 길에 점수를 매기고 그만큼의 페로몬을 자신이 다녔던 길에 남긴다.
끝.
100마리의 개미가 20번 정도 돌았을까? 인간의 직관이나 생각이 전혀 포함되지 않은 이 간단한 규칙은, 무수히 많은 방문점이 있는 문제까지도 전역적 최적에 가까운, 매우 훌륭한 답을 구해내버리고 말아. 신기해. 수적으로는 풀이가 불가능한 문제를 간단규칙과 시간이 해결해주다니.
<공돌이의 노트 #3>
개미의 메커니즘을 사용한 어림법을 ACO(Ant Colony Optimization)이라고 부른다. 이름을 받을 만한 가치가 있지 않은가? 또한, 개미 최적화같은 기법은 단순히 어림법이라 부르지 않고 어림법의 어림법, 즉 meta-heuristics로 따로 분류한다. 특정 문제만을 풀기 위한 어림이 아니라 굉장히 광범위한 문제를 풀 수 있는 '확장성'이 좋기 때문. 이 말인 즉슨 TSP 말고 다른 문제들도 풀 수 있다는 뜻이다. 나중에 다뤄보도록 해야겠다.
(참고로 meta-heuristics에는 유전자 알고리즘(GA), 고래 알고리즘 등 자연현상에서 유래된 다양한 기법(NIC - Nature Inspired Computing)들이 있다고 한다. 흥미롭다. 일반적이고 강력한 기법이 자연이 있고, 그 것이 어림법의 일종이라니.)
[#6 개미가 상징하는 것]
진짜 최적을 찾겠다는 열망을 뒤로한 채, 많은 사람들은 이 간단한 규칙이 어떻게 복잡한 문제의 해답에 다가갈 수 있는 것인지, 그 원인을 궁금해하기 시작해. 흔히 집단 지성이라 말하는 것의 발현인걸까? 우연히 찍는 것이 반복되고, 서로 기억되고 공유될 수 있다는 것의 힘은 무엇일까. 시간(혹은 반복)이라는 건 어떤 의미인걸까.
다음에는 개미 이야기를 바탕으로 정보를 공유하는 것, 확률적 선택이 갖는 의미, 그리고 시간의 힘에 대해 이야기해볼까 해. 개미가 함축하고 있는 것들을 이야기해보면 우리는 이 세상이 변화하고 진화하는 과정에 대한 어떤 고찰을 할 수 있을 것만 같아. 예를 들어 자연현상에 목적이 있는 것인지, 아니면 자연스럽게 흘러가는 것이 어떤 최적에 도달한 것일 뿐인지 등등.
그럼, 다음에 또 글이 쓰고싶어질 때.
참고문헌
영상출처 : https://www.youtube.com/watch?v=rYjxtmt8g9A&ab_channel=inversed
참고문헌 : https://towardsdatascience.com/the-inspiration-of-an-ant-colony-optimization-f377568ea03f
