A New Meta-Heuristic for Improving General Multi-Start Procedures, With an Application to the Planar p-Median Location Problem

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

दशकों से, शोधकर्ता एक रणनीति का उपयोग कर रहे हैं जिसे मल्टी-स्टार्ट (Multi-Start) कहा जाता है। इसे ऐसे समझें जैसे आपने 800,000 अलग-अलग स्काउट्स (या 800,000 अलग-अलग पिज्जा डिलीवरी रूट) को काम पर रखा है जो यादृच्छिक (random) स्थानों से पूरे शहर में दौड़ रहे हैं। प्रत्येक स्काउट तब तक दौड़ता है जब तक वह किसी स्थानीय पहाड़ी पर फंस नहीं जाता, और फिर आप उन सभी में से सबसे अच्छे परिणाम को चुनते हैं। यह काम करता है, लेकिन यह एक बोर्ड पर दस लाख डार्ट्स फेंकने और उम्मीद करने जैसा है कि उनमें से एक बुल्सआई (bullseye) पर लग जाए।

नई तरकीब: "एलीट स्क्वाड" और "बेबी स्टेप्स"

लेखक, ज़वी ड्रेज़नर और जैक ब्रिमबर्ग, एक चतुर नई मेटा-ह्यूरिस्टिक (एक स्मार्ट नियम) प्रस्तावित करते हैं जिसे RPT (जिसका अर्थ है रिपीटेड POST) कहा जाता है। वे तर्क देते हैं कि अपने 800,000 स्काउट्स से केवल एक सबसे अच्छा परिणाम रखने के बजाय, आपको शीर्ष 5 सबसे अच्छे परिणामों की एक छोटी "एलीट स्क्वाड" (Elite Squad) रखनी चाहिए।

यहाँ जादू वाला हिस्सा है:

1. मिक्स-एंड-मैच (Mix-and-Match): दो अलग-अलग "एलीट" समाधानों (पिज्जा दुकानों के दो अलग सेट) को लें। कल्पना करें कि वे माता-पिता हैं।
2. संतान बनाना (Creating Offspring): शहर के बीच से एक रेखा खींचें। माता-पिता A के उन दुकानों को लें जो रेखा के एक तरफ हैं, और माता-पिता B के उन दुकानों को लें जो दूसरी तरफ हैं। आपने अभी-अभी एक नया "बच्चा" समाधान बना लिया है—एक हाइब्रिड मैप जो दोनों माता-पिता के सबसे अच्छे हिस्सों को जोड़ता है।
3. पॉलिश करना (The Polish): इस नए "बच्चे" पर मानक सुधार एल्गोरिदम चलाएं। हो सकता है कि वह एक नई पहाड़ी पर फंस जाए, लेकिन वह एक ऊंची पहाड़ी हो सकती है जो पहले वाली से बेहतर हो।
4. दोहराना (Repeat): यदि यह नया "बच्चा" आपके वर्तमान सबसे अच्छे समाधान से बेहतर है, तो आप उसे एलीट स्क्वाड में रखते हैं और फिर से दूसरों के साथ मिलाने की कोशिश करते हैं। आप इसे तब तक करते रहते हैं जब तक कि आपको कोई बेहतर "बच्चा" न मिल जाए।

पेपर में प्रारंभिक मिक्सिंग चरण को POST (एक पोस्ट-ऑप्टिमाइज़िंग स्टेप) कहा गया है। पूर्ण RPT रणनीति इस प्रक्रिया को एक कदम आगे ले जाती है। एक ही बड़े बैच में 800,000 स्काउट्स चलाने के बजाय, यह काम को छोटे बैचों में विभाजित करती है। यह POST प्रक्रिया को एक छोटे समूह पर चलाती है, सबसे अच्छे 5 को ढूंढती है, उन्हें मिलाती है, और फिर इस पूरे चक्र को कई बार दोहराती है (विशेष रूप से, उनके सबसे अच्छे परीक्षणों में 700 बार)।

उन्होंने क्या पाया (और क्या नहीं)

उन्होंने 48 अलग-अलग शहर के मानचित्रों पर इसका परीक्षण किया (24 समान रूप से फैले ग्राहकों वाले, और 24 बिखरे हुए, असमान समूहों वाले)। उन्होंने दो अलग-अलग "स्काउट" एल्गोरिदम का उपयोग किया: क्लासिक ALT (कूपर का पुराना तरीका) और एक नया, अधिक उन्नत तरीका जिसे CLUST कहा जाता है।

