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]이기에 가능한 해법입니다.