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

मुक्त ज्ञानकोश विकिपीडिया से
(आनुवंशिक एल्गोरिथ्म से अनुप्रेषित)
2006 में निर्मित नासा का अंतरिक्षयान एण्टेना (ST5) : एण्टेना का यह जटिल आकार एक विकासात्मक एल्गोरिद्म का प्रयोग करके प्राप्त किया गया था।
जेनेटिक कलनविधि i: आरम्भन (initialization), f (X): मूल्यांकन (evaluation), ?: समाप्ति की शर्त, Se: चयन (selection), Cr: क्रॉसओवर (crossover), Mu: म्यूटेशन, Re: विस्थापन (replacement), X *: सर्वश्रेष्ठ हल

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

विशेषताएँ[संपादित करें]

लाभ[संपादित करें]

  • (१) यह कलनविधि 'न्वाइजी' स्थितियों के लिए भी अच्छी है।
  • (२) यह मिश्रित समस्याओं पर भी काम करती है जिसमें विविक्त (descrete) और सतत (contineous) दोनों प्रकार के चर उपस्थित हों।
  • (३) यह अवकल (derivatives) का प्रयोग नहीं करता बल्कि पे-ऑफ (objective function) का उपयोग करता है।
  • (४) यह बहूद्देशीय इष्टतमीकरण (multi-objective optimization) के लिए भी उपयोगी है।
  • (५) यह विधि स्थानीय अल्पतम/अधिकतम की दृष्टि से भी रोबस्ट (मजबूत) है।

हानियाँ[संपादित करें]

  • (१) इसमें उद्देश्य फलन (ऑब्जेक्टिव फंक्शन) की डिजाइन करना एवं अन्य कुछ क्रियाएँ कठिन हो सकतीं हैं।
  • (२) यह गणना करने में अधिक समय लेती है।
  • (३) इससे जो 'हल' मिलता है, आवश्यक नहीं कि वह इष्टतम हो। इसके अलावा, समस्या का आकार बढ़ने पर हल की गुणवत्ता और भी बिगड़ जाती है।
  • (४) जेनेटिक कलनविधियों का उपयोग वैश्लेषिक समस्याओं (analytical problems) के लिए करना नहीं चाहिए क्योंकि इनके लिए परम्परागत विधियों के माध्यम से कम समय में ही अच्छा हल मिल सकता है।

पद्धति[संपादित करें]

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

परंपरागत रूप से, समाधान को 0 और 1 की श्रृंखला के रूप में द्विआधारी (binary) में व्यक्त किया जाता है, लेकिन अन्य एनकोडिंग भी संभव है। विकास आमतौर पर यादृच्छिक रूप से उत्पन्न हुए व्यक्तियों से शुरू होता है और पीढियों में होता है।

प्रत्येक पीढी में, प्रत्येक व्यक्ति की फिटनेस का मूल्यांकन किया जाता है, वर्तमान आबादी से स्टोकेस्टिक रूप से कई व्यक्तियों का चयन किया जाता है (उनकी फिटनेस यानि स्वास्थ्य के आधार पर) और नयी आबादी के निर्माण के लिए उनमें संशोधन किया जाता है (पुनर्संयोजन और संभवतया यादृच्छिक रूप से उत्परिवर्तित).

इसके बाद एल्गोरिथ्म की अगले चरण में नयी आबादी का उपयोग किया जाता है।

सामान्यतः, एल्गोरिथ्म तब ख़त्म होता है जब या तो पीढियों की अधिकतम संख्या उत्पन्न हो चुकी हो या आबादी के लिए एक संतोषजनक फिटनेस का स्तर प्राप्त किया जा चुका हो.

यदि एल्गोरिथ्म की समाप्ति पीढियों की अधिकतम संख्या के कारण हुई है, तो एक संतोषजनक समाधान प्राप्त हो सकता है या नहीं भी हो सकता है।

आनुवंशिक एल्गोरिथ्म जैव सूचना (bioinformatics), फाइलोजेनेटिक्स, कम्प्यूटेशनल विज्ञान, अभियांत्रिकी (engineering), अर्थशास्त्र (economics), रसायन विज्ञान (chemistry), विनिर्माण (manufacturing), गणित (mathematics), भौतिकी (physics) और अन्य क्षेत्रों में अनुप्रयोग प्राप्त करता है।


एक प्रारूपिक आनुवंशिक एल्गोरिथ्म के लिए आवश्यक है:

  1. समाधान डोमेन का एक आनुवंशिक प्रतिनिधित्व,
  2. समाधान डोमेन का मूल्यांकन करने के लिए एक फिटनेस फंक्शन.


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

चर लंबाई प्रतिनिधित्व का भी उपयोग किया जा सकता है, लेकिन इस मामले में क्रोसओवर क्रियान्वयन अधिक जटिल हो जाता है।

वृक्ष के प्रकार के प्रतिनिधित्व आनुवंशिक प्रोग्रामिंग में प्रकट होते हैं और प्रतिनिधित्व से प्राप्त ग्राफ विकासवादी प्रोग्रामिंग में प्रकट होते हैं।

फिटनेस फंक्शन को आनुवंशिक प्रतिनिधित्व पर परिभाषित किया जाता है और यह प्रतिनिधित्व के समाधान की गुणवत्ता का मापन करता है।

फिटनेस फंक्शन हमेशा समस्या पर निर्भर करता है। उदाहरण के लिए, नेप्सेक समस्या में कोई व्यक्ति ऑब्जेक्ट के कुल मान को अधिकतम करना चाहता है जिसे किसी निश्चित क्षमता के नेप्सेक में रखा जा सकता है। एक समाधान की अभिव्यक्ति बिट्स की एक एरे हो सकती है, जहां प्रत्येक बिट एक भिन्न ऑब्जेक्ट को अभिव्यक्त करता है और बिट का मान (0 या 1) अभिव्यक्त करता है कि ऑब्जेक्ट नेप्सेक में है या नहीं.

ऐसी प्रत्येक अभिव्यक्ति मान्य नहीं होती है, क्योंकि ऑब्जेक्ट का आकार नेप्सेक की क्षमता से अधिक हो एकता है। समाधान की फिटनेस नेप्सेक में सभी ओब्जेक्ट्स के मान के योग के बराबर है यदि अभिव्यक्ति मान्य है या अन्यथा 0 है। कुछ समस्याओं में, फिटनेस के व्यंजक को परिभाषित करना या तो मुश्किल होता है या फिर असंभव होता है; इन मामलों में, इंटरेक्टिव आनुवंशिक एल्गोरिथ्म का उपयोग किया जाता है।


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


