진화론 이야기 - 신대륙 원숭이의 색각

삼원색 색각에 대해 조사해 보는 동안 흥미로운 사실을 알게 되었습니다.

여기서 신대륙의 짖는원숭이(고함원숭이)를 제외한 다른 원숭이들 중에서도 3원색을 보는 원숭이가 있다고 하더군요. 그것도 일부 암컷에서만 말입니다.
어떤 이유로 전체도 아닌 '일부 암컷'에서만 삼원색을 볼 수 있을까요?

진화론 이야기 - 색각의 진화에서 썼듯이 인간을 비롯한 영장류들의 색각유전자 중 하나는 상염색체에, 다른 하나는 성염색체에 있습니다. 여기서 성염색체 중 하나의 색각유전자에 돌연변이가 일어난다면 어떻게 될까요?

이 원숭이(X유전자 2개이므로 암컷)는 상염색체상의 유전자와 함께 3개의 색상을 보는 원숭이가 될 것입니다.
이 원숭이가 새끼를 낳으면 어떤 새끼가 태어날까요?

결국 이 원숭이무리의 유전자는 다음과 같이 분포됩니다.

이와같이 이 원숭이 무리에서 오직 4번 암컷만이 3원색을 보는 암컷이 될 테고 나머지는 2원색만을 볼 수 있을 것입니다.
물론 (1,3)번이 보는 세상과 (2,5)번이 보는 세상은 다르겠죠. 1번과 2번 원숭이가 모이면 이런 대화를 하지 않을까 생각됩니다.

1 : 어? 넌 어떻게 그렇게 맛있게 익은 열매만 골라내냐?
2 : 넌 어떻게 풀숲에 숨어있는 표범을 그렇게 쉽게 찾아내냐?

진화론 이야기 - 색각의 수렴진화

영장류는 주로 아프리카와 동남아시아, 그리고 남아메리카에 주로 분포합니다. 태평양과 대서양으로 나뉘어진 양 대륙에 분포하는 것을 보면, 아프리카와 아메리카가 나뉠때 서식지가 나뉘어져 서로 각자 진화해온 것으로 추정됩니다. 물론 영장류의 한 종(species)인 '사람 sapiens'은 예외죠. 그들은 두 대륙이 나뉜 이후 아프리카대륙에서 진화했지만, 특이하게 강한 '호기심'을 가지고 있었습니다. 그 때문에 태평양을 건너 오스트레일리아로, 그리고 빙하기로 바다가 줄어든 기회에 베링해협을 건너아메리카대륙으로 이주를 했습니다.

진화론 이야기 - 사인배열(SINE)에서도 언급했었지만, sine 배열 또는 line(long interspersed nuclear elements) 배열을 이용하면 두 종의 진화적 거리를 알 수 있습니다. 그들은 영장류들의 유전자를 분석해서 다음과 같은 진화계통도를 만들었습니다.

여기서 세가지 색으로 표시된 것은 사람처럼 3원색 색각을 가지고 있는 영장류, 두가지 색으로 표시된 것은 2원색 색각을 가진 영장류들입니다. 보시다시피 구대륙(아프리카, 아시아) 영장류들은 모두 3원색 색각을 가지고 있지만 신대륙(아메리카) 영장류들 중에서는 오로지 하나, 짖는원숭이(고함원숭이)뿐입니다.

어떻게 해서 신대륙원숭이들 중에 짖는원숭이만이 삼원색 시각을 가지고 있을까요?

구대륙원숭이와 짖는원숭이만이 가지고 있는 삼원색을 설명하기 위해서는 다음과 같은 두가지 가설이 가능합니다.

첫째, 구대륙원숭이와 짖는원숭이의 공통선조가 3원색을 가지게 되었고, 그들을 제외한 다른 원숭이들은 모두 3원색 시각을 잃었다.

새로운 유전정보가 만들어지기보다는 유전정보를 잃는 것이 쉽다는 면에서는 위와 같은 시나리오가 가능합니다. 다만 진화론 이야기 - 색각의 진화에서 보듯 색각의 퇴화는 동굴생활이나 야행성처럼 빛이 없는 곳에서 활동할 경우에 일어납니다. 야행성이 아닌 주행성 원숭이들 사이에서도 색각의 퇴화가 일어난다는 것이 납득하기가 힘듧니다.

둘째, 구대륙원숭이의 공통조상과 짖는원숭이에게서 똑같은 진화가 일어났다

