Dokumentacioni / Historia

Historike: teza (2026)

Programimi gjenetik në planifikimin e sezonit të bejsbollit. Problemi i fizibilitetit dhe optimizimit. Teza e Inxhinierisë Kompjuterike, ITAM. Këshilltar: Dr. Andrés Gómez de Silva Garza. Miratuar më 23 korrik 2026.

Problemi

MLB planifikon 2,430 ndeshje për 30 skuadra në rreth 180 ditë. Çdo skuadër udhëton midis qyteteve, dhe distanca ndryshon shumë nga skuadra në skuadër. Në vitin 2016, Seattle udhëtoi 76,683 km, dhe Chicago Cubs udhëtuan 39,015 km.

Gjetja e orarit me distancën më të ulët totale njihet si Problemi i Transportit të Turneut (PTT). Është një problem NP-vështirë: numri i orareve të mundshme rritet aq shpejt sa nuk mund t'i kontrollosh të gjitha.

Metoda

Programimi gjenetik (PG), i propozuar nga John Koza në vitin 1992, imiton evolucionin. Ai krijon një popullatë zgjidhjesh, merr më të mirat dhe i kombinon e modifikon për të formuar një brez të ri.

Përfaqësimi: Çdo kalendar është një pemë. Nyjet e tij janë operacione të tilla si crear_juego (data, ekipi vendas, ekipi mysafir) dhe obtener_calendario, që bashkon dy lista lojërash.
Vlefshmëria (C1): Çdo ekip duhet të luajë saktësisht numrin e ndeshjeve që kërkon turneu. Një vlerë 0 do të thotë që orari është i vlefshëm.
Distanca (C2): shuma e transferimeve, e llogaritur me formulën e haversinës në koordinatat e çdo stadiumi.
Softueri: tre module (planifikues, kalkulator dhe program gjenetik) me bibliotekën DEAP, të ndara nga një aplikacion web në Django.

Rezultatet

Provo 30 ekipe, 163 ndeshje për ekip, seri me 5 ndeshje dhe 20 gjenerata.

Krahasimi i Kërkimit të Rastësishëm dhe Programimit Gjenetik
Metoda	Prob. të kalimit	Proba. e mutacionit	Fizibiliteti (C1)	Distanca totale (C2)	Koha
Kërkimi i rastësishëm	0.0	0.0	0 (i vlefshëm)	2,663,470.70 km Distanca më e shkurtër	200.25 s
Programimi gjenetik	0.8	0.2	0 (i vlefshëm)	3,182,738.33 km	3,337.81 s

Gjetja kryesore

Programimi gjenetik nuk performoi më mirë se kërkimi i rastësishëm. Ai dha një distancë 19.5% më të madhe dhe mori pothuajse 17 herë më shumë kohë. Kalendari më i mirë gjithmonë vinte nga gjenerata fillestare, e cila është e rastësishme.

Teza identifikoi këto shkaqe:

Operatorët e përgjithshëm të kryqëzimit dhe mutacionit ndryshojnë nyjet pa e ditur problemin. Ata pothuajse gjithmonë prodhojnë kalendarë të pavlefshëm.
Funksioni i përshtatshmërisë i jep shumë më tepër rëndësi qëndrueshmërisë sesa distancës. Një fëmijë i paaftë gjithmonë humbet ndaj një prindi të vlefshëm.
Algoritmi shpejt konvergoi në një optimum lokal dhe ruajti vetëm zgjidhjet fillestare.

Një rezultat negativ është gjithashtu rezultat. Tregon se përfaqësimi dhe operatorët kanë po aq rëndësi sa algoritmi.

Puna e ardhshme

Teza propozonte operatorë kontekstualë: në vend që të ndryshohen nyjet në mënyrë të rastësishme, ndërrohen seri ose blloqe të tëra që mbajnë kalendarin të vlefshëm. Ai gjithashtu përmendi llogaritjen kuantike për të eksploruar shumë konfigurime njëkohësisht.

Shiko çfarë u bë pas tezës

Kronologjia

Maj 2026 · Versioni parazyrtar i dokumentit të tezës.
23 Korrik 2026 · Mbrojtja në Mexico City. Teza u miratua.

Materialet dhe citimi

Dokumenti i tezës, versioni parazyrtar (PDF, 4.8 MB, në spanjisht)
Prezantimi i mbrojtjes (PDF, 2.9 MB, në spanjisht)

Citim në formatin 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.