स्कीमा (आनुवंशिक एल्गोरिदम)

एक स्कीमा (pl. schemata) कंप्यूटर विज्ञान में आनुवंशिक एल्गोरिदम के क्षेत्र में उपयोग किया जाने वाला एक टेम्पलेट है जो कुछ स्ट्रिंग स्थितियों में समानता वाले स्ट्रिंग के सबसेट की पहचान करता है। स्कीमाटा सिलेंडर सेट का एक विशेष मामला है, जो स्ट्रिंग्स पर उत्पाद टोपोलॉजी के लिए बेस (टोपोलॉजी) बनाता है। दूसरे शब्दों में, स्कीमाटा का उपयोग स्ट्रिंग्स के स्थान पर टोपोलॉजिकल स्पेस उत्पन्न करने के लिए किया जा सकता है।

विवरण

उदाहरण के लिए, लंबाई 6 की बाइनरी स्ट्रिंग पर विचार करें। स्कीमा 1**0*1 लंबाई 6 के सभी शब्दों के सेट का वर्णन करता है, जिसमें पहले और छठे स्थान पर 1 और चौथे स्थान पर 0 है। * एक वाइल्डकार्ड चरित्र प्रतीक है, जिसका अर्थ है कि स्थिति 2, 3 और 5 का मान 1 या 0 हो सकता है। स्कीमा के क्रम को टेम्पलेट में निश्चित स्थितियों की संख्या के रूप में परिभाषित किया गया है, जबकि परिभाषित लंबाई $\delta (H)$ प्रथम और अंतिम विशिष्ट स्थिति के बीच की दूरी है। 1**0*1 का क्रम 3 है और इसकी परिभाषित लंबाई 5 है। स्कीमा की फिटनेस स्कीमा से मेल खाने वाली सभी स्ट्रिंग्स की औसत फिटनेस है। एक स्ट्रिंग की फिटनेस एन्कोडेड समस्या समाधान के मूल्य का एक माप है, जैसा कि समस्या-विशिष्ट मूल्यांकन फ़ंक्शन द्वारा गणना की जाती है।

लंबाई

एक स्कीमा की लंबाई $H$, बुलाया $N(H)$, को स्कीमा में नोड्स की कुल संख्या के रूप में परिभाषित किया गया है। $N(H)$ मेल खाने वाले प्रोग्राम में नोड्स की संख्या के बराबर भी है $H$.

व्यवधान

यदि किसी व्यक्ति का बच्चा जो स्कीमा एच से मेल खाता है वह स्वयं एच से मेल नहीं खाता है, तो स्कीमा को बाधित माना जाता है।

स्कीमा का प्रसार

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

विस्तार और संपीड़न ऑपरेटर

हाल ही में ऑर्डर सिद्धांत का उपयोग करके स्कीमा का अध्ययन किया गया है। स्कीमा के लिए दो बुनियादी ऑपरेटरों को परिभाषित किया गया है: विस्तार और संपीड़न। विस्तार एक स्कीमा को शब्दों के एक सेट पर मैप करता है जिसका वह प्रतिनिधित्व करता है, जबकि संपीड़न शब्दों के एक सेट को एक स्कीमा पर मैप करता है।

निम्नलिखित परिभाषाओं में $\Sigma$ एक वर्णमाला को दर्शाता है, $\Sigma ^{l}$ लंबाई के सभी शब्दों को दर्शाता है $l$ वर्णमाला के ऊपर $\Sigma$, $\Sigma _{*}$ वर्णमाला को दर्शाता है $\Sigma$ अतिरिक्त प्रतीक के साथ $*$. $\Sigma _{*}^{l}$ लंबाई के सभी स्कीमा को दर्शाता है $l$ वर्णमाला के ऊपर $\Sigma _{*}$ साथ ही खाली स्कीमा $\epsilon _{*}$.

किसी भी स्कीम के लिए $s\in \Sigma _{*}^{l}$ निम्नलिखित ऑपरेटर ${\uparrow }s$, इसको कॉल किया गया $expansion$ का $s$, जो मानचित्र करता है $s$ शब्दों के एक उपसमूह में $\Sigma ^{l}$:

$${\uparrow }s:=\{b\in \Sigma ^{l}|b_{i}=s_{i}{\mbox{ or }}s_{i}=*{\mbox{ for each }}i\in \{1,...,l\}\}$$

