Dokumentácia / História

Historické: diplomová práca (2026)

Genetické programovanie pri plánovaní baseballovej sezóny. Problém uskutočniteľnosti a optimalizácie. Dizertačná práca z počítačového inžinierstva, ITAM. Poradca: Dr. Andrés Gómez de Silva Garza. Schválené 23. júla 2026.

Problém

MLB plánuje 2 430 zápasov pre 30 tímov za približne 180 dní. Každý tím cestuje medzi mestami a vzdialenosť sa výrazne líši od tímu k tímu. V roku 2016 Seattle precestoval 76 683 km a Chicago Cubs 39 015 km.

Nájdenie rozpisu s najnižšou celkovou vzdialenosťou je známe ako problém turnajovej dopravy (PTT). Je to NP-ťažký problém: počet možných rozpisov rastie tak rýchlo, že ich nemôžete všetky skontrolovať.

Metóda

Genetické programovanie (PG), navrhnuté Johnom Kozom v roku 1992, napodobňuje evolúciu. Vytvára populáciu riešení, berie tie najlepšie a kombinuje ich a upravuje, aby vytvoril novú generáciu.

Reprezentácia: Každý kalendár je strom. Jeho uzly sú operácie ako crear_juego (dátum, domáci tím, hosťujúci tím) a obtener_calendario, ktoré spájajú dva zoznamy zápasov.
Životaschopnosť (C1): Každý tím musí odohrať presne toľko zápasov, koľko turnaj vyžaduje. Hodnota 0 znamená, že rozpis je platný.
Vzdialenosť (C2): súčet prestupov, vypočítaný pomocou Haversinovej formuly na súradniciach každého štadióna.
Softvér: tri moduly (plánovač, kalkulačka a genetický program) s knižnicou DEAP, oddelené od webovej aplikácie v Django.

Výsledky

Skúste 30 tímov, 163 zápasov na tím, 5-zápasové série a 20 generácií.

Porovnanie náhodného vyhľadávania a genetického programovania
Metóda	Pravdepodobne. prechodu	Pravdepodobne. mutácie	Uskutočniteľnosť (C1)	Celková vzdialenosť (C2)	Čas
Náhodné vyhľadávanie	0.0	0.0	0 (platné)	2,663,470.70 km Kratšia vzdialenosť	200.25 s
Genetické programovanie	0.8	0.2	0 (platné)	3,182,738.33 km	3,337.81 s

Hlavné zistenie

Genetické programovanie neprekonalo náhodné vyhľadávanie. Ukázalo vzdialenosť o 19,5 % väčšiu a trvalo takmer 17-krát dlhšie. Najlepší kalendár vždy pochádzal z počiatočnej generácie, ktorá je náhodná.

Dizertačná práca identifikovala tieto príčiny:

Generické crossover a mutačné operátory menia uzly bez toho, aby poznali problém. Takmer vždy produkujú neplatné kalendáre.
Funkcia zdatnosti kladie oveľa väčšiu váhu životaschopnosti než vzdialenosti. Neplatné dieťa vždy prehráva s platným rodičom.
Algoritmus sa čoskoro priblížil k lokálnemu optimumu a ponechal si len počiatočné riešenia.

Negatívny výsledok je tiež výsledkom. Ukazuje, že reprezentácia a operátory sú rovnako dôležité ako algoritmus.

Budúca práca

Dizertačná práca navrhovala kontextové operátory: namiesto náhodnej zmeny uzlov vymieňajte celé série alebo bloky, ktoré udržiavajú kalendár platný. Spomenul tiež kvantové počítanie na skúmanie viacerých konfigurácií naraz.

Pozrite sa, čo sa robilo po diplomovej práci

Časová os

Máj 2026 · Predoficiálna verzia diplomovej práce.
23. júl 2026 · Obrana v Mexico City. Diplomová práca schválená.

Materiály a citácia

Diplomová práca, predoficiálna verzia (PDF, 4.8 MB, v španielčine)
Prezentácia obhajoby (PDF, 2.9 MB, v španielčine)

Citácia vo formáte 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.