A New Meta-Heuristic for Improving General Multi-Start Procedures

अनुकूलन (optimization) की दुनिया में, वैज्ञानिक और इंजीनियर अक्सर एक ऐसी समस्या का सामना करते हैं जो सरल दिखती है लेकिन संभावनाओं का एक भूलभुलैया छिपाए रखती है: एक समूह को कुशलतापूर्वक सेवा देने के लिए सुविधाओं (जैसे गोदाम या सेल टावर) को रखना। लक्ष्य उस कुल दूरी को कम करना है जो लोगों को निकटतम सुविधा तक पहुँचने के लिए तय करनी पड़ती है। इसे p-मीडियन (p-median) समस्या के रूप में जाना जाता है। क्योंकि संभावित समाधानों का परिदृश्य बहुत विशाल और असमान है, जो अनगिनत स्थानीय शिखरों (local peaks) से भरा है जो सबसे अच्छे उत्तर की तरह दिखते हैं लेकिन वास्तव में केवल जाल हैं, शोधकर्ता एक रणनीति पर भरोसा करते हैं जिसे मल्टी-स्टार्ट प्रक्रिया कहा जाता है। कल्पना कीजिए कि कोहरे से भरी पर्वत श्रृंखला में उच्चतम बिंदु खोजने की कोशिश कर रहे हैं, जिसमें एक हाइकर को एक यादृच्छिक स्थान पर छोड़ दिया जाता है, उसे तब तक चढ़ने दिया जाता है जब तक कि वह और ऊपर नहीं जा सकता, और फिर इस प्रक्रिया को विभिन्न शुरुआती बिंदुओं से हजारों बार दोहराया जाता है। उन सभी प्रयासों में से पाया गया सबसे अच्छा शिखर आमतौर पर सही उत्तर होता है। हालाँकि, हजारों प्रयासों के बाद भी, हाइकर वास्तविक शिखर को मिस कर सकते हैं क्योंकि परिदृश्य बहुत जटिल है।

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

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

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

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

शोधकर्ता यह सुनिश्चित करने के लिए सावधान थे कि इस मिश्रण प्रक्रिया में खर्च किया गया अतिरिक्त समय नगण्य हो। चूंकि मिश्रण द्वारा बनाए गए नए शुरुआती बिंदु पहले से ही उच्च-गुणवत्ता वाले समाधान होते हैं, इसलिए सुधार एल्गोरिदम एक यादृच्छिक शुरुआती बिंदु की तुलना में स्थानीय इष्टतम पर बहुत तेजी से अभिसरित (converge) होता है। POST विधि के लिए आवश्यक कुल समय मानक मल्टी-स्टार्ट दृष्टिकोण की तुलना में केवल थोड़ा ही अधिक था, फिर भी इसने लगातार बेहतर परिणाम दिए। समान (uniform) परीक्षण मामलों के लिए, नए तरीके ने सर्वोत्तम ज्ञात समाधानों में औसतन 0.062 प्रतिशत का सुधार किया, और गैर-समान (non-uniform) मामलों के लिए, 0.068 प्रतिशत का सुधार किया। हालांकि ये प्रतिशत छोटे लग सकते हैं, लेकिन बड़े पैमाने के लॉजिस्टिक्स और सुविधा नियोजन के संदर्भ में, वे दूरी और लागत में महत्वपूर्ण बचत का प्रतिनिधित्व करते हैं।

अध्ययन ने इस दृष्टिकोण की सीमाओं का भी पता लगाया। शोधकर्ताओं ने उल्लेख किया कि यदि मल्टी-स्टार्ट प्रक्रिया ने पहले ही पूर्ण इष्टतम समाधान पा लिया होता, तो POST विधि इसमें और सुधार नहीं कर पाती। हालांकि, चूंकि p-मीडियन समस्या के लाखों स्थानीय इष्टतम होने की ज्ञात है, इसलिए यह बहुत कम संभावना है कि एक मानक खोज संयोग से पूर्ण उत्तर पा लेगी। तथ्य यह है कि POST ने हर एक मामले में परिणामों में सुधार किया, यह सुझाव देता है कि मानक खोजें वास्तव में स्थानीय शिखरों पर फंस रही थीं जिनसे POST बचने में सक्षम था। शोधकर्ताओं ने यह भी देखा कि एक ही बैच में प्रारंभिक खोजों की संख्या बढ़ाने से हमेशा बेहतर परिणाम नहीं मिले; वास्तव में, अधिक पुनरावृत्ति वाले छोटे बैचों ने बेहतर प्रदर्शन किया। यह उनके एक सिद्धांत का समर्थन करता जिसे वे "कम ही अधिक है" (Less is More) कहते हैं, जो यह सुझाव देता है कि कुछ आशाजनक क्षेत्रों को गहराई से और बार-बार खोजना, एक बार व्यापक जाल फेंकने और सबसे अच्छे की उम्मीद करने की तुलना में अधिक प्रभावी है।

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

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