B급 개발

밥을 잘 먹는 유전자를 가진 박테리아를 육성하는 시뮬레이터를 만들 것이다.

이 시뮬레이터는 유전 알고리즘을 기반으로 만들어진다.

실제로 박테리아는 유성생식을 하진 않지만, 유전물질을 교환하여 접합, 교차, 변이를 수행하기도 한다.

< 실제 생명공학의 유전 방법과는 다르다. 해당 알고리즘은 실제 현상을 모방하여 만들어졌을 뿐이다. >

요약

시각적으로나 알고리즘 적으로나 많이 개선해보려고 시도한 내용이다.

개선

개발 편에서 이미 유의미한 결과를 얻었기에 변형 편은 약간 번외 느낌으로 가려고 한다.

이것저것 변형시키고 개선시키는 과정을 거칠 것이다.

개선 TODO

• 시뮬레이팅 모드 개선
• 시뮬레이팅 시각화 개선
• 로그 변경
• 히스토리 추가

우선 시뮬레이터의 시각화 측면에서의 몇 가지 부분을 개선했다.

• 시뮬레이팅 모드
  • 재생모드 : 모든 시뮬레이팅 과정을 정해놓은 프레임으로 감상할 수 있다. (30 프레임 정도가 적당한 것 같다.)
  • 디버깅 모드 : 세대별로 약간씩 대기시간을 주고 마지막 화면만 업데이트한다. (위의 GIF가 디버깅 모드이다.)
  • 연산 모드 : 시뮬레이터상에 업데이트하지 않고 연산과정만 수행한다. (조금 랙이 걸릴 수 있다)

빠른 연산이 필요할 때와, 느리게 지켜보는 게 필요할 때가 있다.

적절히 이용할 수 있도록 모드를 나누었다.

• 시뮬레이팅 시각화
  
  • 시뮬레이팅 상황을 모니터링할 수 있는 차트
  • 여러 라벨 데이터를 쉽게 추가할 수 있는 유틸

Chart.js를 이용했다. 모델 변경에 유연하게 작용하는 유틸을 추가했다.

처음에 d3.js로 개발했으나 코드가 너무 난잡해지는 느낌이 있어서 바꾸었다.

• 로그 변경
  
  • document에 프린트되도록 했다.

기존에 사용하던 개발자 도구의 console.log()는 연산이 많은 작업에는 적합하지 않은 것 같다. 랙이 많이 걸려 불편하다.

당연한 말이지만 사실 웹에서 돌아가는 코드에 과한 연산을 부여하는 건 좋지 않다.

• 히스토리 추가
  • 해당 시뮬레이팅 장면을 재현할 수 있는 히스토리 기능을 추가했다.
  • 모델 변형과 검증 단계에서 더 수준 높은 유추를 할 수 있게 되었다.

강화 학습 모델을 만들 때도 히스토리 기능을 많이 사용하곤 한다. 우리의 적합 방식이랑 비슷한 부분이 많으니 분명 도움이 될 것이다.

히스토리 추가에 사용되는 메모리가 너무 높다 작게나마 레코딩 파일을 두어서 읽어올 수 있게 만드는 게 좋은 구조인 것 같다.

• 타입스크립트 구조적인 정비
  • 자바스크립트로 만들다가 타입스크립트로 갈아탔다. 여러 가지 환경 조작에 유연하게 하기 위해서 타입에 혼동이 있으면 불편하기 때문이다.
  • 타입스크립트 내부에서도 디자인 패턴을 고려하여 만들었다.

변형

문제점 분석

설계할 때의 목표는 화면 밖으로 안 나가는 박테리아 만들기였다.

로직상으로 그냥 못 나가게 막아버릴 수는 있지만,

환경과 보상을 잘 조작해주면 굳이 먹이가 없는 밖으로 나가지 않을 것이라고 생각했다.

하지만 가설일 뿐이고, 만들면서 생각이 든 문제점에 대하여 간단하게 분석해보려고 한다.

