16. 유전자 알고리즘 (Genetic Algorithm)

유전자 알고리즘 (Genetic Algorithm)

 

 

문제에 대한 해를 표현하는 염색체가 집단을 이루어 해집단을 구성하고 유전 알고리즘의 진행 과정속에서 부모 세대와 자식 세대의 역할을 반복적으로 하게 된다.

 

유전 알고리즘은 생물이 살아가면서 교차, 돌연변이, 도태 등으로 환경에 적합하도록 진화한다는 가설에 기반을 둔 최적화 기법이다. 시간 축 상에서 여러 번 계산을 반복해 단계 수를 쌓아서 궁극적으로 구하고 싶은 결과에 수렴한다. 진화 연산의 과정에서 교차와 돌연변이 등 진화론 아이디어를 도입한 계산 방식이다.

 

진화 연산

 

1. 집단성 : 개체 다수를 집단으로 설정해 동시에 탐색할 때는 병렬 연산한다.

2. 가능성 :  탐색 공간( 설명 변수와 목적 변수 등이 취할 수 있는 값의 범위)의 자세한 사전 지식을 요구하지 않는다. 

3. 다양성 : 집단에 있는 개체의 다양성으로 noise와 동적 변화에 적응성을 갖게 되므로 견고한 답을 얻을 수 있다.

 

전자 알고리즘의 흐름

 

집단 전체수를 N으로 하는 초기화를 실행한다. 적합도를 계산해 평가를 진행, 적합도 평가의 결과를 낼 때는 미리 정해 높은 종료 조건으로 검사한다. 종료 조건에 부합, 즉 수렴한다고 판정되면 종료한다. 그렇지 않으면 다음작업 (세대교체)으로 이동한다. 세대교체는 도태 (Selection), 교차 (Crossover), 돌연변이 (Mutation) 등 세 가지 종류가 있으며 개체에 맞는 세대교체를 할당한다. 남아 있거나 생성된 개체는 다음 세대의 개체가 되고 다시 적합도를 평가한다. 이 과정을 반복한다.

 

알고리즘 평가

 

◦ 적합도 평가를 통해 세대를 교체할지 적합도 평가를 종료할지 결정한다. ◦ 이때 종료여부, 즉 수렴했다고 간주할지는 다음 조건에 따라 결정한다. 집단 안 개체 중 적합도가 최대인 것이 임계치(알고리즘 사용자가 정한 목표 적합도)를 초과인 경우 집단 전체의 평균 적합도가 임계치를 초과인 경우 집단 안의 적합도 증가율이 일정 기간 임계치 아래에 있는 경우 세대교체 횟수가 일정 수에 도달 (중단)한 경우

 

세대 교체

 

1. 도태 

 

유전자 알고리즘에서는 적합도가 높은 개체를 선택해 남기면 다음 세대가 되었을 때 집단 안에서 더 최적 해결책에 가까운 개체가 많아지는 상태를 만들 수 있다.

 

- 도태 방법 1. 룰렛 휠 선택 : 개체의 적합도에 따라 개체 선택 가능성이 바뀌므로 개체를 무작위로 선택해도 선택 결과가 한쪽으로 치우치는 상태가 된다. 2. 토너먼트 선택 :집단 안의 일부 개체를 무작위로 선택한 후 가장 적합도가 높은 개체를 남기는 방식으로 집단 안의 일부 개체를 무작위로 선택한 후 가장 적합도가 높은 개체를 남기는 방식으로 집단 전체 수에 해당하는 개체를 얻을 때까지 반복한다. 3. 엘리트 선택 : 집단에서 적합도가 높은 순으로 nG개의 개체를 남기고 그 외 n(1-G)개의 개체에 유전자 조작을 추가하는 방식이다. G를 엘리트율, 1-G를 생식률로 정한다.

 

2. 교차

 

부모의 유전자를 재조합해 자식 둘을 생성하는 것이다. 유전자를 변형해 자식을 생성 할 때 부모의 유전자를 어떻게 이용하느냐에 따라 1점 교차, 다점교차, 균등 교차로 분류, 이외에 자식 하나만 생성하는 평균 교차로 분류한다.

 

이진 인코딩 (binary encoding) : 유전자가 0과 1로 구성된 염색체라고 할 때 데이터 내용의 순서나 실제 값을 나타낸다. 이진 인코딩은 유전자를 순열 인코딩 (permutation encoding) 또는 값 인코딩 (value encoding)으로 표현한다.

 

- 1점교차 (one point crossover) : 어떤 유전자 위치를 경계로 부모의 유전자를 바꿔 자식 생성한다. - 다점 교차 (multi point crossover) : 염색체 위에 1점 교차의 경계를 복수로 설정해 자식 생성한다. - 균등 교차 (uniform crossover) : 0은 확률 p, 1은 확률 1-p로 설정한 후 부모의 유전자를 바꿔 자식을 생성한다. - 평균 교차 (average crossover) : 부모 유전자의 평균치를 자식의 유전자로 한다.

 

3. 돌연변이

 

부모의 유전자를 재조합해 자식 한 명을 생성하는 것으로 적합도를 높인이는 기준이다. 개체를 다루는 도태나 교차와 달리 돌연변이는 무작위 탐색에 가깝다. 따라서 포괄적으로 개체를 다뤄 최적 해결책을 찾는 효과가 있다. 돌연변이가 일어날 확률을 돌연변이율이라고 할 때 교차를 일으킬 확률보다 훨씬 낮은 값으로 설정한다. 인공신경망의 dropout과 같다.