GA - Self Programming(삼목놀이) 1

아시는 분도 계시겠지만, 전 프로그래머입니다. 맨날 코드짜고 디버깅하기 귀찮아서 스스로 코딩하는 프로그램을 만들어 봤습니다. 유전자 알고리즘을 이용해서 말이죠.

진화론 이야기 - DNA, 컴퓨터 프로그램, 띠에라에서도 썼지만,  복사시 오류를 만드는 복사루틴과 오류가 생겨도 문제없이 실행 가능한 프로그램언어를 설계해야 합니다.


㈎ 여기서 사용한 인터프리터(Interpreter)는 세 부분으로 이루어져 있습니다.

㉮ Memory
메모리는 일정한 크기의 Bool 변수의 배열입니다. 코드를 실행함에 따라 이 메모리에서 값을 읽어낼 수도 있고 이 메모리에 값을 쓸 수도 있습니다.
또한 이 메모리의 특정 영역에 값을 입력함으로써 감지기의 역할도 할 수 있습니다.

㉯ Stream
출력에 해당하는 부분입니다.

㉰ Program
실제 프로그램이자 유전자에 해당하는 부분입니다. 명령어는 다음과 같이 Instructor와 Argument로 구성됩니다.

NOP -615
Goto 1452
Label -1627
Goto -1734
Label 493
Return -821
Stream -478
NOP -114
IfNot 1028
Reset -757
NOP 1425
Label 2129
Stream 304
NOP 1450
IfNot 1020
NOP 1206
NOP -794
Label -726
Label -139
NOP -594
Label 729
NOP -442

각 Instructor는 다음과 같은 역할을 합니다.

NOP	아무 역할도 하지 않음
Set	arg에 해당하는 메모리를 true으로 만듦
Reset	arg에 해당하는 메모리를 false로 만듦
Label	아무 역할도 하지 않음
GoSub	현 위치 스택에 저장후 Goto와 동일
GoTo	arg가 +면 +방향, -면 -방향으로 Label 탐색, 　동일한 arg 찾아 실행위치 바꿈
If	arg에 해당하는 메모리가 true면 다음라인 실행, 　아니면 다음라인 무시(NOP는 무시)
IfNot	arg에 해당하는 메모리가 false면 다음라인 실행, 　아니면 다음라인 무시(NOP는 무시)
Stream	arg에 해당하는 채널의 Stream으로 출력
Return	스택 맨 위의 위치부터 실행 　스택이 비어있으면 프로그램 종료

㈏ 교차
Program 부분의 한 라인(Instructor + Argument) 단위로 두 프로그램을 교차시킵니다.

NOP -615
Goto 1452
Label -1627
Goto -1734
Label 493
Return -821
Stream -478
NOP -114
IfNot 1028
Reset -757
NOP 1425
Label 2129
Stream 304
NOP 1450
IfNot 1020
NOP 1206
NOP -794
Label -726
Label -139
NOP -594
Label 729
NOP -442




NOP -87
NOP -1711
Label 1988
Stream 1748
If -1383
If 1254
NOP 801
Set -219
Stream 1789
Reset 1706
NOP -1251
NOP 1203
Set -1665
NOP 1174
Stream 1587
NOP 2000
NOP -909
NOP -1949
If 765
Gosub 1936
Goto 290
NOP -106
IfNot 1117
NOP 825
NOP -792
Goto -1012




위와 같은 두 프로그램을 교차시킨다면

NOP -615
Goto 1452
Label -1627
Goto -1734
Label 493
Return -821
Set -1665
NOP 1174
Stream 1587
NOP 2000
NOP -909
NOP -1949
If 765
Gosub 1936
Goto 290
NOP -106
Label -139
NOP -594
Label 729
NOP -442

NOP -87
NOP -1711
Label 1988
Stream 1748
If -1383
If 1254
NOP 801
Set -219
Stream 1789
Reset 1706
NOP -1251
NOP 1203
Stream -478
NOP -114
IfNot 1028
Reset -757
NOP 1425
Label 2129
Stream 304
NOP 1450
IfNot 1020
NOP 1206
NOP -794
Label -726
IfNot 1117
NOP 825
NOP -792
Goto -1012

와 같은 새로운 프로그램이 만들어집니다.


㈐ 돌연변이
돌연변이에 있어서는 생물 염색체의 돌연변이를 참조해서 다음과 같이 실행합니다.

프로그램의 한 부분이 사라지는 결실, 한 부분이 두번 복사되는 중복, 한 부분의 코드들이 역순으로 배열되는 역위가 존재합니다.

원본

NOP -615
Goto 1452
Label -1627
Goto -1734
Label 493
Return -821
Stream -478
NOP -114
IfNot 1028
Reset -757
NOP 1425
Label 2129
Stream 304
NOP 1450
IfNot 1020
NOP 1206
NOP -794
Label -726
Label -139
NOP -594
Label 729
NOP -442




㉮ 결실

NOP -615
Goto 1452
Label -1627
Goto -1734
Label 493
Return -821
Stream -478
NOP -114
Label -726
Label -139
NOP -594
Label 729
NOP -442



㉯ 중복

NOP -615
Goto 1452
Label -1627
Goto -1734
Label 493
Return -821
Stream -478
NOP -114
IfNot 1028
Reset -757
NOP 1425
Label 2129
Stream 304
NOP 1450
IfNot 1020
NOP 1206
NOP -794
Label -726
Label -139
Return -821
Stream -478
NOP -114
IfNot 1028
Reset -757
NOP 1425
Label 2129
Stream 304
NOP 1450
NOP -594
Label 729
NOP -442



㉰ 역위

NOP -615
Goto 1452
Label -1627
Goto -1734
Label 493
Return -821
Stream -478
NOP -594
Label -139
Label -726
NOP -794
NOP 1206
IfNot 1020
NOP 1450
Stream 304
Label 2129
NOP 1425
Reset -757
IfNot 1028
NOP -114
Label 729
NOP -442



㉱ 점돌연변이
위의 큰 돌연변이들은 일정 확률로 일어나며, 그 외에는 각 Instructor, Argument마다 일정 확률로 바뀌는 점돌연변이가 일어납니다.

NOP -615
Goto 1452
Stream -1627
Goto -1734
Label 493
Return -821
Stream -478
NOP -114
IfNot 1028
Reset -757
Reset 1425
Label 2129
Stream 304
NOP 1450
IfNot 1020
NOP 1206
NOP -794
Label -737
Label -139
NOP -594
Label 729
NOP -442