Dokumentasyon / Kasaysayan

Makasaysayan: ang tesis (2026)

Genetic programming sa pagpaplano ng baseball season. Problema sa posibilidad at optimisasyon. Tesis sa Computer Engineering, ITAM. Tagapayo: Dr. Andrés Gómez de Silva Garza. Inaprubahan noong Hulyo 23, 2026.

Ang problema

Nag-iskedyul ang MLB ng 2,430 laro para sa 30 koponan sa loob ng humigit-kumulang 180 araw. Bawat koponan ay naglalakbay sa pagitan ng mga lungsod, at malaki ang pagkakaiba-iba ng distansya mula koponan sa koponan. Noong 2016, naglakbay ang Seattle ng 76,683 km, at ang Chicago Cubs ay naglakbay ng 39,015 km.

Ang paghahanap ng iskedyul na may pinakamababang kabuuang distansya ay tinatawag na Tournament Transportation Problem (PTT). Mahirap na problema ito para sa NP: napakabilis ng pagdami ng posibleng iskedyul kaya hindi mo na pwedeng tingnan lahat.

Ang pamamaraan

Ang genetic programming (PG), na iminungkahi ni John Koza noong 1992, ay ginagaya ang ebolusyon. Lumilikha ito ng populasyon ng mga solusyon, kinukuha ang pinakamagagaling, at pinagsasama at binabago ang mga ito upang bumuo ng bagong henerasyon.

Representasyon: Bawat kalendaryo ay isang puno. Ang mga node nito ay mga operasyon tulad ng crear_juego (petsa, home team, away team) at obtener_calendario, na pinagsasama ang dalawang listahan ng mga laro.
Viability (C1): Bawat koponan ay kailangang maglaro ng eksaktong bilang ng mga laro na hinihingi ng torneo. Ang halagang 0 ay nangangahulugang valid ang iskedyul.
Distansya (C2): ang kabuuan ng mga transfer, na kinakalkula gamit ang formula ni haversine sa mga coordinate ng bawat stadium.
Software: tatlong module (planner, calculator at genetic program) na may DEAP library, hiwalay sa isang web application sa Django.

Ang mga resulta

Subukan ang 30 koponan, 163 laro kada koponan, 5-laro na serye, at 20 henerasyon.

Paghahambing ng Random Search at Genetic Programming
Pamamaraan	Siguro. ng pagtawid	Prob. ng mutation	Posibilidad (C1)	Kabuuang distansya (C2)	Oras
Random na paghahanap	0.0	0.0	0 (balido)	2,663,470.70 km Mas maikling distansya	200.25 s
Genetic programming	0.8	0.2	0 (balido)	3,182,738.33 km	3,337.81 s

Ang pangunahing natuklasan

Hindi nalampasan ng genetic programming ang random search. Nagbibigay ito ng 19.5% mas mahabang distansya at halos 17 beses na mas matagal. Ang pinakamahusay na kalendaryo ay palaging nagmumula sa unang henerasyon, na random.

Tinukoy ng tesis ang mga ganitong sanhi:

Ang mga generic na operator ng crossover at mutation ay nagpapalit ng node nang hindi alam ang problema. Halos palaging gumagawa sila ng hindi wastong kalendaryo.
Ang fitness function ay nagbibigay ng mas malaking timbang sa viability kaysa sa distansya. Laging natatalo ang isang invalid na bata sa isang valid na magulang.
Agad na nag-converge ang algorithm sa isang lokal na optimum at nanatili lamang ang mga paunang solusyon.

Ang negatibong resulta ay resulta rin. Ipinapakita nito na ang representasyon at mga operator ay kasinghalaga ng algorithm.

Mga susunod na gawain

Iminungkahi ng tesis ang mga contextual operator: sa halip na magpalit ng mga node nang random, palitan ang buong serye o mga bloke na nagpapanatili ng balido sa kalendaryo. Binanggit din niya ang quantum computing upang sabay-sabay na tuklasin ang maraming mga konfigurasyon.

Tingnan kung ano ang ginawa pagkatapos ng thesis

Timeline

Mayo 2026 · Pre-opisyal na bersyon ng thesis document.
Hulyo 23, 2026 · Depensa sa Mexico City. Inaprubahan ang tesis.

Mga materyales at sipi

Dokumento ng tesis, pre-opisyal na bersyon (PDF, 4.8 MB, sa Espanyol)
Presentasyon ng depensa (PDF, 2.9 MB, sa Espanyol)

Sipi sa format na 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.