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

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

विवरण

उदाहरण के लिए, लंबाई 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$ के बराबर भी है।

व्यवधान

यदि किसी चाइल्ड ऑफ़ एन इंडिविजुअल जो स्कीमा H से मेल खाता है वह स्वयं H से मेल नहीं खाता है, तो स्कीमा को बाधित माना जाता है।

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

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

एक्सपेंशन और कम्प्रेशन ऑपरेटर

हाल ही में ऑर्डर सिद्धांत का उपयोग करके स्कीमा का अध्ययन किया गया है।

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

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

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

$${\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 का एक स्कीमा है जैसे कि s में पोजीशन i पर प्रतीक निम्नलिखित तरीके से निर्धारित किया जाता है: यदि सभी $x,y\in A$ के लिए $x_{i}=y_{i}$ तो $s_{i}=x_{i}$। यदि $A=\emptyset$ तब ${\downarrow }A=\epsilon _{*}$ होता है। कोई इस ऑपरेटर के बारे में सोच सकता है कि वह A में सभी आइटम को स्टैक कर रहा है और यदि किसी कॉलम में सभी तत्व समतुल्य हैं, तो एस में उस स्थिति का प्रतीक यह मान लेता है, अन्यथा एक वाइल्ड कार्ड प्रतीक होता है। उदाहरण के लिए, मान लीजिये $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\}$.$s_{i}=*$

कम्प्रेशन और एक्सपेंशन ऑपरेटर एक गैलोइस कनेक्शन बनाते हैं, जहां $\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 )$ हस्से आरेख के रूप में दिखाया गया है।

योजनाबद्ध लैटिस फॉर्मल कांसेप्ट एनालिसिस में पाई जाने वाली अवधारणा लैटिस के समान है।

यह भी देखें

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