डीएए - हिल क्लाइम्बिंग एल्गोरिथम
पिछले अध्यायों में चर्चा किए गए एल्गोरिदम व्यवस्थित रूप से चलते हैं। लक्ष्य को प्राप्त करने के लिए, समाधान की ओर एक या एक से अधिक पहले से खोजे गए मार्ग को इष्टतम समाधान खोजने के लिए संग्रहीत करने की आवश्यकता है।
कई समस्याओं के लिए, लक्ष्य के लिए रास्ता अप्रासंगिक है। उदाहरण के लिए, एन-क्वींस समस्या में, हमें रानियों के अंतिम विन्यास के साथ-साथ रानियों को जोड़ने के आदेश की परवाह करने की आवश्यकता नहीं है।
पहाड़ी की चढ़ाई
हिल क्लाइम्बिंग कुछ अनुकूलन समस्याओं को हल करने की एक तकनीक है। इस तकनीक में, हम एक उप-इष्टतम समाधान के साथ शुरू करते हैं और समाधान को बार-बार सुधारा जाता है जब तक कि किसी स्थिति को अधिकतम नहीं किया जाता है।
उप-इष्टतम समाधान के साथ शुरू करने के विचार की तुलना पहाड़ी के आधार से शुरू करने से की जाती है, समाधान में सुधार करने की तुलना पहाड़ी पर चलने से की जाती है, और अंत में कुछ स्थिति को अधिकतम करने की तुलना पहाड़ी के शीर्ष पर पहुंचने से की जाती है।
इसलिए, पहाड़ी चढ़ाई तकनीक को निम्न चरणों के रूप में माना जा सकता है -
- एक उप-इष्टतम समाधान का निर्माण समस्या की बाधाओं का पालन करना
- चरण-दर-चरण समाधान में सुधार
- समाधान में सुधार जब तक कोई और सुधार संभव नहीं है
पहाड़ी चढ़ाई तकनीक का उपयोग मुख्य रूप से कम्प्यूटेशनल रूप से कठिन समस्याओं को हल करने के लिए किया जाता है। यह केवल वर्तमान स्थिति और तत्काल भविष्य की स्थिति को देखता है। इसलिए, यह तकनीक मेमोरी कुशल है क्योंकि यह खोज ट्री को बनाए नहीं रखती है।
Algorithm: Hill Climbing
Evaluate the initial state.
Loop until a solution is found or there are no new operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal -→ quit
better than current state -→ new current state
Iterative सुधार
पुनरावृत्ति सुधार विधि में, प्रत्येक पुनरावृत्ति में एक इष्टतम समाधान की दिशा में प्रगति करके इष्टतम समाधान प्राप्त किया जाता है। हालांकि, यह तकनीक स्थानीय मैक्सिमा का सामना कर सकती है। इस स्थिति में, बेहतर समाधान के लिए पास की स्थिति नहीं है।
विभिन्न तरीकों से इस समस्या से बचा जा सकता है। इन तरीकों में से एक नकली एनालिंग है।
रैंडम रिस्टार्ट
यह स्थानीय ऑप्टिमा की समस्या को हल करने का एक और तरीका है। यह तकनीक खोजों की एक श्रृंखला आयोजित करती है। हर बार, यह एक यादृच्छिक रूप से उत्पन्न प्रारंभिक अवस्था से शुरू होता है। इसलिए, ऑप्टिमा या लगभग इष्टतम समाधान प्रदर्शन की गई खोजों के समाधान की तुलना करके प्राप्त किया जा सकता है।
हिल क्लाइम्बिंग तकनीक की समस्याएं
स्थानीय मैक्सिमा
यदि हेविस्टिक उत्तल नहीं है, तो ग्लोबल मैक्सिमा के बजाय हिल क्लाइम्बिंग स्थानीय मैक्सिमा में परिवर्तित हो सकती है।
पुलों और Alleys
यदि लक्ष्य फ़ंक्शन एक संकीर्ण रिज बनाता है, तो पर्वतारोही केवल रिज पर चढ़ सकता है या ज़िग-ज़ैगिंग द्वारा गली से उतर सकता है। इस परिदृश्य में, पर्वतारोही को लक्ष्य तक पहुंचने के लिए बहुत छोटे कदम उठाने की आवश्यकता होती है।
पठार
एक पठार का सामना तब किया जाता है जब खोज स्थान सपाट या पर्याप्त रूप से सपाट होता है कि लक्ष्य फ़ंक्शन द्वारा लौटाए गए मान पास के क्षेत्रों के लिए दिए गए मान से अप्रभेद्य होते हैं, मशीन द्वारा इसके मूल्य का प्रतिनिधित्व करने के लिए उपयोग की गई परिशुद्धता के कारण।
पहाड़ी चढ़ाई तकनीक की जटिलता
यह तकनीक अंतरिक्ष से संबंधित मुद्दों से ग्रस्त नहीं है, क्योंकि यह केवल वर्तमान स्थिति में दिखता है। पहले खोजे गए पथ संग्रहीत नहीं हैं।
रैंडम-पुनरारंभ हिल क्लाइम्बिंग तकनीक में अधिकांश समस्याओं के लिए, बहुपद समय में एक इष्टतम समाधान प्राप्त किया जा सकता है। हालांकि, एनपी-पूर्ण समस्याओं के लिए, कम्प्यूटेशनल समय स्थानीय मैक्सिमा की संख्या के आधार पर घातीय हो सकता है।
हिल क्लाइम्बिंग तकनीक के अनुप्रयोग
हिल क्लाइम्बिंग तकनीक का उपयोग कई समस्याओं को हल करने के लिए किया जा सकता है, जहां वर्तमान स्थिति नेटवर्क-प्रवाह, ट्रैवलिंग सेल्समैन समस्या, 8-क्वींस समस्या, एकीकृत सर्किट डिजाइन, आदि जैसे सटीक मूल्यांकन फ़ंक्शन की अनुमति देती है।
हिल क्लाइम्बिंग का उपयोग आगमनात्मक शिक्षण विधियों में भी किया जाता है। इस तकनीक का उपयोग रोबोटिक्स में एक टीम में कई रोबोटों के बीच समन्वय के लिए किया जाता है। कई अन्य समस्याएं हैं जहां इस तकनीक का उपयोग किया जाता है।
उदाहरण
ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए इस तकनीक को लागू किया जा सकता है। पहले एक प्रारंभिक समाधान निर्धारित किया जाता है कि सभी शहरों में एक बार ठीक से जाना जाता है। इसलिए, यह प्रारंभिक समाधान अधिकांश मामलों में इष्टतम नहीं है। यहां तक कि यह समाधान बहुत खराब हो सकता है। हिल क्लाइम्बिंग एल्गोरिथ्म इस तरह के एक प्रारंभिक समाधान के साथ शुरू होता है और पुनरावृत्त तरीके से इसमें सुधार करता है। आखिरकार, बहुत कम मार्ग प्राप्त होने की संभावना है।