과연 3원색으로의 진화가 두번 일어날 수 있었을까요?

과학자들은, 구대륙원숭이의 유전자를 분석해서, 그들이 3원색을 볼 수 있도록 만든 유전자중복의 흔적 - 염기쌍 236개의 흔적 - 을 찾아냈습니다. 마찬가지로 짖는원숭이의 유전자에서도 중복의 흔적을 찾아냈습니다. 그 흔적은 구대륙원숭이에 비해 훨씬 길었습니다.

즉, 구대륙원숭이의 3색각진화와 짖는원숭이의 3색각진화는 서로 다른 사건이었음을 알 수 있는 것입니다.

더욱이, 구대륙원숭이에 있어서, 중복된 부분에 일어난 돌연변이는 약 5%에 이릅니다. 하지만 짖는원숭이의 변이량은 2%대에 불과하죠. 이것은 구대륙원숭이에 비해 짖는원숭이에 일어난 변이가 훨씬 늦게 일어났다는 증거입니다.

출처 : 한치의 의심도 없는 진화 이야기

진화론 이야기 - 색각의 진화

다윈 이후 많은 생물학자들은 조류의 화려한 깃털에 주목했습니다. 여러모로 깃털의 색깔에 대해 연구를 해 왔습니다.
하지만 최근까지 그들의 연구는 제대로된 연구가 아니었습니다. 사람들이 보는 시야와 새들이 보는 시야는 전혀 다르기 때문이죠.

푸른 박새를 연구한 과학자들은 이런 말을 했습니다.

푸른 박새는 사실은 자외선박새다.

왜냐하면 푸른 박새를 자외선광 밑에서 보면 이런 모습이거든요.

푸른 색깔이었던 정수리가 푸른색 파장 뿐 아니라 자외선도 강하게 반사하고 있기 때문입니다. 그리고 박새뿐 아니라 많은 조류들은 자외선을 이용하고 있습니다. 눈으로 보기에는 단색으로 보이는 부분도 자외선카메라로 찍으면 무늬가 보이는 경우가 많습니다.
즉, 자외선 시각을 가지고 있는 조류들은, 사람은 그냥 밋밋한 단색으로 보이는 새들도 울긋불긋 화려한 무늬를 가진 모습으로 볼 수 있다는 것이죠.

출처

옵신 구조[동아사이언스]

척추동물의 망막에는 옵신(opsin)이라는 광감지단백질이 존재합니다. 옵신 안에 들어있는 레티날(retinal)이 빛을 흡수하며, 레티날 주변의 아미노산 종류에 따라 흡수하는 파장이 달라집니다(즉 감지할 수 있는 색깔이 달라집니다)

조류의 경우에는 4가지 옵신을 만들 수 있기에 4가지 색을 구분합니다. 반면 사람은 3가지 색만을 구분할 수 있습니다.

사람이 감지할 수 있는 3가지 색각은 각각 SWS(short wave sensitive), MWS(medium wave sensitive), LWS(long wave sensitive)라고 합니다. 여기에 조류는  UVS(ultraviolet sensitive)까지 가지고 있죠.
반면 개나 고양이 같은 다른 포유류들은 2가지 색각 - SWS와 MWS만을 가지고 있습니다.

왜 이런 차이가 생겨난 것일까요?

과학자들은 이 차이가 공룡시대에 일어났다고 설명합니다. 조류의 선조인 공룡이 낮시간에 활보하는 동안, 공룡에 밀린 포유류들은 밤시간대로 진출합니다. 풍부한 빛 속에서 조류(공룡류)들은 빛을 보는 파장을 진화시키는 한편, 포유류들은 있던 시각유전자마저 잃어버리고 단 두가지 파장만 감지할 수 있게 된 것입니다. 마치 피 없는 물고기에서처럼, 빛이 없는 환경에서는 망가진 색각유전자를 도태시키는 자연선택이 일어날 수 없는 것입니다.

그런데 사람을 비롯한 구대륙(아시아-유럽-아프리카)에 서식하는 영장류들은 다른 포유류들과는 달리 3가지 색을 볼 수 있습니다. 다른 포유류들과는 달리 붉은색 파장을 보는 LWS도 가지고 있는 것입니다. 그들의 주된 먹이인 잘 익은 열매, 또는 부드러운 새순을 찾기 위해서는 붉은색 색각이 필수적이기 때문이죠.

