Dokumentacija / Zgodovina

Zgodovinsko: teza (2026)

Genetsko programiranje pri načrtovanju baseball sezone. Problem izvedljivosti in optimizacije. Diplomska naloga iz računalniškega inženirstva, ITAM. Svetovalec: dr. Andrés Gómez de Silva Garza. Odobreno 23. julija 2026.

Problem

MLB načrtuje 2.430 tekem za 30 ekip v približno 180 dneh. Vsaka ekipa potuje med mesti, razdalja pa se močno razlikuje od ekipe do ekipe. Leta 2016 je Seattle prepotoval 76.683 km, Chicago Cubs pa 39.015 km.

Iskanje urnika z najnižjo skupno razdaljo je znano kot problem turnirskega prevoza (PTT). To je NP-težak problem: število možnih urnikov narašča tako hitro, da jih ne moreš preveriti vseh.

Metoda

Genetsko programiranje (PG), ki ga je leta 1992 predlagal John Koza, posnema evolucijo. Ustvari populacijo rešitev, vzame najboljše in jih združi ter spremeni v novo generacijo.

Predstavitev: Vsak koledar je drevo. Njegova vozlišča so operacije, kot crear_juego so (datum, domača ekipa, gostujoča ekipa) in obtener_calendario, ki združuje dva seznama tekem.
Izvedljivost (C1): Vsaka ekipa mora odigrati natanko toliko tekem, kot zahteva turnir. Vrednost 0 pomeni, da je razpored veljaven.
Razdalja (C2): vsota prestopov, izračunana s Haversinovo formulo na koordinatah vsakega stadiona.
Programska oprema: trije moduli (planner, kalkulator in genetski program) z DEAP knjižnico, ločeni od spletne aplikacije v Django.

Rezultati

Preizkusite 30 ekip, 163 tekem na ekipo, serije s 5 tekmami in 20 generacijami.

Primerjava naključnega iskanja in genetskega programiranja
Metoda	Verjetno. prečkanja	Verjetno. mutacije	Izvedljivost (C1)	Skupna razdalja (C2)	Čas
Naključno iskanje	0.0	0.0	0 (veljavno)	2,663,470.70 km Krajša razdalja	200.25 s
Genetsko programiranje	0.8	0.2	0 (veljavno)	3,182,738.33 km	3,337.81 s

Glavna ugotovitev

Genetsko programiranje ni preseglo naključnega iskanja. Dalo je 19,5 % večjo razdaljo in trajalo skoraj 17-krat dlje. Najboljši koledar je vedno prišel iz začetne generacije, ki je naključna.

Doktorska naloga je opredelila naslednje vzroke:

Generični operatorji prepletov in mutacij menjajo vozlišča, ne da bi poznali problem. Skoraj vedno ustvarijo neveljavne koledarje.
Funkcija prilagodljivosti daje veliko večjo težo izvedljivosti kot razdalji. Invalidni otrok vedno izgubi proti velitemu staršu.
Algoritem se je kmalu približal lokalnemu optumu in ohranil le začetne rešitve.

Negativen rezultat je prav tako rezultat. Pokaže, da sta predstavitev in operatorji prav tako pomembna kot algoritem.

Prihodnje delo

Doktorska naloga je predlagala kontekstualne operatorje: namesto naključne menjave vozlišč zamenjajte celotne serije ali bloke, ki ohranjajo koledar veljaven. Omenil je tudi kvantno računalništvo za raziskovanje več konfiguracij hkrati.

Poglejte, kaj je bilo narejeno po diplomski nalogi

Časovnica

Maj 2026 · Preduradna različica diplomskega dokumenta.
23. julij 2026 · Obramba v Mexico Cityju. Diplomska naloga odobrena.

Gradivo in navedbe

Diplomski dokument, uradna različica (PDF, 4.8 MB, v španščini)
Predstavitev obrambe (PDF, 2.9 MB, v španščini)

Navedba v 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.