유전 알고리즘(Genetic Algorithm)

유전 알고리즘이란?

유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다. 출처 : 위키백과

유전 알고리즘은 선택(Selection), 변이(Mutation), 교차(Crossover)기법을 사용할 수 있다.

선택(Selection)

한 세대에서 다음 세대로 전해지는 해의 후보가 되는 해들을 선택한다. 선택 방법에는 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다. 해의 선택은 유전 알고리즘의 성능에 큰 영향을 미친다. 어떤 방법을 쓰느냐에 따라 최적해로 다가가는 속도가 더디게 되거나, 아니면 지역 최적해에 빠지는 경우가 생길 수도 있기 때문이다. 또는 우수한 해가 보유한 나쁜 인자가 전체 인구에 퍼지거나, 반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있다. 따라서 어떤 해를 선택하는지는 유전 알고리즘의 성능을 위해서 중요한 요소라고 할 수 있다. 일반적으로는 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법이 많이 사용된다. 이는 반대로 말하면, 나쁜 해라 할지라도 그 해에 포함된 좋은 인자를 퍼뜨릴 기회를 준다고 볼 수 있다. 현 세대에서 가장 좋은 해라 할지라도 실제로는 지역 최적해에 가까운 해일 수도 있고, 반대로 좋지 않은 해라 할지라도 전역 최적해에는 더 가까울 수도 있기 때문이다. 실제로 전역 최적해가 어디에 있는지는 알 수 없는 일이므로, 가능한 해들의 평균적인 적합도를 높여 가면서도 유전자의 다양성을 유지하는 것이 지역 최적해에 빠지는 것을 가능한 한 방지하는 방법이며, 이는 실세계의 생명체들 역시 유전적 다양성을 유지하는 종이 장기적인 생존 가능성이 높은 것과 비견할 수 있다.

변이(Mutation)

일반 생명체에서, 유전자의 교차 뿐 아니라, 하나의 유전자가 직접적으로 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다. 변이 연산은 주어진 해의 유전자 내의 유전 인자의 순서 혹은 값이 임의로 변경되어 다른 해로 변형되는 연산이다. 해의 유전자들을 가상의 공간에 맵핑할 경우 교배 연산은 부모해들 사이의 어떤 지점에 자식해를 생성하는 것이라고 볼 수 있다면, 변이 연산은 임의의 위치로 점프하는 것에 비견할 수 있다. 따라서 약간의 확률로 변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하기 위한 주요한 기법이 될 수 있으며, 해집단의 다양성을 높여준다.

교차(Crossover)

생명체는 세대 내에서의 교배를 통해 다음 세대를 생성한다. 이와 마찬가지로 유전 알고리즘에서 자연 선택된 해들은 교배를 통하여 다음 세대의 해들을 생성하게 된다. 일반적으로 두 개의 해를 선택한 후 둘 간에 교배 연산을 수행하게 되며, 이를 통해 생성된 해는 각각의 부모 해의 교차 연산을 통해서 서로 겹치지 않는 위치의 유전인자를 받아 새로운 유전자를 구성하게 된다. 실제 생명체의 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다. 유전 알고리즘의 교차 연산은 이 현상을 본따, 부모 해의 유전자들을 서로 교차시켜서 자식해를 만들어낸다. 교차 연산의 실제 수행 방법은 비트 단위 교차에서부터 블록 단위 교차까지 다양한 방법으로 구현할 수 있으며, 교차를 한 번만 수행할지 전 영역에 대해서 교차시킬지 역시 결정할 수 있다. 또한 모든 해에 대해 교차연산을 수행할 경우 우수한 해가 다른 해와의 교배를 통해서 우수성을 잃어버림에 따라 세대의 최고 우수해가 보존되지 않는 상황이 발생할 수 있다. 이런 경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는 방법도 사용된다.

이런것들의 최적화 과정은 진화적합성(Evolutionary fitness)와 적응형 위상(Adaptive topology)가 있다.

진화적합성(Evolutionary fitness) : 주어진 test case들이 생존해서 교배를 하여 재생산하고, 이를 바탕으로 집단의 능력을 유지 향상 시키는 과정.

적응형 위상(Adaptive topology) : 진화 적합성에서 유지 향상된 test case를 선택하여 이러한 test case에 적합한 값(fitness)을 이용.

"개채 집단 생성 > 적합도 평가 > 유전 연산자 적용 > 새로운 집단 생성"의 과정이 반복된다.

negative test case와 positive test case에 대한 인코딩(encode)과 평가(fitness evaluation)를 사용한다. 

적합도 함수(Fitness function)는 genotype을 사용해서 실행가능한 프로그램(executable program)에서 내부 표현(internal representation)을 컴파일하고 positive test 와 negative test case를 셋트로 재실행한다.

Positive test case란?

우리는 프로그램의 핵심 기능을 인코딩하기 위해 프로그램의 기존 테스트 입력 및 oracle의 하위 집합을 사용하고이를 positive test case라고 부릅니다.

Negative test case란?

우리는 결함을 입증하는 입력 및 비정상적인 출력 (즉, 수정하려는 버그)을 negative test case라고 부릅니다.

유전(gene)또는 basic unit으로 되어있는 문장(statement)같은것을 절차적 단계에 선택(Selection)과 교차(Crossover), 변이(Mutation)연산을 사용한다. 

적합성 평가(Evaluation fitness)

Positive test case와 Negative test case를 실행하여 적합성을 찾는 Fitness function을 생성하여 평가한다.

1단계 : 에러가 난 부분을 어떻게 표현할것인지 선택(Encoding)하고 이러한 집단의 크기(population size)는 각자가 원하는 크기로 정하고, 변이율(Mutation probability)과 교차율(Crossover probability)를 설정한다.

2단계  : 적합도(fitness)를 측정하는 함수를 정의한다.

3단계 : 염색체(gene