유전 알고리즘이란?
유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로 존 홀랜드(John Holland)에 의해서 개발된 전역 최적화 기법으로 진화 연산(Evolutionary Computation)의 대표적인 한 분야이자, 생물의 진화 과정에서 많은 부분을 차용한 알고리즘입니다. 연산 정의에 따라 차이가 있겠지만 일반적으로 유전 알고리즘은 문제를 해결하는 데 상당한 시간이 걸리기에 순회 세일즈맨 문제(Traveling Salesman Problem)와 같이 전역 최적해를 구하기 난해한 문제에서 유용하게 사용됩니다. 그러나 유전 알고리즘을 "특정 문제를 풀기 위한 알고리즘"으로 오해하면 안 됩니다. 유전 알고리즘은 모든 문제에 일괄적으로 적용할 수 있는 소스 코드나 알고리즘이 아니기에 해결하고자 하는 문제에 맞춰서 적용하는 과정이 필요합니다. 즉, 유전 알고리즘을 알고리즘이라고 표현하지만 실제로는 최적화 문제를 풀기 위한 방법론에 가깝습니다. 문제에 일괄적으로 적용할 수 없고 결정해야 하는 변수가 많지만, 유전 알고리즘은 매우 유용한 최적화 기법입니다. 이론적으로 전역 최적점을 찾을 수 있고 수학적으로 명확하게 정의되지 않은 문제에도 적용할 수 있을 뿐만 아니라 적합도 평가에 기울기 정보를 필요로 하지 않으므로 함수의 연속이나 미분가능성 등의 제약을 받지 않는다는 점도 큰 장점으로 작용합니다.
유전 알고리즘의 구조
유전 알고리즘은 크게 Initialize, Fitness Evaluation, Crossover, Mutation, Selection, Terminate으로 구성됩니다. 각 요소는 문제, 염색체의 형태 등에 따라 연산 방법은 변할 수 있지만, 기본적인 역할은 변하지 않습니다. 따라서, 유전 알고리즘을 이해하고 문제에 적용하기 위해서는 각 요소의 역할 파악이 선행되어야 합니다.
- Initialize
Initialize는 크게 유전 알고리즘을 찾고자 하는 해(Solution)을 유전자(Gene) 및 염색체(Chromosome)로 표현하는 단계와 무작위로 염색체를 생성하여 해집합인 유전체(Population)를 구성하는 단계로 구성됩니다.
Fig. 1은 유전 알고리즘을 사용해서 Flexible Job Shop 스케줄링 문제를 풀기 위해 유전자와 염색체를 구성한 예시입니다. 쉽게 말해 각 주문(Order)을 처리하기 위해 n개의 작업(Job)이 주어져 있을 때, 작업을 수행하는 순서를 표현한 것입니다. 유전자의 $O_{n}$은 n번째 주문을 의미하고, 염색체 속 $O_{n}$의 개수는 각 주문을 처리하기 위한 작업의 숫자를 의미합니다. 즉, $O_{1}$은 염색체 내에 4개가 있음으로 첫 번째 주문을 처리하기 위해서는 4개의 작업이 필요하다는 의미로 염색체를 구성한 것입니다.
염색체를 구성했으면 무작위로 염색체를 생성하고 유전체를 구성할 차례입니다. Fig. 1은 4개의 $O_{1}$, 5개의 $O_{2}$, 그리고 3개의 $O_{3}$, 총 12개의 유전자로 구성되어 있습니다. 무작의로 염색체를 구성하는 것은 Fig. 1의 사례에서는 12개의 유전자를 무작위로 배치하는 것과 동일합니다. 이는 유전자 정의에 따라서 달라질 수 있지만, 대부분의 경우 동일할 것입니다. 이후 몇 개의 염색체로 하나의 해 집합인 유전체를 구성할 것인지 판정해야 합니다. 하지만, 몇 개의 염색체가 최적인가에 대한 정보는 주어지지 않았습니다. 가장 적은 수의 염색체를 가지고 최적에 근사한 해를 찾는 경우가 최적임으로 시행착오가 필요한 부분입니다.
TMI: Job Shop 스케줄링은 주문을 처리하기 위한 작업의 순서가 결정되어 있습니다. 하지만, 유전 알고리즘의 Crossover와 Mutation 과정에서 염색체 내의 유전자의 순서가 뒤섞임으로, 유전자에 순서가 반영된다면 스케줄링 문제에 유전 알고리즘을 적용하기 난해한 상황에 도달하게 됩니다. 따라서, 위 예시는 단순하게 주문에 필요한 작업의 수를 유전자로 구성하고 주문에 관한 정보는 외부에 저장함으로서 스케줄링 문제에 유전 알고리즘을 적용한 예시입니다.
- Fitness Evaluation
적합도(Fitness)의 평가는 유전체의 성능을 평가하는 척도입니다. 유전 알고리즘은 좋은 염색체를 찾아내는 과정이기에, 좋은 염색체란 무엇인지 판정할 수 있어야 합니다. 스케줄링을 예로 들면, Regular Measure인 작업완료시간(Makespan) 이나 지연시간(Tardiness) 등을 적합도 평가에 반영한다면, 좋은 염색체를 판정할 수 있습니다. 작업 순서가 결정된다면 Fig. 2와 같은 간트 차트(Gantt Chart)를 통해 작업완료시간이나 지연시간을 계산할 수 있습니다.
- Crossover
Crossover는 주어진 염색체 중에서 뛰어난 염색체를 선정하고 더 나은 염색체를 만드는 과정입니다. 즉, 뛰어난 염색체를 바탕으로 더 좋은 염색체를 만듦으로써 유전 알고리즘이 최적해를 가질 수 있도록 만들어 줍니다. 이 단계에는 Crossover을 위한 두 개의 염색체를 선택하는 과정과 Crossover 방법을 선택해야 합니다.
염색체 두 개의 선택하는 대표적인 방법은 Fig.3의 룰렛 휠(Roulette Wheel) 방법입니다. 적합도 평가 함수를 통해 염색체의 가치를 계산한 후, 가치 크기에 비례하여 룰렛 휠에 염색체를 배당함으로서 적합도가 높은 유전체가 더 많이 선택될 수 있도록 합니다. 룰렛 휠은 적합도의 크기에 따라서 비율이 결정되는 방법입니다. 하지만, 그 외에 다양한 방법이 존재합니다. 예를 들면 임계점 t 값을 결정하고, 무작위로 두 개의 염색체를 선정합니다. 이후 무작위 난수를 발생시킨 후 그 난수가 임계점 t보다 크면 두 염색체 중 높은 적합도 함수값을 가지는 염색체를 선택하는 방법인 토너먼트 선택, 상위 몇 개의 하부 염색체 집합을 생성하고 그 집합 내에서 무작위로 염색체를 뽑는 방법 등 다양한 염색체 선정 방법이 존재합니다.
두 염색체를 선택하였으면, 이제 Crossover 연산을 수행해야 합니다. Crossover은 다양한 연산이 있지만, 스케줄링 문제에 적용했던 순서 교차(Order Crossover) 방법을 소개하고자 합니다. Fig. 4의 순서 교차 방법은 선택한 두 개의 염색체 $s_{1}, s_{2}$에 대하여 임의로 두 개의 자름선을 선정한 다음 두 자름 선 사이에 있는 부분을 $s_{1}$에서 복사하고, 나머지 위치는 $s_{2}$에서 복사하되, 두 번째 자름 선 바로 다음 위치부터 시작하여 사용되지 않은 기호들 중에서 $s_{2}$에서 나타난 순서대로 복사하는 방법입니다.
- Mutation
Mutation은 주어진 염색체에서 낮은 확률로 변이를 일으켜서 새로운 염색체를 만드는 과정입니다. Mutation은 유전 알고리즘의 해가 지역 최적해가 아닌, 전역 최적해를 찾을 수 있도록 해 주는 장치로 유전자의 위치를 바꾸거나 값을 수정하는 형태로 진행됩니다
Mutation에도 다양한 연산이 있지만, 역시 스케줄링 문제에 적용했던 교환(Swap) 방법을 소개하겠습니다. 교환 방법은 하나의 염색체에서 두 유전자를 무작위로 선정하고, 그 위치를 교환하는 방법입니다. 스케줄링 문제에서 두 순서가 바뀜으로서 다양한 종류의 스케줄링을 고려할 수 있게 해주는 연산입니다.
- Selection
Selection은 해집합인 유전체 속의 염색체에 대하여 높은 적합도를 가지는 염색체가 다음 유전체로 전달될 수 있도록 하여 최적의 해를 찾을 수 있도록 하는 과정입니다. 높은 적합도를 가지는 염색체가 다음 세대로 전달되도록 하여 유전 알고리즘이 반복될수록 더 좋은 해를 찾게 합니다. 그렇기에 Selection은 유전 알고리즘의 성능에 크게 영향을 미치게 됩니다. 어떤 방법을 적용하느냐에 따라 최적해로 다가가는 속도가 느려지거나, 지역 최적해에 빠지거나, 혹은 우수한 해가 가진 나쁜 유전자 배열이 유전체 전체에 퍼지거나 반대로 나쁜 해가 가진 우수한 유전자 배열이 사장되는 경우도 발생할 수 있습니다. 그렇기에 Selection도 유전 알고리즘의 성능을 끌어올릴 수 있는 중요한 요소로 고려되어야 합니다.
Selection은 유전체 속의 각 염색체에 대하여 적합도를 측정하고, 다음 세대로 전해질 후보를 선택하는 과정으로 구성됩니다. 적합도의 측정은 Fitness Evaluation의 내용이기에 생략하겠습니다. 다음 세대로 전해질 후보를 선택하는 과정은 적합도 평가 함수 결과값을 기준으로 순위 기반 선택을 하거나, Crossover에서 두 염색체를 선택할 때 사용했던 룰렛 휠, 토너먼트 선택 등의 방법을 활용합니다.
- Terminate
Terminate는 유전 알고리즘의 소요시간과 관련된 요인입니다. 알고리즘을 종료하는 조건은 크게 두 가지가 있습니다. 초기에 정해진 반복 횟수가 끝날 때 까지 알고리즘을 가동하는 방법과 다른 하나는 염색체의 적합도 평가 함수의 값 변화가 특정 횟수 이상 일어나지 않을 때 알고리즘을 종료하는 방법이 있습니다. 두 방법 모두 장단점을 가지고 있기에 적합한 방법을 선택하거나 혹은 두 방법을 혼용해서 사용할 수 있습니다. 적은 수의 반복을 통해 최적해를 찾는 것이 가장 이상적인 상황이지만, 너무 적은 수의 반복을 수행하면 유전 알고리즘이 최적해에 도달하지 못할 수 있음으로 몇 번의 시행착오를 통해서 적정한 반복 횟수를 결정하는 의사결정이 필요합니다.
유전 알고리즘의 동작
유전 알고리즘의 흐름도는 아래 Fig. 6과 같습니다.
유전 알고리즘의 구조에서 설명한 내용들이 흐름도에 모두 표현되어 있습니다. 유전 알고리즘은 문제에 맞춰서 적용하는 방법론임으로 유전 알고리즘을 사용해서 해결하고 싶은 문제가 있다면, 흐름도부터 시작해서 각 요소들을 정의해 나가는 것부터 시작하시기를 권장합니다.
그 외
유전 알고리즘의 다양한 연산에 관한 정보가 필요하거나 문제를 유전자형으로 바꾸는 데 어려움이 있다면, 서울대학교 컴퓨터공학부의 문병로 교수님의 책을 추천드립니다. 저도 유전 알고리즘을 사용한 스케줄링 알고리즘에 관한 논문을 작성할 때 교수님의 책을 읽고 많은 도움을 받았던 기억이 있습니다. 또, 유전 알고리즘의 연산에 주관이 포함되지 않도록 주의하시길 바랍니다. 교차와 변이 연산에 주관이 포함되면 다양한 해를 탐색하기 어려워지고, 오히려 지역 최적화에 머물 가능성이 높아집니다.