d라이브러리

난 다윈. 진화의 원리를 발견한 사람이지. 내가 처음에 진화론을 주장할 때는 ‘우리 할아버지가 원숭이냐?’라는 비아냥거림도 많이 받았는데, 요즘엔 대다수가 받아들이는 과학적 사실이 됐다더군. 게다가 요즘엔 내가 발견한 진화의 원리를 이용해 컴퓨터 프로그램도 만들고, 어려운 수학 문제도 척척 푼다며? 가상현실의 액션 배우도 만든다고 하니, 내가 발견한 원리인데도 너무 궁금해서 가만 있을 수가 없군. 유전 알고리즘이라고 하던데, 같이 한 번 살펴보겠나?

영화 속 등장인물도 진화한다고?

요즘엔 그림이 움직이는구먼. 상상도 하지 못했던 것이 현실이 됐군. 그런데 영화 속 인물이 가상의 세계에서 진화한 것이라고?

전쟁영화 속 한 장면을 생각해 보자. 수많은 사람들이 적진으로 뛰어가는 장면을 찍고 싶지만, 실제로 찍기 어려울 땐 컴퓨터 그래픽으로 만든 특수효과를 사용해야 한다. 하지만 일일이 모든 사람을 표현하긴 힘들다. 용감하게 돌진하거나, 총에 맞아 괴로워하는 사람 등 엄청나게 많은 사람들이 다른 상황에 처해 등장하기 때문이다. 일일이 한 명씩 그릴 수도 있겠지만, 시간과 비용이 많이 든다. 어떻게 해야 할까?

이런 어려움은 게임에도 있다. <;리니지>;나 <;월드오브워크래프트>; 같은 게임을 대규모 다중 사용자 온라인 롤플레잉 게임(MMORPG)라고 한다. 이런 게임에 적게는 수천, 많게는 수십 만 명의 사람들이 함께 온라인으로 접속해 즐긴다. 가상의 공간 속에 가상의 캐릭터를 만들어 적을 물리치기도 하고, 물건을 사고팔기도 한다.

게임 속 가상의 공간에는 사람들이 만든 캐릭터만 있는 것이 아니다. NPC라고 하는 가상의 캐릭터가 존재한다. NPC는 상인일 수도 있고, 동료나 적일 수도 있다. 게임 특성에 따라 이용자에게 임무를 부여하기도 하고, 동맹을 만들거나 아이템을 공짜로 주기도 한다. 또한 다른 이용자에게 피해를 입히는 이용자만 골라 죽이는 NPC도 있다. NPC는 게임을 즐기는 이용자들에게 도움이나 제약을 줘 게임의 재미를 높인다.

예전 게임 속의 NPC들은 단순한 패턴으로 움직였다. 그래서 이들의 패턴을 파악한 머리 좋은 게임 이용자들은 간단히 원하는 바를 얻기도 했다. 하지만 NPC의 단순한 행동은 게임의 재미를 떨어트렸다. 어떻게 하면 이를 해결할 수 있을까?

만약 게임 속 NPC나 영화 속 특수효과 속 등장인물이 인공지능을 가지면 어떨까? 일일이 그리지 않더라도 상황이 주어지면 사람처럼 알아서 움직이도록 만드는 것이다.

이런 인공지능을 만드는 데 다윈이 발견한 진화의 원리가 쓰인다. 생명이 여러 세대를 거치면서 진화하는 것처럼, 인공지능도 진화하게 만드는 것이다. 이것이 바로 진화의 원리를 이용한 유전 알고리즘이다.

적응한 자만이 살아남는 자연선택
 
진화의 원리를 이용한 유전 알고리즘에 대해 알려면, 먼저 진화에 대해 알아야겠지? 이건 내가 가장 잘 아니, 한 수 가르쳐 주지.

다윈은 비글호를 타고 갈라파고스 군도를 여행하던 중 진화의 원리를 발견했다. 이 곳의 섬들은 적당히 떨어져 있어 섬마다 독립적 생태계를 이루고 있었다. 다윈은 각 섬에 사는 동물들이 독자적으로 진화한 모습을 관찰했다.

