유전 알고리즘(Genetic Algorithm) 소개

 

유전 알고리즘 개요

 

유전 알고리즘, Genetic Algorithm(GA)은 최근 10~20년 동안 제어 및 패턴 인식 분야에서 활발하게 연구되어온 주제이다.

 

1960년대에 시작되어 근래에 이르러 전역적 해를 찾는 문제 해결 방법론으로서 그 성능을 인정받아 다양한 분야에서 응용이 이루어지고 있다.

 

유전 알고리즘을 이해하는데에는 먼저 구성요소와 알고리즘의 프로세스에 대해 알 필요가 있다.

 

유전 알고리즘은 그 말처럼 자연계에서 생물이 다음 세대에게 유전자를 전달하면서 환경에 적응한 염색체가 살아남도록 교차와 돌연변이에 의해 진화하는 과정을 모델링 한 것이다. 예를 들어, 인간은 세포 하나마다 DNA 한쌍이 있고 각각에는 약 30억 개의 염기로 이루어져 있다. 유전 알고리즘에서는 문제를 해결하기 위해 이러한 유전자를 적절한 크기와 표현으로 정하고 선택과 교차, 돌연변이, 대치를 통해 원하는 성능을 내도록 목적함수를 만족시킬 때까지 과정을 반복 수행하게 한다.

 

 

2006년 NASA ST5 우주선의 안테나 모양. 이 복잡한 모양은 진화 컴퓨팅을 이용하여 가장 최적화된 형태로 디자인된 산출물이다. (이미지 출처 : http://en.wikipedia.org/wiki/Genetic_algorithm)

 

 

기본 용어 설명

 

유전 알고리즘의 기본적인 내용을 이해하기 위해 필요한 용어는 다음과 같다.

 

- 유전자 표현 혹은 염색체 Chromosome

- 해집단 Population

- 적합도 함수 Fitness Function

- 세대 Generation

 

생명체에 유전 정보를 담고 있는 DNA가 있듯이 유전 알고리즘에서도 이를 모델링 하기 위한 유전자로 구성된 염색체가 존재한다. 가장 간단하게는 바이너리(0 혹은 1)로 이루어진 N개의 데이터로 표현되는데, 여기서 유전자는 하나의 비트가 되며, 염색체는 이러한 비트로 이루어진 N개의 데이터 자체라고 보면 된다.

 

해집단은 복수개의 염색체로 이루어진 집합을 의미한다. 어떤 생명체의 개체수로 의미를 이해하면 된다. 보통 자연계에서는 번식이나 어떤 사건들로 인해 개체수가 늘거나 줄어들지만 유전 알고리즘에서는 그 수를 일정하게 유지한다.

 

적합도 함수는 각각의 개체(염색체)가 주어진 환경에서 얼마나 살아남기에 적합한가를 판단하는 함수이다. 어떤 문제가 주어졌을 때, 염색체 정보가 그 문제를 가장 잘 풀기 위한 해인지를 판단해주는 함수로 사용자가 적합도 함수를 어떻게 놓느냐에 따라 진화의 방향을 결정한다.

 

세대는 해집단에 속해 있는 개체들이 자식을 낳아 다음의 해집단으로 변화되는 과정이다. 몇 번의 알고리즘 연산에 우리가 원하는 진화 목표에 달성할지에 따라 수렴 속도가 빠른지 느린지를 판단한다.

 

우리가 풀기 위한 문제의 성격을 잘 파악한 후, 위의 요소들을 어떤 식을 설정할지 고민해야 한다. 유전자 표현형(이진수, 십진수, 알파벳 등)을 선정한 후 몇 개의 스트링으로 만들것인지, 해집단의 개체수가 너무 작거나 크지는 않은지, 적합도 함수는 원하는 방향으로 진화를 할 수 있도록 설정이 되었는지 또한 이러한 것들이 구현상에서 물리적인 한계에 부딪힐 일이 없는지를 잘 생각해봐야 한다.

 

 

연산

 

유전 알고리즘의 연산은 다음과 같은 것들이 있다.

 

- 선택 Selection

- 교차 Crossover

- 변이 Mutation

- 대치 Replacement

 

선택 연산은 가장 핵심적인 연산으로 해집단에서 유전적으로 훌륭한 개체를 우선적으로 선택하기 위한 연산 과정이다. 선택 연산에는 품질 비례 룰렛휠 선택, 토너먼트 선택, 순위기반 선택 등이 있다.

 

교차 연산은 부모 세대에서 자식 세대로 유전자를 넘겨주기 위해 사용되는 연산이다. 일차원 교차 연산, 다차원 교차 연산, 정규화(Normalization) 등의 교차 연산 기법이 있다. 개체가 가지고 있는 특징이나 속성은 부모로 물려받기 때문에 아버지 혹은 어머니에게 어떤 점을 상속 받았는지를 모델링하고 있다고 보면 된다.

 

변이 혹은 돌연변이는 단순히 유전적인 대물림 이외에 자연발생적으로 유전자 변형이 일어나 부모에게서는 설명하기 힘든 변화를 모델링한다. 단어에서 유추할 수 있듯이 그 확률은 대단히 낮으며, 우리가 원하는 해로부터 멀어지게 할 수도 있지만 원하는 해로 수렴되기 위한 역동적인 요소로 작용하기도 한다. 문제에 따라 적절한 변이의 확률을 정해주는 것이 중요하다. 또한 Gradient Decent Rule과 같은 최적화 알고리즘의 단점으로 알려진 지역 최소점(Local Minima) 문제에 강건하게 한다. 변이 연산에는 전형적 변이, 비균등 변이, 수선 등의 방법이 있다.

 

대치 연산은 다음 세대로 가기 위해 해집단을 교체하는 것을 말한다. 단순하게 모든 해집단 요소를 바꿀 수도 있고, 이전 보다 우수한 개체만 교체할 수도 있다. 대치 연산은 교차와 변이 연산과 연관되어 결정되어야 한다. 교차/변이에 의해 개체가 변형이 많이 일어나면 수렴성이 강한 대치 연산을 사용해도 되나, 변형이 적게 일어난다면 해집단의 다양성을 고려하여 대치 연산을 선택해야 한다.

 

 

유전 알고리즘의 기본적인 내용들을 살펴보았다.

하지만 이정도 만으로는 어떤 것인지 어떤 응용을 할 수 있을지에 대해 감이 잘 안잡힌다. 다른 이론과 마찬가지로 유전 알고리즘도 실생활의 어떤 문제에 적용을 할 수 있는지 많은 고민이 필요할 것이다. 다음에는 간단한 형태의 예제를 통해 유전 알고리즘이 어떤 느낌인지를 알아보도록 하겠다.

 

 

 

(이 글이 마음에 드신다면 아래 버튼을 눌러 주세요~~^^)