Dokumentation / Geschichte
Historisch: die Dissertation (2026)
Genetische Programmierung in der Planung der Baseball-Saison. Machbarkeits- und Optimierungsproblem. Abschlussarbeit in Computertechnik, ITAM. Betreuer: Dr. Andrés Gómez de Silva Garza. Genehmigt am 23. Juli 2026.
Das Problem
Die MLB plant 2.430 Spiele für 30 Teams in etwa 180 Tagen an. Jedes Team reist zwischen den Städten, und die Entfernung variiert stark von Team zu Team. Im Jahr 2016 legte Seattle 76.683 km zurück, die Chicago Cubs 39.015 km.
Den Zeitplan mit der niedrigsten Gesamtdistanz zu finden, nennt man das Turniertransportproblem (PTT). Das ist ein NP-schweres Problem: Die Anzahl der möglichen Zeitpläne wächst so schnell, dass man nicht alle überprüfen kann.
Die Methode
Die genetische Programmierung (PG), vorgeschlagen von John Koza im Jahr 1992, ahmt die Evolution nach. Sie erzeugt eine Population von Lösungen, nimmt die besten und kombiniert und modifiziert sie, um eine neue Generation zu bilden.
- Darstellung: Jeder Kalender ist ein Baum. Seine Knoten sind Operationen wie
crear_juego(Datum, Heimmannschaft, Auswärtsmannschaft) undobtener_calendario, die zwei Spiellisten zusammenschließt. - Spielbarkeit (C1): Jedes Team muss genau die Anzahl der Spiele spielen, die das Turnier verlangt. Ein Wert von 0 bedeutet, dass der Spielplan gültig ist.
- Entfernung (C2): die Summe der Transfers, berechnet mit der Haversine-Formel auf den Koordinaten jedes Stadions.
- Software: drei Module (Planer, Taschenrechner und genetisches Programm) mit der DEAP-Bibliothek, getrennt von einer Webanwendung in Django.
Die Ergebnisse
Versuche 30 Teams, 163 Spiele pro Team, 5-Spiele-Serien und 20 Generationen.
| Methode | Wahrscheinlich. des Überquerens | Wahrscheinlich. von Mutation | Machbarkeit (C1) | Gesamtdistanz (C2) | Zeit |
|---|---|---|---|---|---|
| Zufallssuche | 0.0 | 0.0 | 0 (gültig) | 2,663,470.70 km Kürzere Entfernung | 200.25 s |
| Genetische Programmierung | 0.8 | 0.2 | 0 (gültig) | 3,182,738.33 km | 3,337.81 s |
Der Hauptbefund
Die genetische Programmierung übertraf die zufällige Suche nicht. Sie gab eine um 19,5 % größere Entfernung und dauerte fast 17-mal länger. Der beste Kalender kam immer aus der ersten Generation, die zufällig ist.
Die Dissertation identifizierte folgende Ursachen:
- Generische Crossover- und Mutationsoperatoren wechseln die Knoten, ohne das Problem zu kennen. Sie erzeugen fast immer ungültige Kalender.
- Die Fitnessfunktion legt viel mehr Wert auf die Lebensfähigkeit als auf Distanz. Ein ungültiges Kind verliert immer gegen einen gültigen Elternteil.
- Der Algorithmus konvergierte bald auf ein lokales Optimum und behielt nur die Anfangslösungen.
Ein negatives Ergebnis ist ebenfalls ein Ergebnis. Es zeigt, dass die Darstellung und die Operatoren genauso wichtig sind wie der Algorithmus.
Zukünftige Tätigkeiten
Die Dissertation schlug kontextuelle Operatoren vor: Anstatt die Knoten zufällig zu wechseln, tauschen Sie ganze Reihen oder Blöcke, die den Kalender gültig halten. Er erwähnte außerdem das Quantencomputing, um viele Konfigurationen gleichzeitig zu erforschen.
Zeitstrahl
- · Vor-offizielle Version des Dissertationsdokuments.
- · Verteidigung in Mexiko-Stadt. Abschlussarbeit genehmigt.
Materialien und Zitate
- Dissertationsdokument, voroffizielle Version (PDF, 4.8 MB, auf Spanisch)
- Darstellung der Verteidigung (PDF, 2.9 MB, auf Spanisch)
Zitat im APA-Format:
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.