[AI] Genetic Algorithm

Genetic Algorithm

1. n-Queen Problem

 1) 문제 정의 : N x N 크기의 체스판이 주어질 떄, N개의 퀸이 서로 공격이 불가능하도록 놓는 경우를 구하는 문제

 2) ex : N = 4

		Q
Q
			Q
	Q

2. Genetic Algorithm

 1) Fitness function으로 Fitness 검사 : 어느 정도 해에 가까운지 수치값으로 나타내는 함수로 수치값을 계산

 2) 검사된 결과 중 가장 높은 값은 두 개, 다음 높은 순으로 두 개를 뽑아 서로 형질을 바꾼다.(유전)

 3) 거기에 랜덤(자리, 번호 둘다)으로 형질을 바꿔준다.(돌연변이)

   ex) ①( 3 3 4 2 )   4  4/7      ①( 3 3 | 4 2 )           ( 3 3 | 1 2 )          ( 3 ① 1 2 )

        ②( 1 2 1 2 )   1  1/7      ②( 1 2 | 1 2 )           ( 1 2 | 4 2 )          ( 1 2 4 2 )

        ③( 1 2 3 4 )   0  0/7      ①( 3 | 3 4 2 )           ( 1 | 3 4 2 )          ( 1 3 4 ④ )

        ④( 1 1 1 3 )   2  2/7      ④( 1 | 1 1 3 )           ( 3 | 1 1 3 )          ( 3 1 ③ 3 )

               ⓐ                                ⓑ                       ⓒ                      ⓓ

   ⓐ         : Fitness 검사 : 두개씩 퀸을 페어로 봤을 때 서로 공격이 불가능 한 페어의 개수를 센 값이 클수록 Fitness가 높다.

   ⓑ ~ ⓒ  : 유전 나누는 구간을 랜덤으로 정해 서로 바꾼다(위 예제에선 ①이랑 ②, ③ 이랑 ④를 바꿨다)

   ⓓ         : ⓒ가 끝난 뒤, 특정 지점의 번호를 바꿔준다.(돌연변이)

3. 장단점

 1) 장점

   ① 거의 최적에 가까운 해(near optimal)를 빠르게 찾아낼 수 있다.

   ② parallel 작업이 가능하다

 2) 단점

   ① 어떤 방식으로 최적을 구했는지 재현이 거의 불가능하다.