1. 어떤 위치에서 시작하느냐가 박테리아의 적합도 검증에 큰 영향을 미친다.

개발 편에서 언급했다시피 가장 유리한 방향으로 진동하며 이동하는 방향으로 진화했었다.

• 왼쪽에서 오른쪽으로 움직이도록 진화했다. 하지만 오른쪽에 스폰된다면?

2. 이동에 어떠한 외부 요인도 고려하지 않는다.

방향도 없다. 먹이 탐지도 없다.

적어도 박테리아가 높은 농도를 찾아가게 만들긴 해야 할 것 같다. - 이 부분은 다른 시뮬레이터를 만들 때 다른 기획으로 구현해볼 것이다.

3. 동족과 경쟁해야 한다.

동족이 먹이를 다 먹어버려도 문제다.

동족을 감지하는 로직은 넣지 않았다. - 이 부분은 다른 시뮬레이터를 만들 때 다른 기획으로 구현해볼 것이다.

유전자 수 증가, 매번 랜덤 유닛 5개 추가

20개의 유전자로는 표현될 수 있는 움직임이 너무 적다고 생각되었다. 

20개면 최대로 많은 액션을 한다고 쳐도 (20-3)//2 = 8개다.

150개로 유전자 수를 크게 늘려보았다.

또한 매 세대에 랜덤 초기화 박테리아를 5개씩 추가했다.

작게나마 원형으로 회전하는 녀석이 생겼다. 생각보다 허무하게 목표가 이루어져서 다른 변형 로직도 넣어보려고 한다.

모든 박테리아 가운데서 스폰

가장 성능이 좋았던 유전자에서 계속 뿌리가 뻗어 나가기에

결국 모든 박테리아의 움직임은 하나의 패턴으로 수렴할 수밖에 없다.

빠르게 치고 나가 먹이를 최대한 많이 먹는 전략으로 수렴할 것이라고 생각했으나,

격하게 진동하여 다른 박테리아의 먹이를 뺏어 최고의 유전자가 되는 전략으로 움직였다.

경쟁 과정을 보길 기대하긴 힘들 것이라고 생각했는데 생각보다 쉽게 볼 수 있었다.

예상하지 못한 결과는 좋든 나쁘든 가슴 두근거리게 만든다.

탈출하면 감점! <번외>

맵 밖으로 탈출하지 않는 유전자를 만들기 위해 맵 밖으로 step마다 맵 밖에서 발견되면 evaluation을 감점 처리해봤다.

그 결과로 움직이지 않는 박테리아가 발견되었다. 미세조정이 필요해 보인다.

과식하면 사망 <번외>

과식하면 사망하게 만들면 적당히 먹을까?

얼추 평균적으로 5~9개로 많이 먹는 듯하다. 10개 이상 먹으면 과식으로 사망하게 해 보자.

적당히 먹으려고 최선을 다하는 박테리아의 모습을 볼 수 있다.

밥을 잘 먹는 유전자를 가진 박테리아를 육성하는 시뮬레이터를 만들 것이다.

이 시뮬레이터는 유전 알고리즘을 기반으로 만들어진다.

실제로 박테리아는 유성생식을 하진 않지만, 유전물질을 교환하여 접합, 교차, 변이를 수행하기도 한다.

< 실제 생명공학의 유전 방법과는 다르다. 해당 알고리즘은 실제 현상을 모방하여 만들어졌을 뿐이다. >

개발 스펙

• HTML5, CSS3, Javascript
• Webpack, Typescript

요약

설계한 구조에 대한 간단한 요약이다.

시뮬레이터 로직은 아래와 같이 구성된다.

유전 알고리즘은 선택, 교차, 돌연변이 3개의 알고리즘을 사용했다.

세대 적합도 평가에서 목표 적합도 이상이 나올 시 루프를 중지하고 테스트를 하며 상태를 확인해 보려고 한다.

개발

