Dokumentace / Historie

Historické: diplomová práce (2026)

Genetické programování při plánování baseballové sezóny. Problém proveditelnosti a optimalizace. Diplomová práce z počítačového inženýrství, ITAM. Školitel: Dr. Andrés Gómez de Silva Garza. Schváleno 23. července 2026.

Problém

MLB plánuje 2 430 zápasů pro 30 týmů během přibližně 180 dnů. Každý tým cestuje mezi městy a vzdálenost se výrazně liší tým od týmu. V roce 2016 Seattle urazil 76 683 km a Chicago Cubs 39 015 km.

Nalezení jízdního rozpisu s nejnižší celkovou vzdáleností je známé jako problém turnajové dopravy (PTT). Je to problém NP-těžký: počet možných rozpisů roste tak rychle, že je nelze všechny zkontrolovat.

Metoda

Genetické programování (PG), navržené Johnem Kozou v roce 1992, napodobuje evoluci. Vytváří populaci řešení, bere ta nejlepší a kombinuje je a upravuje, aby vznikla nová generace.

Reprezentace: Každý kalendář je strom. Jeho uzly jsou operace jako crear_juego (datum, domácí tým, hostující tým) a obtener_calendario, které spojují dva seznamy zápasů.
Životaschopnost (C1): Každý tým musí odehrát přesně ten počet zápasů, kolik turnaj vyžaduje. Hodnota 0 znamená, že rozpis je platný.
Vzdálenost (C2): součet přestupů, vypočítaný pomocí Haversinova vzorce na souřadnicích každého stadionu.
Software: tři moduly (plánovač, kalkulačka a genetický program) s knihovnou DEAP, oddělené od webové aplikace v Django.

Výsledky

Zkuste 30 týmů, 163 zápasů na tým, série na 5 zápasů a 20 generací.

Srovnání náhodného vyhledávání a genetického programování
Metoda	Pravděpodobně. překročení	Pravděpodobně. mutace	Proveditelnost (C1)	Celková vzdálenost (C2)	Čas
Náhodné vyhledávání	0.0	0.0	0 (platná)	2,663,470.70 km Kratší vzdálenost	200.25 s
Genetické programování	0.8	0.2	0 (platná)	3,182,738.33 km	3,337.81 s

Hlavní zjištění

Genetické programování nepřekonalo náhodné vyhledávání. Ukázalo vzdálenost o 19,5 % větší a trvalo téměř 17krát déle. Nejlepší kalendář vždy pocházel z počáteční generace, která je náhodná.

Práce identifikovala tyto příčiny:

Generické operátory křížení a mutací mění uzly, aniž by znaly problém. Téměř vždy produkují neplatné kalendáře.
Funkce způsobilosti klade mnohem větší váhu životaschopnosti než vzdálenosti. Neplatné dítě vždy prohrává s platným rodičem.
Algoritmus brzy konvergoval k lokálnímu optimumu a ponechal pouze počáteční řešení.

Negativní výsledek je také výsledkem. Ukazuje, že reprezentace a operátory jsou stejně důležité jako algoritmus.

Budoucí práce

Práce navrhovala kontextové operátory: místo náhodné změny uzlů vyměňujte celé řady nebo bloky, které udržují kalendář platný. Zmínil také kvantové výpočty pro zkoumání mnoha konfigurací najednou.

Podívejte se, co bylo uděláno po diplomové práci

Časová osa

Květen 2026 · Předoficiální verze diplomové práce.
23. července 2026 · Obrana v Mexico City. Diplomová práce schválena.

Materiály a citace

Diplomová dokumentace, předoficiální verze (PDF, 4.8 MB, ve španělštině)
Prezentace obhajoby (PDF, 2.9 MB, ve španělštině)

Citace ve formátu 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.