GA - 여덟여왕문제(8-Queen's Problem)[4] - 마무리

8-Queen Problem의 최종해답은 다음과 같습니다.(출처)


보시다시피 12가지 배열이 존재합니다. 그리고 저 배열들의 회전, 거울상이동 등을 허용한다면 총 92가지 배열이 가능합니다.
앞의 문제에서 종을 판단할때 회전같은 변환은 하지 않았습니다. 그렇다면 이론적으로 92개의 종이 나와야 하겠죠.

앞의 TSP에서도 마찬가지였지만, 유전자알고리즘이라는 것이 랜덤함수에 의존하는 면이 있습니다. 답을 쉽게 찾는 대신 원하는 답을 찾기가 힘들다고나 할까요?

'답을 찾아라'같은 문제라면 유전자알고리즘이 효과적입니다.
'가능한한 많은 답을 찾아라'라는 문제도 (아쉬운 대로) 유전자알고리즘으로 찾을 수 있습니다.
'모든 답을 찾아라'라면 유전자알고리즘으로서는 무리가 따름니다. 이 문제의 경우 92개의 답을 모두 찾아도 93번째 답은 없다는 것을 유전자알고리즘으로는 알 수 없기 때문입니다.

참고로 만약 유전자알고리즘으로 가능한한 많은 답을 찾기 위해서는 다음과 같은 방식을 사용하는 것이 좋습니다.
㉠ 가능한한 개체수를 많이 만들어 실행시킵니다. 개체수가 많을수록 다양성이 커져 더 많은 답을 찾을수 있습니다.
㉡ srand로 랜덤함수를 바꾸어가며 여러번 실행시킵니다.

지적설계론은 지적설계자를 모욕하는 행위 - 팬더의 엄지

작고하신 스티브 굴드의 '팬더의 엄지'로 유명해진 팬더의 엄지 이야기입니다.
팬더의 손가락을 보면 오른쪽 그림과 같이 손가락이 여섯개임을 알 수 있습니다. 하지만 해부학적으로 봤을때 손가락은 다섯개 뿐입니다. 엄지손가락은 손의 종자골이 변형되어 튀어나온 것입니다. 이 새로운 엄지손가락 덕분에 팬더는 주식인 대나무를 손으로 잡아서 먹을 수 있는 것이죠.

하지만 여기서 한가지 의문점이 생깁니다. 만약 창조주가 팬더에게 엄지손가락을 주려고 했다면 왜 영장류와 같은 엄지손가락을 주지 않았을까요? 왜 애매한 뼈를 억지로 변형시켜, 엄지손가락이 아닌 '엄지손가락 같은' 손가락을 주었을까요?

GA - 여덟여왕문제(8-Queen's Problem)[3] - 종(種) 유지

7. 종(種) 분류에 의한 다양성 유지

유전자 알고리즘시의 다양성을 유지하기 위한 한가지 방법으로 개체를 종으로 분류하여 관리하는 방법이 있습니다. 즉, 한 세대의 개체들이 각각 어느 종에 속해 있는지 결정한 후 그 종의 숫자가 클수록 패널티를 주는 것입니다. 앞에서 나왔던 것처럼 어느 한 개체가 다수를 점하게 되어 그 종의 개체수가 늘어나면 그만큼 적응도가 낮아져 재생산대상으로 선택될 가능성이 줄어듧니다. 그때문에 다른 종의 개체들이 살아남을 수 있도록 하는 - 다양성을 유지하도록 하는 것입니다.

7-1. 종 결정
우선 매 세대마다 각각의 개체(하렘)가 어느 종에 속하는지 확인해야 합니다. 그리고 각각의 종에 대해서 개체수가 몇개인지 확인해야 합니다. 다음 알고리즘에서 Dictionary는 지금까지 발견된 모든 종을 가지고 있는 리스트입니다.
매 세대 적응도를 계산하기 전 Dictionary의 모든 population을 0으로 클리어한 후 모든 Harem에 대해 다음 프로시저를 호출, 어떤 종에 속하는지, 그리고 각 종의 개체수는 얼마인지를 계산해야 합니다.

procedure SpeciesIdentify(Harem A)
.. for k := 0, Dictionary.size do
..... if SameSpacies(Dictionary[k].sample, A) then // A가 k번째 샘플과 같은 종일 경우
........ A.species = k // A가 k번째 종이라고 설정
........ Dictionary[k].population := Dictionary[k].population + 1 // 개체수 증가
........ return
..... end
.. end
.. // 어떤 종인지 확인 못했음 - 새로 발견된 종
.. AddElement(Dictionary) // Dictionary에 새로운 종을 등록하기 위해 원소 하나 추가
.. Dictionary[k].sample := A // k번째 종을 묘사하기 위한 샘플 저장
.. Dictionary[k].population := 1 // 하나가 발견되었으므로 1로 세팅
.. A.species = k // A가 k번째 종이라고 설정
end

SameSpacies함수는 생략하겠습니다. 간단히 말하자면 sample과 A의 각각 유전자대로 8*8의 체스판 위에 여왕들을 올려놓은 후 두 배열이 같은지를 확인합니다. 만약 모든 여왕들이 동일한 위치에 서 있다면 둘은 같은 종입니다.

7-2 종의 개체수에 따른 적응도(Fitness) 보정
앞에서 각 하렘의 여왕들이 서로를 방해하는 경우의 수 ConflictNumber를 구한후 -ConflictNumber를 적응도로 간주했습니다. 여기서는 이 하렘이 속한 종의 개체수를 보정해 주어야 합니다. 즉 이 경우에

function Fitness(Harem A)
.. species_ID := A.species
.. species_population := Dictionary[species_ID].population
.. return -A.ConflictNumber - species_population / 10
end

즉, 종의 개체수가 10 증가할 때마다 적응도는 1씩 감소하는 형태가 됩니다.

8. 최종결과

Generation : 499 : 24
[11](-1/3)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * . Q .
. * . Q . * . *
* Q * . * . * .
. * . * . * . Q
* . * . * Q * .
Q * . * . * . *
* . Q . * . * .
. * . * Q * . *

[41](-2/2)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . Q . * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *
* . * . * . * Q
. Q . * . * . *
* . * Q * . * .
. * . * . Q . *

[55](3/-2)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . Q . * .
. * . * . * Q *
Q . * . * . * .
. * Q * . * . *
* . * . * . * Q
. * . * . Q . *
* . * Q * . * .
. Q . * . * . *

[14](3/-3)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * . Q .
Q * . * . * . *
* . Q . * . * .
. * . * . * . Q
* . * . * Q * .
. * . Q . * . *
* Q * . * . * .
. * . * Q * . *

[51](-3/0)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * Q * .
. * . Q . * . *
* . * . * . Q .
Q * . * . * . *
* . Q . * . * .
. * . * Q * . *
* Q * . * . * .
. * . * . * . Q

[46](-3/-1)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . * . * Q
. Q . * . * . *
* . * . Q . * .
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *
* . * Q * . * .
. * . * . Q . *

[32](-2/1)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *
* . * . * Q * .
. * Q * . * . *

[46](-2/3)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * Q * .
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *

[55](3/1)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* Q * . * . * .
. * . Q . * . *
* . * . * Q * .
. * . * . * . Q
* . Q . * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *

[23](-1/2)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * Q * . * .
. Q . * . * . *
* . * . * . * Q
. * . * . Q . *
Q . * . * . * .
. * Q * . * . *
* . * . Q . * .
. * . * . * Q *

[53](3/-1)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* Q * . * . * .
. * . * Q * . *
* . * . * . Q .
Q * . * . * . *
* . Q . * . * .
. * . * . * . Q
* . * . * Q * .
. * . Q . * . *

[20](-3/1)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . Q . * . * .
. * . * . Q . *
* . * . * . * Q
. Q . * . * . *
* . * Q * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *

[28](-2/-2)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . Q . * . * .
. * . * Q * . *
* Q * . * . * .
. * . * . * . Q
* . * . * Q * .
. * . Q . * . *
* . * . * . Q .
Q * . * . * . *

[41](3/0)(-3/2)(1/3)(3/2)(2/-1)(1/3)(-2/3)(-3/-1)
* . * Q * . * .
. * . * . * . Q
Q . * . * . * .
. * Q * . * . *
* . * . * Q * .
. Q . * . * . *
* . * . * . Q .
. * . * Q * . *

[6](3/2)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . Q . * .
. Q . * . * . *
* . * Q * . * .
. * . * . Q . *
* . * . * . * Q
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *

[10](-3/-1)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * . * Q
. Q . * . * . *
* . * Q * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *
* . Q . * . * .
. * . * . Q . *

[36](3/0)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * Q * . * .
. * . * . Q . *
* . * . * . * Q
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. Q . * . * . *

[11](-1/-3)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . * . Q .
. * . * Q * . *
* . Q . * . * .
Q * . * . * . *
* . * . * Q * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *

[38](-3/0)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * Q * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. * Q * . * . *

[28](-1/-2)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * Q * . * .
. * . * . * Q *
* . * . Q . * .
. * Q * . * . *
Q . * . * . * .
. * . * . Q . *
* . * . * . * Q
. Q . * . * . *

[9](-2/-3)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . * Q * .
. * . Q . * . *
* Q * . * . * .
. * . * . * . Q
* . * . Q . * .
. * . * . * Q *
Q . * . * . * .
. * Q * . * . *

[21](-1/-2)(-3/2)(1/3)(3/2)(2/-1)(1/3)(-2/3)(-3/-1)
* . * . Q . * .
. * . * . * Q *
* Q * . * . * .
. * . * . Q . *
* . Q . * . * .
Q * . * . * . *
* . * . * . * Q
. * . Q . * . *

[7](0/3)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* Q * . * . * .
. * . * . * . Q
* . * . * Q * .
Q * . * . * . *
* . Q . * . * .
. * . * Q * . *
* . * . * . Q .
. * . Q . * . *

[13](-2/-2)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . Q . * . * .
. * . * . Q . *
* . * Q * . * .
. Q . * . * . *
* . * . * . * Q
. * . * Q * . *
* . * . * . Q .
Q * . * . * . *


위의 결과에서 볼 수 있듯이 500세대 후 총 24개의 서로 다른 배열을 얻을 수 있습니다.

GA - 여덟여왕문제(8-Queen's Problem)[3] - 다양성에 대하여

6. 1차결과

앞에서 나온 대로 교차와 돌연변이를 실행하여 16384개의 하렘을 500세대동안 진화시켰습니다.
그 결과는 다음과 같습니다.

Generation : 499 : 1
[16349](0/-3)(3/2)(-2/3)(3/2)(2/-1)(1/3)(-2/3)(-3/-1)
* . Q . * . * .
. * . * . Q . *
* Q * . * . * .
. * . * . * Q *
* . * . Q . * .
Q * . * . * . *
* . * . * . * Q
. * . Q . * . *

.은 체스판의 흰 칸, *은 검은 칸, Q는 여왕이 위치한 자리입니다. 분명히 찾긴 찾았는데... 전체 16384개의 하렘들 중 동일한 하렘이 16349개나 생겼군요. 다양성이 완전히 훼손되고 말았습니다. 왜 이런 결과가 나왔을까요?

다른 형태의 해답 A, B, C, D가 유전자 알고리즘에 의해 생겼다고 해 봅시다. 개체 비율은 다음과 같다고 가정해 보죠.

A	B	C	D
25.01%	25%	25%	24.99%

재생산시 A, B, C, D는 동일한 적응도를 가지므로 각각이 선택될 확률은 각각의 개체비율과 동일합니다. 이때 A와 A가 만나 교배를 한다면 A가 다시 나오겠죠. A와 B가 만나 교배를 한다면, 이미 나온 답을 섞으면 그것은 엉뚱한 해답, 곧 낮은 적응도를 가진 개체가 나올 것입니다.
즉, 다음세대에 A가 나올 확률은 전세대의 A가 선택될 확률의 제곱이 됩니다(A가 두개 선택되어야 교배결과 A가 나오므로). 그러므로 다음 세대 각 개체의 비율은

A	B	C	D
6.255001%	6.25%	6.25%	6.245001%
25.02%	25%	25%	24.98%

약간 많던 A의 개체비율은 더 올라갔고(25.01%->25.02%) 반대로 약간 적던 D의 개체비율은 더 떨어졌습니다(24.99%->24.98%). 이런 식으로 해서 세대가 반복되면 다음 그림과 같이 불과 20세대도 지나기 전에 A가 전체를 차지해 버립니다.


즉 불과 0.01% 우세였던 개체가 자신과 같은 점수였던 다른 개체들을 밀어내고 혼자 전체를 차지해 버리는 것이죠.

그렇다면 어떻게 해야 이 시스템의 다양성을 유지하여 많은 해답을 구할 수 있을까요?

GA - 여덟여왕문제(8-Queen's Problem)[2] - 재생산

3. 적응도 계산
역시 자세한 알고리즘은 생략하겠습니다. 각각의 하렘들의 유전자에 따라 여왕들을 배치한 후 각각의 여왕들에 대해 진로를 가로막고 있는 다른 여왕이 있는지 살핍니다. 자신의 진로 위에 다른 여왕이 있을 때마다 ConflictNumber를 하나씩 더합니다. 만약 다른 여왕이 같은 자리를 차지하고 있을 경우, 그 여왕은 가로, 세로, 양쪽 대각선(2~7시방향, 11~5시방향) 네 진로에 걸리므로 ConflictNumber가 4 증가됩니다.
이 하렘의 전체 적응도는 -ConflictNumber가 됩니다(결국 이 문제도 -적응도를 가지게 되었군요)

4. 재생산 대상 선택
앞에서와 같이 Tournament법을 사용했습니다. 다만 여기서는 4차 Tournament법을 사용했습니다.

난수를 통해 16개의 재생산 후보를 골라냅니다. 그리고 이 16개의 후보들을 토너먼트 방식(일반적인 Tournament법과 같이, 0~1 사이의 난수를 발생시켜, 상수 T보다 작으면 적응도가 큰쪽, 상수 T보다 크면 적응도가 작은 쪽이 승자)으로 계속 경쟁시켜 최후의 승자를 재생산 후보로 결정합니다.

5. 교차

여기서는 유전자에 대한 특정한 제한이 없으므로 일반적인 교차를 사용할 수 있습니다. 이 문제에서는 랜덤교차를 사용했습니다.
다만 이경우에, '유전자의 최소단위'가 어떻게 될지 생각해 보는 것이 좋겠군요.

㉠:[(-2/ 1)( 1/ 2)(-3/ 2)(-3/-2)(-3/ 1)( 2/ 3)(-1/ 3)(-2/-1)]
㉡:[(-2/ 1)( 1/ 2)(-2/ 3)( 3/ 2)( 2/-1)(-1/-3)( 3/-2)(-1/ 3)]

위와 같은 두 유전자를 교차시킨다고 생각해 봅시다. 만약

㉠:[(-2/ 1)( 1/ 2)(-3/ 3)( 3/ 2)( 2/-1)(-1/-3)( 3/ 3)(-2/-1)]
㉡:[(-2/ 1)( 1/ 2)(-2/ 2)(-3/-2)(-3/ 1)( 2/ 3)(-1/-2)(-1/ 3)]

와 같이 교차를 시켰다면, ㉠의 (-3/ 3), ( 3/ 3), ㉡의 (-2/ 2)는 (재생산 전에는 앞의 퀸과 부딫치지 않는 위치였음에도) 앞의 퀸과 충돌하는 위치가 되어 버립니다. 그러므로 이 경우에 유전자의 최소단위(bit)는 () 안의 요소가 되어야 합니다.
이 문제에서는 랜덤교차를 사용했으므로 교차 후의 결과는

㉠:[(-2/ 1)( 1/ 2)(-2/ 3)(-3/-2)( 2/-1)( 2/ 3)(-1/ 3)(-2/-1)]
㉡:[(-2/ 1)( 1/ 2)(-3/ 2)( 3/ 2)(-3/ 1)(-1/-3)( 3/-2)(-1/ 3)]

가 될 수 있습니다.

procedure CrossOver(Harem A, Harem B)
.. for k := 0, 8 do
..... if Random(0, 1) > 0.5 then
........ dx := A.gene[k].dx
........ dy := A.gene[k].dy
........ A.gene[k].dx := B.gene[k].dx
........ A.gene[k].dy := B.gene[k].dy
........ B.gene[k].dx := dx
........ B.gene[k].dy := dy
..... end
.. end
end

6. 돌연변이
여기서는 0.0001 확률로 돌연변이시킵니다. 단 이경우에는 dx와 dy에 대해 따로 돌연변이를 시킵니다.

procedure Mutantation(Harem A)
.. for k := 0, 8 do
..... if 0.0001 > Random(0, 1) then
........ A.gene[k].dx := Random(-4, 5) // -4~4 사이의 랜덤값
..... end
..... if 0.0001 > Random(0, 1) then
........ A.gene[k].dy := Random(-4, 5) // -4~4 사이의 랜덤값
..... end
.. end
end

창조론 이야기 - 창조론이 사이비과학인 이유

1. 과학의 시작조건은 나는 아무것도 모른다입니다. 아무것도 모르는 상태에서 현상을 관찰하고 가설을 세우고 증거를 찾아 이론을 정립해 나가는 것입니다.
선입견은 과학에 있어서 금기입니다. 과학역사상 발생한 오류들은 대부분이 이 선입견으로부터 발생한 것입니다. 창조론자들이 즐겨 인용하는 네브라스카인의 경우도 '이것은 사람의 화석이다'라는 선입견 때문에 오류가 생긴 것입니다.

반면 창조론의 시작은 '나는 (성경에 의해) 모든 것을 알고 있다'입니다. 현상으로부터 이론을 정립하는 것이 아니라 반대로 성경에 의한 이론 - 창조론부터 정립해 놓고 증거를 찾아다니는 것입니다. 말하자면 선입견을 금기시한 것이 아니라 아예 선입견으로부터 시작한 것이죠.

발견된 증거가 창조론과 맞지 않아도 이론을 고칠 수는 없습니다. 창조론자들에게 있어서 창조론은 자연의 법칙을 밝히는 것이 아니라 자신의 신앙을 고백하는 수단이기 때문입니다. 그때문에 그들은 증거를 왜곡해서라도 창조론에 끼워맞추어야 합니다.
그러면서도 창조론자들은 진화론의 과정에서 나타나는 여러가지 (그마저도 창조론자들이 알아내기 전에 진화론자들이 먼저 알아내고 고쳐낸) 실수들을 가지고 진화론이 사이비과학이라고 주장합니다. 이를테면, 창조론자들이 주로 이야기하는 필트다운인 같은 경우도 그 오류를 발견해 고친 것은 창조론자가 아니라 진화론자들이었습니다.

2.과학이론은 후에 발견된 증거에 의해 수정되는 경우가 많습니다. 특히 진화론 같이 역사가 깊지 않은 분야는 하루가 다르게 발견되는 새로운 정보들에 의해 기존 이론이 수정되는 일이 잦습니다.
창조론자들은 이러한 이유로 진화론을 '믿을 수 없는 것'이라고 비난하곤 합니다. '어차피 내일이면 다른 이론으로 바뀔 것'이라고 말이죠.

그러나 그러한 수정이 아무리 많이 일어난다고 해도 큰 줄기가 바뀌는 일은 없습니다. 저차가 흰색차냐 회색차냐 정도의 논쟁이지 저것이 차냐 배냐 하는 논쟁은 아니라는 것입니다. 오히려 그러한 논쟁이야말로 진화론을 더욱 단단하게 만드는 원인입니다. 왜냐하면 나중에 창조론자들에게서 나올 문제점이 진화론자들 사이에서 먼저 나와 미리 연구가 되기 때문입니다.

바다로 나간 배가 있습니다. 매일밤 천체를 관측해서 진로를 수정하는 배㉮와, 나침반이 다른 방향을 가리키는 상황에서도 '성경에 의하면 이 방향이 맞다'고 한방향으로만 곧장 가는 배㉯ 중에서 어떤 배가 목적지에 도달할 수 있을까요? 비록 ㉯는 ㉮에게, '맨날 진로를 바꾸니 목적지에 도달할 수나 있겠냐'고 비웃고 있지만 말입니다.


3. 창조론자들은 창조론을 믿습니다. 그러므로 진화론자들도 진화론을 믿고 있다고 생각합니다.
하지만 진화론자들은 진화론을 믿는 것이 아닙니다. 창조론보다 진화론의 증거가 설득력이 있기에 진화론을 인정하는 것이죠.
반면 창조론자들은 창조론보다 진화론의 증거가 설득력이 있음에도 불구하고 창조론을 믿고 있는 것입니다. 믿음이란 증거가 필요 없으니까 말입니다. 창조론자들이 창조론의 증거를 찾고 있는 것은, 자신들의 믿음이 그만큼 얕다는 증거밖에 되지 않습니다.


4. 어떤 신비한 현상이 관찰되었습니다. 과학자들은 상상력을 동원해서 가설을 세우고, 그 가설을 뒷받침할 증거를 찾습니다. 증거를 찾을 수 없다면 그 가설을 폐기하고 다시 상상력을 동원해서 가설을 세우고, 그 가설을 뒷받침할 증거를 찾습니다. 증거를 찾을 수 없다면 그 가설을 폐기하고 다시 상상력을 동원해서 가설을 세우고, 그 가설을 뒷받침할 증거를 찾습니다. 증거를 찾을 수 없다면 그 가설을 폐기하고 다시 상상력을 동원해서 가설을 세우고, 그 가설을 뒷받침할 증거를 찾습니다. 증거를 찾을 수 없다면 ....
이렇게 끝없이 반복하는 것이 과학이죠. 저런 단계를 생략하고 '저것은 신의 작품임에 틀림없다'고 말하는 것은 종교이지 과학이 아닙니다.

무엇보다 창조론자들이 시원한 에어컨 또는 따뜻한 보일러 옆에서 컴퓨터로 노아의 홍수니 지구가 6000살이니 하는 뻘글들을 쓸 수 있는 것은 '모든 것은 신의 작품'이라 주장하는 창조론자들 덕은 아니죠.

GA - 여덟여왕문제(8-Queen's Problem)[1] - 유전자설계, 초기화

체스판 위에 여왕이 서 있습니다. 아시다시피 체스에서의 여왕은 가로, 세로, 대각선으로 진행할 수 있습니다. 만약 체스판 위에 8명의 여왕이 서 있을 경우, 그 여왕들이 서로의 진로를 방해하지 않도록 자리를 잡으려면 어떻게 해야 할까 하는 문제가 8-Queen's Problem이죠.
이 문제의 한가지 해답은 다음과 같습니다.



하지만 이 문제의 해법은 단 하나가 아닙니다. 유전자 알고리즘을 사용해서 이 문제의 해를 (가능한 한 많이) 찾는 것이 목적입니다.

이 문제는 사실은 n-Queen's Problem입니다. 즉 가로세로 n간인 체스판 위에 서로의 진로를 방해하지 않는 n명의 여왕의 자리를 찾는 문제죠. 여기서는 n=8일 경우만 하겠지만 더 크거나 작은 경우 역시 같은 방식으로 찾을 수 있습니다.

1. 유전자 설계
체스판 위에 8명의 여왕 위치를 유전자화시키는 방법은 무엇이 있을까요?

1-1 절대위치지정
가장 간단한 방법이죠. 단순히 8명 여왕의 위치를 좌표로 나열하는 방법입니다.
이를테면, 유전자가
[(7,4)(3,5)(2,6)(4,1)(0,6)(3,5)(3,7)(6,0)]
일 경우, 여왕들은 다음과 같은 자리를 잡게 됩니다. (3, 5)번째 칸에는 두 여왕이 같이 서 있군요.


1-2 상대위치지정
상대위치지정법은 각 좌표가 절대좌표가 아니라 바로 앞 여왕으로부터의 상대좌표를 의미합니다. 만약 유전자가
[(2,3)(-1,4)(-3,1)(6,-2)(3,-5)(-2,1)(-1,4)(4,-2)]
일 경우 여왕들의 자리는 ((0,0)부터 출발해서) 다음과 같이 됩니다. 역시 (4,6)에는 두 여왕이 겹쳐 있군요.


그렇다면 위에서 제시된 절대위치지정법과 상대위치지정법 중에서 어떤 것을 쓰는 것이 좋을까요?

유전자설계시 조심해야 할 점은 '교차시 더 좋은 유전자가 나오도록' 설계를 해야 한다는 점입니다. 이 문제의 핵심은 '다른 여왕의 진로를 방해하지 않는' 위치를 찾는 것입니다. 그러므로 각 여왕 들의 절대적인 위치보다는 각 여왕 사이의 상대적인 위치가 보다 중요합니다. 그러므로 상대위치지정을 했을 경우 교차를 적용한 후에도 앞쪽 퀸의 위치에 따라 자신의 위치가 재조정되므로 교차에 의해 적응도가 줄어드는 현상이 줄어들 수 있습니다.
그러므로 이 문제에서는 상대위치를 지정하는 유전자를 쓰기로 했습니다.


2. 유전자 초기화
하나의 하렘(Harem : 왕비(Queen)들이 모여있는 곳이니...^^ Queen에는 여왕이란 뜻 외에 왕비란 뜻도 있죠.) 유전자는 8쌍의 (dx,dy)로 구성됩니다. 각각의 dx, dy에 임의의 값을 넣어 최초의 하렘을 만들 수 있습니다.

procedure InitGene(Gene gene)
.. for bit := 0, 8 do

..... gene[bit].dx = Random(-4, 5) // -4~4 사이의 랜덤값

..... gene[bit].dy = Random(-4, 5) // -4~4 사이의 랜덤값

.. end

end

16384개의 하렘을 만들어 위와 같은 알고리즘으로 초기화시킨 후 각 하렘들에 대해 유전자 알고리즘을 적용합니다.

진화론 이야기 - 시뮬레이션(simulation)

다윈 이후 백여년간 진화론은 (진정한 유사과학인) 창조론계로부터 '유사과학'이라는 비난을 받아 왔습니다. 물론 이것은 종교적 도그마를 과학에 도입하려는(또는 과학을 종교의 도구로 삼으려는) 창조론자들의 딴지이긴 했습니다만, 한편으로는 진화론 자체가 실험이 불가능한 과학이라는 한계를 가지고 있었기 때문이기도 합니다. 진화라는 현상이 최소한 수천년단위로 일어나기에 진화의 정확한 메커니즘을 실험을 통해 밝히기가 쉽지 않았기 때문입니다.

하지만 20세기 중후반에 들어 진화론자들은 강력한 실험도구를 얻을 수 있었습니다. 바로 컴퓨터죠. 유전자의 움직임을 (때로는 화학반응 수준에서, 때로는 재생산과 돌연변이 수준에서) 묘사하는 시뮬레이션을 통해 생물의 진화과정에서 어떤 일이 벌어지는지 분석할 수 있게 되었습니다.

컴퓨터에서 유전자를 시뮬레이션하면 대부분 다음과 같은 과정이 벌어집니다.(물론 이름은 학술적인 이름이 아닙니다.)

1. 낙원기(Era of Paradise)
시 뮬레이션의 초기단계입니다. 주변에 자원은 많고 유전자는 적으니 유전자들은 마음껏 자원을 얻어 번식을 할 수 있죠. 이 시기에는 보다 효율적인 번식을 해나가는 유전자들이 대세를 차지합니다. 보다 적은 자원으로 보다 빠른 시간에 번식을 하는 유전자들로 가득 차게 됩니다.

2. 경쟁기(Era of Competition)
유전자들은 점점 많아지고 슬슬 자원의 부족이 찾아옵니다. 여기서부터 유전자들의 이전투구가 극심해집니다. 무슨 수를 써서든 자원을 모아 자신의 복제를 만드는 유전자가 대세를 차지하기에, 옆에 있는 유전자를 분해해서 자신의 복제를 만들 재료로 삼는 만행(?)도 사양치 않습니다.

3. 협동기(Era of Cooperation)
밑의 죄수의 딜레마에 서도 언급했지만 일부의 유전자들이 협동의 방법을 알아냅니다. 물론 그들의 성급한 협동시도는 주위의 다른 유전자들에게 먼저 이득을 주겠지만, 그들끼리 만난다면 이기적인 주위의 다른 유전자에 비해 훨씬 효율적으로 번식해 나갈 수 있습니다. 결국 협동하는 유전자들은 시뮬레이션공간을 가득 채우게 됩니다.

4. 기생기(Era of Parasite)
서로 협력하는 유전자들 사이에서 기생충이 나타납니다. 이들은 다른 유전자를 착취한다는 점에서는 협동기때의 수많은 유전자들과 비슷하지만, 그 착취의 방법이 전문화되었다는 점이 다릅니다. 즉, 눈에는 눈 전략을 가진 숙주로부터 착취하기 위해 숙주를 속이는 쪽으로 발달한 것입니다. 하지만 그런만큼 기생충들은 자력생존은 불가능하죠. 지나치게 번식해서 숙주의 수가 줄어든다면 기생충들 역시 위기에 빠질 수밖에 없습니다.

5. 극복기(Era of Overcome)
숙주가 마침내 기생충을 찾는 방법을 알아내고 기생충에게 눈에는 눈 전략을 시전할 수 있게 됩니다. 즉 기생충을 상대로 승리할 수 있는 것이죠. 하지만 기생충은 사라지지 않습니다.

6. 기생충들은 숙주를 피하는 새로운 방법을 찾아내어 되돌아와 4번부터 되풀이됩니다.

이를테면, 숙주가 완벽하게 기생충을 찾는 방법을 찾아내어 기생충을 몰아냈다고 하더라도 기생충은 시간이 지나면 (거의 반드시) 되돌아옵니다. 왜냐하면 기생충을 찾는 방법 자체가 시간과 자원을 소모하는 과정이기 때문이죠.
기생충이 있는 상황에서는 시간과 자원을 소모하여 기생충을 검색해 없애는 숙주가 번식에 유리합니다. 그러나 기생충들이 추방된 상황에서는 더이상 기생충을 검색하는 행위는 시간과 자원을 소모할 뿐인 일이 되죠. 그때는 기생충 검색을 생략하는 숙주가 유리해져 번성하고 그에따라 기생충이 다시 돌아올 터전이 만들어지는 것입니다.

그러한 '기생충'들은 유전자의 세계에만 있는 것이 아닙니다. 현실사회에서도 사회를 좀먹는 기생충들이 존재하죠.
그때문에 원시사회에서조차 그런 기생충을 막기 위한 '사회 규범'이 존재합니다(진화론적으로 말하자면 그런 사회규범이 없는 사회는 이미 붕괴해 버렸다고 할 수 있습니다).
다만 그런 사회규범은 '약속을 어기면 도깨비가 나타나 약속할때 걸었던 손가락을 잘라먹어버린다', '거짓말을 하면 이가 모두 빠진다' 등등 미신적이고 주술적인 모습으로 전해내렸기에 현대인에게 폄하당하고 있을 뿐입니다.
하지만 아주 옛날 사람들에게 '약속을 어기면 상대방도 약속을 어기게 되고 결국에는 서로가 믿지 못하는 사회가 된다'는 설명보다 '약속을 어기면 도깨비가 나타나 약속할때 걸었던 손가락을 잘라먹어버린다'는 설명이 훨씬 이해되기 쉬웠겠죠. '서로가 거짓말을 하면 결국 다른 사람의 말을 믿지 못하게 되고 그것은 사회공동체의 불이익이 된다'는 설명보다 '거짓말을 하면 이가 모두 빠진다'는 설명이 훨씬 간단하면서도 쉽게 와닿는 설명일 것입니다.

불행하게도 일제시대 이후 급격한 근대화를 이루면서 과거의 많은 사회규범은 '미신'이라는 이유로 대부분 사라졌습니다. 한편 그것들을 대신할 새로운 사회규범이 만들어지지는 않은 상태입니다. 그 때문에 지금 우리사회가 어지러운 것이겠죠.