유전 알고리즘 구현해보기

기계 학습이라고 하면 대부분 신경망을 떠올린다. 데이터를 잔뜩 모아 정답을 알려주고, 틀린 만큼 가중치를 조금씩 고쳐나가는 방식 말이다. 그런데 이런 질문을 던져보자. 정답을 모르는 문제는 어떻게 학습시킬까? 정해진 트랙을 자동차가 안정적으로 도는 AI를 만들고 싶다고 해보자. 어느 순간에 핸들을 얼마나 꺾어야 하는지, 그 "정답 핸들값"을 우리는 모른다. 알았다면 애초에 AI가 필요하지도 않았을 것이다.

이럴 때 쓸 수 있는 접근이 하나 있다. 자연이 이미 40억 년 동안 써온 방법이다. 정답을 아무도 모르는 채로, 그저 잘 살아남은 것들이 자손을 남기고, 그 자손이 조금씩 달라지기를 반복하는 것. 우리는 이걸 진화라고 부르고, 이 원리를 컴퓨터로 흉내 낸 것을 유전 알고리즘^{Genetic Algorithm}이라고 부른다.

이 글에서는 유전 알고리즘이 어떤 원리로 동작하는지 바닥부터 살펴보고, 정해진 트랙을 도는 자동차 AI를 직접 만들어볼 것이다. 최대한 오래 살아남는 자동차를 진화로 찾아낼 것이다. 수학은 거의 나오지 않는다. 침착하게 따라오면 생각보다 간단하다. 본문의 예제 코드는 핵심만 추린 JavaScript이고, 이 글 안에 있는 데모들은 그 코드를 실제로 구현한 같은 엔진을 브라우저에서 돌린 것이다. 데모가 곧 살아 움직이는 예제다.

정답을 모르는 문제

먼저 우리가 풀려는 문제가 왜 특이한지부터 짚어보자.

흔히 접하는 지도 학습^{Supervised learning}은 정답표가 있는 문제다. 고양이 사진 1만 장에 "고양이"라는 꼬리표를 붙여두고, 모델이 틀리면 정답과 얼마나 다른지를 계산해 그만큼 가중치를 되돌린다. 이 "정답과의 차이"가 있어야 어느 방향으로 고쳐야 할지 알 수 있다.

그런데 자동차 트랙 문제에는 이 정답표가 없다. 지금 이 순간 핸들을 왼쪽으로 15도 꺾는 게 옳은지 아닌지, 누구도 라벨을 붙여줄 수 없다. 우리가 아는 건 딱 하나다. 결과가 좋았는지 나빴는지. 자동차가 트랙을 벗어나 멈췄다면 나빴던 것이고, 오래 달렸다면 좋았던 것이다. 하지만 "오래 달렸다"는 건 수천 번의 핸들 조작이 모두 끝난 뒤에야 알 수 있는 결과다. 그 수천 번 중 어느 조작이 잘했고 어느 조작이 못했는지는 알려주지 않는다.

이렇게 행동 하나하나의 정답은 모르지만, 전체 결과의 좋고 나쁨은 점수로 매길 수 있는 문제를 다룰 때 유전 알고리즘이 빛을 발한다. 게임 AI, 안테나 형상 설계, 물류 경로 최적화, 로봇 걸음걸이 학습 같은 곳에서 실제로 쓰인다.¹ 공통점은 "좋은 답이 뭔지는 몰라도, 답을 하나 던져주면 그게 얼마나 좋은지는 채점할 수 있다"는 것이다.

유전 알고리즘의 발상은 여기서 출발한다. 정답을 모르면, 무작위로 잔뜩 만들어놓고 채점해서 좋은 것들을 골라 섞자. 그리고 이걸 수십 번 반복하자. 무식해 보이지만, 자연이 이 무식한 방법으로 눈과 날개와 뇌를 만들어냈다.

진화를 흉내 내는 다섯 단계

생물의 진화를 알고리즘으로 옮기면 다섯 개의 단계로 정리된다. 이 다섯 개가 이 글의 전부라고 해도 좋다.

• 개체군^Population: 후보 해답 여러 개를 무작위로 만든다. 한 마리 한 마리가 하나의 후보다.
• 평가^Evaluation: 각 개체가 얼마나 좋은지 점수를 매긴다. 이 점수를 적합도^Fitness라고 부른다.
• 선택^Selection: 점수가 높은 개체가 자손을 남길 확률이 높게 부모를 고른다.
• 교차^Crossover: 두 부모의 유전자를 섞어 자식을 만든다.
• 변이^Mutation: 자식의 유전자를 아주 조금 무작위로 바꾼다.

그리고 이렇게 만든 자식 세대로 부모 세대를 대치^Replacement하고, 다시 평가부터 반복한다. 한 바퀴 돌 때마다 세대^Generation가 하나 넘어간다.

