진화론 이야기 - 팔에서 날개로

지구상에 존재하는 조류(Avian)는 흔히 공룡들의 후손이라고 합니다. 조류가 포유류(Mammal)보다 더 많은 종이 존재한다는 것을 본다면 지구는 아직까지 공룡의 수중에서 완전히 벗어나지 못했다고 볼 수도 있습니다.
토마스 헉슬리(Thomas Henry Huxley)는 공룡 중에서도 특히 소형 육식공룡과 조류와의 유사성을 지적했으며 또한 랩터류 공룡들에게서 깃털의 흔적이 발견됨에 따라 공룡과 조류간의 진화경로는 더욱 확실해졌습니다.
그렇다면 공룡의 발톱달린 앞발이 어떻게 발가락조차 없는 날개로 진화할 수 있었을까요?
여기에는 몇가지 가설이 있습니다.

1. 지상설(地上說)
육식공룡들은 대부분 뒷발로 걷습니다. 그러므로 앞발은 비교적 자유롭게 사용할 수 있습니다. 즉 방향을 바꿀 때 중심을 잡기 위해 사용할 수도 있습니다.그런데 앞다리에 긴 깃털이 무성할수록 중심을 잡기가 수월합니다(우리나라에서 줄타기하는 사람들이 부채를 휘두르는 것을 생각해 보세요). 게다가 긴 깃털이 난 팔을 휘두른다면 뒷쪽으로 기류가 발생해서 달리는 속도에 도움이 될 수 있습니다.
점점 달리는 속도가 빨라지다 보니 저 깃털이 난 팔로 짧은 거리의 활공이 가능해지고 활공거리가 점차 길어지다가 날 수 있게 되었다는 것이 지상설입니다.
지상설은 아래 그림(출처)과 같은 시조새를 분석하면서 만들어진 가설입니다. 현재의 새와는 달리 긴 꼬리와 강한 다리 등 난다기보다는 달리기에 좀더 적당한 신체조건을 가지고 있습니다.

2. 수상설(樹上說)
그런데 2005년 중국에서 날개가 4개 달린 공룡이 발견됩니다. 미크로랍토르(Microraptor)라 이름붙여진 이 공룡은 아래 그림(출처)처럼 앞다리뿐 아니라 뒷다리에도 깃털이 나 있는 것으로 보아 그리 빠르게 달릴 수는 없었을 것으로 생각됩니다. 대신 참새나 딱다구리같이 길고 굽은 발톱을 가지고 나무 위에서 많은 시간을 보냈으리라 추정되는 공룡입니다.즉 이들은 나무 사이를 뛰어다닐때 팔과 다리에 난 깃털을 이용하다가 점차 먼 거리를 뛸 수 있게 되고 결국 날 수 있게 되었다는 가설입니다.

그렇다면 과연 수상설과 지상설 중 어느 쪽이 더 타당할까요?

3. 비탈등반설(ontogenetic-transitional wing hypothesis)
2003년 미국의 케네스 다이얼(Kenneth Dial) 박사는 알에서 갓 깬 바위자고새에 주목하였습니다. 바위자고새의 새끼는 알에서 깨자마자 걸어다닐 수 있습니다. 아직 날 수는 없지만 날개를 보조동력원으로 사용하여 비탈을 오를 수 있습니다. 날개의 힘이 점점 강해짐에 따라 점점 가파른 비탈을 오를 뿐 아니라 결국에는 오버행(경사가 90도가 넘는 비탈)까지 넘을 수 있습니다. 그러다가 결국에는 날아오를 수 있게 됩니다.
다이얼박사는 날개의 진화가 이 바위자고새 날개의 발생과 유사하지 않을까 하는 가설을 내었습니다.

왼쪽 그림은 카우딥테릭스(Caudipterix)라고 하는 공룡입니다. 그림에서 볼 수 있는 것처럼 날기에는 초라한 작은 날개를 가지고 있죠.
이 날개로 지상설에서처럼 달릴 때의 보조동력(지상설) 뿐 아니라 바위자고새 새끼와 같이 사용해서 나무도 오를 수 있었으리라 생각됩니다(수상설). 즉 앞에서 나온 두가지 가설을 모두 아우르는 새로운 가설이 생긴 것이죠.

