유전 알고리즘 쉽게 이해하기 — 배낭 문제로 보는 선택·교차·돌연변이와 세대 진화 탐색 원리

핵심 메시지

• 유전 알고리즘은 진화 알고리즘의 한 종류로, 문제를 적절한 형태로 표현하면 생물의 진화를 흉내 내며 해답을 점점 진화시킨다.
• 예시인 배낭 문제는 정해진 무게 한계를 넘지 않으면서 담은 물건의 가치 합을 최대로 만드는 문제이며, 각 해답은 상자 포함 여부를 나타내는 0과 1의 비트열로 표현된다.
• 적합도 함수가 각 해답의 점수를 매기는데, 무게가 한계를 넘으면 0점을 줘 쓸모없는 해로 처리한다. 점수가 높은 해가 살아남아 퍼지는 적자생존 방식이다.
• 한 세대는 선택(토너먼트·룰렛휠) → 교차(부모 해의 정보를 섞어 자식 생성) → 돌연변이(낮은 확률로 비트를 뒤집음) 순으로 자식 해를 만들고, 개체 수만큼 채울 때까지 반복한다.
• 수백~수천 세대를 돌리면 평균·최고 적합도가 오르다 평탄해진다. 최적해를 보장하진 않지만 좋은 방향을 알려주는 탐색 알고리즘이며, 엘리트주의와 개체 수·교차율·돌연변이율 조정이 성능을 좌우한다.

쉽게 이해하기

유전 알고리즘은 '진화 알고리즘'이라 불리는 더 큰 범주에 속하는 기법이다. 문제를 특정한 방식으로 표현해 두면, 생물의 진화 과정을 흉내 내며 그 문제의 해답을 점점 발전시킬 수 있다. 직접 만들어 실험해 보기 쉽고 시각적이어서, 다른 방법으로는 풀기 어려운 문제에도 좋은 실마리를 준다는 것이 강연자의 설명이다.

예시로 든 것은 배낭 문제다. 배낭에 무게와 가치를 가진 상자들을 담되, 정해진 무게 한계를 넘지 않으면서 가치 합을 최대로 만드는 것이 목표다. 사막에서 보물 동굴에 들어가 배낭 하나에 가장 값진 것들만 골라 담는 상황에 비유할 수 있다. 영상에서는 상자 네 개와 무게 한계 15kg짜리 간단한 버전을 사용한다.

해답은 네 자리 비트열로 표현한다. 각 자리의 0 또는 1은 해당 상자를 배낭에 넣지 않음/넣음을 뜻한다. 예를 들어 무게 합이 한계 안이면 담긴 상자들의 가치를 더해 점수를 주고, 무게 합이 한계를 넘으면 0점을 매겨 버린다. 이렇게 점수를 매기는 규칙이 바로 적합도 함수이며, 처음에는 무작위로 만든 여러 해답(개체군)에서 출발한다.

다음은 한 세대를 만드는 세 단계다. 먼저 선택에서는 다음 세대로 보낼 해를 고른다. 점수가 클수록 큰 몫을 차지하는 룰렛휠 방식도 있지만, 영상에서는 무작위로 두 해를 뽑아 점수가 높은 쪽이 이기는 토너먼트 선택을 사용한다. 이렇게 뽑힌 두 부모 해를 교차로 절반씩 잘라 서로 바꿔 자식 둘을 만들고, 이어 돌연변이에서 각 비트마다 난수를 뽑아 돌연변이율보다 작으면 비트를 뒤집는다. 돌연변이율은 교차율보다 훨씬 낮게(예: 0.01~0.1) 둔다.

이 과정을 원래 개체군과 같은 수의 자식이 채워질 때까지 반복하면 한 세대가 끝난다. 보통 수백에서 수천 세대를 돌리면 평균 적합도와 최고 적합도가 오르다가 점차 평탄해지는데, 그 무렵이 알고리즘을 멈추기 좋은 시점이다. 매개변수가 네 개뿐인 이 예시는 단순하지만, 무게·가치에 더해 크기나 내구성처럼 변수가 많아지고 상자가 수백~수천 개로 늘면 좋은 해를 직관으로 찾기 어려워져 유전 알고리즘의 가치가 커진다.

주요 인사이트

• 유전 알고리즘은 최적해를 보장하지 않는다. 오히려 정확한 답을 못 찾는 경우가 많지만, 해가 어느 방향으로 좋아지는지를 알려줘 문제를 더 잘 이해하게 해준다. 본질은 거대한 탐색 공간을 훑는 탐색 알고리즘이다.
• 무작위성이 약점이자 강점이다. 점수가 가장 높은 해가 우연히 선택되지 못하고 사라질 수 있는데, 이를 막기 위해 최고 해를 다음 세대에 그대로 넣는 엘리트주의 같은 전략을 쓴다.
• 돌연변이는 개체군에 변이를 더해 다양성을 유지하는 장치다. 변이가 없으면 해들이 비슷해져 더 나은 답을 찾을 여지가 줄어든다.
• 개체 수, 교차율, 돌연변이율, 토너먼트 크기 같은 매개변수 조정이 성능의 핵심이다. 강연자는 변수와 상자가 많아질 경우 개체 수 500, 교차율 0.5, 돌연변이율 0.05, 토너먼트 크기 4~8 정도를 출발점으로 제안한다.

자주 묻는 질문