유전자 알고리즘 시작 부분에서 나온 것처럼, 유전자알고리즘은 '우수한 개체'를 재생산함으로써 진행됩니다. 여기서 '우수한 개체가 선택될 가능성'을 선택압이라고 합니다.
앞의 꼬마자동차 문제로 돌아가 보죠.
1000세대가 지나면서 가끔씩 1000점짜리 꼬마자동차가 생기긴 했습니다만 번번히 번식기회(?)를 놓치고 도태되고 말았습니다. 그 이유가 무엇일까요?
어느 순간 1000점짜리 꼬마자동차가 하나 탄생했습니다. 나머지 127대는 평균 950점대에 분포되어 있습니다. 꼬마자동차에서 재생산대상을 선택하기 위한 Roulette법에 의한다면, 점수의 총합은 950 * 127 + 1000 = 121650입니다. 그러므로 1000점짜리 꼬마자동차가 선택될 가능성은 1000/121650 = 0.00822 = 0.822%, 즉 1% 이하가 됩니다. 전체 128개 꼬마자동차 중에서 1% 이하라면 다른 꼬마자동차들과 거의 동일한 확률로 재생산된다고 봐야 하겠죠.
그러므로 1000점짜리 꼬마자동차를 늘리기 위해서는 선택압을 높일 필요가 있겠습니다.
선택압을 높이기 위해서는 재생산을 위한 부모를 찾는 방식을 바꾸어야 합니다. 여기서는 다음과 같은 두가지 방법을 시도해 봤습니다.
1. 순위법
순위법은 1위부터 차례로 순서를 매긴 후 등수에 따라 점수를 다르게 다시 주는 방법입니다. 여기서는 1위에게는 1000점, 2위에게는 950점, 3위에게는 900점 등으로 점수를 다시 계산했습니다.
function SelectParent()
.. sort car[] // 자동차 리스트를 소트(car[0]에 최대값이 들어가도록)
.. curscore := car[0].score
.. newscore := 1000;
.. order := 0;
.. for k := 0, 128 do
..... order := order + 1
..... if car[k].score == curscore then // 동점자일때는 같은점수
........ car[k].score := newscore
..... else
........ curscore := car[k].score
........ newscore = 1000 - order * 50;
........ car[k].score := newscore
..... end
.. end
.. // 이후는 Roulette법과 동일
end
순위법으로 선택압을 높여 유전자 알고리즘을 진행시킨 결과는 다음과 같습니다.
Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
......
Generation 48 MaxScore:990 MinScore:850 AverageScore:928
Generation 49 MaxScore:1000 MinScore:830 AverageScore:919
Generation 50 MaxScore:980 MinScore:820 AverageScore:926
Generation 51 MaxScore:990 MinScore:830 AverageScore:922
......
Generation 225 MaxScore:990 MinScore:810 AverageScore:925
Generation 226 MaxScore:1000 MinScore:820 AverageScore:925
Generation 227 MaxScore:1000 MinScore:810 AverageScore:923
Generation 228 MaxScore:990 MinScore:810 AverageScore:928
Generation 229 MaxScore:990 MinScore:800 AverageScore:925
Generation 230 MaxScore:1000 MinScore:810 AverageScore:928
Generation 231 MaxScore:1000 MinScore:800 AverageScore:945
Generation 232 MaxScore:1000 MinScore:800 AverageScore:969
Generation 233 MaxScore:1000 MinScore:940 AverageScore:974
......
Generation 680 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 681 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 682 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 683 MaxScore:1000 MinScore:900 AverageScore:999
Generation 684 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 685 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 686 MaxScore:1000 MinScore:1000 AverageScore:1000
최초의 만점 꼬마자동차(이것을 영웅이라 부릅시다^^)는 49세대만에 나타났다가 도태되었습니다. 그러나 이 경우 영웅은 많은 재생산기회를 가지므로 영웅의 유전자는 교차에 의해 분리되어 많은 다음세대의 꼬마자동차들에 흩어져 들어갑니다. 이 영웅유전자를 일부라도 가진 꼬마자동차들은 비교적 높은 점수를 얻을 수 있고 다음 재생산 대상이 될 수 있으므로 영웅유전자는 자꾸만 늘어납니다. 결국 영웅유전자끼리 만날 가능성은 점점 커지고(230세대) 마침내는 모든 꼬마자동차가 영웅유전자를 가질 수 있는 것이죠(600세대 이후). 이 이후 가끔씩 보이는 감점은 돌연변이에 의한 결과입니다.
2. 재계산법
재계산법은 꼬마자동차들 사이의 점수분포를 제한된 범위 안에 분포하도록 재계산하는 방식입니다. 룰렛방식 부모선택의 경우 1000세대 이후의 점수분포는 주로
Generation 1006 MaxScore:990 MinScore:840 AverageScore:938
Generation 1007 MaxScore:990 MinScore:850 AverageScore:935
Generation 1008 MaxScore:990 MinScore:860 AverageScore:937
Generation 1009 MaxScore:990 MinScore:810 AverageScore:938
Generation 1010 MaxScore:980 MinScore:870 AverageScore:933
810~990 사이였습니다. 이 범위를 꼬마자동차의 경우 10~1000 사이로 확대하여 재계산한 후 룰렛법과 같은 방식으로 계산합니다.
function SelectParent()
.. // 점수의 상한선과 하한선 찾기
.. minscore := 10000;
.. maxscore := 0;
.. for k := 0, 128 do
..... if minscore > car[k].score then
........ minscore := car[k].score
..... if car[k].score > maxscore then
........ maxscore := car[k].score
.. end
.. if maxscore != minscore then // 모든 자동차의 점수가 다 같은 경우는 적용할 수 없음
..... // max를 1000, min을 10으로 맞춤
..... newmax := 1000
..... newmin := 10
..... diff := maxscore - minscore; // 보정 전의 스코어 차이
..... for k := 0, 128 do
........ score := car[k].score
........ score := score - minscore
........ score := score * (newmax - newmin) / diff + newmin
........ car[k].score := score
..... end
.. end
.. // 이후는 Roulette법과 동일
end
재계산법으로 돌린 결과입니다.
Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
......
Generation 47 MaxScore:980 MinScore:700 AverageScore:898
Generation 48 MaxScore:990 MinScore:740 AverageScore:919
Generation 49 MaxScore:1000 MinScore:780 AverageScore:918
Generation 50 MaxScore:980 MinScore:820 AverageScore:926
Generation 51 MaxScore:990 MinScore:830 AverageScore:922
Generation 52 MaxScore:990 MinScore:850 AverageScore:928
......
Generation 492 MaxScore:990 MinScore:820 AverageScore:931
Generation 493 MaxScore:1000 MinScore:860 AverageScore:935
Generation 494 MaxScore:990 MinScore:870 AverageScore:937
Generation 495 MaxScore:990 MinScore:780 AverageScore:936
Generation 496 MaxScore:1000 MinScore:860 AverageScore:937
Generation 497 MaxScore:1000 MinScore:860 AverageScore:938
Generation 498 MaxScore:1000 MinScore:810 AverageScore:942
Generation 499 MaxScore:1000 MinScore:850 AverageScore:943
빠르고 늦고의 차이가 있을 뿐 전체적인 모습은 순위법일 경우와 동일합니다.
뱀발 :
그렇다면 유전자 알고리즘에서 선택압이 높을수록 좋은 것일까요? 그것은 아닙니다. 특히 초반에 지나치게 높은 선택압은 개체의 '다양성'을 해칠 수 있습니다. 말하자면 모든 꼬마자동차가 왼쪽에 있는 장애물만 못피하는데, 왼쪽 장애물을 피할 수 있는 유전자가 멸종해서 더이상의 개선이 불가능한 경우가 생길 수 있다는 것이죠.(물론 돌연변이가 있긴 하지만, 돌연변이에만 의존하는 유전자알고리즘은 비효율적입니다)
다양성에 대한 이야기는 다음 기회에 하도록 하겠습니다. 다만, 순위법이든 재계산법이든 후반에 선택압을 높이기 위해 사용할 수도 있지만 반대로 초반에 선택압을 줄여서 다양성을 유지하기 위해 사용할 수도 있습니다.
지적설계론은 지적설계자를 모욕하는 행위 - 가오리와 가자미
가오리와 가자미, 둘다 비슷한 습성을 가지고 있습니다. 납작한 모습을 하고 있으며 천적을 피하기 위해 바다 밑바닥에 납작 붙어 있다는 점에서 비슷한 습성을 하고 있다는 것을 알 수 있습니다.
하지만 이들이 바닥에 납작 붙기 위해 선택한 길은 전혀 다릅니다.
가오리는 이를테면 정석
적인 방법으로 납작한 몸을 얻었습니다. 좌우대칭인 몸을 유지하며 위아래로 납작해진 것입니다. 그때문에 몸이 납작해진 것 외에는 다른 부작용이 없습니다.
하지만 가자미의 경우는 다르죠. 몸이 위아래로 납작해진 것이 아니라 양옆으로 납작해진 것입니다.
일단 둘 다 납작한 몸을 가졌으므로 바다 밑바닥에 납작 붙어서 적의 눈을 피하는 데는 이상 없습니다.
하지만 정석적인 방법으로 납작한 몸을 얻게 된 가오리와는 달리 가자미는 한가지 문제점을 가지게 되었죠. 양옆으로 눌려 납작해진 몸으로 바다 밑바닥에 붙기 위해서는 몸을 옆으로 뉘일 수밖에 없습니다. 그러나 그렇게 되면 항상 한쪽 눈이 모래에 묻히게 됩니다. 결국 가자미는 양쪽에 있던 눈을 한쪽으로 몰아버릴 수밖에 없었습니다.
치어때만 해도 정상적으로 양쪽에 위치해 있던 두 눈이, 자라면서 두개골이 뒤틀리면서 한쪽으로 몰리고, 그에 따라 입까지 삐뚤어지는 현상이 나타나는 것입니다.
가오리는 정상적으로 만들었던 지적설계자는, 가자미는 왜 저렇게 비합리적으로 만들었을까요?
하지만 이들이 바닥에 납작 붙기 위해 선택한 길은 전혀 다릅니다.
가오리는 이를테면 정석
적인 방법으로 납작한 몸을 얻었습니다. 좌우대칭인 몸을 유지하며 위아래로 납작해진 것입니다. 그때문에 몸이 납작해진 것 외에는 다른 부작용이 없습니다.하지만 가자미의 경우는 다르죠. 몸이 위아래로 납작해진 것이 아니라 양옆으로 납작해진 것입니다.
일단 둘 다 납작한 몸을 가졌으므로 바다 밑바닥에 납작 붙어서 적의 눈을 피하는 데는 이상 없습니다.
하지만 정석적인 방법으로 납작한 몸을 얻게 된 가오리와는 달리 가자미는 한가지 문제점을 가지게 되었죠. 양옆으로 눌려 납작해진 몸으로 바다 밑바닥에 붙기 위해서는 몸을 옆으로 뉘일 수밖에 없습니다. 그러나 그렇게 되면 항상 한쪽 눈이 모래에 묻히게 됩니다. 결국 가자미는 양쪽에 있던 눈을 한쪽으로 몰아버릴 수밖에 없었습니다.
치어때만 해도 정상적으로 양쪽에 위치해 있던 두 눈이, 자라면서 두개골이 뒤틀리면서 한쪽으로 몰리고, 그에 따라 입까지 삐뚤어지는 현상이 나타나는 것입니다.가오리는 정상적으로 만들었던 지적설계자는, 가자미는 왜 저렇게 비합리적으로 만들었을까요?
GA - 자동차[2] 재생산
3. 가상환경에서의 적응도 테스트
이부분은 자세한 알고리즘은 생략하겠습니다. 단지 먼저 1000점을 주고, 임의로 만들어진 도로를 앞에서 설계한 유전자에 따라 일정거리(100칸) 이동시키면서 장애물을 들이받을 때마다 10점씩 감점시키는 것입니다. 다만 만약 앞 3칸이 다 장애물로 채워진 경우, 자동차는 장애물을 들이받을 수밖에 없기에 이런 장애물은 미리 제거하였습니다.
4. 재생산할 꼬마자동차 찾기
높은 점수를 받은 꼬마자동차를 찾아 재생산해야 '더 우수한 꼬마자동차'가 만들어질 수 있습니다. 재생산할 꼬마자동차를 찾는 가장 기본적인 방법은 룰렛법입니다. 룰렛법에 의하면 각자의 꼬마자동차가 선택될 확률은 그 꼬마자동차의 점수와 비례합니다.
function SelectParent()
.. // 모든 꼬마자동차의 점수 합 계산
.. totalscore := 0
.. for i := 0, 128 do
..... totalscore := totalscore + car[i].score
.. end
.. // 점수비율로 선택
.. rnd := Random(0:totalscore - 1)
.. for i := 0, 128 do
..... if car[i].score > rnd then
........ return car[i]
..... end
..... rnd := rnd - car[i].score
.. end
.. error Not Selected
end
5. 교차
선택된 두 꼬마자동차를 복제하는 것만으로는 더 우수한 꼬마자동차를 얻을 수 없습니다. 꼬마자동차의 유전자를 섞어야 선택된 두 부모의 장점을 이어받은 꼬마자동차를 얻을수 있죠.
실제 생물계에서도 오른쪽 그림과 같이 DNA가닥의 교차가 일어납니다.
여기서는 가장 간단한 1점교차를 사용해 유전자를 혼합하기로 하겠습니다. 즉, 임의의 한 점을 골라 그 점을 중심으로 유전자를 바꾸는 것입니다.
이를테면
A : 02101001
B : 11022120
였던 유전자가 3번 위치에서 교차가 일어났을 경우
A : 11001001
B : 02122120
가 되는 것입니다.
procedure CrossOver(Car A, car B)
.. // 교차가 일어날 위치 결정
.. crosspoint = Random(1, 7)
.. // 실제 교차
.. for k = 0, crosspoint do
..... tmp = A.gene[k]
..... A.gene[k] = B.gene[k]
..... B.gene[k] = tmp
.. end
end
한편 교차에는 위와 같은 일점교차뿐 아니라 2점교차 및 n점교차도 존재합니다. n점교차란 n개의 점을 선택해 자른 후 각각의 조각을 서로 바꾸는 교차입니다.
다음 유전자를
A : 02101001
B : 11022120
다음 유전 2, 5, 7점에서 3점교차를 한다면
A : 11101121
B : 02022000
와 같은 두 유전자가 만들어집니다.
마지막으로 랜덤교차는, 각각의 유전자 하나하나마다 일정확률을 적용시켜 교환할지 말지를 결정하는 교차방법입니다.
A : 02101001
B : 11022120
이것을 랜덤교차시킨다면
A : 11121021
B : 02002100
같이 보다 많이 뒤섞이게 됩니다.
6. 돌연변이
돌연변이는 임의의 비트를 전혀 다른 값으로 바꾸어버림으로써 새로운 정보를 만들고 유전자의 다양성을 증가시키기 위한 기본적인 방법입니다.
돌연변이 없이는 완전히 새로운 정보를 만들어낼 수도 없습니다(이 꼬마자동차는 처음 만들었을때 모든 유전자가 '직진'으로만 채워져 있기에 돌연변이 없이는 옆으로 이동이 불가능하죠). 그러나 돌연변이는 자칫하면 이미 잘 만들어진 유전자를 흐트러뜨릴 수도 있습니다(장애물을 잘 피해가던 꼬마자동차가 돌연변이에 의해 장애물을 들이받을 수도 있습니다). 그러므로 유전자알고리즘에서는, 돌연변이를 적용하더라도그 비율은 매우 낮게 적용합니다.
이 꼬마자동차의 경우에는 각 유전자 비트가 0.1%확률로 돌연변이를 일으키도록 설정했습니다.
procedure Mutantation(Car a)
.. for k = 0, 8 do
..... if Random(0, 999) == 0 then
........ a.gene[k] := Random(0, 2)
..... end
.. end
end
이렇게 새롭게 만든 128개의 꼬마자동차들을 원래의 배열로 옮기면 한 세대가 끝납니다. 이 새로운 세대를 대상으로 적응도테스트를 반복하면 점차 적응성이 높아지는 모습을 볼 수 있습니다.
다음은 실제로 유전자알고리즘을 돌린 결과입니다. 각 세대당 최고, 최저, 평균점수를 표시했습니다.
Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
Generation 6 MaxScore:900 MinScore:710 AverageScore:804
............
Generation 999 MaxScore:1000 MinScore:830 AverageScore:935
Generation 1000 MaxScore:1000 MinScore:790 AverageScore:930
Generation 1001 MaxScore:980 MinScore:830 AverageScore:934
Generation 1002 MaxScore:990 MinScore:870 AverageScore:935
Generation 1003 MaxScore:990 MinScore:850 AverageScore:939
Generation 1004 MaxScore:1000 MinScore:840 AverageScore:935
Generation 1005 MaxScore:990 MinScore:840 AverageScore:934
Generation 1006 MaxScore:990 MinScore:840 AverageScore:938
Generation 1007 MaxScore:990 MinScore:850 AverageScore:935
Generation 1008 MaxScore:990 MinScore:860 AverageScore:937
Generation 1009 MaxScore:990 MinScore:810 AverageScore:938
Generation 1010 MaxScore:980 MinScore:870 AverageScore:933
Generation 1011 MaxScore:1000 MinScore:860 AverageScore:935
Generation 1012 MaxScore:990 MinScore:850 AverageScore:935
Generation 1013 MaxScore:980 MinScore:860 AverageScore:929
......
1000세대 이상 지난 상태입니다. 1000점짜리(모든 장애물을 완전하게 피한) 꼬마자동차가 나타났군요. 하지만 만점 꼬마자동차가 계속 유지되지 않습니다. 만점 꼬마자동차가 도태되었다가 다시 만들어지는 현상의 반복이군요.
다음번엔 이것을 한번 고쳐봅시다.
이부분은 자세한 알고리즘은 생략하겠습니다. 단지 먼저 1000점을 주고, 임의로 만들어진 도로를 앞에서 설계한 유전자에 따라 일정거리(100칸) 이동시키면서 장애물을 들이받을 때마다 10점씩 감점시키는 것입니다. 다만 만약 앞 3칸이 다 장애물로 채워진 경우, 자동차는 장애물을 들이받을 수밖에 없기에 이런 장애물은 미리 제거하였습니다.
4. 재생산할 꼬마자동차 찾기
높은 점수를 받은 꼬마자동차를 찾아 재생산해야 '더 우수한 꼬마자동차'가 만들어질 수 있습니다. 재생산할 꼬마자동차를 찾는 가장 기본적인 방법은 룰렛법입니다. 룰렛법에 의하면 각자의 꼬마자동차가 선택될 확률은 그 꼬마자동차의 점수와 비례합니다.
function SelectParent()
.. // 모든 꼬마자동차의 점수 합 계산
.. totalscore := 0
.. for i := 0, 128 do
..... totalscore := totalscore + car[i].score
.. end
.. // 점수비율로 선택
.. rnd := Random(0:totalscore - 1)
.. for i := 0, 128 do
..... if car[i].score > rnd then
........ return car[i]
..... end
..... rnd := rnd - car[i].score
.. end
.. error Not Selected
end
5. 교차
선택된 두 꼬마자동차를 복제하는 것만으로는 더 우수한 꼬마자동차를 얻을 수 없습니다. 꼬마자동차의 유전자를 섞어야 선택된 두 부모의 장점을 이어받은 꼬마자동차를 얻을수 있죠.실제 생물계에서도 오른쪽 그림과 같이 DNA가닥의 교차가 일어납니다.
여기서는 가장 간단한 1점교차를 사용해 유전자를 혼합하기로 하겠습니다. 즉, 임의의 한 점을 골라 그 점을 중심으로 유전자를 바꾸는 것입니다.
이를테면
A : 02101001
B : 11022120
였던 유전자가 3번 위치에서 교차가 일어났을 경우
A : 11001001
B : 02122120
가 되는 것입니다.
procedure CrossOver(Car A, car B)
.. // 교차가 일어날 위치 결정
.. crosspoint = Random(1, 7)
.. // 실제 교차
.. for k = 0, crosspoint do
..... tmp = A.gene[k]
..... A.gene[k] = B.gene[k]
..... B.gene[k] = tmp
.. end
end
한편 교차에는 위와 같은 일점교차뿐 아니라 2점교차 및 n점교차도 존재합니다. n점교차란 n개의 점을 선택해 자른 후 각각의 조각을 서로 바꾸는 교차입니다.
다음 유전자를
A : 02101001
B : 11022120
다음 유전 2, 5, 7점에서 3점교차를 한다면
A : 11101121
B : 02022000
와 같은 두 유전자가 만들어집니다.
마지막으로 랜덤교차는, 각각의 유전자 하나하나마다 일정확률을 적용시켜 교환할지 말지를 결정하는 교차방법입니다.
A : 02101001
B : 11022120
이것을 랜덤교차시킨다면
A : 11121021
B : 02002100
같이 보다 많이 뒤섞이게 됩니다.
6. 돌연변이
돌연변이는 임의의 비트를 전혀 다른 값으로 바꾸어버림으로써 새로운 정보를 만들고 유전자의 다양성을 증가시키기 위한 기본적인 방법입니다.
돌연변이 없이는 완전히 새로운 정보를 만들어낼 수도 없습니다(이 꼬마자동차는 처음 만들었을때 모든 유전자가 '직진'으로만 채워져 있기에 돌연변이 없이는 옆으로 이동이 불가능하죠). 그러나 돌연변이는 자칫하면 이미 잘 만들어진 유전자를 흐트러뜨릴 수도 있습니다(장애물을 잘 피해가던 꼬마자동차가 돌연변이에 의해 장애물을 들이받을 수도 있습니다). 그러므로 유전자알고리즘에서는, 돌연변이를 적용하더라도그 비율은 매우 낮게 적용합니다.
이 꼬마자동차의 경우에는 각 유전자 비트가 0.1%확률로 돌연변이를 일으키도록 설정했습니다.
procedure Mutantation(Car a)
.. for k = 0, 8 do
..... if Random(0, 999) == 0 then
........ a.gene[k] := Random(0, 2)
..... end
.. end
end
이렇게 새롭게 만든 128개의 꼬마자동차들을 원래의 배열로 옮기면 한 세대가 끝납니다. 이 새로운 세대를 대상으로 적응도테스트를 반복하면 점차 적응성이 높아지는 모습을 볼 수 있습니다.
다음은 실제로 유전자알고리즘을 돌린 결과입니다. 각 세대당 최고, 최저, 평균점수를 표시했습니다.
Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
Generation 6 MaxScore:900 MinScore:710 AverageScore:804
............
Generation 999 MaxScore:1000 MinScore:830 AverageScore:935
Generation 1000 MaxScore:1000 MinScore:790 AverageScore:930
Generation 1001 MaxScore:980 MinScore:830 AverageScore:934
Generation 1002 MaxScore:990 MinScore:870 AverageScore:935
Generation 1003 MaxScore:990 MinScore:850 AverageScore:939
Generation 1004 MaxScore:1000 MinScore:840 AverageScore:935
Generation 1005 MaxScore:990 MinScore:840 AverageScore:934
Generation 1006 MaxScore:990 MinScore:840 AverageScore:938
Generation 1007 MaxScore:990 MinScore:850 AverageScore:935
Generation 1008 MaxScore:990 MinScore:860 AverageScore:937
Generation 1009 MaxScore:990 MinScore:810 AverageScore:938
Generation 1010 MaxScore:980 MinScore:870 AverageScore:933
Generation 1011 MaxScore:1000 MinScore:860 AverageScore:935
Generation 1012 MaxScore:990 MinScore:850 AverageScore:935
Generation 1013 MaxScore:980 MinScore:860 AverageScore:929
......
1000세대 이상 지난 상태입니다. 1000점짜리(모든 장애물을 완전하게 피한) 꼬마자동차가 나타났군요. 하지만 만점 꼬마자동차가 계속 유지되지 않습니다. 만점 꼬마자동차가 도태되었다가 다시 만들어지는 현상의 반복이군요.
다음번엔 이것을 한번 고쳐봅시다.
GA - 자동차[1] 유전자설계 및 초기화
여러분은 오른쪽 그림과 같은 꼬마자동차를 만들었습니다. 그리고는 무선조종이 아니라 이 자동차가 스스로 장애물을 피해 움직이도록 하려고 합니다.다만 센서가 약한 관계로 오른쪽 그림과 같이 단 세군데(바로 앞, 바로 앞의 왼쪽, 바로 앞의 오른쪽)만을 감지할 수 있습니다. 그리고 그 결과로 직진할지 왼쪽 앞으로 갈지 오른쪽 앞으로 갈지 결정해야 하는 것입니다.
물론 프로그래밍을 배운 사람은 초보자라도 간단하게 프로그램을 짤 수 있을 것입니다. 그러나 지금 이 자동차는 유전자 알고리즘을 공부하기 위한 샘플이니 직접 프로그래밍하는 것은 잠시 미뤄두시기 바랍니다.
1. 유전자 설계
유전자 프로그램을 할때 가장 첫단계는, 이 꼬마자동차의 '유전자를 설계'하는 일입니다. 보통 입력과 출력 사이의 상관관계를 유전자화시켜야 합니다.
이 꼬마자동차 문제에서 입력은 각 세 군데에서 장애물이 있는지 없는지 여부(장애물이 있으면 1, 없으면 0)로 나타낼 수 있습니다. 즉 8가지의 입력이 존재합니다.
출력은 각 상태일 경우 직진할지 왼쪽앞으로 갈지, 아니면 오른쪽 앞으로 갈지 결정해야 합니다.
그러므로 8개의 동작만으로 연결된 다음과 같은 유전자를 만들 수 있습니다.
| 차량 | 유전자(0:왼쪽앞으로 1:직진 2:오른쪽앞으로) |
| 가 | 10212001 |
| 나 | 22120001 |
| 다 | 11220210 |
| 라 | 21010112 |
| 마 | 00211201 |
| ... | ... |
만약 꼬마자동차가 왼쪽과 같은 상황에 처했다면, 입력장치는
011, 즉 3이란 입력을 보냅니다. 각 꼬마자동차들은 자신의 유전자에서 3 위치를 검색, 다음에 어떤 행동을 할 것인지 결정합니다.'가'의 경우 3 위치에 해당하는 것은 (첫 동작이 0이므로) <1-직진>입니다. 그러므로 '가'는 사람을 치고 지나가겠죠.
'다'의 경우 3위치의 동작은 <2-오른쪽앞>이므로 '다'는 나무를 향해 돌진할 것입니다.
이와같이 해서 꼬마자동차의 입력과 출력을 연결할 수 있는 유전자를 설계할 수 있습니다.
물론 다른 방식으로 유전자를 설계할 수도 있습니다. 그러나 이 꼬마자동차 문제는 유전자 알고리즘을 공부하기 위한 첫단계이므로 가장 간단하고 직관적인 유전자로 설계했습니다.
2. 최초 세대의 유전자 초기화(GeneInit)
이 프로그램에서는 한 세대의 꼬마자동차 수를 128대로 정의했습니다. 128개 꼬마자동차의 배열 또는 벡터를 만든 후 각 꼬마자동차의 유전자를 초기화하는 루틴을 만들어야 합니다.
| 사실 이 128이란 숫자는 유전자알고리즘에서 적당한 세대인구가 아닙니다. 보통 유전자알고리즘은 '수로 승부하는 방법'이라고 할 수 있습니다. 가능하면 많은 개체를 사용하여, 다양성을 증가시켜야 제대로된 결과가 나올 수 있습니다. 다만 이 꼬마자동차는 상당히 간단한 유전자 구조를 가지고 있기에 세대인구가 적더라도 비교적 빨리 원하는 결과를 얻을 수 있습니다. 보통 유전자알고리즘의 세대인구수는 최소 1000 이상, 대개 10000단위까지 올라갈 수 있습니다. |
초기화루틴은 다음과 같이 정의합니다.
procedure GeneInit(KidCar car)
.. for i := 0,8 do
..... car.gene[i] := 1 // 모든 경우에 무조건 직진으로 세팅
end
| 일반적으로 유전자를 초기화하기 위해서는 유전자의 각 위치(bit)에 유전자가 허용하는 랜덤값을 넣는 것이 정도(正道)입니다. 즉 ..... car.gene[i] := Random(0:2) // 0, 1, 2중 임의 선택 가 되어야 합니다. 다만 이 꼬마자동차에서는 돌연변이 효과를 확인하기 위해 일부러 모든 경우 직진하는 코드를 넣었습니다. |
GA - 쓰임새와 흐름도
유전자 알고리즘은 뜻밖에 여러 곳에 쓰일 수 있습니다. 각 개체의 적응도(Fitness)를 어떻게 정하느냐에 따라 많은 곳에 사용할 수 있습니다.
1. AI : 이것은 각 개체의 적응도를 AI의 효율성으로 정할 경우 최적의 AI를 만들기 위해 쓰일수 있습니다. 이를테면 미로를 통과하는 AI의 경우, 출구에서 얼마나 가까이 접근했는가, 또는 쉬운 미로부터 시작해서 몇개의 미로를 통과했는가 등을 적응도의 척도로 삼을 수 있습니다.
그러나 이 경우에는, 유전자 알고리즘을 실행하는 환경과, 그 결과물을 실제로 적용해야 할 환경이 정확하게 같을 필요가 있습니다. 그렇지 않으면, 오작동이 일어날 가능성이 매우 높아집니다.
2. 최적의 조합 찾기 : 간단한 보기로 이런 문제가 있을 수 있습니다.
이런 문제는 각 개체가 가지고 있는 보석의 총 가치를 적응도로 설정해서 유전자 알고리즘을 돌릴 수 있습니다.
3. 최적의 연결 찾기 : 회로도 등을 설계할때 적용되는 기술입니다. 기판 위에 각종 전자부품을 배열하고 그들끼리 연결을 해야 합니다. 이 연결선은 최소한의 길이, 최소한의 겹침을 필요로 합니다. 이 경우에도 각 연결선의 길이의 합, 겹침수 등을 적응도로 설정할 수 있습니다.
대부분의 경우에 유전자알고리즘의 순서도는 다음과 같습니다.
begin
.. declear Creature creature[GenerationNo] // GenerationNo만큼의 Creature 생성
.. for i := 0, GenerationNo do
..... call GeneInit(creature[i]) // 각각의 creature들의 유전자 초기화
.. end
.. while(1) do
..... for i := 0, GenerationNo do // 모든 creature들에 대해 적응도 계산
........ call TestReady(creature[i]) // i번째 creature가 시험받을 준비(score 초기화)
........ call FitnessCalc(creature[i])// i번째 creature의 적응도 계산
..... end
..... if(endcondition) // 만족할만한 creature가 나왔으면 끝냄
........ break
..... declear Creature nextgeneration[GenerationNo] // 다음세대 creature를 만들 버퍼
..... while(not fill nextgeneration) do // nextgeneration이 채워질 동안 반복
........ Creature a, b
........ while 1 do
........... a := SelectParent() // 적응도에 의해 재생산할 creature 선택
........... b := SelectParent() // a, b에 선택된 것의 복사본 만듦
........... if a != b then // 다른 Creature간의 유전자 혼합을 위해
.............. break
........... end
........ end
........ call CrossOver(a, b) // a, b의 유전자를 섞음
........ call Mutantation(a) // a, b에 적당한 돌연변이 가함
........ call Mutantation(b)
........ store a, b to nextgeneration // a, b를 다음 세대 버퍼에 넣음
..... end
..... creature := nextgeneration // 새로 만들어진 creature들로 계속 실행
.. end
end
1. AI : 이것은 각 개체의 적응도를 AI의 효율성으로 정할 경우 최적의 AI를 만들기 위해 쓰일수 있습니다. 이를테면 미로를 통과하는 AI의 경우, 출구에서 얼마나 가까이 접근했는가, 또는 쉬운 미로부터 시작해서 몇개의 미로를 통과했는가 등을 적응도의 척도로 삼을 수 있습니다.
그러나 이 경우에는, 유전자 알고리즘을 실행하는 환경과, 그 결과물을 실제로 적용해야 할 환경이 정확하게 같을 필요가 있습니다. 그렇지 않으면, 오작동이 일어날 가능성이 매우 높아집니다.
2. 최적의 조합 찾기 : 간단한 보기로 이런 문제가 있을 수 있습니다.
| 100개의 보석이 있다. 모두 무게와 가치가 다르다. 그 보석들 중에서 100g만 가지고 나갈 수 있다. 100g의 한계 안에서 최대가치의 보석을 가지고 나가려면 어떤 보석들을 가지고 나가야 할까? |
이런 문제는 각 개체가 가지고 있는 보석의 총 가치를 적응도로 설정해서 유전자 알고리즘을 돌릴 수 있습니다.
3. 최적의 연결 찾기 : 회로도 등을 설계할때 적용되는 기술입니다. 기판 위에 각종 전자부품을 배열하고 그들끼리 연결을 해야 합니다. 이 연결선은 최소한의 길이, 최소한의 겹침을 필요로 합니다. 이 경우에도 각 연결선의 길이의 합, 겹침수 등을 적응도로 설정할 수 있습니다.
대부분의 경우에 유전자알고리즘의 순서도는 다음과 같습니다.
begin
.. declear Creature creature[GenerationNo] // GenerationNo만큼의 Creature 생성
.. for i := 0, GenerationNo do
..... call GeneInit(creature[i]) // 각각의 creature들의 유전자 초기화
.. end
.. while(1) do
..... for i := 0, GenerationNo do // 모든 creature들에 대해 적응도 계산
........ call TestReady(creature[i]) // i번째 creature가 시험받을 준비(score 초기화)
........ call FitnessCalc(creature[i])// i번째 creature의 적응도 계산
..... end
..... if(endcondition) // 만족할만한 creature가 나왔으면 끝냄
........ break
..... declear Creature nextgeneration[GenerationNo] // 다음세대 creature를 만들 버퍼
..... while(not fill nextgeneration) do // nextgeneration이 채워질 동안 반복
........ Creature a, b
........ while 1 do
........... a := SelectParent() // 적응도에 의해 재생산할 creature 선택
........... b := SelectParent() // a, b에 선택된 것의 복사본 만듦
........... if a != b then // 다른 Creature간의 유전자 혼합을 위해
.............. break
........... end
........ end
........ call CrossOver(a, b) // a, b의 유전자를 섞음
........ call Mutantation(a) // a, b에 적당한 돌연변이 가함
........ call Mutantation(b)
........ store a, b to nextgeneration // a, b를 다음 세대 버퍼에 넣음
..... end
..... creature := nextgeneration // 새로 만들어진 creature들로 계속 실행
.. end
end
GA(유전자 알고리즘) - 시작
유전자 알고리즘이란 생물의 진화과정을 프로그램에 응용한 것입니다. 즉 진화의 과정인 변이와 자연선택을 흉내내는 프로그램기법입니다.
이를테면, 장애물을 피해 움직여야 하는 자동차를 상상해 봅시다.
1. 초기상태
다음과 같은 10대의 자동차를 만들었습니다. 각각의 자동차들은 장애물의 위치에 따라 다음 표와 같은 행동을 합니다.
2. 자연선택
그 다음에는 이 차들을 실제 장애물이 있는 도로에서 달리게 합니다. 물론 저들중 제대로 도로를 통과하는 차들은 없을 것입니다. (가)의 경우 오른쪽이나 정면에 장애물이 나타난다면 그대로 장애물을 들이받을 테니까 말입니다. 하지만 (다) 같은 경우 모든 장애물을 들이받겠지만 (가)는 왼쪽에 장애물이 나타난 경우, (나)는 왼쪽에 장애물이 나타난 경우는 제대로 피할 수 있습니다. 이런 식으로 각 자동차들의 성능을 점수를 매길 수 있습니다.
3. 재생산
2번 과정에서 점수를 가장 많이 얻은 자동차들을 모아 재생산을 합니다. 자연상태에서 한쌍의 어미가 유전자를 섞어 자손을 만들듯 높은 점수를 얻은 두 자동차의 특성을 섞어 새로운 자동차를 만드는 것입니다.
위의 경우 (가)와 (나)가 (그중에) 높은 점수를 얻어 재생산하게 되었다면
인 새로운 두 자동차가 만들어집니다.
이때 (가')는 부모인 (가), (나)의 장점만을 받아 더 향상된 성능을 가지게 됩니다. 아, 물론 (나')는 오히려 (가)와 (나)의 단점만을 물려받아 성능이 더 나빠졌죠.
4. 자연선택
3번 단계에서 재생산된 자동차들을 가지고 다시한번 도로에서 테스트를 합니다.
5. 재생산
4의 결과를 가지고 다시 재생산을 합니다. 이 경우에 (가')는 확실히 (가)나 (나)보다 높은 점수를 받을 테니 다음번 재생산 대상이 될 수 있을 것입니다. 반면에 (나')는 점수가 형편없어질 테니 재생산대상이 될 수 없겠죠.
이런 식으로 반복해 나간다면 결국은 모든 경우에 장애물을 피할 수 있는 자동차가 나타날 것입니다. 이것이 유전자 알고리즘의 원리입니다.
이를테면, 장애물을 피해 움직여야 하는 자동차를 상상해 봅시다.
1. 초기상태
다음과 같은 10대의 자동차를 만들었습니다. 각각의 자동차들은 장애물의 위치에 따라 다음 표와 같은 행동을 합니다.
| 차량 | 왼쪽장애물 | 앞쪽장애물 | 오른쪽장애물 |
| 가 | 직진 | 직진 | 오른쪽이동 |
| 나 | 왼쪽이동 | 직진 | 왼쪽이동 |
| 다 | 왼쪽이동 | 직진 | 오른쪽이동 |
| 라 | 오른쪽이동 | 직진 | 직진 |
| 마 | 왼쪽이동 | 왼쪽이동 | 오른쪽이동 |
| ... | ... | ... | ... |
2. 자연선택
그 다음에는 이 차들을 실제 장애물이 있는 도로에서 달리게 합니다. 물론 저들중 제대로 도로를 통과하는 차들은 없을 것입니다. (가)의 경우 오른쪽이나 정면에 장애물이 나타난다면 그대로 장애물을 들이받을 테니까 말입니다. 하지만 (다) 같은 경우 모든 장애물을 들이받겠지만 (가)는 왼쪽에 장애물이 나타난 경우, (나)는 왼쪽에 장애물이 나타난 경우는 제대로 피할 수 있습니다. 이런 식으로 각 자동차들의 성능을 점수를 매길 수 있습니다.
3. 재생산
2번 과정에서 점수를 가장 많이 얻은 자동차들을 모아 재생산을 합니다. 자연상태에서 한쌍의 어미가 유전자를 섞어 자손을 만들듯 높은 점수를 얻은 두 자동차의 특성을 섞어 새로운 자동차를 만드는 것입니다.
위의 경우 (가)와 (나)가 (그중에) 높은 점수를 얻어 재생산하게 되었다면
| 차량 | 왼쪽장애물 | 앞쪽장애물 | 오른쪽장애물 |
| 가 | 직진 | 직진 | 오른쪽이동 |
| 나 | 왼쪽이동 | 직진 | 왼쪽이동 |
으로부터
| 차량 | 왼쪽장애물 | 앞쪽장애물 | 오른쪽장애물 |
| 가' | 직진 | 직진 | 왼쪽이동 |
| 나' | 왼쪽이동 | 직진 | 오른쪽이동 |
이때 (가')는 부모인 (가), (나)의 장점만을 받아 더 향상된 성능을 가지게 됩니다. 아, 물론 (나')는 오히려 (가)와 (나)의 단점만을 물려받아 성능이 더 나빠졌죠.
4. 자연선택
3번 단계에서 재생산된 자동차들을 가지고 다시한번 도로에서 테스트를 합니다.
5. 재생산
4의 결과를 가지고 다시 재생산을 합니다. 이 경우에 (가')는 확실히 (가)나 (나)보다 높은 점수를 받을 테니 다음번 재생산 대상이 될 수 있을 것입니다. 반면에 (나')는 점수가 형편없어질 테니 재생산대상이 될 수 없겠죠.
이런 식으로 반복해 나간다면 결국은 모든 경우에 장애물을 피할 수 있는 자동차가 나타날 것입니다. 이것이 유전자 알고리즘의 원리입니다.
진화론 이야기 - 죄수의 딜레마(Prisoner's Dilemma)
1. 상황
G는 보석을 가지고 있습니다. 하지만 돈이 쪼들립니다.
M은 돈을 가지고 있습니다. 하지만 그는 보석을 가지고 싶어합니다.
그들은 모종의 이유로 서로 만날 수도, 연락을 할 수도 없습니다. 단지 지정된 시간(동시)에 G는 보석을, M은 돈을 서로 상대방에게 택배로 보낼 뿐입니다.
이 경우에 이들이 선택할 최선의 전략은 어떤 것일까요?
(물론 실제의 죄수의 딜레마와는 조금 다르지만 진화론과 관련해서 설명하기에는 이쪽이 낫습니다)
서로가 약속을 지키면(협력하면) G는 돈을, M은 보석을 얻는 최선의 결과를 얻습니다.(양쪽에 10점씩)
서로가 서로를 배신하면 둘 다 아무 변화가 없습니다(양쪽에 0점)
어느 한쪽만이 배신하면 배신한 쪽은 돈과 보석을 다 얻지만(15점) 배신당한 쪽은 다 잃습니다(-5점)
원래의 죄수의 딜레마와 같이 배신하는 쪽이 항상 이득입니다.
하지만 G는 많은 보석을 가지고 있으며 계속 돈을 필요로 합니다. M은 돈은 매우 많으며 보석욕심도 점점 커집니다. 이후에도 두 사람은 계속 거래를 해야 합니다. 이럴 경우에는 어떤 전략을 사용하는 것이 가장 좋을까요?
2. Tit-for-Tat
1970년대 엑셀로드(Axelrod)는 이런 상황을 가정하여 최적의 전략 - 과거 상대방의 반응으로부터 협력할지 배신할지를 선택하는 프로그램을 공모했습니다. 그리고 토너먼트식으로 공모된 전략들을 맞붙여 어떤 전략이 가장 높은 득점을 하는지 확인했습니다.
그 토너먼트에서 우승한 전략이 Tit-for-Tat(받은만큼돌려주기 또는 눈에는눈)이었습니다. 즉 가장 처음에는 협력하고, 그 다음부터는 상대가 한 대로 돌려주는 것입니다.
눈에는눈은 협력을 우선하여 상호간의 이익을 추구합니다. 즉 먼저 배신하지 않습니다.
눈에는눈은 배신을 당했을 경우 자신도 배신함으로써 응징합니다.
눈에는눈은 응징에 성공(자신이 배신할때 상대가 협력)한다면 용서하고 다시 상호간의 이익을 추구합니다.
3. 생존경쟁
윗실험에 참가했던 전략들을 일정 수만큼 컴퓨터에 넣고, 임의로 짝을 지워 게임을 시킵니다. 그리고 그때 얻은 점수 비율에 따라 다음 세대의 수를 결정하는 프로그램을 만듧니다.
초기에는 '어떻게든 상대를 착취하는 사기꾼' 전략들이 강세를 보입니다. '순진한 촌뜨기' 전략들을 착취하면서 세력을 떨치는 것이죠.
하지만 촌뜨기들이 줄어들고 더이상 착취할 상대가 남아있지 않게 되면 사기꾼들 역시 나락으로 떨어지고 맙니다. 눈에는눈을 착취하려고 하면 응징을 당하고, 다른 사기꾼 상대를 만나도 착취할 건덕지가 없습니다.
반면 눈에는눈은 사기꾼을 만나면 한번 배신당하지만 응징에 의해 더이상의 착취를 당하지는 않습니다. 다른 눈에는눈이나 촌뜨기를 만나면 상호협력에 의해 양측 다 점수를 얻습니다.
결국 시간이 지나면 눈에는눈이 대세를 이루고, 눈에는눈에 기대는 소수의 촌뜨기, 그리고 가끔씩 만나는 촌뜨기를 삥뜯으며 살아가는 소수의 사기꾼이 평형을 이루는 상태가 됩니다.
4. 유전자 알고리즘
윗 실험은 이미 개발된 전략들의 우열을 판가름하는 내용이었습니다. 그런데 완전한 무질서 상태에서도, 도덕이니 양심이니 하는 것이 전혀 없는 상태에서도 저런 협력이 나올 수 있을까요?
4-1. 초기에 무조건 배신하는 전략들만을 모아놓고 3번의 생존경쟁과 같은 프로그램을 돌립니다. 역시 가장 높은 점수를 얻은 전략은 많은 자손을 남길 수 있습니다. 그러나 이때는 약간의 돌연변이를 일으킨 자손을 만듧니다.
돌연변이에 의해 조심스럽게 협력을 시도하는(하지만 배신당했다면 바로 협력관계를 취소하는) 전략이 생깁니다. 이들은 많은경우 주위에게 조금씩 착취당하지만, 이런 변이체들끼리 만난다면 더 높은 점수를 얻고 더 많은 번식기회를 가질수 있습니다. 그 다음 세대에는 협력하는 전략들끼리 만날 기회가 더 많아지고 더 높은 점수를 얻을 것입니다.
결국 이 생태계는 눈에는눈은 아니지만 눈에는눈과 비슷한 형태의 전략으로 가득 차게 됩니다.
4-2. 반대로 초기에 무조건 협력하는 전략들만을 모아놓는다면 어떨까요? 배신하는 돌연변이가 나온다면 그는 주위 모든 것들을 착취해서 급격히 세를 불려나갑니다. 결국 4-1의 초기상태와 비슷하게 되고 마찬가지 결과가 나옵니다.
5. 결론
진화론에 의해서도 착한 놈이 이긴다.(진화론이 정설이 되면 사회가 약육강식의 정글이 된다고 걱정하는 창조론자들이 있어서...)
G는 보석을 가지고 있습니다. 하지만 돈이 쪼들립니다.
M은 돈을 가지고 있습니다. 하지만 그는 보석을 가지고 싶어합니다.
그들은 모종의 이유로 서로 만날 수도, 연락을 할 수도 없습니다. 단지 지정된 시간(동시)에 G는 보석을, M은 돈을 서로 상대방에게 택배로 보낼 뿐입니다.
이 경우에 이들이 선택할 최선의 전략은 어떤 것일까요?
(물론 실제의 죄수의 딜레마와는 조금 다르지만 진화론과 관련해서 설명하기에는 이쪽이 낫습니다)
서로가 약속을 지키면(협력하면) G는 돈을, M은 보석을 얻는 최선의 결과를 얻습니다.(양쪽에 10점씩)
서로가 서로를 배신하면 둘 다 아무 변화가 없습니다(양쪽에 0점)
어느 한쪽만이 배신하면 배신한 쪽은 돈과 보석을 다 얻지만(15점) 배신당한 쪽은 다 잃습니다(-5점)
원래의 죄수의 딜레마와 같이 배신하는 쪽이 항상 이득입니다.
하지만 G는 많은 보석을 가지고 있으며 계속 돈을 필요로 합니다. M은 돈은 매우 많으며 보석욕심도 점점 커집니다. 이후에도 두 사람은 계속 거래를 해야 합니다. 이럴 경우에는 어떤 전략을 사용하는 것이 가장 좋을까요?
2. Tit-for-Tat
1970년대 엑셀로드(Axelrod)는 이런 상황을 가정하여 최적의 전략 - 과거 상대방의 반응으로부터 협력할지 배신할지를 선택하는 프로그램을 공모했습니다. 그리고 토너먼트식으로 공모된 전략들을 맞붙여 어떤 전략이 가장 높은 득점을 하는지 확인했습니다.
그 토너먼트에서 우승한 전략이 Tit-for-Tat(받은만큼돌려주기 또는 눈에는눈)이었습니다. 즉 가장 처음에는 협력하고, 그 다음부터는 상대가 한 대로 돌려주는 것입니다.
눈에는눈은 협력을 우선하여 상호간의 이익을 추구합니다. 즉 먼저 배신하지 않습니다.
눈에는눈은 배신을 당했을 경우 자신도 배신함으로써 응징합니다.
눈에는눈은 응징에 성공(자신이 배신할때 상대가 협력)한다면 용서하고 다시 상호간의 이익을 추구합니다.
| 정확히 말해서 눈에는눈을 능가하는 단 하나의 전략이 있었습니다. 이것은 처음부터 배신해서 상대의 반응을 살핍니다. 상대가 내 배신에 반응하지 않으면 계속 배신으로 상대를 착취하는 것입니다. 내 배신에 상대도 배신으로 반응한다면 그때는 눈에는눈으로 변신하는 것이죠. 하지만 그것은 특수한 상황 - 상대중에 Random이라는, 50%확률로 협력과 배신을 결정하는 전략이 있었기에 가능했던 것입니다. 만약 Random이 없다면 상대를 떠보기 위한 배신의 부담으로 순수한 눈에는눈에 비해 낮은 점수를 얻게 됩니다. |
3. 생존경쟁
윗실험에 참가했던 전략들을 일정 수만큼 컴퓨터에 넣고, 임의로 짝을 지워 게임을 시킵니다. 그리고 그때 얻은 점수 비율에 따라 다음 세대의 수를 결정하는 프로그램을 만듧니다.
초기에는 '어떻게든 상대를 착취하는 사기꾼' 전략들이 강세를 보입니다. '순진한 촌뜨기' 전략들을 착취하면서 세력을 떨치는 것이죠.
하지만 촌뜨기들이 줄어들고 더이상 착취할 상대가 남아있지 않게 되면 사기꾼들 역시 나락으로 떨어지고 맙니다. 눈에는눈을 착취하려고 하면 응징을 당하고, 다른 사기꾼 상대를 만나도 착취할 건덕지가 없습니다.
반면 눈에는눈은 사기꾼을 만나면 한번 배신당하지만 응징에 의해 더이상의 착취를 당하지는 않습니다. 다른 눈에는눈이나 촌뜨기를 만나면 상호협력에 의해 양측 다 점수를 얻습니다.
결국 시간이 지나면 눈에는눈이 대세를 이루고, 눈에는눈에 기대는 소수의 촌뜨기, 그리고 가끔씩 만나는 촌뜨기를 삥뜯으며 살아가는 소수의 사기꾼이 평형을 이루는 상태가 됩니다.
4. 유전자 알고리즘
윗 실험은 이미 개발된 전략들의 우열을 판가름하는 내용이었습니다. 그런데 완전한 무질서 상태에서도, 도덕이니 양심이니 하는 것이 전혀 없는 상태에서도 저런 협력이 나올 수 있을까요?
4-1. 초기에 무조건 배신하는 전략들만을 모아놓고 3번의 생존경쟁과 같은 프로그램을 돌립니다. 역시 가장 높은 점수를 얻은 전략은 많은 자손을 남길 수 있습니다. 그러나 이때는 약간의 돌연변이를 일으킨 자손을 만듧니다.
돌연변이에 의해 조심스럽게 협력을 시도하는(하지만 배신당했다면 바로 협력관계를 취소하는) 전략이 생깁니다. 이들은 많은경우 주위에게 조금씩 착취당하지만, 이런 변이체들끼리 만난다면 더 높은 점수를 얻고 더 많은 번식기회를 가질수 있습니다. 그 다음 세대에는 협력하는 전략들끼리 만날 기회가 더 많아지고 더 높은 점수를 얻을 것입니다.
결국 이 생태계는 눈에는눈은 아니지만 눈에는눈과 비슷한 형태의 전략으로 가득 차게 됩니다.
4-2. 반대로 초기에 무조건 협력하는 전략들만을 모아놓는다면 어떨까요? 배신하는 돌연변이가 나온다면 그는 주위 모든 것들을 착취해서 급격히 세를 불려나갑니다. 결국 4-1의 초기상태와 비슷하게 되고 마찬가지 결과가 나옵니다.
5. 결론
진화론에 의해서도 착한 놈이 이긴다.(진화론이 정설이 되면 사회가 약육강식의 정글이 된다고 걱정하는 창조론자들이 있어서...)
진화론을 증명하면 25만달러?
"저, 여기 알파 센타우리까지의 거리를 측정하면 100만달러를 주는데 맞죠? 제가 연주시차를 이용해서 측정했습니다. 그 결과는 약 ..."
"저희는 연주시차로 계산한 결과는 신뢰하지 않습니다. 오직 줄자를 이용한 측정만 믿죠. 그러니까 줄자를 가지고 cm단위까지 재오시면 100만 달러를 드리겠습니다"
[진화론의 증거를 가져오면 250만달러를 준다]는 제안이 있다더군요.
호빈드 박사의 25만 불 제안 2
누구도 알파 센타우리별까지의 거리를 직접 잴 수 없습니다. 하지만 연주시차란 방법으로 간접적으로 잴 수 있습니다.
누구도 플라스크에서 자기복제분자가 저절로 만들어지는 것을 관측할 수 없습니다. 하지만 여러가지 화학반응으로서 자기복제분자가 만들어질 수 있음을 간접적으로 증명할 수 있습니다.
이런 간접적인 방법을 무시하고 직접 만들어보라고 요구하는 것은 알파 센타우리까지의 거리를 줄자로 재오라는 것이나 마찬가지입니다.
"저희는 연주시차로 계산한 결과는 신뢰하지 않습니다. 오직 줄자를 이용한 측정만 믿죠. 그러니까 줄자를 가지고 cm단위까지 재오시면 100만 달러를 드리겠습니다"
[진화론의 증거를 가져오면 250만달러를 준다]는 제안이 있다더군요.
호빈드 박사의 25만 불 제안 2
누구도 알파 센타우리별까지의 거리를 직접 잴 수 없습니다. 하지만 연주시차란 방법으로 간접적으로 잴 수 있습니다.
누구도 플라스크에서 자기복제분자가 저절로 만들어지는 것을 관측할 수 없습니다. 하지만 여러가지 화학반응으로서 자기복제분자가 만들어질 수 있음을 간접적으로 증명할 수 있습니다.
이런 간접적인 방법을 무시하고 직접 만들어보라고 요구하는 것은 알파 센타우리까지의 거리를 줄자로 재오라는 것이나 마찬가지입니다.
신이 기도를 들어주지 않는 이유
어느 마을에서 홍수가 나서 집이 모두 물에 잠겼습니다. 물이 점점 차오르는 상황에서 한 남자가 지붕 위에 고립되어 있었습니다.
그 남자에게로 보트 한척이 다가왔습니다.
"자, 높은 곳으로 태워다줄테니 어서 타요"
"아닙니다. 저는 신에게 기도하고 있는 중입니다. 신께서 날 구해줄 겁니다"
그 보트는 다른 사람을 태우기 위해 노를 저어 갔습니다.
물은 계속 불어나 허리까지 차올랐습니다. 어디선가 모터보트 한척이 다가와 말했습니다.
"여기 계속 있으면 위험해요, 빨리 타세요"
"아닙니다. 신께서는 제 기도를 들어줄 겁니다. 그때까지 기다리겠습니다."
마침내 물은 그사람의 가슴까지 차올랐습니다. 그때 굉음과 함께 헬리콥터 한대가 다가왔습니다.
"줄사다리를 내려줄 테니 꼭 잡으시오"
"아닙니다. 필요 없습니다. 저는 신이 꼭 도와줄 것이라 믿고 있습니다."
결국 헬리콥터는 연료가 떨어진듯 돌아갔고, 그 남자는 익사하여 저승에서 신을 만났습니다.
화가난 그 남자는 신에게 따졌습니다.
"제가 그렇게 열심히 기도를 했는데 왜 도와주지 않았습니까?"
"내가 도와주지 않았다고? 나는 자네에게 보트 두척과 심지어 헬리콥터까지 보냈네. 더이상 어떻하란 말인가?"
얼마전 '에반 올마이티'란 영화를 봤습니다. 거기서 모건 프리먼의 이 대사가 생각나는군요(사실 기억나는 것이 이것뿐이긴 합니다만...^^;).
"신에게 지혜를 빈다면 신은 지혜를 줄까요, 지혜로워질 기회를 줄까요? 신에게 용기를 빈다면 신은 용기를 줄까요, 용감해질 기회를 줄까요?
그리고 신에게 가정의 화목을 빈다면, 신은 가정의 화목을 줄까요, 화목해질 기회를 줄까요?"
많은 사람들이 신(기독교의 야훼든 불교의 부처든 아니면 전통신앙의 하늘님이든...)에게 기도를 하지만, 신이 준 기회를 놓치지 않는 것도 중요할 듯 싶습니다.
그 남자에게로 보트 한척이 다가왔습니다.
"자, 높은 곳으로 태워다줄테니 어서 타요"
"아닙니다. 저는 신에게 기도하고 있는 중입니다. 신께서 날 구해줄 겁니다"
그 보트는 다른 사람을 태우기 위해 노를 저어 갔습니다.
물은 계속 불어나 허리까지 차올랐습니다. 어디선가 모터보트 한척이 다가와 말했습니다.
"여기 계속 있으면 위험해요, 빨리 타세요"
"아닙니다. 신께서는 제 기도를 들어줄 겁니다. 그때까지 기다리겠습니다."
마침내 물은 그사람의 가슴까지 차올랐습니다. 그때 굉음과 함께 헬리콥터 한대가 다가왔습니다.
"줄사다리를 내려줄 테니 꼭 잡으시오"
"아닙니다. 필요 없습니다. 저는 신이 꼭 도와줄 것이라 믿고 있습니다."
결국 헬리콥터는 연료가 떨어진듯 돌아갔고, 그 남자는 익사하여 저승에서 신을 만났습니다.
화가난 그 남자는 신에게 따졌습니다.
"제가 그렇게 열심히 기도를 했는데 왜 도와주지 않았습니까?"
"내가 도와주지 않았다고? 나는 자네에게 보트 두척과 심지어 헬리콥터까지 보냈네. 더이상 어떻하란 말인가?"
얼마전 '에반 올마이티'란 영화를 봤습니다. 거기서 모건 프리먼의 이 대사가 생각나는군요(사실 기억나는 것이 이것뿐이긴 합니다만...^^;).
"신에게 지혜를 빈다면 신은 지혜를 줄까요, 지혜로워질 기회를 줄까요? 신에게 용기를 빈다면 신은 용기를 줄까요, 용감해질 기회를 줄까요?
그리고 신에게 가정의 화목을 빈다면, 신은 가정의 화목을 줄까요, 화목해질 기회를 줄까요?"
많은 사람들이 신(기독교의 야훼든 불교의 부처든 아니면 전통신앙의 하늘님이든...)에게 기도를 하지만, 신이 준 기회를 놓치지 않는 것도 중요할 듯 싶습니다.
피드 구독하기:
글 (Atom)