Dokumentasi / Sejarah

Sejarah: tesis (2026)

Pengaturcaraan genetik dalam perancangan musim besbol. Masalah kebolehlaksanaan dan pengoptimuman. Tesis Kejuruteraan Komputer, ITAM. Penasihat: Dr. Andrés Gómez de Silva Garza. Diluluskan pada 23 Julai 2026.

Masalahnya

MLB menjadualkan 2,430 perlawanan untuk 30 pasukan dalam kira-kira 180 hari. Setiap pasukan bergerak antara bandar, dan jaraknya sangat berbeza antara pasukan. Pada tahun 2016, Seattle menempuh perjalanan sejauh 76,683 km, dan Chicago Cubs menempuh 39,015 km.

Mencari jadual dengan jumlah jarak paling rendah dikenali sebagai Masalah Pengangkutan Kejohanan (PTT). Ini adalah masalah yang sukar bagi NP: bilangan jadual yang mungkin meningkat dengan sangat pantas sehingga anda tidak dapat memeriksa semuanya.

Kaedah

Pengaturcaraan genetik (PG), yang dicadangkan oleh John Koza pada tahun 1992, meniru evolusi. Ia mencipta populasi penyelesaian, mengambil yang terbaik, dan menggabungkan serta mengubahnya untuk membentuk generasi baru.

Perwakilan: Setiap kalendar adalah pokok. Nodnya adalah operasi seperti crear_juego (tarikh, pasukan tuan rumah, pasukan pelawat) dan obtener_calendario, yang menggabungkan dua senarai permainan.
Kebolehlaksanaan (C1): Setiap pasukan mesti bermain tepat bilangan perlawanan yang ditetapkan oleh kejohanan. Nilai 0 bermakna jadual adalah sah.
Jarak (C2): jumlah pemindahan, dikira dengan formula haversine pada koordinat setiap stadium.
Perisian: tiga modul (perancang, kalkulator dan program genetik) dengan perpustakaan DEAP, berasingan daripada aplikasi web dalam Django.

Keputusan

Cuba 30 pasukan, 163 perlawanan setiap pasukan, siri 5 perlawanan, dan 20 generasi.

Perbandingan Carian Rawak dan Pengaturcaraan Genetik
Kaedah	Mungkin. melintasi	Mungkin. mutasi	Kebolehlaksanaan (C1)	Jumlah jarak (C2)	Masa
Carian rawak	0.0	0.0	0 (sah)	2,663,470.70 km Jarak yang lebih pendek	200.25 s
Pengaturcaraan genetik	0.8	0.2	0 (sah)	3,182,738.33 km	3,337.81 s

Penemuan utama

Pengaturcaraan genetik tidak mengatasi pencarian rawak. Ia memberikan jarak 19.5% lebih jauh dan mengambil masa hampir 17 kali lebih lama. Kalendar terbaik sentiasa datang dari generasi awal, yang rawak.

Tesis tersebut mengenal pasti punca-punca berikut:

Operator crossover dan mutasi generik menukar nod tanpa mengetahui masalahnya. Mereka hampir selalu menghasilkan kalendar yang tidak sah.
Fungsi kecergasan memberi lebih banyak penekanan kepada kebolehlaksanaan berbanding jarak. Anak yang tidak sihat sentiasa kalah kepada ibu bapa yang sah.
Algoritma ini segera mencapai optimum setempat dan hanya mengekalkan penyelesaian awal.

Hasil negatif juga merupakan keputusan. Ia menunjukkan bahawa representasi dan operator sama pentingnya dengan algoritma.

Kerja masa depan

Tesis itu mencadangkan operator kontekstual: daripada menukar nod secara rawak, tukar keseluruhan siri atau blok yang mengekalkan kalendar sah. Beliau juga menyebut pengkomputeran kuantum untuk meneroka banyak konfigurasi sekaligus.

Lihat apa yang dilakukan selepas tesis

Garis masa

Mei 2026 · Versi prarasmi dokumen tesis.
23 Julai 2026 · Pertahanan di Mexico City. Tesis diluluskan.

Bahan dan sitasi

Dokumen tesis, versi pra-rasmi (PDF, 4.8 MB, dalam bahasa Sepanyol)
Pembentangan pembelaan (PDF, 2.9 MB, dalam bahasa Sepanyol)

Petikan dalam format 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.