말로만 보면 추상적이니 우리 문제에 대입해보자. "개체"는 자동차 한 대의 두뇌다. "적합도"는 그 자동차가 트랙에서 살아남은 시간이다. 처음엔 무작위 두뇌를 가진 자동차 수십 대가 대부분 즉시 벽에 처박히겠지만, 그중 조금이라도 오래 버틴 녀석들을 골라 섞고 조금 바꾸기를 반복하면, 놀랍게도 몇십 세대 만에 트랙을 완주하는 자동차가 나타난다. 직접 보자.

위 데모는 이 글에서 만들 유전 알고리즘을 실제로 돌린 것이다. 처음엔 자동차들이 우왕좌왕하다 대부분 벽에 부딪혀 사라지지만, 세대가 넘어갈수록 살아남는 자동차가 늘어나고, 결국 트랙을 도는 개체가 나온다. 리셋 버튼으로 무작위 0세대부터 다시 볼 수 있고, 개체들이 오래 버티기 시작해 한 세대가 길어지면 배속 버튼으로 빨리감기 하면 된다. 이 장면 하나에 방금 말한 다섯 단계가 전부 담겨 있다. 이제 각 단계를 하나씩 뜯어보자.

개체를 무엇으로 표현할 것인가

가장 먼저 정할 것은 개체 하나를 무엇으로 표현할 것인가다. 유전 알고리즘에서 개체는 곧 유전자^Genome이고, 유전자는 보통 숫자의 나열이다. 생물의 DNA가 A·T·G·C 네 글자의 나열인 것처럼, 우리의 유전자는 실수의 나열이 될 것이다. 이 표현을 어떻게 정하느냐가 사실 유전 알고리즘 설계에서 가장 창의력이 필요한 부분이다.

자동차의 두뇌 설계

자동차는 매 순간 두 가지를 한다. 주변을 감지하고, 핸들을 꺾는다. 속도는 일정하게 고정하고² 오직 조향만 학습시키기로 하자. 그러면 자동차의 두뇌는 이런 함수다.

주변 감지값 → (어떤 계산) → 핸들을 얼마나 꺾을지

주변을 어떻게 감지할까? 자동차 앞쪽으로 부채살처럼 다섯 개의 감지선(레이)을 쏜다. 정면, 좌우 45도, 좌우 90도. 각 선이 벽에 닿기까지의 거리를 재면, 자동차는 "왼쪽 벽이 가깝다", "앞이 뚫려 있다" 같은 정보를 5개의 숫자로 얻는다.

이 5개의 거리값을 입력받아 핸들값 하나를 뱉는 계산기가 바로 두뇌다. 계산기로는 아주 작은 신경망을 쓴다. 신경망이라는 말에 겁먹을 필요 없다. 여기서 신경망은 그냥 입력 숫자들에 가중치를 곱하고 더해서 출력을 내는 함수일 뿐이다. 우리가 만들 신경망은 이렇게 생겼다.

• 입력층: 5개 (감지선 거리)
• 은닉층: 6개 (중간 계산 노드)
• 출력층: 1개 (핸들값, -1이면 좌회전 최대, +1이면 우회전 최대)

각 연결마다 가중치라는 숫자가 하나씩 붙는다. 입력 5개와 은닉 6개를 잇는 가중치가 30개, 은닉층의 편향 6개, 은닉 6개와 출력 1개를 잇는 가중치 6개, 출력의 편향 1개. 다 더하면 43개의 숫자다. 바로 이 43개의 숫자 뭉치가 자동차 한 대의 유전자다. 편향^bias은 입력이 전부 0이어도 노드가 기본적으로 갖는 출력 성향을 조절하는 값인데, 지금은 "가중치와 함께 진화로 찾아야 할 숫자가 몇 개 더 있다" 정도로만 알아도 충분하다.

// 유전자는 그냥 43개의 실수 배열이다
const N_IN = 5; // 입력: 감지선 5개
const N_HID = 6; // 은닉 노드 6개
const GENOME_LEN = N_IN * N_HID + N_HID + N_HID + 1; // 30 + 6 + 6 + 1 = 43

// 무작위 유전자 하나 만들기 (-1 ~ 1 사이 난수 43개)
function randomGenome(rand) {
  const g = new Float32Array(GENOME_LEN);
  for (let i = 0; i < GENOME_LEN; i++) g[i] = rand() * 2 - 1;
  return g;
}

유전자만 있으면 두뇌가 완성된다. 43개 숫자를 신경망의 가중치 자리에 그대로 꽂아 넣고, 감지선 5개를 입력하면 핸들값이 나온다.

// 유전자(가중치 43개)를 신경망에 꽂아 핸들값을 계산한다
// 유전자 배치: [입력→은닉 가중치 30, 은닉 편향 6, 은닉→출력 가중치 6, 출력 편향 1]
function forward(genome, sensors, hid) {
  let g = 0;
  // 입력 5개 → 은닉 6개
  for (let h = 0; h < N_HID; h++) {
    let sum = 0;
    for (let i = 0; i < N_IN; i++) sum += genome[g++] * sensors[i];
    hid[h] = sum;
  }
  // 은닉 노드에 편향을 더하고 tanh로 눌러준다 (-1 ~ 1로)
  for (let h = 0; h < N_HID; h++) hid[h] = Math.tanh(hid[h] + genome[g++]);
  // 은닉 6개 → 출력 1개
  let out = 0;
  for (let h = 0; h < N_HID; h++) out += genome[g++] * hid[h];
  return Math.tanh(out + genome[g++]); // -1(좌회전) ~ +1(우회전)
}

