Documentatie / Geschiedenis
Historisch: de thesis (2026)
Genetische programmering in het plannen van honkbalseizoenen. Haalbaarheids- en optimalisatieprobleem. Scriptie Computertechniek, ITAM. Adviseur: Dr. Andrés Gómez de Silva Garza. Goedgekeurd op 23 juli 2026.
Het probleem
De MLB plant 2.430 wedstrijden voor 30 teams in ongeveer 180 dagen. Elk team reist tussen steden, en de afstand verschilt sterk van team tot team. In 2016 legde Seattle 76.683 km af en de Chicago Cubs 39.015 km.
Het vinden van het schema met de laagste totale afstand staat bekend als het Tournament Transportation Problem (PTT). Het is een NP-moeilijk probleem: het aantal mogelijke schema's groeit zo snel dat je ze niet allemaal kunt controleren.
De methode
Genetisch programmeren (PG), voorgesteld door John Koza in 1992, bootst evolutie na. Het creëert een populatie van oplossingen, neemt de beste oplossingen en combineert en wijzigt ze om een nieuwe generatie te vormen.
- Representatie: Elke kalender is een boom. De knooppunten zijn operaties zoals
crear_juego(datum, thuisteam, uitteam) enobtener_calendario, die twee lijsten van wedstrijden samenvoegen. - Levensvatbaarheid (C1): Elk team moet precies het aantal wedstrijden spelen dat het toernooi vereist. Een waarde van 0 betekent dat het schema geldig is.
- Afstand (C2): de som van de transfers, berekend met de Haversine-formule op de coördinaten van elk stadion.
- Software: drie modules (planner, rekenmachine en genetisch programma) met de DEAP-bibliotheek, los van een webapplicatie in Django.
De resultaten
Probeer 30 teams, 163 wedstrijden per team, 5-wedstrijden series en 20 generaties.
| Methode | Waarschijnlijk. van het oversteken | Waarschijnlijk. van mutatie | Haalbaarheid (C1) | Totale afstand (C2) | Tijd |
|---|---|---|---|---|---|
| Willekeurige zoekopdracht | 0.0 | 0.0 | 0 (geldig) | 2,663,470.70 km Kortere afstand | 200.25 s |
| Genetische programmering | 0.8 | 0.2 | 0 (geldig) | 3,182,738.33 km | 3,337.81 s |
De belangrijkste bevinding
Genetische programmering presteerde niet beter dan willekeurige zoekopdrachten. Het gaf een 19,5% grotere afstand en duurde bijna 17 keer langer. De beste kalender kwam altijd van de eerste generatie, die willekeurig is.
De scriptie identificeerde deze oorzaken:
- Generieke crossover- en mutatie-operatoren veranderen knooppunten zonder het probleem te kennen. Ze produceren bijna altijd ongeldige kalenders.
- De fitnessfunctie hecht veel meer waarde aan levensvatbaarheid dan aan afstand. Een ongeldig kind verliest altijd van een geldige ouder.
- Het algoritme convergeerde al snel op een lokaal optimum en behield alleen de beginoplossingen.
Een negatief resultaat is ook een resultaat. Het laat zien dat de representatie en operatoren net zo belangrijk zijn als het algoritme.
Toekomstig werk
De scriptie stelde contextuele operatoren voor: in plaats van willekeurig van knooppunt te wisselen, wissel hele reeksen of blokken om die de kalender geldig houden. Hij noemde ook quantum computing om vele configuraties tegelijk te verkennen.
Tijdlijn
- · Pre-officiële versie van het scriptiedocument.
- · Verweer in Mexico-Stad. Scriptie goedgekeurd.
Materialen en bronvermelding
- Scriptiedocument, pre-officiële versie (PDF, 4.8 MB, in het Spaans)
- Presentatie van de verdediging (PDF, 2.9 MB, in het Spaans)
Citaat in APA-formaat:
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.