विकासात्मक कलनविधि

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

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

कार्यान्वयन

निम्नलिखित सामान्य एकल-उद्देश्य आनुवंशिक कलनविधि का उदाहरण है।

चरण एक: व्यक्तियों की प्रारंभिक जनसंख्या को यादृच्छिक रूप से उत्पन्न करें। (पहली पीढ़ी)

चरण दो: समाप्ति तक निम्नलिखित पुनर्जनन चरणों को दोहराएं:

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

प्रकार

इसी प्रकार की तकनीक आनुवंशिक प्रतिनिधित्व और अन्य कार्यान्वयन विवरण, और विशेष रूप से लागू समस्या की प्रकृति से भिन्न होती है।

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

सैद्धांतिक पृष्ठभूमि

निम्नलिखित सैद्धांतिक सिद्धांत सभी या लगभग सभी इए पर लागू होते हैं।

कोई मुफ्त लंच प्रमेय नहीं

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

अभिसरण

ईए के लिए, जिसमें वंश के अतिरिक्त, पेरेंट्स पीढ़ी के कम से कम सर्वश्रेष्ठ व्यक्ति का उपयोग पश्चात की पीढ़ी (तथाकथित अभिजात्य ईए) का निर्माण करने के लिए किया जाता है, इस शर्त के अनुसार अभिसरण का सामान्य प्रमाण है कि इष्टतम उपलब्ध है। सामान्यता नुकसान के बिना, अधिकतम खोज सबूत के लिए माना जाता है:

अभिजात्य संतानों की स्वीकृति और इष्टतम के अस्तित्व की संपत्ति से यह प्रति पीढ़ी का अनुसरण करता है $k$ फिटनेस में सुधार $F$ संबंधित सर्वश्रेष्ठ व्यक्ति की $x'$ संभावना के साथ होगा $P>0$, इस प्रकार:

$F(x'_{1})\leq F(x'_{2})\leq F(x'_{3})\leq \cdots \leq F(x'_{k})\leq \cdots$

अर्थात, फिटनेस मान मोनोटोनिक फ़ंक्शन गैर-घटते अनुक्रम का प्रतिनिधित्व करते हैं, जो कि इष्टतम के अस्तित्व के कारण सीमित है। इससे इष्टतम के विरुद्ध अनुक्रम का अभिसरण होता है।

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

वर्चुअल अक्षर

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

जैविक प्रक्रियाओं की तुलना

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

संबंधित तकनीकें

स्वार्म कलनविधि सम्मलित है:

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

अन्य जनसंख्या-आधारित मेटाह्यूरिस्टिक प्रकार

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

उदाहरण

2020 में, गूगल ने कहा कि उनका ऑटोएमएल-शून्य न्यूरल नेटवर्क की अवधारणा जैसे क्लासिक एल्गोरिदम को सफलतापूर्वक पुनः खोज सकता है।

कंप्यूटर सिम्युलेशन टिएरा (कंप्यूटर सिमुलेशन) और एविडा मैक्रोइवोल्यूशनरी डायनामिक्स को मॉडल करने का प्रयास करते हैं।

गैलरी

• 

  एक दो-जनसंख्या ईए बाध्य वैश्विक इष्टतम के साथ एक विवश रोसेनब्रॉक फ़ंक्शन पर खोज करता है

• 

  एक दो-आबादी ईए एक विवश रोसेनब्रॉक फ़ंक्शन पर खोज करता है। वैश्विक इष्टतम बाध्य नहीं है।

• 

  वितरण एल्गोरिदम का अनुमान कीन के कार्य पर

• 

  Simionescu's function के सीमित ऑप्टिमा की एक दो-आबादी ईए खोज

बाहरी संबंध

• An Overview of the History and Flavors of Evolutionary Algorithms

ग्रन्थसूची

• Ashlock, D. (2006), Evolutionary Computation for Modeling and Optimization, Springer, ISBN 0-387-22196-4.
• Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press.
• Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford Univ. Press. doi:10.1201/9780367802486
• Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction, Morgan Kaufmann, San Francisco.
• Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer. doi:10.1007/978-3-662-44874-8
• Holland, J. H. (1992), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor
• Michalewicz, Z.; Fogel, D.B. (2004), How To Solve It: Modern Heuristics. Springer, Berlin, Heidelberg, ISBN 978-3-642-06134-9, doi:10.1007/978-3-662-07807-5.
• Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms". 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA). pp. 298–302. doi:10.1109/BICTA.2010.5645312. ISBN 978-1-4244-6437-1. S2CID 16875144.
• Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4. Archived from the original on 2016-05-27. Retrieved 2011-03-05.
• Price, K., Storn, R.M., Lampinen, J.A., (2005). Differential Evolution: A Practical Approach to Global Optimization, Springer, Berlin, Heidelberg, ISBN 978-3-642-42416-8, doi:10.1007/3-540-31306-0.
• Ingo Rechenberg (1971), Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
• Hans-Paul Schwefel (1974), Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
• Hans-Paul Schwefel (1995), Evolution and Optimum Seeking. Wiley & Sons, New York. ISBN 0-471-57148-2
• Simon, D. (2013), Evolutionary Optimization Algorithms, Wiley.
• Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013), Computational Intelligence: A Methodological Introduction. Springer, London. ISBN 978-1-4471-5012-1, doi:10.1007/978-1-4471-5013-8.
• Rahman, Rosshairy Abd.; Kendall, Graham; Ramli, Razamin; Jamari, Zainoddin; Ku-Mahamud, Ku Ruhana (2017). "Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints". Complexity. 2017: 1–12. doi:10.1155/2017/7053710.