유전 알고리즘(Genetic Algorith) #2. 유전 연산자의 종류

유전 연산자(Genetic Operators)

개요

유전 알고리즘에서 개체를 진화시키기(?) 위해서 유전 연산자를 이용하고 있습니다.

유전 연산자에는 선택, 교배, 변이가 있습니다.

■  선택은, 높은 적합도를 보이는 상위 염색체들을 확률적으로 선택하여 다음 세대에 사용합니다.

■  교배는, 선택된 염색체들을 서로간 교배를 통하여 새로운 구조를 가지는 염색체를 만들어냅니다.

■  변이는, 교배를 통한 재조합이 끝난 후 일부를 바꾸어주는 과정(자연계 생명체 유전자의 돌연변이 과정)

선택, 교배, 변이의 각각의 과정들은 다양한 방법과 형태들이 있으나, 저는 제가 아는 지식의 범위 내에서 대표적으로 판단되는 몇가지들을 소개하고자 합니다.

선택 연산자(Selection)

Roulette wheel selection

각 염색체의 적합도에 비례하는 만큼 roulette의 영역을 할당한 다음, roulette을 돌려 화살표가 가리키는 영역의 염색체를 선택합니다.

적합도가 높은 것은 선택될 확률이 그만큼 많고 적합도가 낮을 것은 선택될 확률이 상대적으로 낮아집니다.

Ranking selection

적합도의 크기 순서에 따라 순위를 매기고 순위에 따라 확률을 결정합니다.

여기서의 확률은 Roulette wheel selection과 달리 순위에 의해 사전에 결정된 확률입니다.

Elitist preserving selection

가장 적합도가 높은 개체는 다음 세대에도 그대로 살려둡니다.

Tournament selection

임의의 수의 개체를 무작위로 선택하며, 그 가운데 접합도가 높은 개체를 다음 세대로 넘깁니다.

교배 연산자(Crossover)

단순교차(Simple Crossover)

하나의 교차위치 설정하며, 그 전후를 기준으로 부모의 유전자형을 교환합니다.

복수점교차(Simple Crossover)

교차위치가 복수인 경우이며, 그림과 같이 기준을 전후로 부모의 유전자형을 교환합니다.

일정교차(Uniform Crossover)

마스크를 사용하여 어느 쪽의 유전자를 받아들일지 결정합니다.

예를 들어 마스크에서 ‘0’인경우는 그대로 유전자를 전달하며, ‘1’인 경우, 유전자를 교환합니다.

일명 필터링이라고도 합니다.

산술교배(Arithmetic Crossover)

실수 표현(Value Encoding)일 경우 사용 가능하며, 염색체의 각 위치에 대해 두 부모 염색체 유전자의 평균값을 이용합니다.

일반적으로 매우 빠른 수렴을 보이므로, 변이 등을 적절히 조절하여 설익은 수렴이 되지 않도록 주의해야합니다.

변이 연산자(Mutation)

유전자를 일정한 확률로 변화시키는 조작입니다.

부모해가 가지지 못한 성질을 부여하여 탐색범위를 확보합니다. 이는 전역적 탐색효과를 극대화 시킵니다(Maximize Global Search).

변이는 집단의 다양성 증대시킵니다. 돌연변이가 없다면, 초기 유전자 조합 이외에 공간을 탐색할 수 없기 때문에 적절하지 않은 초기 조합을 선택하게 되면 원하는 해를 구할 수 없습니다(Local Optimum 방지).

각 유전자 별로 난수를 발생하여 미리 설정한 변이 확률보다 작으면 변이시킵니다.

일반적으로 정적변이와 정적변이가 있습니다.

■  정적 변이는 돌연변이의 확률을 일정하게 고정합니다.

■  동적 변이는 초기 품질이 좋지 않은 해가 많으므로 변이의 강도를 높이며, 후반에는 변이가 강할 경우 품질 향상이 일어나지 않으므로 변이의 강도를 낮춥니다.

변이의 확률이 높아지면,

다양한 해 생성에 의해 유전 알고리즘의 역동성이 높아집니다.

그러나 반대로 수렴성이 떨어져 수행 시간이 많이 걸립니다.