대표적인 동물이 ‘핀치 새’였다. 섬마다 이 새들은 부리의 모양, 크기, 골격이 조금씩 달랐다. 가장 큰 차이는 부리였다. 섬에서 구할 수 있는 먹이에 따라 부리의 크기와 모양이 달라졌기 때문이다.

다윈은 이렇게 부리가 달라진 이유가 자연선택 때문이라고 설명했다. 처음에 핀치 새들은 딱딱한 먹이를 잘 먹는 부리, 벌레를 잘 먹는 부리, 열매의 속만 파먹는 부리 등 다양한 부리를 가지고 있었다. 이 중 섬에서 나는 먹이를 먹는 데 적당한 부리를 가진 새들이 살아남아 자식 새를 낳는다. 부리가 그대로 자식 새에게 전해지는 것이 아니라, 교배로 두 마리 새의 특징이 섞이기도 한다. 또 전혀 새로운 (돌연)변이가 나타나 유전되기도 한다.

자연선택설은 이처럼 자연계에서는 환경에 적합한 생물체는 계속 살아남고, 적합하지 않은 것은 사라진다는 학설이다. 자연선택설에 따르면 환경에 잘 적응한 생물체만이 자손을 남겨, 생존에 유리한 특성을 자손에게 전한다. 여러 세대를 거듭하면서 이런 특성이 점차 쌓이게 되
고, 결국에는 선조와 다른 특성을 가진 종으로 변한다.

진화를 이용한 유전 알고리즘

유전 알고리즘은 이런 진화의 원리를 이용해 인공지능을 만들거나, 풀기 어려운 문제의 근삿값을 구한다. 망치를 예로 유전 알고리즘을 설명해 보자.

먼저 아무렇게나 만든 망치를 모은다. 이 중 두 망치를 선택한 다음, 두 망치의 특징을 결합해 새로운 망치를 만든다. 이렇게 만들어진 망치를 약간 변형시킨다. 만들어진 망치들 중 사용하기 편리한 망치를 고른다. 이제 조금 나아진 망치 중 두 개를 선택해 다시 새로운 망치를 만들고, 변형시킨다. 이를 반복하다 보면 좋은 망치가 나온다.

이런 망치를 만드는 과정은 진화의 과정과 닮았다. 수많은 망치 중 두 개를 선택해 새로운 망치로 만드는 과정은 유전자의 ‘교차’를 의미한다. 만들어진 망치를 약간 변형시키는 것은 ‘변이’고, 사용하기 편한 망치를 고르는 것은 ‘자연선택’이다. 이는 생명의 진화와 비슷하다.

게임과 영화 속 캐릭터도 마찬가지다. 두 발로 걷는 사람을 만들기 위해 먼저 사람의 근육과 뼈를 본 뜬 가상의 모형 집단을 만든다. 그 중
둘을 골라 특징을 교차하고, 변이를 가한다. 이렇게 만든 모형 집단 중에서 좋은 것을 선택하고, 이 과정을 반복하면 처음에 제대로 못 걷던 모형은 세대를 거듭할수록 똑바로 걷기 시작한다.
 
오래 걸리는 계산도 척척!

듣고 보니 유전 알고리즘은 내가 발견한 진화를 많이 본땄군. 이걸로 수학 난제도 풀 수 있다고 하는데, 정말인가? 뭐? 난제뿐만 아니라 프로야구 일정도 짠다고?

유전 알고리즘은 아주 복잡한 계산 문제를 푸는 데도 유용하다. 계산문제는 문제의 난이도에 따라 P문제와 NP문제로 나뉜다. P는 계산하는 데 그리 오래 걸리지 않는 문제의 집합이고, NP는 아주 오랜 시간이 걸리는 문제의 집합이다. 외판원이 N개의 도시를 모두 한 번 씩 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제도 NP문제에 해당한다. 유전 알고리즘으로는 이런 NP문제의 대략적인 해를 구할 수 있다.

외판원 문제에서 각각의 경로는 하나의 답에 해당한다. 외판원 문제는 이들 중 가장 길이가 짧은 답을 찾아내야 한다. 이 문제를 풀려면 가능한 모든 경우를 다 계산한 다음, 최소거리를 여행하는 경로를 선택하면 된다. 방문해야 할 도시가 50개면, 방문할 수 있는 모든 경로의 수는 49!로, 약 6.08×10⁶⁸개나 돼 가장 짧은 경로를 찾기가 힘들다.
 