위에서 소개한 세가지는 아직까지는 '가설'상태를 면하지 못하고 있습니다. 더 증거가 쌓여야 셋 중에서 어느 것이 정설이 될지(아니면 제 4의 가설이 정설이 될지) 알 수 있을 것입니다.

출처 : 믿을 수 없는 생물진화론(기타무라 유이치北村雄一 저)

GA - LISP-link-Language And/OR

5. 유전자 초기화
일반적으로 트리구조는 재귀호출과 동적할당을 통해 구현합니다.
LlL에서는 다음과 같이 유전자 초기화를 합니다.

procedure GeneInit(LlLRoot root)
begin
.. root.Program := new LlLNode;
.. NodeInit(root.Program, 3); // 3은 하위노드를 만들 수 있는 확률
end

procedure NodeInit(LlLNode node, double rate)
begin
.. // node.Command 세팅
.. if Random(0, 1) >= 0.1 then
..... node.Command := RandomCommand; // 19개 명령어들 중 하나
.. eles
..... node.Command := Random(0, 1000); // 0~1000 사이의 상수
.. end

.. // 하위노드 만들기(맥스 3개)
.. node.BrenchNumber := 0;
.. for k := 0, 3 do
..... if rate > Random(0, 1) then
........ node.Brench[node.BrenchNumber] = new LlLNode;
........ NodeInit(node.Brench[node.BrenchNumber], rate / 2);
..... end
.. end
end

6. 변수리스트
명령어리스트에서 본 것과 마찬가지로, LlL에서는 변수를 사용합니다. 그러나 변수의 갯수가 무한이 될 수는 없습니다.
여기서는 32개의 변수를 사용합니다. 그러나 만약 (setv () ())나 (getv ()) 함수의 경우, 32 이상의 변수위치를 가리키게 된다면 32로 나눈 나머지로 위치를 결정합니다.
이를테면

(setv (364) (21))

이라면 364 % 32 == 12이므로 13번째 변수(0까지 포함하므로)에 21값을 넣습니다.

7. 실행
간단한 인터프리터를 만들어서 저 프로그램을 실행시킵니다. 먼저 32개 모든 변수를 0으로 초기화하고, 몇몇변수에 초기값을 넣어 트리모양으로 구성된 프로그램을 따라 실행시킵니다.
이때 프로그램에 따라 (특히 while문이 포함되어 있을 경우) 무한루프에 빠질 가능성이 있으므로 3000개의 명령어를 실행한 후에는 프로그램을 강제로 끝내도록 했습니다.
그리고 그 결과를 그 프로그램의 fitness로 저장한 후 유전자알고리즘으로 진화시켰습니다.

8. AND/OR 연산 결과
LlL을 이용하여 AND/OR연산을 할 수 있는지 확인해 봤습니다.
두개의 입력(0/1)을 각각 [0], [1]변수에 넣은 후 출력값을 살펴보았습니다. 다만 출력값이 1 이상이면 1로, 0 이하면 0으로 간주했습니다.
이때 Fitness를 계산하는데 트리의 크기를 고려해야 합니다.
1차원 또는 2차원 유전자의 경우 균일교차로서 교차가 어떻게 일어나더라도 유전자의 크기가 일정합니다. 그러나 나무형유전자의 교차는 불균일교차로서 트리 크기를 제어하지 않는다면 트리가 얼마나 커질지 알 수 없습니다.
그러므로 100번 연산을 해서 점수를 매긴 후, 트리 크기를 뺀 값을 Fitness로 정했습니다.
그 결과가 다음과 같은 프로그램들입니다.

OR
(getv
.. (getv
..... (>
........ (=
........ )
........ (!=
........ )
..... )
.. )
.. (/
.. )
.. (while
.. )
)

