Documentație / Istoric

Istoric: teza (2026)

Programarea genetică în planificarea sezonului de baseball. Fezabilitate și problemă de optimizare. Teză de Inginerie Calculatoare, ITAM. Coordonator: Dr. Andrés Gómez de Silva Garza. Aprobat la 23 iulie 2026.

Problema

MLB programează 2.430 de meciuri pentru 30 de echipe în aproximativ 180 de zile. Fiecare echipă călătorește între orașe, iar distanța variază foarte mult de la o echipă la alta. În 2016, Seattle a parcurs 76.683 km, iar Chicago Cubs 39.015 km.

Găsirea programului cu cea mai mică distanță totală se numește Problema Transportului la Turnee (PTT). Este o problemă NP-dificilă: numărul programelor posibile crește atât de repede încât nu le poți verifica pe toate.

Metoda

Programarea genetică (PG), propusă de John Koza în 1992, imită evoluția. Creează o populație de soluții, le ia pe cele mai bune și le combină și le modifică pentru a forma o nouă generație.

Reprezentare: Fiecare calendar este un arbore. Nodurile sale sunt operații precum crear_juego (data, echipa gazdă, echipa oaspete) și obtener_calendario, care se alătură a două liste de meciuri.
Viabilitate (C1): Fiecare echipă trebuie să joace exact numărul de meciuri cerut de turneu. O valoare de 0 înseamnă că programul este valabil.
Distanța (C2): suma transferurilor, calculată cu formula lui Haversine pe coordonatele fiecărui stadion.
Software: trei module (planificator, calculator și program genetic) cu biblioteca DEAP, separate de o aplicație web în Django.

Rezultatele

Încearcă 30 de echipe, 163 de meciuri pe echipă, serii de 5 meciuri și 20 de generații.

Comparație între căutarea aleatorie și programarea genetică
Metodă	Probabil. de a trece	Probabil. de mutație	Fezabilitate (C1)	Distanța totală (C2)	Timp
Căutare aleatorie	0.0	0.0	0 (valid)	2,663,470.70 km Distanță mai scurtă	200.25 s
Programare genetică	0.8	0.2	0 (valid)	3,182,738.33 km	3,337.81 s

Descoperirea principală

Programarea genetică nu a depășit căutarea aleatorie. A oferit o distanță cu 19,5% mai mare și a durat aproape de 17 ori mai mult. Cel mai bun calendar a venit întotdeauna din generația inițială, care este aleatorie.

Teza a identificat următoarele cauze:

Operatorii generici de crossover și mutație schimbă nodurile fără a ști problema. Aproape întotdeauna produc calendare invalide.
Funcția de fitness acordă mult mai multă importanță viabilității decât distanței. Un copil invalid pierde întotdeauna în fața unui părinte valid.
Algoritmul a convergit rapid către un optim local și a păstrat doar soluțiile inițiale.

Un rezultat negativ este, de asemenea, un rezultat. Arată că reprezentarea și operatorii contează la fel de mult ca algoritmul.

Lucrări viitoare

Teza propunea operatori contextuali: în loc să schimbe nodurile aleatoriu, să schimbi serii sau blocuri întregi care mențin calendarul valabil. El a menționat, de asemenea, calculul cuantic pentru a explora multe configurații simultan.

Vezi ce s-a făcut după teză

Cronologie

Mai 2026 · Versiunea preoficială a documentului de teză.
23 iulie 2026 · Apărare în Mexico City. Teză aprobată.

Materiale și citare

Documentul tezei, versiunea pre-oficială (PDF, 4.8 MB, în spaniolă)
Prezentarea apărării (PDF, 2.9 MB, în spaniolă)

Citare în format 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.