Nyaraka / Hadithi

Kihistoria: thesis (2026)

Programu ya maumbile katika upangaji wa msimu wa besiboli. Yakinifu na shida ya uboreshaji. Tasnifu ya Uhandisi wa Kompyuta, ITAM. Mshauri: Dk. Andrés Gómez de Silva Garza. Imeidhinishwa mnamo Julai 23, 2026.

Tatizo

MLB hupanga michezo 2,430 kwa timu 30 kwa takriban siku 180. Kila timu husafiri kati ya miji, na umbali hutofautiana sana kutoka timu hadi timu. Mnamo 2016, Seattle ilisafiri kilomita 76,683, na Chicago Cubs ilisafiri kilomita 39,015.

Kupata ratiba iliyo na umbali wa chini kabisa inajulikana kama Tatizo la Usafiri wa Mashindano (PTT). Ni tatizo gumu la NP: idadi ya ratiba zinazowezekana hukua haraka sana hivi kwamba huwezi kuziangalia zote.

Njia

Programu ya maumbile (PG), iliyopendekezwa na John Koza mnamo 1992, inaiga mageuzi. Inaunda idadi ya suluhisho, inachukua bora zaidi, na inachanganya na kuzirekebisha kuunda kizazi kipya.

Uwakilishi: Kila kalenda ni mti. Nodi zake ni shughuli kama crear_juego vile (tarehe, timu ya nyumbani, timu ya ugenini) na obtener_calendario, ambayo inajiunga na orodha mbili za michezo.
Uwezekano (C1): Kila timu lazima icheze idadi ya michezo ambayo mashindano yanahitaji. Thamani ya 0 inamaanisha kuwa ratiba ni halali.
Umbali (C2): jumla ya uhamisho, uliohesabiwa na fomula ya haversine kwenye kuratibu za kila uwanja.
Programu: moduli tatu (mpangaji, kikokotoo na programu ya maumbile) na maktaba ya DEAP, tofauti na programu ya wavuti huko Django.

Matokeo

Jaribu timu 30, michezo 163 kwa kila timu, mfululizo wa michezo 5, na vizazi 20.

Ulinganisho wa Utafutaji wa Nasibu na Programu ya Maumbile
Njia	Prob. ya kuvuka	Prob. ya mabadiliko	Yakinifu (C1)	Jumla ya umbali (C2)	Wakati
Utafutaji wa nasibu	0.0	0.0	0 (halali)	2,663,470.70 km Umbali mfupi	200.25 s
Programu ya maumbile	0.8	0.2	0 (halali)	3,182,738.33 km	3,337.81 s

Matokeo kuu

Programu ya maumbile haikushinda utafutaji wa nasibu. Ilitoa umbali mkubwa wa 19.5% na ilichukua karibu mara 17 zaidi. Kalenda bora kila wakati ilitoka kwa kizazi cha awali, ambacho ni cha nasibu.

Thesis ilibainisha sababu hizi:

Waendeshaji wa kawaida wa crossover na mabadiliko hubadilisha nodi bila kujua shida. Karibu kila wakati hutoa kalenda batili.
Kazi ya usawa inatoa uzito zaidi kwa uwezekano kuliko umbali. Mtoto batili daima hupoteza kwa mzazi halali.
Algorithm hivi karibuni iliungana kwenye bora ya ndani na kuhifadhi suluhisho za awali tu.

Matokeo mabaya pia ni matokeo. Inaonyesha kuwa uwakilishi na waendeshaji ni muhimu kama algorithm.

Kazi ya baadaye

Thesis ilipendekeza waendeshaji wa muktadha: badala ya kubadilisha nodi bila mpangilio, badilisha safu nzima au vizuizi ambavyo vinaweka kalenda halali. Alitaja pia kompyuta ya quantum kuchunguza usanidi mwingi mara moja.

Tazama kilichofanyika baada ya thesis

Ratiba ya matukio

Huenda 2026 · Toleo rasmi la awali la hati ya thesis.
Julai 23, 2026 · Ulinzi katika Jiji la Mexico. Thesis imeidhinishwa.

Nyenzo na nukuu

Hati ya thesis, toleo rasmi la awali (PDF, 4.8 MB, kwa Kihispania)
Uwasilishaji wa utetezi (PDF, 2.9 MB, kwa Kihispania)

Nukuu katika muundo wa 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.