시뮬레이터 로직에 대한 간단한 설명과 개발물을 정리한다.

환경 생성

시뮬레이터는 HTML5 Canvas 기능을 이용하여 만든다.

하나의 세대에서 환경은 다음과 같다.

• 배양판
  • size: 800*600
  • step: 1000 
• 배지 (영양분)
  
  • num: 300
  • size: 5*5
• 박테리아
  • num: 20
  • size: 15*15
  • gene size: 20
  • mutation rate: 15%
• 보상
  • 영양분을 섭취했을 때 +1

시뮬레이션

설계 편에서 설명했던 유전자 프로그래밍으로 각각의 박테리아가 움직일 수 있도록 하고.

박테리아에게 닿은 먹이는 해당 박테리아가 먹고 몇 개의 먹이를 먹었는지 저장하게 만들었다. 

세대가 처음 시작되면 설계 편에서 언급한 박테리아의 움직임을 프로그래밍하는 "AGC"염기가 존재하지 않아서 움직이지 못하는,

즉 장애를 가진 박테리아들이 존재한다.

세대 초반에는 "AGC"염기를 가진, 움직일 수 있는 박테리아가 높은 적합도를 얻었다. (보상 = 적합도)

하지만 세대 초반만 넘어가면 유전 로직에 따라 거의 모든 박테리아가 "AGC"염기를 가지게 된다.

모든 박테리아가 "AGC"염기를 가지게 된다면 더 활발한 움직임을 코딩하는 염기를 가지도록 진화할 것으로 예상한다.

세대 적합도 평가

세대에 대하여 적합도를 평가하고, 세대의 모든 박테리아에 대한 적합도를 평가한다.

적합도는 박테리아가 먹은 먹이의 개수로 정했다.

300개의 먹이 중에  150개인 절반을 먹는 세대를 만들어 내는 것을 목표로 해보자.

* score: 150 일 때 loop 멈춤.

유전자 선택

다음 세대의 부모가 되어줄 유전자를 선택한다.

유전자 선택 알고리즘은 룰렛 휠 알고리즘을 사용했다.

모든 유전자를 룰렛 위에 적합도의 비율로 공간을 분배하여 그리고 룰렛을 던져 맞춘 유전자를 뽑는 느낌으로 지어진 이름 같다.

각 필자의 코드에서 선택되는 박테리아는 모두 (박테리아(i)의 적합도 / 모든 박테리아의 적합도 합)의 확률로 선택되게 했다.

적합도가 높은 유전자를 높은 확률로 선택하는 알고리즘으로, 적합도가 낮은 유전자가 뽑힐 확률도 남겨 두는 느낌이다.

박테리아의 관점으로 보면 먹이를 많이 먹은 유전자가 자손을 만드는.. 느낌.

유전자 교차

부모로 선택된 박테리아는 자손을 만든다.

선택 연산을 2번 하여 부모 A와 부모 B를 선출한 뒤, 교차 포인트는 랜덤으로 하나 지정하고, 포인트를 기준으로 교차하게 만든다.

직관적으로 이해할 수 있도록 그려봤다.

위에선 1개의 교차 포인트를 두었지만 2개 이상 사용하는 방법도 있다고 한다.

유전자 돌연변이

교차로 나온 자손을 다음 세대에 투입하기 전 낮은 확률로 돌연변이가 일어날 수 있게 한다.

15% 확률로 유전자 돌연변이가 일어나도록 했다.

돌연변이는 보통 반전(reverse) 연산이나 교환(exchange) 연산을 하는 경우가 많은데

위 시뮬레이터에서는 교환 연산만 이용했다.

자손 B가 15% 확률로 돌연변이가 생긴다면, 랜덤 한 두 염기의 위치가 바뀌게 되는 것이다.

새로운 세대 생성

위와 같은 연산으로 세대를 생성하여 다음 세대의 시뮬레이션에 투입시킬 준비를 한다.

다시 환경 생성과 시뮬레이션

