예전에 장애물을 피해 앞으로 가는 자동차를 유전자알고리즘으로 만들어본 적이 있습니다.
 |
| GA - 자동차[1] 유전자설계 및 초기화 |
여러가지 방식으로 움직이는 자동차 수백대를 만들어 생존경쟁을 시킨후 우수한 녀석들만 모아 자연선택하여 번식시키고 그중에 돌연변이를 만들어 생존경쟁을 반복하면 결국 장애물을 잘 피할 수 있는 자동차를 찾을 수 있다는 것이 유전자알고리즘입니다.
이것과 비슷하지만 이번에는 전혀 다른 식으로 접근해 보았습니다.
1. 개체
기존 방법에서는 여러가지 행동을 하는 자동차를 수백대 만들었습니다. 그리고 그들 사이에서 생존경쟁을 펼쳤습니다.
그런데 이런 생존경쟁을 자동차끼리 시키는 것이 아니라 자동차 내부에서 시킬 수는 없을까요? 즉 자동차가 판단하는 과정을 여러개로 나눈 생각단위란 것을 만들고, 이들에 의해 자동차를 제어하며 동시에 그들 사이의 생존경쟁을 시킨다는 것이죠.
여기서는 다음과 같은 생각단위를 만들었습니다.
만약 자동차가
와 같은 상태에 있다면 ㉠의 경우는 앞에 바위가 있으니 각 방향으로 움직일 확률이(-0.25, 0.3, -0.28)이 될 것입니다. ㉡은 왼쪽 앞에 길이 있으니 (0.32, 0.82, -0.21)이 되겠죠.
그리고 이 확률을 가지고 자동차의 다음 행동을 결정합니다. ㉠의 경우는 앞으로 가서 바위와 충돌하겠군요. ㉡의 경우는 왼쪽 앞으로 제대로 갈 확률이 ⅓도 되지 않습니다.
2. 모둠활동
이런 생각단위 하나둘로는 이 차가 처한 상태를 제대로 판단할 수 없습니다. 위처럼 ㉠과 ㉡만 가지고 판단한다면 오른쪽 앞에 뭐가 있는지는 알 수 없는 상태로 결정을 내리게 될 것입니다. 반대로 1024개의 생각단위 모두를 가지고 판단한다면 어떤 것이 유익하고 어떤 것이 불리한지 전혀 알 수 없는 상태가 될 것입니다. 그러므로 1024개의 생각단위 중에서 16개를 뽑아 모둠을 만들어 처리합니다. 그렇게 되면 행동의 결과를 해당 모둠 멤버에게 책임지울 수 있죠.
다만 이렇게 모둠을 만들어 처리하면 한가지 문제가 생깁니다. 바로
이런 문제 말이죠.
올바른 결정을 내리는 생각단위들의 모둠 속에 트롤 하나가 섞여있으면 그 트롤도 이득을 얻어 번식할 수 있습니다. 또는 이 트롤 때문에 일이 틀어지면 같은 모둠의 다른 생각단위들도 같은 손해를 볼 수 있다는 것입니다. 마치 조별과제에 하나도 기여하지 못한 학생 때문에 다른 학생들의 점수고 깎이고, 정작 놀러다닌 학생은 다른 열심히 한 학생들과 같은 점수를 받는 것처럼 말이죠.
이 문제를 해결하기 위해 조별과제의 최후와 같은 해결책을 써보기로 했습니다. 생각단위들 사이의 호감도를 도입했습니다.
최초에는 아무렇게나 모둠을 만들지만, 모둠활동이 끝나면 그 결과에 따라 멤버들의 호감도를 수정합니다. 결과가 좋으면(길을 따라 움직이면) 멤버들 사이의 호감도를 증가시키고 결과가 나쁘면(바위 위로 올라가면) 멤버들 사이의 호감도를 감소시키는 것이죠. 그리고 새로 모둠을 만들 때 이 호감도를 참조해서 멤버들을 모읍니다.
3. 재생산
기존의 GA일 경우에는 각 세대가 확실하게 구분되었습니다. 무리를 만들어 생존경쟁을 시키고 번식시킨 후에는 기존 세대는 싹 죽여버립니다. 그리고 새로 태어난 세대를 가지고 반복합니다.
하지만 이 문제의 경우는 한가지 문제가 있어요. 이렇게 세대가 교체된 직후에는 효율이 0으로 떨어진다는 것입니다. 물론 그 후에는 효율이 올라가지만 주기적으로 효율이 떨어지는 것은 어쩔 수 없는 현상입니다.
여기서는 각 생각단위가 각자의 수명을 가지고 있습니다. 수명이 끝난 생각단위는 제거되며, 나머지 생각단위들 중에서 하나를 선택, 번식시켜 빈자리를 채우게 됩니다. 이렇게 되면 세대 전체를 바꿀 때 효율이 떨어지는 현상이 사라집니다.
4. 호감도
처음 만난 생각단위들 사이에도 기본적인 호감도는 가지고 있습니다(호감도가 전혀 없다면 최초 모둠을 만들 수가 없죠).
호감도 높은 것들을 중심으로 모둠을 만들고 나서 그 모둠의 활동결과에 따라 해당 모둠 멤버들의 호감도를 늘리거나 줄입니다. 이 호감도는 다음에 모둠을 다시 만들 때의 기준이 되죠.
새로운 생각단위가 태어난다면, 그 생각단위는 모체와 거의 유사합니다. 즉 모체와 사이좋은 생각단위는 이 새로 태어난 녀석과도 사이가 좋을 가능성이 크죠.
그 때문에 이 경우에는 다른 생각단위에 대한 모체의 호감도의 절반을 기본값으로 설정했습니다.
이런 식으로 만든 자동차가 움직이기 시작할 때의 모습입니다.
그리고 약 10만회의 진행을 했을 때의 모습입니다.
댓글 없음:
댓글 쓰기