A Physarum polycephalum plasmodium sends out streamers along its tree.
아메바가 최상의 호율적인 루트를 찾는 실험의 결과 사진
(왼쪽 위부터 시계 방향으로 n=4, n=5, n=6, n=7)
컴퓨터 공학계의 가장 오래되고 유명한 문제인 TSP
(Traveling Salesman Problem: 세일즈맨의 출장 문제)문제를
하나의 단세포 생물이 해결해 주었다는 논문이 2018년 12월 말에 발표되었다.
일본 도쿄에 소재한 게이오 대학교 연구팀은 단세포 아메바를 사용해서
TSP 문제를 다음과 같이 풀었다고 한다.
가령 당신이 여러 도시를 돌아다니면서 상품을 파는 세일즈맨이라면,
가장 효율적인 세일즈 방식으로 최고의 수익을 올리는 것이 목적이다.
그러기 위해서는 담당된 도시들을 가장 짧은 거리와 시간을 들여서
한번씩 방문한 다음에, 다시 시작한 도시로 돌아오는 최상의 루트가 필요하다.
하지만 이 문제를 해결해 줄 간단한 수학공식은 존재하지 않는다.
유일한 방법은 방문해야 할 도시와 도시 사이의 거리를 일일이 측정해서
그 중에서 제일 효율적이고 짧은 루트를 알아내는 수 밖에 없다.
더 골치아픈 것은 방문해야 할 도시의 숫자가 증가하면서
가능한 모든 루트의 숫자는 기하학적으로 증가하는 것이다.
예를 들면 도시가 4개면 오직 3개의 루트의 거리만 재면 되지만,
도시의 숫자가 6개이면 360개로, 10개 이상이 되면 수백만이 넘어간다.
(방문해야 할 루트의 숫자는(n − 1)!/2 만큼 증가한다.)
나무에 서식하는 Physarum polycephalum 아메바
그래서 이 TSP 문제는 컴퓨터 공학에서 "NP hard' 라고 불리우는 일반적인 문제로,
컴퓨터 해킹 시스템이나 암호화폐(cryptocurrency) 관련된 안보 문제와도 밀접한 관계를 있어서,
많은 사람들이 빠른 시간내에 빨리 유사한 문제를 해결하고자 노력을 기울여 왔다.
지금까지 이런 문제는 컴퓨터에서 널리 사용되는 알고리듬을 사용해서 문제를 풀고자 해 왔는데,
게이오 대학교 연구진은 지금까지 사용하던 방법과 완전히 다른 각도와 방법으로
아메바(Physarum polycephalum)를 사용해서 이 복잡하고 어려운 문제를 해결고리를 찾아냈다.
이 아메바는 아주 간단한 단세포 생물체로 환경 자극에 두가지 반응을 한다:
하나는 영양분이 있는 방향으로 움직이고,
또 하나는 빛을 피해서 달아나는 것인데,
수백만년동안 이 아메바는 이 두가지 기능을
아주 효율적으로 이행할 수 있게 진화된 생물체이기도 하다.
게이온 연구팀은 바로 이 아메바의 효율성을 토대로 TSP 문제를 해결하기 위해서
합성수지 소재로 별 모양의 칩(resin chip)을 구조를 만들었다.
이 칩의 가운데 둥근 특수한 방은 64개의 같은 길이의 채널로 둘러 쌓였고,
각 채널끝에 음식을 준비해 두고, 아메바를 그 특수 방에 투입했다.
left: 아메바가 이동할 수 있게 제작된 64개의 채널(루트)로 만들어진 수지 칩과 빛 센서
right: 각 채널마다 빛을 제공하거나 막아서 아메바의 이동을 콘트롤 할 수 있는 장치
Image credit: Zhu et al, doi: 10.1098/rsos.180396.
투입된 아메바는 바로 음식이 있는 방향으로 이동해서 음식을 흡수했다.
하지만, 음식을 흡수하게 되면, 다른 채널의 불이 꺼지도록 장치를 해 놓았다.
그러면 아메바는 불이 꺼진 다른 채널로 이동하게 된다.
이 실험에 사용된 각 채널은 세일즈맨의 가상적인 루트를 상징해 주며,
아울러 어떤 도시부터 방문해야 할지 순서 역시 상징한다.
아메바가 한 채널로 들어 가면, 곧 세일즈맨의 한 도시로 간주되며,
아메바가 그 채널에서 음식을 취득하면, 자동적으로 불이 꺼진 다른 채널들은
세일즈맨이 다음에 방문해야 할 도시들에 해당한다.
멀리 떨어진 도시일수록, 그 도시를 나타내는 채널의 불은 더 자주 꺼지게 된다.
'TSP 문제를 해결한 아메바' 논문을 요약한 동영상
(Source: Zhu, L. et al, 2018/ YouTube)
이런 방식은 TSP 문제를 푸는데에 효율적인 방법같지 않지만,
이 시스템의 가장 큰 잇점은 투입된 아메바는 컴퓨터의 알고리듬대로 빠르게 각 채널의 거리를
일일이 체크해서 가장 효율적인 루트를 파악하는 것이 아니라,
아메바는 수백년간의 진화로 가장 잘 할 수 있는 두가지 기능을
주위 환경에 따라서 그저 본능에 의거해서 가장 최상의 루트를 찾아가는 것이다.
이는 곧 방문해야 할 도시의 숫자를 추가해서, 기하학적으로 가능한 루트가 기하학적으로 증가해도
아메바는 이 문제를 푸는데 추가의 시간을 요하지 않는다는 것이 이 시스템의 제일 큰 수확이다.
그 이유는 컴퓨터는 알고리듬대로 한가지 명령을 차례대로 수행하는데(Serial) 반해서,
아메바는 Linear(or parallel) 방식으로 수행해서 도시가 (n)이 하나씩 증가할 때마다
기하하적의 가능성이 아니라, 일차원식(linear)으로 증가하기 때문이다.
도쿄의 지형에 맞추어서 음식의 양(쉽게 통과할 수 있는 장소)과
빛의 밝기(장애물)를 제작한 실험 세트에서
아메바의 이동경로가(가운데) 실제 도쿄의 철도/전철 지도의 디자인과 많이 흡사하다.
Image credit: adapted from Atsushi Tero et al, doi: 10.1126/science.1177894.
고로, 아메바는 컴퓨터 알고리듬보다 더 빠르게 NP-hard 문제를 풀 수 있다는 것이 밝혀졌다.
그렇다면 어떻게 이런 결과를 나올 수 있을까? 라는 질문에는
아이러니칼하게도 게이오 연구팀도 이 메카니즘을 확실히 모른다고
이 연구팀의 리더이자 연구 논문 저자인 마사시 아오노 박사가 기자회견에서 말했다.
만약 아메바가 어떤 메카니즘으로 이 문제를 해결할 수 있는지 밝혀낸다면,
단지 TSP 문제만 아니라, 컴퓨터로도 문제의 답을 푸는데 시간이 많이 걸리는
다양한 문제들, 특히 컴퓨터 안전에 관한 분야의 문제들을 해결하는데
시간을 많이 단축할 수 있는 가능성이 아주 높아진다.
아메바의 이동방식처럼 parallel computing/아나로그 linear 방법은
화공학, 천문물리학,기후 모델링과 단백질의 기능의 예측하는데 기여할 수 있으며,
아메바처럼 생물학적 토대로한 차세대 컴퓨터 개발의 가능성을 제시해 주기도 한다.
아주 단순하고 작고 보잘것 없는 단세포 생물인 아메바가
아주 복잡하고 어려운 문제를 풀 수 있게 도와주고,
더 나아가서 컴퓨터의 기본 알고리듬을 바꾸어 놓을 수 있다는 사실이
그저 놀랍고, 자연계의 무궁무진한 가능성을 재발견하게 된다.
