Dokumentacija / Povijest

Povijesno: teza (2026)

Genetsko programiranje u planiranju bejzbol sezone. Problem izvedivosti i optimizacije. Diplomski rad iz računalnog inženjerstva, ITAM. Mentor: dr. Andrés Gómez de Silva Garza. Odobreno 23. srpnja 2026.

Problem

MLB zakazuje 2.430 utakmica za 30 momčadi u otprilike 180 dana. Svaka momčad putuje između gradova, a udaljenost se znatno razlikuje od momčadi do momčadi. Godine 2016. Seattle je prešao 76.683 km, a Chicago Cubs 39.015 km.

Pronalaženje rasporeda s najnižom ukupnom udaljenošću poznato je kao problem turnirskog prijevoza (PTT). To je NP-težak problem: broj mogućih rasporeda raste tako brzo da ih ne možete sve provjeriti.

Metoda

Genetsko programiranje (PG), koje je predložio John Koza 1992. godine, oponaša evoluciju. Stvara populaciju rješenja, uzima najbolje i kombinira ih te modificira kako bi formirao novu generaciju.

Reprezentacija: Svaki kalendar je stablo. Njegovi čvorovi su operacije poput crear_juego (datum, domaća momčad, gostujuća momčad) i obtener_calendario, koje spajaju dva popisa utakmica.
Održivost (C1): Svaka momčad mora odigrati točno onoliko utakmica koliko turnir zahtijeva. Vrijednost 0 znači da je raspored valjan.
Udaljenost (C2): zbroj prijenosa, izračunat Haversinovom formulom na koordinatama svakog stadiona.
Softver: tri modula (planer, kalkulator i genetski program) s DEAP bibliotekom, odvojeni od web aplikacije u Djangu.

Rezultati

Probajte 30 timova, 163 utakmice po momčadi, serije od 5 utakmica i 20 generacija.

Usporedba slučajnog pretraživanja i genetskog programiranja
Metoda	Vjerojatno. prijelaza	Vjerojatno. mutacije	Izvedivost (C1)	Ukupna udaljenost (C2)	Vrijeme
Nasumično pretraživanje	0.0	0.0	0 (valjano)	2,663,470.70 km Kraća udaljenost	200.25 s
Genetsko programiranje	0.8	0.2	0 (valjano)	3,182,738.33 km	3,337.81 s

Glavno otkriće

Genetsko programiranje nije nadmašilo nasumično pretraživanje. Dalo je 19,5% veću udaljenost i trajalo gotovo 17 puta duže. Najbolji kalendar uvijek je dolazio iz početne generacije, koja je nasumična.

Teza je identificirala sljedeće uzroke:

Generički operatori preklapanja i mutacija mijenjaju čvorove bez da znaju o čemu je problem. Gotovo uvijek proizvode nevažeće kalendare.
Funkcija prilagodbe daje mnogo veću važnost održivosti nego udaljenosti. Neispravno dijete uvijek gubi od valjanog roditelja.
Algoritam se ubrzo približio lokalnom optimumu i zadržao samo početna rješenja.

Negativan rezultat je također rezultat. Pokazuje da su reprezentacija i operatori jednako važni kao i algoritam.

Budući rad

Teza je predložila kontekstualne operatore: umjesto nasumične promjene čvorova, zamijenite cijele serije ili blokove koji održavaju kalendar valjanim. Također je spomenuo kvantno računarstvo za istraživanje više konfiguracija odjednom.

Pogledajte što je učinjeno nakon diplomskog rada

Vremenska crta

Svibanj 2026. · Službena verzija diplomskog rada.
23. srpnja 2026. · Obrana u Mexico Cityju. Diplomski rad odobren.

Materijali i citati

Diplomski rad, predslužbena verzija (PDF, 4.8 MB, na španjolskom)
Izlaganje obrane (PDF, 2.9 MB, na španjolskom)

Citiranje u APA formatu:

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.