오늘의유머 - 알고리즘에 진화의 아이디어를 접목시키기

진화론 이야기가 나온 김에 심심해서 예에에에전에 짠 유전 알고리즘 코드를 예토전생 시켜서 소개해봅니다.

별 생각이 없어서 (사실은 배고파서) 다소 말주변이 없어 보이는 점 양해 부탁드립니다.

+ 스압 주의.

인간의 지능은 다른 동물들보다 높다는 걸 잘 알고계실 겁니다. 그렇다면 인간은 어떻게 이런 높은 지능을 가지게 되었나라는 의문을 가질 만합니다.

당연히 누가 인위적으로 그렇게 만들어준 건 아니고(이를 진지하게 믿는 사람이 있지만 이 글에선 넘어가도록 합시다) 진화를 해서 그렇죠.

유전 알고리즘은 바로 이 진화의 개념을 알고리즘으로 구현한 것입니다.

함수 f(x, y, z, ...)이 있습니다. 우리가 원하는 건 f의 최댓값인데, 문제는 함수가 너무 복잡한 나머지 f의 최댓값은 물론 f가 최대가 되도록 하는 x, y, z, ...를 적당한 수학적 계산을 통해서는 도저히 못 구하겠다는 거죠. 어떻게 할까요? 유전 알고리즘은 다음과 같은 방법으로 답을 찾아 나갑니다.

0. x, y, z, ...를 유전자로 하는 인공 생명체를 생각합니다.

1. 태초에 적당한 유전자(대충 랜덤하게 줬습니다)를 가진 생명체들이 있었습니다.

2. 각 생명체의 유전자에 대해 f의 값을 계산해서 높은 순서대로 줄을 세웁니다.

3. 'f 값이 높다'를 '주변 환경에 잘 적응한다'로 정의하고, 주변 환경에 잘 적응하는 상위 몇 마리만 남기고 죽입니다(!)

4. 살아남은 생명체끼리 교배시킵니다. 이때, (생식세포 감수분열 할 때 처럼) 부모 유전자 사이에 교차를 시켜서 자식의 유전자를 만듭니다.

4-1. 필요하다면 돌연변이도 생성합니다.

5. 부모 + 자식으로 생긴 새로운 집단으로 다시 2로 돌아갑니다. 만족할 만한 결과가 나올 때 까지 반복합니다.

예시 하나 들어볼게요.

a1, a2, ... , a6는 1부터 5까지의 정수값을 가질 수 있다. a1 + (a2 - a3) * (a4 % a5) - a6의 값을 최대로 하는 a1, a2, ... , a6값을 구하시오.

(여기서 %는 나머지 연산입니다. a4 % a5 는 a4를 a5로 나눈 나머지.)

0. 인공 생명체를 생각합시다. 이 인공 생명체는 1부터 5까지의 정수값 6개를 유전자로 가집니다.

1. 적당히 생명체를 만듭시다.

Generation 0 : -0.875

515515 (0)

355432 (1)

235414 (-2)

442221 (3)

425454 (-12)

331332 (1)

444545 (-1)

332525 (-1)

545225 (0)

333555 (-2)

442235 (3)

131222 (-1)

145412 (-1)

323142 (0)

321412 (1)

144154 (-3)

프로그램을 실행시켜서 나온 제 0 세대입니다. 생명체는 총 16마리고, 각 생명체는 6자리 정수 배열을 가집니다.

일단은 모든 유전자를 랜덤으로 주었습니다.

뒤쪽 괄호 안 숫자는 우리가 최대로 만들고 싶은 바로 그 함수의 값입니다. 제일 위 세대 표시 오른쪽은 모든 개체들의 평균 함수 값입니다.

보면 알겠지만, -12인 것도 있고 0인 것도 있죠. 총체적 난국입니다.

이제부터 진화를 시작하겠습니다.

2. 줄을 세웁니다.

Generation 0 : -0.875

442221 (3)

442235 (3)

355432 (1)

331332 (1)

321412 (1)

515515 (0)

545225 (0)

323142 (0)

444545 (-1)

332525 (-1)

131222 (-1)

145412 (-1)

235414 (-2)

333555 (-2)

144154 (-3)

425454 (-12)

줄을 세워봤습니다. -12가 좀 많이 독보적이군요?

3. 몇 마리만 남깁니다.

Generation 0 : -0.875

442221 (3)

442235 (3)

355432 (1)

331332 (1)

321412 (1)

515515 (0)

프로그램 상에서는 6마리만 남기도록 했습니다.

4. 남은 개체들을 교배시킵니다.

여기서 교배라는 건, 두 유전자를 섞어서 새 유전자를 만드는 겁니다.

421353과 511551를 선택했다고 가정합시다.

부모 1 : 421353

부모 2 : 511551

자식 : ******

여기서 자식의 각 유전자는 양쪽 부모 중 한 쪽에서 물려받게 됩니다. 어느 쪽에서 물려받는지는 완전히 랜덤입니다. 가능한 한 경우는 다음과 같습니다.