शुरुआत
[संपादित करें]

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

चयन[संपादित करें]

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


विशिष्ट चयन विधियां प्रत्येक समाधान कि फिटनेस को निर्धारित करती हैं और सर्वोत्तम समाधान के चुनाव को प्राथमिकता देती हैं।

अन्य विधियां आबादी के केवल एक यादृच्छिक नमूने को निर्धारित करती हैं, क्योंकि इस प्रक्रिया में बहुत अधिक समय लग सकता है।

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

लोकप्रिय और अच्छी प्रकार से चयन की गयी विधियों में शामिल हैं रौलेट व्हील चयन और टूर्नामेंट चयन.



प्रजनन[संपादित करें]


अनुवांशिक ऑपरेटर के माध्यम से चयन किये गए समाधान की दूसरी पीढी की आबादी को उत्पन्न करने का अगला चरण है: क्रॉसओवर (जो पुनर्संयोजन (crossover) भी कहलाता है) और / या उत्परिवर्तन (mutation).

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

हालांकि प्रजनन की विधियां जो दो जनकों की उपयोग पर आधारित हैं, वे "जैव विज्ञान से अधिक प्रेरित" हैं, हाल ही में किये गए अनुसंधान (इस्लाम अबाऊ एल अता 2006)[उद्धरण चाहिए] सुझाव देते हैं कि दो से अधिक "जनकों" का उपयोग करना एक अच्छी गुणवत्ता के गुणसूत्र के प्रजनन के लिए बेहतर है।

इन प्रक्रियाओं के परिणामस्वरूप अंततः गुणसूत्रों की अगली पीढी की आबादी उत्पन्न होती है जो प्रारंभिक पीढी से अलग होती है।

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

समाप्ति[संपादित करें]

पीढियों की इस प्रक्रिया को तब तक दोहराया जाता है जब तक एक समाप्ति की स्थिति नहीं आ जाती है। समाप्ति के लिए सामान्य शर्तें हैं:

  • एक ऐसा समाधान मिल जाता है जो न्यूनतम मापदंडों को संतुष्ट करता है।
  • पीढियां स्थिर संख्या तक पहुंच जाती हैं।
  • आवंटित बजट (संगणना का समय / धन) प्राप्त हो जाता है।
  • उच्चतम रैंकिंग समाधान एक ऐसे समतल तक पहुंच जाता है या पहुंच गया है, जहां क्रमागत इट्रेशन और अधिक बेहतर परिणाम उत्पन्न नहीं करता है।
  • मानवीय निरीक्षण (Manual inspection)
  • उपरोक्त के संयुग्मन

साधारण पीढ़ीगत आनुवंशिक एल्गोरिथ्म कूट संहिता[संपादित करें]

(Simple generational genetic algorithm pseudocode)

  1. व्यक्तियों की प्रारंभिक आबादी का चयन करें.
  2. उस आबादी में प्रत्येक व्यक्ति की फिटनेस का मूल्यांकन.
  3. इस पीढी को समाप्ति तक दोहराएं: (समय सीमा, पर्याप्त फिटनेस की प्राप्ति, आदि)
    1. प्रजनन के लिए सबसे फिट व्यक्ति को चुनें.
    2. संतति को जन्म देने के लिए क्रॉसओवर और उत्परिवर्तन के माध्यम से नए व्यक्तियों का प्रजनन करें.
    3. नए व्यक्तियों की व्यक्तिगत फिटनेस (स्वास्थ्य) का मूल्यांकन करें.
    4. सबसे कम फिट आबादी को नए व्यक्तियों से प्रतिस्थापित करें.

प्रेक्षण[संपादित करें]

आनुवंशिक एल्गोरिथम के माध्यम से समाधान की पीढी के बारे में कई सामान्य प्रेक्षण हैं:

  • जटिल समस्याओं के लिए बार बार फिटनेस फंक्शन का मूल्यांकन अक्सर, कृत्रिम विकासवादी एल्गोरिथम का सबसे निषिद्ध और सीमित खंड होता है।

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

इस मामले में, संभवतया यह जरुरी हो सकता है कि एक सटीक मूल्यांकन को छोड़ दिया जाये और एक ऐसे सन्निकटन फिटनेस का प्रयोग किया जाये जो संगणना की दृष्टि से प्रभावी है। ऐसा प्रतीत होता है सन्निकट नमूनों का सम्मिश्रण एक ऐसा सबसे वायदापूर्ण दृष्टिकोण हो सकता है जो जटिल वास्तविक जीवन की समस्याओं को हल करने के लिए जान बूझ कर EA का प्रयोग करता है।

  • "बेहतर" केवल अन्य समाधान में तुलना है। परिणामस्वरूप, रोकने की कसौटी स्पष्ट नहीं है।
  • कई समस्याओं में, समस्या के वैश्विक अनुकूलन के बजाय, GAs में साधारण ओप्टिमा या यहां तक कि यादृच्छिक बिन्दुओं के प्रति कवरेज़ की प्रवृति होती है,

इसका अर्थ यह है कि यह नहीं जानता है कि दीर्घकालिक फिटनेस प्राप्त करने के लिए अल्पकालिक फिटनेस का बलिदान कैसे दिया जाये. इस घटना की संभावना फिटनेस लैण्डस्केप के आकार पर निर्भर करती है: विशिष्ट समस्याएं एक वैश्विक अनुकूलता के प्रति एक आसान चढाई को उपलब्ध कराती हैं, अन्य स्थानीय अनुकूलता की खोज के लिए फंक्शन हेतू इसे आसान बनाते हैं। इस समस्या को भिन्न फिटनेस फंक्शन के उपयोग से, उत्परिवर्तन की दर के बढ़ने से, या उन चयनात्मक तकनीकों के उपयोग से कम किया जा सकता है, जो समाधानों की विविध आबादी को बनाये रखती हैं, हालांकि नो फ्री लंच प्रमेय (No Free Lunch) सिद्ध करती है कि इस समस्या का कोई सामान्य समाधान नहीं है। विविधता को बनाये रखने की एक सामान्य तकनीक है एक "नीचे पेनल्टी (niche penalty)" को अध्यारोपित करना, जिसमें, पर्याप्त समानता (नीचे रेडियस (niche radius)) के व्यक्तियों के किसी समूह में अतिरिक्त पेनल्टी होती है, जो आने वाली पीढियों में उस समूह की अभिव्यक्ति को कम करेगी, जिससे जनसंख्या में अन्य व्यक्तियों (कम सामान) को बनाये रखा जा सके. यह दांव, तथापि, इस समस्या के परिदृश्य के आधार पर प्रभावी नहीं हो सकती है। आनुवंशिक एल्गोरिथम (और आनुवंशिक प्रोग्रामिंग) में विविधता महत्वपूर्ण है क्योंकि एक समजीनी आबादी का क्रोसिंग ओवर नए समाधान नहीं देता है। विकास रणनीतियों और विकास प्रोग्रामिंग में, उत्परिवर्तन पर अधिक निर्भरता के कारण विविधता जरुरी नहीं है।


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

