Loading AI tools
विकिपीडिया से, मुक्त विश्वकोश
जेनेटिक एल्गोरिथ्म (GA) एक सर्च (खोज) तकनीक है जिसका उपयोग इष्टतमीकरण तथा खोजने की समस्याओं के लिए सटीक या सन्निकट हल प्राप्त करने के लिए किया जाता है। यह एल्गोरिद्म, अनेकों विकासात्मक कलनविधियों में से एक है। विकासात्मक कलनविधियाँ, विकासवाद तथा उससे सम्बन्धित अवधारणाओं (वंशागति, उत्परिवर्तन, चुनाव, तथा क्रासओवर आदि) तकनीकों के अनुसरण पर आधारित हैं।
आनुवंशिक एल्गोरिथ्म का क्रियान्वयन एक कंप्यूटर सिमुलेशन में किया जाता है, जिसमें एक समस्या के अनुकूलन के लिए उम्मीदवार के समाधान (व्यक्ति, प्राणी या लक्षण प्रारूप (phenotype) कहलाता है) के सार प्रतिनिधित्व (जो जीनोम का जीनोटाईप (जीन प्रारूप) या गुणसूत्र कहलाता है) की एक आबादी बेहतर हल विकसित करती है।
परंपरागत रूप से, समाधान को 0 और 1 की श्रृंखला के रूप में द्विआधारी (binary) में व्यक्त किया जाता है, लेकिन अन्य एनकोडिंग भी संभव है। विकास आमतौर पर यादृच्छिक रूप से उत्पन्न हुए व्यक्तियों से शुरू होता है और पीढियों में होता है।
प्रत्येक पीढी में, प्रत्येक व्यक्ति की फिटनेस का मूल्यांकन किया जाता है, वर्तमान आबादी से स्टोकेस्टिक रूप से कई व्यक्तियों का चयन किया जाता है (उनकी फिटनेस यानि स्वास्थ्य के आधार पर) और नयी आबादी के निर्माण के लिए उनमें संशोधन किया जाता है (पुनर्संयोजन और संभवतया यादृच्छिक रूप से उत्परिवर्तित).
इसके बाद एल्गोरिथ्म की अगले चरण में नयी आबादी का उपयोग किया जाता है।
सामान्यतः, एल्गोरिथ्म तब ख़त्म होता है जब या तो पीढियों की अधिकतम संख्या उत्पन्न हो चुकी हो या आबादी के लिए एक संतोषजनक फिटनेस का स्तर प्राप्त किया जा चुका हो.
यदि एल्गोरिथ्म की समाप्ति पीढियों की अधिकतम संख्या के कारण हुई है, तो एक संतोषजनक समाधान प्राप्त हो सकता है या नहीं भी हो सकता है।
आनुवंशिक एल्गोरिथ्म जैव सूचना (bioinformatics), फाइलोजेनेटिक्स, कम्प्यूटेशनल विज्ञान, अभियांत्रिकी (engineering), अर्थशास्त्र (economics), रसायन विज्ञान (chemistry), विनिर्माण (manufacturing), गणित (mathematics), भौतिकी (physics) और अन्य क्षेत्रों में अनुप्रयोग प्राप्त करता है।
एक प्रारूपिक आनुवंशिक एल्गोरिथ्म के लिए आवश्यक है:
समाधान का एक मानक प्रतिनिधित्व बिट की एक एरे (सारणी) है। अन्य प्रकार और सरंचनाओं के एरे को आवश्यक रूप से सामान तरीके से प्रयुक्त किया जा सकता है। मुख्य गुण जो इन आनुवंशिक प्रतिनिधित्वों को सुविधाजनक बनाता है, वह यह है कि उनके भाग उनके निश्चित आकार के कारण आसानी से संरेखित हो जाते हैं, जो साधारण क्रोसोवर क्रियाविधि को आसान बनाता है।
चर लंबाई प्रतिनिधित्व का भी उपयोग किया जा सकता है, लेकिन इस मामले में क्रोसओवर क्रियान्वयन अधिक जटिल हो जाता है।
वृक्ष के प्रकार के प्रतिनिधित्व आनुवंशिक प्रोग्रामिंग में प्रकट होते हैं और प्रतिनिधित्व से प्राप्त ग्राफ विकासवादी प्रोग्रामिंग में प्रकट होते हैं।
फिटनेस फंक्शन को आनुवंशिक प्रतिनिधित्व पर परिभाषित किया जाता है और यह प्रतिनिधित्व के समाधान की गुणवत्ता का मापन करता है।
फिटनेस फंक्शन हमेशा समस्या पर निर्भर करता है। उदाहरण के लिए, नेप्सेक समस्या में कोई व्यक्ति ऑब्जेक्ट के कुल मान को अधिकतम करना चाहता है जिसे किसी निश्चित क्षमता के नेप्सेक में रखा जा सकता है। एक समाधान की अभिव्यक्ति बिट्स की एक एरे हो सकती है, जहां प्रत्येक बिट एक भिन्न ऑब्जेक्ट को अभिव्यक्त करता है और बिट का मान (0 या 1) अभिव्यक्त करता है कि ऑब्जेक्ट नेप्सेक में है या नहीं.
ऐसी प्रत्येक अभिव्यक्ति मान्य नहीं होती है, क्योंकि ऑब्जेक्ट का आकार नेप्सेक की क्षमता से अधिक हो एकता है। समाधान की फिटनेस नेप्सेक में सभी ओब्जेक्ट्स के मान के योग के बराबर है यदि अभिव्यक्ति मान्य है या अन्यथा 0 है। कुछ समस्याओं में, फिटनेस के व्यंजक को परिभाषित करना या तो मुश्किल होता है या फिर असंभव होता है; इन मामलों में, इंटरेक्टिव आनुवंशिक एल्गोरिथ्म का उपयोग किया जाता है।
एक बार जब हम आनुवंशिक अभिव्यक्ति और फिटनेस फंक्शन को परिभाषित कर लेते हैं, GA समाधान की आबादी को शुरू करने के लिए आगे बढ़ता है, फिर उत्परिवर्तन, क्रोसोवर, उत्क्रमण और चयन ऑपरेटरों के माध्यम से इसमें सुधार करता है।
प्रारंभ में एक प्रारंभिक आबादी के निर्माण के लिए कई व्यक्तिगत समाधान यादृच्छिक रूप से उत्पन्न किये जाते हैं। आबादी का आकार समस्या की प्रकृति पर निर्भर करता है, लेकिन इसमें प्रारूपिक रूप से कई सैंकडों हजारों संभव समाधान होते हैं। परंपरागत रूप से, जनसंख्या यादृच्छिक रूप से उत्पन्न होती है और संभव समाधानों की पूरी रेंज को कवर करती है (सर्च स्पेस). कभी कभी, समाधान उन क्षेत्रों में "शुरू किये" जा सकते हैं जहां अनुकूलतम समाधान मिलने की संभावना होती है।
प्रत्येक अगली पीढी के दौरान, एक नयी पीढी के प्रजनन के लिए मौजूदा आबादी के एक अनुपात का चयन किया जाता है। एक फिटनेस आधारित प्रक्रिया के माध्यम से व्यक्तिगत समाधानों का चयन किया जाता है, जहां प्रारूपिक रूप से अधिक फिट समाधान (जैसा कि एक फिटनेस फंक्शन के द्वारा मापा जाता है) के चुने जाने की अधिक संभावना होती है।
विशिष्ट चयन विधियां प्रत्येक समाधान कि फिटनेस को निर्धारित करती हैं और सर्वोत्तम समाधान के चुनाव को प्राथमिकता देती हैं।
अन्य विधियां आबादी के केवल एक यादृच्छिक नमूने को निर्धारित करती हैं, क्योंकि इस प्रक्रिया में बहुत अधिक समय लग सकता है।
अधिकांश फंक्शन स्टोकेस्टिक होते हैं और उन्हें इस प्रकार से डिजाइन किया जाता है कि कम फिट समाधान के एक छोटे अनुपात का चयन किया जाये. यह बुरे समाधान पर समय पूर्व अभिसरण को रोकते हुए, आबादी की विविधता को बड़ा बनाने में मदद करता है।
लोकप्रिय और अच्छी प्रकार से चयन की गयी विधियों में शामिल हैं रौलेट व्हील चयन और टूर्नामेंट चयन.
अनुवांशिक ऑपरेटर के माध्यम से चयन किये गए समाधान की दूसरी पीढी की आबादी को उत्पन्न करने का अगला चरण है: क्रॉसओवर (जो पुनर्संयोजन (crossover) भी कहलाता है) और / या उत्परिवर्तन (mutation).
उत्पन्न किये जाने वाले प्रत्येक नए समाधान के लिए, "जनक" समाधान के एक युग्म का चयन किया जाता है, ताकि पहले चयन किये गए पूल से प्रजनन किया जा सके. क्रोस ओवर और उत्परिवर्तन की उपरोक्त विधि का प्रयोग करते हुए, एक "बच्चा या संतान" समाधान के उत्पादन के द्वारा, एक नया समाधान निर्मित किया जाता है, जो प्रारूपिक रूप से इसके "जनक" के कई लाक्षणिक गुण रखता है। प्रत्येक बच्चे के लिए नए जनक का चयन किया जाता है और यह प्रक्रिया तब तक जारी रहती है जब तक उपयुक्त आकार के समाधान की एक नयी आबादी उत्पन्न नहीं हो जाती है।
हालांकि प्रजनन की विधियां जो दो जनकों की उपयोग पर आधारित हैं, वे "जैव विज्ञान से अधिक प्रेरित" हैं, हाल ही में किये गए अनुसंधान (इस्लाम अबाऊ एल अता 2006)[उद्धरण चाहिए] सुझाव देते हैं कि दो से अधिक "जनकों" का उपयोग करना एक अच्छी गुणवत्ता के गुणसूत्र के प्रजनन के लिए बेहतर है।
इन प्रक्रियाओं के परिणामस्वरूप अंततः गुणसूत्रों की अगली पीढी की आबादी उत्पन्न होती है जो प्रारंभिक पीढी से अलग होती है।
आमतौर पर आबादी के लिए इस प्रक्रिया के द्वारा औसतन फिटनेस में वृद्धि होगी, चूंकि पहली पीढी से केवल सर्वोत्तम जीवों को प्रजनन के लिए चुना जाता है, साथ ही कम फिट समाधान के एक छोटे अनुपात को लिया जाता है, इसके लिए कारण ऊपर बताये गए हैं।
पीढियों की इस प्रक्रिया को तब तक दोहराया जाता है जब तक एक समाप्ति की स्थिति नहीं आ जाती है। समाप्ति के लिए सामान्य शर्तें हैं:
(Simple generational genetic algorithm pseudocode)
आनुवंशिक एल्गोरिथम के माध्यम से समाधान की पीढी के बारे में कई सामान्य प्रेक्षण हैं:
जटिल उच्च आयामी, बहुलमोड़ की समस्याओं हेतु अनुकूल हल की खोज के लिए अक्सर बहुत महंगे फिटनेस फंक्शन मूल्यांकन की आवश्यकता होती है। असली दुनिया की समस्याओं जैसे संरचनात्मक अनुकूलन समस्याओं में, एकमात्र फंक्शन मूल्यांकन के लिए पूर्ण सिमुलेशन के कई घंटों से कई दिनों तक की जरुरत हो सकती है। प्रारूपिक अनुकूलन पद्धति इस प्रकार की समस्या से निपट नहीं सकती है।
इस मामले में, संभवतया यह जरुरी हो सकता है कि एक सटीक मूल्यांकन को छोड़ दिया जाये और एक ऐसे सन्निकटन फिटनेस का प्रयोग किया जाये जो संगणना की दृष्टि से प्रभावी है। ऐसा प्रतीत होता है सन्निकट नमूनों का सम्मिश्रण एक ऐसा सबसे वायदापूर्ण दृष्टिकोण हो सकता है जो जटिल वास्तविक जीवन की समस्याओं को हल करने के लिए जान बूझ कर EA का प्रयोग करता है।
इसका अर्थ यह है कि यह नहीं जानता है कि दीर्घकालिक फिटनेस प्राप्त करने के लिए अल्पकालिक फिटनेस का बलिदान कैसे दिया जाये. इस घटना की संभावना फिटनेस लैण्डस्केप के आकार पर निर्भर करती है: विशिष्ट समस्याएं एक वैश्विक अनुकूलता के प्रति एक आसान चढाई को उपलब्ध कराती हैं, अन्य स्थानीय अनुकूलता की खोज के लिए फंक्शन हेतू इसे आसान बनाते हैं। इस समस्या को भिन्न फिटनेस फंक्शन के उपयोग से, उत्परिवर्तन की दर के बढ़ने से, या उन चयनात्मक तकनीकों के उपयोग से कम किया जा सकता है, जो समाधानों की विविध आबादी को बनाये रखती हैं, हालांकि नो फ्री लंच प्रमेय (No Free Lunch) सिद्ध करती है कि इस समस्या का कोई सामान्य समाधान नहीं है। विविधता को बनाये रखने की एक सामान्य तकनीक है एक "नीचे पेनल्टी (niche penalty)" को अध्यारोपित करना, जिसमें, पर्याप्त समानता (नीचे रेडियस (niche radius)) के व्यक्तियों के किसी समूह में अतिरिक्त पेनल्टी होती है, जो आने वाली पीढियों में उस समूह की अभिव्यक्ति को कम करेगी, जिससे जनसंख्या में अन्य व्यक्तियों (कम सामान) को बनाये रखा जा सके. यह दांव, तथापि, इस समस्या के परिदृश्य के आधार पर प्रभावी नहीं हो सकती है। आनुवंशिक एल्गोरिथम (और आनुवंशिक प्रोग्रामिंग) में विविधता महत्वपूर्ण है क्योंकि एक समजीनी आबादी का क्रोसिंग ओवर नए समाधान नहीं देता है। विकास रणनीतियों और विकास प्रोग्रामिंग में, उत्परिवर्तन पर अधिक निर्भरता के कारण विविधता जरुरी नहीं है।
इस के लिए एक उपाय के रूप में कई विधियों के प्रस्ताव दिए गए हैं, जैसे किसी तरह से आनुवंशिक विविधता को बढ़ाकर और जल्दी अभिसरण को रोक कर, या तो उत्परिवर्तन की संभावना को बढा कर जब विलयन की गुणवत्ता गिर जाती है, (ट्रिगर हो गया अति उत्परिवर्तन या triggered hypermutation कहलाता है), या कभी कभी जीन पूल में पूरी तरह से नए, यादृच्छिक रूप उत्पन्न तत्वों के द्वारा (यादृच्छिक अप्रवासी या random immigrants कहलाते हैं).फिर से विकास की रणनीतियों और विकास की प्रोग्रामिंग को एक तथाकथित "कोमा रणनीति (comma strategy)" के साथ क्रियान्वित किया जा सकता है, जिसमें जनकों को संभाल कर नहीं रखा जाता है और नए जनकों का चुनाव केवल संतति से ही किया जाता है। यह गतिशील समस्याओं पर अधिक प्रभावी हो सकता है।
इन मामलों में, एक यादृच्छिक सर्च एक समाधान को उतनी ही जल्दी खोज सकती है जितनी कि एक GA. हालांकि, यदि स्थिति ऐसी है कि सफलता/असफलता के परीक्षण को (संभवतया) अलग अलग परिणाम देते हुए दोहराया जाता है, तो सफलता और असफलता का अनुपात एक उपयुक्त फिटनेस का माप उपलब्ध कराता है।
कुछ लोग यह तर्क देते हैं कि क्रोसओवर सबसे अधिक महत्वपूर्ण है, जबकि उत्परिवर्तन केवल यह सुनिश्चित करने के लिए आवश्यक है कि संभावी समाधान खोये नहीं हैं।
दूसरे लोगों का तर्क है कि बहुत अधिक समतल आबादी में केवल क्रोसओवर ही उन नवाचारों को आगे बढ़ाता है जो मूल रूप से उत्परिवर्तन से पैदा हुए हैं और एक अ-समतल आबादी में क्रोसओवर लगभग हमेशा एक बहुत बड़े उत्परिवर्तन के समतुल्य होता है। (जिसके भयावह (catastrophic) होने की संभावना होती है) फोगल (2006) में ऐसे कई सन्दर्भ हैं जो उत्परिवर्तन आधारित सर्च के महत्त्व का समर्थन करते हैं, लेकिन इन सभी समस्याओं के पार नो फ्री लंच प्रमेय बनी रहती है, इसलिए ये राय मेरिट के बिना हैं जब तक चर्चा को एक विशेष समस्या के लिए प्रतिबंधित न किया जाये.
यही बात निश्चित रूप से विकास की रणनीतियों और विकास की प्रोग्रामिंग के लिए भी सच है।
वैकल्पिक और पूरक एल्गोरिथम में शामिल हैं विकास की रणनीतियां, विकास की प्रोग्रामिंग, सिमुलेटेड एनिलिंग, गाउसी अनुकूलन और स्वार्म होशियारी, (उदाहरण: चींटी कॉलोनी अनुकूलन, कण झुंड अनुकूलनकण स्वार्म अनुकूलन) और पूर्णांक रैखिक प्रोग्रामिंग पर आधारित विधियां .
जिस प्रश्न की कोई समस्या आनुवंशिक एल्गोरिथम के लिए उपयुक्त है (इस अर्थ में कि ऐसे एल्गोरिथम दूसरों से बेहतर हैं) वह खुली और विवादस्पद होती है।
उत्परिवर्तन की एक बहुत कम दर एक आनुवंशिक ड्रिफ्ट पैदा कर सकती है (जो स्वभाव से गैर-एर्गोडिक होती है). एक पुनर्संयोजन दर, जो बहुत उच्च है, वह आनुवंशिक एल्गोरिथम के समयपूर्व अभिसरण का कारण हो सकता है।
एक बहुत उच्च उत्परिवर्तन दरभी अच्छे समाधानों की क्षति का कारण हो सकती है, जब तक संभ्रांतवादी चयन न हो.
इन पैरामीटर्स के लिए सैद्धांतिक उपरी और नीचले बंधन हैं लेकिन अब तक प्रायोगिक बंधन नहीं हैं, जो चयन के मार्गदर्शन में मदद कर सकते हैं।
सरलतम एल्गोरिथ्म प्रत्येक गुणसूत्र को एक बिट श्रृंखला के रूप में अभिव्यक्त करता है।
आमतौर पर, आंकिक पैरामीटर्स को पूर्णांक के द्वारा व्यक्त किया जा सकता है, हालांकि फ्लोटिंग बिंदु निरूपण का उपयोग करना भी संभव है। फ्लोटिंग बिन्दु निरूपण, विकास की रणनीतियों और विकास की प्रोग्रामिंग के लिए स्वाभाविक है। वास्तविक मान के आनुवंशिक एल्गोरिथम की अवधारणा को पेश किया गया है लेकिन यह वास्तव में एक मिथ्या अवधारणा है, क्योंकि यह वास्तव में बिल्डिंग ब्लॉक सिद्धांत को अभिव्यक्त नहीं करती है, जिसे 1970 के दशक में होलेन्ड के द्वारा प्रस्तावित किया गया था।
यह सिद्धांत भी समर्थन से रहित नहीं है हालांकि यह सैद्धांतिक और प्रायोगिक परिणामों पर आधारित है (नीचे देखें). बुनियादी एल्गोरिथ्म बिट स्तर पर क्रोसओवर और उत्परिवर्तन करता है। अन्य विभेद गुणसूत्र के साथ संख्याओं की एक सूची के जैसा व्यवहार करते हैं जो एक निर्देश सारणी में अनुक्रमित हैं, एक लिंक्ड सूची, हेश, ऑब्जेक्ट, या किसी अन्य काल्पनिक डेटा सरंचना में नोड्स हैं।
क्रोसओवर और उत्पर्तन, डेटा तत्व सीमा के सन्दर्भ में किये जाते हैं। अधिकांश डेटा प्रकार के लिए, विशिष्ट विभेदन ऑपरेटरों को डिजाइन किया जा सकता है।
विभिन्न गुणसूत्री डेटा के प्रकार, भिन्न विशिष्ट समस्या डोमेन के लिए बेहतर या बदतर कार्य करते हैं।
जब पूर्णांक के बिट श्रृंखला निरूपण का उपयोग किया जाता है, ग्रे कोडिंग को अक्सर काम में लिया जाता है।
इस प्रकार से, पूर्णांक में छोटे परिवर्तन उत्परिवर्तन या क्रोस ओवर से शीघ्र ही प्रभावित हो सकते हैं। ऐसा पाया गया है कि यह तथाकथित हेमिंग वॉल्स पर समयपूर्व अभिसरण को रोकने में मदद करता है, जिसमें बहुत अधिक समकालीन उत्परिवर्तन (या क्रोसओवर की घटनाएं) होने चाहियें ताकि एक बेहतर समाधान के लिए गुणसूत्र में परिवर्तन आ जाये.
अन्य दृष्टिकोणों में शामिल है गुणसूत्र की अभिव्यक्ति के लिए बिट श्रृंखला के उपयोग के बजाय वास्तविक मान की संख्याओं के एरे का उपयोग करना. सिद्धांततः, जितना छोटा वर्ण होगा, उतना बेहतर प्रदर्शन होगा, लेकिन विडंबना यह है कि, वास्तविक मान के गुणसूत्रों का उपयोग करते हुए अच्छे परिणाम प्राप्त किये गए हैं।
एक नयी आबादी के निर्माण की सामान्य प्रक्रिया का एक बहुत ही सफल (हल्का) विभेद है, वर्तमान पीढी से किसी बेहतर जीव को प्राप्त करने में मदद करना जो अगले अपरिवर्तित जीव को स्थानांतरित हो. यह रणनीति संभ्रांतवादी चयन (elitist selection) के रूप में जानी जीती है।
आनुवंशिक एल्गोरिथम का सामानांतर क्रियान्वयन दो रूपों में आता है। स्थूल कणों का समानान्तर आनुवंशिक एल्गोरिथम प्रत्येक कंप्यूटर नोड पर एक आबादी और नोड्स के बीच व्यक्तियों के प्रवास को बताता है।
सूक्ष्म कणों का समानान्तर आनुवंशिक एल्गोरिथम प्रत्येक प्रोसेसर नोड पर एक व्यक्ति को बताता है जो चयन और प्रजनन के लिए पडौसी जीवों के साथ कार्य करता है।
अन्य विभेद, जैसे ऑनलाइन अनुकूलन समस्याओं के लिए आनुवंशिक एल्गोरिथम, फिटनेस फंक्शन में शोर या समय पर निर्भरता शुरू करते हैं।
यह GA के अन्य अनुकूलन विधियों के साथ संयोजन हेतु बहुत प्रभावी हो सकता है।
सामान्य रूप से अच्छे वैश्विक समाधान की खोज करने में GA की प्रवृति बहुत अच्छी होती है, लेकिन पूर्णतया अनुकूल की खोज के लिए पिछले कुछ उत्परिवर्तनों की खोज में यह काफी अप्रभावी होता है।
अन्य तकनीकें (जैसे साधारण पहाडी की चढ़ाई) एक सीमित क्षेत्र में पूर्णतया अनुकूल की खोज में बहुत प्रभावी होती हैं।
पहाडी के चढ़ाई में मजबूती के अभाव को पार पाने के लिए वैकल्पिक GA और पहाडी की चढ़ाई GA की प्रभावित को बढा सकते हैं।
इसका अर्थ यह है कि प्राकृतिक मामले में आनुवंशिक विभिन्नता के नियमों का भिन्न अर्थ हो सकता है।
उदाहरण के लिए-दिया गया है कि चरणों को क्रमागत क्रम में संग्रहित किया गया है-क्रोसिंग ओवर पैतृक DNA से पदों की संख्या को जोड़ते हुए मातृक DNA से पदों की संख्या का योग कर सकता है और ऐसा चलता रहता है।
यह उन सदिशों के योग की तरह है जिनके लक्षण प्ररुपी परिदृश्य में एक रिज का अनुसरण करने की संभावना अधिक होती है।
इस प्रकार से इस प्रक्रिया की कुशलता कि परिमाण के कई क्रमों के द्वारा बढाया जा सकता है। इसके अलावा, उलटा ऑपरेटर (inversion operator) के पास यह मौका होता है कि वह प्रभाविता की उत्तरजीविता के पक्ष में पदों को क्रमागत क्रम में या किसी अन्य उपयुक्त क्रम में रख सके.
(उदाहरण के लिए देखें[1] या यात्रा करते हुए विक्रेता की समस्या में उदाहरण.)
आबादी-आधारित वृद्धि शिक्षण (Population-based incremental learning) एक विभेद है जहां एक पूर्ण रूप में आबादी इसके व्यक्तिगत सदस्यों के बजाय उत्पन्न होती है।
वे समस्याएं जो आनुवंशिक एल्गोरिथम के द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं, उनमें शामिल हैं समय सारणी बनाने और समयबद्धन की समस्याएं (timetabling and scheduling problems) और कई समयबद्धन सॉफ्टवेयर पैकेज GAs पर आधारित होते हैं।
GAs को अभियांत्रिकी (engineering) पर भी लागू किया जा सकता है। आनुवंशिक एल्गोरिथम को अक्सर वैश्विक अनुकूलन समस्याओं के समाधान के एक दृष्टिकोण के रूप में लागू किया जाता है।
चूंकि थम्ब आनुवंशिक एल्गोरिथम का एक सामान्य नियम समस्या डोमेन में उपयोगी हो सकता है जिसमें पुनर्संयोजन के रूप में एक जटिल फिटनेस परिदृश्य होता है, जिसे आबादी को स्थानीय ओपटिमा से दूर हटाने के लिए डिजाइन किया जाता है, ताकि पारंपरिक पहाड़ी चढाई एल्गोरिथम इसमें जुड़ जाये.
विकास का कंप्यूटर सिमुलेशन 1954 में नील्स आल बेरीसेली के कार्य के साथ शुरू हुआ, जो न्यू जर्सी में इंस्टीट्युट फॉर एडवांस्ड स्टडी इन प्रिंसटन में कंप्यूटर का उपयोग कर रहे थे।[2][3]उनके 1954 के प्रकाशन पर अधिक ध्यान नहीं दिया गया। 1957 में शुरू करके,[4] ऑस्ट्रेलियाई मात्रात्मक आनुवंशिकी विज्ञानी एलेक्स फ्रासर ने, मापन योग्य लक्षण का नियंत्रण करने वाले एकाधिक बिन्दुपथ से युक्त जीव के कृत्रिम चयन के सिमुलेशन पर पेपर्स की एक श्रृंखला प्रकाशित की.
इन शुरुआत से, जीव विज्ञानियों के द्वारा विकास का कंप्यूटर सिमुलेशन 1960 के दशक के प्रारंभ में अधिक सामान्य बन गया और विधियों को फ्रासर और बरनेल (1970)[5] और क्रोस्बी (1973)[6]के द्वारा पुस्तकों में वर्णित किया गया।
फ्रासर के सिमुलेशन में आधुनिक आनुवंशिक एल्गोरिथम के सभी आवश्यक तत्व शामिल हैं।
इसके अतिरिक्त, हंस ब्रेमरमेन ने 1960 के दशक में कागजों की एक श्रृंखला प्रकाशित की जिसमें भी समस्याओं के अनुकूलन, पुनर्संयोजन, उत्परिवर्तन और चयन के लिए समाधान की आबादी को अपनाया गया। ब्रेमरमेन के अनुसंधान में भी आधुनिक आनुवंशिक एल्गोरिथम के तत्व शामिल हैं। अन्य उल्लेखनीय प्रारंभिक पथ प्रदर्शकों में शामिल हैं, रिचर्ड फ्रीदबर्ग, जॉर्ज फ्रीदमेन और माइकल कोनराड. कई आरंभिक पत्रों को फोगल के द्वारा (1998) पुनः मुद्रित किया गया।[7]
हालांकि बेरीसेली, की 1963 की रिपोर्ट में, एक साधारण खेल खेलने की क्षमता के विकास को सिमुलेट किया गया,[8] 1960 के दशक में इंगो रेचेनबर्ग और हंस-पॉल श्वेफेलके कार्य के परिणामस्वरूप कृत्रिम विकास व्यापक रूप से मान्यता प्राप्त अनुकूलन बन गया। और 1970 के प्रारंभ में रेचेनबर्ग समूह विकास की रणनीतियों के माध्यम से जटिल आभियांत्रिकी समस्याओं को हल करने में समर्थ था।[9][10][11][12] एक अन्य दृष्टिकोण था लॉरेंस जे फोगल की विकास प्रोग्रामिंग तकनीक, जिसे कृत्रिम होशियारी उत्पन्न करने के लिए प्रस्तावित किया गया।
विकासवादी प्रोग्रामिंग ने मूल रूप से वातावरण की भविष्यवाणी के लिए परिमित अवस्था की मशीनों का प्रयोग किया और पूर्वानुमान के तर्क को अनुकूलित करने के लिए विभेद और चयन का प्रयोग किया। 1970 के प्रारंभ में जॉन होलेन्ड के कार्य के माध्यम से आनुवंशिक एल्गोरिथम विशेष रूप से लोकप्रिय बन गया और विशेष रूप से उनकी पुस्तक अडेपटेशन इन नेचुरल एंड आर्टिफिशल सिस्टम्स (1975) के कारण ऐसा हुआ। उनका कार्य सेलुलर ऑटोमेटा के अध्ययन के साथ उत्पन्न हुआ, इसे मिशिगन विश्वविद्यालय में हॉलैंड और उनके विद्यार्थियों के द्वारा संचालित किया गया। हॉलैंड ने अगली पीढी की गुणवत्ता के निर्धारण के लिए एक औपचारिक रुपरेखा जारी की, जिसे होलेन्ड की स्कीमा प्रमेय के नाम से जाना जाता है। GA में अनुसंधान 1980 के मध्य तक बड़े पैमाने पर सैद्धांतिक बने रहे, जब आनुवंशिक एल्गोरिथम पर पहले अंतर्राष्ट्रीय सम्मलेन को पिट्सबर्ग, पेन्सिलवेनिया में आयोजित किया गया।
जैसे जैसे अकादमिक रूचि बढ़ती गयी, डेस्कटॉप कम्प्यूटेशनल क्षमता में नाटकीय वृद्धि ने नयी तकनीक के व्यवहारिक अनुप्रयोग में मदद की. 1980 के दशक के अंत में, जनरल इलेक्ट्रिक ने दुनिया के पहले आनुवंशिक एल्गोरिथम के उत्पाद को बेचना शुरू किया, औद्योगिक प्रक्रियाओं के लिए एक मुख्य रुपरेखा पर आधारित टूलकिट डिजाइन किया गया। 1989 में, एक्सेलिस, इन्कोर्पोरेशन ने दुनिया के दूसरे और डेस्कटॉप कंप्यूटर के पहले GA उत्पाद इवोल्वर को जारी किया। न्यूयॉर्क टाइम्स प्रौद्योगिकी लेखक जॉन मर्कोफ्फ़ ने लिखा 1990 में इवोल्वर के बारे में लिखा.[13]
जहां एक ओर यह आनुवंशिक एल्गोरिथम ओर स्थानीय सर्च के अन्य रूपों से आम तौर पर निम्न होता है, यह उन समस्याओं में परिणाम उत्पन्न कर सकता है, जहां कोई वैश्विक या अद्यतन परिप्रेक्ष्य प्राप्त नहीं किये जा सकते हैं, ओर इस प्रकार से अन्य विधियों को लागू नहीं किया जा सकता है। [उद्धरण चाहिए]
विकासवादी पारिस्थितिकी सजीवों का उनके वातावरण के परिप्रेक्ष्य में अध्ययन है, जिसका उद्देश्य है यह खोज करना कि वे कैसे अनुकूलित होते हैं। इसकी मूल धारणा यह है कि एक विषम युग्मजी वातावरण में आप किसी ऐसे व्यक्ति को नहीं खोज सकते जो पूरे वातावरण को फिट करे. तो, आपको आबादी के स्तर पर कारण देना होगा. BAs ने GAs की तुलना में समस्याओं पर बेहतर परिणाम दिए हैं, जैसे जटिल स्थिति समस्याएं, (सेल फोन के लिए एंटीना, शहरी नियोजन और इस प्रकार) और डेटा खनन.[14]
पैरामीटर्स को क्रोस एंट्रोपी न्यूनीकरण के माध्यम से अद्यतन किया जाता है, ताकि अगले चरण में बेहतर नमूने उत्पन्न किये जा सकें.
ES एल्गोरिथम को विशेष रूप से वास्तविक-मान डोमेन में समस्या के समाधान के लिए डिजाइन किया गया है। वे सर्च के नियंत्रण पैरामीटर्स को समायोजित करने के लिए स्व-अनुकूलन का प्रयोग करते हैं।
एल्गोरिथम के पीछे शासक सिद्धांत यह है कि अल्प गुणवत्ता के अवयवों को चयनात्मक रूप से हटाकर एमर्जेंट सुधार और उन्हें यादृच्छिक रूप से चुने गए अवयवों से प्रतिस्थापित करना. इसे GA के साथ निर्धारित किया गया है जो बेहतर समाधान पाने के प्रयास में अच्छे समाधान का चयन करता है।
इसे साधारण पैरामीट्रिक अनुकूलन के लिए भी इस्तेमाल किया जा सकता है। यह एक निश्चित प्रमेय पर निर्भर है जो स्वीकार्यता के सभी क्षेत्रों और सभी गाऊसी वितरण के लिए मान्य है। NA की कुशलता जानकारी प्रमेय और कुशलता की एक निश्चित प्रमेय पर निर्भर करती है
इसकी कुशलता को जानकारी प्राप्त करने के लिए आवश्यक कार्य के द्वारा विभाजित जानकारी के रूप में परिभाषित किया जाता है।[15]क्योंकि NA व्यक्तिगत फिटनेस के बजाय माध्य फिटनेस को अधिकतम करता है, परिदृश्य इतना समतल हो जाता है कि चोटियों के बीच में खाईयां गायब हो जाती हैं। इसलिए इसकी एक निश्चित "महत्वाकांक्षा", फिटनेस या स्वास्थ्य परिदृश्य में स्थानीय चोटियों से बचने की है। NA मूमेंट मेट्रिक्स के अनुकूलन के द्वारा तीखी चढाई की चोटी पर चढ़ने में भी अच्छा होता है, क्योंकि NA गाउसी के विकार (औसत जानकारी) को अधिकतम कर सकता है साथ ही माध्य फिटनेस को स्थिर बनाये रखता है।
मेमेटिक एल्गोरिथम का विचार मेमे (memes) से आया, जो जीन के विपरीत अपने आप को अनुकूलित कर सकते हैं। कुछ समस्या क्षेत्रों में ये पारंपरिक विकास एल्गोरिथम से अधिक कुशल दिखाई देते हैं।
एक उत्परिवर्तन जो फिटनेस या स्वास्थ्य को बढाता है उसे हमेशा स्वीकार किया जाता है।
एक उत्परिवर्तन जो फिटनेस को कम करता है उसे कम होते ताप के पैरामीटर और फिटनेस में अंतर के आधार पर संभवतया स्वीकार किया जाता है। SA की भाषा में, कोई व्यक्ति अधिकतम फिटनेस के बजाय न्यूनतम ऊर्जा की जरुरत की बात करता है। SA का उपयोग, अपेक्षाकृत उत्परिवर्तन की ऊँची दर के साथ शुरू करके और एक दी गयी समय सारणी के अनुसार इसे कम कर के, एक मानक GA एल्गोरिथम के भीतर किया जा सकता है।
एक ऐसे समाधान की ओर जाने से रोका जाता है जिसमें तबू सूची के अवयव शामिल हों, जिसे अद्यतन किया गया हो क्योंकि समाधान, समाधान के स्थान को बढ़ावा देते हैं।
आनुवंशिक एल्गोरिथम को लागू करना अपेक्षाकृत आसान है, लेकिन उनके व्यवहार को समझना मुश्किल है। विशेष रूप से यह समझना मुश्किल है कि वे अक्सर उच्च फिटनेस के समाधान को उत्पन्न करने में सफल क्यों रहते हैं। बिल्डिंग ब्लॉक परिकल्पना (BBH) में शामिल है:
(गोल्डबर्ग 1989:41) सार अनुकूलन क्रियाप्रनाली को निम्नानुसार वर्णित करते हैं:
एक तरह से, इन विशेष स्किमेता (बिल्डिंग ब्लॉक) के साथ कार्य करके, हमने हमारी समस्या की जटिलता को कम कर दिया है; प्रत्येक प्रयास के दरार उच्च प्रदर्शन की श्रृंखला के निर्माण के बजाय, हम पिछले नमूनों के सर्वोत्तम आंशिक समाधान से बेहतर ओर बेहतर श्रृंखला बनाते हैं।
(गोल्डबर्ग 1989) का दावा है कि बिल्डिंग ब्लॉक परिकल्पना कि होलेन्ड की स्कीमा प्रमेय समर्थन देती है।
बिल्डिंग ब्लॉक परिकल्पना की इस आधार पर बहुत अधिक आलोचना की गयी है कि इसमें सैद्धांतिक ओर प्रायोगिक औचित्य परिणामों की कमी है, इसके परिणामों को प्रकाशित भी किया गया है जो इस पर प्रश्न उठाते हैं।
सैद्धांतिक पक्ष में, उदाहरण के लिए, राइट एट अल. कहते हैं कि
प्रयोगात्मक पक्ष पक्ष पर समान क्रोस ओवर देखा गया जो कई फिटनेस फंक्शन पर एक-बिंदु ओर दो-बिंदु क्रोस वोवर को दर्शाता है, इसका अध्ययन सेस्वर्दा के द्वारा किया गया।[18]
इन परिणामों को संक्षेप में बताते हुए फोगल कहते हैं कि
सिस्वर्दा के परिणाम बिल्डिंग ब्लॉक परिकल्पना के खिलाफ हैं क्योंकि समान क्रोस ओवर कम स्कीमेता के साथ बहु विघटनकारी है, जबकि एक ओर दो बिंदु क्रोस ओवर संभवतया कम स्किमेता को अधिक संरक्षित करते हैं और पुनर्संयोजन में पैदा हुए बच्चों में परिभाषित बीत का संयोजन करते हैं।
बिल्डिंग ब्लॉक परिकल्पना पर बहस बताती है कि GAs कैसे "कार्य" करते हैं (यानि प्रदर्शन अनुकूलन) यह मुद्दा वर्तमान से बहुत दूर है।
अनुक्रम पर निर्भर या गैर-अनुक्रम पर निर्भर सेट-अप वातावरण में जॉब के समयबद्धन के लिए ऑब्जेक्टिव, ताकि उत्पादन की मात्रा को बढ़ाते हुए किसी प्रकार के दोष जैसे मंदी को कम किया जा सके.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
