Genetic Algorithm - AI Car Simulator

배경

• 2019년 처음 Unity와 C#을 공부하며 혼자 끄적였던 프로젝트이다.
• 우연히 유튜브로 유전 알고리즘으로 로봇이 그네 타는 방법을 학습시키는 영상을 보게 되었다.
• 재밌어보여서 유전 알고리즘을 공부하고, 직접 자율주행 시뮬레이터를 만들어보았다.

요약

1. 자동차 전면에 방향별 센서를 부착한다.
2. 장애물이 센서에 부딪히는 위치 상황별 회전값을 24bit 유전자로 인코딩하고, 20대의 자동차가 트랙을 주행한다.
3. 얼마나 멀리, 빠르게 완주했는지를 점수화한다.
4. 점수가 높은 자동차끼리 유전자를 교배하고, 일정 확률로 돌연변이를 만든다.
5. 세대를 반복하면 자동차들이 점점 더 빠르게 완주하도록 진화한다.

유전 알고리즘

개념

• 유전 알고리즘은 자연의 진화를 모방한 알고리즘이다.
• 더 나은 결과를 갖는 염색체끼리 유전 정보를 교차하며 세대를 거듭하면, 점점 더 나은 염색체를 얻을 수 있다는 아이디어에서 출발한다.
• 유전 알고리즘의 핵심 키워드는 다음과 같다.

Chromosome (염색체)

• 하나의 개체를 의미한다.
• 이 프로젝트에서는 자동차 한 대가 하나의 염색체로, 20대의 서로 다른 주행 방법을 갖고 있는 자동차가 경쟁하며 더 좋은 염색체를 비교해간다.

Gene (유전 정보)

• 염색체가 갖는 유전 정보이다.
• 이 프로젝트에서는 출발 위치, 센서별 회전값을 유전 정보로 하여, 어떤 위치에 있을 때 장애 감지별 회전 정도가 얼마인지를 24bit로 기억하여 주행한다.

Fitness (적합도)

• 생존 결과를 점수화하여 염색체의 우수함을 구분하는 척도이다.
• 이 프로젝트에서는 얼마나 멀리 주행했는지, 얼마나 빠르게 완주했는지로 각 자동차별 유전 정보를 점수화한다.

Selection (선택)

• 적합도를 기준으로 교배될 염색체를 선정하는 과정이다.
• 이 프로젝트에서는 룰렛 휠 방식으로 적합도에 비례한 확률로 교배 대상을 선택하였다.

Crossover (교배)

• 선택된 염색체들의 유전 정보를 섞어 다음 세대의 자식 염색체를 만드는 과정이다.
• 이 프로젝트에서는 비트 마스킹으로 두 부모 염색체의 유전자를 조합하여 자식 염색체를 생성하였다.

Mutation (돌연변이)

• 일정 확률로 기존 유전 정보와 무관한 완전히 새로운 유전자를 출현시키는 것이다.
• 중세 유럽 왕가의 근친 결혼이 유전병을 낳았듯, 우수한 유전자끼리만 반복 교배하면 유전적 다양성이 사라져 최적의 결과에 도달할 수 없다.
• 일정 확률로 돌연변이를 만들어야 지역 최적에 갇히지 않고 더 나은 해를 탐색할 수 있다.
• 이 프로젝트에서는 0.5% 확률로 염색체를 완전히 랜덤한 값으로 교체하였다.

구현

• 각 자동차에는 좌/우 대각선 센서와 정면 센서, 총 3개의 센서를 부착한다.
• 굽은 길에서 센서가 벽을 감지하면, 유전자가 정한 회전값만큼 꺾어서 진행한다.
• 목표는 벽에 부딪히지 않고 트랙을 완주하는 것이고, 완주 이후에는 더 빠르게 완주하는 것이다.
• 즉 최적의 출발 위치와 센서 감지별 최적의 회전량을 찾는 것이 핵심이다.

Gene (유전 정보)

• 염색체는 24비트로 구성하였다.
• 출발 위치와 센서별 회전값을 인코딩한다.

영역	비트	설명
x, y	각 2bit	16개 출발 위치 중 하나를 결정한다
Sides	8bit	좌/우 한쪽 센서만 감지 시 회전량이다
Sides & Forward	8bit	좌/우 + 정면 센서 동시 감지 시 회전량이다
Forward	4bit	정면 센서만 감지 시 회전량이다

• Sides 계열은 8bit(0~255)로 세밀한 회전 각도를 표현할 수 있도록 하였고, Forward는 정면 감지 시 큰 범위의 회전이 필요 없다고 판단하여 4bit(0~15)로 구성하였다.
• 센서 감지 상태는 3비트 비트마스크로 표현한다.
• 좌측 센서 0b100, 정면 센서 0b010, 우측 센서 0b001로 OR 연산하여 조합한다.

예) 0xC5A03C (24bit)

  x    y     Sides   Sides&Forward  Forward
 [11] [00]  [01011010]  [00000011]   [1100]

→ 출발 위치: x=3, y=0
→ 좌/우만 감지 시 회전량: 90
→ 좌/우+정면 감지 시 회전량: 3
→ 정면만 감지 시 회전량: 12

