तब्बू सर्च

तब्बू खोज (टीएस) एक मेटाह्यूरिस्टिक खोज विधि है जो अनुकूलन (गणित) के लिए उपयोग की जाने वाली स्थानीय खोज (अनुकूलन) विधियों को नियोजित करती है। इसे 1986 में फ्रेड डब्ल्यू ग्लोवर द्वारा बनाया गया था^[1] और 1989 में औपचारिक रूप दिया गया।^[2]^[3] स्थानीय (पड़ोस) खोजें किसी समस्या का संभावित समाधान लेती हैं और एक बेहतर समाधान खोजने की उम्मीद में उसके निकटतम पड़ोसियों (अर्थात, बहुत कम छोटी-छोटी जानकारियों को छोड़कर समान समाधान) की जांच करती हैं। स्थानीय खोज विधियों में उप-इष्टतम क्षेत्रों या पठारों में फंसने की प्रवृत्ति होती है जहां कई समाधान समान रूप से फिट होते हैं।

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

टैबू खोज का कार्यान्वयन मेमोरी संरचनाओं का उपयोग करता है जो विज़िट किए गए समाधानों या उपयोगकर्ता द्वारा प्रदत्त नियमों के सेट का वर्णन करता है।^[2]यदि किसी संभावित समाधान का पहले एक निश्चित अल्पकालिक अवधि के भीतर दौरा किया गया है या यदि उसने किसी नियम का उल्लंघन किया है, तो इसे वर्जित (निषिद्ध) के रूप में चिह्नित किया जाता है ताकि कलन विधि उस संभावना पर बार-बार विचार न करे।

पृष्ठभूमि

Taboo#Etymology शब्द टोंगन भाषा के शब्द से आया है जो उन चीजों को इंगित करता है जिन्हें छुआ नहीं जा सकता क्योंकि वे पवित्र हैं।^[4] तब्बू खोज एक मेटाह्यूरिस्टिक एल्गोरिदम है जिसका उपयोग संयोजन अनुकूलन समस्याओं (ऐसी समस्याएं जहां इष्टतम क्रम और विकल्पों का चयन वांछित है) को हल करने के लिए किया जा सकता है।

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

मूल विवरण

तब्बू खोज एक संभावित समाधान से पुनरावृत्तीय रूप से आगे बढ़ने के लिए स्थानीय खोज (अनुकूलन) खोज प्रक्रिया का उपयोग करती है $x$ एक बेहतर समाधान के लिए $x'$ के पड़ोस में $x$ , जब तक कि कुछ रोक मानदंड संतुष्ट नहीं हो जाते (आम तौर पर, एक प्रयास सीमा या स्कोर सीमा)। स्थानीय खोज प्रक्रियाएँ अक्सर खराब स्कोर वाले क्षेत्रों या उन क्षेत्रों में अटक जाती हैं जहाँ स्कोर पठार होता है। इन नुकसानों से बचने और ऊर्जा कार्य के उन क्षेत्रों का पता लगाने के लिए जिन्हें अन्य स्थानीय खोज प्रक्रियाओं द्वारा अनदेखा छोड़ दिया जाएगा, जैसे-जैसे खोज आगे बढ़ती है, टैबू खोज प्रत्येक समाधान के पड़ोस का सावधानीपूर्वक पता लगाती है। नए पड़ोस में स्वीकार किए गए समाधान, $N^{*}(x)$ , स्मृति संरचनाओं के उपयोग के माध्यम से निर्धारित किए जाते हैं। इन मेमोरी संरचनाओं का उपयोग करते हुए, खोज वर्तमान समाधान से पुनरावृत्तीय रूप से आगे बढ़ती है $x$ एक बेहतर समाधान के लिए $x'$ में $N^{*}(x)$ .

तब्बू खोज में तैयार किए हुयी धातु पे पानी चढाने की कला के साथ कई समानताएं हैं, क्योंकि दोनों में संभावित डाउनहिल चालें शामिल हैं। वास्तव में, सिम्युलेटेड एनीलिंग को टीएस के एक विशेष रूप के रूप में देखा जा सकता है, जिसके तहत हम स्नातक कार्यकाल का उपयोग करते हैं, यानी, एक निर्दिष्ट संभावना के साथ एक कदम वर्जित हो जाता है।

