Crossover (genetic algorithm)
आनुवंशिक एल्गोरिदम और विकासवादी गणना में, क्रॉसओवर, जिसे पुनर्संयोजन भी कहा जाता है, एक आनुवंशिक संचालक है जिसका उपयोग दो माता-पिता की आनुवंशिक जानकारी को मिलाकर नई संतान पैदा करने के लिए किया जाता है। यह एक मौजूदा आबादी से नए समाधान उत्पन्न करने का एक तरीका है, और जीव विज्ञान में यौन प्रजनन के दौरान होने वाले क्रॉसओवर के समान है। समाधान एक मौजूदा समाधान की क्लोनिंग द्वारा भी उत्पन्न किया जा सकता है, जो अलैंगिक प्रजनन के अनुरूप है। नए उत्पन्न समाधानों को आबादी में जोड़ने से पहले उत्परिवर्तित किया जा सकता है। विकासवादी गणना में अलग-अलग एल्गोरिदम आनुवंशिक जानकारी को संग्रहीत करने के लिए अलग-अलग डेटा संरचनाओं का उपयोग कर सकते हैं, और प्रत्येक आनुवंशिक प्रतिनिधित्व को अलग-अलग क्रॉसओवर ऑपरेटरों के साथ फिर से जोड़ा जा सकता है। विशिष्ट डेटा संरचनाएँ जिन्हें क्रॉसओवर के साथ पुनः संयोजित किया जा सकता है, वे हैं बिट सरणी, वास्तविक संख्याओं के वैक्टर या वृक्ष। नीचे प्रस्तुत प्रचालक की सूची किसी भी तरह से पूर्ण नहीं है और मुख्य रूप से इस डायडिक आनुवंशिक प्रचालक प्रकार के अनुकरणीय चित्रण के रूप में कार्य करती है। अधिक संचालक और अधिक विवरण साहित्य में पाए जा सकते हैं। द्विआधारी सरणी के लिए क्रॉसओवर पारंपरिक आनुवंशिक एल्गोरिदम आनुवंशिक जानकारी को एक बिट सरणी द्वारा दर्शाए गए गुणसूत्र में संग्रहीत करते हैं। बिट सरणी के लिए क्रॉसओवर विधियाँ लोकप्रिय हैं और आनुवंशिक पुनर्संयोजन का एक उदाहरण है। एक-बिंदु क्रॉसओवर दोनों माता-पिता के गुणसूत्रों पर एक बिंदु को यादृच्छिक रूप से चुना जाता है, और एक 'क्रॉसओवर बिंदु' नामित किया जाता है। उस बिंदु के दाईं ओर के बिट्स को दो मूल गुणसूत्रों के बीच अदला-बदली किया जाता है। इसके परिणामस्वरूप दो संतानें होती हैं, जिनमें से प्रत्येक में माता-पिता दोनों से कुछ आनुवंशिक जानकारी होती है। दो-बिंदु और के-बिंदु क्रॉसओवर दो-बिंदु क्रॉसओवर में, दो क्रॉसओवर बिंदुओं को मूल गुणसूत्रों से यादृच्छिक रूप से चुना जाता है। दो बिंदुओं के बीच के बिट्स को मूल जीवों के बीच अदला-बदली किया जाता है। दो-बिंदु क्रॉसओवर अलग-अलग क्रॉसओवर बिंदुओं के साथ दो एकल-बिंदु क्रॉसओवर करने के बराबर है। इस रणनीति को किसी भी सकारात्मक पूर्णांक k के लिए k-बिंदु क्रॉसओवर के लिए सामान्यीकृत किया जा सकता है, जो k क्रॉसओवर बिंदुओं को चुनता है। समान क्रॉसओवर में, आम तौर पर, प्रत्येक बिट को समान संभावना के साथ किसी भी मूल से चुना जाता है। अन्य मिश्रण अनुपातों का कभी-कभी उपयोग किया जाता है, जिसके परिणामस्वरूप संतानों को एक माता-पिता से दूसरे की तुलना में अधिक आनुवंशिक जानकारी विरासत में मिलती है। एक समान क्रॉसओवर में, हम गुणसूत्र को खंडों में विभाजित नहीं करते हैं, बल्कि हम प्रत्येक जीन का अलग से इलाज करते हैं। इसमें, हम अनिवार्य रूप से प्रत्येक गुणसूत्र के लिए एक सिक्का पलटते हैं ताकि यह तय किया जा सके कि इसे ऑफ-स्प्रिंग में शामिल किया जाएगा या नहीं। पूर्णांक या वास्तविक-मूल्य वाले जीनोम के लिए क्रॉसओवर ऊपर प्रस्तुत क्रॉसओवर ऑपरेटरों के लिए और बिट स्ट्रिंग्स के लिए अधिकांश अन्य क्रॉसओवर ऑपरेटरों के लिए, यह माना जाता है कि उन्हें पूर्णांक या वास्तविक-मूल्य वाले जीनोम के अनुसार भी लागू किया जा सकता है जिनके जीन में प्रत्येक में एक पूर्णांक या वास्तविक-मूल्य वाली संख्या होती है। अलग-अलग बिट्स के बजाय, पूर्णांक या वास्तविक-मूल्यवान संख्याओं को केवल चाइल्ड जीनोम में कॉपी किया जाता है। संतान दोनों माता-पिता द्वारा फैले हाइपरबॉडी के शेष कोनों पर होती है और जैसा कि त्रि-आयामी मामले के लिए साथ की छवि में उदाहरण दिया गया है। असतत पुनर्संयोजन यदि बिट स्ट्रिंग्स के लिए समान क्रॉसओवर के नियम संतान की पीढ़ी के दौरान लागू किए जाते हैं, तो इसे असतत पुनर्संयोजन भी कहा जाता है। मध्यवर्ती पुनर्संयोजन इस पुनर्संयोजन प्रचालक में, बाल जीनोम के एलील मान दो मूल जीनोम के एलील को मिलाकर उत्पन्न होते हैं औरः यादृच्छिक रूप से प्रति जीन समान रूप से वितरित अंतराल के चयन का कारण यह है कि मूल जीन के एलील मूल्यों द्वारा फैले हाइपरबॉडी के आंतरिक भाग के अलावा अतिरिक्त रूप से संतान के मूल्यों की सीमा के लिए एक निश्चित वातावरण प्रश्न में है। एलील मानों को कम करने की प्रवृत्ति का प्रतिकार करने के लिए एक मूल्य की सिफारिश की जाती है जो अन्यथा पर मौजूद होता है। निकटवर्ती आकृति द्वि-आयामी मामले के लिए दो अनुकरणीय माता-पिता के संभावित नए एलील की सीमा और मध्यवर्ती पुनर्संयोजन को दर्शाती है। असतत पुनर्संयोजन की संतानों को भी प्लॉट किया जाता है। मध्यवर्ती पुनर्संयोजन आभासी वर्णमाला सिद्धांत द्वारा आवश्यक बाल जीनोम के एलील मूल्यों की अंकगणितीय गणना को संतुष्ट करता है। विकास रणनीति में एक मानक के रूप में विविक्त और मध्यवर्ती पुनर्संयोजन का उपयोग किया जाता है। क्रमपरिवर्तन के लिए क्रॉसओवर संयोजन कार्यों के लिए, क्रमपरिवर्तन का उपयोग आमतौर पर किया जाता है जो विशेष रूप से जीनोम के लिए डिज़ाइन किए जाते हैं जो स्वयं एक समूह के क्रमपरिवर्तन होते हैं। अंतर्निहित समुच्चय आमतौर पर या का एक उपसमुच्चय होता है। यदि ऐसे जीनोम के लिए पूर्णांक जीनोम के लिए 1-या एन-बिंदु या समान क्रॉसओवर का उपयोग किया जाता है, तो एक बाल जीनोम में कुछ मान दो बार हो सकते हैं और अन्य गायब हो सकते हैं। इसे आनुवंशिक मरम्मत द्वारा ठीक किया जा सकता है, जैसे। अन्य बाल जीनोम से लापता जीन के लिए स्थितिगत निष्ठा में अनावश्यक जीन को प्रतिस्थापित करके। अमान्य संतानों की उत्पत्ति से बचने के लिए, क्रमपरिवर्तन के लिए विशेष क्रॉसओवर ऑपरेटर विकसित किए गए हैं जो क्रमपरिवर्तन के लिए ऐसे ऑपरेटरों की बुनियादी आवश्यकताओं को पूरा करते हैं, अर्थात् प्रारंभिक क्रमपरिवर्तन के सभी तत्व भी नए में मौजूद होते हैं और केवल क्रम बदल जाता है। इसे संयोजन कार्यों के बीच अलग किया जा सकता है, जहां सभी अनुक्रम स्वीकार्य हैं, और जहां अस्वीकार्य आंशिक अनुक्रमों के रूप में बाधाएं हैं। पहले कार्य प्रकार का एक प्रसिद्ध प्रतिनिधि यात्रा विक्रेता समस्या (टी. एस. पी.) है, जहाँ लक्ष्य सबसे छोटे दौरे पर ठीक एक बार शहरों के एक समूह का दौरा करना है। सीमित कार्य प्रकार का एक उदाहरण कई कार्यप्रवाहों का समय निर्धारण है। कार्यप्रवाह में कुछ व्यक्तिगत कार्य चरणों पर अनुक्रम बाधाएं शामिल होती हैं। उदाहरण के लिए, एक धागे को तब तक नहीं काटा जा सकता जब तक कि संबंधित छेद को वर्कपीस में ड्रिल नहीं किया जाता है। इस तरह की समस्याओं को क्रम-आधारित क्रमपरिवर्तन भी कहा जाता है। निम्नलिखित में, दो क्रॉसओवर ऑपरेटरों को उदाहरण के रूप में प्रस्तुत किया गया है, टीएसपी द्वारा प्रेरित आंशिक रूप से मानचित्रित क्रॉसओवर (पीएमएक्स) और ऑर्डर-आधारित क्रमपरिवर्तन के लिए डिज़ाइन किया गया ऑर्डर क्रॉसओवर (ओएक्स1)। प्रत्येक मामले में मूल गुणसूत्रों का आदान-प्रदान करके दूसरी संतान पैदा की जा सकती है। आंशिक रूप से मानचित्रित क्रॉसओवर (पी. एम. एक्स.) पी. एम. एक्स. प्रचालक को टी. एस. पी. जैसी समस्याओं के लिए एक पुनर्संयोजन प्रचालक के रूप में तैयार किया गया था। प्रक्रिया की व्याख्या एक उदाहरण द्वारा सचित्र हैः ऑर्डर क्रॉसओवर (ओएक्स1) ऑर्डर क्रॉसओवर अपने मूल रूप में डेविस के पास वापस जाता है और यहां दो से अधिक क्रॉसओवर अंकों के साथ थोड़ा सामान्यीकृत संस्करण में प्रस्तुत किया गया है। यह दूसरे माता-पिता से संतान को सापेक्ष क्रम के बारे में जानकारी स्थानांतरित करता है। सबसे पहले, क्रॉसओवर बिंदुओं की संख्या और स्थिति यादृच्छिक रूप से निर्धारित की जाती है। परिणामस्वरूप जीन अनुक्रमों को फिर नीचे वर्णित अनुसार संसाधित किया जाता हैः अन्य बातों के अलावा, ऑर्डर क्रॉसओवर कई कार्यप्रवाहों को निर्धारित करने के लिए अच्छी तरह से अनुकूल है, जब 1-और एन-पॉइंट क्रॉसओवर के साथ संयोजन में उपयोग किया जाता है। क्रमपरिवर्तन के लिए आगे क्रॉसओवर ऑपरेटर समय के साथ, क्रमपरिवर्तन के लिए बड़ी संख्या में क्रॉसओवर ऑपरेटर प्रस्तावित किए गए हैं, इसलिए निम्नलिखित सूची केवल एक छोटा चयन है। अधिक जानकारी के लिए, पाठक को साहित्य के लिए संदर्भित किया जाता है। साइकिल क्रॉसओवर (सी. एक्स.) ऑर्डर-बेस्ड क्रॉसओवर (ओ. एक्स. 2) पोजीशन-बेस्ड क्रॉसओवर (पी. ओ. एस.) एज रिकॉम्बिनेशन वोटिंग रिकॉम्बिनेशन (वी. आर.) अल्टरनेटिंग-पोजीशन क्रॉसओवर (ए. पी.) मैक्सिमल प्रिजर्वेटिव क्रॉसओवर (एम. पी. एक्स.) मर्ज क्रॉसओवर (एम. एक्स.) सीक्वेंशियल कंस्ट्रक्टिव क्रॉसओवर ऑपरेटर (एस. सी. एक्स.) आनुवंशिक या, अधिक सामान्य रूप से, विकासवादी एल्गोरिदम द्वारा टी. एस. पी. जैसी समस्याओं को हल करने के लिए सामान्य दृष्टिकोण, पहले प्रस्तुत किया गया है, या तो अवैध वंशजों की मरम्मत करना या ऑपरेटरों को उचित रूप से समायोजित करना है ताकि अवैध संतान पहली जगह में उत्पन्न न हो। वैकल्पिक रूप से, रियाज़ी एक दोहरे गुणसूत्र प्रतिनिधित्व के उपयोग का सुझाव देता है, जो अवैध संतानों से बचाता है। इवोल्यूशनरी एल्गोरिदम जेनेटिक रिप्रेजेंटेशन फिटनेस फंक्शन सिलेक्शन (जेनेटिक एल्गोरिदम) बिब्लियोग्राफी जॉन हॉलैंड (1975) भी देखें। प्राकृतिक और कृत्रिम प्रणालियों में अनुकूलन, पीएचडी थीसिस, मिशिगन विश्वविद्यालय प्रेस, एन आर्बर, मिशिगन। .. संदर्भ बाहरी लिंक न्यूज़ग्रुपः comp.ai.genetic FAQ-क्रॉसओवर पर अनुभाग देखें (जिसे पुनर्संयोजन के रूप में भी जाना जाता है)। विकासवादी एल्गोरिदम आनुवंशिक एल्गोरिदम