유전 알고리즘은 우선 몇 개의 가능한 해답을 구한 다음, 이 해답을 서로 교차시킨다. 그리고 변이를 일으킨다. 이렇게 생성된 해답 가운데 더 나은 답들을 선택해 다시 교차와 변이를 시키는 과정을 무수히 되풀이하면, 정답에 가까운 답을 얻을 수 있다.

이처럼 유전 알고리즘은 어려운 문제를 푸는 장점이 있지만, 일반적으로 쉽게 풀 수 있는 문제를 푸는 데는 별 매력이 없다. 유전 알고리즘으로 문제를 푸는 데는 많은 시간이 걸리는데, 쉬운 문제는 간단하게 문제를 푸는 빠른 알고리즘이 존재하기 때문이다.

또 유전 알고리즘으로 구한 값이 가장 좋은 값은 아니다. 어떤 값이 가장 좋은지 판별하기 어렵기 때문이다. 마치 빌딩 숲에서 모든 건물의 높이를 재지 않고, 가장 높은 건물을 찾는 것과 비슷하다. 그래서 유전 알고리즘으로 구한 해들은 정확한 답이 아니라 근삿값이다. 이런 점은 장점이기도 하다. 답에 근접한 다양한 해집합을 구할 수 있기 때문이다. 따라서 영화 속 가상 인물의 개성있는 다양한 움직임을 만들기에 적당하다.

유전 알고리즘의 다양한 응용

공평한 프로야구 일정 짜기

한국 프로야구단 롯데 자이언츠의 한 시즌 이동거리는 상당히 길다. 수도권에 네 팀이 옹기종기 모여 있는 것과 달리, 롯데는 연고지가 부산이어서 한반도의 한쪽 끝에 있기 때문이다. 그래서 늘 롯데 선수단은 오랜 시간 버스에 타고 다닐 수밖에 없어 체력을 관리하기가 쉽지 않다. 롯데뿐만 아니라 각 팀마다 일정에 따라 이런 저런 불만이 있다.
그래서 프로스포츠 리그의 일정을 짤 때는 이동거리와 팀당 상대 경기수 등의 까다로운 제약 조건을 만족해야 한다. 리그의 규모가 커질수록 어려워지는데, 유전 알고리즘을 이용하면 주어진 제약조건을 만족하는 답을 구할 수 있다. 실제론 이밖에도 다양한 방법으로 일정을 짠다.

효율적인 휴대전화 키패드 설계

휴대전화에서 문자를 보낼 때는 되도록 적게 누르면 좋다. 일반 키보드처럼 자음과 모음으로 나눠 문자를 쓰면 좋겠지만, 휴대전화의 키패드 개수는 제한돼 있다. 따라서 한 개의 자음과 모음을 찍기 위해 여러 번 눌러야 한다. 우리가 실제 사용하는 빈도에 따라 가장 효율적인 키패드를 만드는 것은 쉬운 일이 아니다. 모든 방법에 따라 일일이 대입해 계산하기가 어렵기 때문이다. 따라서 유전 알고리즘을 이용하면 빠른 시간 안에 가장 효율적인 키패드를 만들 수 있다.

인공 생명의 아름다움을 예술로 표현

유전 알고리즘을 이용해 예술 작품을 만들기도 한다. 이런 예술을 ‘진화예술’이라고 한다. 진화예술은 진화예술가가 초기에 여러 작품을 임의로 만들어 놓는 것에서 시작된다. 아름다움을 컴퓨터가 판단할 수 없으므로, 괜찮다고 생각하는 작품을 진화예술가가 선택하고 이를 교차하고 변형한다. 그 뒤 이를 컴퓨터로 무수히 반복한다. 그 결과 세대를 거듭하면서 점점 아름다운 작품이 만들어진다.

유전 알고리즘은 이밖에도 경제 현상 분석이나 금융공학, 반도체 등 계산하기 어려운 문제에서 쓰이고 있다는군. 내가 발견한 진화에서 수학적 원리를 찾아 이렇게 많이 쓰고 있다니 정말 놀라워. 생명의 원리까지 수학 안에 담다니, 정말 수학은 대단하구만!