Τεκμηρίωση / Ιστορία
Ιστορική: η διατριβή (2026)
Γενετικός προγραμματισμός στον προγραμματισμό σεζόν του μπέιζμπολ. Πρόβλημα σκοπιμότητας και βελτιστοποίησης. Διατριβή Μηχανικού Υπολογιστών, ITAM. Σύμβουλος: Dr. Andrés Gómez de Silva Garza. Εγκρίθηκε στις 23 Ιουλίου 2026.
Το πρόβλημα
Το MLB προγραμματίζει 2,430 παιχνίδια για 30 ομάδες σε περίπου 180 ημέρες. Κάθε ομάδα ταξιδεύει μεταξύ πόλεων και η απόσταση ποικίλλει πολύ από ομάδα σε ομάδα. Το 2016, το Σιάτλ ταξίδεψε 76,683 χιλιόμετρα και οι Chicago Cubs ταξίδεψαν 39,015 χιλιόμετρα.
Η εύρεση του προγράμματος με τη χαμηλότερη συνολική απόσταση είναι γνωστή ως Πρόβλημα Μεταφοράς Τουρνουά (PTT). Είναι ένα δύσκολο πρόβλημα NP: ο αριθμός των πιθανών δρομολογίων αυξάνεται τόσο γρήγορα που δεν μπορείτε να τα ελέγξετε όλα.
Η μέθοδος
Ο γενετικός προγραμματισμός (PG), που προτάθηκε από τον John Koza το 1992, μιμείται την εξέλιξη. Δημιουργεί έναν πληθυσμό λύσεων, παίρνει τις καλύτερες και τις συνδυάζει και τις τροποποιεί για να σχηματίσει μια νέα γενιά.
- Αναπαράσταση: Κάθε ημερολόγιο είναι ένα δέντρο. Οι κόμβοι του είναι λειτουργίες όπως
crear_juego(ημερομηνία, γηπεδούχος, φιλοξενούμενη ομάδα) καιobtener_calendario, που ενώνει δύο λίστες παιχνιδιών. - Βιωσιμότητα (C1): Κάθε ομάδα πρέπει να παίξει ακριβώς τον αριθμό των παιχνιδιών που απαιτεί το τουρνουά. Η τιμή 0 σημαίνει ότι το πρόγραμμα είναι έγκυρο.
- Απόσταση (C2): το άθροισμα των μεταγραφών, που υπολογίζεται με τον τύπο του haversine στις συντεταγμένες κάθε σταδίου.
- Λογισμικό: τρία modules (planner, calculator και genetic program) με τη βιβλιοθήκη DEAP, ξεχωριστά από μια web εφαρμογή στο Django.
Τα αποτελέσματα
Δοκιμάστε 30 ομάδες, 163 παιχνίδια ανά ομάδα, σειρές 5 αγώνων και 20 γενιές.
| Μέθοδος | Prob. διέλευσης | Prob. της μετάλλαξης | Σκοπιμότητα (C1) | Συνολική απόσταση (C2) | Χρόνος |
|---|---|---|---|---|---|
| Τυχαία αναζήτηση | 0.0 | 0.0 | 0 (έγκυρο) | 2,663,470.70 km Μικρότερη απόσταση | 200.25 s |
| Γενετικός προγραμματισμός | 0.8 | 0.2 | 0 (έγκυρο) | 3,182,738.33 km | 3,337.81 s |
Το κύριο εύρημα
Ο γενετικός προγραμματισμός δεν ξεπέρασε την τυχαία αναζήτηση. Έδωσε 19,5% μεγαλύτερη απόσταση και χρειάστηκε σχεδόν 17 φορές περισσότερο. Το καλύτερο ημερολόγιο προερχόταν πάντα από την αρχική γενιά, η οποία είναι τυχαία.
Η διατριβή εντόπισε αυτές τις αιτίες:
- Οι γενικοί τελεστές διασταύρωσης και μετάλλαξης αλλάζουν κόμβους χωρίς να γνωρίζουν το πρόβλημα. Σχεδόν πάντα παράγουν μη έγκυρα ημερολόγια.
- Η λειτουργία φυσικής κατάστασης δίνει πολύ μεγαλύτερη βαρύτητα στη βιωσιμότητα παρά στην απόσταση. Ένα ανάπηρο παιδί χάνει πάντα από έναν έγκυρο γονέα.
- Ο αλγόριθμος σύντομα συνέκλινε σε ένα τοπικό βέλτιστο και διατήρησε μόνο τις αρχικές λύσεις.
Ένα αρνητικό αποτέλεσμα είναι επίσης αποτέλεσμα. Δείχνει ότι η αναπαράσταση και οι τελεστές έχουν τόση σημασία όσο και ο αλγόριθμος.
Μελλοντικές εργασίες
Η διατριβή πρότεινε τελεστές με βάση τα συμφραζόμενα: αντί να αλλάζετε κόμβους τυχαία, ανταλλάξτε ολόκληρες σειρές ή μπλοκ που διατηρούν το ημερολόγιο έγκυρο. Ανέφερε επίσης τον κβαντικό υπολογισμό για να εξερευνήσει πολλές διαμορφώσεις ταυτόχρονα.
Χρονοδιάγραμμα
- · Προ-επίσημη έκδοση του εγγράφου της διατριβής.
- · Άμυνα στην Πόλη του Μεξικού. Η διατριβή εγκρίθηκε.
Υλικό και παραπομπή
- Έγγραφο διατριβής, προεπίσημη έκδοση (PDF, 4.8 MB, στα Ισπανικά)
- Παρουσίαση της υπεράσπισης (PDF, 2.9 MB, στα Ισπανικά)
Παραπομπή σε μορφή 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.