इस के लिए एक उपाय के रूप में कई विधियों के प्रस्ताव दिए गए हैं, जैसे किसी तरह से आनुवंशिक विविधता को बढ़ाकर और जल्दी अभिसरण को रोक कर, या तो उत्परिवर्तन की संभावना को बढा कर जब विलयन की गुणवत्ता गिर जाती है, (ट्रिगर हो गया अति उत्परिवर्तन या triggered hypermutation कहलाता है), या कभी कभी जीन पूल में पूरी तरह से नए, यादृच्छिक रूप उत्पन्न तत्वों के द्वारा (यादृच्छिक अप्रवासी या random immigrants कहलाते हैं).फिर से विकास की रणनीतियों और विकास की प्रोग्रामिंग को एक तथाकथित "कोमा रणनीति (comma strategy)" के साथ क्रियान्वित किया जा सकता है, जिसमें जनकों को संभाल कर नहीं रखा जाता है और नए जनकों का चुनाव केवल संतति से ही किया जाता है। यह गतिशील समस्याओं पर अधिक प्रभावी हो सकता है।

  • GA प्रभावी रूप से समस्याओं को हल नहीं कर सकता है, जिसमें केवल फिटनेस का माप ही एकमात्र सही/गलत का माप होता है (जैसे निर्धारण की समस्या (decision problems)), क्योंकि समाधान पर अभिसरण का कोई तरीका नहीं होता है। (चढ़ने के लिए कोई पहाडी नहीं होती है).

इन मामलों में, एक यादृच्छिक सर्च एक समाधान को उतनी ही जल्दी खोज सकती है जितनी कि एक GA. हालांकि, यदि स्थिति ऐसी है कि सफलता/असफलता के परीक्षण को (संभवतया) अलग अलग परिणाम देते हुए दोहराया जाता है, तो सफलता और असफलता का अनुपात एक उपयुक्त फिटनेस का माप उपलब्ध कराता है।

  • चयन स्पष्ट रूप से एक महत्वपूर्ण आनुवंशिक ऑपरेटर होता है, लेकिन राय को क्रोसओवर बनाम उत्परिवर्तन के महत्त्व पर विभाजित किया जाता है।

कुछ लोग यह तर्क देते हैं कि क्रोसओवर सबसे अधिक महत्वपूर्ण है, जबकि उत्परिवर्तन केवल यह सुनिश्चित करने के लिए आवश्यक है कि संभावी समाधान खोये नहीं हैं।

दूसरे लोगों का तर्क है कि बहुत अधिक समतल आबादी में केवल क्रोसओवर ही उन नवाचारों को आगे बढ़ाता है जो मूल रूप से उत्परिवर्तन से पैदा हुए हैं और एक अ-समतल आबादी में क्रोसओवर लगभग हमेशा एक बहुत बड़े उत्परिवर्तन के समतुल्य होता है। (जिसके भयावह (catastrophic) होने की संभावना होती है) फोगल (2006) में ऐसे कई सन्दर्भ हैं जो उत्परिवर्तन आधारित सर्च के महत्त्व का समर्थन करते हैं, लेकिन इन सभी समस्याओं के पार नो फ्री लंच प्रमेय बनी रहती है, इसलिए ये राय मेरिट के बिना हैं जब तक चर्चा को एक विशेष समस्या के लिए प्रतिबंधित न किया जाये.

  • अक्सर, GA तेजी से अच्छे समाधानों को स्थापित कर सकते हैं, यहां तक कि मुश्किल सर्च स्थानों के लिए भी ऐसा संभव है।

यही बात निश्चित रूप से विकास की रणनीतियों और विकास की प्रोग्रामिंग के लिए भी सच है।

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

वैकल्पिक और पूरक एल्गोरिथम में शामिल हैं विकास की रणनीतियां, विकास की प्रोग्रामिंग, सिमुलेटेड एनिलिंग, गाउसी अनुकूलन और स्वार्म होशियारी, (उदाहरण: चींटी कॉलोनी अनुकूलन, कण झुंड अनुकूलनकण स्वार्म अनुकूलन) और पूर्णांक रैखिक प्रोग्रामिंग पर आधारित विधियां .

जिस प्रश्न की कोई समस्या आनुवंशिक एल्गोरिथम के लिए उपयुक्त है (इस अर्थ में कि ऐसे एल्गोरिथम दूसरों से बेहतर हैं) वह खुली और विवादस्पद होती है।

  • चूंकि सभी वर्तमान मशीन लर्निंग समस्याओं के साथ पैरामीटर्स की ट्यूनिंग की जा सकती है जैसे उत्परिवर्तन की संभावना, पुनर्संयोजन की संभावना और जिस समस्या वर्ग पर कार्य किया जा रहा है उसके लिए उपयुक्त सेटिंग खोजने के लिए जनसंख्या का आकार.

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

एक बहुत उच्च उत्परिवर्तन दरभी अच्छे समाधानों की क्षति का कारण हो सकती है, जब तक संभ्रांतवादी चयन न हो.

इन पैरामीटर्स के लिए सैद्धांतिक उपरी और नीचले बंधन हैं लेकिन अब तक प्रायोगिक बंधन नहीं हैं, जो चयन के मार्गदर्शन में मदद कर सकते हैं।

  • फिटनेस फंक्शन का मूल्यांकन और क्रियान्वयन एल्गोरिथम की प्रभाविता और गति में एक महत्वपूर्ण कारक है।