tanh는 어떤 숫자든 -1과 1 사이로 눌러주는 함수다. 핸들값이 -1과 1 사이여야 하니 마지막에 한 번 눌러주는 것이고, 은닉층에 쓴 것은 신경망이 단순한 직선 이상의 판단을 하게 해주는 장치다.³ 지금은 "숫자를 -1~1 범위로 부드럽게 구부려주는 함수" 정도로 이해하면 충분하다.

여기서 중요한 발상 전환이 하나 있다. 우리는 이 가중치들을 학습으로 구할 생각이 없다. 신경망을 안다면 보통 경사하강법으로 가중치를 조금씩 고쳐나가는 걸 떠올리겠지만, 그러려면 "정답 핸들값"이 필요하고 우리에겐 그게 없다. 대신 우리는 이 43개 숫자를 진화로 찾을 것이다. 신경망은 그저 유전자를 행동으로 번역해주는 통역사일 뿐, 학습의 주체가 아니다.

평가: 살아남은 시간이 곧 점수

개체를 표현했으니 이제 점수를 매겨야 한다. 우리의 목표는 "최대한 오래 살아남는 자동차"이므로, 적합도는 단순하다. 트랙 위에서 버틴 프레임 수. 매 프레임 감지하고, 핸들을 꺾고, 조금 전진한다. 트랙을 벗어나는 순간 죽고, 그때까지 버틴 프레임 수가 그 개체의 점수가 된다.

// 자동차 한 대를 트랙에서 굴려보고 살아남은 프레임 수를 잰다
function evaluate(track, genome, maxFrames) {
  const car = spawnCar(track, genome); // 출발선에 세운다
  for (let f = 0; f < maxFrames; f++) {
    senseRays(track, car); // 감지선 5개로 벽까지 거리 측정
    const steer = forward(genome, car.sensors, car.hid); // 두뇌가 핸들 결정
    car.heading += steer * MAX_TURN * DT; // 핸들만큼 방향 전환
    car.x += Math.cos(car.heading) * SPEED * DT; // 전진
    car.y += Math.sin(car.heading) * SPEED * DT;
    if (!track.inside(car.x, car.y)) return f; // 벽 밖이면 죽음, 여기까지가 점수
  }
  return maxFrames; // 끝까지 살아남으면 만점
}

maxFrames로 상한을 둔 이유는, 트랙을 완벽하게 도는 자동차는 사실상 죽지 않기 때문이다. 이 세계는 난수가 없는 결정적 시뮬레이션이고 트랙의 코너 종류는 유한하다. 어떤 개체가 모든 코너를 통과했다면 다음 바퀴에서도 같은 코너를 거의 같은 방식으로 넘는다. 그래서 개체의 생존 시간은 양극단으로 갈린다. 자기가 처리 못 하는 코너를 만나 몇 초 안에 죽거나, 그런 코너가 없어서 계속 돌거나. 무한히 기다릴 수는 없으니 30초(1,800프레임)를 버티면 만점으로 치고 멈춘다. 우리 트랙은 오른쪽에 급하게 꺾어 들어가는 헤어핀과 아래쪽에 S자 시케인이 있는 한 바퀴 약 2,195픽셀짜리 난코스인데, 자동차 속도로 30초면 약 1.9바퀴다. 만점을 받았다는 건 헤어핀과 시케인을 두 번씩 통과할 만큼 안정적으로 돈다는 뜻이다.

여기서 적합도 설계의 미묘함을 하나 짚고 넘어가자. 왜 "달린 거리"가 아니라 "살아남은 시간"을 점수로 했을까? 속도가 고정이라 사실 둘은 비례하지만, 만약 속도까지 학습시켰다면 이야기가 달라진다. "거리"로 점수를 주면 직진으로 벽에 빠르게 돌진하는 자동차가 코너를 조심조심 도는 자동차보다 높은 점수를 받는 사고가 난다. 짧고 빠르게 죽는 것이 길고 느리게 사는 것보다 유리해지는 것이다. 적합도 함수를 잘못 설계하면 진화는 우리가 원한 것이 아니라 우리가 점수를 준 것을 향해 최적화된다. 이건 유전 알고리즘에서 두고두고 발목을 잡는 함정이라 뒤에서 다시 이야기하겠다.

0세대는 얼마나 처참한가

이제 무작위 유전자로 첫 개체군을 만들어 채점해보자. 무작위 43개 숫자로 만든 두뇌가 얼마나 형편없는지 실제로 재봤다. 무작위 자동차 300마리를 트랙에 풀어 살아남은 시간을 측정한 결과다.

