स्कीमा (आनुवंशिक एल्गोरिदम): Difference between revisions
From Vigyanwiki
(Created page with "{{Evolutionary algorithms}} एक स्कीमा ({{Plural form|'''schemata'''}}) कंप्यूटर विज्ञान में आनुवंशिक...") |
(text) |
||
| Line 1: | Line 1: | ||
{{Evolutionary algorithms}} | {{Evolutionary algorithms}} | ||
एक स्कीमा ({{Plural form|''' | एक स्कीमा ({{Plural form|'''स्केमाता'''}}) [[कंप्यूटर विज्ञान]] में जेनेटिक एल्गोरिदम के क्षेत्र में उपयोग किया जाने वाला एक टेम्पलेट है जो कुछ स्ट्रिंग पोजीशन में समानता वाले स्ट्रिंग के [[सबसेट]] की पहचान करता है। स्कीमाटा [[सिलेंडर सेट]] की एक विशेष स्थिति है, जो स्ट्रिंग्स पर [[उत्पाद टोपोलॉजी|प्रोडक्ट टोपोलॉजी]] के लिए बेस (टोपोलॉजी) बनाता है। <ref name="Holland1">{{cite book |title=प्राकृतिक और कृत्रिम प्रणाली में अनुकूलन|year=1992|edition=reprint|publisher=The MIT Press|author=Holland, John Henry |isbn=9780472084609 |url=https://books.google.com/books?id=JE5RAAAAMAAJ |url-status=live |accessdate=22 April 2014}}</ref> दूसरे शब्दों में, स्कीमाटा का उपयोग स्ट्रिंग्स के स्थान पर [[टोपोलॉजिकल स्पेस]] उत्पन्न करने के लिए किया जा सकता है। | ||
== विवरण == | == विवरण == | ||
उदाहरण के लिए, लंबाई 6 की बाइनरी स्ट्रिंग पर विचार करें। स्कीमा 1**0*1 लंबाई 6 के सभी शब्दों के सेट का वर्णन करता है, जिसमें पहले और छठे स्थान पर 1 और चौथे स्थान पर 0 है। * एक [[वाइल्डकार्ड चरित्र]] प्रतीक है, जिसका अर्थ है कि | उदाहरण के लिए, लंबाई 6 की बाइनरी स्ट्रिंग पर विचार करें। स्कीमा 1**0*1 लंबाई 6 के सभी शब्दों के सेट का वर्णन करता है, जिसमें पहले और छठे स्थान पर 1 और चौथे स्थान पर 0 है। * एक [[वाइल्डकार्ड चरित्र|वाइल्डकार्ड करैक्टर]] प्रतीक है, जिसका अर्थ है कि पोजीशन 2, 3 और 5 का मान 1 या 0 हो सकता है। स्कीमा के क्रम को टेम्पलेट में निश्चित पोजीशन की संख्या के रूप में परिभाषित किया गया है, जबकि परिभाषित लंबाई <math> \delta(H) </math> प्रथम और अंतिम विशिष्ट पोजीशन के बीच की दूरी है। 1**0*1 का क्रम 3 है और इसकी परिभाषित लंबाई 5 है। स्कीमा की फिटनेस स्कीमा से मेल खाने वाली सभी स्ट्रिंग्स की औसत फिटनेस है। एक स्ट्रिंग की फिटनेस एन्कोडेड समस्या समाधान के मूल्य का एक माप है, जैसा कि समस्या-विशिष्ट मूल्यांकन फ़ंक्शन द्वारा गणना की जाती है। | ||
===लंबाई=== | ===लंबाई=== | ||
एक स्कीमा की लंबाई <math>H</math>, | एक स्कीमा की लंबाई <math>H</math>, <math>N(H)</math> बुलाया जाता है, उसको स्कीमा में नोड्स की कुल संख्या के रूप में परिभाषित किया गया है। <math>N(H)</math> मेल खाने वाले प्रोग्राम में नोड्स की संख्या <math>H</math> के बराबर भी है। <ref name="UCL1">{{cite web|title=आनुवंशिक प्रोग्रामिंग की नींव|url=http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP/|publisher=UCL UK|accessdate=13 July 2010}}</ref> | ||
===व्यवधान=== | ===व्यवधान=== | ||
यदि किसी | यदि किसी चाइल्ड ऑफ़ एन इंडिविजुअल जो स्कीमा H से मेल खाता है वह स्वयं H से मेल नहीं खाता है, तो स्कीमा को बाधित माना जाता है। <ref name="UCL1" /> | ||
==स्कीमा का प्रसार== | ==स्कीमा का प्रसार== | ||
[[आनुवंशिक एल्गोरिदम]] और [[ आनुवंशिक प्रोग्रामिंग ]] जैसे [[विकासवादी कंप्यूटिंग]] में, | [[आनुवंशिक एल्गोरिदम|जेनेटिक एल्गोरिदम]] और [[ आनुवंशिक प्रोग्रामिंग | जेनेटिक प्रोग्रामिंग]] जैसे [[विकासवादी कंप्यूटिंग|एवोलुशनरी कंप्यूटिंग]] में, प्रोपागेशन का तात्पर्य एक जनरेशन द्वारा अगली जनरेशन की करैक्टरिस्टिक्स की इनहेरिटेंस से है। उदाहरण के लिए, एक स्कीमा का प्रोपागेशन तब किया जाता है जब उपस्थित जनरेशन के इंडिविजुअल उससे मेल खाते हैं और अगली जनरेशन के इंडिविजुअल भी उससे मेल खाते हैं। अगली जनरेशन में वे चिल्ड्रन ऑफ़ पेरेंट्स हो सकते हैं (लेकिन होना आवश्यक नहीं है) जो इससे मेल खाते हों। | ||
== | == एक्सपेंशन और कम्प्रेशन ऑपरेटर == | ||
हाल ही में ऑर्डर सिद्धांत का उपयोग करके स्कीमा का अध्ययन किया गया है।<ref name = "Fletcher"> | हाल ही में ऑर्डर सिद्धांत का उपयोग करके स्कीमा का अध्ययन किया गया है। <ref name = "Fletcher"> | ||
{{cite arXiv |author=Jack McKay Fletcher and Thomas Wennkers |year=2017 |title=A natural approach to studying schema processing |eprint=1705.04536|class=cs.NE }}</ref> | {{cite arXiv |author=Jack McKay Fletcher and Thomas Wennkers |year=2017 |title=A natural approach to studying schema processing |eprint=1705.04536|class=cs.NE }}</ref> | ||
निम्नलिखित परिभाषाओं में <math> \Sigma </math> एक | स्कीमा के लिए दो बेसिक ऑपरेटर्स को परिभाषित किया गया है: एक्सपेंशन और कम्प्रेशन। एक्सपेंशन एक स्कीमा को शब्दों के एक सेट पर मैप करता है जिसका वह प्रतिनिधित्व करता है, जबकि कम्प्रेशन शब्दों के एक सेट को एक स्कीमा पर मैप करता है। | ||
निम्नलिखित परिभाषाओं में <math> \Sigma </math> एक अल्फाबेट को दर्शाता है, <math> \Sigma^l </math> लंबाई के सभी शब्दों को दर्शाता है <math> l </math> अल्फाबेट के ऊपर <math> \Sigma </math>, <math> \Sigma_* </math> अल्फाबेट <math>\Sigma</math> को अतिरिक्त प्रतीक <math>*</math>. <math>\Sigma_*^l</math> के साथ लंबाई <math> l </math> अल्फाबेट के ऊपर <math> \Sigma_* </math> साथ ही खाली स्कीमा <math> \epsilon_* </math> के सभी स्कीमा को दर्शाता है। | |||
किसी भी | किसी भी स्कीमा <math>s \in \Sigma^l_*</math> के लिए, निम्नलिखित ऑपरेटर <math>{\uparrow}s</math> को s का <math>expansion</math> कहा जाता है, जो <math>\Sigma^l </math> में शब्दों के सबसेट के लिए <math>s</math> को मैप करता है। : | ||
<math display="block">{\uparrow}s := \{b \in \Sigma^l | b_i = s_i \mbox{ or } s_i = * \mbox{ for each } i \in \{1,...,l\}\} </math> | <math display="block">{\uparrow}s := \{b \in \Sigma^l | b_i = s_i \mbox{ or } s_i = * \mbox{ for each } i \in \{1,...,l\}\} </math> | ||
जहां | जहां <math>i</math> एक शब्द या स्कीमा में सबस्क्रिप्ट पोजीशन <math>i</math> में वर्ण को दर्शाता है। जब <math> s= \epsilon_*</math> तब <math>{\uparrow}s = \emptyset</math>। अधिक सरल शब्दों में कहें तो, <math>{\uparrow}s</math> सभी शब्दों का समुच्चय <math>\Sigma^l</math> है, जिसे <math>*</math> में प्रतीक <math>s</math> से प्रतीक <math>\Sigma</math> के साथ एक्सचेंज करके बनाया जा सकता है। उदाहरण के लिए, यदि <math>\Sigma=\{0,1\}</math>, <math>l=3</math> और <math>s=10*</math> तब <math>{\uparrow}s=\{100,101\} </math>। | ||
इसके विपरीत, किसी के लिए <math>A \subseteq \Sigma^l</math> हम | इसके विपरीत, किसी के लिए <math>A \subseteq \Sigma^l</math> हम <math>{\downarrow}{A}</math> परिभाषित करते हैं, इसको <math>compression</math> का <math>A</math> बुलाया गया, जो <math>A</math> एक स्कीमा पर <math>s\in \Sigma_*^l</math> मैप करता है: | ||
<math display="block">{\downarrow}A:= s</math> | <math display="block">{\downarrow}A:= s</math> | ||
जहाँ <math>s</math> लंबाई l का एक स्कीमा है जैसे कि s में पोजीशन i पर प्रतीक निम्नलिखित तरीके से निर्धारित किया जाता है: यदि सभी <math>x,y \in A</math> के लिए <math>x_i = y_i</math> तो <math>s_i = x_i</math>। यदि <math>A = \emptyset</math> तब <math>{\downarrow}A = \epsilon_*</math> होता है। कोई इस ऑपरेटर के बारे में सोच सकता है कि वह A में सभी आइटम को स्टैक कर रहा है और यदि किसी कॉलम में सभी तत्व समतुल्य हैं, तो एस में उस स्थिति का प्रतीक यह मान लेता है, अन्यथा एक वाइल्ड कार्ड प्रतीक होता है। उदाहरण के लिए, मान लीजिये <math>A = \{100,000,010\}</math> तब <math>{\downarrow}A = **0</math> है। | |||
स्कीमाटा को आंशिक रूप से ऑर्डर किया जा सकता है। किसी <math>a,b \in \Sigma^l_*</math> के लिए हम कहते हैं <math>a \leq b</math> यदि और केवल यदि <math>{\uparrow}a \subseteq {\uparrow}b</math>। यह इस प्रकार है कि <math>\leq</math> [[रिफ्लेक्सिव ऑपरेटर बीजगणित|रेफ्लेक्सिविटी]], [[ प्रतिसममिति |एंटीसीममेट्री]] और सबसेट रिलेशन के ट्रान्सिटिविटी से स्कीमाटा के एक सेट पर पार्शियल ऑर्डरिंग है। उदाहरण के लिए, <math>\epsilon_* \leq 11 \leq 1* \leq **</math>। यह है क्योंकि <math>{\uparrow}\epsilon_* \subseteq {\uparrow}11 \subseteq {\uparrow}1* \subseteq {\uparrow}** = \emptyset \subseteq \{11\} \subseteq \{11,10\} \subseteq \{11,10,01,00\}</math>.<math>s_i = *</math> | |||
कम्प्रेशन और एक्सपेंशन ऑपरेटर एक [[गैलोइस कनेक्शन]] बनाते हैं, जहां <math>\downarrow</math> निचला जोड़ है और <math>\uparrow</math> ऊपरी जोड़ ट्रान्सिटिविटी है। <ref name="Fletcher" /> | |||
== | == स्कीमैटिक कम्पलीशन और स्कीमैटिक लैटिस == | ||
एक सेट के लिए <math>A \subseteq \Sigma^l</math>, हम ए के प्रत्येक उपसमुच्चय | एक सेट के लिए <math>A \subseteq \Sigma^l</math>, हम ए के प्रत्येक उपसमुच्चय <math>\{{\downarrow}X | X \subseteq A\}</math> पर कम्प्रेशन की गणना करने की प्रक्रिया को कहते हैं , <math>A</math> का योजनाबद्ध समापन, निरूपित <math>\mathcal{S}(A)</math> है। <ref name="Fletcher"/> | ||
उदाहरण के लिए, | उदाहरण के लिए, मान लीजिये <math>A = \{110, 100, 001, 000\}</math>. का योजनाबद्ध समापन <math>A</math>, निम्नलिखित सेट में परिणाम: | ||
<math display="block">\mathcal{S}(A) = | |||
\{001, 100, 000, 110, 00*, *00, 1*0, **0, *0*, ***, \epsilon_*\}</math> | \{001, 100, 000, 110, 00*, *00, 1*0, **0, *0*, ***, \epsilon_*\}</math> | ||
[[पोसेट]] <math>(\mathcal{S}(A),\leq)</math> हमेशा एक [[पूर्ण जाली]] बनाता है जिसे योजनाबद्ध | [[पोसेट]] <math>(\mathcal{S}(A),\leq)</math> हमेशा एक [[पूर्ण जाली|कम्पलीट लैटिस]] बनाता है जिसे योजनाबद्ध लैटिस कहा जाता है। | ||
[[File:Schematic Lattice.png|thumb|सेट पर योजनाबद्ध समापन से योजनाबद्ध | [[File:Schematic Lattice.png|thumb|सेट पर योजनाबद्ध समापन से योजनाबद्ध लैटिस का निर्माण हुआ <math>A=\{111, 011, 001\}</math>. यहाँ योजनाबद्ध लैटिस है <math>(\mathcal{S}(A),\leq)</math> [[हस्से आरेख]] के रूप में दिखाया गया है।]]योजनाबद्ध लैटिस [[औपचारिक अवधारणा विश्लेषण|फॉर्मल कांसेप्ट एनालिसिस]] में पाई जाने वाली अवधारणा लैटिस के समान है। | ||
{{clear}} | {{clear}} | ||
Revision as of 10:31, 24 July 2023
एक स्कीमा (pl. स्केमाता) कंप्यूटर विज्ञान में जेनेटिक एल्गोरिदम के क्षेत्र में उपयोग किया जाने वाला एक टेम्पलेट है जो कुछ स्ट्रिंग पोजीशन में समानता वाले स्ट्रिंग के सबसेट की पहचान करता है। स्कीमाटा सिलेंडर सेट की एक विशेष स्थिति है, जो स्ट्रिंग्स पर प्रोडक्ट टोपोलॉजी के लिए बेस (टोपोलॉजी) बनाता है। [1] दूसरे शब्दों में, स्कीमाटा का उपयोग स्ट्रिंग्स के स्थान पर टोपोलॉजिकल स्पेस उत्पन्न करने के लिए किया जा सकता है।
विवरण
उदाहरण के लिए, लंबाई 6 की बाइनरी स्ट्रिंग पर विचार करें। स्कीमा 1**0*1 लंबाई 6 के सभी शब्दों के सेट का वर्णन करता है, जिसमें पहले और छठे स्थान पर 1 और चौथे स्थान पर 0 है। * एक वाइल्डकार्ड करैक्टर प्रतीक है, जिसका अर्थ है कि पोजीशन 2, 3 और 5 का मान 1 या 0 हो सकता है। स्कीमा के क्रम को टेम्पलेट में निश्चित पोजीशन की संख्या के रूप में परिभाषित किया गया है, जबकि परिभाषित लंबाई प्रथम और अंतिम विशिष्ट पोजीशन के बीच की दूरी है। 1**0*1 का क्रम 3 है और इसकी परिभाषित लंबाई 5 है। स्कीमा की फिटनेस स्कीमा से मेल खाने वाली सभी स्ट्रिंग्स की औसत फिटनेस है। एक स्ट्रिंग की फिटनेस एन्कोडेड समस्या समाधान के मूल्य का एक माप है, जैसा कि समस्या-विशिष्ट मूल्यांकन फ़ंक्शन द्वारा गणना की जाती है।
लंबाई
एक स्कीमा की लंबाई , बुलाया जाता है, उसको स्कीमा में नोड्स की कुल संख्या के रूप में परिभाषित किया गया है। मेल खाने वाले प्रोग्राम में नोड्स की संख्या के बराबर भी है। [2]
व्यवधान
यदि किसी चाइल्ड ऑफ़ एन इंडिविजुअल जो स्कीमा H से मेल खाता है वह स्वयं H से मेल नहीं खाता है, तो स्कीमा को बाधित माना जाता है। [2]
स्कीमा का प्रसार
जेनेटिक एल्गोरिदम और जेनेटिक प्रोग्रामिंग जैसे एवोलुशनरी कंप्यूटिंग में, प्रोपागेशन का तात्पर्य एक जनरेशन द्वारा अगली जनरेशन की करैक्टरिस्टिक्स की इनहेरिटेंस से है। उदाहरण के लिए, एक स्कीमा का प्रोपागेशन तब किया जाता है जब उपस्थित जनरेशन के इंडिविजुअल उससे मेल खाते हैं और अगली जनरेशन के इंडिविजुअल भी उससे मेल खाते हैं। अगली जनरेशन में वे चिल्ड्रन ऑफ़ पेरेंट्स हो सकते हैं (लेकिन होना आवश्यक नहीं है) जो इससे मेल खाते हों।
एक्सपेंशन और कम्प्रेशन ऑपरेटर
हाल ही में ऑर्डर सिद्धांत का उपयोग करके स्कीमा का अध्ययन किया गया है। [3]
स्कीमा के लिए दो बेसिक ऑपरेटर्स को परिभाषित किया गया है: एक्सपेंशन और कम्प्रेशन। एक्सपेंशन एक स्कीमा को शब्दों के एक सेट पर मैप करता है जिसका वह प्रतिनिधित्व करता है, जबकि कम्प्रेशन शब्दों के एक सेट को एक स्कीमा पर मैप करता है।
निम्नलिखित परिभाषाओं में एक अल्फाबेट को दर्शाता है, लंबाई के सभी शब्दों को दर्शाता है अल्फाबेट के ऊपर , अल्फाबेट को अतिरिक्त प्रतीक . के साथ लंबाई अल्फाबेट के ऊपर साथ ही खाली स्कीमा के सभी स्कीमा को दर्शाता है।
किसी भी स्कीमा के लिए, निम्नलिखित ऑपरेटर को s का कहा जाता है, जो में शब्दों के सबसेट के लिए को मैप करता है। :
जहां एक शब्द या स्कीमा में सबस्क्रिप्ट पोजीशन में वर्ण को दर्शाता है। जब तब । अधिक सरल शब्दों में कहें तो, सभी शब्दों का समुच्चय है, जिसे में प्रतीक से प्रतीक के साथ एक्सचेंज करके बनाया जा सकता है। उदाहरण के लिए, यदि , और तब ।
इसके विपरीत, किसी के लिए हम परिभाषित करते हैं, इसको का बुलाया गया, जो एक स्कीमा पर मैप करता है:
जहाँ लंबाई l का एक स्कीमा है जैसे कि s में पोजीशन i पर प्रतीक निम्नलिखित तरीके से निर्धारित किया जाता है: यदि सभी के लिए तो । यदि तब होता है। कोई इस ऑपरेटर के बारे में सोच सकता है कि वह A में सभी आइटम को स्टैक कर रहा है और यदि किसी कॉलम में सभी तत्व समतुल्य हैं, तो एस में उस स्थिति का प्रतीक यह मान लेता है, अन्यथा एक वाइल्ड कार्ड प्रतीक होता है। उदाहरण के लिए, मान लीजिये तब है।
स्कीमाटा को आंशिक रूप से ऑर्डर किया जा सकता है। किसी के लिए हम कहते हैं यदि और केवल यदि । यह इस प्रकार है कि रेफ्लेक्सिविटी, एंटीसीममेट्री और सबसेट रिलेशन के ट्रान्सिटिविटी से स्कीमाटा के एक सेट पर पार्शियल ऑर्डरिंग है। उदाहरण के लिए, । यह है क्योंकि .
कम्प्रेशन और एक्सपेंशन ऑपरेटर एक गैलोइस कनेक्शन बनाते हैं, जहां निचला जोड़ है और ऊपरी जोड़ ट्रान्सिटिविटी है। [3]
स्कीमैटिक कम्पलीशन और स्कीमैटिक लैटिस
एक सेट के लिए , हम ए के प्रत्येक उपसमुच्चय पर कम्प्रेशन की गणना करने की प्रक्रिया को कहते हैं , का योजनाबद्ध समापन, निरूपित है। [3]
उदाहरण के लिए, मान लीजिये . का योजनाबद्ध समापन , निम्नलिखित सेट में परिणाम:
पोसेट हमेशा एक कम्पलीट लैटिस बनाता है जिसे योजनाबद्ध लैटिस कहा जाता है।
सेट पर योजनाबद्ध समापन से योजनाबद्ध लैटिस का निर्माण हुआ . यहाँ योजनाबद्ध लैटिस है हस्से आरेख के रूप में दिखाया गया है।
योजनाबद्ध लैटिस फॉर्मल कांसेप्ट एनालिसिस में पाई जाने वाली अवधारणा लैटिस के समान है।
यह भी देखें
- हॉलैंड का स्कीमा प्रमेय
- औपचारिक अवधारणा विश्लेषण
संदर्भ
- ↑ Holland, John Henry (1992). प्राकृतिक और कृत्रिम प्रणाली में अनुकूलन (reprint ed.). The MIT Press. ISBN 9780472084609. Retrieved 22 April 2014.
{{cite book}}: CS1 maint: url-status (link) - ↑ 2.0 2.1 "आनुवंशिक प्रोग्रामिंग की नींव". UCL UK. Retrieved 13 July 2010.
- ↑ 3.0 3.1 3.2 Jack McKay Fletcher and Thomas Wennkers (2017). "A natural approach to studying schema processing". arXiv:1705.04536 [cs.NE].