विभेद (Variants)[संपादित करें]

सरलतम एल्गोरिथ्म प्रत्येक गुणसूत्र को एक बिट श्रृंखला के रूप में अभिव्यक्त करता है।

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

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

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

विभिन्न गुणसूत्री डेटा के प्रकार, भिन्न विशिष्ट समस्या डोमेन के लिए बेहतर या बदतर कार्य करते हैं।


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


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



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


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

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



यह GA के अन्य अनुकूलन विधियों के साथ संयोजन हेतु बहुत प्रभावी हो सकता है। सामान्य रूप से अच्छे वैश्विक समाधान की खोज करने में GA की प्रवृति बहुत अच्छी होती है, लेकिन पूर्णतया अनुकूल की खोज के लिए पिछले कुछ उत्परिवर्तनों की खोज में यह काफी अप्रभावी होता है। अन्य तकनीकें (जैसे साधारण पहाडी की चढ़ाई) एक सीमित क्षेत्र में पूर्णतया अनुकूल की खोज में बहुत प्रभावी होती हैं। पहाडी के चढ़ाई में मजबूती के अभाव को पार पाने के लिए वैकल्पिक GA और पहाडी की चढ़ाई GA की प्रभावित को बढा सकते हैं।


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

(उदाहरण के लिए देखें[1] या यात्रा करते हुए विक्रेता की समस्या में उदाहरण.)


आबादी-आधारित वृद्धि शिक्षण (Population-based incremental learning) एक विभेद है जहां एक पूर्ण रूप में आबादी इसके व्यक्तिगत सदस्यों के बजाय उत्पन्न होती है।


समस्या डोमेन (Problem domains)[संपादित करें]

वे समस्याएं जो आनुवंशिक एल्गोरिथम के द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं, उनमें शामिल हैं समय सारणी बनाने और समयबद्धन की समस्याएं (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]


संबंधित तकनीकें[संपादित करें]

  • चींटी कॉलोनी अनुकूलन (ACO) स्थानीय रूप से उत्पादक क्षेत्रों और हल स्थान को तय करने के लिए कई चींटियों (या कारकों) का उपयोग करते हैं।

जहां एक ओर यह आनुवंशिक एल्गोरिथम ओर स्थानीय सर्च के अन्य रूपों से आम तौर पर निम्न होता है, यह उन समस्याओं में परिणाम उत्पन्न कर सकता है, जहां कोई वैश्विक या अद्यतन परिप्रेक्ष्य प्राप्त नहीं किये जा सकते हैं, ओर इस प्रकार से अन्य विधियों को लागू नहीं किया जा सकता है।[उद्धरण चाहिए]



विकासवादी पारिस्थितिकी सजीवों का उनके वातावरण के परिप्रेक्ष्य में अध्ययन है, जिसका उद्देश्य है यह खोज करना कि वे कैसे अनुकूलित होते हैं। इसकी मूल धारणा यह है कि एक विषम युग्मजी वातावरण में आप किसी ऐसे व्यक्ति को नहीं खोज सकते जो पूरे वातावरण को फिट करे. तो, आपको आबादी के स्तर पर कारण देना होगा. BAs ने GAs की तुलना में समस्याओं पर बेहतर परिणाम दिए हैं, जैसे जटिल स्थिति समस्याएं, (सेल फोन के लिए एंटीना, शहरी नियोजन और इस प्रकार) और डेटा खनन.[14]



  • क्रोस-एंट्रोपी विधि क्रोस एंट्रोपी विधि एक पैरामिट्रीकृत संभावना वितरण के माध्यम से उम्मीदवार समाधान उत्पन्न करती है।

पैरामीटर्स को क्रोस एंट्रोपी न्यूनीकरण के माध्यम से अद्यतन किया जाता है, ताकि अगले चरण में बेहतर नमूने उत्पन्न किये जा सकें.


  • सांस्कृतिक एल्गोरिथ्म में आबादी का ऐसा अवयव शामिल है जो आनुवंशिक एल्गोरिथम के लगभग समान होता है, इसके अलावा, एक ज्ञान अवयव विश्वास स्थान कहलाता है।



  • विकास रणनीतियां (ES, रेचेनबर्ग, 1994), उत्परिवर्तन और अंतर मध्यस्थ और असतत पुनर्संयोजन के माध्यम से व्यक्तियों का विकास करती हैं।

