d라이브러리

순회세일즈맨 문제(TSP, Traveling Salesman Problem)는 컴퓨터과학의 대표적 난제 중 하나다. 세일즈맨이 N개의 도시를 모두 한번씩 방문하고 돌아오는 가장 짧은 경로를 찾는 문제다. 방문해야 할 도시 수가 50개면, 방문하는 모든 경로 수는 49!, 즉 6.08×1062개다. 여기서 각각의 경로는 하나의 솔루션이 된다. 최적화 알고리즘은 이들 중 가장 길이가 짧은 솔루션, 즉 가장 매력적인 솔루션을 찾아내는 것이 목적이다.

(그림 1)을 예로 든다면 각 격자점은 솔루션 하나에 해당한다. 최적의 솔루션은 가장 높은 봉우리에 해당한다. 이처럼 솔루션들이 이루고 있는 지형적 공간을 ‘문제공간’이라 한다. 다만 TSP를 포함한 대부분의 문제는 (그림 1)보다 훨씬 복잡한 다차원의 문제공간을 이룬다. 즉 (그림 1)과 같이 시각적으로 상상하기는 힘들다.
 

이런 지형적 관점에서 보면 문제 해결의 과정은 공간 탐색의 과정이다. 각각의 문제는 고유의 지형을 갖고 있다. 대부분의 난제들은 다차원 공간에서 복잡한 지형을 띠고 있어 이 지형을 파악하는 것 또한 난제다.

문제공간은 유전알고리즘의 활동 무대다. 문제공간에 대한 언급을 생략한 유전알고리즘의 묘사는 함수의 특성은 모르는 채 미분공식만 언급하는 것과 같다. 유전알고리즘은 효과적인 문제공간 탐색 기법의 하나이고, 문제공간에 대한 적절한 이해를 토대로 좋은 알고리즘이 만들어질 수 있다.

공간 탐색 게임 축구

흔히 축구를 공을 차는 운동이라 생각하지만 사실 축구는 ‘공간만들기 게임’이라고 보는 편이 정확하다. (그림 2)에서처럼 경기장을 7천개의 격자로 나누면, 어느 순간 22 명의 선수와 축구공은 이 7천개의 격자 중 하나를 차지하게 된다. 이 때 있을 수 있는 모든 경우의 수는 7천개 중 23개를 골라 줄을 세우는 방법의 총수인 7000P23이 된다. 이는 1조의 7승보다 큰 수다.
 

따라서 축구 경기에는 총 7000P23개의 점이 있고, 90분간 이 점들로 이루어진 문제공간을 옮겨 다니는 게임이 축구다. 이 점들 중에는 거의 골인 상태인 점이 있고, 골을 넣을 가능성이 아주 높은 점도 있을 것이다. 하지만 대부분은 골과 연결이 쉽지 않은 점들이다. 즉 각각의 점은 골을 넣기에 매력적인 정도를 나타내는 ‘적합도’를 가진다. 11명의 선수는 각자의 지능적이고 협동적인 움직임을 통해 축구장의 모양을 적합도가 높은 점에 대응되도록 만드는 것이다. 그래서 축구는 공을 가진 사람보다 공을 갖지 않은 사람의 움직임이 중요하다는 것이다.

문제공간 탐색의 또다른 좋은 예는 바둑이다. 한국 바둑은 1990년대 이후 중국과 일본을 제치고 세계 바둑의 정상으로 군림해오고 있다. 물론 조훈현과 이창호라는 두 걸출한 기사가 존재했기 때문에 가능한 일이었지만 그 저변에는 그들을 있게 한 ‘한국류’바둑이 있다.

일본 바둑은 미학을 추구한다. 모양이 아니면 택하지 않는다. 이에 반해 한국 바둑은 어린 기사들을 중심으로 미학의 너머에 존재하는 영역을 탐색해 한국적 탐색 스타일을 만들어냈다. (그림 3)의 기보에서 흑9에 대한 가장 일반적인 대응은 백A이고, 발상을 전환한다해도 백B 정도가 전통적인 정석이었다. 이 장면에서 백10으로 붙이는 것이 ‘한국류’의 대표적 정석이다. 통념을 깨는 공간탐색의 예를 보여주는 이 정석은 일본과 중국에서도 선풍적인 인기를 끌고 있다.
 

