진화론 이야기가 나온 김에 심심해서 예에에에전에 짠 유전 알고리즘 코드를 예토전생 시켜서 소개해봅니다. <div>별 생각이 없어서 (사실은 배고파서) 다소 말주변이 없어 보이는 점 양해 부탁드립니다.</div> <div><br></div> <div>+ <b>스압</b> 주의.<br><div><br></div> <div><br></div> <div>인간의 지능은 다른 동물들보다 높다는 걸 잘 알고계실 겁니다. 그렇다면 인간은 어떻게 이런 높은 지능을 가지게 되었나라는 의문을 가질 만합니다.</div> <div>당연히 누가 인위적으로 그렇게 만들어준 건 아니고(이를 진지하게 믿는 사람이 있지만 이 글에선 넘어가도록 합시다) 진화를 해서 그렇죠.</div> <div><br></div> <div>유전 알고리즘은 바로 이 진화의 개념을 알고리즘으로 구현한 것입니다.</div> <div><br></div> <div>함수 f(x, y, z, ...)이 있습니다. 우리가 원하는 건 f의 최댓값인데, 문제는 함수가 너무 복잡한 나머지 f의 최댓값은 물론 f가 최대가 되도록 하는 x, y, z, ...를 적당한 수학적 계산을 통해서는 도저히 못 구하겠다는 거죠. 어떻게 할까요? 유전 알고리즘은 다음과 같은 방법으로 답을 찾아 나갑니다.</div> <div><br></div> <div><b>0</b>. x, y, z, ...를 유전자로 하는 인공 생명체를 생각합니다.</div> <div><br></div> <div><b>1</b>. 태초에 적당한 유전자(대충 랜덤하게 줬습니다)를 가진 생명체들이 있었습니다.</div> <div><b>2</b>. 각 생명체의 유전자에 대해 f의 값을 계산해서 높은 순서대로 줄을 세웁니다.</div> <div><b>3</b>. 'f 값이 높다'를 '주변 환경에 잘 적응한다'로 정의하고, 주변 환경에 잘 적응하는 상위 몇 마리만 남기고 죽입니다(!)</div> <div><b>4</b>. 살아남은 생명체끼리 교배시킵니다. 이때, (생식세포 감수분열 할 때 처럼) 부모 유전자 사이에 교차를 시켜서 자식의 유전자를 만듭니다.</div> <div><b>    4-1</b>. 필요하다면 돌연변이도 생성합니다.</div> <div><b>5</b>. 부모 + 자식으로 생긴 새로운 집단으로 다시 2로 돌아갑니다. 만족할 만한 결과가 나올 때 까지 반복합니다.</div> <div><br></div> <div><br></div> <div>예시 하나 들어볼게요.</div></div> <div><br></div> <div>a1, a2, ... , a6는 1부터 5까지의 정수값을 가질 수 있다. a1 + (a2 - a3) * (a4 % a5) - a6의 값을 최대로 하는 a1, a2, ... , a6값을 구하시오.</div> <div>(여기서 %는 나머지 연산입니다. a4 % a5 는 a4를 a5로 나눈 나머지.)</div> <div><br></div> <div><b>0</b>. 인공 생명체를 생각합시다. 이 인공 생명체는 1부터 5까지의 정수값 6개를 유전자로 가집니다.</div> <div><br></div> <div><b>1</b>. 적당히 생명체를 만듭시다.</div> <div><br></div> <div><div>Generation 0 : -0.875</div> <div>515515 (0)</div> <div>355432 (1)</div> <div>235414 (-2)</div> <div>442221 (3)</div> <div>425454 (-12)</div> <div>331332 (1)</div> <div>444545 (-1)</div> <div>332525 (-1)</div> <div>545225 (0)</div> <div>333555 (-2)</div> <div>442235 (3)</div> <div>131222 (-1)</div> <div>145412 (-1)</div> <div>323142 (0)</div> <div>321412 (1)</div> <div>144154 (-3)</div></div> <div><br></div> <div>프로그램을 실행시켜서 나온 제 0 세대입니다. 생명체는 총 16마리고, 각 생명체는 6자리 정수 배열을 가집니다.</div> <div><span style="font-size:9pt;line-height:1.5;">일단은 모든 유전자를 랜덤으로 주었습니다.</span></div> <div><span style="font-size:9pt;line-height:1.5;">뒤쪽 괄호 안 숫자는 우리가 최대로 만들고 싶은 바로 그 함수의 값입니다. 제일 위 세대 표시 오른쪽은 모든 개체들의 평균 함수 값입니다.</span></div> <div><br></div> <div>보면 알겠지만, -12인 것도 있고 0인 것도 있죠. 총체적 난국입니다.</div> <div>이제부터 진화를 시작하겠습니다.</div> <div><br></div> <div><b>2</b>. 줄을 세웁니다.</div> <div><br></div> <div><div> <div>Generation 0 : -0.875</div> <div>442221 (3)</div> <div>442235 (3)</div> <div>355432 (1)</div> <div>331332 (1)</div> <div>321412 (1)</div> <div>515515 (0)</div> <div>545225 (0)</div> <div>323142 (0)</div> <div> <div>444545 (-1)</div> <div>332525 (-1)</div></div> <div> <div>131222 (-1)</div> <div>145412 (-1)</div></div> <div>235414 (-2)</div> <div>333555 (-2)</div> <div>144154 (-3)</div> <div>425454 (-12)</div></div> <div><br></div> <div>줄을 세워봤습니다. -12가 좀 많이 독보적이군요?</div> <div><br></div> <div><b>3</b>. 몇 마리만 남깁니다.</div> <div><br></div> <div> <div> <div>Generation 0 : -0.875</div> <div>442221 (3)</div> <div>442235 (3)</div> <div>355432 (1)</div> <div>331332 (1)</div> <div>321412 (1)</div> <div>515515 (0)</div></div> <div><br></div></div> <div>프로그램 상에서는 6마리만 남기도록 했습니다.</div></div> <div><br></div> <div><b>4</b>. 남은 개체들을 교배시킵니다.</div> <div><br></div> <div>여기서 교배라는 건, 두 유전자를 섞어서 새 유전자를 만드는 겁니다.</div> <div>421353과 511551를 선택했다고 가정합시다.</div> <div><br></div> <div>부모 1 : 421353</div> <div>부모 2 : 511551</div> <div>자식   : ******</div> <div><br></div> <div>여기서 자식의 각 유전자는 양쪽 부모 중 한 쪽에서 물려받게 됩니다. 어느 쪽에서 물려받는지는 완전히 랜덤입니다. 가능한 한 경우는 다음과 같습니다.</div> <div><br></div> <div><div>부모 1 : <b><font color="#ff0000">421353</font></b></div> <div>부모 2 : <b><font color="#366092">511551</font></b></div> <div>자식   : <b><font color="#ff0000">4</font><font color="#366092">115</font><font color="#ff0000">53</font></b></div></div> <div><b><font color="#ff0000"><br></font></b></div> <div>빨간색은 부모 1, 파란색은 부모 2에게서 물려받았습니다.</div> <div><br></div> <div><b>4-1</b>. 필요하다면 돌연변이도 생성합니다.</div> <div><br></div> <div>돌연변이도 진화의 중요한 원동력입니다. 일정 확률로 돌연변이를 만들어 줍시다.</div> <div><br></div> <div><div>부모 1 : <b><font color="#ff0000">421353</font></b></div> <div>부모 2 : <b><font color="#366092">511551</font></b></div> <div>자식   : <b><font color="#ff0000">4</font><font color="#366092">1</font><font color="#7030a0">2</font><font color="#366092">5</font><font color="#ff0000">53</font></b></div></div> <div><br></div> <div>3번째 1을 2로 바꾸었습니다.</div> <div><br></div> <div><b>5</b>. 새 집단을 가지고 2로 돌아갑니다.</div> <div><br></div> <div>일단 제 1 세대를 보시죠.</div> <div><br></div> <div>Generation 1 : 1.062</div> <div><div>442221 (3)</div> <div>442235 (3)</div> <div>355432 (1)</div> <div>331332 (1)</div> <div>321412 (1)</div> <div>515515 (0)</div> <div>442235 (3)</div> <div>321412 (1)</div> <div>315515 (-2)</div> <div>355421 (2)</div> <div>445515 (-1)</div> <div>442512 (2)</div> <div>515535 (-8)</div> <div>542235 (4)</div> <div>442232 (6)</div> <div>321412 (1)</div></div> <div><br></div> <div>저번보다 평균 함숫값이 증가했습니다. 계속 진화시킵니다.</div> <div><br></div> <div><div>Generation 2 : 3.688</div> <div>442232 (6)</div> <div>542235 (4)</div> <div>442221 (3)</div> <div>442235 (3)</div> <div>442235 (3)</div> <div>355421 (2)</div> <div>355422 (1)</div> <div>352235 (4)</div> <div>442235 (3)</div> <div>542232 (7)</div> <div>442235 (3)</div> <div>442221 (3)</div> <div>442235 (3)</div> <div>442232 (6)</div> <div>452235 (5)</div> <div>442235 (3)</div></div> <div><br></div> <div><div>Generation 3 : 5.312</div> <div>542232 (7)</div> <div>442232 (6)</div> <div>442232 (6)</div> <div>452235 (5)</div> <div>542235 (4)</div> <div>352235 (4)</div> <div>542232 (7)</div> <div>542235 (4)</div> <div>452235 (5)</div> <div>452235 (5)</div> <div>452235 (5)</div> <div>452235 (5)</div> <div>442232 (6)</div> <div>442232 (6)</div> <div>442235 (3)</div> <div>352232 (7)</div></div> <div><br></div> <div>======</div> <div><br></div> <div><div>Generation 8 : 6.875</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>352232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>352232 (7)</div> <div>542132 (5)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div></div> <div><br></div> <div>제 8 세대까지 진행시키면 거의 유전자들이 똑같아집니다. 대부분의 개체가 환경에 적합해진다는 거죠. 그리고 적합하지 못했던 개체는 도태되어 사라졌습니다.</div> <div><br></div> <div>======</div> <div><br></div> <div><div>Generation 12 : 7.500</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>352232 (7)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>542232 (7)</div> <div>552232 (9)</div> <div>542232 (7)</div> <div>542232 (7)</div> <div>352232 (7)</div> <div>542234 (5)</div> <div>542232 (7)</div></div> <div><br></div> <div>물론 진화는 여기서 끝나지 않습니다. 계속 좋아지고 있네요.</div> <div><br></div> <div>======</div> <div><br></div> <div><div>Generation 14 : 9.000</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div></div> <div><br></div> <div>모든 개체의 유전자가 동일해진 시점입니다. 여기선 더이상 교배만으로는 새로운 유전자가 탄생하지 않습니다.</div> <div>그래서 이게 답이냐, 하면 그렇지 않습니다. 유전 알고리즘의 맹점이죠.</div> <div>유전 알고리즘은 "전역적 최대점"을 보장하지 않습니다. 우리가 구한 건 지역적 최소점이죠.</div> <div><br></div> <div><div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201604/1459611012d454939e462d4b18b5c7eacc1d1f9958__mn655684__w520__h367__f8413__Ym201604.png" alt="최댓점.png" style="border:none;width:320px;height:226px;" filesize="8413"></div> <div style="text-align:left;">왼쪽 동그라미가 전역적 최대점, 오른쪽이 지역적 최대점입니다.</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">이 상황을 타파하기 위해서 돌연변이가 존재합니다. 적자생존만으로는 완벽한 진화에 다가가기 힘듭니다.</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">======</div> <div style="text-align:left;"><br></div> <div style="text-align:left;"> <div>Generation 16 : 6.750</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>213432 (-2)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>212232 (-2)</div> <div>552212 (3)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>513432 (1)</div> <div>552232 (9)</div> <div>552232 (9)</div></div><br></div> <div>돌연변이가 나타났습니다. 근데 -2로, 정작 더 값이 낮아져버렸습니다.</div> <div><br></div> <div><div>Generation 17 : 9.000</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div> <div>552232 (9)</div></div> <div><br></div> <div>좋은 유전자가 아니니 그 다음 세대에서 자연히 도태됩니다.</div> <div><br></div> <div>======</div> <div><br></div> <div>이후로도 더 진행해봤는데, 도저히 9에서 더 올라가질 않아서 새로 시도해봤습니다.</div> <div><br></div> <div><div>Generation 0 : -0.125</div> <div>453533 (5)</div> <div>151111 (0)</div> <div>252352 (9)</div> <div>444145 (-1)</div> <div>324132 (-1)</div> <div>442324 (2)</div> <div>311145 (-2)</div> <div>131443 (-2)</div> <div>115215 (-4)</div> <div>334144 (-2)</div> <div>112442 (-1)</div> <div>545333 (2)</div> <div>531413 (2)</div> <div>112252 (-3)</div> <div>342253 (4)</div> <div>114535 (-10)</div></div> <div><br></div> <div>======</div> <div><br></div> <div><div>Generation 5 : 11.000</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div></div> <div><br></div> <div>11까지 올라갔습니다.</div> <div><br></div> <div>======</div> <div><br></div> <div><div>Generation 10 : 10.812</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>451352 (14)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452152 (5)</div></div> <div><br></div> <div>제 10 세대에서 돌연변이가 두 개 일어났습니다. 이대로 한 세대 더 진행시키면?</div> <div><br></div> <div><div>Generation 11 : 4.625</div> <div>451352 (14)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>452352 (11)</div> <div>214144 (-5)</div> <div>212352 (-3)</div> <div>451352 (14)</div> <div>212352 (-3)</div> <div>451344 (12)</div> <div>451352 (14)</div> <div>214144 (-5)</div> <div>214144 (-5)</div> <div>452344 (9)</div> <div>212352 (-3)</div> <div>214352 (-9)</div></div> <div><br></div> <div>돌연변이가 폭탄이군요. 유전자들이 완전히 뒤죽박죽이 되었습니다.</div> <div><br></div> <div>======</div> <div><br></div> <div><div>Generation 20 : 13.188</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>451342 (14)</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>411342 (2)</div> <div>451352 (14)</div> <div>451342 (14)</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>451352 (14)</div> <div>351352 (13)</div></div> <div><br></div> <div>제 20 세대입니다. 14에서 고정되어버렸군요.</div> <div><br></div> <div><br></div> <div>참고로 최댓값은 5 + (5 - 1) * (4 % 5) - 1 = 20 입니다.</div> <div><br></div> <div><br></div> <div><br></div> <div><br></div> <div>마무리(?).</div>