Dokumentáció / Történelem
Történelmi: a tézis (2026)
Genetikai programozás a baseball szezontervezésben. Megvalósíthatósági és optimalizálási probléma. Számítógép-mérnöki szakdolgozat, ITAM. Témavezető: Dr. Andrés Gómez de Silva Garza. 2026. július 23-án hagyták jóvá.
A probléma
Az MLB körülbelül 180 nap alatt 2 430 mérkőzést tervez 30 csapatnak. Minden csapat városok között utazik, és a távolság csapatonként jelentősen eltér. 2016-ban Seattle 76 683 km-t tett meg, míg a Chicago Cubs 39 015 km-t.
A legkisebb össztávolságú menetrend megtalálását Tournament Transportation Problem-nek (PTT) nevezik. Ez egy NP-nehéz probléma: a lehetséges menetrendek száma olyan gyorsan nő, hogy nem tudod mindet ellenőrizni.
A módszer
A genetikai programozás (PG), amelyet John Koza javasolt 1992-ben, az evolúciót utánozza. Megoldások populációját hozza létre, a legjobbakat választja, majd egyesíti és módosítja őket, hogy új generációt alkosson.
- Ábrázolás: Minden naptár egy fa. Csomópontjai olyan műveletek, mint
crear_juego(dátum, hazai csapat, idegen csapat) ésobtener_calendario, amelyek két meccslistához csatlakoznak. - Életképesség (C1): Minden csapatnak pontosan annyi mérkőzést kell játszania, amennyit a torna előír. 0 érték azt jelenti, hogy a menetrend érvényes.
- Távolság (C2): az áthelyezések összege, amelyet a stadionok koordinátáiról alkotott Haversine képletével számítanak ki.
- Szoftver: három modul (tervező, számoló és genetikai program) a DEAP könyvtárral, külön egy webalkalmazástól Django-ban.
Az eredmények
Próbálj ki 30 csapatot, 163 meccset csapatonként, 5 meccses sorozatot és 20 generációt.
| Módszer | Valószínűség. átkelés | Valószínűség. a mutáció | Megvalósíthatóság (C1) | Teljes távolság (C2) | Idő |
|---|---|---|---|---|---|
| Véletlenszerű keresés | 0.0 | 0.0 | 0 (érvényes) | 2,663,470.70 km Rövidebb távolság | 200.25 s |
| Genetikai programozás | 0.8 | 0.2 | 0 (érvényes) | 3,182,738.33 km | 3,337.81 s |
A fő felfedezés
A genetikai programozás nem teljesítette felül a véletlenszerű keresést. 19,5%-kal nagyobb távolságot adott, és majdnem 17-szer tovább tartott. A legjobb naptár mindig az első generációból származik, ami véletlenszerű.
A szakdolgozat ezeket az okokat azonosította:
- A generikus crossover és mutációs operátorok anélkül, hogy tudnák volna a problémát, cserélnek csomópontokat. Szinte mindig érvénytelen naptárakat eredményeznek.
- A alkalmasságfüggvény sokkal nagyobb súlyt ad az életképességnek, mint a távolságnak. Egy betegtelen gyermek mindig veszít egy érvényes szülővel szemben.
- Az algoritmus hamarosan egy helyi optimumhoz konvergálódott, és csak az eredeti megoldásokat tartotta meg.
A negatív eredmény is eredmény. Ez azt mutatja, hogy a reprezentáció és az operátorok ugyanolyan fontosak, mint az algoritmus.
Jövőbeli munkák
A tézis kontextuális operátorokat javasolt: ahelyett, hogy véletlenszerűen cserélnénk csomópontokat, cserélj egy egész sorozatot vagy blokkot, amelyek fenntartják a naptárt. Megemlítette a kvantumszámítást is, hogy egyszerre sok konfigurációt lehet felfedezni.
Idővonal
- · A szakdolgozat hivatalos előzetes változata.
- · Védelem Mexikóvárosban. A szakdolgozat jóváhagyva.
Anyagok és hivatkozások
- Szakdolgozat, prehivatalos változat (PDF, 4.8 MB, spanyol nyelven)
- A védelem bemutatása (PDF, 2.9 MB, spanyol nyelven)
Hivatkozás APA formátumban:
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.