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