जब कुछ कम्यूटर ट्रेनें लाइन के अंत में पहुंचती हैं, तो उन्हें एक स्विचिंग प्लेटफॉर्म पर यात्रा करनी चाहिए ताकि वे स्टेशन को बाद में प्रस्थान कर सकें, अक्सर एक अलग मंच से जिस पर वे पहुंचे।
इंजीनियर इन आंदोलनों की योजना बनाने के लिए एल्गोरिथम सॉल्वर नामक सॉफ़्टवेयर प्रोग्राम का उपयोग करते हैं, लेकिन हजारों साप्ताहिक आगमन और प्रस्थान के साथ एक स्टेशन पर, समस्या एक पारंपरिक सॉल्वर के लिए एक बार में सभी को उजागर करने के लिए बहुत जटिल हो जाती है।
मशीन लर्निंग का उपयोग करते हुए, एमआईटी शोधकर्ताओं ने एक बेहतर योजना प्रणाली विकसित की है जो हल समय को 50 प्रतिशत तक कम कर देता है और एक समाधान का उत्पादन करता है जो बेहतर उपयोगकर्ता के उद्देश्य को पूरा करता है, जैसे कि समय पर ट्रेन प्रस्थान। नई विधि का उपयोग कुशलता से अन्य जटिल तार्किक समस्याओं को हल करने के लिए भी किया जा सकता है, जैसे कि अस्पताल के कर्मचारियों को शेड्यूल करना, एयरलाइन क्रू को असाइन करना, या कारखाने मशीनों को कार्य आवंटित करना।
इंजीनियर अक्सर इस प्रकार की समस्याओं को ओवरप्रोफ्लेम को ओवरलैपिंग के अनुक्रम में तोड़ते हैं, जिन्हें प्रत्येक को संभव समय में हल किया जा सकता है। लेकिन ओवरलैप्स के कारण कई फैसले अनावश्यक रूप से फिर से शुरू हो जाते हैं, इसलिए सॉल्वर को एक इष्टतम समाधान तक पहुंचने में अधिक समय लगता है।
नया, कृत्रिम बुद्धिमत्ता-संवर्धित दृष्टिकोण सीखता है कि प्रत्येक उपप्रकार के कौन से हिस्से अपरिवर्तित रहना चाहिए, उन चरों को निरर्थक संगणना से बचने के लिए ठंड। फिर एक पारंपरिक एल्गोरिथम सॉल्वर शेष चर से निपटता है।
“अक्सर, एक समर्पित टीम महीनों या सालों तक खर्च कर सकती है, यहां तक कि इन कॉम्बिनेटरियल समस्याओं में से एक को हल करने के लिए एक एल्गोरिथ्म डिजाइन करने में भी। आधुनिक गहरी सीखने से हमें इन एल्गोरिदम के डिजाइन को सुव्यवस्थित करने में मदद करने के लिए नए अग्रिमों का उपयोग करने का अवसर मिलता है। हम जो कुछ भी जानते हैं उसे अच्छी तरह से ले सकते हैं, और इसे तेजी लाने के लिए एआई का उपयोग करें, (IDSS) MIT में, और सूचना और निर्णय प्रणालियों (LIDS) के लिए प्रयोगशाला का एक सदस्य।
वह एक आईडीएसएस स्नातक छात्रा सिरुई ली के प्रमुख लेखक सिरुई ली द्वारा कागज पर शामिल हैं; वेनबिन ओयंग, एक सीईई स्नातक छात्र; और एमए, एक लिड्स पोस्टडॉक। अनुसंधान को सीखने के अभ्यावेदन पर अंतर्राष्ट्रीय सम्मेलन में प्रस्तुत किया जाएगा।
अतिरेक को समाप्त करना
इस शोध के लिए एक प्रेरणा एक मास्टर के छात्र डेविन केमिली विल्किंस द्वारा वू के एंट्री-लेवल ट्रांसपोर्टेशन कोर्स में पहचानी गई एक व्यावहारिक समस्या है। छात्र बोस्टन के नॉर्थ स्टेशन पर एक वास्तविक ट्रेन-डिस्पैच समस्या के लिए सुदृढीकरण सीखने को लागू करना चाहता था। पारगमन संगठन को कई ट्रेनों को सीमित संख्या में प्लेटफार्मों पर असाइन करने की आवश्यकता है, जहां उन्हें स्टेशन पर अपने आगमन से पहले अच्छी तरह से चारों ओर घुमाया जा सकता है।
यह एक बहुत ही जटिल कॉम्बिनेटरियल शेड्यूलिंग समस्या है – सटीक प्रकार की समस्या वू की लैब ने पिछले कुछ वर्षों में काम करने में बिताया है।
जब एक दीर्घकालिक समस्या का सामना करना पड़ता है जिसमें मशीनों के एक समूह के लिए कारखाने के कार्यों की तरह संसाधनों का एक सीमित सेट असाइन करना शामिल होता है, तो योजनाकार अक्सर लचीली नौकरी की दुकान के समय निर्धारण के रूप में समस्या को फ्रेम करते हैं।
लचीली नौकरी की दुकान शेड्यूलिंग में, प्रत्येक कार्य को पूरा करने के लिए एक अलग समय की आवश्यकता होती है, लेकिन कार्यों को किसी भी मशीन को सौंपा जा सकता है। उसी समय, प्रत्येक कार्य संचालन से बना होता है जिसे सही क्रम में किया जाना चाहिए।
इस तरह की समस्याएं पारंपरिक सॉल्वरों के लिए जल्दी से बहुत बड़ी और अनजान हो जाती हैं, इसलिए उपयोगकर्ता समस्या को प्रबंधनीय विखंडन में तोड़ने के लिए रोलिंग क्षितिज अनुकूलन (आरएचओ) को नियुक्त कर सकते हैं जो तेजी से हल किए जा सकते हैं।
RHO के साथ, एक उपयोगकर्ता एक निश्चित नियोजन क्षितिज में मशीनों को प्रारंभिक कुछ कार्य प्रदान करता है, शायद चार घंटे की समय खिड़की। फिर, वे उस अनुक्रम में पहले कार्य को निष्पादित करते हैं और अगले कार्य को जोड़ने के लिए चार-घंटे की योजना क्षितिज को आगे स्थानांतरित करते हैं, प्रक्रिया को दोहराते हैं जब तक कि पूरी समस्या हल नहीं हो जाती है और टास्क-मशीन असाइनमेंट की अंतिम अनुसूची बनाई जाती है।
एक नियोजन क्षितिज किसी भी कार्य की अवधि से अधिक लंबा होना चाहिए, क्योंकि समाधान बेहतर होगा यदि एल्गोरिथ्म उन कार्यों पर भी विचार करता है जो आने वाले हैं।
लेकिन जब नियोजन क्षितिज आगे बढ़ता है, तो यह पिछले नियोजन क्षितिज में संचालन के साथ कुछ ओवरलैप बनाता है। एल्गोरिथ्म पहले से ही इन अतिव्यापी कार्यों के प्रारंभिक समाधान के साथ आया था।
“शायद ये प्रारंभिक समाधान अच्छे हैं और फिर से गणना करने की आवश्यकता नहीं है, लेकिन शायद वे अच्छे नहीं हैं। यह वह जगह है जहां मशीन लर्निंग आती है,” वू बताते हैं।
उनकी तकनीक के लिए, जिसे वे लर्निंग-गाइडेड रोलिंग होराइजन ऑप्टिमाइज़ेशन (L-RHO) कहते हैं, शोधकर्ताओं ने एक मशीन-लर्निंग मॉडल सिखाया, ताकि यह अनुमान लगाया जा सके कि किन संचालन, या चर, को फिर से शुरू किया जाना चाहिए जब योजना क्षितिज के आगे बढ़ता है।
एल-आरएचओ को मॉडल को प्रशिक्षित करने के लिए डेटा की आवश्यकता होती है, इसलिए शोधकर्ताओं ने शास्त्रीय एल्गोरिथम सॉल्वर का उपयोग करके उपप्रकारों के एक सेट को हल किया। उन्होंने सबसे अच्छा समाधान लिया – सबसे अधिक संचालन वाले जिन्हें पुन: व्यवस्थित करने की आवश्यकता नहीं है – और इनका उपयोग प्रशिक्षण डेटा के रूप में किया।
एक बार प्रशिक्षित होने के बाद, मशीन-लर्निंग मॉडल को एक नया उपप्रकार प्राप्त होता है जिसे उसने पहले नहीं देखा है और यह भविष्यवाणी करता है कि किन संचालन को पुन: व्यवस्थित नहीं किया जाना चाहिए। शेष संचालन को एल्गोरिथम सॉल्वर में वापस खिलाया जाता है, जो कार्य को निष्पादित करता है, इन संचालन को फिर से शुरू करता है, और नियोजन क्षितिज को आगे बढ़ाता है। फिर लूप फिर से शुरू होता है।
“अगर, अगर, हमें उन्हें फिर से तैयार करने की आवश्यकता नहीं थी, तो हम उन चर को समस्या से हटा सकते हैं। क्योंकि ये समस्याएं तेजी से आकार में बढ़ती हैं, यह काफी फायदेमंद हो सकता है अगर हम उन चरों में से कुछ को छोड़ सकते हैं,” वह कहती हैं।
एक अनुकूलनीय, स्केलेबल दृष्टिकोण
उनके दृष्टिकोण का परीक्षण करने के लिए, शोधकर्ताओं ने एल-आरएचओ की तुलना कई बेस एल्गोरिथम सॉल्वर, विशेष सॉल्वर, और दृष्टिकोणों से की, जो केवल मशीन लर्निंग का उपयोग करते हैं। इसने उन सभी को बेहतर बनाया, समय को हल करने के समय को 54 प्रतिशत तक कम किया और समाधान की गुणवत्ता में 21 प्रतिशत तक सुधार किया।
इसके अलावा, उनकी विधि सभी बेसलाइन को बेहतर बनाती रही जब उन्होंने इसे समस्या के अधिक जटिल वेरिएंट पर परीक्षण किया, जैसे कि जब फैक्ट्री मशीनें टूट जाती हैं या जब अतिरिक्त ट्रेन की भीड़ होती है। यहां तक कि इसने अतिरिक्त आधार रेखाओं को भी बेहतर बनाया कि शोधकर्ताओं ने अपने सॉल्वर को चुनौती देने के लिए बनाया।
वह कहती हैं, “हमारे दृष्टिकोण को इन सभी अलग -अलग वेरिएंट में संशोधन के बिना लागू किया जा सकता है, जो कि वास्तव में हम अनुसंधान की इस पंक्ति के साथ क्या करना चाहते हैं,” वह कहती हैं।
एल-आरएचओ भी अनुकूलित कर सकता है यदि उद्देश्य बदलते हैं, तो समस्या को हल करने के लिए स्वचालित रूप से एक नया एल्गोरिथ्म उत्पन्न करना-इसकी आवश्यकता एक नया प्रशिक्षण डेटासेट है।
भविष्य में, शोधकर्ता कुछ चर को फ्रीज करने के अपने मॉडल के फैसले के पीछे के तर्क को बेहतर ढंग से समझना चाहते हैं, लेकिन अन्य नहीं। वे इन्वेंट्री प्रबंधन या वाहन रूटिंग जैसी अन्य प्रकार की जटिल अनुकूलन समस्याओं में अपने दृष्टिकोण को एकीकृत करना चाहते हैं।
इस काम का समर्थन किया गया था, नेशनल साइंस फाउंडेशन, MIT की रिसर्च सपोर्ट कमेटी, एक अमेज़ॅन रोबोटिक्स पीएचडी फेलोशिप और मैथवर्क्स द्वारा भाग में।
(टैगस्टोट्रांसलेट) कैथी वू (टी) कॉम्बिनेटरियल ऑप्टिमाइज़ेशन (टी) लचीली नौकरी की दुकान शेड्यूलिंग