다섯 중 넷은 1초도 못 버티고 벽에 처박힌다. 무작위로 만든 두뇌란 이렇게 처참하다. 그런데 최고 기록 8.5초는 랜덤치고 길다고 느낄 수도 있다. 여기엔 설계가 깔아준 공짜 출발선이 있다. 자동차를 출발선에서 트랙 진행 방향을 보도록 세웠고, 속도는 항상 전진이며, 신경망 구조상 어떤 유전자든 매끄러운 조향을 하기 때문에, 아무 생각 없는 개체도 첫 코너까지는 도로를 따라간다. 문제를 풀 만하게 판을 까는 것까지가 설계자의 몫이고, 그 판 위의 탐색이 진화의 몫이다. 그리고 그 판 위에서도 대부분이 즉사하는 와중에, 순전히 운으로 남들보다 조금 나은 두뇌를 타고난 개체가 존재한다. 진화는 바로 이 "조금 나은 놈"을 물고 늘어지는 과정이다.

선택: 좋은 것이 자손을 남긴다

개체군을 채점했으니 이제 다음 세대의 부모를 골라야 한다. 자연에서는 잘 살아남은 개체가 자손을 남길 확률이 높다. 이것이 선택이다. 핵심은 "무조건 1등만 남긴다"가 아니라 **"점수가 높을수록 뽑힐 확률이 높다"**는 확률적 편향이다. 왜 1등만 남기면 안 되는지는 곧 드러난다.

선택 방식은 여러 가지가 있는데, 대표적인 두 가지를 보자.

룰렛 휠 선택

가장 직관적인 방법이다. 점수에 비례해 룰렛 판의 칸 크기를 정하고 돌리는 것이다. 점수가 100인 개체는 점수가 10인 개체보다 10배 넓은 칸을 차지하니, 10배 자주 뽑힌다. 이름 그대로 룰렛 휠 선택^{Roulette wheel selection}이다.

// 점수(fits)에 비례하는 확률로 개체 하나를 고른다
function rouletteSelect(pop, fits, rand) {
  let total = 0;
  for (const f of fits) total += f; // 전체 점수 합 = 룰렛 둘레
  let r = rand() * total; // 둘레 위의 무작위 지점
  for (let i = 0; i < pop.length; i++) {
    r -= fits[i]; // 각 개체의 칸을 지나가며
    if (r <= 0) return pop[i]; // 무작위 지점이 걸린 칸의 개체를 반환
  }
  return pop[pop.length - 1];
}

직관적이지만 약점이 있다. 어쩌다 한 개체의 점수가 다른 개체들을 압도하면(예: 혼자만 1,800점이고 나머지는 50점) 룰렛 판을 그 개체가 거의 다 차지해서, 매번 그 개체만 뽑히게 된다. 다양성이 순식간에 무너진다. 반대로 모두의 점수가 고만고만하면 선택압^{Selection pressure}, 즉 "잘난 놈을 골라내는 힘"이 약해져서 무작위 선택과 다를 게 없어진다.

토너먼트 선택

그래서 실무에서 더 자주 쓰는 방식이 토너먼트 선택^{Tournament selection}이다. 개체군에서 무작위로 몇 마리(예: 3마리)를 뽑아 그중 점수가 가장 높은 하나를 부모로 삼는다. 이걸 부모가 필요할 때마다 반복한다. 점수의 절대값이 아니라 순위만 보기 때문에 점수를 따로 정규화할 필요가 없고 구현도 단순해서, 개체군이 크거나 적합도 범위가 들쭉날쭉한 실무 문제에서 특히 손이 덜 간다.

// 무작위 k마리를 뽑아 그중 최고를 부모로 삼는다
function tournamentSelect(pop, fits, k, rand) {
  let best = -1;
  for (let i = 0; i < k; i++) {
    const c = Math.floor(rand() * pop.length); // 무작위 도전자
    if (best < 0 || fits[c] > fits[best]) best = c;
  }
  return pop[best];
}

토너먼트의 장점은 선택압을 손잡이 하나로 조절할 수 있다는 것이다. 이 손잡이가 토너먼트 크기 k다. k가 크면 매번 넓은 후보 중 최고를 뽑으니 강한 개체가 부모가 될 확률이 높아진다(강한 선택압). k가 작으면 약한 개체도 운 좋게 부모가 될 수 있다(약한 선택압). 그리고 점수의 절대값이 아니라 순위만 보기 때문에, 룰렛처럼 한 개체가 점수로 판을 독식하는 사고가 없다.

선택압이 없으면 진화도 없다

선택이 정말 필요한지 실험으로 확인해보자. 선택을 아예 무작위로 바꿔서(점수와 무관하게 부모를 뽑는다) 다른 조건은 그대로 두고 진화시켜봤다.

무작위 선택은 30세대가 지나도 평균 111점, 약 2초 수준에 머문다. 첫 만점 개체조차 8번 중 3번은 45세대 안에 나오지 못했고, 나와도 엘리트 보존이 우연히 건져 올린 것일 뿐 개체군 전체는 끝까지 엉망이다. 반면 선택압이 있는 방식들은 개체군 절반이 만점(30초 완주)에 도달한다. 점수를 보고 부모를 고르는 것, 이 하나가 진화의 엔진이다. 선택이 없으면 아무리 교차와 변이를 해도 개선이 축적되지 않는다. 좋은 유전자가 다음 세대에 더 많이 전달되어야 개선이 쌓이는데, 무작위 선택은 그 축적을 끊어버리기 때문이다.

