Dokumentaatio / Historia
Historiallinen: väitöskirja (2026)
Geneettinen ohjelmointi baseball-kauden suunnittelussa. Toteutettavuus- ja optimointiongelma. Tietokonetekniikan opinnäytetyö, ITAM. Ohjaaja: Dr. Andrés Gómez de Silva Garza. Hyväksytty 23. heinäkuuta 2026.
Ongelma
MLB aikatauluttaa 2 430 ottelua 30 joukkueelle noin 180 päivän aikana. Jokainen joukkue matkustaa kaupunkien välillä, ja etäisyydet vaihtelevat suuresti joukkueittain. Vuonna 2016 Seattle matkusti 76 683 km ja Chicago Cubs 39 015 km.
Aikataulun löytämistä, jossa on vähin kokonaismatka, tunnetaan nimellä Tournament Transportation Problem (PTT). Se on NP-vaikea ongelma: mahdollisten aikataulujen määrä kasvaa niin nopeasti, ettei kaikkia voi tarkistaa.
Menetelmä
John Kozan vuonna 1992 ehdottama geneettinen ohjelmointi (PG) jäljittelee evoluutiota. Se luo ratkaisupopulaation, ottaa parhaat ja yhdistää sekä muokkaa niitä muodostaakseen uuden sukupolven.
- Esitys: Jokainen kalenteri on puu. Sen solmut ovat operaatioita kuten
crear_juego(päivämäärä, kotijoukkue, vierasjoukkue) jaobtener_calendario, jotka yhdistävät kaksi pelilistaa. - Kannattavuus (C1): Jokaisen joukkueen on pelattava täsmälleen sen määrän pelejä, joita turnaus vaatii. Arvo 0 tarkoittaa, että aikataulu on voimassa.
- Etäisyys (C2): siirtojen summa, joka lasketaan Haverinen kaavalla kunkin stadionin koordinaatista.
- Ohjelmisto: kolme moduulia (suunnittelija, laskin ja geneettinen ohjelma) DEAP-kirjastolla, erillään Djangon verkkosovelluksesta.
Tulokset
Kokeile 30 joukkuetta, 163 ottelua per joukkue, 5 ottelun sarja ja 20 sukupolvea.
| Menetelmä | Todennäköisesti. ylityksestä | Todennäköisesti. mutaation | Toteutettavuus (C1) | Kokonaisetäisyys (C2) | Aika |
|---|---|---|---|---|---|
| Satunnaishaku | 0.0 | 0.0 | 0 (pätevä) | 2,663,470.70 km Lyhyempi matka | 200.25 s |
| Geneettinen ohjelmointi | 0.8 | 0.2 | 0 (pätevä) | 3,182,738.33 km | 3,337.81 s |
Pääasiallinen löytö
Geneettinen ohjelmointi ei ylittänyt satunnaishakua. Se antoi 19,5 % pidemmän matkan ja kesti lähes 17 kertaa kauemmin. Paras kalenteri tuli aina alkuperäisestä sukupolvesta, joka on satunnainen.
Väitöskirjassa tunnistettiin seuraavat syyt:
- Geneeriset crossover- ja mutaatiooperaattorit vaihtavat solmuja tietämättä ongelmaa. Ne tuottavat lähes aina virheellisiä kalentereita.
- Soveltuvuusfunktio antaa paljon enemmän painoarvoa elinkelpoisuudelle kuin etäisyydelle. Virheellinen lapsi häviää aina pätevälle vanhemmalle.
- Algoritmi konvergoi pian paikalliseen optimaaliin ja säilytti vain alkuperäiset ratkaisut.
Negatiivinen tulos on myös tulos. Se osoittaa, että esitys ja operaattorit ovat yhtä tärkeitä kuin algoritmi.
Tuleva työ
Väitöskirja ehdotti kontekstuaalisia operaattoreita: solmujen satunnaisen vaihtamisen sijaan vaihdetaan kokonaisia sarjoja tai lohkoja, jotka pitävät kalenterin voimassa. Hän mainitsi myös kvanttilaskennan tutkiakseen monia konfiguraatioita samanaikaisesti.
Aikajana
- · Esivirallinen versio väitöskirjasta.
- · Puolustus Mexico Cityssä. Väitöskirja hyväksytty.
Materiaalit ja viittaukset
- Väitöskirja, esivirallinen versio (PDF, 4.8 MB, espanjaksi)
- Puolustuksen esittäminen (PDF, 2.9 MB, espanjaksi)
Viittaus APA-muodossa:
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.