바둑이야말로 현존하는 가장 거대한 공간 탐색 게임이다. 바둑의 문제공간 크기를 정확히 계산하기는 힘들지만, 죽은 돌을 들어낸 곳에 다시 돌을 놓거나 패가 발생하는 경우를 제외하고 2백수 정도에서 게임이 끝난다는 단순한 조건으로 계산해도 약 361P200 정도의 어마어마한 크기의 문제공간이 발생한다.

스윙폼 바꾸기 힘든 이유

우리 몸에 있는 약 3만개 정도의 유전자는 발생과정에서 다양한 기능을 하는 특정세포를 만든다. 즉 줄기세포가 발생과정을 거쳐 안정된 형태로 수렴하면 머리카락 세포나 손톱, 뼈세포, 신경세포 등 특정 기능을 가진 하나의 세포가 된다. 이들은 잠재적으로 다른 세포가 될 가능성을 자신으로 흡수함으로써 세포의 한 종류로서 이름을 올렸다.

생태계에서 만들어질 수 있는 종의 수는 이론적으로 무한하다. 하지만 이들 중 극히 일부만이 출현할 수 있다. 한 종은 유사한 다른 종이 만들어질 수 있는 가능성을 흡수해 버리기 때문이다. 또한 테니스를 치는 사람은 각각 자신의 스윙폼을 갖고 있다. 수많은 스윙폼 중에서 시간이 지나면서 자신만의 폼으로 정착된다. 한번 형성된 폼을 고쳐보려고 조금 변화를 줘도 의례 원래의 폼이 흡수해 버린다.

이 같은 세포와 종, 스윙폼 등은 공간 탐색에서 문제공간과 함께 중요한 개념 중 하나인 ‘끌개’(attractor)의 예다. 끌개는 솔루션들이 이루는 공간에서 다른 솔루션들을 끌어들이는 흡인력을 가진 솔루션들을 말한다. (그림 1)의 지형에서 더 올라갈 수 없는 봉우리들은 지형상의 끌개다.

수없이 많은 제품 중에 시장을 형성하고 상품 분류상의 한 자리를 차지하는 제품도 끌개이며, 각 개인이 형성하는 고정관념이나 인생관 등도 끌개다. 끌개는 강한 흡인력을 가져 그 언저리에서는 다른 끌개가 형성되지 못하게 한다.

한번 형성된 제도를 바꾸려면 엄청난 노력이 들고, 이미 고정된 테니스의 스윙폼을 바꾸려면 처음 시작하는 것보다 몇배의 노력이 드는 이유가 끌개의 흡인력 때문이다. 공간 탐색에서도 끌개에 한번 빨려 들어가면 좀처럼 빠져 나오기 힘들다. 최적화 알고리즘의 중요한 과제 중 하나가 품질이 나쁜 끌개에 말려 들어가는 것을 피하는 것이다. 끌개는 문제공간의 블랙홀이고 최적화에 있어서 목표이자 장애물이기도 하다.

상상을 초월하는 크기

물리계에서 입자들이 모여 이루는 구조는 입자의 상호작용에 따라 일정 수준의 에너지를 갖는다. 수없이 많은 가능한 구조들은 에너지의 크기에 따라 다차원의 지형을 이룬다. 에너지가 낮아 주변에 다른 구조가 형성되지 못하도록 하는 안정된 구조는 끌개다. 즉 끌개는 입자들이 모여 자연계에 존재할 수 있는 형태의 후보들인 셈이다. 이런 시스템에서는 입자의 수에 지수함수적으로 비례하는 개수의 끌개들이 존재하는 것으로 알려져 있다.

필자의 연구실에서 TSP의 끌개 수를 세어본 결과, 물리계에서와 마찬가지로 문제의 크기에 지수함수적으로 비례하는 수의 끌개가 존재하는 것으로 확인됐다. 10개 도시 TSP의 경우, 끌개는 평균 4개, 20개 도시는 평균 1백70개 정도의 끌개가 존재한다. 도시 수가 1백개로 커지면 끌개 수는 평균 ${3.4×10}^{16}$ 정도 될 것으로 추정된다. 이는 3경4천조라는 엄청난 수다.

끌개 수가 엄청나게 많아 보여도 전체 해의 수에 비하면 미미하다. 1백 도시 TSP의 모든 해의 수는 ${9.3×10}^{157}$ 정도다. 전체 문제공간에 있는 해들 중 ${3 ×10}^{141}$ 개당 하나씩의 끌개가 존재하는 셈이다. 즉 평균적으로 1조의 11승에 30억을 곱한 수만큼의 해마다 하나씩의 봉우리가 존재하는 것이다.