토너먼트 k=7이 k=3보다 빨리 수렴하는 것도 보인다. 선택압이 셀수록 초반 수렴은 빠르다. 다만 항상 센 게 좋은 건 아니다. 선택압이 너무 세면 초반에 우연히 잘난 개체 하나에게 개체군 전체가 쏠려버려서, 더 나은 가능성을 탐색하기도 전에 다양성이 고갈된다. 이걸 조기 수렴^{Premature convergence}이라고 부르는데, 유전 알고리즘의 가장 흔한 실패다.

교차: 두 부모의 유전자를 섞는다

부모 둘을 골랐으니 이제 자식을 만들 차례다. 교차는 두 부모의 유전자를 섞어 새로운 유전자를 만드는 연산이다. 생물의 유성생식에서 아버지와 어머니의 염색체가 섞이는 것과 같은 발상이다.

우리 유전자는 43개 숫자 배열이니, 섞는 방법도 배열을 어떻게 자르고 붙이느냐의 문제다. 두 가지가 대표적이다.

한 점 교차^{One-point crossover}는 배열의 한 지점을 무작위로 정해, 그 앞은 부모 A에서, 뒤는 부모 B에서 가져온다.

function crossoverOnePoint(a, b, rand) {
  const c = new Float32Array(GENOME_LEN);
  const p = 1 + Math.floor(rand() * (GENOME_LEN - 1)); // 자를 지점
  for (let i = 0; i < GENOME_LEN; i++) c[i] = i < p ? a[i] : b[i];
  return c;
}

균등 교차^{Uniform crossover}는 각 자리마다 동전을 던져 A에서 올지 B에서 올지 정한다.

function crossoverUniform(a, b, rand) {
  const c = new Float32Array(GENOME_LEN);
  for (let i = 0; i < GENOME_LEN; i++) c[i] = rand() < 0.5 ? a[i] : b[i]; // 자리마다 동전
  return c;
}

교차의 취지는 좋은 조각들의 조합이다. 부모 A는 우회전 코너를 잘 돌고 부모 B는 좌회전 코너를 잘 돈다면, 둘을 섞은 자식은 양쪽 다 잘 도는 두뇌를 물려받을 수 있다. 서로 다른 개체가 각자 발견한 좋은 특성을 한데 모으는 것, 이것이 교차가 노리는 바다.

교차가 정말 도움이 될까

솔직히 말하면, 교차는 유전 알고리즘에서 가장 논쟁적인 연산이다. 신경망 가중치처럼 숫자들이 서로 얽혀 의미를 만드는 유전자에서는, 두 부모의 절반씩을 잘라 붙인 자식이 부모보다 나으리란 보장이 전혀 없다. 잘 돌던 두뇌 둘을 반씩 섞었더니 아예 못 도는 자식이 나오기도 한다.⁴ 실제로 재봤다.

흥미롭게도 우리 문제에서는 교차를 아예 빼도 뒤처지지 않았다. 부모를 복제해서 변이만 주는 쪽이 균등 교차와 대등하거나 오히려 조금 빨랐고, 한 점 교차는 확실히 느렸다. 신경망 가중치 최적화에서는 드물지 않은 결과다. 그렇다고 교차가 쓸모없다는 뜻은 아니다. 유전자의 각 부분이 독립적인 의미를 갖는 문제(예: 배낭 문제에서 어떤 물건을 담을지의 0/1 선택)에서는 교차가 위력을 발휘한다. 어떤 연산이 좋은지는 문제에 따라 다르다. 유전 알고리즘에 정답 설정 같은 건 없고, 문제에 맞춰 실험으로 찾아야 한다는 걸 보여주는 좋은 사례다. 이 글의 데모는 교차라는 개념을 온전히 보여주기 위해 균등 교차를 그대로 쓰지만, 방금 본 것처럼 이 문제에서 진화를 실제로 끌고 가는 주역은 다음 장의 변이다.

변이: 다양성을 지키는 안전장치

여기서 교차의 근본적인 한계를 하나 짚어야 한다. 교차만으로는 새로운 유전자가 생기지 않는다. 교차는 어디까지나 이미 개체군에 있는 숫자들을 재조합할 뿐이다. 만약 개체군 전체가 특정 자리에 0.5라는 값만 갖고 있다면, 아무리 섞어도 그 자리는 영원히 0.5다. 진화가 탐험할 수 있는 범위가 초기 개체군에 갇혀버린다.

변이는 이 벽을 뚫는다. 자식 유전자의 각 자리를 낮은 확률로 무작위로 살짝 바꾼다. 우리는 가우시안 노이즈, 즉 종 모양 분포의 작은 난수를 더하는 방식을 쓴다.

// 각 유전자 자리를 rate 확률로 살짝 흔든다
function mutate(genome, rate, sigma, rand) {
  for (let i = 0; i < GENOME_LEN; i++) {
    if (rand() < rate) genome[i] += gaussian(rand) * sigma; // 작은 난수를 더한다
  }
}

