हेयुरिस्टिक

For other uses, see स्वानुभविक (विसंदिग्धीकरण).

गणितीय अनुकूलन और कंप्यूटर विज्ञान में, हेयुरिस्टिक, ग्रीक शब्द εὑρίσκω से उत्पन्न हुआ है जिसका अर्थ है 'खोज' यह ऐसी तकनीक है जिसे समस्या को अत्यधिक शीघ्रता से हल करने के लिए तब प्ररूपित किया गया जब पारंपरिक विधियां अनुमानित समाधान खोजने में बहुत धीमी थी या ये सटीक समाधान खोजने में विफल होती थी। यह इष्टतमता, पूर्णता, सटीकता या गति के लिए सटीकता के सापेक्ष प्राप्त किया जाता है। एक तरह से इसे लघुपथ के रूप मे संदर्भित किया जा सकता है।

एक हेयुरिस्टिक फलन, जिसे "ह्यूरिस्टिक" भी कहा जाता है, गणित मे एक फलन है जो उपलब्ध जानकारी के आधार पर खोज कलनविधियों में विकल्पों को स्तरीकृत करता है जिस से यह तय किया जा सके कि कौन सी शाखा का पालन करना है। उदाहरण के लिए, इसका प्रयोग सटीक समाधानों का अनुमान लगाने के लिए किया जा सकता है।

परिभाषा और प्रेरणा

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

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

सैद्धांतिक कंप्यूटर विज्ञान में एनपी-कठोरता के परिणाम विभिन्न प्रकार की जटिल अनुकूलन समस्याओं के लिए ह्यूरिस्टिक्स को एकमात्र व्यवहार्य विकल्प बनाते हैं जिन्हें वास्तविक दुनिया के अनुप्रयोगों में नियमित रूप से हल करने की आवश्यकता होती है।

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

ट्रेड-ऑफ

किसी समस्या को हल करने के लिए अनुमानी का उपयोग करना है या नहीं, यह तय करने के लिए ट्रेड-ऑफ मानदंड में निम्नलिखित शामिल हैं:

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

कुछ मामलों में, यह तय करना मुश्किल हो सकता है कि क्या ह्यूरिस्टिक द्वारा पाया गया समाधान काफी अच्छा है, क्योंकि ह्यूरिस्टिक्स में अंतर्निहित सिद्धांत बहुत विस्तृत नहीं है।

उदाहरण

सरल समस्या

एक अनुमानी से अपेक्षित कम्प्यूटेशनल प्रदर्शन लाभ प्राप्त करने का एक तरीका एक सरल समस्या को हल करना है जिसका समाधान भी प्रारंभिक समस्या का समाधान है।

ट्रैवलिंग सेल्समैन समस्या

ट्रैवलिंग सेल्समैन की समस्या (TSP) को हल करने के लिए सन्निकटन का एक उदाहरण जॉन बेंटले (कंप्यूटर वैज्ञानिक) द्वारा वर्णित किया गया है:

• शहरों की एक सूची और शहरों की प्रत्येक जोड़ी के बीच की दूरी को देखते हुए, सबसे छोटा संभव मार्ग कौन सा है जो प्रत्येक शहर में एक बार जाता है और मूल शहर में वापस आता है?

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

खोजें

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

नेवेल और साइमन: अनुमानी खोज परिकल्पना

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

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

एंटीवायरस सॉफ्टवेयर

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

नुकसान

कुछ अनुमानों का एक मजबूत अंतर्निहित सिद्धांत है; वे या तो सिद्धांत से टॉप-डाउन तरीके से प्राप्त होते हैं या प्रायोगिक या वास्तविक विश्व डेटा के आधार पर पहुंचे हैं। अन्य सिद्धांत की एक झलक के बिना वास्तविक दुनिया के अवलोकन या अनुभव के आधार पर केवल अंगूठे का नियम हैं। उत्तरार्द्ध बड़ी संख्या में नुकसान के संपर्क में हैं।

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

गलत परिणामों की संभावना का अनुमान लगाने के लिए अनुमानों को नियोजित करते समय सांख्यिकीय विश्लेषण किया जा सकता है। किसी खोज समस्या या नैपसैक समस्या को हल करने के लिए एक अनुमानी का उपयोग करने के लिए, यह जांचना आवश्यक है कि अनुमानी स्वीकार्य अनुमानी है। एक अनुमानी समारोह दिया $h(v_{i},v_{g})$ वास्तविक इष्टतम दूरी का अनुमान लगाने के लिए $d^{\star }(v_{i},v_{g})$ लक्ष्य नोड के लिए $v_{g}$ एक निर्देशित ग्राफ में $G$ युक्त $n$ लेबल किए गए कुल नोड या शीर्ष $v_{0},v_{1},\cdots ,v_{n}$, स्वीकार्य का अर्थ मोटे तौर पर यह है कि अनुमानी लक्ष्य की लागत या औपचारिक रूप से कम आंकता है $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ सभी के लिए $(v_{i},v_{g})$ कहाँ ${i,g}\in [0,1,...,n]$.

यदि एक अनुमानी स्वीकार्य नहीं है, तो यह कभी भी लक्ष्य को प्राप्त नहीं कर सकता है, या तो ग्राफ़ के मृत अंत में समाप्त हो सकता है $G$ या दो नोड्स के बीच आगे और पीछे लंघन करके $v_{i}$ और $v_{j}$ कहाँ ${i,j}\neq g$.

व्युत्पत्ति

19वीं सदी की शुरुआत में ह्यूरिस्टिक शब्द का प्रयोग शुरू हुआ। यह ग्रीक भाषा के शब्द ह्यूरिसकेन से अनियमित रूप से बना है, जिसका अर्थ है खोजना।

यह भी देखें

• कलन विधि
• रचनात्मक अनुमानी
• जेनेटिक एल्गोरिद्म
• अनुमानी
• हेयुरिस्टिक रूटिंग
• हेयूरिस्टिक मूल्यांकन: उपयोगकर्ता इंटरफेस में उपयोगिता समस्याओं की पहचान करने की विधि।
• Metaheuristic: बुनियादी अनुमानी एल्गोरिदम को नियंत्रित करने और ट्यूनिंग करने के तरीके, आमतौर पर स्मृति और सीखने के उपयोग के साथ।
• मैथ्यूरिस्टिक्स: मेटाह्यूरिस्टिक्स और गणितीय प्रोग्रामिंग (एमपी) तकनीकों के इंटरऑपरेशन द्वारा बनाए गए अनुकूलन एल्गोरिदम।
• प्रतिक्रियाशील खोज अनुकूलन: अनुमानों की स्व-ट्यूनिंग के लिए ऑनलाइन यंत्र अधिगम सिद्धांतों का उपयोग करने वाली विधियाँ।
• रिकर्सन (कंप्यूटर विज्ञान)
• मैक्रो (कंप्यूटर विज्ञान)