सीखी गई स्थानीय खोज हेयुरिस्टिक्स की सीमाओं का अनावरण: क्या आप नम्र लोगों में सबसे शक्तिशाली हैं?

लिंक की तालिका

सार एवं परिचय

संबंधित कार्य

मैक्स-कट के लिए मूल्यांकन

SAT के लिए मूल्यांकन

सारांश और दृष्टिकोण, संदर्भ

पूरक सामग्री

अमूर्त

हाल के वर्षों में, न्यूरल नेटवर्क को स्थानीय खोज हेरिस्टिक्स के साथ संयोजित करना कॉम्बिनेटरियल ऑप्टिमाइज़ेशन के क्षेत्र में लोकप्रिय हो गया है। इसकी काफी कम्प्यूटेशनल मांगों के बावजूद, इस दृष्टिकोण ने न्यूनतम मैनुअल इंजीनियरिंग के साथ आशाजनक परिणाम प्रदर्शित किए हैं। हालाँकि, हमने इन एकीकरण प्रयासों के अनुभवजन्य मूल्यांकन में तीन महत्वपूर्ण सीमाओं की पहचान की है। सबसे पहले, मध्यम जटिलता और कमजोर आधार रेखाओं वाले उदाहरण सीखने-आधारित दृष्टिकोणों की प्रभावशीलता का सटीक मूल्यांकन करने में एक चुनौती पेश करते हैं। दूसरे, एब्लेशन अध्ययन की अनुपस्थिति गहन शिक्षण वास्तुकला में सुधारों को सटीक रूप से मापना और उन्हें जिम्मेदार ठहराना मुश्किल बनाती है। अंत में, विविध वितरणों में सीखे गए हेरिस्टिक्स का सामान्यीकरण अभी भी कम खोजा गया है। इस अध्ययन में, हम इन पहचानी गई सीमाओं की एक व्यापक जांच करते हैं। आश्चर्यजनक रूप से, हम प्रदर्शित करते हैं कि टैबू सर्च पर आधारित एक सरल सीखा हुआ हेरिस्टिक प्रदर्शन और सामान्यीकरण के मामले में अत्याधुनिक (SOTA) सीखे हुए हेरिस्टिक्स से आगे निकल जाता है। हमारे निष्कर्ष प्रचलित मान्यताओं को चुनौती देते हैं और कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में भविष्य के शोध और नवाचार के लिए रोमांचक रास्ते खोलते हैं।

1 परिचय

एनपी-हार्ड कॉम्बिनेटरियल ऑप्टिमाइजेशन (सीओ) समस्याओं के लिए प्रभावी हेरिस्टिक्स या सन्निकटन एल्गोरिदम डिजाइन करना एक चुनौतीपूर्ण कार्य है, जिसके लिए अक्सर डोमेन ज्ञान और व्यापक परीक्षण-और-त्रुटि की आवश्यकता होती है। इस प्रकार, किसी समस्या की अंतर्निहित संरचना का फायदा उठाने वाले एल्गोरिदम सीखने के लिए मशीन लर्निंग के माध्यम से इस मांग और थकाऊ डिजाइन प्रक्रिया को स्वचालित करने के विचार ने शोधकर्ताओं के बीच महत्वपूर्ण रुचि प्राप्त की है (बेलो एट अल., 2016; खलील एट अल., 2017; बेंगियो एट अल., 2021; डोंग एट अल., 2021)। विशेष रूप से, इन कार्यों का एक बड़ा हिस्सा (खलील एट अल., 2017; बैरेट एट अल., 2020; योलकू और पोकोज़ोस, 2019) सीओ समस्याओं के लिए ग्राफ न्यूरल नेटवर्क (जीएनएन) को नियोजित करने पर केंद्रित है। कम्प्यूटेशनल मांगों के बावजूद, इन जीएनएन-आधारित दृष्टिकोणों ने विशिष्ट समस्याओं के अनुरूप एसओटीए हेरिस्टिक्स की तुलना में प्रतिस्पर्धी प्रदर्शन का प्रदर्शन किया है।

हालांकि ये संभावित प्रगति बहुत आशाजनक हैं, फिर भी कुछ चिंताएँ बनी हुई हैं। सीखे गए ह्यूरिस्टिक्स के बेहतर प्रदर्शन का श्रेय विशिष्ट उदाहरणों और बेसलाइन के चयन को दिया जा सकता है। विशेष रूप से, यदि बेसलाइन कमज़ोर हैं, तो सीखे गए ह्यूरिस्टिक्स आसानी से उनसे बेहतर प्रदर्शन कर सकते हैं। हार्ड इंस्टेंस और उचित बेसलाइन चयन के बिना, सीखे गए ह्यूरिस्टिक्स आसानी से SOTA ह्यूरिस्टिक्स के साथ तुलनीय प्रदर्शन दिखा सकते हैं, और इससे सीखे गए ह्यूरिस्टिक्स की वास्तविक क्षमताओं का अधिक आकलन हो सकता है। इसके अलावा, डीप लर्निंग आर्किटेक्चर के साथ स्केलेबिलिटी चुनौतियों के कारण SOTA ह्यूरिस्टिक्स के साथ तुलना कभी-कभी छोड़ दी जाती है।

