[ML Algorithm] 인공지능 - 유전 알고리즘

1. 유전 알고리즘

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

 

“어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulate devolution) 탐색 알고리즘”

-> 유전알고리즘

 

 

2. 유전 알고리즘 구조

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

진화연산의 특징

집단성 : 개체 다수를 집단으로 설정해 동시에 탐색할 때는 병렬 연산 탐구 가능성 :  탐색 공간( 설명 변수와 목적 변수 등이 취할 수 있는 값의 범위)의 자세한 사전 지식을 요구하지 않는다. 다양성 : 집단에 있는 개체의 다양성으로 노이즈와 동적 변화에 적응성을 갖게 되므로 견고한 답을 얻을 수 있다.

 

3. 유전 알고리즘 용어와 알고리즘 흐름

- 유전 알고리즘에는 특유의 용어가 있음

- 일부 용어는 옛날부터 알려진 진화론과 유전학 용어를 그대로 사용

- 유전 알고리즘 안 유전학 용어가 데이터의 성격을 설명한다

 

 

유전알고리즘의 흐름

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

 

 

4. 평가

- 적합도 평가를 통해 세대를 교체할 지 적합도 평가를 종료할지 결정

- 이때 종료여부, 즉 수렴했다고 간주할지는 다음 조건에 따라 결정

• 집단 안 개체 중 적합도가 최대인 것이 임계치(알고리즘 사용자가 정한 목표 적합도)를 초과
• 집단 전체의 평균 적합도가 임계치를 초과
• 집단 안의 적합도 증가율이 일정 기간 임계치 아래에 있음
• 세대교체 횟수가 일정 수에 도달(중단)

5. 세대교체 

 

5.1. 도태

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

 

5.1 도태 방법

1. 룰렛 휠 선택

- 개체의 적합도에 따라 개체 선택 가능성이 바뀌므로 개체를 무작위로 선택해도 선택 결과가 한쪽으로 치우치는 상태가 된다

2. 토너먼트 선택

- 집단 안의 일부 개체를 무작위로 선택한 후 가장 적합도가 높은 개체를 남기는 방식으로 집단 안의 일부 개체를 무작위로 선택한 후 가장 적합도가 높은 개체를 남기는 방식으로 집단 전체수에 해당하는 개체를 얻을 때까지 반복

3. 엘리트 선택

- 집단에서 적합도가 높은 순으로 nG개의 개체를 남기고 그 외 n(1-G)개의 개체에 유전자 조작을 추가하는 방식

- G를 엘리트율, 1-G를 생식률

 

 

 

5.2. 교차

- 교차? 부모의 유전자를 재조합해 자식 둘을 생성하는 것

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

 

-  이진 인코딩(binary encoding) : 유전자가 0과 1로 구성된 염색체

But 데이터 내용의 순서나 실제 값을 나타낼 필요가 있을 때, 이진 인코딩은 불편한 점이 있다.

• 해결방법 : 유전자를 순열 인코딩(permutation encoding) or 값 인코딩(value encoding)으로 표현

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

 

 

5.3. 돌연변이

- 돌연변이? 부모의 유전자를 재조합해 자식 한 명을 생성하는 것으로 적합도를 높인다는 하나의 기준

- 개체를 다루는 도태나 교차와 달리 돌연변이는 무작위 탐색에 가깝다

-> 포괄적으로 개체를 다뤄서 최적 해결책을 찾는다는 효과가 있음

- 돌연변이가 일어날 확률을 돌연변이율, <- 교차를 일으킬 확률보다 훨씬 낮은 값으로 설정

- 인공신경망의 dropout과 같다? 

 

 

 

 

*유전 알고리즘 사용 예 -> 외판원 문제

 

 

 

출처

1. 처음배우는 인공지능, 타다 사토시