그렇다면 3천 도시 TSP의 경우 문제공간의 크기와 끌개의 수는 얼마나 될까. 공간탐색 알고리즘은 이런 황량한 공간을 돌아다니는 외로운 교통수단이다.

최적화 알고리즘 분야에서는 ‘언덕오르기 방식’이라는 기초적 기법이 있다. 문제공간에서 임의의 위치를 기준으로 우선 매력적으로 보이는 방향으로 봉우리를 올라가는 방식이다. 이 방식으로 1백 도시 TSP의 문제공간을 탐색하면, 3경4천조개의 봉우리 중 출발한 지점에서 대략 가장 가까운 봉우리에서 멈춘다. 방대하고 복잡한 문제공간을 이해하기 시작하면 이 방법이 한심해 보이게 된다.

유전알고리즘의 주연산자인 ‘교차’(자세한 내용은 7월호 연재 참조)는 문제공간에서 떨어져 있는 두해의 특성을 부분 결합해 새로운 해를 만들어낸다. 이는 봉우리 주변에 있는 두 해가 결합해 봉우리로 올라가도록 돕기도 하지만, 기존의 해가 몇몇 봉우리 주변에서 벗어나도록 도와주기도 한다. 즉 교차에 의해 새롭게 만들어진 해가 특정 봉우리에 고착되는 것을 피하고 또다른 봉우리를 탐색할 수 있는 가능성을 높이는 것이다. 그리고 변이는 문제공간에서 점프를 해 다른 지역으로 이동하는 효과를 준다.

탐색 알고리즘의 능력이 강해지면 어떤 끌개는 다른 끌개를 흡수한다. 알고리즘은 문제공간을 여행을 하는 교통수단에 해당된다. 비행기를 타고 3차원의 문제공간을 탐색한다면 걷는 것에 비해 작은 봉우리에 고착되는 것을 어느 정도 피할 수 있다. 작은 봉우리들은 비행기의 우수한 탐색 능력에 의해 주변의 큰 봉우리에 흡수되기 때문이다.

그렇지만 비행기를 이용한다고 해서 우리나라에서 출발해 에베레스트산 정상을 찾기는 쉽지 않을 것이다. 더욱이 문제공간이 3차원을 넘어 TSP와 같이 다차원으로 바뀌면 이 확률이 얼마나 될지는 상상하기 힘들다.

유전자 수에 비례하는 세포 수

스튜어트 카우프만은 의사이자 뛰어난 생물학자로 1987년 천재적 연구자에게만 주는 ‘맥아더 연구비’를 받은 사람이다. 자신의 생각을 남에게 몇 시간이고 이야기하기를 좋아해서 그가 지적인 넋두리를 시작할 낌새가 보이면 모두들 도망간다는 일화도 있다.

카우프만은 개체들간의 관계가 만들어내는 시스템의 최종형태를 알아보려고 ‘NK-지형’이라는 모델을 제안했다. 이 모델에는 N개의 전구가 있고 각 전구의 점멸은 다른 K개 전구의 점멸 상태에 영향을 받는다. 즉 N개의 각 전구에 불이 켜지거나 꺼져 있는 임의의 상태에서 시작한 시스템은 시간이 지남에 따라 다양한 패턴으로 변해간다. 당연히 K값이 클수록 시스템은 복잡해진다. N개의 전구들이 만들어낼 수 있는 모든 경우의 수는 ${2}^{N}$ 이다.

카우프만은 K가 2인 경우, 즉 N개의 전구가 다른 두개의 전구에 영향을 받는 경우에 특히 관심을 가졌다. 이 경우 임의의 상태에서 시작해 시간이 흐르면 시스템의 최종 상태는 어떻게 될까. 각 시스템의 최종 상태는 모두 다를까. 그렇지 않다. 최종 상태는 대략 $\sqrt{N}$에 비례하는 것으로 나타났다. ${2}^{N}$ 만큼이나 많은 엄청난 수의 시작점들이 시간이 지남에 따라 대략 $\sqrt{N}$개 중의 하나로 귀착되는 것이다. 이 귀착점들은 모두 끌개다.

카우프만은 유전자수가 N개인 생물체에서 나타나는 서로 다른 세포의 종류를 조사해 본 결과 흥미로운 관계를 알아냈다. 만약 유전자수가 N이면 최종 세포의 수는 대략 $\sqrt{N}$에 비례한다는 사실을 발견한 것이다. (그림 4)는 카우프만이 유전자 수와 세포 유형의 수 사이의 관계를 나타낸 그림이다. 카우프만은 이 같은 사실로부터 N개의 유전자를 갖는 생물의 네트워크는 K=2 정도의 NK-지형과 비슷한 수의 끌개를 가질 것으로 추정한다. 실제로 유전자들은 대개 2-10 정도의 연관된 유전자를 갖고 있는 것으로 알려져 있다.

