Dokümantasyon / Tarihçe
Tarihi: tez (2026)
Beyzbol sezon planlamasında genetik programlama. Fizibilite ve optimizasyon problemi. Bilgisayar Mühendisliği Tezi, ITAM. Danışman: Dr. Andrés Gómez de Silva Garza. 23 Temmuz 2026'da onaylandı.
Sorun
MLB, yaklaşık 180 günde 30 takım için 2.430 maç planlıyor. Her takım şehirler arasında seyahat ediyor ve mesafe takımdan takıma büyük ölçüde değişiyor. 2016'da Seattle 76.683 km, Chicago Cubs ise 39.015 km yol kat etti.
En düşük toplam mesafeye sahip programı bulmak, Turnuva Ulaşım Problemi (PTT) olarak bilinir. Bu NP-zor bir problem: olası programların sayısı o kadar hızlı büyür ki hepsini kontrol edemezsiniz.
Yöntem
John Koza tarafından 1992'de önerilen genetik programlama (PG) evrimi taklit eder. Çözümler popülasyonu oluşturur, en iyilerini alır ve bunları birleştirip yeni bir nesil oluşturmak için değiştirir.
- Temsil: Her takvim bir ağaçtır. Düğümleri (tarih, ev sahibi takım, deplasman takımı) ve
obtener_calendario, gibi işlemlerdircrear_juego; bu da iki oyun listesine katılır. - Kullanılabilirlik (C1): Her takım, turnuvanın gerektirdiği maç sayısını tam olarak oynamalıdır. 0 değeri, takvimin geçerli olduğu anlamına gelir.
- Mesafe (C2): transferlerin toplamı, her stadyumun koordinatları üzerinde Haversine formülüyle hesaplanır.
- Yazılım: DEAP kütüphanesiyle üç modül (planlayıcı, hesaplayıcı ve genetik program) ve Django'daki bir web uygulamasından ayrı.
Sonuçlar
30 takım, takım başına 163 maç, 5 maçlık seri ve 20 nesil deneyin.
| Yöntem | Muhtemelen. Geçiş | muhtemelen. mutasyonun | Fizibilite (C1) | Toplam mesafe (C2) | Zaman |
|---|---|---|---|---|---|
| Rastgele arama | 0.0 | 0.0 | 0 (geçerli) | 2,663,470.70 km Daha kısa mesafe | 200.25 s |
| Genetik programlama | 0.8 | 0.2 | 0 (geçerli) | 3,182,738.33 km | 3,337.81 s |
Ana bulgu
Genetik programlama rastgele aramayı geride bırakmadı. %19,5 daha fazla mesafe sağladı ve neredeyse 17 kat daha uzun sürdü. En iyi takvim her zaman rastgele olan ilk nesildən gelirdi.
Tez şu nedenleri belirledi:
- Genel çapraz geçiş ve mutasyon operatörleri sorunu bilmeden düğümleri değiştirir. Neredeyse her zaman geçersiz takvimler üretirler.
- Uygunluk fonksiyonu, mesafeden çok daha fazla önem verir. Geçerli bir çocuk her zaman geçerli bir ebeveyne kaybeder.
- Algoritma kısa sürede yerel bir optimuma yaklaştı ve sadece ilk çözümleri korudu.
Negatif sonuç da bir sonuçtur. Bu, temsil ve operatörlerin algoritma kadar önemli olduğunu gösterir.
Gelecek çalışmalar
Tez, bağlamsal operatörler önerdi: düğümleri rastgele değiştirmek yerine, takvimi geçerli tutan tüm seri veya blokları değiştirin. Ayrıca kuantum hesaplamanın birçok konfigürasyonu aynı anda keşfetmesini de belirtti.
Zaman çizelgesi
- · Tez belgesinin resmi öncesi versiyonu.
- · Meksiko Şehri'nde savunma. Tez onaylandı.
Materyaller ve atıf
- Tez belgesi, resmi öncesi versiyon (PDF, 4.8 MB, İspanyolca)
- Savunmanın sunumu (PDF, 2.9 MB, İspanyolca)
APA formatında atıf:
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.