Dokumentasi / Sejarah

Historis: tesis (2026)

Pemrograman genetik dalam perencanaan musim bisbol. Masalah kelayakan dan optimasi. Tesis Teknik Komputer, ITAM. Pembimbing: Dr. Andrés Gómez de Silva Garza. Disetujui pada 23 Juli 2026.

Masalahnya

MLB menjadwalkan 2.430 pertandingan untuk 30 tim dalam sekitar 180 hari. Setiap tim melakukan perjalanan antar kota, dan jaraknya sangat bervariasi dari satu tim ke tim lain. Pada tahun 2016, Seattle menempuh jarak 76.683 km, dan Chicago Cubs menempuh 39.015 km.

Menemukan jadwal dengan jarak total terendah dikenal sebagai Tournament Transportation Problem (PTT). Ini adalah masalah NP yang sulit: jumlah jadwal yang mungkin bertambah begitu cepat sehingga Anda tidak bisa memeriksa semuanya.

Metode

Pemrograman genetik (PG), yang diusulkan oleh John Koza pada tahun 1992, meniru evolusi. Ia menciptakan populasi solusi, mengambil yang terbaik, dan menggabungkan serta memodifikasinya untuk membentuk generasi baru.

Representasi: Setiap kalender adalah sebuah pohon. Node-nya adalah operasi seperti crear_juego (tanggal, tim tuan rumah, tim tamu) dan obtener_calendario, yang menggabungkan dua daftar pertandingan.
Kelayakan (C1): Setiap tim harus memainkan persis jumlah pertandingan yang diminta turnamen. Nilai 0 berarti jadwal tersebut valid.
Jarak (C2): jumlah transfer, dihitung dengan rumus haversine pada koordinat setiap stadion.
Perangkat lunak: tiga modul (perencana, kalkulator, dan program genetik) dengan pustaka DEAP, terpisah dari aplikasi web di Django.

Hasilnya

Coba 30 tim, 163 pertandingan per tim, seri 5 pertandingan, dan 20 generasi.

Perbandingan antara Pencarian Acak dan Pemrograman Genetik
Metode	Prob. menyeberang	Prob. mutasi	Kelayakan (C1)	Total jarak (C2)	Waktu
Pencarian acak	0.0	0.0	0 (valid)	2,663,470.70 km Jarak lebih pendek	200.25 s
Pemrograman genetik	0.8	0.2	0 (valid)	3,182,738.33 km	3,337.81 s

Temuan utama

Pemrograman genetik tidak mengalahkan pencarian acak. Itu memberikan jarak 19,5% lebih jauh dan memakan waktu hampir 17 kali lebih lama. Kalender terbaik selalu berasal dari generasi awal, yang bersifat acak.

Tesis tersebut mengidentifikasi penyebab-penyebab berikut:

Operator crossover dan mutasi generik berganti node tanpa mengetahui masalahnya. Mereka hampir selalu menghasilkan kalender yang tidak valid.
Fungsi kebugaran memberikan bobot lebih besar pada kelayakan daripada jarak. Anak yang tidak valid selalu kalah dari orang tua yang valid.
Algoritma segera mencapai optimum lokal dan hanya mempertahankan solusi awal.

Hasil negatif juga merupakan hasil. Ini menunjukkan bahwa representasi dan operator sama pentingnya dengan algoritma.

Karya Masa Depan

Tesis tersebut mengusulkan operator kontekstual: alih-alih mengubah node secara acak, tukar seluruh deret atau blok yang menjaga kalender tetap valid. Ia juga menyebutkan komputasi kuantum untuk mengeksplorasi banyak konfigurasi sekaligus.

Lihat apa yang dilakukan setelah tesis

Linimasa

Mei 2026 · Versi pra-resmi dari dokumen tesis.
23 Juli 2026 · Pertahanan di Mexico City. Tesis disetujui.

Materi dan kutipan

Dokumen tesis, versi pra-resmi (PDF, 4.8 MB, dalam bahasa Spanyol)
Penyajian pembelaan (PDF, 2.9 MB, dalam bahasa Spanyol)

Kutipan 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.