And
(getv
.. (getv
..... (＜
..... )
.. )
.. (if
..... (>=
..... )
.. )
.. (-
..... (＜=
..... )
.. )
)

필요없는 부분(나중에 돌연변이에 의해 잘려나갈 부분)을 정리하고 보기쉽게 정리하면 다음과 같은 프로그램이 남습니다.
OR
(getv
.. (getv
..... (1)
.. )
)

And
(getv
.. (getv
..... (0)
.. )
)

결국 OR는 var[var[1]], AND는 var[var[0]]과 동일합니다. 비록 일반적인 형태는 아니지만, AND/OR연산법을 찾은 것은 맞습니다. 물론 이것은 입력이 0/1 뿐이고 입력변수도 [0]과 [1]이기에 가능한 해법입니다.

GA - LISP-like-Language

1. LISP-like-Language(LlL)
실제로 리스프언어를 사용하여 진화알고리즘을 시험해 봤으면 좋겠습니다만... 약간의 문제가 있습니다.
진화알고리즘을 통해 만들어진 리스프 프로그램을 리스프 인터프리터와 연동시킬 수가 없다는 - 리스프 인터프리터까지 만들어야 한다는 - 문제죠(물론 그보다 더 큰 문제는 저 자신이 리스프언어를 잘 모른다는 점...).

그래서 여기서는 LlL이라는, 말 그대로 '리스프모양의 언어'를 만들어 사용하기로 했습니다.

