세대
목표 도달
가장 빠른 도착
최근접 거리
  • 비행 중
  • 목표 도달
  • 충돌
  • 지난 세대의 최고 비행
  • 목표 도달
  • 충돌

유전 알고리즘에 대해 더 알아보기

유전 알고리즘 플레이그라운드

유전 알고리즘은 진화가 생물을 빚어내는 방식으로 문제를 풉니다. 무작위 답을 많이 시도하고, 더 나은 것을 남기고, 그것들을 섞고 몇 군데를 무작위로 바꾼 뒤, 이를 반복합니다. 여기서 답은 로켓입니다. 각 로켓은 무작위 추진력 목록만 따를 뿐 다른 것은 아무것도 하지 않으므로, 처음에는 목적 없이 이리저리 굴러다닙니다. '실행'을 누르고, 누구도 어디로 가야 하는지 알려 주지 않는데도 무리가 세대를 거듭하며 나아져 마침내 대부분의 로켓이 벽을 돌아 목표에 도달하는 모습을 지켜보세요. '실행'을 누르고 로켓 무리가 초록색 목표에 닿으려고 애쓰는 모습을 지켜보세요. 각 로켓은 오직 자신의 유전자만 따릅니다. 유전자는 작은 추진력들의 목록으로, 비행의 매 순간마다 하나씩 있습니다. 비행이 끝날 때마다 목표에 가장 가까이 간 로켓, 무엇보다 목표에 도착한 로켓이 다음 세대의 부모가 될 가능성이 가장 높습니다. 부모의 유전자는 섞이고, 그중 몇 개는 무작위로 바뀝니다. '다음 세대'는 비행의 나머지를 건너뜁니다. 필드 위를 드래그하면 벽을 그릴 수 있고, 벽을 클릭하면 지울 수 있습니다.

작동 원리

  1. 장애물을 고르거나 필드 위를 드래그해 벽을 직접 그리고, 개체 수, 돌연변이율, 수명을 설정하세요.
  2. '실행'을 누르고 세대마다 비행하는 모습을 지켜보세요. '다음 세대'는 비행의 나머지를 건너뜁니다.
  3. 타일과 차트에서 목표에 도달한 비율을 확인하고, 다른 돌연변이율과 선택 방식도 시도해 보세요.

로켓은 어떻게 진화할까요

모든 로켓은 유전자를 지니고 있습니다. 비행의 매 순간마다 작은 추진력이 하나씩 있습니다. 첫 세대의 유전자는 무작위입니다. 비행이 끝나면 각 로켓은 적합도 점수를 받습니다. 일찍 도착할수록 가장 높고, 그다음으로는 목표에 가까이 끝났을수록 높으며, 충돌하면 10으로 나뉩니다. 다음 세대의 부모는 무작위로 선택되지만, 적합도가 높은 로켓일수록 선택될 가능성이 큽니다. 각 자식은 유전자의 앞부분을 한쪽 부모에게서, 나머지를 다른 부모에게서 받고, 몇몇 유전자는 무작위 추진력으로 바뀝니다. 이것이 돌연변이입니다. 세대를 거듭하면서 좋은 비행 계획이 퍼지고 개선됩니다.

설정이 바꾸는 것

개체 수가 많을수록 한 번에 더 많은 비행 계획을 탐색하고 막힐 가능성도 줄어들지만, 세대마다 시간이 더 걸립니다. 돌연변이율은 탐색과 잘되는 것을 유지하는 것 사이의 균형을 맞춥니다. 돌연변이가 없으면 무리는 금세 새로운 아이디어가 바닥나고, 너무 많으면 좋은 비행을 찾는 것보다 더 빨리 잊어버립니다. 룰렛 선택은 적합도에 비례해 부모를 고르고, 토너먼트는 무작위로 고른 로켓 세 대 중 가장 좋은 것을 뽑는데, 이는 적합도의 척도를 어떻게 잡느냐에 덜 민감합니다. 엘리트 보존은 최고의 로켓을 그대로 다음 세대에 복사하므로 최고 결과가 나빠지는 일이 없습니다.

자주 묻는 질문

로켓은 왜 엇갈린 벽 뒤에서 막힐까요?

적합도가 목표까지의 직선 거리를 재기 때문에, 목표 아래의 벽으로 날아가 부딪히는 로켓이 틈을 찾으러 멀리 날아가는 로켓보다 점수가 더 높습니다. 그래서 무리는 그 막다른 곳, 즉 국소 최적해에 몰려듭니다. 개체 수를 늘리거나 돌연변이를 늘리거나 토너먼트 선택을 쓰면 빠져나오는 데 도움이 되고, 벽을 돌아가는 실제 경로를 재는 적합도라면 이 함정을 피할 수 있습니다. 좋은 적합도 함수를 고르는 것이 유전 알고리즘을 사용할 때 가장 어려운 부분입니다.

자연에서도 진화가 이렇게 일어나나요?

큰 틀에서는 그렇습니다. 돌연변이와 재조합에서 오는 변이, 유전자의 유전, 가장 적합한 개체의 선택은 다윈 이론의 재료입니다. 하지만 차이도 큽니다. 자연에는 목표도 적합도 공식도 없고 오직 생존과 번식만 있으며, 실제 유전체는 행동을 나열하는 대신 발생 과정을 통해 몸을 만듭니다.

유전 알고리즘은 어디에 쓰이나요?

가능한 답의 공간이 엄청나게 크고 후보를 쉽게 평가할 수 있는 문제에 쓰입니다. 안테나, 날개, 자동차 부품의 형상 설계, 시간표 작성, 다른 알고리즘의 설정 조정, 신경망 설계, 그리고 예술 작품과 게임 전략 창작 등이 그 예입니다. 2006년 ST5 위성에 실린 NASA의 진화된 안테나가 유명한 예입니다.

최고의 로켓이 다음 세대에서 왜 가끔 더 못 날까요?

엘리트 보존이 없으면 최고의 로켓은 복사되지 않습니다. 그 유전자는 다른 유전자와 섞이고 경우에 따라 돌연변이된 채로만 살아남으므로, 다음 세대는 그 비행을 정확히 그대로 잃을 수 있습니다. 엘리트 보존을 켜면 최고의 로켓이 그대로 유지되고 최고 결과가 나빠지는 일이 없습니다.

서버로 전송되는 것이 있나요?

아니요. 로켓은 브라우저 안에서 날고 진화하며, 직접 그린 벽은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동