ये मेमोरी संरचनाएं टैबू सूची के रूप में जानी जाती हैं, नियमों और प्रतिबंधित समाधानों का एक सेट जो फ़िल्टर करने के लिए उपयोग किया जाता है कि कौन से समाधान पड़ोस में स्वीकार किए जाएंगे $N^{*}(x)$ खोज द्वारा पता लगाया जाना है। अपने सरलतम रूप में, टैबू सूची उन समाधानों का एक अल्पकालिक सेट है जिन्हें हाल ही में देखा गया है (इससे कम) $n$ पुनरावृत्तियाँ पहले, कहाँ $n$ संग्रहीत किए जाने वाले पिछले समाधानों की संख्या है - इसे टैबू कार्यकाल भी कहा जाता है)। आमतौर पर, टैबू सूची में ऐसे समाधान शामिल होते हैं जो एक समाधान से दूसरे समाधान में जाने की प्रक्रिया के कारण बदल गए हैं। विवरण में आसानी के लिए किसी "समाधान" को कोडित करना और ऐसी विशेषताओं द्वारा प्रस्तुत करना समझना सुविधाजनक है।

मेमोरी के प्रकार

टैबू खोज में उपयोग की जाने वाली मेमोरी संरचनाओं को मोटे तौर पर तीन श्रेणियों में विभाजित किया जा सकता है:^[6]

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

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

पारंपरिक स्थानीय खोज विधियों द्वारा पाए गए समाधानों से बेहतर समाधान प्राप्त करने के लिए अकेले अल्पकालिक स्मृति पर्याप्त हो सकती है, लेकिन कठिन समस्याओं को हल करने के लिए मध्यवर्ती और दीर्घकालिक संरचनाएं अक्सर आवश्यक होती हैं।^[7] तब्बू खोज को अक्सर अन्य मेटाह्यूरिस्टिक तरीकों के मुकाबले बेंचमार्क किया जाता है - जैसे कि सिम्युलेटेड एनीलिंग, जेनेटिक एल्गोरिद्म, चींटी कॉलोनी अनुकूलन एल्गोरिदम, प्रतिक्रियाशील खोज अनुकूलन, निर्देशित स्थानीय खोज, या लालची यादृच्छिक अनुकूली खोज प्रक्रिया। इसके अलावा, हाइब्रिड विधियां बनाने के लिए टैबू खोज को कभी-कभी अन्य मेटाह्यूरिस्टिक्स के साथ जोड़ा जाता है। सबसे आम टैबू खोज हाइब्रिड टीएस को स्कैटर खोज के साथ जोड़ने से उत्पन्न होता है,^[8]^[9] जनसंख्या-आधारित प्रक्रियाओं का एक वर्ग जिसकी जड़ें टैबू खोज के साथ समान हैं, और अक्सर बड़े गैर-रेखीय अनुकूलन समस्याओं को हल करने में नियोजित किया जाता है।

स्यूडोकोड

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

sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(bestCandidate)
    bestCandidate ← sNeighborhood[0]
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
            bestCandidate ← sCandidate
        end
    end
    if (fitness(bestCandidate) > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest

पंक्तियाँ 1-4 कुछ प्रारंभिक सेटअप का प्रतिनिधित्व करती हैं, क्रमशः एक प्रारंभिक समाधान (संभवतः यादृच्छिक रूप से चुना गया) बनाना, उस प्रारंभिक समाधान को आज तक देखे गए सबसे अच्छे के रूप में सेट करना, और इस प्रारंभिक समाधान के साथ एक टैबू सूची प्रारंभ करना। इस उदाहरण में, टैबू सूची केवल एक अल्पकालिक स्मृति संरचना है जिसमें देखे गए राज्यों के तत्वों का रिकॉर्ड होगा।

कोर एल्गोरिथम लूप लाइन 5 में शुरू होता है। यह लूप एक इष्टतम समाधान की खोज तब तक जारी रखेगा जब तक कि उपयोगकर्ता द्वारा निर्दिष्ट स्टॉपिंग स्थिति पूरी नहीं हो जाती (ऐसी स्थितियों के दो उदाहरण एक साधारण समय सीमा या फिटनेस स्कोर पर एक सीमा है)। पंक्ति 9 में टैबू तत्वों के लिए पड़ोसी समाधानों की जाँच की जाती है। इसके अतिरिक्त, एल्गोरिथ्म पड़ोस में सबसे अच्छे समाधान का ट्रैक रखता है, जो टैबू नहीं है।

फिटनेस फ़ंक्शन आम तौर पर एक गणितीय फ़ंक्शन होता है, जो एक अंक लौटाता है या आकांक्षा मानदंड संतुष्ट होते हैं - उदाहरण के लिए, एक आकांक्षा मानदंड पर विचार किया जा सकता है क्योंकि एक नया खोज स्थान पाया जाता है^[4]). यदि सर्वश्रेष्ठ स्थानीय उम्मीदवार का फिटनेस मूल्य वर्तमान सर्वश्रेष्ठ (पंक्ति 13) से अधिक है, तो इसे नए सर्वश्रेष्ठ (पंक्ति 14) के रूप में सेट किया गया है। स्थानीय सर्वश्रेष्ठ उम्मीदवार को हमेशा टैबू सूची (पंक्ति 16) में जोड़ा जाता है और यदि टैबू सूची पूरी हो जाती है (पंक्ति 17), तो कुछ तत्वों को समाप्त होने की अनुमति दी जाएगी (पंक्ति 18)। आम तौर पर, तत्व सूची से उसी क्रम में समाप्त होते हैं जिस क्रम में उन्हें जोड़ा जाता है। स्थानीय इष्टतम से बचने के लिए प्रक्रिया सर्वश्रेष्ठ स्थानीय उम्मीदवार का चयन करेगी (हालाँकि इसकी फिटनेस sBest से भी बदतर है)।