सीखने-आधारित दृष्टिकोणों का एक उपसमूह (खलील एट अल., 2017; योलकू और पोकोज़ोस, 2019; बैरेट एट अल., 2020, 2022) पारंपरिक ह्यूरिस्टिक्स की कार्यक्षमता या व्यवहार को शामिल करता है, जो ह्यूरिस्टिक्स सिद्धांतों को मशीन लर्निंग घटकों के साथ एकीकृत करके संभावित रूप से बेहतर या बेहतर प्रदर्शन प्रदान करता है। यदि एकीकृत ह्यूरिस्टिक्स के साथ व्यापक तुलना और डीप लर्निंग आर्किटेक्चर के पृथक्करण अध्ययन की कमी है, तो डीप लर्निंग आर्किटेक्चर के विशिष्ट योगदान को निर्धारित करना चुनौतीपूर्ण हो जाता है। नतीजतन, यदि एकीकृत ह्यूरिस्टिक्स मजबूत हैं, तो सीखे गए ह्यूरिस्टिक्स बेसलाइन ह्यूरिस्टिक्स से बेहतर प्रदर्शन कर सकते हैं, जबकि डीप लर्निंग आर्किटेक्चर थोड़ी भूमिका निभाता है।

सीखे हुए अनुमानों की एक और बड़ी उपलब्धि (खलील एट अल., 2017; बैरेट एट अल., 2020; टोएनशॉफ एट अल., 2019), जिसे शुरू में एक विशेष वितरण से छोटे और विशिष्ट उदाहरणों पर प्रशिक्षित किया गया था, जब विभिन्न वितरणों से बड़े उदाहरणों पर परीक्षण किया गया तो प्रभावशाली प्रदर्शन प्रदर्शित करता है। यह उपलब्धि एक महत्वपूर्ण उपलब्धि के रूप में सामने आती है, जो सीखने-आधारित दृष्टिकोणों को नियोजित करने के मुख्य उद्देश्य के साथ संरेखित होती है: अनुमानों द्वारा अक्सर आवश्यक व्यापक अनुकूलन और डोमेन-विशिष्ट ज्ञान की आवश्यकता को कम करना। हालाँकि हाइपरपैरामीटर वाले क्लासिकल अनुमानों को भी चुनौतियों का सामना करना पड़ सकता है यदि उन्हें किसी विशिष्ट वितरण के लिए ठीक किया जाता है, तो वे विभिन्न वितरणों में सामान्यीकृत भी हो सकते हैं। प्राथमिक जांच इस बात के इर्द-गिर्द घूमती है कि क्या सीखे गए अनुमान वास्तव में क्लासिकल अनुमानों की तुलना में बेहतर सामान्यीकरण प्रदर्शित करते हैं। सीखे गए अनुमानों के विरुद्ध क्लासिकल अनुमानों की गहन और व्यावहारिक तुलना सीखे गए अनुमानों की सामान्यीकरण क्षमता के बारे में मूल्यवान अंतर्दृष्टि प्रदान करती है।

सीखे गए अनुमानों में अक्सर सैद्धांतिक गारंटी का अभाव होता है, जिससे प्रस्तावित पद्धतियों की ताकत और सीमाओं को समझने के लिए अनुभवजन्य मूल्यांकन एकमात्र तरीका बन जाता है। हमारा मानना है कि इन कार्यों के अनुभवजन्य मूल्यांकन में कई मौलिक, फिर भी महत्वपूर्ण प्रश्न अनदेखे रह गए हैं। जबकि ये पूछताछ सभी प्रकार के सीखे गए अनुमानों के लिए प्रासंगिक हैं, हम स्थानीय खोज अनुमानों को सीखने पर केंद्रित अत्यधिक उद्धृत और हाल ही में सहकर्मी-समीक्षित प्रकाशनों का विश्लेषण करके उन्हें पूछते हैं और उनका उत्तर देते हैं। हमारा लक्ष्य हमारे काम में चर्चा की गई सीओ समस्याओं के लिए संपूर्ण बेंचमार्क प्रदान करना नहीं है, बल्कि भविष्य के शोधकर्ताओं को उनके शोध का मूल्यांकन करने में सहायता करना है।

ठोस रूप से, हम निम्नलिखित प्रश्न पूछते हैं और उनका उत्तर देते हैं:

1. क्या सीखे गए हेयुरिस्टिक्स को ओवर-पैरामीटराइज़ किया जा सकता है? बिल्कुल। ECO-DQN में GNN को रैखिक प्रतिगमन से प्रतिस्थापित करके और ECO-DQN (बैरेट एट अल., 2020) से सुविधाओं के एक उपसमूह का उपयोग करके जो टैबू सर्च (ग्लोवर, 1990) से जुड़ता है, हम ECO-DQN का एक छोटा संस्करण पेश करते हैं जिसे सॉफ्टटैबू कहा जाता है। हमारा अध्ययन दर्शाता है कि सॉफ्टटैबू एनपीहार्ड मैक्सिमम-कट (मैक्स-कट) समस्या के लिए ECO-DQN की तुलना में बेहतर प्रदर्शन और सामान्यीकरण को प्रदर्शित करता है।

2. क्या बेसलाइन पूर्वाग्रह को सीखे गए ह्यूरिस्टिक्स के बेहतर प्रदर्शन के लिए जिम्मेदार ठहराया जा सकता है? हां, हम प्रदर्शित करते हैं कि सॉफ़्टटैबू, एक वेनिला सीखा हुआ ह्यूरिस्टिक, मैक्स-कट समस्या के लिए S2V-DQN (खलील एट अल., 2017) और बूलियन संतुष्टि (SAT) के लिए GNNSAT (योलकू और पोकोज़ोस, 2019) से बेहतर प्रदर्शन कर सकता है।

*3. क्या सीखा हुआ अनुमान उदाहरण चयन पूर्वाग्रह के कारण बेहतर सामान्यीकरण को प्रदर्शित कर सकता है?*हां, हम प्रदर्शित करते हैं कि ECO-DQN कठिन उदाहरणों पर खराब सामान्यीकरण दिखाता है और आसानी से खोज स्थान में फंस जाता है।