다시 먹이를 랜덤으로 깔고

새로운 세대를 랜덤 한 위치에 배치하고 

위의 과정을 반복한다.

결과

세대가 갈수록 항상 더 높은 적합도를 갖는 박테리아가 나타나지는 않지만, 대체적으로 점점 적합도가 높아지는 경향을 보였다.

그리고 목표한 총적합도 150을 넘는 세대도 만들 수 있었다. 161세대에 172점으로 성공했다.

이동패턴을 프로그래밍하는 "AGC"염기도 가장 앞으로 나온 모습을 볼 수 있다.

분석

성공한 세포의 움직임이다. 얼추 예상했던 패턴과 예상 못했던 패턴이 있었다.

위 세포를 분석해보자면 아래와 같다.

• 진동하며 이동한다. 
  • 비교적 크기가 작은 먹이를 스쳐서 지나치지 않기 위해 최대한 진동하며 이동하여 더 많은 먹이를 먹을 수 있게 진화한 것이라고 분석했다.
• 옆쪽 방향으로 이동한다. 
  • 이동은 유전자의 조합을 통해 모든 방향으로 움직일 수 있지만 보통 옆으로 움직이도록 진화했다.
  • 세포는 매 세대마다 랜덤 한 위치에 스폰됨으로 대각선으로 이동해버리면 먹이를 거의 먹지 못하고 배양판을 탈출해 버리는 문제가 발생하고, 위로 이동한다면 가로보다 세로 길이가 짧기 때문에 더 적은 먹이를 먹게 될 확률이 크기 때문이라고 분석했다.
  • 디테일하게 짚자면 옆쪽 방향으로 각도가 많이 기울어진 대각선이 가장 좋은 듯하다. (이동 가능 거리 + 진동 여부 고려)
• 이동패턴을 프로그래밍하는 "AGC"염기가 앞으로 이동했다.
  • 활발하게 움직이는 진화 전략이 선택된 만큼 이동패턴이 복잡할수록 먹이를 잘 먹을 수 있기 때문인 것이라고 분석했다.

다음 모델에서는 어떤 점을 개선해야 할까?

• 처음 기획할 때 예측하길 배양판 밖에는 먹이가 없음으로 진화를 거듭한다면 원을 그리며 움직여 배양판을 쉽게 나가지 않고 최대한 많이 휘젓고 다니게 진화하지 않을까 생각했지만 그러진 않았다.
• 배양판을 나가지 않고 최대한 많이 움직여야 높은 점수를 얻을 수 있을 거라고 생각했다.
  • 배양판을 나가서 오래 있을수록 적합도 점수를 깎아볼까?
  • 돌연변이 확률을 올리거나, 세대에 완전 랜덤 한 박테리아를 섞어서 넣어볼까?

우선 이 정도 생각해 볼 수 있을 것 같다.

분석편에서 이부분을 더 자세하게 짚어보겠다.

밥을 잘 먹는 유전자를 가진 박테리아를 육성하는 시뮬레이터를 만들 것이다.

이 시뮬레이터는 유전 알고리즘을 기반으로 만들어진다.

실제로 박테리아는 유성생식을 하진 않지만, 유전물질을 교환하여 접합, 교차, 변이를 수행하기도 한다.

< 실제 생명공학의 유전 방법과는 다르다. 해당 알고리즘은 실제 현상을 모방하여 만들어졌을 뿐이다. >

간단 이론

유전

유전에 대하여 알아보자. 아니 사실 알필요도 없다.

유전학 하나로 책이 수천 권이 나올 정도로 내용이 많음으로 필요한 개념만 정리한다.

유전자는 A, G, C, T의 염기의 배열로 이루어져 있다.

이러한 유전물질은 박테리아가 복제할 때 같이 복제되어 나누어지는데,

이때 많은 오류들이 발생하고 중합요소에 의하여 수리되지 못한 염기서열로 인하여 돌연변이가 발생하기도 한다.

