תיעוד / היסטוריה
היסטורי: התזה (2026)
תכנות גנטי בתכנון עונת הבייסבול. בעיית היתכנות ואופטימיזציה. עבודת גמר בהנדסת מחשבים, ITAM. יועץ: ד"ר אנדרס גומז דה סילבה גרזה. אושר ב-23 ביולי 2026.
הבעיה
ה-MLB מתכנן 2,430 משחקים ל-30 קבוצות בכ-180 ימים. כל קבוצה נוסעת בין ערים, והמרחק משתנה מאוד מקבוצה לקבוצה. בשנת 2016, סיאטל נסעה 76,683 ק"מ, ושיקגו קאבס נסעו 39,015 ק"מ.
מציאת לוח הזמנים עם המרחק הכולל הנמוך ביותר נקראת בעיית התחבורה בטורניר (PTT). זו בעיה קשה של NP: מספר הלוחות זמנים האפשריים גדל כל כך מהר שאי אפשר לבדוק את כולם.
השיטה
תכנות גנטי (PG), שהוצע על ידי ג'ון קוזה ב-1992, מחקה אבולוציה. הוא יוצר אוכלוסייה של פתרונות, לוקח את הטובים ביותר, ומשלב ומשנה אותם ליצירת דור חדש.
- ייצוג: כל לוח שנה הוא עץ. הצמתים שלו הם פעולות כמו
crear_juego(תאריך, קבוצה ביתית, קבוצה אורחת) וobtener_calendario-, שמצטרף לשתי רשימות משחקים. - כדאיות (C1): כל קבוצה חייבת לשחק בדיוק את מספר המשחקים שהטורניר דורש. ערך של 0 אומר שהלוח זמנים תקף.
- מרחק (C2): סכום ההעברות, מחושב לפי נוסחת הברסין על הקואורדינטות של כל אצטדיון.
- תוכנה: שלושה מודולים (מתכנן, מחשבון ותוכנית גנטית) עם ספריית DEAP, נפרדת מאפליקציית ווב בג'אנגו.
התוצאות
נסה 30 קבוצות, 163 משחקים לכל קבוצה, סדרות של 5 משחקים, ו-20 דורות.
| שיטה | בעיה. של חצייה | בעיה. של מוטציה | היתכנות (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.