유전 알고리즘 - Genetic Algorithm
존 홀랜드가 개발한 최적화 기법의 일종으로, 생명체의 진화를 모방하여 가장 적절한 해집단을 찾아간다
유전 알고리즘의 역사
미국 최초의 컴퓨터과학 박사로도 알려진 존 홀랜드 교수는, 평소 스승이었던 아서 막스 교수와 폰 노이만 교수의 오토마타 이론과 로널드 피셔의 자연선택을 다룬 책, <The Genetical Theory Of Natural Selection>을 읽고 그 영향을 받아 '유전 알고리즘'을 창시하게 된다. 발표 당시 연결주의론의 위기 등과 맞물려 인공지능 연구에 대한 지원이 크게 줄었고, 당시 학자들 또한 유전 알고리즘을 이해하길 꺼려했던 이유로 유전 알고리즘은 크게 주목받지 못하였다. 하지만, 인공지능이 다시 부흥하게 되며 그의 제자들과 다른 여러 학자들은 유전 알고리즘을 다시 주목하게 되었고, 이후 여러 연구가 거듭되며 많은 발전을 이루었다.
유전 알고리즘이란?
유전 알고리즘은 다윈의 적자생존 이론을 기반으로 한 전역 최적화 기법이다. 많은 해집단(집단) 속에서 주어진 문제를 가장 잘 풀어내는, 혹은 가장 적합한 해를 선택하는 것을 목표로 하며 이 과정에서 자연계의 진화를 본딴 여러 연산을 수행한다.
유전 알고리즘의 수행
유전 알고리즘은 먼저 해집단의 각 원소들(해)를 하나의 염색체처럼 나타낸다. 이 염색체들은 실수 혹은 여러 데이터 집합으로 나타내어지게 되고, 이 염색체의 각 원소를 유전자로서 표현한다.
또한 프로그래머가 정의한 적합도 함수fitness function 을 통해 이 유전자를 평가하고, 자연선택과 같이 살아남을 유전자들을 선택한다. 이 때, 유전적 다양성을 해치지 않기 위해서 선택을 너무 '박하게' 해선 안된다. 선택된 유전자들은 마치 생명체가 교배를 통해 유전자들을 섞듯, 일정한 규칙에 따라 교차되고 서로 섞인다. 또한, 한 유전자의 자손만이 살아남아 유전적인 다양성을 형성하지 못하고 일정 정확도에 접근하는 것에서 멈춰버리는 현상을 막기 위해서-선택 연산을 수행하는 것과 같은 맥락이다- 일부 유전자에 일정 확률로 '변이'를 주게 되는데, 이는 선택 가능한 범위 내에서 수행해야 한다.
선택 연산
자연 선택을 통해 생명체가 진화하려면, 환경에 의해 혹은 천적에 의해서든, '좋은' 유전자들을 선별해서 이들이 자연스레 살아남게끔 설정되어야 한다. 유전 알고리즘에서 그런 역할을 수행하는 것이 바로 선택 연산이다.
앞서 말했듯이, 유전적 다양성을 지키기 위해서, 어떤 한 종만이 살아남아 더 나은 발전을 하지 못하고 일정한 수준에서 진화가 멈춰버리는 현상을 막기 위해서 당장은 '좋지 않은' 염색체일지라도, 세대에 약간의 변동을, 진화의 매개가 될 수 있는 약간의 변동을 주기 위해서 살아남게끔 해야 하는것이다.
선택 연산은 이 자연선택을 하나의 알고리즘적인 메서드로 구현한 것이다. 프로그래머가 기술한 적합도 함수를 통해 염색체의 적합도를 계산하고, 이를 이용하여 확률적으로 혹은 특정한 염색체를 선택한다.
- 토너먼트 선택 연산
토너먼트 연산은 가장 간단한 선택 연산 메서드이다. 세대에서 두 개의 염색체를 임의로 선택하고, 난수 p를 생성한다. 이 난수 p와 미리 정의한 선택압 k(우수한 염색체를 남기는 비율, p와 동일한 정의역을 가진다)의 대소를 따지고, p>k이면 적합도 함수에 의해 평가된 적합도가 다른 하나보다 낮은 염색체를 선택하고 반대의 경우 높은 염색체를 선택한다. 이는, 프로그래머가 k값을 조절하여 적합도가 낮은 염색체들을 남기는 비율을 조정할 수 있게 하기 위함이다. 이 과정을 통해 하나의 염색체를 선택하고, 나머지 염색체들에 대해서도 똑같은 연산을 실시해 원하는 만큼의 염색체만을 남긴다.
- 품질 비례 룰렛휠 연산
품질 비례 룰렛휠 연산은 또 다른 선택 연산 메서드의 일종으로, 염색체의 적합도의 비로 전체 세대를 비례 배분하여 룰렛휠에서 각 염색체가 차지하는 지분을 결정하고 룰렛휠의 범위 내에서 난수를 생성하여 그 난수 범위에 해당되는 염색체를 선택한다. 이 때 각 염색체의 적합도 f_i는 다음과 같이 계산된다.
(C_w : 해집단 내의 가장 열등한 염색체의 비용, C_b : 해집단 내의 가장 우수한 염색체의 비용, C_i : 적합도를 구하고자 하는 염색체의 비용)
즉 룰렛휠에서의 염색체 i의 지분은 해집단 전체의 f값의 합에 대한 f_i의 비로서 결정된다. 이 룰렛휠은 0에서부터 해집단 전체의 f 합까지의 난수를 생성하고, 그 난수가 소속된 범위를 갖는 염색체를 선택한다. 이 선택은 프로그래머가 원하는 만큼의 염색체를 남길 때 까지 계속한다.
이 외에도 순위 기반 선택 연산 등이 존재한다.
교차 연산
자연선택된, 살아남은, 선택 연산을 통과한 생명체, 염색체들은 감수분열과 교배를 통해 자신을 닮고 또 다른 자손을 만들어낸다. 유성 생식을 하는 생명체들의 특징이자 강점이다. 이 과정에서 모체와 부체의 염색체가 섞이게 된다. 이 과정으로 말미암아 생명체는 환경에 적응하고, 환경을 이겨내고 살아남았으며, 이는 우리의 알고리즘에도 적용될 것이다.
- n점 교차
n점 교차는 보통 일점 교차와 다점 교차로 나누어 칭하지만, 방법은 크게 다르지 않기에 본 포스팅에서는 합쳐 설명하도록 하겠다. n점 교차는 염색체를 섞는 교차 연산의 대표적인 메서드로, 점의 개수, 즉 n이 높을수록 유전자를 섞는 '교란'의 정도가 높아져 보다 넓은 공간을 탐색할 수 있지만-반대급부로 정답에 수렴하는 시간이 낮아진다는 단점이 있다. n점 교차는 선택된 두 염색체를 n개의 점으로 나누고, 점을 지나면 다음 세대로 넘기는 유전자를 달리 하는 방법을 사용한다. 예를 들어, 첫번째 점 이전까지는 첫번째 염색체를 유전자를, 첫번째 점과 두번째 점 사이는 두번째 염색체의 유전자를 남기고 그 뒤는 다시 첫번째 염색체의 유전자를 후대로 남기는 방법이다.
- 균등 교차
균등 교차는 간단한 교차 연산 메서드로, 선택압 k를 설정하고 이와 같은 정의역을 갖는 난수 p를 선택된 두 염색체의 각 유전자에 대해 생성하여 k>p이면 우수한 비용을 갖는 염색체의 유전자를, k<p이면 낮은 비용을 갖는 염색체의 유전자를 유전시킨다. 프로그래머는 이 k값을 통해 우수한 염색체를 얼마나 남길 지 결정할 수 있어 이를 선택압이라 부른다. 이 선택압 값은 주로 0.6을 사용한다
변이 연산과 유전적 다양성
누차 말하지만, 진화가 목표치까지 도달하지 못하고 끝나게 되지 않게 하려면 유전적 다양성을 유지해야 한다. 이는 선택 연산과 교차 연산을 통해 이루어지는 것뿐만 아닌, 염색체 자체에 변동을 주는 과감함이 필요하다. 생태계의 돌연변이를 본딴 변이 연산은 이 유전적 다양성을 유지하게끔 한다. 또한, 변이가 종의 진화에 좋은 영향을 끼치지 않을 것을 걱정할 수 있다. 하지만 그 변이가 좋은 영향을 주는 변이라면 살아남을 터이지만 나쁜 영향을 끼친다면 자연스레 도태될 것이기에 걱정할 필요는 없다.
비균등 변이
보통 학습의 초반부에는 큰 변이가 유용하다. 하지만 학습의 후반부로 갈수록 변이는 종 전체의 진화보다는 안정된 세대의 혼동을 부를 뿐이다. 이를 방지하기 위해 변이에 약간의 시간적 보정을 더한 것이 비균등 변이이다. 비균등 변이는 유전자 v와 이진 난수 r에 대해 아래 식을 통해 이루어진다.
(여기서 UB와 LB는 각각 변이의 최대치와 최소치를 나타내고, T는 전체 세대 수, t는 현재 세대 수를 나타낸다.)
유전 알고리즘의 사용
유전 알고리즘은 해를 염색체의 꼴로 나타낼 수 있을 때 사용 가능하고, 또한 이를 적합도 함수로 평가할 수 있을 때에 사용 가능하다(위키백과 발췌), 또한 해를 통해 접근하는 방식을 취하기에 데이터세트의 양이 방대하여 해를 구하는 데에 오랜 시간이 소요되는 문제의 경우 유전 알고리즘이 주로 사용된다.
