유전 알고리즘 해설
진화는 설계자 없이도 눈과 날개와 뇌를 만들어 냈습니다. 잘되는 것을 남기고 그것을 변화시켰을 뿐입니다. 유전 알고리즘은 이 아이디어를 빌려 컴퓨터로 문제를 풉니다. 문제를 이해할 필요 없이 더 나은 답과 더 못한 답을 구별하기만 하면 되므로, 가능한 답의 공간이 너무 크고 너무 기묘해서 다른 방법으로는 탐색할 수 없을 때 강력한 도구가 됩니다.
기본 아이디어
1960년대와 1970년대에 미시간 대학교의 존 홀랜드(John Holland)는 다윈의 이론을 알고리즘으로 바꾸었고, 이를 1975년 저서 『자연 및 인공 시스템의 적응(Adaptation in Natural and Artificial Systems)』에서 설명했습니다. 비슷한 시기에 독일의 잉고 레헨베르크(Ingo Rechenberg)와 한스파울 슈베펠(Hans-Paul Schwefel)은 공학 설계를 위한 진화 전략을 개발했습니다. 공통된 방법은 후보 해의 집단을 유지하고, 점수를 매기고, 더 나은 후보가 변화를 동반해 번식하게 한 뒤, 이를 여러 세대 반복하는 것입니다.
유전자와 집단
각 후보는 염색체, 즉 유전자의 목록으로 표현됩니다. 플레이그라운드에서 로켓의 유전자는 비행의 매 순간마다 하나씩 있는 추진력입니다. 다른 문제에서는 숫자의 비트, 경로에 있는 도시의 순서, 설계에 쓰인 부품의 크기 등이 유전자가 될 수 있습니다. 첫 세대는 무작위이므로 답의 공간을 넓게 탐색하지만 좋은 답은 거의 없습니다.
적합도 함수
적합도는 후보가 얼마나 좋은지를 나타내는 하나의 숫자이며, 알고리즘이 문제에 대해 아는 유일한 것입니다. 로켓의 경우 일찍 도착하는 것을 가장 크게 보상하고, 그다음으로 목표 가까이에서 끝나는 것을 보상하며, 충돌에는 벌을 줍니다. 잘 고른 적합도 함수는 탐색을 좋은 답 쪽으로 매끄럽게 이끌지만, 부주의하게 만든 적합도 함수는 엉뚱한 것을 보상하고, 알고리즘은 거기에 남은 허점을 어떻게든 이용합니다.
선택
부모는 적합도가 높은 후보가 더 많은 자식을 갖도록 선택되지만, 약한 후보에게도 기회가 주어집니다. 그 유전자에 쓸모 있는 조각이 들어 있을 수 있기 때문입니다. 룰렛 휠 선택은 각 후보에게 적합도에 비례하는 크기의 휠 조각을 주고, 토너먼트 선택은 몇 개를 무작위로 골라 그중 가장 좋은 것을 택합니다. 선택이 강할수록 진전은 빨라지지만 집단이 서로 비슷해져서 탐색이 너무 일찍 끝날 수 있습니다.
교차와 돌연변이
교차는 두 부모를 결합합니다. 여기서는 자식이 유전자의 앞부분을 한쪽 부모에게서, 나머지를 다른 부모에게서 받으므로, 한 로켓의 초반 기동이 다른 로켓의 후반 기동과 만날 수 있습니다. 돌연변이는 몇몇 유전자를 무작위로 바꿉니다. 교차는 집단이 이미 가진 것을 재조합하고, 돌연변이는 집단이 한 번도 가져 본 적 없는 것을 들여옵니다. 홀랜드의 스키마 정리는 이러한 선택과 재조합의 조합 아래에서 좋은 유전자로 이루어진 짧은 구성 요소가 집단에 어떻게 퍼지는지 설명합니다.
엘리트 보존, 탐색과 활용
가장 좋은 후보 몇 개를 그대로 다음 세대에 복사하는 엘리트 보존은 최고의 답이 결코 사라지지 않도록 보장합니다. 모든 유전 알고리즘은 탐색 공간의 새로운 영역을 시도하는 탐색과 이미 좋은 것을 다듬는 활용 사이에서 균형을 잡아야 합니다. 변이가 너무 적으면 집단은 평범한 답 하나로 수렴하고, 너무 많으면 결코 자리를 잡지 못합니다. 개체 수, 돌연변이율, 선택압이 이 균형을 맞추는 다이얼입니다.
국소 최적해
유전 알고리즘은 적합도만 따르므로 속을 수 있습니다. 최고의 답으로 가는 길이 먼저 더 나쁜 답들을 거쳐야 할 때, 집단은 가장 가까운 언덕에 올라 그곳에 머무릅니다. 이것이 국소 최적해입니다. 플레이그라운드의 엇갈린 벽 뒤에서는 목표 아래에서 충돌하는 로켓이 방향을 돌려 틈을 찾는 로켓보다 점수가 높아서, 집단이 벽 앞에 몰려듭니다. 해결책으로는 개체 수 늘리기, 돌연변이율 높이기, 집단의 다양성 유지하기, 그리고 무엇보다 더 나은 적합도 함수가 있습니다.
직접 탐구해 보세요
유전 알고리즘 플레이그라운드를 열고 벽 하나, 틈, 기둥, 엇갈린 벽 또는 직접 그린 벽을 돌아가도록 로켓을 진화시켜 보세요. 개체 수, 돌연변이율, 수명, 선택 방식을 바꾸고, 엘리트 보존을 켰다 껐다 하면서, 목표에 도달하는 로켓의 비율이 얼마나 빨리 늘어나는지, 또는 왜 늘어나지 않는지 차트에서 확인해 보세요.
자주 묻는 질문
유전 알고리즘은 인공지능의 일종인가요?
탐색 및 최적화 방법으로서 AI와 머신러닝이라는 더 넓은 분야에 속합니다. 신경망처럼 예제로부터 학습하는 것이 아니라, 시행과 선택을 통해 후보 해를 개선합니다. 둘은 자주 결합되는데, 예를 들어 신경망의 구조나 가중치를 진화시키는 방법이 있으며 이를 신경진화라고 합니다.
유전 알고리즘은 항상 최고의 답을 찾나요?
아니요. 유전 알고리즘은 휴리스틱입니다. 어려운 문제에 대해 대개 좋은 답을 찾지만, 최고의 답이라는 보장은 없으며 그 답이 최적에 얼마나 가까운지에 대한 증명도 없습니다. 정확한 방법이 충분히 빠른 문제라면 그 방법이 더 낫습니다.
유전 알고리즘과 진화 전략은 어떻게 다른가요?
둘 다 진화 알고리즘입니다. 고전적인 유전 알고리즘은 문자열 같은 염색체에 대한 교차를 강조하고, 진화 전략은 주로 실수에 대한 돌연변이를 사용하며 진행하면서 돌연변이의 크기를 스스로 조정하는 경우가 많습니다. 현대적인 방법은 두 가지의 아이디어를 섞어 씁니다.
로켓은 처음에 왜 그렇게 서툴까요?
처음 유전자는 완전히 무작위인 추진력이라서 평균적으로 서로 상쇄되고, 로켓은 그냥 떠다닙니다. 우연히 대략 올바른 방향으로 추진한 드문 로켓들을 선택이 남기고, 교차가 그 로켓들의 좋은 구간을 결합한 뒤에야 비로소 조화로운 비행이 나타납니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
유전 알고리즘 플레이그라운드 열기