यह प्रक्रिया तब तक जारी रहती है जब तक उपयोगकर्ता द्वारा निर्दिष्ट रोक मानदंड पूरा नहीं हो जाता, जिस बिंदु पर, खोज प्रक्रिया के दौरान देखा गया सबसे अच्छा समाधान वापस आ जाता है (पंक्ति 21)।

उदाहरण: ट्रैवलिंग सेल्समैन की समस्या

ट्रैवलिंग सेल्समैन समस्या (टीएसपी) का उपयोग कभी-कभी टैबू खोज की कार्यक्षमता दिखाने के लिए किया जाता है।^[7]यह समस्या एक सीधा सवाल खड़ा करती है: शहरों की सूची को देखते हुए, हर शहर तक जाने वाला सबसे छोटा मार्ग कौन सा है? उदाहरण के लिए, यदि शहर ए और शहर बी एक-दूसरे के बगल में हैं, जबकि शहर सी दूर है, तो शहर सी का दौरा करने से पहले शहर ए और बी का एक के बाद एक दौरा करने पर यात्रा की गई कुल दूरी कम होगी। एक इष्टतम समाधान खोजने के बाद से एनपी कठिन है, अनुमान-आधारित सन्निकटन विधियां (जैसे स्थानीय खोज) निकटतम-इष्टतम समाधान तैयार करने के लिए उपयोगी हैं। अच्छे टीएसपी समाधान प्राप्त करने के लिए, ग्राफ़ संरचना का दोहन करना आवश्यक है। समस्या संरचना के दोहन का मूल्य मेटाह्यूरिस्टिक तरीकों में एक आवर्ती विषय है, और टैबू खोज इसके लिए उपयुक्त है। टैबू खोज से जुड़ी रणनीतियों की एक श्रेणी जिसे इजेक्शन चेन विधियां कहा जाता है, ने उच्च गुणवत्ता वाले टीएसपी समाधान कुशलतापूर्वक प्राप्त करना संभव बना दिया है ^[10] दूसरी ओर, ट्रैवलिंग सेल्समैन की समस्या के लिए एक संतोषजनक समाधान खोजने के लिए एक सरल टैबू खोज का उपयोग किया जा सकता है (अर्थात्, एक समाधान जो पर्याप्तता मानदंड को पूरा करता है, हालांकि ग्राफ़ संरचना का शोषण करके प्राप्त उच्च गुणवत्ता के साथ नहीं)। खोज एक प्रारंभिक समाधान के साथ शुरू होती है, जिसे यादृच्छिक रूप से या किसी प्रकार के निकटतम पड़ोसी एल्गोरिदम के अनुसार उत्पन्न किया जा सकता है। नए समाधान बनाने के लिए, संभावित समाधान में दो शहरों का दौरा करने का क्रम बदल दिया जाता है। सभी शहरों के बीच की कुल यात्रा दूरी का उपयोग यह निर्धारित करने के लिए किया जाता है कि एक समाधान दूसरे की तुलना में कितना आदर्श है। चक्रों को रोकने के लिए - यानी, समाधानों के एक विशेष सेट पर बार-बार जाना - और स्थानीय ऑप्टिमा में फंसने से बचने के लिए, एक समाधान को टैबू सूची में जोड़ा जाता है यदि इसे समाधान पड़ोस में स्वीकार किया जाता है, $N^{*}(x)$ .

