유전 알고리즘에 대해 간단히 알아봅니다. 많은 내용은 “유전 알고리즘(문병로, 2003)” 책을 통해 공부하고 정리하였습니다.
Introduction
유전 알고리즘에 대해 공부한 것을 정리하는 차원에서 쓰도록 하겠습니다.
얼마 전에 정말 신기했던 프로그램을 하나 봤습니다. 보고 정렬이라는 정렬 방식이 있는데, 정말 단순하고 무식한 정렬 방법입니다. 리스트의 모든 원소를 무작위로 재배치하고 정렬되었는지 확인하는 작업을, 정렬이 완료될때까지 한없이 반복하는겁니다. 의사코드로 표현하면 이런 모양이 됩니다.
repeat {
shuffle a list;
} until (list sort complete);
극강의 단순함을 자랑합니다. 정렬에 시간이 얼마나 걸릴 지는 며느리도 모릅니다. 이 정렬 방식의 별명이 Stupid Sort인데는 이유가 있습니다.
그런데 이 단순무식한 정렬법에, 유전 알고리즘(Genetic Algorithm) 이라는 녀석을 이용해서 정렬 속도를 획기적으로 개선한 것을 보았습니다. 물론, 아직 정렬 속도는 다른 정렬 알고리즘에 비해 한없이 멍청하긴 합니다만, 진화한다는 컨셉으로 만들어진 알고리즘 자체가 정말 흥미롭습니다.
유전 알고리즘은, 방금 말했듯이 진화라는 키워드에서 생겨난 문제 해결 알고리즘입니다. 자연에서는, 적자 생존의 원칙에 의해 환경에 적응하지 못한 약한 생물들은 쇠퇴하고 멸종하여, 시간이 지날수록 강인하고 환경에 더 적합한 생물만 남게 됩니다. 또한 생물들은 살아남기 위해 진화를 해서 자연 환경에 자신을 맞추려고도 합니다. 유전 알고리즘은 자연의 이런 현상을 문제 해결에 사용해보자는 아이디어에서 시작되었다고 합니다.
유전 알고리즘의 골자를 간단히 설명하자면, 어떤 문제를 해결하기 위해 수많은 문제의 해의 후보들을 생성하여, 그 후보 해들이 문제의 최적해에 수렴하도록 진화시키는 것입니다. 유전 알고리즘이 사용되는 대부분의 문제는 최적해가 딱 정해져 있지 않거나, Traveling Salesman Problem 등의 최적 경로 문제와 같은, NP-hard 문제의 최적화 버전입니다. 자료를 정렬하는 등의, 문제를 풀이하기 위한 더욱 빠른 알고리즘이 존재하는 많은 문제들을 풀이할 때는 굳이 속도가 느린 유전 알고리즘을 사용할 필요가 없습니다.
기본적인 용어들
생물학에서 유전을 담당하는 유전 물질은 염색체(Chromosome) 입니다. 생물 개체들은 염색체의 교차를 통해 유전자가 재조합되고, 희박한 확률로 일어나는 돌연변이로 새로운 특성을 가진 개체들을 만들어냅니다. 또 그렇게 만들어진 개체들은 환경에 적응하기 유리한 종에 따라 선택적으로 번성하게 됩니다.
유전 알고리즘은 자연의 이런 유전 현상을 그대로 문제 해결 알고리즘에 옮겨 놓은 것입니다. 문제 해결 중 생기는 임의의 해는 자연계에서의 역할과 동일하게 표현되어 염색체라고 부릅니다. 자연계에서는 개체 집단 안의 개체의 수가 가변적이고 제한이 없지만, 유전 알고리즘에서는 대부분의 경우에 정해진 수의 염색체를 가진 집단을 운영하는데, 이 집단을 해집단(Population) 이라고 합니다.
염색체 상의 각각의 인자를 유전자(Gene) 이라고 합니다. 유전자는 유전 알고리즘의 최소 단위입니다. 유전 알고리즘에는 염기와 같은 유전자의 하위 개념은 사용되지 않습니다. 또한, 생물학에서와 같이 유전자형(Genotype) 은 유전자들의 조합, 즉 유전 알고리즘에서는 염색체 그 자체이고, 표현형(Phenotype) 은 관찰되는 형질으로써, 유전 알고리즘에서는 해 또는 염색체의 성격이나 품질 등을 표현형이라고 합니다.
자연계에서는, 어떤 생물의 개체군이 자식을 낳고 번성하며 시간이 흐르면, 부모 개체들은 다 늙거나 죽고 자식 개체들이 해당 생물의 운명을 이어가게 됩니다. 이를 세대(Generation) 라고 부르는데, 현재 살아가고 있는 개체들은 ‘현재 세대’라고 부르고, 현재 세대 개체들의 자식 개체군을 ‘자식 세대’ 또는 ‘다음 세대’라고 부릅니다. 유전 알고리즘에서도 이 모습을 그대로 사용합니다. 어느 시점의 해집단을 그 시점의 세대(Generation)이라고 부릅니다. 현재 운용중인 해집단을 현재 세대라 하고, 유전 연산을 통하여 이전 세대로부터 만들어진 해집단을 자식 세대 또는 다음 세대라고 칭합니다.
유전 알고리즘의 구조
유전 알고리즘은 자연의 현상을 그대로 옮겨온 것이기 때문에, 자연의 그것과 매우 닮아있습니다. 굳이 만드는 한가지 차이라면, 자연계에서는 어떤 생물이 모두 멸종할 때까지 유전과 진화가 이루어지지만, 유전 알고리즘에서는 정해진 조건에 의한 최적해가 생기면 알고리즘을 정지 한다는 정도가 있겠습니다.
유전 알고리즘의 전형적인 구조를 살펴보겠습니다. 유전 알고리즘은 대부분 정해진 수의 해, 즉 염색체로 구성되는 해집단을 가지고 있습니다. 어떤 유전 알고리즘의 해집단의 해의 수를 \(n\) 이라고 하겠습니다. 이 해집단으로부터 다음 세대를 구성할 \(k\) 개의 새로운 해를 만들어 내는데, 각각의 해는 선택(Selection), 교차(Crossover), 변이(Mutation) 의 세 단계를 거쳐 생성됩니다. 여기서 새롭게 만들어진 \(k\) 개의 해는 현재 해집단 내의 \(k\) 개의 해와 대치(Replace) 됩니다. 이러한 과정을 알고리즘의 정지 조건을 만족할 때까지 반복하다가, 정지 조건을 만족하면 그 시점의 해집단 내에서 가장 좋은 해, 즉 최적해를 문제의 답으로 삼는 것입니다.
이 구조를 의사 코드로 나타내면 다음과 같아집니다. 의사 코드는 유전 알고리즘(문병로, 2003) 서적에서 본 내용임을 밝힙니다.
// offspring[] : 새로 만들어진, 곧 현재 해집단과 대치될 염색체 집단
n개의 초기 염색체를 가진 해집단 생성;
repeat {
for i=1 to k {
선택 알고리즘에 의하여 두 염색체 p1, p2 선택;
offspring[i] = Crossover(p1, p2) // 선택된 두 염색체를 교차해 새로운 염색체 생성
offspring[i] = Mutation(offspring[i]) // 일정 확률로 변이 시행
}
offspring[] 내의 모든 k개의 염색체를 현재 해집단 내의 k개의 염색체와 대치;
} until (정지 조건 만족);
남은 해 중 최적해를 return;
위에서 상수 k 는 해집단의 염색체들이 한 번에 얼마나 많이 대치되느냐를 결정하는데, 여기서 \(k / n\) 을 세대차(Generation Gap) 이라고 합니다. 세대차가 1에 가까운, 즉 절대 다수의 해를 매 세대마다 대치시키는 유전 알고리즘을 세대형 유전 알고리즘(Generational Genetic Algorithm) 이라고 하고, 세대차가 \(1 / n\) 에 가까운, 해가 생기는 대로 해집단에 넣어주는 유전 알고리즘을 안정 상태 유전 알고리즘(Steady-state Genetic Algorithm) 이라고 합니다. 이 두 유전 알고리즘간에는 서로 장단점이 있으므로, 문제 상황에 맞게 선택해야 할 것입니다.
위의 유전 연산자들 중 선택 연산자는 교차 연산을 위하여 현재 해집단 내에서 임의의 해를 선택하는 작업입니다. 기본적으로 더욱 우수한 해에게 더욱 높은 선택 확률이 주어집니다. 교차는 선택된 두 개의 부모해로부터 자식해를 생성해내는 연산자인데, 유전 알고리즘의 성능에 지대한 영향을 미칩니다. 변이는 해를 일정한 확률로 임의로 변형시키는 연산자입니다. 부모해에 없는 속성을 새롭게 만들어 해의 다양성을 높이는 역할을 수행합니다.
유전 알고리즘의 연산자
유전 알고리즘 연산자의 피연산자는 염색체입니다. 유전 알고리즘에서 염색체는 특정한 형태로 존재하는데, 보통 1차원 스트링 형태로 이루어집니다. 이진수 스트링인 경우도 있고, 정수 스트링이거나 실수, 문자열 스트링일 수도 있습니다. 이번 글에서는 이진수와 정수 스트링 염색체만을 이용하여 예시를 들도록 하겠습니다.
선택 연산자
선택 연산자는 교차 연산을 하여 자식 염색체를 만들기 위해서 부모 염색체를 선택하는 과정입니다. 자연계에서도 환경에 잘 적응하고 강인한 생물이 번식을 하여 번영을 누리듯이, 유전 알고리즘에서도 문제에서 요구하는 해에 더욱 가까울수록 자손을 퍼트려 우수한 형질을 남길 확률이 높아집니다. 여기서, 어떤 염색체가 문제에서 요구하는 해와 얼마나 비슷한지, 얼마나 가까운지를 적합도(Fitness) 라고 하고, 임의의 염색체의 적합도를 구해주는 함수를 적합도 함수(Fitness function) 이라고 합니다. 따라서, 유전 알고리즘의 선택 연산자에 의해 선택되는 염색체는 일정한 적합도 함수에 의해 구해진 적합도가 높은 염색체일 확률이 높습니다. 선택 연산자에서 중요한 부분이 하나 또 있는데, 바로 해의 다양성입니다. 해의 다양성을 위하여, 적합도가 낮은 염색체들에게도 선택될 기회를 조금이나마 주어야 합니다.
위 그림은 선택 연산의 예시를 보여줍니다. 선택 기준, 즉 적합도 함수가 이 문제에서는 정수 7과의 차이라고 볼 수 있습니다. 위 사진의 각각의 정수들이 염색체라고 할 때, 6과 8이 제일 적합한 염색체로 판단될 수 있습니다. 유전 알고리즘은 이렇게 선택된 두 부모해를 가지고 다음 연산을 진행하게 됩니다. 선택 연산자에는 다양한 종류가 있는데, 나중에 따로 포스팅을 해서 설명하겠습니다.
교차 연산자
교차 연산은 두 개의 부모 염색체의 특징을 부분적으로 결합하여 하나의 새로운 자식 염색체를 만들어내는 과정입니다. 교차 연산은 해집단을 직접 생성하는 역할을 하므로, 유전 알고리즘에서 가장 중요하며 성능을 가장 크게 좌우하는 연산입니다. 그런 만큼 정말 많은 방법들이 있는데, 이 방법들을 사용하기 전에 가장 중요한 것은 문제의 해의 표현 방법을 결정하는 것입니다.
이 그림은 1점 교차 연산의 예를 보여줍니다. 그림을 보면, 두 개의 부모해인 [1 1 2 2 3 3 4 4 5 5]와 [6 6 7 7 8 8 9 9 0 0]이 있습니다. 두 개의 해를 하나의 자름선을 기준으로 하여 각각 두 부분으로 나눠서, 각 염색체에서 한 부분씩 가져와서 새로운 자식해를 생성합니다.
자름선의 개수가 \(n\)개일 때의 교차 연산을 \(n\)점 교차라고 합니다. 이 그림은 3점 교차 연산의 예를 보여주고 있습니다.
세 개의 자름선을 설정하여 부모해를 각각 네 부분으로 나눕니다. 자식해는 두 부모해로부터 번갈아가며 복사받아 생성됩니다.
n점 교차 말고도 균등 교차, 싸이클 교차, PMX 교차 등의 다양한 교차 연산들이 존재하는데, 이것들은 따로 교차 연산자에 대한 글을 작성하여 설명하겠습니다.
변이 연산자
변이 연산자는 단순합니다. 자연계에서 생물에게 일어나는 변이와 같이, 교차를 통해 만들어진 자식해에게 일정 확률로 돌연변이를 일으켜주는 과정입니다. 부모해에서 없는 유전적 형질을 자식해에 새롭게 도입하기 위해서 변이를 일으킵니다.
이 그림은 일차원 스트링 염색체 상의 변이 과정을 보여줍니다.
보통 변이는 확률적으로 일으키는데, 0부터 1 사이의 실수 난수를 생성하여 미리 정한 임계값 미만의 수가 나오면 해당 염색체를 임의로 변형시킵니다. 임계값은 보통 0.015, 0.0015 등의 값이 사용됩니다.
자연계에서 가끔씩 일어나는 변이가 생물 집단에 크게 영향을 미치지 않는 반면, 유전 알고리즘의 변이 연산은 대부분의 경우 해집단의 품질에 큰 영향을 미치게 되므로, 변이 확률의 조정이 중요합니다.
염색체의 다양한 표현법
유전 알고리즘의 궁극적인 목적은 문제 해결에 가장 적합한 염색체(최적해)를 구하는 것입니다. 따라서 유전 알고리즘에서 문제의 임의의 해를 어떻게 표현할 것인지 결정하는 것은 매우 중요한 작업입니다. 문제의 특징이나 해의 모양에 따라서 염색체를 표현할 방법이 크게 달라질 수 있습니다. 또 해의 표현 방법에 따라서 유전 알고리즘의 성능이 크게 좌우될 수도 있으니 적절한 해의 표현법을 사용하는 것이 중요합니다.
가장 기본적인 염색체의 모양은 다음과 같은 이진수 스트링 형태입니다.
010010110110001111010100
유전 알고리즘이 연구되던 초기 시절에는 이진수 스트링 형태의 염색체 모양이 유전 알고리즘의 중요한 특징 중 하나라고 소개되기도 했습니다. 이 형태 염색체의 가장 큰 장점은 유전 연산자를 적용하기가 매우 편하고 응용하기도 좋다는 점입니다. 2진수를 제외한 n진 정수 스트링 형태의 염색체와 비교해서 살펴보겠습니다.
정수 스트링 형태의 염색체는 보통 10진수와 16진수 형태를 많이 사용합니다.
94856322
19A8CD
이제 10진 정수 스트링 형태의 염색체 94856322 를 2진수 스트링으로 바꾸어 보겠습니다.
94856322 -> 10010100100001010110001100100010
10진수 정수 한 자리를 2진수 4자리로 각각 치환한 결과 스트링입니다. 딱 봐도 염색체의 길이 자체가 매우 길어진 것을 보실 수 있습니다. 이렇게 긴 염색체는, 대부분의 경우에서 교차와 변이 연산을 시행할 때 (특히 교차 연산을 시행할 때) 더 넓은 범위에서의 연산을 가능하게 합니다. 또, 10진 정수 스트링 염색체를 교차할 때는 일어날 수 없는 추가적인 교차 연산들이 더 일어날 수 있으므로 추가적인 변이의 기능까지 수행할 수 있습니다.
그렇지만, 그렇다고 해서 무조건 2진수 스트링 형태의 염색체가 낫다는 것은 아닙니다. 염색체의 표현법을 결정할 때는 무조건 문제에 맞게 표현을 구성하는 것이 우선입니다. 잘못된 염색체 표현은 유전 알고리즘의 성능을 저하시키는 요인이 될 수 있습니다.
2.15 2.65 3.22 9.55 7.40
보시듯이, 실수 배열 형태의 염색체입니다. 실수 배열 형태 염색체의 가장 큰 매력은 수의 ‘크기’ 개념을 염색체에 담을 수 있다는 점입니다. 이 장점을 최대한 살린 ‘산술적 교차’ 라는 연산도 존재합니다. 동일 위치에 있는 두 부모의 유전자들의 값을 평균 내어 자식의 동일 위치 유전자 값으로 삼는 교차 연산입니다.
다음으로, 이진 스트링 형태 염색체의 변형판인 그레이 코딩이 있습니다.
이진 코딩 - 그레이 코딩
0000 - 0000
0001 - 0001
0010 - 0011
0011 - 0010
0100 - 0110
0101 - 0111
0110 - 0101
0111 - 0100
1000 - 1100
1001 - 1101
1010 - 1111
1011 - 1110
1100 - 1010
1101 - 1011
1110 - 1001
1111 - 1000
그레이 코딩의 특징은, 인접한 두 수가 반드시 한 개의 비트만 차이난다는 점입니다. 의미상으로 유사한 두 해가 가까운 거리에 위치하게 하는 것이 그레이 코딩 염색체의 개발 동기라고 합니다. 그레이 코딩은 임의의 한 비트를 바꾸었을 때 급격한 변화를 방지하는 역할을 합니다.