Documentazione / Storia
Storico: la tesi (2026)
Programmazione genetica nella pianificazione della stagione di baseball. Problema di fattibilità e ottimizzazione. Tesi di Ingegneria Informatica, ITAM. Relatore: Dr. Andrés Gómez de Silva Garza. Approvato il 23 luglio 2026.
Il problema
La MLB programma 2.430 partite per 30 squadre in circa 180 giorni. Ogni squadra viaggia tra le città e la distanza varia notevolmente da squadra a squadra. Nel 2016, Seattle ha percorso 76.683 km e i Chicago Cubs 39.015 km.
Trovare il calendario con la distanza totale più bassa è noto come Problema del Trasporto del Torneo (PTT). È un problema NP-difficile: il numero di possibili orari cresce così rapidamente che non puoi controllarli tutti.
Il metodo
La programmazione genetica (PG), proposta da John Koza nel 1992, imita l'evoluzione. Crea una popolazione di soluzioni, prende le migliori e le combina e modifica per formare una nuova generazione.
- Rappresentazione: ogni calendario è un albero. I suoi nodi sono operazioni come
crear_juego(data, squadra di casa, squadra ospite) eobtener_calendario, che uniscono due liste di partite. - Fattibilità (C1): Ogni squadra deve giocare esattamente il numero di partite richieste dal torneo. Un valore pari a 0 significa che il calendario è valido.
- Distanza (C2): la somma dei trasferimenti, calcolata con la formula di Haversine sulle coordinate di ciascun stadio.
- Software: tre moduli (planner, calcolatrice e programma genetico) con la libreria DEAP, separati da un'applicazione web in Django.
I risultati
Prova 30 squadre, 163 partite per squadra, serie da 5 partite e 20 generazioni.
| Metodo | Probabilmente. di attraversare | Probabilmente. di mutazione | Fattibilità (C1) | Distanza totale (C2) | Tempo |
|---|---|---|---|---|---|
| Ricerca casuale | 0.0 | 0.0 | 0 (valido) | 2,663,470.70 km Distanza più breve | 200.25 s |
| Programmazione genetica | 0.8 | 0.2 | 0 (valido) | 3,182,738.33 km | 3,337.81 s |
Il principale ritrovamento
La programmazione genetica non ha superato la ricerca casuale. Ha dato una distanza superiore del 19,5% e ha impiegato quasi 17 volte più tempo. Il miglior calendario è sempre arrivato dalla generazione iniziale, che è casuale.
La tesi ha identificato queste cause:
- Gli operatori generici di crossover e mutazione cambiano nodo senza conoscere il problema. Quasi sempre producono calendari invalidi.
- La funzione di fitness dà molto più peso alla vitalità che alla distanza. Un bambino invalido perde sempre contro un genitore valido.
- L'algoritmo convergeva presto su un ottimale locale e manteneva solo le soluzioni iniziali.
Un risultato negativo è anche un risultato. Dimostra che la rappresentazione e gli operatori contano tanto quanto l'algoritmo.
Lavori futuri
La tesi proponeva operatori contestuali: invece di cambiare nodi casualmente, scambiare intere serie o blocchi che mantengano valido il calendario. Ha anche menzionato il calcolo quantistico per esplorare molte configurazioni contemporaneamente.
Cronologia
- · Versione pre-ufficiale del documento di tesi.
- · Difesa a Città del Messico. Tesi approvata.
Materiali e citazione
- Documento di tesi, versione pre-ufficiale (PDF, 4.8 MB, in spagnolo)
- Presentazione della difesa (PDF, 2.9 MB, in spagnolo)
Citazione in 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.