(이외에도 돌연변이가 발생하는 원인은 많다)

이렇게 만들어진 유전자는 박테리아의 구성과 박테리아의 행동지침을 프로그래밍한다.

여기서 우리는 정말 간단한 유전 알고리즘을 만들 것임으로 이 정도만 알고 가도록 하자. (더 알면 만들기도 골치 아프다)

유전 알고리즘

유전 알고리즘은 우리가 통상적으로 배운 유전과는 조금 다르다.

시뮬레이션에서 각각의 유전자를 가진 개체들이 유전자에 대응되는 행동을 수행하게 하며,

시뮬레이션이 끝나면 이를 한 세대 (generation)이라고 한다.

이후 시뮬레이션 환경을 초기화하고 다시 개체들을 투입시켜 다음 세대를 시작하고 이를 높은 성능을 내는 개체가 나올 때까지 반복한다.

이때 다음 세대에 투입되는 개체의 유전자를 결정하는 것이 유전 알고리즘의 핵심이다.

여기에 사용되는 여러 가지 연산 방법 중 선택, 교차, 변이를 알아보자.

- 선택

현재 세대에서 우수했던 개체를 골라 다음 세대의 부모로 선정하는 방법입니다.

우수했던 개체를 고르는 방법도 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등 여러 가지 방법이 있다.

- 교차

현재 세대 내에서 교배를 통해 만들어진 자손을 다음 세대에 투입시키는 방법입니다.

여러 가지 방법이 있지만 하나만 예를 들자면, 유전자배열의 랜덤한 부위를 잘라 교차로 붙여 자손을 만드는 방법이 있다.

- 변이

교배를 통해 만들어진 자손의 유전자 배열을 교체하거나 순서를 바꾼 돌연변이를 다음 세대에 투입시키는 방법이다.

이것도 여러가지 방법이 있다

설계

환경 설계

• 800 X 600 사이즈의 맵에 무작위 위치에 여러 개의 먹이가 배치된다.
• 박테리아 또한 세대 초기화 때마다 무작위 위치에 배치된다.
• 박테리아와 닿는 먹이는 해당 박테리아가 먹이를 먹는 것으로 판정한다.
• 적합도 계산은 먹은 먹이의 개수로 판단한다.
• 유전자 요소는 실제로 유전자를 구성하는 A, G, C, T 염기를 이용하기로 했다.

유전자 번역 시스템

유전자에서 첫 AGC 염기가 발견된 시점부터 끝까지의 내용이 이동 시스템으로 프로그래밍된다.

* 방향
A = 0도
G = 90도
C = 180도
T = 270도

* 속도
A = 최대 속력
G = 최대 속력 * 0.9
C = 최대 속력 * 0.8
T = 최대 속력 * 0.7

AGCAA <end>
는 표적 각도로 최대 속력을 1 step으로 하여 반복이다.

AGCAAAGGG <end>
일 경우 2개씩 끊어서 AA AG GG 3 step을 반복한다.

AGCAAA <end>
다음과 같이 짝이 안 맞는 경우엔 맨 뒤의 A가 잘린다.

* 최종

<start> CTAGCAAGGA <end>

시작 염기인 AGC 앞에 있는 CT는 번역하지 않는다.

시작 염기인 AGC 뒤에 있는 AAGGA를 번역한다.

AA GG로 쌍을 이루었으므로 짝이 없는 A를 버린다.

위의 유전자를 가진 개체는

• 0도 방향으로 최대속력으로 이동하기
• 90도 방향으로 최대속력 * 0.9로 이동하기

위 2개의 행동을 반복하게 된다.

유전 시스템

유전 시스템은 위에서 설명한 3가지 선택, 교차, 변이를 모두 이용할 것이다.

유전 알고리즘에서는 이 부분이 가장 중요하니 개발 편을 작성하면서 마저 설명하도록 한다.

위 포스트는 개발 편에서 이어집니다.