जेनेटिक एल्गोरिद्म

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

शुरुआत

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

चयन

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

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

प्रजनन

अनुवांशिक ऑपरेटर के माध्यम से चयन किये गए समाधान की दूसरी पीढी की आबादी को उत्पन्न करने का अगला चरण है: क्रॉसओवर (जो पुनर्संयोजन (crossover) भी कहलाता है) और / या उत्परिवर्तन (mutation).
उत्पन्न किये जाने वाले प्रत्येक नए समाधान के लिए, "जनक" समाधान के एक युग्म का चयन किया जाता है, ताकि पहले चयन किये गए पूल से प्रजनन किया जा सके. 
क्रोस ओवर और उत्परिवर्तन की उपरोक्त विधि का प्रयोग करते हुए, एक "बच्चा या संतान" समाधान के उत्पादन के द्वारा, एक नया समाधान निर्मित किया जाता है, जो प्रारूपिक रूप से इसके "जनक" के कई लाक्षणिक गुण रखता है। प्रत्येक बच्चे के लिए नए जनक का चयन किया जाता है और यह प्रक्रिया तब तक जारी रहती है जब तक उपयुक्त आकार के समाधान की एक नयी आबादी उत्पन्न नहीं हो जाती है। 
हालांकि प्रजनन की विधियां जो दो जनकों की उपयोग पर आधारित हैं, वे "जैव विज्ञान से अधिक प्रेरित" हैं, हाल ही में किये गए अनुसंधान (इस्लाम अबाऊ एल अता 2006) सुझाव देते हैं कि दो से अधिक "जनकों" का उपयोग करना एक अच्छी गुणवत्ता के गुणसूत्र के प्रजनन के लिए बेहतर है। 
इन प्रक्रियाओं के परिणामस्वरूप अंततः गुणसूत्रों की अगली पीढी की आबादी उत्पन्न होती है जो प्रारंभिक पीढी से अलग होती है। 
आमतौर पर आबादी के लिए इस प्रक्रिया के द्वारा औसतन फिटनेस में वृद्धि होगी, चूंकि पहली पीढी से केवल सर्वोत्तम जीवों को प्रजनन के लिए चुना जाता है, साथ ही कम फिट समाधान के एक छोटे अनुपात को लिया जाता है, इसके लिए कारण ऊपर बताये गए हैं।

विभेद (Variants)

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

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

एक नयी आबादी के निर्माण की सामान्य प्रक्रिया का एक बहुत ही सफल (हल्का) विभेद है, वर्तमान पीढी से किसी बेहतर जीव को प्राप्त करने में मदद करना जो अगले अपरिवर्तित जीव को स्थानांतरित हो. यह रणनीति संभ्रांतवादी चयन (elitist selection) के रूप में जानी जीती है। 

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

यह GA के अन्य अनुकूलन विधियों के साथ संयोजन हेतु बहुत प्रभावी हो सकता है। 
सामान्य रूप से अच्छे वैश्विक समाधान की खोज करने में GA की प्रवृति बहुत अच्छी होती है, लेकिन पूर्णतया अनुकूल की खोज के लिए पिछले कुछ उत्परिवर्तनों की खोज में यह काफी अप्रभावी होता है।
अन्य तकनीकें (जैसे साधारण पहाडी की चढ़ाई) एक सीमित क्षेत्र में पूर्णतया अनुकूल की खोज में बहुत प्रभावी होती हैं। 
पहाडी के चढ़ाई में मजबूती के अभाव को पार पाने के लिए वैकल्पिक GA और पहाडी की चढ़ाई GA की प्रभावित को बढा सकते हैं। 
 