과연 이 영장류들은 조상의 2색 시각에서 3색 시각으로 어떻게 정보를 늘렸을까요?

인간의 경우 SWS는 7번 유전자(물론 다른 포유류에서는 다른 유전자)에 존재합니다. 반면 LWS와 MWS는 성염색체인 X염색체에, 그것도 바로 옆에 인접해서 붙어 있습니다.

다른 포유류들의 경우에는 X염색체에 MWS 하나만 존재합니다. 이 염색체가 복제중 중복에 의해 색각유전자가 2개로 늘어나고, 그중 하나가 돌연변이에 의해 붉은색 파장을 감지하는 LWS로 바뀐 것이죠

창조론자들은 유전정보가 증가하는 경우는 없다고 하지만, 이와 같이 유전정보가 증가하는 것은 충분히 가능합니다. 물론 창조론자들의 입장에서는 받아들이지 않죠. '이것은 유전정보의 증가가 아니다'라고 계속 주장할 겁니다.
그들 입장에서는 대진화는 '아직 관찰되지 않은 진화'이며 정보증가는 '아직 관찰되지 않은 형질이 생기는 것'일 뿐이니까요. 그러므로 어떤 진화가 관찰되어도 그것은 '소진화'(이미 관찰되었으니)이며 어떤 정보의 증가가 관찰되어도 정보의 증가가 아닌(역시 이미 관찰되었으므로)것입니다.

출처 : 한치의 의심도 없는 진화 이야기

진화론 이야기 - 모든 인간은 돌연변이다

사람들이 과학에 대해 잘못된 상식을 가지고 있는 경우가 많습니다. 대표적인 것이 진화론에 관련된 것들이죠.

'나는 상대성이론에 대해 잘 알고 있다'라고 생각하는 사람이나 '나는 양자역학에 대해 잘 알고 있다'고 주장하는 사람은 별로 없습니다. 그렇지만 '나는 진화론에 대해 잘 알고 있다'라 생각하는 사람은 꽤 많죠.
특히나 진화를 언급하는 여러 영화(Evolution), 만화(포켓몬, 디지몬) 등으로 진화론을 배운 사람들에게서 많이 나타나는 현상입니다.
사실 포켓몬이나 디지몬 등에서 말하고 있는 '진화'는 진화가 아니라 '변태 變態 metamorphosis' 가 맞습니다. 바바리맨이나 SM같은 변태 올챙이가 개구리로 변태하거나 애벌레가 나비로 변태하는 것처럼 말이죠.

돌연변이 역시 마찬가지로 잘못알고 있는 경우가 많습니다. X-men이라든가 각종 SF물, 포스트 아포칼립스물에서 묘사된 돌연변이들에 의해 잘못 알고 있는 경우가 많습니다. 돌연변이라고 하면 이상한 초능력을 가지고 있다거나, 몸 여기저기서 촉수 같은 것을 달고 있다거나 눈이 셋, 팔이 넷이라거나...


그러나 실제로 돌연변이란 그렇게 거창한 것이 아닙니다. 유전자 복사 중에 오류가 생기면 그것이 바로 돌연변이입니다. 그리고 그런 복사오류는 매우 흔하게 나타나는 현상이며, 본체에 거의 영향을 주지 않습니다.

2015년 KBS '넥스트 휴먼'이란 기획물에서 나온 한장면입니다.

즉 돌연변이는 불가능하다고 주장하는 사람이나 돌연변이는 나쁜 방향으로 나타난다고 주장하는 사람도 약 35~50개, 많을 경우에는 100개가 넘는 돌연변이를 가지고 있는 셈입니다.
그럼에도 불구하고 그들은 X-men같은 초능력도 없고 등에 촉수가 돋아나지도 않은 '평범한 돌연변이'일 뿐이죠.

만약 그 돌연변이가 Junk DNA처럼 쓰이지 않는 부분에서 일어났다면 겉으로는 전혀 드러나지 않는 돌연변이가 될 것입니다.
만약 그 돌연변이가 눈 색깔을 결정하는 부분에서 일어났다면 눈 색깔에 돌연변이로 나타날 것입니다.
만약 그 돌연변이가 피부색을 결정하는 부분에서 일어났다면 피부 색에 돌연변이로 나타날 것입니다.
만약 그 돌연변이가 혈구를 만드는 부분에서 일어났다면 겸상적혈구증⁺으로 나타날 것입니다.

