Dokumentacja / Historia

Historyczne: praca magisterska (2026)

Programowanie genetyczne w planowaniu sezonów baseballowych. Problem wykonalności i optymalizacji. Praca dyplomowa z inżynierii komputerowej, ITAM. Doradca: dr Andrés Gómez de Silva Garza. Zatwierdzone 23 lipca 2026 r.

Problem

MLB planuje 2 430 meczów dla 30 drużyn w ciągu około 180 dni. Każda drużyna podróżuje między miastami, a odległość znacznie różni się w zależności od zespołu. W 2016 roku Seattle przejechał 76 683 km, a Chicago Cubs 39 015 km.

Znalezienie harmonogramu z najniższym całkowitym dystansem znane jest jako Problem Transportu Turniejowego (PTT). To problem NP-trudny: liczba możliwych harmonogramów rośnie tak szybko, że nie da się ich wszystkich sprawdzić.

Metoda

Programowanie genetyczne (PG), zaproponowane przez Johna Kozę w 1992 roku, naśladuje ewolucję. Tworzy populację rozwiązań, bierze najlepsze i łączy je oraz modyfikuje, tworząc nowe pokolenie.

Reprezentacja: Każdy kalendarz to drzewo. Jego węzłami są operacje takie jak crear_juego (data, drużyna gospodarzy, drużyna gości) oraz obtener_calendario, które łączą dwie listy meczów.
Rozgrywność (C1): Każda drużyna musi rozegrać dokładnie tyle meczów, ile przewiduje turniej. Wartość 0 oznacza, że harmonogram jest ważny.
Odległość (C2): suma transferów, obliczana wzorem Haversina na współrzędnych każdego stadionu.
Oprogramowanie: trzy moduły (planer, kalkulator i program genetyczny) z biblioteką DEAP, oddzielne od aplikacji webowej w Django.

Wyniki

Spróbuj 30 drużyn, 163 mecze na drużynę, serie 5-meczowe i 20 generacji.

Porównanie losowego wyszukiwania i programowania genetycznego
Metoda	Prawdopodobnie. przeprawy	Prawdopodobnie. mutacji	Wykonalność (C1)	Całkowity dystans (C2)	Czas
Losowe wyszukiwanie	0.0	0.0	0 (ważne)	2,663,470.70 km Krótszy dystans	200.25 s
Programowanie genetyczne	0.8	0.2	0 (ważne)	3,182,738.33 km	3,337.81 s

Główne odkrycie

Programowanie genetyczne nie przewyższało losowego wyszukiwania. Dawało o 19,5% większą odległość i trwało prawie 17 razy dłużej. Najlepszy kalendarz zawsze pochodził z początkowego pokolenia, które jest losowe.

Praca dyplomowa wskazała następujące przyczyny:

Operatory krzyżowania i mutacji generyczne zmieniają węzły bez znajomości problemu. Prawie zawsze generują nieprawidłowe kalendarze.
Funkcja przystosowania przywiązuje znacznie większą wagę do trwałości niż do odległości. Nieważne dziecko zawsze przegrywa z ważnym rodzicem.
Algorytm szybko zbiegł się do lokalnego optimum i zachowywał jedynie początkowe rozwiązania.

Wynik negatywny jest również wynikiem. Pokazuje, że reprezentacja i operatory mają równie duże znaczenie jak algorytm.

Przyszła działalność

Praca zaproponowała operatory kontekstowe: zamiast losowej zmiany węzłów, zamieniać całe szeregi lub bloki, które utrzymują ważność kalendarza. Wspomniał także o obliczeniach kwantowych do eksploracji wielu konfiguracji jednocześnie.

Zobacz, co zrobiono po pracy dyplomowej

Oś czasu

Maj 2026 · Oficjalna wersja pracy dyplomowej.
23 lipca 2026 · Obrona w Mexico City. Praca dyplomowa zatwierdzona.

Materiały i cytaty

Dokument dyplomowy, wersja przedoficjalna (PDF, 4.8 MB, po hiszpańsku)
Prezentacja obrony (PDF, 2.9 MB, po hiszpańsku)

Cytowanie w formacie 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.