Dokumentation / Historie

Historisk: tesen (2026)

Genetisk programmering i planlægning af baseballsæsonen. Gennemførligheds- og optimeringsproblem. Computer Engineering Speciale, ITAM. Vejleder: Dr. Andrés Gómez de Silva Garza. Godkendt den 23. juli 2026.

Problemet

MLB planlægger 2.430 kampe for 30 hold på omkring 180 dage. Hvert hold rejser mellem byer, og afstanden varierer meget fra hold til hold. I 2016 tilbagelagde Seattle 76.683 km, og Chicago Cubs tilbagelagde 39.015 km.

At finde tidsplanen med den laveste samlede distance kaldes Tournament Transportation Problem (PTT). Det er et NP-svært problem: antallet af mulige tidsplaner vokser så hurtigt, at du ikke kan tjekke dem alle.

Metoden

Genetisk programmering (PG), foreslået af John Koza i 1992, efterligner evolution. Den skaber en population af løsninger, tager de bedste og kombinerer og modificerer dem for at danne en ny generation.

Repræsentation: Hver kalender er et træ. Dens noder er operationer som crear_juego (dato, hjemmehold, udehold) og obtener_calendario, som forbinder to lister af kampe.
Levedygtighed (C1): Hvert hold skal spille præcis det antal kampe, som turneringen kræver. En værdi på 0 betyder, at planen er gyldig.
Distance (C2): summen af overførslerne, beregnet med Haversines formel på koordinaterne for hvert stadion.
Software: tre moduler (planlægger, regnemaskine og genetisk program) med DEAP-biblioteket, adskilt fra en webapplikation i Django.

Resultaterne

Prøv 30 hold, 163 kampe pr. hold, 5-kamps serier og 20 generationer.

Sammenligning af tilfældig søgning og genetisk programmering
Metode	Sandsynligvis. af at krydse	Sandsynligvis. af mutation	Gennemførlighed (C1)	Total distance (C2)	Tidspunkt
Tilfældig søgning	0.0	0.0	0 (gyldig)	2,663,470.70 km Kortere distance	200.25 s
Genetisk programmering	0.8	0.2	0 (gyldig)	3,182,738.33 km	3,337.81 s

Hovedfundet

Genetisk programmering overgik ikke tilfældig søgning. Den gav en 19,5% større afstand og tog næsten 17 gange længere tid. Den bedste kalender kom altid fra den første generation, som er tilfældig.

Afhandlingen identificerede følgende årsager:

Generiske crossover- og mutationsoperatorer skifter noder uden at kende problemet. De producerer næsten altid ugyldige kalendere.
Fitnessfunktionen giver meget mere vægt til levedygtighed end til afstand. Et ugyldigt barn taber altid til en gyldig forælder.
Algoritmen konvergerede snart mod et lokalt optimum og bevarede kun de oprindelige løsninger.

Et negativt resultat er også et resultat. Det viser, at repræsentationen og operatorerne betyder lige så meget som algoritmen.

Fremtidigt arbejde

Afhandlingen foreslog kontekstuelle operatorer: i stedet for at skifte noder tilfældigt, byt hele rækker eller blokke, der holder kalenderen gyldig. Han nævnte også kvantecomputing for at udforske mange konfigurationer på én gang.

Se, hvad der blev gjort efter specialet

Tidslinje

Maj 2026 · Præofficiel version af specialedokumentet.
23. juli 2026 · Forsvar i Mexico City. Afhandling godkendt.

Materialer og kildehenvisning

Specialedokument, præ-officiel version (PDF, 4.8 MB, på spansk)
Fremstilling af forsvaret (PDF, 2.9 MB, på spansk)

Citation i APA-format:

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.