[유전 알고리즘] 밥 잘먹는 박테리아 배양 시뮬레이터 설계편

진행중인 프로젝트입니다.

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

 

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

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

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

 

lunaB/Genetic-Algorithm-Simulation

---

간단 이론

유전

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

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

 

유전자는 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가지 선택, 교차, 변이를 모두 이용할 것이다.

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

---

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