rate는 각 자리가 변이될 확률(예: 0.1이면 자리마다 10% 확률), sigma는 흔드는 세기다. 변이는 교차가 도달할 수 없는 완전히 새로운 유전자값을 개체군에 공급한다. 자연에서 방사선이나 복제 오류가 새로운 형질을 만들어내는 것과 같은 역할이다.

변이가 없으면 벌어지는 일

변이의 진짜 중요성은 없애봐야 드러난다. 다른 조건은 전부 그대로 두고 변이율만 바꿔가며, 60마리 개체군을 45세대씩 8번 돌려봤다.

결과가 극단적이다. 변이가 없으면(0.02처럼 거의 없어도) 45세대 동안 단 한 번도 완주 개체가 나오지 않았다. 개체군 평균은 500점 언저리, 약 8초 수준에서 영원히 정체된다. 헤어핀 앞까지는 가는데 그걸 넘는 유전자 조합이 개체군 안에 없고, 새로 생길 방법도 없는 것이다.

왜 이렇게 되는지는 개체군의 유전자 다양성을 재보면 보인다. 개체군 전체 유전자의 표준편차(값이 얼마나 퍼져 있는지)를 세대별로 추적한 결과다.

변이가 없으면 다양성이 세대를 거치며 계속 쪼그라든다. 선택과 교차는 기존 유전자를 고르고 섞을 뿐 새 값을 만들지 않기 때문에, 세대가 지날수록 개체군은 몇몇 조상의 유전자로 수렴해간다. 결국 모두가 비슷비슷해지면 교차를 해도 자식이 부모와 똑같아서, 진화는 그 자리에 멈춘다. 지금 갖고 있는 유전자로 만들 수 있는 최선에 갇히는 것이다. 이게 앞서 말한 조기 수렴이고, 위 표의 "8번 모두 실패"가 조기 수렴의 실제 얼굴이다. 변이 0.1은 다양성을 32세대까지 0.5 안팎으로 유지하면서 개체군이 한 점으로 붕괴하지 않게 붙잡아준다.

개체군 크기도 같은 원리로 움직인다. 개체군을 16마리로 줄이면 초기 다양성 자체가 얕아져서, 변이 0.1을 줘도 12번 중 5번만 60세대 안에 완주에 성공했다(변이 0은 12번 전부 실패). 다양성의 원천은 두 곳, 넉넉한 초기 개체군과 변이뿐이다.

변이는 세면 셀수록 좋을까

위 표에는 반전이 하나 더 있다. 변이율 0.3과 0.8이 0.1보다 첫 만점을 더 빨리 찾았다(11세대, 10세대 vs 23세대). 흔히 변이가 너무 세면 애써 찾은 좋은 유전자를 매번 망가뜨려서 해롭다고 설명하는데, 왜 여기서는 벌금이 안 보일까?

안전망 덕분이다. 우리 구성에는 엘리트 보존(다음 장에서 설명한다)이 있어서 최고 개체 2마리는 변이를 면제받는다. 챔피언이 금고에 안전하게 보관되어 있으니, 나머지 58마리는 아무리 과감하게 도박해도 잃을 것이 없다. 어려운 트랙일수록 넓게 탐험하는 쪽이 유리하니 높은 변이율이 첫 발견을 앞당긴 것이다. 대신 개체군 전체가 만점에 안착하는 속도(절반 만점)는 0.8이 되레 0.3보다 늦다. 찾기는 빨라져도 찾은 것을 개체군에 퍼뜨려 정착시키는 일은 큰 변이가 계속 방해하기 때문이다. 그리고 이 안전망을 치우는 순간 높은 변이율의 청구서가 날아오는데, 그건 다음 장에서 실험으로 보인다.

정리하면, 변이는 탐험^Exploration과 활용^Exploitation 사이의 저울이다. 변이가 크면 미지의 영역을 넓게 탐험하지만 찾은 것을 지키지 못하고, 변이가 작으면 찾은 것을 갈고닦지만 새로운 가능성을 놓친다. 어느 쪽이 유리한지는 문제의 난이도와 나머지 구성(엘리트, 개체군 크기)에 따라 달라져서, 결국 실험으로 맞춰야 한다. 우리 문제에서는 0.1~0.3 언저리가 무난했다.

대치: 세대를 넘긴다

선택·교차·변이로 자식들을 충분히 만들었으면, 이제 이 자식 세대로 부모 세대를 갈아치운다. 이것이 대치다. 가장 단순하게는 부모 세대를 통째로 버리고 자식 세대로 교체하면 된다. 이걸 세대 대치^{Generational replacement}라고 한다. 반대로 매 세대 개체군 전체를 갈아치우지 않고 자식 한두 마리만 만들어 가장 약한 개체와 교체하는 방식도 있는데, 이건 정상상태 대치^{Steady-state replacement}라고 부른다. 우리는 구현이 단순한 세대 대치를 쓴다.