जहां सबस्क्रिप्ट $i$ स्थिति में वर्ण को दर्शाता है $i$ एक शब्द या स्कीमा में. कब $s=\epsilon _{*}$ तब ${\uparrow }s=\emptyset$. अधिक सरल शब्दों में कहें तो, ${\uparrow }s$ सभी शब्दों का समुच्चय है $\Sigma ^{l}$ जिसे एक्सचेंज करके बनाया जा सकता है $*$ में प्रतीक $s$ से प्रतीकों के साथ $\Sigma$. उदाहरण के लिए, यदि $\Sigma =\{0,1\}$, $l=3$ और $s=10*$ तब ${\uparrow }s=\{100,101\}$.

इसके विपरीत, किसी के लिए $A\subseteq \Sigma ^{l}$ हम परिभाषित करते हैं ${\downarrow }{A}$, इसको कॉल किया गया $compression$ का $A$, जो मानचित्र करता है $A$ एक स्कीमा पर $s\in \Sigma _{*}^{l}$:

$${\downarrow }A:=s$$

कहाँ $s$ लंबाई का एक स्कीमा है $l$ इस प्रकार कि प्रतीक अपनी स्थिति पर हो $i$ में $s$ निम्नलिखित तरीके से निर्धारित किया जाता है: यदि $x_{i}=y_{i}$ सभी के लिए $x,y\in A$ तब $s_{i}=x_{i}$ अन्यथा $s_{i}=*$. अगर $A=\emptyset$ तब ${\downarrow }A=\epsilon _{*}$. कोई इस ऑपरेटर के बारे में सोच सकता है कि वह सभी वस्तुओं को ढेर कर रहा है $A$ और यदि किसी कॉलम में सभी तत्व समतुल्य हैं, तो उस स्थिति में प्रतीक $s$ यह मान लेता है, अन्यथा एक वाइल्ड कार्ड प्रतीक होता है। उदाहरण के लिए, चलो $A=\{100,000,010\}$ तब ${\downarrow }A=**0$.

स्कीमाटा को आंशिक रूप से ऑर्डर किया जा सकता है। किसी के लिए $a,b\in \Sigma _{*}^{l}$ हम कहते हैं $a\leq b$ अगर और केवल अगर ${\uparrow }a\subseteq {\uparrow }b$. यह इस प्रकार है कि $\leq$ रिफ्लेक्सिव ऑपरेटर बीजगणित, प्रतिसममिति और उपसमुच्चय संबंध के संक्रमणीय संबंध से स्कीमाटा के एक सेट पर आंशिक क्रम है। उदाहरण के लिए, $\epsilon _{*}\leq 11\leq 1*\leq **$. यह है क्योंकि ${\uparrow }\epsilon _{*}\subseteq {\uparrow }11\subseteq {\uparrow }1*\subseteq {\uparrow }**=\emptyset \subseteq \{11\}\subseteq \{11,10\}\subseteq \{11,10,01,00\}$.

संपीड़न और विस्तार ऑपरेटर एक गैलोइस कनेक्शन बनाते हैं, जहां $\downarrow$ निचला जोड़ है और $\uparrow$ ऊपरी जोड़.

योजनाबद्ध समापन और योजनाबद्ध जाली

एक सेट के लिए $A\subseteq \Sigma ^{l}$, हम ए के प्रत्येक उपसमुच्चय पर संपीड़न की गणना करने की प्रक्रिया को कहते हैं $\{{\downarrow }X|X\subseteq A\}$, का योजनाबद्ध समापन $A$, निरूपित ${\mathcal {S}}(A)$.

उदाहरण के लिए, चलो $A=\{110,100,001,000\}$. का योजनाबद्ध समापन $A$, निम्नलिखित सेट में परिणाम:

$${\mathcal {S}}(A)=\{001,100,000,110,00*,*00,1*0,**0,*0*,***,\epsilon _{*}\}$$

पोसेट $({\mathcal {S}}(A),\leq )$ हमेशा एक पूर्ण जाली बनाता है जिसे योजनाबद्ध जाली कहा जाता है।

सेट पर योजनाबद्ध समापन से योजनाबद्ध जाली का निर्माण हुआ $A=\{111,011,001\}$. यहाँ योजनाबद्ध जाली है $({\mathcal {S}}(A),\leq )$ हस्से आरेख के रूप में दिखाया गया है।

योजनाबद्ध जाली औपचारिक अवधारणा विश्लेषण में पाई जाने वाली अवधारणा जाली के समान है।

यह भी देखें

• हॉलैंड का स्कीमा प्रमेय
• औपचारिक अवधारणा विश्लेषण