카오스 - 나비효과

흔히들 하는 말 중에 나비효과 Butterfly Effect 란 말이 있습니다. 조그맣게 시작된 일이 점점 커져 걷잡을 수 없는 상황이 되는 것을 일컫곤 하죠. 기상학자인 기상학자 에드워드 로렌츠 박사가 처음 발견한 것이죠. 하지만 진화론이 흔히 그렇듯 나비효과 역시 흔히들 잘못 이해하고 있는 개념이기도 합니다.

대부분 이 만화와 같이 '나비 날갯짓이 태풍만큼 커지는 것이 나비효과'라고 이해하는 경우가 많습니다.
만약 나비의 날갯짓이 태풍으로 발전한다면, 정작 태풍은 무엇으로 발전해야 할까요?

사실 나비효과는 '규모의 확대'가 아니라 '오차범위의 확대'입니다. 나비의 날갯짓 정도의 오차(±0.0001)가 점점 확대(±0.001 → ±0.01 → ± 0.1 → ±1 → ±10 → ±100)된다는 것입니다. 즉 나비의 날갯짓에 의해 '태풍이 분다'가 아니라 나비의 날갯짓만한 오차(±0.001)가 계속 커져서 태풍만큼의 오차(±10000)가 된다 - 태풍이 불지 안불지 알 수가 없게 된다라는 것이 바로 나비효과입니다.

에드워드 로렌츠 박사는 기상현상을 계산하는 방정식을 간략화시켜 다음과 같은 비선형방정식을 만들었습니다.

이 비선형방정식의 X좌표만 뽑아 다음과 같은 그래프를 그렸습니다. X의 초기값을 -1.18702803233463로 시작한 것이 푸른색, 소수점 6째자리에서 반올림한 -1.18703로 시작한 것이 붉은색 그래프입니다.

보시다시피 처음 두 그래프는 구분할 수 없을만큼 같은 모습을 하다가 점차 둘 사이에 차이가 보이기 시작하고 마침내 두 그래프는 전혀 다른 길을 가게 되죠.

바로 이런 이유로 장기적인 기상예보가 불가능한 것입니다. 0.000002 정도의 오차가 시간이 지날수록 점점 커지다가 결국에는 전혀 다른 기상이 나타나게 되니까 말입니다.

그렇다면 이런 카오스 이론은 예측이 불가능한 쓸모없는 것일까요?

카오스 이론이 다루고 있는 것은 특정한 사건이 아니라 '사건의 패턴'입니다. 이 그래프에서 보더라도 어느 순간의 X값이 얼마가 될지는 예측할 수 없습니다. 하지만 'X값은 -20에서 +20 사이에서 오르내린다'라든가, '+나 -영역에서 진폭이 점점 커지며 이 진폭이 커질수록 반대쪽 영역으로 이동할 가능성이 커진다' 등의 패턴을 찾는 것이 카오스이론입니다.

이와 같은 카오스 시스템의 다른 특징 중 하나가 '안정성'입니다. '나비의 날갯짓' 정도의 오차는 그렇다 치고, 만약 '칙쇼루브 소행성 정도의 오차'가 생겼다면 어떨까요?

실제로 위와 같은 방정식에서 '칙쇼루브 소행성 정도의 오차'를 가정해서 가끔 엉뚱한 값을 대입해본 결과입니다.

이 그래프와 같이 X에 어떤 값이 들어가도(어떤 재앙이 닥쳐도) 빠른 시간 안에 원래의 패턴 -  'X값은 -20에서 +20 사이에서 오르내린다', '+나 -영역에서 진폭이 점점 커지며 이 진폭이 커질수록 반대쪽 영역으로 이동할 가능성이 커진다' 같은 패턴을 되찾게 됩니다. 그때문에 칙쇼루브에 소행성이 떨어진 이후에도 다시 이전의 환경을 되찾게 된 것입니다.

이와 같이 카오스시스템이 되돌아가는 패턴을 끌개 - 어트랙터Attractor라고 합니다. 위와 같은 미분방정식 역시 어떤 상태에서도 위 그래프와 같은 패턴으로 돌아가므로 이것을 로렌츠 끌개(Lorenz Attractor)라고 합니다.

생물체나 생태계 역시 이런 카오스시스템이라고 할 수 있습니다.
창조론자들은 '이 동물이 어떤 식으로 진화할 것인지 예측해 봐라'라고 요구하지만, 이런 이유로 인해 그런 예측은 불가능합니다. 하지만 그것을 예측 못한다고 해도 아무 상관 없죠.
진화론에서 말하는 것은 '진화하는 패턴'이며 그 패턴은 이미 잘 밝혀져 있으니까 말입니다.

GA - Self Programming(삼목놀이) 2

이와 같은 언어를 가지고, 가장 간단한 삼목놀이(TicTacToe)를 하는 프로그램을 만들어 봤습니다.
삼목놀이용 인터프리터는 다음과 같이 구성되어 있습니다.

㉮ 메모리
36개의 bool변수 배열을 사용합니다. 이중 0~26부분은 현재 보드 상태를 입력하는데 사용합니다.
Set이나 Reset, If 등 메모리를 참조하는 연산은, [해당 명령의 arg % 36]의 메모리를 참조합니다.

㉯ 출력
출력은 9채널의 float배열을 사용합니다. 마찬가지로 [Stream 명령의 arg % 9]의 배열에 출력합니다.

0	1	2
3	4	5
6	7	8

만약 5번출력이 10, 7번출력이 30이라면 25% 확률로 5번칸에, 75%확률로 7번에 돌을 놓습니다. 물론 모든 출력이 0 이하라면 아무 곳에도 돌을 놓지 않습니다.

㉰ 프로그램
초기 프로그램의 길이는 1024개 길이로 랜덤의 Instructor와 Argument로 구성합니다.

이와 같은 Interpreter 4096개를 만든 후 그들 사이에 가상의 삼목게임을 반복합니다.

㉱ 적응도 계산
적응도 계산에는 승패보다 먼저 규칙습득을 우선했습니다. 돌을 어디에 놓을지 결정 못하거나(모든 Stream채널 0 이하) 이미 돌이 놓인 곳에 다시 돌을 놓는다면 1000점 감점(적당한 곳에 놓는다면 1000점 가산), 그리고 승패가 나면 100점 가산/감산을 하도록 했습니다.

㉲ 재생산
적응도에 따라 앞에서 설명한 교차와 돌연변이를 통해 새로운 세대를 만듦니다.

㉳ 결과
삼목놀이란 것이 원래 승패가 없는 게임입니다. 제대로 놓는다면 무승부가 나올 수밖에 없는 게임이죠.
이와 같은 식으로 약 400세대 진행시켜본 결과입니다(실은 실수로 컴퓨터를 끄는 바람에 중간에 멈췄어요...ㅜㅜ)

매 세대마다 편차가 심해, 알아보기 쉽도록 적당히 보정한 그래프입니다.
보시다시피 No Decide(어디에 둘지 결정 못함)는 전체적으로 거의 없습니다. 왜냐하면 Stream명령어를 다른 명령어보다 많이 넣었거든요.
하지만 DoubleStone(이미 돌이 있는 곳에 또 놓음)은 서서히 줄어듧니다. 마찬가지로 Win/Lose 역시 증가하다가 감소하죠.
결국 세대가 증가할수록 제대로된 AI가 만들어짐을 알 수 있습니다.

다만 삼목처럼 손으로 만들면 1,20분이면 될 AI도, 제대로 만들어지려면 며칠이 걸린다는 것이 함정...ㅡㅡ

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