부모 1 : 421353

부모 2 : 511551

자식 : 411553

빨간색은 부모 1, 파란색은 부모 2에게서 물려받았습니다.

4-1. 필요하다면 돌연변이도 생성합니다.

돌연변이도 진화의 중요한 원동력입니다. 일정 확률로 돌연변이를 만들어 줍시다.

부모 1 : 421353

부모 2 : 511551

자식 : 412553

3번째 1을 2로 바꾸었습니다.

5. 새 집단을 가지고 2로 돌아갑니다.

일단 제 1 세대를 보시죠.

Generation 1 : 1.062

442221 (3)

442235 (3)

355432 (1)

331332 (1)

321412 (1)

515515 (0)

442235 (3)

321412 (1)

315515 (-2)

355421 (2)

445515 (-1)

442512 (2)

515535 (-8)

542235 (4)

442232 (6)

321412 (1)

저번보다 평균 함숫값이 증가했습니다. 계속 진화시킵니다.

Generation 2 : 3.688

442232 (6)

542235 (4)

442221 (3)

442235 (3)

355421 (2)

355422 (1)

352235 (4)

442235 (3)

542232 (7)

442235 (3)

442221 (3)

442235 (3)

442232 (6)

452235 (5)

442235 (3)

Generation 3 : 5.312

542232 (7)

442232 (6)

452235 (5)

542235 (4)

352235 (4)

542232 (7)

542235 (4)

452235 (5)

442232 (6)

442235 (3)

352232 (7)

======

Generation 8 : 6.875

542232 (7)

352232 (7)

542232 (7)

352232 (7)

542132 (5)

542232 (7)

제 8 세대까지 진행시키면 거의 유전자들이 똑같아집니다. 대부분의 개체가 환경에 적합해진다는 거죠. 그리고 적합하지 못했던 개체는 도태되어 사라졌습니다.

======

Generation 12 : 7.500

552232 (9)

542232 (7)

352232 (7)

542232 (7)

552232 (9)

542232 (7)

552232 (9)

542232 (7)

352232 (7)

542234 (5)

542232 (7)

물론 진화는 여기서 끝나지 않습니다. 계속 좋아지고 있네요.

======

Generation 14 : 9.000

552232 (9)

모든 개체의 유전자가 동일해진 시점입니다. 여기선 더이상 교배만으로는 새로운 유전자가 탄생하지 않습니다.

그래서 이게 답이냐, 하면 그렇지 않습니다. 유전 알고리즘의 맹점이죠.

유전 알고리즘은 "전역적 최대점"을 보장하지 않습니다. 우리가 구한 건 지역적 최소점이죠.

왼쪽 동그라미가 전역적 최대점, 오른쪽이 지역적 최대점입니다.

이 상황을 타파하기 위해서 돌연변이가 존재합니다. 적자생존만으로는 완벽한 진화에 다가가기 힘듭니다.

======

Generation 16 : 6.750

552232 (9)

213432 (-2)

552232 (9)

212232 (-2)

552212 (3)

552232 (9)

513432 (1)

552232 (9)

돌연변이가 나타났습니다. 근데 -2로, 정작 더 값이 낮아져버렸습니다.

Generation 17 : 9.000

552232 (9)

좋은 유전자가 아니니 그 다음 세대에서 자연히 도태됩니다.

======

이후로도 더 진행해봤는데, 도저히 9에서 더 올라가질 않아서 새로 시도해봤습니다.

Generation 0 : -0.125

453533 (5)

151111 (0)

252352 (9)

444145 (-1)

324132 (-1)

442324 (2)

311145 (-2)

131443 (-2)

115215 (-4)

334144 (-2)

112442 (-1)

545333 (2)

531413 (2)

112252 (-3)

342253 (4)

114535 (-10)

======

Generation 5 : 11.000

452352 (11)

11까지 올라갔습니다.

======

Generation 10 : 10.812

452352 (11)

451352 (14)

452352 (11)

452152 (5)

제 10 세대에서 돌연변이가 두 개 일어났습니다. 이대로 한 세대 더 진행시키면?

Generation 11 : 4.625

451352 (14)

452352 (11)

214144 (-5)

212352 (-3)

451352 (14)

212352 (-3)

451344 (12)

451352 (14)

214144 (-5)

452344 (9)

212352 (-3)

214352 (-9)

돌연변이가 폭탄이군요. 유전자들이 완전히 뒤죽박죽이 되었습니다.

======

Generation 20 : 13.188

451352 (14)

451342 (14)

451352 (14)

411342 (2)

451352 (14)

451342 (14)

451352 (14)

351352 (13)

제 20 세대입니다. 14에서 고정되어버렸군요.

참고로 최댓값은 5 + (5 - 1) * (4 % 5) - 1 = 20 입니다.

마무리(?).