그런데 여기에 함정이 하나 있다. 부모 세대에 트랙을 완주하는 챔피언이 있었다고 하자. 그런데 선택은 확률적이라 이 챔피언이 부모로 뽑히지 않을 수도 있고, 뽑혀서 자식을 만들어도 교차와 변이로 그 좋은 유전자가 망가질 수 있다. 그러면 애써 찾은 최고 기록이 다음 세대에서 사라진다. 진화가 뒷걸음질 치는 것이다.

이걸 막는 장치가 엘리트 보존^Elitism이다. 각 세대에서 점수가 가장 높은 개체 몇 마리는 아무 변형 없이 그대로 다음 세대로 복사한다. 챔피언에게만은 확률의 심판을 면제해주는 것이다.

// 평가가 끝난 개체군으로 다음 세대를 만든다 (대치)
function nextGeneration(pop, fits, opts, rand) {
  const idx = fits.map((_, i) => i).sort((a, b) => fits[b] - fits[a]); // 점수 내림차순 정렬
  const next = [];

  // 엘리트 보존: 상위 몇 마리는 변형 없이 그대로 다음 세대로
  for (let e = 0; e < opts.elitism; e++) next.push(pop[idx[e]]);

  // 나머지는 선택 → 교차 → 변이로 채운다
  while (next.length < opts.popSize) {
    const p1 = tournamentSelect(pop, fits, opts.tournamentK, rand);
    const p2 = tournamentSelect(pop, fits, opts.tournamentK, rand);
    const child = crossoverUniform(p1, p2, rand);
    mutate(child, opts.mutRate, opts.mutSigma, rand);
    next.push(child);
  }
  return next;
}

엘리트 보존이 있고 없고의 차이

엘리트 보존의 효과는 변이가 셀 때 극명하게 드러난다. 앞 장에서 예고한 청구서가 여기 있다. 변이율을 0.4로 높여(일부러 좋은 유전자가 잘 망가지게) 엘리트 유무를 비교했다. "후퇴"는 세대 최고 기록이 직전 세대보다 낮아진 횟수다.

엘리트가 없으면 최고 기록이 스물다섯 번이나 뒷걸음질 쳤다. 어렵게 찾은 좋은 두뇌가 변이에 파괴되어 사라진 것이다. 앞 장에서 높은 변이율이 공짜처럼 보였던 건 순전히 엘리트라는 금고 덕분이었고, 금고를 치우면 이렇게 성과가 줄줄 샌다. 엘리트 보존이 있으면 최고 기록은 절대 떨어지지 않는다(0회). 진화가 앞으로만 가도록 래칫(한 방향으로만 도는 톱니바퀴)을 걸어주는 셈이다.

재미있는 점은 엘리트가 있는 쪽이 평균 적합도는 오히려 살짝 낮다는 것이다. 엘리트를 너무 많이 보존하면(예: 개체군의 절반) 그 소수의 유전자가 개체군을 지배해 다양성이 줄고 조기 수렴 위험이 커진다. 그래서 보통 엘리트는 개체군의 1~5% 정도, 아주 소수만 남긴다. 우리는 60마리 중 2마리만 엘리트로 뒀다.

전체를 하나로 잇기

이제 다섯 조각이 다 모였다. 하나의 진화 루프로 이어보자. 놀랄 만큼 짧다.

function evolve(track, opts) {
  const rand = mulberry32(opts.seed);
  // 1. 개체군: 무작위 유전자 popSize개
  let pop = Array.from({ length: opts.popSize }, () => randomGenome(rand));

  for (let gen = 0; gen < opts.generations; gen++) {
    // 2. 평가: 각 개체를 트랙에서 굴려 살아남은 프레임 수를 잰다
    const fits = pop.map((g) => evaluate(track, g, opts.maxFrames));

    // 3~6. 선택·교차·변이·대치로 다음 세대를 만든다
    pop = nextGeneration(pop, fits, opts, rand);
  }
  return pop;
}

바깥 루프가 세대를 돌리고, 안에서 평가하고, nextGeneration이 선택·교차·변이·대치를 담당한다. 이게 유전 알고리즘의 전부다. 수백 줄의 미분도, 역전파도 없다. 그저 채점하고, 좋은 것을 골라 섞고, 조금 흔들기를 반복할 뿐이다.

이 루프를 우리 자동차 문제에 60마리 개체군으로 돌리면, 10개의 서로 다른 무작위 시작점(시드) 모두에서 트랙을 완주하는 자동차가 나왔다. 첫 완주 개체가 등장하는 시점은 중앙값 22세대, 평가 횟수로 치면 1,300여 마리다.

이 숫자의 무게는 무작위 탐색과 비교해야 보인다. 순전히 운으로 무작위 두뇌를 계속 뽑으면 어떻게 될까. 시드 5개에서 각각 20만 마리씩, 총 100만 개의 무작위 두뇌를 뽑아 채점했지만 완주 개체는 단 한 마리도 나오지 않았다.⁵ 유전 알고리즘이 1,300여 회 평가로 해내는 일을 무작위 탐색은 20만 회로도 못 한 것이다. 무작위로 헤매는 대신 좋은 방향으로 탐색을 집중시키기 때문이다. 반 바퀴 가는 개체를 발판 삼아 헤어핀을 넘는 개체를 만들고, 그걸 발판 삼아 시케인까지 넘는 식으로, 앞 세대의 성과 위에 다음 세대를 쌓는다. 이 축적이 바로 선택·교차·변이가 만들어내는 힘이다.

