[유전자 알고리즘을 사용한 인공생태계 구현]

- 우종하(deepseas(AT)sogang.ac.kr)

 


    - 마우스로 개체를 클릭하면 특성치 표시

    - 소스코드 [Down]

    - 자바 Runtime [Down] : 애플릿이 실행이 안될 경우 설치, 설치후 익스플로어 재실행

 

유전자 알고리즘(Genetic Algorithm)

유전자 알고리즘은 자연의 진화과정을 모델링하여 구현한 탐색 알고리즘이라 할 수 있다. 기본적인 개념은 주어진 문제에 대해 가능한 해들을 정해진 형태로 표현한 후 이들을 변화시키고, 그 결과들 중 적합도가 높은 것들을 선택하여 변화를 계속함으로써 보다 좋은 해에 도달한다는 것이다. 이는 마치 부모의 유전인자 중 우성의 형질을 지닌 개체가 번성해간다는 다윈의 진화론적 적자생존의 법칙과 유사하다.

주어진 문제에 가능한 해, 즉 각 개체들의 유전적 구조는 보통 고정된 길이의 이진값으로 표현되다. 이러한 유전자는 다음과 같이 두 가지 방법으로 부모개체로부터 새로운 개체로 생성된다. 첫째는 교차변이(crossover)라고 하는 것으로 부모 개체들의 특정 교차점에서 그 이후의 값들을 서로 교환하는 것이다. 둘째는 돌연변이(mutation)로 0을 1로, 혹은 1을 0으로 비트값을 반대값으로 변환하는 것이다.

이렇게 새로운 자식 개체들을 생성한 후에 적합도 함수(fitness function)을 통해서 주어진 문제에 적합한 개체들만을 골라 선택하고, 다시 선택된 개체들을 교차변이와 돌연변이를 통해 새로운 개체들을 생성함으로써 보다 좋은 해에 도달할 때까지 반복한다.

 

진화하는 간단한 인공생계태의 구현

위와 같은 유전자 알고리즘을 사용하여 인공적인 환경안에서 진화하는 가상생명체들을 구현하여 보았다. 인공환경안에는 저글링, 파이어뱃, 질럿이라는 세 종류의 종족이 존재하고 각 종족은 저다마 다른 육체적 특징을 갖고 있다. 그리고 이러한 특성은 유전자 코드에 저장되어 있고, 번식을 수행할 때 개체의 유전적 특성이 전달되어 부모개체의 특징들이 자식개체에게로 이어진다.

이때 특정한 확률로 임의의 유전코드가 돌연변이를 통해 변이를 함으로써 부모개체의 특성을 유지하지만 조금 변형된 특성을 물려받게 되고 만약 변형된 특성이 환경에서 살아남기에 더 적합하다면 그러한 특성이 개체들이 더욱 번성하게 될 것이다.

유전자 종류가 많지 않은 특성상 교차변이는 사용하지 않고 돌연변이 방법만 사용하였다. 그리고 특정한 적합도 함수는 존재하지 않고 환경안에서 보다 많은 먹이를 먹고 싸움에 이기는 개체들은 자식개체를 생성하고 그렇지 못한 개체들은 죽음으로써 자연스럽게 환경에 적합한 특성을 가진 개체들만이 살아남아 번성하게 될 것이다.

처음에는 랜덤하게 선택된 유전자 특성들로 시작하지만, 시간이 흐를수록 환경에 유리한 개체들만이 살아남아 번식을 하게 될 것이다. 이 프로그램의 목적은 서로 다른 육체적 특징을 갖고 있는 세 종족이 어떻게 환경에 적응을 하고 어떠한 방향으로 유전적 특징들이 발전하는지를 살펴보는데 있다.

 

개체의 유전자 종류

개체의 유전자 특성은 다음과 같이 4가지가 있다.

- 시야(Sight)
    : 개체가 바라볼 수 있는 거리. 시야가 넓을수록 먹이를 먼저 발견하여 먹이를 향해 다가간다.
    : 각 종족마다 가질 수 있는 시야의 범위는 저글링(5~10), 파이어뱃(3~7), 질럿(1~5)

- 힘(Strength)
    : 개체의 전투 능력. 힘이 높을수록 싸움에서 이길 확률이 높다.
    : 각 종족마다 가질 수 있는 힘의 범위는 저글링(1~5), 파이어뱃(3~7), 질럿(5~10)

- 이동성향(Move)
    : 높을수록 이동할 확률이 높고 낮을수록 움직이지 않을 확률이 높다.
    : 세 종족 모두 (1~10)

- 공격성향(Attack)
    : 높을수록 다른 종족과 전투할 확률이 높고 낮을수록 전투를 회피할 확률이 높다.
    : 세 종족 모두 (1~10)

 

기타 규칙들

- 각 종족의 기본체력은 저글링(50), 파이어뱃(70), 질럿(100)
- 미네랄을 먹으면 체력이 20 증가
- 미네랄은 턴마다 설정된 개수만큼 증가(0~5)
- 시야내에 미네랄이 있으면 그쪽으로 이동
- 한 칸 이동시 체력이 일정수치 감소. 저글링(-1), 파이어뱃(-2), 질럿(-5)
- 대기시에도 체력이 일정수치 감소. 저글링(-1), 파이어뱃(-1), 질럿(-1)
- 주위(한칸)에 다른 종족 발견시 공식에 의해 전투여부 결정 : 공격성향1+공격성향2+랜덤치 > 일정수치
- 전투발생시 공식에 의해 승패 결정 : 힘x(체력/10+랜덤치)
- 전투승리시 상대 만큼 체력 증가
- 기본체력의 2배가 되면 번식
- 번식시 특정한 확률로 각 특성값이 돌연변이됨
- 체력이 '0'이 되면 죽음
- 전투시 빨간색 테투리 표시
- 번식시 파란색 테투리 표시

 

결과 분석

예외가 있긴 하지만 보통 충분한 시간이 흐른뒤에 각 종족의 특성을 살펴보면 다음과 같다.

- 저글링
    : 시야와 힘이 높다
    : 이동성향이 높다
    : 공격성향이 낮다

- 파이어뱃
    : 시야와 힘이 높다
    : 이동성향이 높다
    : 공격성향이 높다

- 질럿
    : 시야와 힘이 높다
    : 이동성향이 낮다
    : 공격성향이 높다

세 종족 모두 공통적으로 시야와 힘이 높은 개체들이 번성하였다. 이는 먹이 발견과 싸움시 유리하게 작용하기 때문이다.저글링은 육체적 특성이 시야가 넓은 대신 힘이 약하기 때문에 빨리 이동하고 싸움을 피하는 특성을 보였다. 파이어뱃은 육체적 특성이 중간치이기 때문이라 그런지 이동성이 높아 먹이도 빨리먹고 공격성향도 높아 저글링에 경우 공격하는 것이 유리하게 작용한다. 질럿은 시야가 좁고 이동시 체력이 많이 드는 대신 힘이 좋기 때문에 이동은 적게 하고 주로 공격을 통해 체력을 높이는 방향으로 발전하였다.

 

[참고자료]

    - AI Game Programming Wisdom, Francois Laramee, p.841 ~ p.853
    - 인공생명, 스티븐 프레이타, p.201 ~ p.226

 

[1]