ES एल्गोरिथम को विशेष रूप से वास्तविक-मान डोमेन में समस्या के समाधान के लिए डिजाइन किया गया है। वे सर्च के नियंत्रण पैरामीटर्स को समायोजित करने के लिए स्व-अनुकूलन का प्रयोग करते हैं।



  • विकास प्रोग्रामिंग (EP) में प्राथमिक रूप से उत्परिवर्तन और चयन और मनमानी अभिव्यक्ति के साथ समाधान की आबादी शामिल है। वे पैरामीटर्स को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं और उनमें अन्य विभेद कार्यविधियां भी शामिल हो सकती हैं, जैसे एकाधिक जनकों के से जानकारी का संयोजन.


  • बाहरी अनुकूलन (EO) GAs के विपरीत, जो उम्मीदवार समाधान की आबादी के साथ कार्य करता है, EO एकमात्र समाधान विकसित करता है और सबसे बुरे घटकों के लिए स्थानीय संशोधन करता है। इसके लिए यह जरुरी है कि एक उपयुक्त प्रतिनिधित्व का चुनाव किया जाये जो एक गुणवत्ता माप ("फिटनेस") देने के लिए व्यक्तिगत समाधान अवयवों की अनुमति दे.

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



  • गाऊसी अनुकूलन (सामान्य या प्राकृतिक अनुकूलन, GA से भरम न हो इसलिए संक्षेप में NA कहा जाता है संकेत प्रोसेसिंग प्रणाली की निर्माण की उपज को अधिकतम करता है।

इसे साधारण पैरामीट्रिक अनुकूलन के लिए भी इस्तेमाल किया जा सकता है। यह एक निश्चित प्रमेय पर निर्भर है जो स्वीकार्यता के सभी क्षेत्रों और सभी गाऊसी वितरण के लिए मान्य है। NA की कुशलता जानकारी प्रमेय और कुशलता की एक निश्चित प्रमेय पर निर्भर करती है

इसकी कुशलता को जानकारी प्राप्त करने के लिए आवश्यक कार्य के द्वारा विभाजित जानकारी के रूप में परिभाषित किया जाता है।[15]क्योंकि NA व्यक्तिगत फिटनेस के बजाय माध्य फिटनेस को अधिकतम करता है, परिदृश्य इतना समतल हो जाता है कि चोटियों के बीच में खाईयां गायब हो जाती हैं। इसलिए इसकी एक निश्चित "महत्वाकांक्षा", फिटनेस या स्वास्थ्य परिदृश्य में स्थानीय चोटियों से बचने की है। NA मूमेंट मेट्रिक्स के अनुकूलन के द्वारा तीखी चढाई की चोटी पर चढ़ने में भी अच्छा होता है, क्योंकि NA गाउसी के विकार (औसत जानकारी) को अधिकतम कर सकता है साथ ही माध्य फिटनेस को स्थिर बनाये रखता है।


  • आनुवंशिक प्रोग्रामिंग (GP) एक संबंधित तकनीक है जिसे जॉन कोजा के द्वारा लोकप्रिय बने गया जिसमें फंक्शन पैरामीटर्स के बजाय कंप्यूटर प्रोग्राम को अनुकूलित किया जाता है। आनुवंशिक प्रोग्रामिंग आनुवंशिक एल्गोरिथम की प्रारूपिक सरंचना सूची के बजाय अनुकूलन के लिए कंप्यूटर प्रोग्राम कि अभिव्यक्ति हेतु अक्सर वृक्ष-आधारित डेटा सरंचना का उपयोग करता है।



  • समूहन आनुवंशिक एल्गोरिथ्म समूहन (GGA) GA का विकास है जहां ध्यान व्यक्तिगत वस्तुओं से स्थानांतरित कर दिया गया है जैसे क्लासिकल GA में इसे समूहों या आइटम के सबसेट की ओर स्थानांतरित कर दिया गया है।[16]इस GA विकास के पीछे एमेन्युल फलकेनौर के द्वारा प्रस्तावित विचार है कुछ जटिल समस्याओं का समाधान करना, a.k.a. समस्याओं का समूहन (clustering) या विभाजन (partitioning) जहां आइटमों के एक समुच्चय को एक अनुलित तरीके से आइटमों के समूह में विभाजित किया जाना चाहिए, इसे जीन के समतुल्य आइटमों के समूहों को लाक्षणिक बना कर बेहतर प्राप्त किया जा सकता है। इस प्रकार की समस्याओं में शामिल हैं बिन पैकिंग, रेखा संतुलन, समूहन w.r.t. एक दूरी मापन, बराबर पाइल्स, आदि जिस पर क्लासिक GA का प्रदर्शन बुरा साबित हुआ है। जीनों को समूहों के तुली बनाना उन गुणसूत्रों को अभिव्यक्त करता है जो विभेद लम्बाई और विशेष आनुवंशिक ओपरेटर में सामान्य हैं, जो आइटमों के पूरे समूह पर प्रभावी हैं। विशेष रूप से बिन पैकिंग के लिए, एक GGA को मार्तेलो और टोथ के प्रभुत्व मानदंड के साथ संकरित किया जाता है, यह तार्किक रूप से अब तक की सबसे अच्छी तकनीक है।



  • हार्मोनी सर्च (HS) एक एल्गोरिथम है जो सुधार प्रक्रिया में संगीतज्ञ के व्यवहार की नक़ल करती है।


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




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

मेमेटिक एल्गोरिथम का विचार मेमे (memes) से आया, जो जीन के विपरीत अपने आप को अनुकूलित कर सकते हैं। कुछ समस्या क्षेत्रों में ये पारंपरिक विकास एल्गोरिथम से अधिक कुशल दिखाई देते हैं।


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



  • सिमुलेटेड एनिलिंग (SA) सम्बंधित वैश्विक अनुकूलन तकनीक है जो व्यक्तिगत समाधान पर यादृच्छिक उत्परिवर्तनों के परीक्षणों के द्वारा सर्च को आगे बढाती है।

एक उत्परिवर्तन जो फिटनेस या स्वास्थ्य को बढाता है उसे हमेशा स्वीकार किया जाता है।

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





  • तब्बू खोज (TS) सिमुलेटेड एनिलिंग के समतुल्य है जिसमें दोनों एक व्यक्तिगत समाधान के उत्परिवर्तन के परिक्षण के द्वारा समाधान स्थान को बढ़ावा देते हैं। जहां एक ओर सिमुलेटेड एनिलिंग एक ही उत्वर्तित समाधान उत्पन्न करती है, तबू खोज कई उत्परिवर्तित समाधान खोजती है, ओर उस समाधान कि ओर जाती है जिसकी ऊर्जा न्यूनतम हो.साइकलिंग को रोकने के लिए ओर समाधान स्थान के माध्यम से अधिक गति को प्रोत्साहित करने के लिए आंशिक या पूर्ण समाधान की एक तबू सूची को बनाये रखा जाता है।

एक ऐसे समाधान की ओर जाने से रोका जाता है जिसमें तबू सूची के अवयव शामिल हों, जिसे अद्यतन किया गया हो क्योंकि समाधान, समाधान के स्थान को बढ़ावा देते हैं।


बिल्डिंग ब्लॉक परिकल्पना[संपादित करें]

आनुवंशिक एल्गोरिथम को लागू करना अपेक्षाकृत आसान है, लेकिन उनके व्यवहार को समझना मुश्किल है। विशेष रूप से यह समझना मुश्किल है कि वे अक्सर उच्च फिटनेस के समाधान को उत्पन्न करने में सफल क्यों रहते हैं। बिल्डिंग ब्लॉक परिकल्पना (BBH) में शामिल है:


  1. एक सार अनुकूली क्रियाप्रनाली का वर्णन जो "बिल्डिंग ब्लॉक्स" के पुनर्संयोजन के द्वारा अनुकूलन करती है, जैसे कम आदेश, कम परिभाषी-सम्बाई स्कीमेता उपरोक्त औसत फिटनेस के साथ.
  2. एक परिकल्पना कि एक आनुवंशिक एल्गोरिथ्म इस सार अनुकूलन क्रियाप्रनाली कि कुशलता से क्रियान्वित करके अनुकूलन करती है।


(गोल्डबर्ग 1989:41) सार अनुकूलन क्रियाप्रनाली को निम्नानुसार वर्णित करते हैं:



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



ठीक उसी तरह जैसे एक बच्चा लकडी (बिल्डिंग ब्लॉक) के साधारण ब्लॉक्स की व्यवस्था से शानदार ईमारत बनाता है, इसी तरह आनुवंशिक एल्गोरिथम बिल्डिंग ब्लॉक या छोटे, कम-आदेश के, उच्च प्रदर्शन के स्कीमेता की निकटता सी अनुकूली प्रदर्शक की तलाश करता है।


(गोल्डबर्ग 1989) का दावा है कि बिल्डिंग ब्लॉक परिकल्पना कि होलेन्ड की स्कीमा प्रमेय समर्थन देती है।


बिल्डिंग ब्लॉक परिकल्पना की इस आधार पर बहुत अधिक आलोचना की गयी है कि इसमें सैद्धांतिक ओर प्रायोगिक औचित्य परिणामों की कमी है, इसके परिणामों को प्रकाशित भी किया गया है जो इस पर प्रश्न उठाते हैं।

सैद्धांतिक पक्ष में, उदाहरण के लिए, राइट एट अल. कहते हैं कि

"GAs के बारे में भिन्न दावे जिन्हें पारंपरिक रूप से बिल्डिंग ब्लॉक परिकल्पना के नाम के तहत बनाया गया है, उनके पास कोई सैद्धांतिक आधार नहीं है, ओर कुछ मामलों में, वे बिलकुल बेमेल हैं। "[17]


प्रयोगात्मक पक्ष पक्ष पर समान क्रोस ओवर देखा गया जो कई फिटनेस फंक्शन पर एक-बिंदु ओर दो-बिंदु क्रोस वोवर को दर्शाता है, इसका अध्ययन सेस्वर्दा के द्वारा किया गया।[18]

इन परिणामों को संक्षेप में बताते हुए फोगल कहते हैं कि


"आम तौर पर समान क्रोस ओवर दो-बिंदु क्रोस ओवर की तुलना में बेहतर प्रदर्शन देता है, जो बदले में एक बिंदु उत्परिवर्तन की तुलना में बेहतर प्रदर्शन करता है।"[19]


सिस्वर्दा के परिणाम बिल्डिंग ब्लॉक परिकल्पना के खिलाफ हैं क्योंकि समान क्रोस ओवर कम स्कीमेता के साथ बहु विघटनकारी है, जबकि एक ओर दो बिंदु क्रोस ओवर संभवतया कम स्किमेता को अधिक संरक्षित करते हैं और पुनर्संयोजन में पैदा हुए बच्चों में परिभाषित बीत का संयोजन करते हैं।


बिल्डिंग ब्लॉक परिकल्पना पर बहस बताती है कि GAs कैसे "कार्य" करते हैं (यानि प्रदर्शन अनुकूलन) यह मुद्दा वर्तमान से बहुत दूर है।


इन्हें भी देखें[संपादित करें]


अनुप्रयोग[संपादित करें]


  • एक वित्तीय क्षेत्र में अत्याधुनिक व्यापार प्रणालियों के स्वचालित डिजाइन.


  • कंटेनर लोडिंग अनुकूलन
  • एक सही डिक्रिप्शन के लिए सिफर के बड़े समाधान स्पेस की सर्च के लिए GA का उपयोग करते हुए, कोड ब्रेकिंग.[21]






  • समयबद्धन आवेदन, जिसमें जॉब-दुकान समयबद्धन शामिल है।

अनुक्रम पर निर्भर या गैर-अनुक्रम पर निर्भर सेट-अप वातावरण में जॉब के समयबद्धन के लिए ऑब्जेक्टिव, ताकि उत्पादन की मात्रा को बढ़ाते हुए किसी प्रकार के दोष जैसे मंदी को कम किया जा सके.




नोट्स[संपादित करें]

  1. "एक-नटशेल-में विकास". मूल से 22 जून 2007 को पुरालेखित. अभिगमन तिथि 22 जून 2007.
  2. Barricelli, Nils Aall (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68.
  3. Barricelli, Nils Aall (1957). "Symbiogenetic evolution processes realized by artificial methods". Methodos: 143–182.
  4. Fraser, Alex (1957). "Simulation of genetic systems by automatic digital computers. I. Introduction". Aust. J. Biol. Sci. 10: 484–491.
  5. Fraser, Alex; Donald Burnell (1970). Computer Models in Genetics. New York: McGraw-Hill.
  6. Crosby, Jack L. (1973). Computer Simulation in Genetics. London: John Wiley & Sons.
  7. Fogel, David B. (editor) (1998). Evolutionary Computation: The Fossil Record. New York: IEEE Press.सीएस1 रखरखाव: फालतू पाठ: authors list (link)
  8. Barricelli, Nils Aall (1963). "Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life". Acta Biotheoretica (16): 99–126.
  9. Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog.
  10. Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (PhD thesis).
  11. Schwefel, Hans-Paul (1977). Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. Basel; Stuttgart: Birkhäuser. आई॰ऍस॰बी॰ऍन॰ 3764308761.
  12. Schwefel, Hans-Paul (1981). Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie. Chichester ; New York: Wiley. आई॰ऍस॰बी॰ऍन॰ 0471099880.
  13. Markoff, John (1989). "What's the Best Answer? It's Survival of the Fittest". New York Times. मूल से 2 दिसंबर 2010 को पुरालेखित. अभिगमन तिथि 9 अगस्त 2009.
  14. Baudry, Benoit; Franck Fleurey, Jean-Marc Jézéquel, and Yves Le Traon (मार्च/April 2005). "Automatic Test Case Optimization: A Bacteriologic Algorithm" (PDF). IEEE Software. IEEE Computer Society. 22: 76–82. डीओआइ:10.1109/MS.2005.30. मूल (PDF) से 16 दिसंबर 2008 को पुरालेखित. अभिगमन तिथि 9 अगस्त 2009. |date= में तिथि प्राचल का मान जाँचें (मदद)सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
  15. Kjellström, G. (1991). "On the Efficiency of Gaussian Adaptation". Journal of Optimization Theory and Applications. 71 (3): 589–597. डीओआइ:10.1007/BF00941405. नामालूम प्राचल |month= की उपेक्षा की गयी (मदद)
  16. Falkenauer, Emanuel (1997). Genetic Algorithms and Grouping Problems. Chichester, England: John Wiley & Sons Ltd. आई॰ऍस॰बी॰ऍन॰ 978-0-471-97150-4.
  17. Wright, A.H.; et al. (2003). "Implicit Parallelism". Proceedings of the Genetic and Evolutionary Computation Conference. 
  18. Syswerda, G. (1989). "Uniform crossover in genetic algorithms". In J. D. Schaffer. Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann. 
  19. Fogel, David B. (2000). Evolutionary Computation: Towards a New Philosophy of Machine Intelligence. New York: IEEE Press. पपृ॰ 140.
  20. Hill T, Lundgren A, Fredriksson R, Schiöth HB (2005). "Genetic algorithm for large-scale maximum parsimony phylogenetic analysis of proteins". Biochimica et Biophysica Acta. 1725: 19–29. PMID 15990235.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
  21. जोआचिम दे जुत्टर
  22. To CC, Vohradsky J (2007). "A parallel genetic algorithm for single class pattern classification and its application for gene expression profiling in Streptomyces coelicolor". BMC Genomics. 8: 49. PMID 17298664. डीओआइ:10.1186/1471-2164-8-49.
  23. Bagchi Tapan P (1999). "Multiobjective Scheduling by Genetic Algorithms". पाठ " Kluwer Academic. ISBN 0-7923-8561-6" की उपेक्षा की गयी (मदद); नामालूम प्राचल |book= की उपेक्षा की गयी (मदद); Cite journal requires |journal= (मदद)
  24. "नेटवर्क पैरामीटर्स और वास्तुकला को सीखने के लिए बारम्बार तंत्रिका नेटवर्क के लिए आनुवंशिक एल्गोरिथम को लागू करना". मूल से 6 दिसंबर 2010 को पुरालेखित. अभिगमन तिथि 6 अगस्त 2015.
  25. Wang S, Wang Y, Du W, Sun F, Wang X, Zhou C, Liang Y (2007). "A multi-approaches-guided genetic algorithm with application to operon prediction". Artificial Intelligence in Medicine. 41: 151–159. PMID 17869072. डीओआइ:10.1016/j.artmed.2007.07.010.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
  26. "BBC समाचार | मनोरंजन | बाइट की थाप". मूल से 16 अक्तूबर 2015 को पुरालेखित. अभिगमन तिथि 6 अगस्त 2015.
  27. Willett P (1995). "Genetic algorithms in molecular recognition and design". Trends in Biotechnology. 13: 516–521. PMID 8595137. डीओआइ:10.1016/S0167-7799(00)89015-0.
  28. van Batenburg FH, Gultyaev AP, Pleij CW (1995). "An APL-programmed genetic algorithm for the prediction of RNA secondary structure". Journal of Theoretical Biology. 174: 269–280. PMID 7545258. डीओआइ:10.1006/jtbi.1995.0098.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
  29. Notredame C, Higgins DG (1995). "SAGA a Genetic Algorithm for Multiple Sequence Alignment". Nulceic Acids Research. 174: 1515. PMID 8628686.
  30. "सिडरिक नोटरडम होम पेज". मूल से 6 अगस्त 2015 को पुरालेखित. अभिगमन तिथि 6 अगस्त 2015.
  31. Gondro C, Kinghorn BP (2007). "A simple genetic algorithm for multiple sequence alignment". Genetics and Molecular Research. 6: 964–982. PMID 18058716.
  32. हितोशी इबा, सुमिताका अकीबा, तेतसुया हिगुची, ताईसुके सातो: BUGS : आनुवंशिक एल्गोरिथम का उपयोग करते हुए एक बैग आधारित सर्च रणनीति. PPSN 1992:
  33. इब्राहिम, डब्ल्यू और आमेर, एच.: VLSI टेस्ट वेक्टर चयन के लिए एक अनुकूली आनुवंशिक एल्गोरिथम.
  34. "BiSNET / e - वितरित सॉफ्टवेयर सिस्टम समूह, मैसाचुसेट्स विश्वविद्यालय, बोस्टन". मूल से 22 जून 2009 को पुरालेखित. अभिगमन तिथि 6 अगस्त 2015.
  35. "सिम्बायोटिक स्फेयर - वितरित सॉफ्टवेयर सिस्टम समूह, मैसाचुसेट्स विश्वविद्यालय, बोस्टन". मूल से 29 मार्च 2009 को पुरालेखित. अभिगमन तिथि 6 अगस्त 2015.


सन्दर्भ[संपादित करें]

  • बन्ज़हाफ, वोल्फगेंग; नोरदिन, पीटर; केलर, रॉबर्ट; फ़्रन्कोन, फ्रेंक (1998) आनुवंशिक प्रोग्रामिंग-एक परिचय, मोर्गन कॉफमेन, सेन फ्रांसिस्को, CA.
  • Bies, Robert R; Muldoon, Matthew F; Pollock, Bruce G; Manuck, Steven; Smith, Gwenn and Sale, Mark E (2006). "A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection". Journal of Pharmacokinetics and Pharmacodynamics. Netherlands: Springer: 196–221.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
  • Cha, Sung-Hyuk; Tappert, Charles C (2009). "A Genetic Algorithm for Constructing Compact Binary Decision Trees". Journal of Pattern Recognition Research. 4 (1): 1–13. |title=, |journal= में बाहरी कड़ी (मदद)
  • Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction". Australian Journal of Biological Sciences. 10: 484–491.
  • गोल्डबर्ग, डेविड E (1989), खोज, अनुकूलन और मशीन लर्निंग में आनुवंशिक एल्गोरिथम, क्लुवर अकादमिक प्रकाशक, बोस्टन, MA
  • गोल्डबर्ग, डेविड E (2002), नवाचार के डिजाइन: सक्षम आनुवंशिक एल्गोरिथम से और के लिए अध्याय, एडिसन-वेस्ले, पठन, MA.
  • फोगल, डेविड B(2006), विकासवादी संगणना: टुवर्ड अ न्यू फिलोसोफी ऑफ़ मशीन इंटेलिजेंस, IEEE प्रेस, पिस्कतावे, NJ तीसरा संस्करण.
  • हॉलैंड, जॉन H(1975), प्राकृतिक और कृत्रिम प्रणाली में अनुकूलन, मिशिगन विश्वविद्यालय प्रेस, अन्न अर्बोर
  • कोजा, जॉन (1992), आनुवंशिक प्रोग्रामिंग: प्राकृतिक चयन के अनुसार कम्प्यूटर्स की प्रोग्रामिंग पर, MIT प्रेस आईएसबीएन 0-262-11170-5
  • मिकालेविक्ज़, ज्बिगनियु (1999), आनुवंशिक एल्गोरिथम और डेटा सरंचनाएं= विकास प्रोग्राम, स्प्रिन्जर-वर्लेग.


  • मिशेल, मेलानी, (1996), आनुवंशिक एल्गोरिथम का एक परिचय, MIT प्रेस, कैम्ब्रिज, MA
  • Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. आई॰ऍस॰बी॰ऍन॰ 978-1-4092-0073-4.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
  • रेचेनबर्ग, इंगो (1994): विकास रणनीति '94, स्तुगर्ट: फ्रोमान-होल्ज्बूग.


  • श्मिट, लोथर M; नेहानिव, क्रिस्टोफर एल; फुजी, रॉबर्ट H (1998), आनुवंशिक एल्गोरिथम का रैखिक विश्लेषण, सैद्धांतिक कंप्यूटर विज्ञान 208: 111-148
  • श्मिट, लोथर M (2001), आनुवंशिक एल्गोरिथम का सिद्धांत, सैद्धांतिक कंप्यूटर विज्ञान 259: 1-61


  • श्मिट, लोथर M (2004), आनुवंशिक एल्गोरिथम का सिद्धांत II: मॉडल फॉर जिनेटिक ऑपरेटर्स ओवर द स्ट्रिंग-टेन्सर रिप्रेजेंटेशन ऑफ़ पोपुलेशन एंड कोन्वर्जेन्स टू ग्लोबल ओप्टिमा फॉर आरबिटरेरी फिटनेस फंक्शन अंडर स्केलिंग, सैद्धांतिक कंप्यूटर विज्ञान 310: 181-231
  • श्वेफेल, हंस-पॉल (1974): नुमेरिस्चे ओप्तिमीएरुंग वॉन कंप्यूटर मोदेल्लेन (पीएचडी थीसिस). बिर्कहउजर द्वारा पुनः प्रकाशित. (1977)
  • वोसे, माइकल डी (1999), सरल जेनेटिक एल्गोरिथम: बुनियाद और सिद्धांत, MIT प्रेस, कैम्ब्रिज, MA.
  • व्हिट्ले, डी. (1994).एक आनुवंशिक एल्गोरिथ्म ट्यूटोरियल . सांख्यिकी और कम्प्यूटिंग, 4, 65-85.

इन्हें भी देखें[संपादित करें]

बाहरी कड़ियाँ[संपादित करें]


बिल्डिंग ब्लॉक परिकल्पना का एक विकल्प[संपादित करें]

  • उत्पादक निर्धारण A साधारण पुनर्संयोजक आनुवंशिक एल्गोरिथम की अनुकूली क्षमता के लिए एकीकृत विवरण.



अनुप्रयोग[संपादित करें]


  • आनुवंशिक एल्गोरिथम का उपयोग करते हुए एक यांत्रिक भुजा प्रशिक्षण का आनुवंशिक आर्म सिमुलेशन.

कस्टम लक्ष्यों को एक पटकथा भाषा का प्रयोग करते हुए परिभाषित किया जा सकता है। नमूने का एक वीडियो पेज पर उपलब्ध है।




संसाधन[संपादित करें]

  • DigitalBiology.NET GA/GP संसाधनों के लिए उर्ध्व सर्च इंजन.
  • आनुवंशिक एल्गोरिथम सूचकांक साईट आनुवंशिक प्रोग्रामिंग नोटबुक, आनुवंशिक एल्गोरिथम के क्षेत्र में वेब पेज के लिए एक सरंचना संसाधन सूचक प्रदान करती है।


ट्युटोरियल[संपादित करें]


]


पुस्तकालय (Libraries)[संपादित करें]

  • ECJ सबसे लोकप्रिय जावा विकासवादी अभिकलन पुस्तकालयों में एक.
  • EO एक बहुत ही लोकप्रिय C + + विकासवादी अभिकलन टूलकिट.
  • पेराडाईस EO, EO के लिए एक समानांतर और बहुल ऑब्जेक्टिव विस्तार.
  • ओपन बीगल एक और लोकप्रिय C++ विकासवादी अभिकलन टूलकिट.


  • एवोप्टूल एक फ्रेमवर्क और पुस्तकालयों का समुच्चय जिसे विकासवादी संगणना के लिए C++ में लिखा गया है, जिसमें कई आनुवंशिक एल्गोरिथम और EDA भी शामिल हैं।
  • जेनेज आनुवंशिक एल्गोरिथम के लिए एक अनुकूलित जावा पुस्तकालय.
  • पाइवोल्व आनुवंशिक एल्गोरिथम के लिए एक पाइथन रुपरेखा.
  • रूबी में आनुवंशिक एल्गोरिथम
  • GAlib आनुवंशिक एल्गोरिथम के घटकों का एक C++ पुस्तकालय.
  • MOGAlib GALib C++ पुस्तकालय का एक बहु उद्देश्यी विस्तार.
  • GAEDALib GAlib, में आधारित विकासवादी एल्गोरिथम (GAs, EDAs, DEs और अन्य) का एक C++ पुस्तकालय जो MOS और सामानांतर कम्प्यूटिंग को समर्थन देता है।
  • Jenetics आनुवंशिक एल्गोरिथम पुस्तकालय जिसे जावा में लिखा गया है।
  • ga MATLAB में आनुवंशिक एल्गोरिथम (GA कैसे MATLAB में काम करता है)
  • gamultiobj MATLAB में बहुल ऑब्जेक्टिव आनुवंशिक एल्गोरिथम.
  • GARAGe मिशिगन राज्य विश्वविद्यालय की आनुवंशिक एल्गोरिथम लायब्रेरी C में, GALLOPS
  • GAOT NCSU द्वारा, मेट्लेब के लिए आनुवंशिक एल्गोरिथम अनुकूलन टूल बॉक्स (GAOT).
  • JGAP जावा आनुवंशिक एल्गोरिथम पैकेज लक्षण व्यापक इकाई परीक्षण
  • speedyGA मेट्लेब में एक तेज हल्के वजन का आनुवंशिक एल्गोरिथम.