नए समाधान तब तक बनाए जाते हैं जब तक कुछ रोक मानदंड, जैसे कि पुनरावृत्तियों की मनमानी संख्या, पूरी नहीं हो जाती। एक बार जब सरल टैबू खोज बंद हो जाती है, तो यह अपने निष्पादन के दौरान पाया गया सर्वोत्तम समाधान लौटाता है।

संदर्भ

↑ Fred Glover (1986). "इंटीजर प्रोग्रामिंग के लिए भविष्य के रास्ते और आर्टिफिशियल इंटेलिजेंस से लिंक". Computers and Operations Research. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1.
↑ ^2.0 ^2.1 Fred Glover (1989). "Tabu Search – Part 1". ORSA Journal on Computing. 1 (2): 190–206. doi:10.1287/ijoc.1.3.190.
↑ Fred Glover (1990). "Tabu Search – Part 2". ORSA Journal on Computing. 2 (1): 4–32. doi:10.1287/ijoc.2.1.4.
↑ ^4.0 ^4.1 "Courses" (PDF).
↑ F. Glover; M. Laguna (1997). तब्बू खोज. Kluwer Academic Publishers. ISBN 978-1-4613-7987-4.
↑ Fred Glover (1990). "Tabu Search: A Tutorial". Interfaces.
↑ ^7.0 ^7.1 M. Malek; M. Huruswamy; H. Owens; M. Pandya (1989). "Serial and parallel search techniques for the traveling salesman problem". Annals of OR: Linkages with Artificial Intelligence.
↑ F. Glover, M. Laguna & R. Marti (2000). "Fundamentals of Scatter Search and Path Relinking". Control and Cybernetics. 29 (3): 653–684.
↑ M. Laguna & R. Marti (2003). Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers. ISBN 9781402073762.
↑ D. Gamboa, C. Rego & F. Glover (2005). "Data Structures and Ejection Chains for Solving Large Scale Traveling Salesman Problems". European Journal of Operational Research. 160 (1): 154–171. CiteSeerX 10.1.1.417.9789. doi:10.1016/j.ejor.2004.04.023.

बाहरी संबंध

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

| below =

Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

| below =* सॉफ्टवेयर

}}

[glover86-1] Fred Glover (1986). "इंटीजर प्रोग्रामिंग के लिए भविष्य के रास्ते और आर्टिफिशियल इंटेलिजेंस से लिंक". Computers and Operations Research. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1.

[glover89-2] 2.0 ^2.1 Fred Glover (1989). "Tabu Search – Part 1". ORSA Journal on Computing. 1 (2): 190–206. doi:10.1287/ijoc.1.3.190.

[glover90-3] Fred Glover (1990). "Tabu Search – Part 2". ORSA Journal on Computing. 2 (1): 4–32. doi:10.1287/ijoc.2.1.4.

[ise.ncsu.edu-4] 4.0 ^4.1 "Courses" (PDF).

[gloverlaguna1997-5] F. Glover; M. Laguna (1997). तब्बू खोज. Kluwer Academic Publishers. ISBN 978-1-4613-7987-4.

[glover90b-6] Fred Glover (1990). "Tabu Search: A Tutorial". Interfaces.

[malek89-7] 7.0 ^7.1 M. Malek; M. Huruswamy; H. Owens; M. Pandya (1989). "Serial and parallel search techniques for the traveling salesman problem". Annals of OR: Linkages with Artificial Intelligence.

[glover2000-8] F. Glover, M. Laguna & R. Marti (2000). "Fundamentals of Scatter Search and Path Relinking". Control and Cybernetics. 29 (3): 653–684.

[laguna2003-9] M. Laguna & R. Marti (2003). Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers. ISBN 9781402073762.

[gamboa2005-10] D. Gamboa, C. Rego & F. Glover (2005). "Data Structures and Ejection Chains for Solving Large Scale Traveling Salesman Problems". European Journal of Operational Research. 160 (1): 154–171. CiteSeerX 10.1.1.417.9789. doi:10.1016/j.ejor.2004.04.023.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]