단백질의 3차원 구조에도 강력한 끌개가 존재한다. 단백질 3차원 구조 규명은 학자들이 세기의 도전이라고 부를 정도의 핫이슈로 주목받고 있다. 세포 속에서 수백 또는 수천개의 아미노산 서열이 주어지면 순식간에 3차원 구조를 만드는데 이것이 단백질이다. 어떻게 중앙통제장치도 없는 세포에서 이렇게 일관된 구조를 만들 수 있을까.

진화 통해 형성된 단백질 끌개

물리적인 접근을 하는 사람들은 주어진 아미노산 서열로 구성할 수 있는 모든 3차원 구조 중에 가장 에너지가 낮은 구조로 귀착된다고 추측한다. 그래서 이 문제를 주어진 서열을 갖고 최소에너지 구조를 찾는 최적화 문제로 풀기도 한다.

그렇지만 세포가 결코 복잡한 공간탐색 알고리즘을 수행할 리 없다. 단백질이 항상 일관된 모양을 쉽게 갖추려면 아미노산 서열이 주어질 때 3차원 구조 형성은 이미 쉬운 문제가 돼 있어야 한다 (적어도 세포에게는). 다만 우리가 아미노산 서열을 어떻게 모델링해야 그렇게 쉬운 문제가 되는지를 모를 뿐이다.

진화의 과정을 통해 임의의 상황에서 시작하더라고 쉽게 강력한 한 끌개로 귀착되는 성질을 가진 아미노산 서열들이 살아남아 단백질로 이름을 올렸을 것이다. 이 구조가 반드시 최소에너지 상태가 아니라도 상관없다. 주변의 잠재적인 3차원적 모양을 강력하게 흡인하기만 하면 된다.

솔루션들이 한 끌개로 강하게 빨려 들어가는 공간 구조를 ‘퍼넬’(funnel)이라 하는데 대부분의 단백질은 하나의 지배적 퍼넬을 가진 서열이어야 한다. 두개 이상의 경쟁적 퍼넬을 가진 서열이 있다면 세포의 상태에 따라 다른 3차원 구조를 갖는 단백질로 존재할 것이다. 문제공간의 속성상 이런 희귀한 서열도 분명히 존재할 것이다.

메커니즘 이해해도 결과 예측은 무리

제도나 관습이 고착된다는 것은 하나의 끌개로 귀착됐다는 말이다. 특정 제도나 관습이 마음에 들지 않는 사람은 이 끌개로부터 벗어나려고 시도한다. 오랫동안 고착된 강력한 끌개는 웬만큼 흔들어서는 흡인력을 잃지 않는다. 혁명이나 개혁은 다름 아닌 끌개로부터의 강력한 점프에 해당하는 것이다. 개인적 습관을 바꾸기 위해 단식을 하거나 머리를 깎는 것도 모두 끌개로부터 강력한 점프를 해보려는 무의식적인 노력인 것이다.

유전알고리즘에도 이런 속성이 포함되어 있다. 한번 형성된 끌개로부터 탈출하는 일은 쉽지 않지만, 문제 공간상의 임의의 점으로부터 이를 수 있는 끌개들은 무수히 많다. 이것으로 카오스이론에서 말하는 ‘나비효과’를 설명할 수 있고, 경제학의 결정론적인 예측 모델이 맞지 않는 이유를 설명할 수도 있다.

한 국가의 경제 시스템은 결코 단백질과 같이 하나의 모양으로 수렴하는 단순한 문제공간을 가질 수 없다. 임의의 위치에서 비슷한 매력을 가진 수많은 분기점이 존재하고, 일련의 선택을 통해 하나의 끌개로 이동하는 것이다. 그러니 이런 작동의 메커니즘을 설명하는 것은 가능해도 결과를 예측하기는 힘들다.

우리 사회의 현재 모습은 수없이 많은 안정적 가능성 중에 하나가 실현돼 있을 뿐이다. 미래를 예측한다는 것은 이런 측면에서 큰 한계를 갖는다. 마치 유전알고리즘이 어떤 끌개에서 탐색을 멈출지 예측하기 힘든 것처럼 말이다.