문서 / 역사

역사적: 논문 (2026)

야구 시즌 계획에서의 유전 프로그래밍. 타당성 및 최적화 문제. 컴퓨터공학 논문, ITAM. 지도교수: 안드레스 고메스 데 실바 가르사 박사. 2026년 7월 23일 승인.

문제

MLB는 약 180일 동안 30개 팀에 2,430경기를 일정 조정합니다. 각 팀은 도시 간 이동을 하며, 팀마다 거리가 크게 다릅니다. 2016년 시애틀은 76,683km, 시카고 컵스는 39,015km를 이동했습니다.

총 거리가 가장 짧은 일정을 찾는 것을 토너먼트 교통 문제(PTT)라고 합니다. 이것은 NP 어려운 문제로, 가능한 일정 수가 너무 빠르게 늘어나 모두 확인할 수 없습니다.

방법

유전적 프로그래밍(PG)은 1992년 존 코자가 제안한 진화를 모방합니다. 이 방법은 여러 해답을 만들고, 가장 좋은 것들을 조합하고 변형하여 새로운 세대를 만듭니다.

표현: 각 달력은 트리입니다. 노드는 (날짜, 홈팀, 원정팀) 와 obtener_calendario같은 crear_juego 연산으로, 두 경기 리스트에 연결됩니다.
유효성(C1): 각 팀은 토너먼트가 요구하는 정확한 경기 수를 치러야 합니다. 0이 되면 일정이 유효하다는 뜻입니다.
거리(C2): 각 경기장 좌표에 대한 하버사인 공식으로 계산한 전송 횟수의 합.
소프트웨어: DEAP 라이브러리와 함께 Django 웹 애플리케이션과 분리된 세 가지 모듈(계획기, 계산기, 유전 프로그램)입니다.

결과

30개 팀, 팀당 163경기, 5경기 시리즈, 20세대를 시도해 보세요.

무작위 탐색과 유전 프로그래밍의 비교
방법	아마도. 건너는 것에 대해	아마도. 돌연변이에 대해	타당성 (C1)	총 거리 (C2)	시간
무작위 탐색	0.0	0.0	0 (유효)	2,663,470.70 km 짧은 거리	200.25 s
유전 프로그래밍	0.8	0.2	0 (유효)	3,182,738.33 km	3,337.81 s

주요 발견

유전자 프로그래밍은 무작위 탐색보다 더 뛰어나지 않았습니다. 무작위 탐색 은 19.5% 더 긴 거리를 제공했고, 거의 17배 더 오래 걸렸습니다. 가장 좋은 달력은 항상 무작위인 초기 세대에서 나왔습니다.

논문은 다음과 같은 원인들을 밝혀냈다:

일반적인 교차 및 돌연변이 연산자는 문제를 모른 채 노드를 변경합니다. 거의 항상 유효하지 않은 달력을 생성합니다.
적합도 함수는 거리보다 생존 가능성에 훨씬 더 큰 비중을 둡니다. 무효 아동은 항상 유효한 부모에게 패배합니다.
알고리즘은 곧 국소 최적에 수렴하여 초기 해만 유지했다.

음수 결과도 결과입니다. 이는 표현과 연산자가 알고리즘만큼 중요함을 보여줍니다.

향후 활동

논문은 맥락적 연산자를 제안했습니다: 노드를 무작위로 바꾸는 대신, 달력을 유효하게 유지하는 전체 시리즈나 블록을 교체하는 것. 그는 또한 양자 컴퓨팅을 언급하여 여러 구성을 동시에 탐구했습니다.

논문 이후에 어떤 작업이 이루어졌는지 확인해 보세요

연대표

2026년 5월 · 논문 문서의 공식 이전 버전입니다.
2026년 7월 23일 · 수심 심사는 멕시코시티. 논문 승인.

자료 및 인용문

논문 문서, 공식 이전 버전 (PDF, 4.8 MB, 스페인어로)
변호 측 제시 (PDF, 2.9 MB, 스페인어로)

APA 형식의 인용:

Brenes Valencia, L. P. (2026). Programación genética en la planificación de temporadas de béisbol (Tesis de Ingeniería en Computación). Instituto Tecnológico Autónomo de México (ITAM), Ciudad de México, México.