2. LlL의 명령어
LlL에는 다음과 같은 19개의 명령어가 존재합니다.
2.1 (proc (ㄱ) (ㄴ) (ㄷ) ..... (ㅎ))
(ㄱ)부터 (ㅎ)까지 차례로 실행한 후 (ㅎ)의 리턴값을 리턴합니다. 만약 하위노드가 하나도 없다면 0을 리턴합니다.
2.2 (setv (ㄱ) (ㄴ) ....)
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ)번째 변수에 (ㄴ)의 리턴값을 넣습니다. 그리고 (ㄴ)의 리턴값을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.3 (getv (ㄱ) ... )
(ㄱ)를 실행한 후(만약 (ㄱ)가 없으면 0으로 간주) 해당되는 변수의 값을 리턴합니다. 두번째 이후의 식은 실행되지 않습니다.
2.4 (+ (ㄱ) (ㄴ) .... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) 두 값의 합을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.5 (- (ㄱ) (ㄴ) .... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) - (ㄴ)를 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.6 (* (ㄱ) (ㄴ) .... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) 두 값의 곱을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.7 (/ (ㄱ) (ㄴ) .... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) / (ㄴ)를 리턴합니다. 만약 (ㄴ)의 리턴값이 0이면 프로그램이 종료됩니다. 3번째 이후의 식은 실행되지 않습니다.
2.8 (if (ㄱ) (ㄴ) (ㄷ) ... )
(ㄱ)를 실행한 후 그 값이 0이 아니면 (ㄴ)를, 0이면 (ㄷ)를 실행후 그 값을 리턴시킵니다. (ㄴ)나 (ㄷ)가 없다면 0을 리턴시킵니다. 그 이외의 식은 실행되지 않습니다.
2.9 (while (ㄱ) (ㄴ) .... )
(ㄱ)를 검사하여 0이 아니면 (ㄴ)를 실행시킵니다. 이 과정을 (ㄱ)가 0이 될 때까지 반복합니다. (ㄱ)가 0이 되면 최후에 실행했을 때의 (ㄴ)값을 리턴합니다.
2.10 (> (ㄱ) (ㄴ) ... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) > (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.11 (>= (ㄱ) (ㄴ) ... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) >= (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.12 (== (ㄱ) (ㄴ) ... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) == (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.13 (!= (ㄱ) (ㄴ) ... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) != (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.14 (＜ (ㄱ) (ㄴ) ... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) ＜ (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.15 (＜= (ㄱ) (ㄴ) ... ) (ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) ＜= (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.16 (& (ㄱ) (ㄴ) ... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) & (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.17 (| (ㄱ) (ㄴ) ... )
(ㄱ)와 (ㄴ)를 차례로 실행한 후(만약 (ㄱ)나 (ㄴ)가 없다면 0으로 간주) (ㄱ) | (ㄴ)을 리턴합니다. 3번째 이후의 식은 실행되지 않습니다.
2.18 (exit (ㄱ) ... )
(ㄱ)식을 계산한 후 프로그램을 종료시키며 전체 값을 프로그램의 리턴값으로 합니다. 이후의 식은 실행되지 않습니다.
2.19 (숫자 (ㄱ) (ㄴ) .... )
하위 식들은 전혀 실행되지 않습니다. 그리고 숫자의 값이 리턴값이 됩니다. 숫자는 0 이상의 정수입니다.

3. 보기
이 LlL로 어떤 수 (0번째 변수에 입력된 수)가 소수인지 아닌지 확인하는 프로그램입니다.

(proc
.. (setv (1) (2)) // 1번변수(이후 [1]로 표시)에 2 입력
.................. // 이후 [1]을 계속 증가시켜가며 나누기할 예정
.. (while
..... (>
........ (* (getv (1)) // [1]의 제곱이 [0]보다 커지면 더이상 계산 불필요
........... (getv (1)) // while문 탈출
........ )
........ (getv (0))
..... )
..... (proc
........ (setv (2)
.............. (/ (getv (0)) // 다음 단락까지 [0] / [1] * [1]을 계산
................. (getv (1))
.............. )
........ )
........ (setv (3)
.............. (* (getv (2)) // 계산결과를 [3]에 저장
................. (getv (1))
.............. )
........ )
........ (if (== (getv (3)) // [3]과 [0]이 같다는 것은 나머지가 0이라는 것
................ (getv (0))
............ )
............ (exit 0) // 소수가 아니므로 0을 리턴하고 프로그램 종료
........ }
........ (setv (1)
.............. (+ (getv (1)) // [1]값을 1 증가
................. (1)
.............. )
........ )
..... )
.. )
.. (1) // while문을 통과했다면 전체 proc함수가 1을 리턴하도록
}

GA - 나무형유전자와 LISP

1. 개요
지금까지는 1차원(선형)유전자 또는 2차원(평면)유전자만을 다루어 왔습니다. 그리고 모두 데이터를 유전자화시켜 최적의 데이터조합을 찾기 위해 유전자알고리즘을 사용해 왔습니다.

그에 반해 이번에 소개할 '진화 알고리즘'은, 데이터가 아니라 프로그램 자체를 진화시키는 방식입니다. 방식은 똑같습니다. 임의로 만든 프로그램으로부터 시작해서 조금이라도 잘 돌아가는 프로그램들을 재생산하여 목적에 맞는 프로그램을 진화시키는 것입니다.
물론 모든 프로그램을 그렇게 진화시킬 수 있는 것은 아닙니다. 진화시키기에 가장 적당한 언어는 리스프(LISP)입니다. 왜냐하면 리스프 프로그램은 다음과 같이 트리구조로 바꾸기에 가장 적당한 언어이기 때문입니다.

(defun prime (x)
.. (do ((num 2 1))
...... ((> (* num num) x) 0)
...... (setq d (/ x num))
...... (setq t (* d num))
...... (if (= t x)
.......... (return nil)
...... )
.. )
)

2. 교차
이렇게 프로그램을 나무형으로 변환했지만 이 프로그램을 '진화'시키기 위해서는 진화연산 - 교차와 돌연변이가 필요합니다.
1차원이나 2차원유전자의 교차에서 유전자 일부를 교환했던 것처럼 나무형 유전자 역시 유전자 일부를 교환함으로써 교차를 할 수 있습니다. 즉 다음 그림과 같이 임의의 가지를 교환함으로써 교차를 실행할 수 있습니다.3. 돌연변이
나무형 유전자의 돌연변이에는 다음과 같은 여러가지가 있습니다.
3.1 가지추가
3.2 순서교환
3.3 가지삭제