진화하는 셀룰러 오토마타

Source: Dev.to

소개

안녕하세요, 호기심 많은 여러분! 셀룰러 오토마타와 유전 알고리즘의 흥미로운 교차점을 탐구하여 나타나는 패턴과 행동을 발견해 봅시다.

이 글은 2019년에 러시아어로 Habr에 발표한 글을 번역·각색한 것입니다. 여기서는 셀룰러 오토마타의 메커니즘을 살펴보고, 유전 알고리즘을 사용해 이를 진화시키며, 몇 가지 흥미로운 결과를 보여드립니다.

Repository

셀룰러 오토마타 규칙

셀룰러 오토마타의 가장 단순한 형태는 1차원 변형입니다. 1차원 셀룰러 오토마타에서는 초기 상태를 나타내는 단일 배열을 시작점으로 삼으며, 각 셀은 0 또는 1의 이진 값을 가집니다. 각 셀의 다음 상태는 현재 상태와 바로 인접한 두 이웃의 상태에 의해, 미리 정의된 규칙에 따라 결정됩니다.

셀 셀과 두 이웃, 총 3개의 셀로 구성된 경우 가능한 구성은 (2^3 = 8)가지가 있습니다:

각 구성마다 셀의 다음 상태(0 또는 1)를 정의하여 8비트 규칙, 즉 Wolfram 코드라 부르는 것을 만들게 됩니다. 이렇게 하면 가능한 1차원 셀룰러 오토마타는 (2^8 = 256)가지가 됩니다.

256개의 규칙을 모두 수작업으로 살펴보는 것은 가능하지만, 이제는 2차원 셀룰러 오토마타로 확장해 보겠습니다. 여기서는 복잡도가 기하급수적으로 증가합니다.

2차원 오토마타에서는 배열 대신 격자(행렬)를 사용합니다. 각 셀은 Moore 이웃(수평, 수직, 대각선) 안에 8개의 이웃을 가집니다. 일관성을 위해 이웃은 다음과 같이 순서를 정합니다:

셀 하나와 그 8개의 이웃을 합하면 가능한 구성은 (2^9 = 512)가지이며, 규칙은 512비트 문자열로 인코딩됩니다. 따라서 가능한 2차원 오토마타는 (2^{512} \approx 1.34 \times 10^{154})가지가 되는데, 이는 관측 가능한 우주의 원자 수 (10^{80})을 훨씬 초과하는 수치입니다.

이 모든 규칙을 수작업으로 탐색하는 것은 불가능합니다. 빅뱅 이후 매초 하나씩 규칙을 확인한다 해도 약 (4.35 \times 10^{17})개의 규칙만 살펴볼 수 있을 뿐입니다. 여기서 유전 알고리즘이 등장합니다. 유전 알고리즘을 사용하면 특정 기준을 만족하는 오토마타를 효율적으로 탐색할 수 있습니다.

2차원 셀룰러 오토마타

무작위 규칙 생성

// 512‑bit rule
const rulesize = 512;
const rule = new Array(rulesize).fill(0).map(() => Math.round(Math.random()));

그리드 초기화

// 89×89 grid (odd dimensions help keep dynamics interesting)
const sizex = 89;
const sizey = 89;
const size = 2;          // pixel size for drawing
let a = [];

for (let x = 0; x < sizex; x++) {
    a[x] = [];
    for (let y = 0; y < sizey; y++) {
        a[x][y] = Math.round(Math.random());
        if (a[x][y]) context.fillRect(x * size, y * size, size, size);
    }
}

다음 상태 계산 (주기적 경계 조건)

function step() {
    const temp = new Array(sizex);
    for (let x = 0; x < sizex; x++) {
        temp[x] = new Array(sizey);
        const xm = (x - 1 + sizex) % sizex; // left neighbor (wrap)
        const xp = (x + 1) % sizex;          // right neighbor (wrap)

        for (let y = 0; y < sizey; y++) {
            const ym = (y - 1 + sizey) % sizey; // top neighbor (wrap)
            const yp = (y + 1) % sizey;          // bottom neighbor (wrap)

            // Build 9‑bit mask from the Moore neighborhood
            const q = (
                (a[xm][ym] << 8) |
                (a[x][ym]  << 7) |
                (a[xp][ym] << 6) |
                (a[xm][y]  << 5) |
                (a[x][y]   << 4) |
                (a[xp][y]  << 3) |
                (a[xm][yp] << 2) |
                (a[x][yp]  << 1) |
                a[xp][yp]
            );

            temp[x][y] = rule[q];
            if (temp[x][y]) context.fillRect(x * size, y * size, size, size);
        }
    }
    a = temp;
}

무작위 규칙으로 이 오토마타를 실행하면 종종 혼돈스럽고 백색 잡음과 같은 행동을 보이며, 마치 튜닝되지 않은 TV에서 나오는 잡음과 같습니다:

유전 알고리즘

유전 알고리즘을 TV를 조정해 깨끗한 신호를 찾는 과정에 비유할 수 있습니다. 손으로 직접 노브를 돌리는 대신 원하는 특성을 정의하고, 알고리즘이 그 특성을 만족하는 규칙을 찾아 탐색합니다. (구현 세부 사항은 원본 소스에서 계속됩니다.)