완성된 챔피언

마지막으로, 위 루프가 진화시킨 챔피언을 보자. 60세대 진화 중 23세대에 나타난 개체로, 이 자동차의 두뇌(43개 숫자)를 그대로 데모에 넣었다. 재평가에서 5분(18,000프레임) 동안 단 한 번도 트랙을 벗어나지 않고 19바퀴를 돌았다. 참고로 만점(30초)을 받은 개체라고 전부 이렇게 오래 버티는 건 아니다. 바퀴마다 궤적이 미세하게 어긋나기 때문에 수십 바퀴 뒤에 실수하는 개체도 있는데, 이 챔피언은 5분 재평가까지 통과한 놈이다.

이 자동차에게 우리는 코너를 어떻게 돌지 단 한 줄도 알려주지 않았다. "왼쪽 벽이 가까우면 오른쪽으로 꺾어라" 같은 규칙도 없다. 오직 오래 살아남은 놈이 자손을 남긴다는 규칙 하나를, 무작위로 시작한 개체군에 스물몇 세대 반복했을 뿐이다. 그런데 그 결과로 나온 두뇌는 트랙의 모든 코너를 부드럽게 돈다. 43개의 숫자 안에 "이 트랙을 도는 법"이 새겨진 셈이다. 그 숫자 하나하나가 무슨 뜻인지는 아무도 설명하지 못하는데도 말이다.

유전 알고리즘의 한계

여기까지 오면 유전 알고리즘이 만능처럼 보일 수 있으니, 균형을 위해 한계도 짚어두자.

첫째, 느리다. 매 세대 모든 개체를 평가해야 하는데, 우리 문제처럼 개체 하나 평가에 시뮬레이션을 30초씩 돌려야 한다면 비용이 만만치 않다. 경사하강법이 쓸 수 있는 문제라면 대개 그쪽이 훨씬 빠르다. 유전 알고리즘은 미분이 불가능하거나 정답이 없어서 다른 방법을 못 쓸 때 꺼내는 카드다.

둘째, 적합도 함수 설계가 전부다. 앞에서 속도까지 학습시킬 경우 "거리로 점수를 주면 벽에 빠르게 돌진하는 자동차가 이긴다"고 했던 그 함정이다. 진화는 우리가 의도한 목표가 아니라 우리가 실제로 점수를 준 것을 향해 최적화된다. 점수 함수에 허점이 있으면 진화는 기어코 그 허점을 파고든다. "청소 로봇에게 먼지를 감지하지 않을수록 점수를 줬더니 눈을 감아버렸다"는 식의 사고가 이 바닥엔 널렸다.⁶

셋째, 하이퍼파라미터가 많다. 개체군 크기, 변이율, 변이 세기, 토너먼트 크기, 엘리트 수. 이 손잡이들의 좋은 조합은 문제마다 다르고, 이 글에서 본 것처럼 대부분 실험으로 찾아야 한다. 이론적으로 최적값을 계산하는 깔끔한 공식 같은 건 없다.

그럼에도 유전 알고리즘이 매력적인 이유는, 문제에 대해 거의 아무것도 몰라도 시작할 수 있다는 점이다. 미분 가능성도, 정답 데이터도, 문제 구조에 대한 통찰도 필요 없다. "답을 하나 주면 채점은 할 수 있다"는 것만으로 충분하다. 그 최소한의 조건에서 출발해, 무작위에서 시작한 개체군이 스스로 트랙을 도는 법을 찾아내는 과정은, 여러 번 봐도 신기하다.

마치며

유전 알고리즘의 다섯 조각을 다시 늘어놓아 보자. 개체군을 만들고, 채점하고, 좋은 것을 골라(선택), 섞고(교차), 조금 흔들고(변이), 세대를 넘긴다(대치). 이 단순한 반복이 정답 없는 문제를 푼다는 것이 이 알고리즘의 아름다움이다.

각 조각이 왜 필요한지도 실험으로 확인했다. 선택이 없으면 개선이 축적되지 않고, 변이가 없으면 다양성이 고갈되어 조기 수렴하며, 엘리트 보존이 없으면 애써 찾은 챔피언이 사라진다. 그리고 이 조각들의 균형(선택압, 변이율, 엘리트 수)을 어떻게 맞추느냐가 진화의 속도와 성패를 가른다.

무엇보다, 우리는 자동차에게 운전을 가르치지 않았다. 그저 오래 살아남는 놈이 이긴다는 규칙만 세워두고 진화가 알아서 답을 찾게 했다. 정답을 모르는 채로도 좋은 답을 길러낼 수 있다는 것, 그것이 40억 년 된 이 방법이 여전히 쓸모 있는 이유다.

이 글의 전체 코드는 GitHub 저장소에서 볼 수 있다.