• परिणाम: हर एक 48 टेस्ट केस में, RPT(CLUST) विधि ने मानक मल्टी-स्टार्ट दृष्टिकोण की तुलना में बेहतर समाधान खोजा। (नोट: मानक RPT(ALT) विधि ने परिणामों में महत्वपूर्ण सुधार किया लेकिन सभी 48 मामलों में नए सर्वश्रेष्ठ-ज्ञात समाधान नहीं खोजे; यह विशिष्ट उपलब्धि CLUST एल्गोरिदम के साथ जोड़े जाने पर RPT विधि को मिली है)।
• गति: यहाँ मुख्य बात यह है कि इस मिक्सिंग और मैचिंग में लगने वाला अतिरिक्त समय लगभग नगण्य था। 24 समान वितरण वाले उदाहरणों के लिए, मानक ALT विधि चलाने का औसत समय लगभग 257.68 मिनट था। RPT विधि ने लगभग 257.45 मिनट लिए। उन्होंने लगभग उतने ही समय में बेहतर परिणाम प्राप्त किए।
• सुधार: मानक ALT विधि के लिए, समाधान औसतन सर्वश्रेष्ठ ज्ञात परिणामों से 0.80% खराब थे। RPT ने इसे घटाकर 0.53% कर दिया। कुछ विशिष्ट मामलों में, सुधार बहुत बड़ा था, जिसने त्रुटि को 60% या 70% से अधिक कम कर दिया।

जब उन्होंने नए, धीमे CLUST एल्गोरिदम का उपयोग किया, तो परिणाम और भी प्रभावशाली थे। मानक CLUST विधि ने पहले से ही बहुत अच्छे समाधान खोजे थे, लेकिन RPT ने सभी 24 समान (uniform) मामलों और सभी 24 गैर-समान (non-uniform) मामलों के लिए नए सर्वश्रेष्ठ-ज्ञात समाधान खोजे। वास्तव में, समान परीक्षणों के लिए, RPT विधि ने एक विशिष्ट सेटिंग (I = 1,000) के साथ, 24 में से 14 मामलों में अपने आप में सर्वश्रेष्ठ ज्ञात समाधान खोजा। यदि आप विभिन्न सेटिंग्स (I=1,000 और I=10,000) के परिणामों को मिलाते हैं, तो नया सर्वश्रेष्ठ ज्ञात समाधान 24 में से 21 मामलों में पाया गया। गैर-समान परीक्षणों के लिए, RPT विधि ने अकेले ही 24 में से 13 मामलों में सर्वश्रेष्ठ ज्ञात समाधान खोजा, और यदि आपने विभिन्न सेटिंग्स के परिणामों को मिलाया, तो इसने सभी 24 मामलों में सर्वश्रेष्ठ ज्ञात समाधान खोजा।

वे क्या खारिज करते हैं

पेपर स्पष्ट रूप से बताता है कि यह विधि क्या नहीं है।

• यह कोई जादुई छड़ी नहीं है जो हर बार परफेक्ट ग्लोबल ऑप्टिममम की गारंटी देती है। लेखक स्पष्ट रूप से कहते हैं: "यदि मल्टी-स्टार्ट ह्यूरिस्टिक अनुकूलतम समाधान खोज लेता है, तो निश्चित रूप से RPT उसमें सुधार नहीं कर सकता।" यदि आपने पहले ही पूर्णतः सर्वोत्तम उत्तर खोज लिया है, तो RPT उसे बेहतर नहीं बना सकता।
• यह ऐसा तरीका नहीं है जिसके लिए आपको कंप्यूटर को कई दिनों तक चलाने की आवश्यकता हो। वे तर्क देते हैं कि अतिरिक्त समय "नगण्य" है।
• वे यह भी सुझाव देते हैं कि आपको "परफेक्ट" पैरामीटर (जैसे कि कितने स्काउट्स का उपयोग करना है) खोजने के लिए जुनूनी होने की आवश्यकता नहीं है। उन्होंने विभिन्न समूह आकारों (जैसे 1,000 बनाम 10,000) का परीक्षण किया और पाया कि वे समान रूप से प्रदर्शन करते हैं, जिससे पता चलता है कि "उचित मापदंडों का कोई भी चयन समान रूप से अच्छा प्रदर्शन करेगा।"

वे कितने आश्वस्त हैं?

लेखक अपने नंबरों को लेकर बहुत आश्वस्त हैं क्योंकि उन्होंने इंटेल i7 प्रोसेसर वाले डेस्कटॉप कंप्यूटर पर वास्तविक सिमुलेशन चलाए। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने परिणामों को मापा।

• उन्होंने सांख्यिकीय परीक्षणों (पेयर्ड टी-टेस्ट) का उपयोग किया और पाया कि सुधार सांख्यिकीय रूप से महत्वपूर्ण थे (p-वैल्यू $6.7 \times 10^{-5}$ जितनी कम थी)।
• वे दावा करते हैं कि यह विधि "सामान्य मल्टी-स्टार्ट सुधार एल्गोरिदम" के लिए काम करती है, लेकिन उन्होंने इसे केवल प्लानर p-मीडियन समस्या पर प्रदर्शित किया है। वे सुझाव देते हैं कि यह अन्य समस्याओं (जैसे क्लस्टरिंग) पर भी काम कर सकती है, लेकिन उन्होंने अभी तक इसे साबित नहीं किया है।

मुख्य निष्कर्ष (Takeaway)

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

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