돌연변이에 의해 눈 색깔이 바뀐다거나 피부 색깔이 바뀌는 것이 즉각적으로 생존에 영향을 주지는 않습니다. 겸상적혈구증 역시 말라리아가 창궐하는 지역에서는 오히려 생존에 도움을 줍니다.
그러므로 이들 돌연변이들은 도태되지 않고 유전자풀에 남아있게 되며 이들이 진화의 추진력이 될 수 있는 것이죠.

⁺ 겸상적혈구증 역시 사람들이 잘못 알고 있는 경우가 많죠. 이것에 대해서는 다음에 따로 글을 올리겠습니다.

진화론 이야기 - 다윈과 멘델 2

'진화론 이야기 - 다윈과 멘델'에서도 한번 다루었지만 다윈의 진화론과 멘델의 유전법칙에 대해 오해하는 분들이 많더군요. 멘델의 유전법칙에 의하면 종이 변하는 일이 없기 때문에 다윈의 진화론이 부정된다고 말입니다.

http://www.kictnet.net/bbs/board.php?bo_table=sub5_1&wr_id=172&page=11

잠시 다른 이야기 좀 하죠.
중학교 과학에서 배우는 보일 샬의 법칙(Boyle-Charles' Law)이 있습니다. 기체의 온도와 압력, 부피에 관련된 식으로

입니다.
그런데 실제로 기체를 가지고 실험해 보면 저 식이 정확하게 맞을까요?
죄송합니다만 실제 기체로 실험을 해 본다면 정확하게 저 공식을 따르지 않습니다. 왜냐하면 저 보일 샬의 법칙은 이상기체(理想氣體 ideal gas), 즉 완전한 구형, 분자크기 0, 분자간 상호작용 0, 완전탄성충돌체인 가상적인 기체에서 정확하게 성립하는 법칙입니다. 그런데 실제 기체는 크기를 가지고 있고 분자간 인력도 발생하고 있죠.


마찬가지로 멘델의 유전법칙 역시 일반적인 유전자가 아닌 이상유전자(ideal gene)^*, 말하자면
1. 모든 유전자는 뚜렷하게 구분되는 성질(노랑 또는 초록)이 있다.
2. 유전자의 변이는 절대로 나타나지 않는다.
3. 자연선택 또는 실험자의 선택에 의한 유전자의 도태는 일어나지 않는다.
라는 조건 하에서만 정확하게 성립되는 법칙입니다.

하지만 실생활에서 저런 유전자가 존재할까요? 2번, 유전자의 변이는 절대로 나타나지 않는다 하나만으로도 이상적인 유전자는 존재하지 않습니다.

진화의 가장 중요한 요인이 유전자의 변이와 자연선택에 의한 도태입니다. 멘델의 유전법칙에서는 이 두 가지를 제외합니다. 그런데 멘델의 유전법칙으로 진화를 부정하는 것이 말이 된다고 생각하시는지요?

덧 :
위에서 이상기체(ideal gas)니 이상유전자(ideal gene)니 이야기하면서 법칙과 현실의 차이를 이야기했는데, 아마도 창조론자들 중에서 '실제와 차이가 나는 것이 무슨 법칙이냐'라고 할지도 모르겠군요(아니, 과학에 대한 창조론자들의 이해수준을 본다면 저런 말이 나올 가능성은 100%에 가까와 보입니다).
'이상기체에 적용되는 법칙'이란 말은 '최소한의 보정만으로 모든 기체'에 적용될 수 있는 법칙'이란 뜻입니다. 만약 산소기체라면 보일 샬의 법칙을 산소기체에 적용한 후 산소기체에 대한 보정을 하면 산소기체의 움직임을 이해할 수 있다는 뜻이죠.
마찬가지로 멘델의 법칙 또한 멘델의 법칙을 자연계의 유전자에 적용한 후 유전자에 대한 보정(돌연변이, 자연선택)을 하면 유전자의 움직임(진화)을 이해할 수 있다는 뜻입니다.

^* 학술적으로 통용되는 언어가 아니라, 유전법칙을 설명하기 위해 제가 만든 말입니다. 이상(異常)한 유전자가 아니라 이상(理想)적인 유전자를 말합니다. 하긴 너무나 이상(理想)적이라는 것 자체가 이상(異常)한 것이긴 합니다만.

엮인글 : 진화론 이야기 - 다윈과 멘델

GA - 자원운송계획 - 재생산

4. 재생산
8193개의 개체들 중 최고적응도의 개체를 골라 엘리트로 복사하고, 나머지 8192개의 개체는 유전자알고리즘을 사용해 재생산했습니다.
T=0.99의 Tournament법을 사용하여 우수개체를 골라 교차 및 돌연변이를 일으켰습니다.

5. 교차
일반적인 유전자알고리즘의 경우와 같이 여기서도 재생산 대상을 두개 선택한 후 그들을 교차시킵니다. 그러나 유전자가 예전의 1차원 유전자가 아니라 2차원 유전자라는 문제가 있습니다.
일반적으로 2차원 유전자의 교차는 (아니 1차원부터 2차원, 3차원 이상의 고차원 유전자의 교차는) 구획나누기 이후 구획 재배치로 정의될 수 있습니다. 문제는 구획을 어떻게 나누느냐가 됩니다.
다음의 보기는 2차원의 경우이지만 n차원으로 확장시킬 수 있습니다.

① 다음 그림과 같이 x, y축을 몇개의 구획으로 나눕니다. 그후 아래 그림과 같이 순서대로 교차시키는 것입니다. 이것은 1차원교차에서 주로 사용했던 n점교차를 확장한 형태입니다.

② 또다른 방법은 구획을 다음 그림과 같이 도형으로 나누는 경우도 있습니다. 이 경우에는 구획 재배치가 쉽지 않아 보이지만, 간단히 짝수(0 포함) 또는 홀수개의 도형에 포함되는 구획만 교환하면 생각보다 쉽게 됩니다.

③ 마지막으로 임의로 선을 그어 구획을 나눌 수 있습니다.
①, ②번은 각각 하나의 축만, 그리고 각 차원에서의 원/구를 생각하면 되므로 4차원 이상의 유전자에도 비교적 쉽게 적용할 수 있습니다. 그러나 ③번은, 개념적으로는 3차원에서는 3각형평면의 연속, 4차원에서는 삼각뿔 도형의 연속, ... 등으로 할 수 있으나 직관적으로 다가오지 않아 상당히 어려운 작업이 될 수 있습니다.
여기서는 3개의 임의의 원을 그려 ②번과 같은 식의 교차를 시행했습니다.

procedure CrossOver(MoonBase a, MoonBase b)
.. // 세개의 임의의 원을 만듦
.. for k := 0, 3 do
..... circle[k].f := Random(0, 10) // 유전자크기가 10X10이므로
..... circle[k].t := Random(0, 10)
..... circle[k].radius := Random(0, 10)
.. end
.. for f := 0, 10 do
..... for t := 0, 10 do
........ covered := 0
........ // 3개 원중 몇개에 겹쳐지는지 계산
........... for k := 0, 3 do
.............. // (f,t)와 k번째 원 중심간 거리 계산
.............. df := f - circle[k].f
.............. dt := t - circle[k].t
.............. dist := sqrt(df * df + dt * dt)
.............. // 만약 거리가 반지름보다 작다면(원에 포함된다면)
.............. if dist < circle[k].radius then
................. covered := covered + 1
.............. end
........... end
........ if covered % 2 then // 홀수개에 겹쳐져 있다면 교환
........... temp := a[f][t]
........... a[f][t] := b[f][t]
........... b[f][t] := temp
........ end
..... end
.. end
end


6. 돌연변이
10×10개의 칸 하나하나에 대해 돌연변이를 적용시킵니다.

procedure Mutantation(Gene gene)
.. for f := 1, 10 do
..... for t := 1, 10 do
........ if gene[f][t] == 0 then
........... if MutantationRate then
............. gene[f][t] := Random(0, 10)
........... end
........ else // f->t로의 운송량 있을 경우
........... if MutantationRate then // 운송을 제거
............. gene[f][t] := 0
........... end
........... else if MutantationRate then // 운송량 변경
............. gene[f][t] := gene[f][t] + Random(-1, 1)
........... end
........... else if MutantationRate then // 운송을 나눔
............. T := Random(1, 3)
............. split := Random(0, gene[f][t])
............. gene[f][t] := gene[f][t] - split
............. gene[f][T] := gene[f][t] + split
........... end
........ end
..... end
.. end
end

GA - CNNC를 실은 꼬마자동차[2] - 입력과 출력, 교차

5. 꼬마자동차의 신경망 입력
꼬마자동차가 알아야 할 정보는, 바로 앞의 블럭정보, 그리고 연료가 어디 있는지에 대한 정보입니다.
꼬마자동차 CNNC의 입력노드 중 3개는 앞쪽에 어떤 장애물이 있는지(있으면 1, 없으면 -1), 마지막 하나는 연료의 위치를 -1~+1 사이의 float값으로 입력합니다.

procedure Detect(Car car, StoneRoad road)
.. cl := car.Locate.Len
.. cw := car.Locate.Wid

.. // 앞쪽 3칸 블럭정보
.. if road[cl - 1][cw - 1] == ROCK then
..... SetCharge(car.CNNC, 0, 1) // 0번셀에 입력
.. else
..... SetCharge(car.CNNC, 0, -1)
.. end
.. if road[cl - 1][cw + 0] == ROCK then
..... SetCharge(car.CNNC, 1, 1) // 1번셀에 입력
.. else
..... SetCharge(car.CNNC, 1, -1)
.. end
.. if road[cl - 1][cw + 1] == ROCK then
..... SetCharge(car.CNNC, 2, 1) // 2번셀에 입력
.. else
..... SetCharge(car.CNNC, 2, -1)
.. end

.. // 기름통 위치정보(차에서 가장 가까운)
.. fl := road.Fuel(car).Locate.Len
.. fw := road.Fuel(car).Locate.Wid
.. SetCharge(car.CNNC, 3, (fw - cw) / (fl - cl)) // 3번셀에 입력
end

6. 꼬마자동차의 신경망 출력
신경망 출력을 꼬마자동차의 움직임으로 바꾸기 위해 3개의 출력노드를 사용합니다. 그리고 각 출력노드의 출력양에 따라 직진할지 왼쪽이나 오른쪽으로 움직일지 결정하는 것입니다.
그러나 신경망의 특성상 가능하면 노드수를 줄이는 것이 최적화시키는데 도움이 됩니다. 여기서는 출력노드를 두개로 만들어, 더 강한 출력을 보이는 쪽으로 이동시키도록 하겠습니다. 즉,

procedure Action(Car car, StoneRoad road)
.. left = 0
.. right = 0
.. l := GetCharge(car.CNNC, 0);
.. r := GetCharge(car.CNNC, 1);
.. if l > 0 then // 왼쪽으로 움직이려는 경향
..... left := left + l
.. else // -왼쪽(즉 오른쪽)으로 움직이려는 경향
..... right := right - l
.. end .. if r > 0 then // 오른쪽으로 움직이려는 경향
..... right := right + r
.. else // -오른쪽(즉 왼쪽)으로 움직이려는 경향
..... left := left - r
.. end
.. // 출력이 강한 쪽으로 이동
.. rnd := Random(0, 2)
.. if left > rnd then
..... if right > rnd then
........ MoveForwar(car)
..... else
........ MoveLeft(car)
..... end
... else
..... if right > rnd then
........ MoveRight(car)
..... else
........ MoveForwar(car)
..... end
.. end
end

출력노드를 하나로 해 놓고, +1에 가까울수록 왼쪽으로, -1에 가까울수록 오른쪽으로 움직이도록 할 수도 있지만, 생각만큼 수렴이 잘 되지 않더군요. 우선은 출력노드 두개짜리로 실행해 봤습니다.

7. 적응도 계산
위와 같은 식으로 256개의 꼬마자동차와 64개의 돌길 개체를 만듧니다. 이 256개의 꼬마자동차 각각은 64개의 돌길을 통과하고 각 꼬마자동차와 돌길의 적응도를 결정합니다.
① 꼬마자동차의 적응도 : 평지로 진입할 때마다 10점추가, 장애물을 통과할때 10점감점
② 돌길의 적응도 : 자동차가 기름을 먹으면 5점감점, 장애물로 진입하면 10점추가

8. 교차
꼬마자동차의 경우는 앞의 XOR회로와 같은 일반적인 CNNC식 교차를 사용했습니다.
돌길의 경우는 길 전체를 길이 100의 선형유전자로 간주하고 일반적인 일점교차를 사용했습니다.

procedure CrossOver(StoneRoad a, StoneRoad b)
.. cut := Random(1, 99)
.. for l := 0, cut do
..... for w := 0, 11 do
........ tmp := a[l][w]
........ a[l][w] := b[l][w]
........ b[l][w] := tmp
..... end
.. end
end

9. 돌연변이
돌연변이 역시 꼬마자동차의 경우에는 CNNC의 돌연변이 루틴을 사용합니다.
돌길의 돌연변이는 두 단계로 이루어집니다. 첫째, 일정한 확률로 장애물을 만들기(또는 장애물을 없애기), 둘째, 기름통 위치 바꾸기입니다.

procedure Mutantation(StoneRoad gene)
.. for l := 0, 99 do
..... for w := 1, 10 do // 가장자리는 장애물로 유지
........ if MutantRate then
........... if gene[l][w] == ROCK then
.............. gene[l][w] := ROAD
........... else if gene[l][w] == ROAD then
.............. gene[l][w] := ROCK
........... end
..... end
.. end

.. for l := 0, 99 do
..... for w := 1, 10 do // 가장자리는 장애물로 유지
........ if gene[l][w] == FUEL then
........... if MutantRate then
.............. gene[l][w] := ROAD
.............. gene[l][Random(1, 10)] := FUEL
.............. break // w 루프 탈춮
........... end
........ end
..... end
.. end
end

10. 재생산
256개 꼬마자동차들이 모두 64개 돌길에서 달려 본 후 꼬마자동차와 돌길을 재생산합니다. 역시 꼬마자동차의 경우는 CNNC의 재생산 루틴을 사용했으며(이 경우 상위 8개의 꼬마자동차를 다음 세대에 그대로 복사하는 Elitism을 사용했습니다.)
돌길의 경우에는 T==0.95, Round==4인 토너먼트법(임의로 2⁴=16개의 돌길을 고른 후 95%의 확률로 적응도 높은 쪽이 이기는 토너먼트를 4회 반복)으로 재생산시켰습니다.

GA - CNNC를 이용한 XOR 회로[4] - 돌연변이

6. 돌연변이
교차에 의해 만들어진 아기CNNC는 약간의 돌연변이 처치를 받습니다.
교차는 아무리 많이 하더라도 구조(라기보다는 히든노드 수)를 바꿀 수 없습니다. 그때문에 돌연변이가 필수인 것이죠.

돌연변이의 역할은 다음과 같습니다.

① 작은 돌연변이
이것은 구조를 바꾸기보다는 복제 후 각 노드의 상수(Bias, SigmoidFactor) 및 각 채널의 강도에 약간의 변경을 가합니다. 때로는 활성화되어 있던 채널을 닫거나 닫혀있던 채널을 열기도 합니다. 즉, 노드(세포) 갯수는 고정된 상태에서 새로운 연결을 만들거나 연결을 제거하는 역할을 합니다.
미소돌연변이는 큰 변이 없이 최적의 상수값을 찾아가기 위해 사용합니다.

procedure MicroMutantation(GeneNode node)
.. if MutantRate() then
..... node.Bias := Random(-5, 5)
.. else
..... node.Bias := node.Bias * Random(0.8, 1.2)
.. end

.. if MutantRate() then
..... node.SigmoidFactor := Random(-5, 5)
.. else
..... node.SigmoidFactor := node.SigmoidFactor * Random(0.8, 1.2)
.. end

.. for c := 0, gene.ChannelSize do
..... if node.RecvChannel[c] == 0 then
........ if MutantRate() then
.......... node.RecvChannel[c] := Random(-5, 5)
........ end
..... else
........ if MutantRate() then
.......... node.RecvChannel[c] := 0
........ else
.......... node.RecvChannel[c] := node.RecvChannel[c] * * Random(0.8, 1.2)
........ end
..... end
..... // SendChannel에 대해서도 동일한 처리
.. end
end

② 큰 돌연변이
거대돌연변이는 새로운 노드를 추가 또는 삭제하여 전혀 새로운 구조를 만들기 위해 사용됩니다.

procedure NodeAppend(Gene gene)
.. // 각 파라미터 초기화
.. newnode.Layer := Random(0, 1)
.. newnode.Bias := Random(-5, 5)
.. newnode.Sigmoid := Random(-5, 5)
.. //채널 초기화
.. for k := 0, ChannelSize do
..... newnode.RecvChannel[k] := 0
..... newnode.SendChannel[k] := 0
.. end

.. // 입력노드 연결
.. inputnode := NodeFind(gene, -100, 100)
..... // 모든 노드들(input node + hidden node + output node) 중에서 임의선택
.. channel := Random(0, ChannelSize)
.. newnode.RecvChannel[channel] := Random(-5, 5)
.. if inputnode.SendChannel[channel] == 0 then
..... inputnode.SendChannel[channel] := Random(-5, 5)
.. end

.. // 출력노드 연결
.. outputnode := NodeFind(gene, -100, 1)
..... // Layer가 0 이상(hidden node + output node) 인 것들 중에서 임의선택
.. channel := Random(0, ChannelSize)
.. newnode.SendChannel[channel] := Random(-5, 5)
.. if outputnode.RecvChannel[channel] == 0 then
..... outputnode.RecvChannel[channel] := Random(-5, 5)
.. end
.. gene.Insert(newnode)
end

procedure NodeRemove(Gene gene)
.. node := NodeFind(gene, 0, 1)
......... // Layer가 0과 1 사이(히든노드들) 중 임의의 노드 하나 선택
.. if node != NULL then
..... gene.Remove(node) // 제거할 히든노드가 있을 경우에만 삭제
.. end
end

그러므로 돌연변이 루틴은 다음과 같습니다.

procedure Mutantation(Gene gene)
.. // 작은돌연변이
.. for node := 0, NodeSize do
..... MicroMutantation(gene.Node[node])
.. end

.. // 큰돌연변이
.. if MutantRate() then
..... NodeAppend(gene)
.. else if MutantRate() then
..... NodeRemove(gene)
.. end
end

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

GA - 장사꾼여행문제(TSP) [4] - 돌연변이

8. 돌연변이

교차와 마찬가지로 돌연변이 역시 유전자 최소단위(비트-bit)를 임의로 바꾸는 일반적인 돌연변이를 사용할 수 없습니다. 모든 도시를 한번만 방문할 수 있다는 제한 때문이죠.
여기서 사용한 돌연변이는 두가지입니다.
만약 유전자가 7385920416이라면

㉠ 임의의 경로 뒤집기
임의의 도시와 돌연변이시킬 길이를 임의로 정합니다. 2번도시와 길이 4가 정해졌다면
먼저 2번도시를 첫머리로 옮깁니다.

2041673859

그 후에는 앞에서 4개 길이를 뒤집습니다. 즉 2->0->4->1을 1->4->0->2로 바꿉니다.

1402673859

㉡ 임의의 경로 바꾸기
임의의 도시와 돌연변이시킬 범위의 앞뒤를 임의로 정합니다. 8번도시와 3~7이 정해졌다면, 먼저 8번도시를 첫머리로 재배열합니다.

8592041673

다음에는 0~2와 3~7까지의 경로를 뒤바꿉니다.

2041859673

㉢ 돌연변이 확률
꼬마자동차의 경우처럼 일반적인 돌연변이는 비트 하나하나에 대해 돌연변이 확률을 계산합니다. 그러므로 비트 하나하나에 대한 돌연변이 확률이 작더라도 개체 하나에 대한 돌연변이는 생각보다 크게 나오는 경우가 많습니다.
이 문제의 경우에는 비트 하나하나에 대한 돌연변이가 아니라 개체 전체에 대한 돌연변이를 채택했기에 돌연변이 확률은 좀 높이는 것이 좋습니다.

procedure Mutantation(Salesman s)
.. if Random(0, 10) == 0 then // 10% 확률로 돌연변이
..... if Random(0, 2) == 0 then // 경로 뒤집기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := 0
........ endpnt := Random(1, 150 / 2 + 1)
........ while endpnt > startpnt do
........... // startpnt도시와 endpnt도시를 바꿈
........... tmp := s.gene[startpnt]
........... s.gene[startpnt] := s.gene[endpnt]
........... s.gene[endpnt] := tmp
........... startpnt := startpnt + 1
........... endpnt := endpnt - 1
........ end
..... else // 경로 바꾸기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := Random(1, 150 / 2 + 1)
........ endpnt := Random(startpnt + 1, startpnt + 150 / 3 + 1)
........ Salesman tmp
........ tmp := s // 복사본을 만들어 놓음
........ sub := 0
........ for k := startpnt, endpnt do // startpnt~endpnt까지 앞에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
........ for k := 0, startpnt do // 0~startpnt까지 그 뒤에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
..... end
.. end
end

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점짜리(모든 장애물을 완전하게 피한) 꼬마자동차가 나타났군요. 하지만 만점 꼬마자동차가 계속 유지되지 않습니다. 만점 꼬마자동차가 도태되었다가 다시 만들어지는 현상의 반복이군요.
다음번엔 이것을 한번 고쳐봅시다.