// sensor.cs
if (this.gameObject.name == "Left_Sensor")
    car.sensor_detected |= 0b100;
if (this.gameObject.name == "Middle_Sensor")
    car.sensor_detected |= 0b010;
if (this.gameObject.name == "Right_Sensor")
    car.sensor_detected |= 0b001;

• 자동차는 감지 상태에 따라 다른 회전값을 적용한다.

// car.cs
switch (sensor_detected)
{
    case 0b000: Drive(); break;               // 감지 없음 → 직진
    case 0b100: Turn(sharpTurnValue); break;   // 좌측만 → 우회전
    case 0b001: Turn(-sharpTurnValue); break;  // 우측만 → 좌회전
    case 0b110: Turn(smoothTurnValue); break;  // 좌측+정면 → 부드러운 우회전
    case 0b011: Turn(-smoothTurnValue); break; // 우측+정면 → 부드러운 좌회전
    case 0b111:
    case 0b010:
    case 0b101: Turn(backTurnValue); break;    // 그 외 → 후진 회전
}

Fitness (적합도)

• 생존 결과를 점수화하여 우수한 염색체를 구분해야 한다.
• 적합도는 완주 전에는 거리에 비례, 완주 후에는 걸린 시간에 반비례해야 한다.
• 트랙을 여러 구간으로 나누어 통과한 구간마다 점수를 매긴다.
• 완주가 확인되면 (100 - 소요시간)을 보너스로 추가한다.
• 이렇게 하면 완주를 못한 자동차보다 항상 높은 적합도를 가지면서도, 완주한 자동차끼리는 시간에 반비례한 스코어를 얻는다.

// car.cs
private void complete() {
    ScoreCheck();            // 통과 구간 수 × 10점
    record += (100 - time);  // 빠를수록 높은 보너스
    this.dead = true;
}

Selection (선택)

• 룰렛 휠 방식을 사용하였다.
• 적합도를 모두 합산한 뒤 각 염색체의 적합도 비율을 백분위로 구한다.
• 적합도가 높은 염색체가 더 많이 교배될 수 있도록 가중치를 둔다.

// GA.cs
float PR = (fitness[i] / fitness_sum) * 100;
if (PR <= rand)
    rand -= PR;
else
    return i;

Crossover (교배)

• 선택된 염색체 중 임의의 2개는 교배 없이 그대로 다음 세대에 보존한다.
• 나머지는 2개씩 짝지어 비트 마스킹으로 유전자를 조합한다.
• 하나의 부모에서 x, Sides, Forward 일부를, 다른 부모에서 y, Sides&Forward, Forward 나머지를 가져온다.

// GA.cs
int cv = (cars[selected[idx1]].value & 0xCF0F0C)
       + (cars[selected[idx2]].value & 0x30F0F3);

Mutation (돌연변이)

• 아무리 좋은 유전자를 갖더라도 같은 염색체끼리만 교배하면 최적의 자손을 기대할 수 없다.
• 지정된 확률(기본 0.5%)로 염색체를 완전히 랜덤한 값으로 교체하여 유전적 다양성을 유지한다.

// GA.cs
if (mutateRand < mutatePR) {
    childCarsValue[i] = Random.Range(0, 0xFFFFFF + 1);
}

결과

• 초기 세대에서는 센서에 벽이 감지되어도 랜덤한 회전값으로 제대로 나아가지 못한다.
• 세대가 진행되면서 완주에 성공하는 자동차가 나타나고, 이후에는 점점 더 빠른 주행이 가능해진다.
• 돌연변이가 없으면 모든 자동차가 결국 하나의 염색체로 수렴한다.

장애물 추가

• Map에 장애물을 넣어보았다.
• 첫 번째 장애물은 부드럽게 넘어가지만, 두 번째 장애물은 감지 시 오히려 오른쪽으로 부드럽게 꺾어 벽에 충돌하고, SharpTurn을 이용해서 왼쪽으로 틀어 지나는 등 생각했던 것과 다른 다양한 방식으로 장애물을 피해가는 것으로 학습되었다.

학습 데이터 기록

• 학습이 잘 진행되고 있는지 확인하기 위해 각 세대의 적합도, 선택된 염색체, 교배 상황, 부모-자식 염색체 변화를 기록하였다.

• selectedData에서, 적합도가 높은 8, 6이 비교적 많이 선별되었고 낮은 확률로 0이 선택되었다.
• crossoverData에서, 선별된 염색체 중 임의의 2개(2, 8)에 해당하는 염색체는 그대로 다음 자식이 되고, 이후에는 2개씩 짝지어져 유전자가 조합되어 자식 유전자를 형성하는 것을 볼 수 있다.
• geneData는 부모 유전자와 다음 자식 유전자를 보여준다.

스크린샷

• 23세대에 걸쳐 장애물을 모두 피하는 개체가 발생하였다 (빨강).
• 1순위와 2순위 개체로 점점 갈리는 상황을 볼 수 있다.
• 노란색은 돌연변이이다.