[Genetic Algorithm] 유전 알고리즘 응용사례 (흥미로운 동영상)

유전 알고리즘을 배우면 뭘 할 수 있는데?

  스케줄링 알고리즘으로서의 '유전 알고리즘'에 관한 짧은 교육을 준비하다가, 유전 알고리즘으로 할 수 있는 일(?)에 대해서 보여주고 싶어서 유튜브 영상 중, 괜찮다 싶은 영상들을 몇개 모아 봤습니다. 개인적으로 숲을 먼저 보고 나무를 보고 싶어하는 아주 피곤한 스타일이라, 다른 사람들에게도 뭔가 설명해줄 때, '그래서 이 지루하고 긴 교육을 받고 나면 뭘 할 수 있는 건데?'라는 질문에 항상 답을 해주고 싶습니다. 제가 교육을 받을 때, 가장 교수/강사에게 바라는 것이기도 합니다.

Travelling Salesman Problem

  TSP, 순회외판원문제

  대표적인 NP-Hard ('복잡도 이론'에서 NP에 해당할 만큼의 복잡도를 자랑하는, 그래서 해답을 찾아내는 연산에 걸리는 시간이 매우 길 것으로 예상되는 문제) 문제의 해결에 많이 사용됩니다.

  아래 영상에서 메인 GUI의 오른편 상자에서, 20개의 색으로 구분된 가로줄은 하나의 가능해 (염색체, chromosome)를 나타내고, 세로 3000줄은 해를 탐색하는 해집단(population)의 수가 3000개라는 것을 의미합니다.

  시간이 흐를 수록 좋다고 생각되는 (혹은 충분히 반복 연산해서 검증된) 해 부분이 동일한 색깔을 갖추어가는 모습을 보여주기 때문에 유전 알고리즘의 특징을 보여주는 좋은 예인 것 같습니다. 역시 사람은 이렇게 시각적으로 학습하는 것이 매우 효율적이네요. 하지만, 늘 가시적으로 표현하는 것은 노력이 요구되는 일입니다. 알고리즘 제대로 짜기도 어려운 판국에 말이죠 -_-

Genetic Algorithm : Scheduling Optimization for Dummies

  유전 알고리즘을 이용해서 스케줄링 최적화(Scheduling Optimization)를 하는 영상

  공장이나 머신의 스케줄은 아니고, 고등학교 수업 시간표를 짜는 모습

  기본적인 유전 알고리즘의 세 연산을 충분히 활용해서 시간표를 생성하고 있습니다.

  학생들이 동시에 두가지 수업을 들을 수 없다는 '제한조건' 등에 대해서도 언급하고 있네요.

Auto Adaptable Walking Robot with Genetic Algorithm

  일반적으로 사람들이 제일 흥미를 느낄 것 같은, 유전 알고리즘을 이용한 로봇의 주행 성능을 점점 향상시키는 영상입니다. 로봇이라는 플랜트(plant)가 움직여 주니, 단순히 해의 질(quality)가 높아지는 것을 숫자로 보는 것보다 훨씬 보는 재미가 있네요. 물리적인 의미를 가질 수 있게, 로봇을 만들어 낸 기술이 부럽습니다.

  최적화 함수(유전 알고리즘에서는 적합도 함수 fitness function)를 어떻게 구성했는지에 대해서는 언급하고 있지 않지만, 6개의 독립된 다리를 제어하는 명령을 랜덤으로 생성해서, 실제 로봇의 주행거리, 자세 등을 센서로 입력받고, 더 나은 움직임을 보인 명령들을 계속해서 발전시켜 나간 것은 아닌지하는 막연한, 제어를 공부한 사람이라면 누구나 할 수 있는 상상을 한번 해봅니다 (  -_-)=3

Mona Lisa approximated with 150 circles through Genetic Algorithm

  150개의 원으로 모나리자 그림과 비슷한 형태의 영상을 보여주도록 유도한 내용.

  모나리자의 원본 그림과 빛들이 만들어 내는 모습을 어떻게 비교하도록 최적화 식을 구성했는지가 너무 궁금합니다. 교육 때, 보여주니 사람들 반응이 꽤나 신기해하는 느낌이었습니다.

슈퍼마리오 최적 점프 타이밍 계산

(Super Mario 1-1)

  슈퍼 마리오 모르는 사람도 있을까요.

  게임을 좋아하는 제가, 설명에 빼먹기에는 너무 아쉬운 게임 적용 예시입니다.

  슈퍼 마리오가 마지막 'goal'까지 가기 위해서 어떤 타이밍에 '점프'를 하면 죽지않고 마지막까지 살아남을 수 있을지를 유전 알고리즘으로 연구한 영상입니다.

  적들의 움직임이 프로그램된 대로 항상 동일하다는 가정하에서, 경험적으로 점프 족보(어떤 타이밍에 점프할 것인가)를 만들어내고, 완성해가고 있습니다. 프레임을 기준으로 족보(최적해, chromosome)를 생성하고 있습니다. 시간 기준 동일한 프레임을 가지고 있을 경우, 프레임은 시간에 대한 함수로 변환할 수 있으니, 시간에 따른 점프 족보라고 말해도 될 것입니다.

  그런데, 영상에서는 처음부터 끝까지 살아남는 점프 타이밍 최적해를 구해주지는 못하고 있네요.

  저도 뭐, 단순히 유전 알고리즘을 이해하고 기본적인 적용을 해보는 수준에만 연구를 그쳤었는데, 더 다양한 분야에 적용해 보고 싶다는 생각이 들었습니다.