प्रलेखन / इतिहास
ऐतिहासिक: थीसिस (2026)
बेसबॉल सीज़न योजना में आनुवंशिक प्रोग्रामिंग। व्यवहार्यता और अनुकूलन समस्या। कंप्यूटर इंजीनियरिंग थीसिस, आईटीएएम। सलाहकार: डॉ. एंड्रेस गोमेज़ डी सिल्वा गार्ज़ा। 23 जुलाई, 2026 को स्वीकृत।
समस्या
एमएलबी लगभग 2,430 दिनों में 30 टीमों के लिए 180 गेम शेड्यूल करता है। प्रत्येक टीम शहरों के बीच यात्रा करती है, और दूरी एक टीम से दूसरी टीम में बहुत भिन्न होती है। 2016 में, सिएटल ने 76,683 किमी की यात्रा की, और शिकागो शावक ने 39,015 किमी की यात्रा की।
सबसे कम कुल दूरी के साथ शेड्यूल ढूँढना टूर्नामेंट परिवहन समस्या (पीटीटी) के रूप में जाना जाता है। यह एक एनपी-कठिन समस्या है: संभावित शेड्यूल की संख्या इतनी तेजी से बढ़ती है कि आप उन सभी की जांच नहीं कर सकते।
विधि
1992 में जॉन कोज़ा द्वारा प्रस्तावित जेनेटिक प्रोग्रामिंग (पीजी), विकास की नकल करता है। यह समाधानों की आबादी बनाता है, सबसे अच्छे समाधानों को लेता है, और उन्हें एक नई पीढ़ी बनाने के लिए जोड़ता है और संशोधित करता है।
- प्रतिनिधित्व: प्रत्येक कैलेंडर एक पेड़ है। इसके नोड्स ऑपरेशन हैं जैसे (
crear_juegoतारीख, होम टीम, दूर टीम) औरobtener_calendario, जो खेलों की दो सूचियों में शामिल हो जाता है। - व्यवहार्यता (C1): प्रत्येक टीम को ठीक उतने ही गेम खेलने चाहिए जितने टूर्नामेंट के लिए कहता है। 0 के मान का मतलब है कि शेड्यूल मान्य है।
- दूरी (C2): स्थानान्तरण का योग, प्रत्येक स्टेडियम के निर्देशांक पर हैवरसिन के सूत्र के साथ गणना की जाती है।
- सॉफ्टवेयर: डीईएपी लाइब्रेरी के साथ तीन मॉड्यूल (प्लानर, कैलकुलेटर और जेनेटिक प्रोग्राम), Django में एक वेब एप्लिकेशन से अलग।
परिणाम
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, स्पेनिश में)
एपीए प्रारूप में उद्धरण:
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.