Documentação / História
Histórico: a tese (2026)
Programação genética no planejamento de temporadas de beisebol. Problema de viabilidade e otimização. Tese de Engenharia da Computação, ITAM. Orientador: Dr. Andrés Gómez de Silva Garza. Aprovado em 23 de julho de 2026.
O problema
A MLB agenda 2.430 jogos para 30 times em cerca de 180 dias. Cada time viaja entre cidades, e a distância varia muito de time para time. Em 2016, Seattle percorreu 76.683 km, e o Chicago Cubs percorreu 39.015 km.
Encontrar o cronograma com a menor distância total é conhecido como o Problema do Transporte para Torneios (PTT). É um problema NP-difícil: o número de horários possíveis cresce tão rápido que você não consegue conferir todos.
O método
A programação genética (PG), proposta por John Koza em 1992, imita a evolução. Ela cria uma população de soluções, pega as melhores e as combina e modifica para formar uma nova geração.
- Representação: Cada calendário é uma árvore. Seus nós são operações como
crear_juego(data, time da casa, time visitante) eobtener_calendario, que juntam duas listas de jogos. - Viabilidade (C1): Cada equipe deve jogar exatamente o número de jogos que o torneio exige. Um valor de 0 significa que o calendário é válido.
- Distância (C2): a soma das transferências, calculada com a fórmula de Haversine nas coordenadas de cada estádio.
- Software: três módulos (planejador, calculadora e programa genético) com a biblioteca DEAP, separados de uma aplicação web em Django.
Os resultados
Tente 30 times, 163 jogos por time, séries de 5 jogos e 20 gerações.
| Método | Provavelmente. de atravessar | Provavelmente. de mutação | Viabilidade (C1) | Distância total (C2) | Tempo |
|---|---|---|---|---|---|
| Busca aleatória | 0.0 | 0.0 | 0 (válido) | 2,663,470.70 km Distância mais curta | 200.25 s |
| Programação genética | 0.8 | 0.2 | 0 (válido) | 3,182,738.33 km | 3,337.81 s |
A principal descoberta
A programação genética não superou a busca aleatória. Ela deu uma distância 19,5% maior e levou quase 17 vezes mais. O melhor calendário sempre veio da geração inicial, que é aleatória.
A tese identificou as seguintes causas:
- Operadores genéricos de crossover e mutação trocam de nós sem saber qual é o problema. Eles quase sempre produzem calendários inválidos.
- A função de aptidão dá muito mais peso à viabilidade do que à distância. Uma criança inválida sempre perde para um pai válido.
- O algoritmo logo convergiu para um ótimo local e manteve apenas as soluções iniciais.
Um resultado negativo também é um resultado. Mostra que a representação e os operadores importam tanto quanto o algoritmo.
Trabalhos futuros
A tese propôs operadores contextuais: em vez de mudar de nós aleatoriamente, trocar séries ou blocos inteiros que mantêm o calendário válido. Ele também mencionou computação quântica para explorar muitas configurações ao mesmo tempo.
Linha do tempo
- · Versão pré-oficial do documento de tese.
- · Defesa na Cidade do México. Tese aprovada.
Materiais e citações
- Documento de tese, versão pré-oficial (PDF, 4.8 MB, em espanhol)
- Apresentação da defesa (PDF, 2.9 MB, em espanhol)
Citação em formato 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.