Dokumentation / Historia

Historisk: avhandlingen (2026)

Genetisk programmering i planering av basebollsäsongen. Genomförbarhets- och optimeringsproblem. Examensarbete om datorteknik, ITAM. Handledare: Dr. Andrés Gómez de Silva Garza. Godkänt den 23 juli 2026.

Problemet

MLB schemalägger 2 430 matcher för 30 lag på cirka 180 dagar. Varje lag reser mellan städer, och avståndet varierar mycket från lag till lag. År 2016 färdades Seattle 76 683 km och Chicago Cubs 39 015 km.

Att hitta schemat med lägst total distans kallas Tournament Transportation Problem (PTT). Det är ett NP-svårt problem: antalet möjliga scheman växer så snabbt att du inte kan kolla alla.

Metoden

Genetisk programmering (PG), föreslagen av John Koza 1992, efterliknar evolution. Den skapar en population av lösningar, tar de bästa och kombinerar och modifierar dem för att bilda en ny generation.

Representation: Varje kalender är ett träd. Dess noder är operationer som crear_juego (datum, hemmalag, bortalag) och obtener_calendario, som slår ihop två matchlistor.
Livskraft (C1): Varje lag måste spela exakt det antal matcher som turneringen kräver. Ett värde på 0 betyder att schemat är giltigt.
Avstånd (C2): summan av överföringarna, beräknad med Haversines formel på koordinaterna för varje arena.
Programvara: tre moduler (planerare, miniräknare och genetiskt program) med DEAP-biblioteket, separat från en webbapplikation i Django.

Resultaten

Prova 30 lag, 163 matcher per lag, 5-matchers serier och 20 generationer.

Jämförelse av slumpmässig sökning och genetisk programmering
Metod	Troligen. av att korsa	Troligen. av mutation	Genomförbarhet (C1)	Total sträcka (C2)	Tid
Slumpmässig sökning	0.0	0.0	0 (giltig)	2,663,470.70 km Kortare distans	200.25 s
Genetisk programmering	0.8	0.2	0 (giltig)	3,182,738.33 km	3,337.81 s

Huvudfyndet

Genetisk programmering överträffade inte slumpmässig sökning. Den gav 19,5 % längre avstånd och tog nästan 17 gånger längre tid. Den bästa kalendern kom alltid från den initiala generationen, som är slumpmässig.

Avhandlingen identifierade dessa orsaker:

Generiska crossover- och mutationsoperatorer byter noder utan att känna till problemet. De ger nästan alltid ogiltiga kalendrar.
Fitnessfunktionen ger mycket större vikt åt livsduglighet än åt avstånd. Ett ogiltigt barn förlorar alltid mot en giltig förälder.
Algoritmen konvergerade snart mot ett lokalt optimum och behöll endast de initiala lösningarna.

Ett negativt resultat är också ett resultat. Det visar att representationen och operatorerna är lika viktiga som algoritmen.

Framtida arbete

Avhandlingen föreslog kontextuella operatorer: istället för att slumpmässigt byta noder, byt hela serier eller block som håller kalendern aktuell. Han nämnde också kvantdatorer för att utforska många konfigurationer samtidigt.

Se vad som gjordes efter avhandlingen

Tidslinje

Maj 2026 · Förofficiell version av avhandlingsdokumentet.
23 juli 2026 · Försvar i Mexico City. Avhandling godkänd.

Material och källhänvisningar

Avhandlingsdokument, förofficiell version (PDF, 4.8 MB, på spanska)
Försvarets presentation (PDF, 2.9 MB, på spanska)

Källhänvisning 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.