स्थानीय खोज (अनुकूलन)

कंप्यूटर विज्ञान में, स्थानीय खोज कम्प्यूटेशनल रूप से कठिन गणितीय अनुकूलन समस्याओं को हल करने के लिए एक अनुमानी पद्धति है। स्थानीय खोज का उपयोग उन समस्याओं पर किया जा सकता है जिन्हें कई उम्मीदवार समाधानों के बीच मानदंड को अधिकतम करने वाले समाधान को खोजने के रूप में तैयार किया जा सकता है। स्थानीय खोज एल्गोरिदम स्थानीय परिवर्तनों को लागू करके उम्मीदवार समाधान ("खोज स्थान") के स्थान पर समाधान से समाधान की ओर बढ़ते हैं, जब तक कि इष्टतम माना जाने वाला समाधान नहीं मिल जाता है या समय सीमा समाप्त नहीं हो जाती है।

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

उदाहरण

कुछ समस्याएँ जहाँ स्थानीय खोज लागू की गई हैं:

1. [[ वर्टेक्स कवर समस्या ]], जिसमें एक समाधान एक ग्राफ (असतत गणित) का एक वर्टेक्स कवर है, और लक्ष्य न्यूनतम संख्या में नोड्स के साथ एक समाधान खोजना है
2. ट्रैवलिंग सेल्समैन की समस्या, जिसमें एक समाधान एक चक्र (ग्राफ सिद्धांत) है जिसमें ग्राफ के सभी नोड होते हैं और लक्ष्य चक्र की कुल लंबाई को कम करना है
3. बूलियन संतुष्टि समस्या, जिसमें एक उम्मीदवार समाधान एक सत्य असाइनमेंट है, और लक्ष्य असाइनमेंट द्वारा संतुष्ट क्लॉज (तर्क) की संख्या को अधिकतम करना है; इस मामले में, अंतिम समाधान तभी उपयोगी होता है जब वह सभी खंडों को संतुष्ट करता हो
4. नर्स शेड्यूलिंग समस्या जहां एक समाधान पाली में काम के लिए नर्सों का असाइनमेंट है जो सभी स्थापित बाधा संतुष्टि को संतुष्ट करता है
5. कश्मीर Medoid क्लस्टरिंग समस्या और अन्य संबंधित सुविधा स्थान समस्याएं जिनके लिए स्थानीय खोज सबसे खराब स्थिति के दृष्टिकोण से सबसे अच्छा ज्ञात सन्निकटन अनुपात प्रदान करती है
6. हॉपफील्ड न्यूरल नेटवर्क्स समस्या जिसके लिए हॉपफील्ड नेटवर्क में स्थिर कॉन्फ़िगरेशन ढूंढा जा रहा है।

विवरण

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

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

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

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

शूरमैन और साउथी स्थानीय खोज (गहराई, गतिशीलता और कवरेज) के लिए प्रभावशीलता के तीन उपाय प्रस्तावित करते हैं: * गहराई: वर्तमान (सर्वश्रेष्ठ) समाधान की लागत;

• गतिशीलता: खोज स्थान के विभिन्न क्षेत्रों में तेजी से जाने की क्षमता (लागत कम रखते हुए);
• कवरेज: खोज कैसे व्यवस्थित रूप से खोज स्थान को कवर करती है, किसी भी अनछुए असाइनमेंट और सभी विज़िट किए गए असाइनमेंट के बीच की अधिकतम दूरी।

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

यह भी देखें

स्थानीय खोज निम्न का एक उप-क्षेत्र है:

• मेटाह्यूरिस्टिक्स
• स्टोकेस्टिक अनुकूलन
• गणितीय अनुकूलन

स्थानीय खोज में फ़ील्ड शामिल हैं:

• पहाड़ी की चढ़ाई
• सिम्युलेटेड एनीलिंग (स्थानीय या वैश्विक खोज के लिए उपयुक्त)
• तब्बू खोज
• देर से स्वीकृति पहाड़ी चढ़ाई
• प्रतिक्रियाशील खोज अनुकूलन (यंत्र अधिगम और स्थानीय खोज अनुमानों का संयोजन)

वास्तविक-मूल्यवान खोज-स्थान

वास्तविक संख्या की स्थानीय खोज करने के लिए कई विधियाँ मौजूद हैं | वास्तविक-मूल्यवान खोज-स्थान:

• लुस-जाकोला एक समान वितरण (निरंतर) और तेजी से घटती खोज-श्रेणी का उपयोग करके स्थानीय रूप से खोज करता है।
• यादृच्छिक अनुकूलन एक सामान्य वितरण का उपयोग करके स्थानीय रूप से खोज करता है।
• यादृच्छिक खोज वर्तमान स्थिति के आसपास के अति क्षेत्र का नमूना लेकर स्थानीय रूप से खोज करती है।
• पैटर्न खोज (अनुकूलन)ऑप्टिमाइज़ेशन) तेजी से घटते स्टेप साइज़ का उपयोग करके सर्च-स्पेस के अक्ष के साथ कदम उठाता है।

ग्रन्थसूची

• Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0. Archived from the original on 2012-03-16.
• Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.
• Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal of Computing 33(3).
• Juraj Hromkovič: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics (Springer)
• Wil Michiels, Emile Aarts, Jan Korst: Theoretical Aspects of Local Search (Springer)