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을 리턴하도록
}
실제로 리스프언어를 사용하여 진화알고리즘을 시험해 봤으면 좋겠습니다만... 약간의 문제가 있습니다.
진화알고리즘을 통해 만들어진 리스프 프로그램을 리스프 인터프리터와 연동시킬 수가 없다는 - 리스프 인터프리터까지 만들어야 한다는 - 문제죠(물론 그보다 더 큰 문제는 저 자신이 리스프언어를 잘 모른다는 점...).
그래서 여기서는 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 가지삭제
지금까지는 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 가지삭제
피드 구독하기:
글 (Atom)