इसका अर्थ यह है कि प्राकृतिक मामले में आनुवंशिक विभिन्नता के नियमों का भिन्न अर्थ हो सकता है। 
उदाहरण के लिए-दिया गया है कि चरणों को क्रमागत क्रम में संग्रहित किया गया है-क्रोसिंग ओवर पैतृक DNA से पदों की संख्या को जोड़ते हुए मातृक DNA से पदों की संख्या का योग कर सकता है और ऐसा चलता रहता है। 
यह उन सदिशों के योग की तरह है जिनके लक्षण प्ररुपी परिदृश्य में एक रिज का अनुसरण करने की संभावना अधिक होती है। 
इस प्रकार से इस प्रक्रिया की कुशलता कि परिमाण के कई क्रमों के द्वारा बढाया जा सकता है। इसके अलावा, उलटा ऑपरेटर (inversion operator) के पास यह मौका होता है कि वह प्रभाविता की उत्तरजीविता के पक्ष में पदों को क्रमागत क्रम में या किसी अन्य उपयुक्त क्रम में रख सके. 
(उदाहरण के लिए देखें या यात्रा करते हुए विक्रेता की समस्या में उदाहरण.)
आबादी-आधारित वृद्धि शिक्षण (Population-based incremental learning) एक विभेद है जहां एक पूर्ण रूप में आबादी इसके व्यक्तिगत सदस्यों के बजाय उत्पन्न होती है।

समस्या डोमेन (Problem domains)

वे समस्याएं जो आनुवंशिक एल्गोरिथम के द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं, उनमें शामिल हैं समय सारणी बनाने और समयबद्धन की समस्याएं (timetabling and scheduling problems) और कई समयबद्धन सॉफ्टवेयर पैकेज GAs पर आधारित होते हैं। 
GAs को अभियांत्रिकी (engineering) पर भी लागू किया जा सकता है। आनुवंशिक एल्गोरिथम को अक्सर वैश्विक अनुकूलन समस्याओं के समाधान के एक दृष्टिकोण के रूप में लागू किया जाता है। 

चूंकि थम्ब आनुवंशिक एल्गोरिथम का एक सामान्य नियम समस्या डोमेन में उपयोगी हो सकता है जिसमें पुनर्संयोजन के रूप में एक जटिल फिटनेस परिदृश्य होता है, जिसे आबादी को स्थानीय ओपटिमा से दूर हटाने के लिए डिजाइन किया जाता है, ताकि पारंपरिक पहाड़ी चढाई एल्गोरिथम इसमें जुड़ जाये.

इतिहास

विकास का कंप्यूटर सिमुलेशन 1954 में नील्स आल बेरीसेली के कार्य के साथ शुरू हुआ, जो न्यू जर्सी में इंस्टीट्युट फॉर एडवांस्ड स्टडी इन प्रिंसटन में कंप्यूटर का उपयोग कर रहे थे।उनके 1954 के प्रकाशन पर अधिक ध्यान नहीं दिया गया। 1957 में शुरू करके, ऑस्ट्रेलियाई मात्रात्मक आनुवंशिकी विज्ञानी एलेक्स फ्रासर ने, मापन योग्य लक्षण का नियंत्रण करने वाले एकाधिक बिन्दुपथ से युक्त जीव के कृत्रिम चयन के सिमुलेशन पर पेपर्स की एक श्रृंखला प्रकाशित की. 
इन शुरुआत से, जीव विज्ञानियों के द्वारा विकास का कंप्यूटर सिमुलेशन 1960 के दशक के प्रारंभ में अधिक सामान्य बन गया और विधियों को फ्रासर और बरनेल (1970) और क्रोस्बी (1973)के द्वारा पुस्तकों में वर्णित किया गया। 

फ्रासर के सिमुलेशन में आधुनिक आनुवंशिक एल्गोरिथम के सभी आवश्यक तत्व शामिल हैं। 
इसके अतिरिक्त, हंस ब्रेमरमेन ने 1960 के दशक में कागजों की एक श्रृंखला प्रकाशित की जिसमें भी समस्याओं के अनुकूलन, पुनर्संयोजन, उत्परिवर्तन और चयन के लिए समाधान की आबादी को अपनाया गया। 
ब्रेमरमेन के अनुसंधान में भी आधुनिक आनुवंशिक एल्गोरिथम के तत्व शामिल हैं। अन्य उल्लेखनीय प्रारंभिक पथ प्रदर्शकों में शामिल हैं, रिचर्ड फ्रीदबर्ग, जॉर्ज फ्रीदमेन और माइकल कोनराड. कई आरंभिक पत्रों को फोगल के द्वारा (1998) पुनः मुद्रित किया गया।

हालांकि बेरीसेली, की 1963 की रिपोर्ट में, एक साधारण खेल खेलने की क्षमता के विकास को सिमुलेट किया गया, 1960 के दशक में इंगो रेचेनबर्ग और हंस-पॉल श्वेफेलके कार्य के परिणामस्वरूप कृत्रिम विकास व्यापक रूप से मान्यता प्राप्त अनुकूलन बन गया। और 1970 के प्रारंभ में रेचेनबर्ग समूह विकास की रणनीतियों के माध्यम से जटिल आभियांत्रिकी समस्याओं को हल करने में समर्थ था। एक अन्य दृष्टिकोण था लॉरेंस जे फोगल की विकास प्रोग्रामिंग तकनीक, जिसे कृत्रिम होशियारी उत्पन्न करने के लिए प्रस्तावित किया गया। 
विकासवादी प्रोग्रामिंग ने मूल रूप से वातावरण की भविष्यवाणी के लिए परिमित अवस्था की मशीनों का प्रयोग किया और पूर्वानुमान के तर्क को अनुकूलित करने के लिए विभेद और चयन का प्रयोग किया। 
1970 के प्रारंभ में जॉन होलेन्ड के कार्य के माध्यम से आनुवंशिक एल्गोरिथम विशेष रूप से लोकप्रिय बन गया और विशेष रूप से उनकी पुस्तक अडेपटेशन इन नेचुरल एंड आर्टिफिशल सिस्टम्स  (1975) के कारण ऐसा हुआ। उनका कार्य सेलुलर ऑटोमेटा के अध्ययन के साथ उत्पन्न हुआ, इसे मिशिगन विश्वविद्यालय में हॉलैंड और उनके विद्यार्थियों के द्वारा संचालित किया गया। हॉलैंड ने अगली पीढी की गुणवत्ता के निर्धारण के लिए एक औपचारिक रुपरेखा जारी की, जिसे होलेन्ड की स्कीमा प्रमेय के नाम से जाना जाता है। 
GA में अनुसंधान 1980 के मध्य तक बड़े पैमाने पर सैद्धांतिक बने रहे, जब आनुवंशिक एल्गोरिथम पर पहले अंतर्राष्ट्रीय सम्मलेन को पिट्सबर्ग, पेन्सिलवेनिया में आयोजित किया गया।
जैसे जैसे अकादमिक रूचि बढ़ती गयी, डेस्कटॉप कम्प्यूटेशनल क्षमता में नाटकीय वृद्धि ने नयी तकनीक के व्यवहारिक अनुप्रयोग में मदद की. 
1980 के दशक के अंत में, जनरल इलेक्ट्रिक ने दुनिया के पहले आनुवंशिक एल्गोरिथम के उत्पाद को बेचना शुरू किया, औद्योगिक प्रक्रियाओं के लिए एक मुख्य रुपरेखा पर आधारित टूलकिट डिजाइन किया गया। 1989 में, एक्सेलिस, इन्कोर्पोरेशन ने दुनिया के दूसरे और डेस्कटॉप कंप्यूटर के पहले GA उत्पाद इवोल्वर को जारी किया। 
न्यूयॉर्क टाइम्स प्रौद्योगिकी लेखक जॉन मर्कोफ्फ़ ने लिखा 1990 में इवोल्वर के बारे में लिखा.