जेनेटिक एल्गोरिद्म: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (10 intermediate revisions by 4 users not shown) | |||
| Line 4: | Line 4: | ||
[[Image:St 5-xband-antenna.jpg|thumb|2006 नासा [[अंतरिक्ष प्रौद्योगिकी 5]] अंतरिक्ष यान एंटीना। यह जटिल आकार एक विकासवादी कंप्यूटर डिजाइन प्रोग्राम द्वारा सर्वोत्तम विकिरण पैटर्न बनाने के लिए पाया गया था। इसे एक [[विकसित एंटीना]] के रूप में जाना जाता है।]] | [[Image:St 5-xband-antenna.jpg|thumb|2006 नासा [[अंतरिक्ष प्रौद्योगिकी 5]] अंतरिक्ष यान एंटीना। यह जटिल आकार एक विकासवादी कंप्यूटर डिजाइन प्रोग्राम द्वारा सर्वोत्तम विकिरण पैटर्न बनाने के लिए पाया गया था। इसे एक [[विकसित एंटीना]] के रूप में जाना जाता है।]] | ||
[[कंप्यूटर विज्ञान]] और संचालन अनुसंधान में, एक आनुवंशिक एल्गोरिथम (जीए) [[प्राकृतिक चयन]] की प्रक्रिया से प्रेरित एक [[मेटाह्यूरिस्टिक]] है जो [[विकासवादी एल्गोरिदम]] (ईए) के बड़े वर्ग से संबंधित है। उत्परिवर्तन (जेनेटिक एल्गोरिथम), | [[कंप्यूटर विज्ञान]] और संचालन अनुसंधान में, एक आनुवंशिक एल्गोरिथम (जीए) [[प्राकृतिक चयन]] की प्रक्रिया से प्रेरित एक [[मेटाह्यूरिस्टिक]] है जो [[विकासवादी एल्गोरिदम]] (ईए) के बड़े वर्ग से संबंधित है। उत्परिवर्तन (जेनेटिक एल्गोरिथम), पारगमन (जेनेटिक एल्गोरिथम) और चयन (जेनेटिक एल्गोरिथम) जैसे जैविक रूप से प्रेरित प्रचालक पर विश्वाश करके [[अनुकूलन (गणित)]] और [[खोज एल्गोरिदम]] के उच्च-गुणवत्ता वाले समाधान उत्पन्न करने के लिए जेनेटिक एल्गोरिदम का सामान्यतः उपयोग किया जाता है।{{sfn|Mitchell|1996|p=2}} जीए अनुप्रयोगों के कुछ उदाहरणों में उत्तम प्रदर्शन के लिए, [[सुडोकू हल करने वाले एल्गोरिदम|सुडोकू पहेलियों]] को समाधान करने के लिये [[निर्णय वृक्ष सीखना|निर्णयावली]] का अनुकूलन,<ref>{{Cite journal|last1=Gerges|first1=Firas|last2=Zouein|first2=Germain|last3=Azar|first3=Danielle|date=2018-03-12|title=Genetic Algorithms with Local Optima Handling to Solve Sudoku Puzzles|url=https://doi.org/10.1145/3194452.3194463|journal=Proceedings of the 2018 International Conference on Computing and Artificial Intelligence|series=ICCAI 2018|location=New York, NY, USA|publisher=Association for Computing Machinery|pages=19–22|doi=10.1145/3194452.3194463|isbn=978-1-4503-6419-5|s2cid=44152535 }}</ref> [[हाइपरपैरामीटर अनुकूलन]], आदि सम्मिलित हैं। | ||
== कार्यप्रणाली == | == कार्यप्रणाली == | ||
=== अनुकूलन समस्याएं === | === अनुकूलन समस्याएं === | ||
एक आनुवंशिक एल्गोरिथम में, अनुकूलन समस्या के लिए [[उम्मीदवार समाधान]] (जिन्हें व्यक्ति, जीव, जीव, या [[फेनोटाइप]] कहा जाता है) की | एक आनुवंशिक एल्गोरिथम में, अनुकूलन समस्या के लिए [[उम्मीदवार समाधान]] (जिन्हें व्यक्ति, जीव, जीव, या [[फेनोटाइप|लक्षणप्ररूप]] कहा जाता है) की सरंध्रता उत्तम समाधान की ओर विकसित होती है। प्रत्येक उम्मीदवार समाधान में गुणों का एक सेट होता है (इसके गुणसूत्र या [[जीनोटाइप]]) जिन्हें उत्परिवर्तित और परिवर्तित किया जा सकता है; परंपरागत रूप से, समाधान 0s और 1s की स्ट्रिंग्स के रूप में बाइनरी में प्रस्तुत किए जाते हैं, किन्तु अन्य कोडलेखन भी संभव हैं।{{sfn|Whitley|1994|p=66}} | ||
विकास सामान्यतः | विकास सामान्यतः अव्यवस्थित रूप से उत्पन्न व्यक्तियों की सरंध्रता से प्रारंभ होता है, और प्रत्येक पुनरावृत्ति में जनसंख्या के साथ एक पुनरावृत्त प्रक्रिया होती है जिसे एक पीढ़ी कहा जाता है। प्रत्येक पीढ़ी में, जनसंख्या में प्रत्येक व्यक्ति की [[फिटनेस (जीव विज्ञान)|उपयुक्तता (जीव विज्ञान)]] का मूल्यांकन किया जाता है; उपयुक्तता सामान्यतः पर अनुकूलन समस्या में उद्देश्य फलन का मान का समाधान किया जा रहा है। अधिक फिट व्यक्तियों को वर्तमान सरंध्रता से [[स्टोकेस्टिक्स|यादृच्छिक]] रूप से चुना जाता है और प्रत्येक व्यक्ति के जीनोम को एक नई पीढ़ी बनाने के लिए संशोधित (पुन: संयोजित और संभवतः यादृच्छिक रूप से उत्परिवर्तित) किया जाता है। नई पीढ़ी के उम्मीदवार समाधानों का उपयोग [[कलन विधि]] के अगले पुनरावृत्ति में किया जाता है। सामान्यतः, एल्गोरिथ्म समाप्त हो जाता है जब या तो अधिकतम पीढ़ियों का उत्पादन किया जाता है, या जनसंख्या के लिए एक संतोषजनक उपयुक्तता स्तर तक पहुंच जाता है। | ||
एक विशिष्ट आनुवंशिक एल्गोरिथम की आवश्यकता होती है: | एक विशिष्ट आनुवंशिक एल्गोरिथम की आवश्यकता होती है: | ||
# समाधान डोमेन का एक [[आनुवंशिक प्रतिनिधित्व]], | # समाधान डोमेन का एक [[आनुवंशिक प्रतिनिधित्व]], | ||
# समाधान डोमेन का मूल्यांकन करने के लिए एक [[फिटनेस कार्य]] | # समाधान डोमेन का मूल्यांकन करने के लिए एक [[फिटनेस कार्य|उपयुक्तता कार्य]] | ||
प्रत्येक उम्मीदवार समाधान का एक मानक प्रतिनिधित्व एक [[बिट सरणी]] (जिसे बिट सेट या बिट स्ट्रिंग भी कहा जाता है) के रूप में होता है।{{sfn|Whitley|1994|p=66}} अन्य प्रकार की सरणियों और संरचनाओं का अनिवार्य रूप से उसी प्रकार उपयोग किया जा सकता है। मुख्य गुण जो इन आनुवंशिक अभ्यावेदन को सुविधाजनक बनाती है, वह यह है कि उनके हिस्से उनके निश्चित आकार के कारण आसानी से संरेखित होते हैं, जो सरल | प्रत्येक उम्मीदवार समाधान का एक मानक प्रतिनिधित्व एक [[बिट सरणी]] (जिसे बिट सेट या बिट स्ट्रिंग भी कहा जाता है) के रूप में होता है।{{sfn|Whitley|1994|p=66}} अन्य प्रकार की सरणियों और संरचनाओं का अनिवार्य रूप से उसी प्रकार उपयोग किया जा सकता है। मुख्य गुण जो इन आनुवंशिक अभ्यावेदन को सुविधाजनक बनाती है, वह यह है कि उनके हिस्से उनके निश्चित आकार के कारण आसानी से संरेखित होते हैं, जो सरल पारगमन (आनुवांशिक एल्गोरिथम) संचालन की सुविधा प्रदान करता है। परिवर्तनीय लंबाई के प्रतिनिधित्व का भी उपयोग किया जा सकता है, किन्तु इस स्थितियों में पारगमन कार्यान्वयन अधिक जटिल है। [[आनुवंशिक प्रोग्रामिंग]] में ट्री-लाइक प्रतिनिधित्व का पता लगाया जाता है और [[विकासवादी प्रोग्रामिंग]] में आरेख-प्रपत्र प्रतिनिधित्व का पता लगाया जाता है; [[जीन अभिव्यक्ति प्रोग्रामिंग]] में रैखिक गुणसूत्रों और पेड़ों दोनों के मिश्रण का पता लगाया जाता है। | ||
एक बार आनुवंशिक प्रतिनिधित्व और | एक बार आनुवंशिक प्रतिनिधित्व और उपयुक्तता फलन परिभाषित हो जाने के बाद, एक जीए समाधानों की सरंध्रता को प्रारंभ करने के लिए आगे बढ़ता है और फिर उत्परिवर्तन, पारगमन, उलटा और चयन प्रचालक के दोहराव वाले आवेदन के माध्यम से इसे सुधारता है। | ||
==== प्रारंभ ==== | ==== प्रारंभ ==== | ||
जनसंख्या का आकार समस्या की प्रकृति पर निर्भर करता है, किन्तु सामान्यतः कई सैकड़ों या हजारों संभावित समाधान होते हैं। प्राय: प्रारंभिक जनसंख्या | जनसंख्या का आकार समस्या की प्रकृति पर निर्भर करता है, किन्तु सामान्यतः कई सैकड़ों या हजारों संभावित समाधान होते हैं। प्राय: प्रारंभिक जनसंख्या अव्यवस्थित रूप से उत्पन्न होती है, जिससे संभावित समाधानों की पूरी श्रृंखला (संभव क्षेत्र) की अनुमति मिलती है। कभी-कभी, समाधान उन क्षेत्रों में लगाए जा सकते हैं जहां इष्टतम समाधान मिलने की संभावना है। | ||
==== चयन ==== | ==== चयन ==== | ||
{{Main|चयन (आनुवंशिक एल्गोरिथम)}} | {{Main|चयन (आनुवंशिक एल्गोरिथम)}} | ||
प्रत्येक क्रमिक पीढ़ी के समय, वर्तमान | प्रत्येक क्रमिक पीढ़ी के समय, वर्तमान सरंध्रता का एक हिस्सा एक नई पीढ़ी के प्रजनन के लिए चयन (आनुवांशिक एल्गोरिथम) होता है। एक उपयुक्तता-आधारित प्रक्रिया के माध्यम से व्यक्तिगत समाधानों का चयन किया जाता है, जहां उपयुक्तता (जीव विज्ञान) समाधान (जैसा कि एक उपयुक्तता फलन द्वारा मापा जाता है) सामान्यतः चुने जाने की अधिक संभावना होती है। कुछ चयन विधियां प्रत्येक समाधान की उपयुक्तता को रेट करती हैं और अधिमानतः सर्वोत्तम समाधानों का चयन करती हैं। अन्य विधियाँ जनसंख्या के केवल एक यादृच्छिक मानकों का मूल्यांकन करती हैं, क्योंकि पूर्व प्रक्रिया बहुत समय लेने वाली हो सकती है। | ||
उपयुक्तता फलन को आनुवंशिक प्रतिनिधित्व पर परिभाषित किया गया है और प्रतिनिधित्व किए गए समाधान की गुणवत्ता को मापता है। उपयुक्तता फलन हमेशा समस्या पर निर्भर होता है। उदाहरण के लिए, थैला समस्या में व्यक्ति उन वस्तुओं के कुल मान को अधिकतम करना चाहता है जिन्हें किसी निश्चित क्षमता के थैले में रखा जा सकता है। एक समाधान का प्रतिनिधित्व बिट्स की एक सरणी हो सकता है, जहां प्रत्येक बिट एक अलग वस्तु का प्रतिनिधित्व करता है, और बिट का मान (0 या 1) दर्शाता है कि वस्तु नैपसैक में है या नहीं। ऐसा हर प्रतिनिधित्व मान्य नहीं है, क्योंकि वस्तुओं का आकार थैला की क्षमता से अधिक हो सकता है। यदि निरूपण वैध है, या अन्यथा 0 है, तो समाधान की उपयुक्तता थैला में सभी वस्तुओं के मानों का योग है। | |||
कुछ समस्याओं में, | कुछ समस्याओं में, उपयुक्तता अभिव्यक्ति को परिभाषित करना कठिन या असंभव भी है; इन स्थितियों में, एक लक्षणप्ररूप के उपयुक्तता फलन मान को निर्धारित करने के लिए एक [[कंप्यूटर सिमुलेशन|कंप्यूटर अनुकरण]] का उपयोग किया जा सकता है (उदाहरण के लिए कम्प्यूटेशनल द्रव गतिकी का उपयोग वाहन के वायु प्रतिरोध को निर्धारित करने के लिए किया जाता है जिसका आकार लक्षणप्ररूप के रूप में एन्कोड किया गया है), या यहां तक कि [[इंटरएक्टिव विकासवादी संगणना|पारस्परिक विकासवादी संगणना]] का उपयोग किया जाता है . | ||
==== जेनेटिक ऑपरेटर ==== | ==== जेनेटिक ऑपरेटर ==== | ||
{{Main|क्रॉसओवर (आनुवंशिक एल्गोरिथम)|उत्परिवर्तन (आनुवंशिक एल्गोरिथम)}} | {{Main|क्रॉसओवर (आनुवंशिक एल्गोरिथम)|उत्परिवर्तन (आनुवंशिक एल्गोरिथम)}} | ||
अगला चरण [[आनुवंशिक ऑपरेटर]] | अगला चरण [[आनुवंशिक ऑपरेटर]] पारगमन (जिसे पुनर्संयोजन भी कहा जाता है) और उत्परिवर्तन के संयोजन के माध्यम से चुने गए लोगों से समाधान की दूसरी पीढ़ी की सरंध्रता उत्पन्न करना है। | ||
उत्पादित किए जाने वाले प्रत्येक नए समाधान के लिए, पहले से चयनित पूल से प्रजनन के लिए मूल समाधानों की एक जोड़ी का चयन किया जाता है। | उत्पादित किए जाने वाले प्रत्येक नए समाधान के लिए, पहले से चयनित पूल से प्रजनन के लिए मूल समाधानों की एक जोड़ी का चयन किया जाता है। पारगमन और उत्परिवर्तन के उपरोक्त विधियों का उपयोग करके एक चाइल्ड समाधान तैयार करके, एक नया समाधान तैयार किया जाता है जो सामान्यतः अपने माता-पिता की कई विशेषताओं को साझा करता है। प्रत्येक नए बच्चे के लिए नए माता-पिता का चयन किया जाता है, और यह प्रक्रिया तब तक जारी रहती है जब तक कि उपयुक्त आकार के समाधानों की एक नई सरंध्रता उत्पन्न नहीं हो जाती है। | ||
यद्यपि प्रजनन के विधियों जो दो माता-पिता के उपयोग पर आधारित हैं, अधिक जीव विज्ञान से प्रेरित हैं, कुछ शोध<ref>Eiben, A. E. et al (1994). "Genetic algorithms with multi-parent recombination". PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78–87. {{ISBN|3-540-58484-6}}.</ref><ref>Ting, Chuan-Kang (2005). "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403–412. {{ISBN|978-3-540-28848-0}}.</ref> सुझाव देता है कि दो से अधिक माता-पिता उच्च गुणवत्ता वाले गुणसूत्र उत्पन्न करते हैं। | यद्यपि प्रजनन के विधियों जो दो माता-पिता के उपयोग पर आधारित हैं, अधिक जीव विज्ञान से प्रेरित हैं, कुछ शोध<ref>Eiben, A. E. et al (1994). "Genetic algorithms with multi-parent recombination". PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78–87. {{ISBN|3-540-58484-6}}.</ref><ref>Ting, Chuan-Kang (2005). "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403–412. {{ISBN|978-3-540-28848-0}}.</ref> सुझाव देता है कि दो से अधिक माता-पिता उच्च गुणवत्ता वाले गुणसूत्र उत्पन्न करते हैं। | ||
इन प्रक्रियाओं के परिणामस्वरूप अंततः अगली पीढ़ी के गुणसूत्रों की | इन प्रक्रियाओं के परिणामस्वरूप अंततः अगली पीढ़ी के गुणसूत्रों की सरंध्रता होती है जो प्रारंभिक पीढ़ी से अलग होती है। सामान्यतः, सरंध्रता के लिए इस प्रक्रिया से औसत उपयुक्तता में वृद्धि होगी, क्योंकि पहली पीढ़ी के केवल सबसे अच्छे जीवों को कम फिट समाधानों के एक छोटे अनुपात के साथ प्रजनन के लिए चुना जाता है। ये कम फिट समाधान माता-पिता के आनुवंशिक पूल के अन्दर आनुवंशिक विविधता सुनिश्चित करते हैं और इसलिए बाद की पीढ़ी के बच्चों की आनुवंशिक विविधता सुनिश्चित करते हैं। | ||
पारगमन बनाम उत्परिवर्तन के महत्व पर राय बंटी हुई है। डेविड बी फोगेल (2006) में कई संदर्भ हैं जो उत्परिवर्तन-आधारित खोज के महत्व का समर्थन करते हैं। | |||
चूंकि | चूंकि पारगमन और उत्परिवर्तन को मुख्य जेनेटिक ऑपरेटर के रूप में जाना जाता है, फिर भी जेनेटिक एल्गोरिदम में रीग्रुपिंग, कॉलोनाइजेशन-विलुप्त होने या माइग्रेशन जैसे अन्य प्रचालक का उपयोग करना संभव है।{{citation needed|date=November 2019}} | ||
समस्या वर्ग के लिए उचित सेटिंग्स खोजने के लिए | समस्या वर्ग के लिए उचित सेटिंग्स खोजने के लिए उत्परिवर्तन (आनुवांशिक एल्गोरिदम) संभावना, पारगमन (जेनेटिक एल्गोरिदम) संभावना और जनसंख्या आकार जैसे ट्यूनिंग पैरामीटर के लायक है। बहुत कम उत्परिवर्तन दर से [[आनुवंशिक बहाव]] हो सकता है (जो प्रकृति में गैर-[[एर्गोडिसिटी]] है)। एक पुनर्संयोजन दर जो बहुत अधिक है, आनुवंशिक एल्गोरिथम के समय से पहले अभिसरण का कारण बन सकती है। एक उत्परिवर्तन दर जो बहुत अधिक है, अच्छे समाधानों के हानि का कारण बन सकती है, जब तक कि उत्कृष्टता कार्यरत न हो। एक पर्याप्त जनसंख्या आकार हाथ में समस्या के लिए पर्याप्त आनुवंशिक विविधता सुनिश्चित करता है, किन्तु आवश्यकता से अधिक मूल्य पर सेट होने पर कम्प्यूटेशनल संसाधनों की पतन हो सकती है। | ||
==== आंकलन ==== | ==== आंकलन ==== | ||
ऊपर दिए गए मुख्य | ऊपर दिए गए मुख्य प्रचालक के अतिरिक्त, गणना को तेज या अधिक शक्तिशाली बनाने के लिए अन्य [[अनुमानी|अनुमानों]] को नियोजित किया जा सकता है। परिकल्पना अनुमानवादी उम्मीदवार समाधानों के बीच पारगमन को दंडित करता है जो बहुत समान हैं; यह जनसंख्या विविधता को प्रोत्साहित करता है और कम इष्टतम समाधान के लिए समय से पहले [[अभिसरण (विकासवादी कंप्यूटिंग)]] को रोकने में सहायता करता है।<ref>{{Cite book|title=Handbook of Evolutionary Computation|last1=Deb|first1=Kalyanmoy|last2=Spears|first2=William M.|s2cid=3547258|publisher=Institute of Physics Publishing|year=1997|chapter=C6.2: Speciation methods}}</ref><ref>{{Cite book|title=Handbook of Natural Computing|last=Shir|first=Ofer M.|date=2012|publisher=Springer Berlin Heidelberg|isbn=9783540929093|editor-last=Rozenberg|editor-first=Grzegorz|pages=1035–1069|language=en|chapter=Niching in Evolutionary Algorithms|doi=10.1007/978-3-540-92910-9_32|editor-last2=Bäck|editor-first2=Thomas|editor-last3=Kok|editor-first3=Joost N.}}</ref> | ||
| Line 57: | Line 57: | ||
समाप्ति की स्थिति तक पहुंचने तक यह पीढ़ीगत प्रक्रिया दोहराई जाती है। सामान्य समाप्ति की स्थिति हैं: | समाप्ति की स्थिति तक पहुंचने तक यह पीढ़ीगत प्रक्रिया दोहराई जाती है। सामान्य समाप्ति की स्थिति हैं: | ||
* एक समाधान पाया जाता है जो न्यूनतम मानदंडों को पूरा करता | * एक समाधान पाया जाता है जो न्यूनतम मानदंडों को पूरा करता है। | ||
* पीढ़ियों की निश्चित संख्या पहुँची | * पीढ़ियों की निश्चित संख्या पहुँची है। | ||
* आवंटित बजट (गणना समय/पैसा) पहुंच गया | * आवंटित बजट (गणना समय/पैसा) पहुंच गया है। | ||
* उच्चतम रैंकिंग समाधान की | * उच्चतम रैंकिंग समाधान की उपयुक्तता पहुँच रही है या एक पठार पर पहुँच गई है जैसे कि क्रमिक पुनरावृत्तियाँ अब उत्तम परिणाम नहीं देती है। | ||
* | * स्वतः निरीक्षण | ||
* उपरोक्त का संयोजन | * उपरोक्त का संयोजन | ||
== | == रचक खंड परिकल्पना == | ||
जेनेटिक एल्गोरिदम को प्रायुक्त करना आसान है, किन्तु उनके व्यवहार को समझना कठिन है। विशेष रूप से, यह समझना कठिन है कि व्यावहारिक समस्याओं पर प्रायुक्त होने पर ये एल्गोरिदम अधिकांश उच्च | जेनेटिक एल्गोरिदम को प्रायुक्त करना आसान है, किन्तु उनके व्यवहार को समझना कठिन है। विशेष रूप से, यह समझना कठिन है कि व्यावहारिक समस्याओं पर प्रायुक्त होने पर ये एल्गोरिदम अधिकांश उच्च उपयुक्तता के समाधान उत्पन्न करने में क्यों सफल होते हैं। रचक खंड परिकल्पना (बीबीएच) में सम्मिलित हैं: | ||
# एक अनुमानी का विवरण जो | # एक अनुमानी का विवरण जो रचक खण्डों की पहचान और पुनर्संयोजन करके अनुकूलन करता है, अर्थात् कम क्रम, कम परिभाषित-लंबाई वाली स्कीमा (आनुवांशिक एल्गोरिदम) ऊपर औसत उपयुक्तता के साथ। | ||
# एक परिकल्पना कि एक आनुवंशिक एल्गोरिथम इस अनुमानी को स्पष्ट रूप से और कुशलता से प्रायुक्त करके अनुकूलन करता है। | # एक परिकल्पना कि एक आनुवंशिक एल्गोरिथम इस अनुमानी को स्पष्ट रूप से और कुशलता से प्रायुक्त करके अनुकूलन करता है। | ||
गोल्डबर्ग अनुमानी का वर्णन इस प्रकार करते हैं: | गोल्डबर्ग अनुमानी का वर्णन इस प्रकार करते हैं: | ||
: | : कम, लो ऑर्डर, और अत्यधिक फिट स्कीमाटा का मानक लिया जाता है, पारगमन (जेनेटिक एल्गोरिथम) [क्रॉस ओवर], और संभावित उच्च उपयुक्तता के तार बनाने के लिए फिर से तैयार किया जाता है। एक प्रकार से, इन विशेष स्कीमाटा [रचक खण्डों] के साथ काम करके, हमने अपनी समस्या की जटिलता को कम किया है; प्रत्येक बोधगम्य संयोजन की कोशिश करके उच्च-प्रदर्शन स्ट्रिंग्स बनाने के अतिरिक्त, हम पिछले मानकों के सर्वोत्तम आंशिक समाधानों से उत्तम और उत्तम स्ट्रिंग्स का निर्माण करते हैं। | ||
: क्योंकि कम परिभाषित लंबाई और निम्न क्रम के अत्यधिक फिट स्कीमाटा आनुवंशिक एल्गोरिदम की कार्रवाई में इतनी महत्वपूर्ण भूमिका निभाते हैं, हमने उन्हें पहले से ही एक विशेष नाम दिया है: | : क्योंकि कम परिभाषित लंबाई और निम्न क्रम के अत्यधिक फिट स्कीमाटा आनुवंशिक एल्गोरिदम की कार्रवाई में इतनी महत्वपूर्ण भूमिका निभाते हैं, हमने उन्हें पहले से ही एक विशेष नाम दिया है: रचक खण्डों। जिस प्रकार एक बच्चा लकड़ी के साधारण ब्लॉकों की व्यवस्था के माध्यम से शानदार किले बनाता है, उसी प्रकार एक आनुवंशिक एल्गोरिथ्म शॉर्ट, लो-ऑर्डर, हाई-परप्रपत्रेंस स्कीमाटा, या रचक खण्डों के संयोजन के माध्यम से इष्टतम प्रदर्शन की तलाश करता है।{{sfn|Goldberg|1989|p=41}} | ||
बिल्डिंग-ब्लॉक परिकल्पना की वैधता के संबंध में सामान्य सहमति की कमी के अतिरिक्त, इसका लगातार मूल्यांकन किया गया है और पूरे वर्षों में संदर्भ के रूप में इसका उपयोग किया गया है। वितरण एल्गोरिदम के कई अनुमान, उदाहरण के लिए, एक वातावरण प्रदान करने के प्रयास में प्रस्तावित किए गए हैं जिसमें परिकल्पना मान्य होगी।<ref>{{cite book|last1=Harik|first1=Georges R.|last2=Lobo|first2=Fernando G.|last3=Sastry|first3=Kumara|title=Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA)|journal=Scalable Optimization Via Probabilistic Modeling|volume=33|date=1 January 2006|pages=39–61|doi=10.1007/978-3-540-34954-9_3|language=en|series=Studies in Computational Intelligence|isbn=978-3-540-34953-2}}</ref><ref>{{cite book|last1=Pelikan|first1=Martin|last2=Goldberg|first2=David E.|last3=Cantú-Paz|first3=Erick|title=BOA: The Bayesian Optimization Algorithm|journal=Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1|date=1 January 1999|pages=525–532|url=http://dl.acm.org/citation.cfm?id=2933973|isbn=9781558606111|series=Gecco'99}}</ref> चूंकि समस्याओं के कुछ वर्गों के लिए अच्छे परिणाम बताए गए हैं, जीए दक्षता के स्पष्टीकरण के रूप में बिल्डिंग-ब्लॉक परिकल्पना की विस्तृतता और/या व्यावहारिकता के संबंध में संदेह अभी भी बना हुआ है। | बिल्डिंग-ब्लॉक परिकल्पना की वैधता के संबंध में सामान्य सहमति की कमी के अतिरिक्त, इसका लगातार मूल्यांकन किया गया है और पूरे वर्षों में संदर्भ के रूप में इसका उपयोग किया गया है। वितरण एल्गोरिदम के कई अनुमान, उदाहरण के लिए, एक वातावरण प्रदान करने के प्रयास में प्रस्तावित किए गए हैं जिसमें परिकल्पना मान्य होगी।<ref>{{cite book|last1=Harik|first1=Georges R.|last2=Lobo|first2=Fernando G.|last3=Sastry|first3=Kumara|title=Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA)|journal=Scalable Optimization Via Probabilistic Modeling|volume=33|date=1 January 2006|pages=39–61|doi=10.1007/978-3-540-34954-9_3|language=en|series=Studies in Computational Intelligence|isbn=978-3-540-34953-2}}</ref><ref>{{cite book|last1=Pelikan|first1=Martin|last2=Goldberg|first2=David E.|last3=Cantú-Paz|first3=Erick|title=BOA: The Bayesian Optimization Algorithm|journal=Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1|date=1 January 1999|pages=525–532|url=http://dl.acm.org/citation.cfm?id=2933973|isbn=9781558606111|series=Gecco'99}}</ref> चूंकि समस्याओं के कुछ वर्गों के लिए अच्छे परिणाम बताए गए हैं, जीए दक्षता के स्पष्टीकरण के रूप में बिल्डिंग-ब्लॉक परिकल्पना की विस्तृतता और/या व्यावहारिकता के संबंध में संदेह अभी भी बना हुआ है। वास्तविक में, वितरण एल्गोरिदम के अनुमान के परिप्रेक्ष्य से इसकी सीमाओं को समझने का प्रयास करने के लिए एक उचित मात्रा में काम है।<ref>{{cite book|last1=Coffin|first1=David|last2=Smith|first2=Robert E.|title=Linkage Learning in Estimation of Distribution Algorithms|journal=Linkage in Evolutionary Computation|volume=157|date=1 January 2008|pages=141–156|doi=10.1007/978-3-540-85068-7_7|language=en|series=Studies in Computational Intelligence|isbn=978-3-540-85067-0}}</ref><ref>{{cite journal|last1=Echegoyen|first1=Carlos|last2=Mendiburu|first2=Alexander|last3=Santana|first3=Roberto|last4=Lozano|first4=Jose A.|title=On the Taxonomy of Optimization Problems Under Estimation of Distribution Algorithms|journal=Evolutionary Computation|date=8 November 2012|volume=21|issue=3|pages=471–495|doi=10.1162/EVCO_a_00095|pmid=23136917|s2cid=26585053|issn=1063-6560}}</ref><ref>{{cite book|last1=Sadowski|first1=Krzysztof L.|last2=Bosman|first2=Peter A.N.|last3=Thierens|first3=Dirk|title=On the Usefulness of Linkage Processing for Solving MAX-SAT|journal=Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation|date=1 January 2013|pages=853–860|doi=10.1145/2463372.2463474|isbn=9781450319638|series=Gecco '13|hdl=1874/290291|s2cid=9986768}}</ref> | ||
| Line 81: | Line 81: | ||
वैकल्पिक अनुकूलन एल्गोरिदम की तुलना में आनुवंशिक एल्गोरिथम के उपयोग की सीमाएँ हैं: | वैकल्पिक अनुकूलन एल्गोरिदम की तुलना में आनुवंशिक एल्गोरिथम के उपयोग की सीमाएँ हैं: | ||
* जटिल समस्याओं के लिए बार-बार | * जटिल समस्याओं के लिए बार-बार उपयुक्तता फलन का मूल्यांकन अधिकांश कृत्रिम विकासवादी एल्गोरिदम का सबसे निषेधात्मक और सीमित खंड होता है। जटिल उच्च-आयामी, बहुआयामी समस्याओं का इष्टतम समाधान खोजने के लिए अधिकांश बहुत महंगे उपयुक्तता फलन मूल्यांकन की आवश्यकता होती है। वास्तविक संसार की समस्याओं जैसे संरचनात्मक अनुकूलन समस्याओं में, एक एकल कार्य मूल्यांकन के लिए कई घंटों से लेकर कई दिनों तक पूर्ण अनुकरण की आवश्यकता हो सकती है। विशिष्ट अनुकूलन विधियाँ इस प्रकार की समस्या से नहीं निपट सकती हैं। इस स्थितियों में, एक त्रुटिहीन मूल्यांकन छोड़ना और एक उपयुक्तता सन्निकटन का उपयोग करना आवश्यक हो सकता है जो कम्प्यूटेशनल रूप से कुशल है। यह स्पष्ट है कि जटिल वास्तविक जीवन की समस्याओं को समाधान करने के लिए जीए का उपयोग करने के लिए उपयुक्तता सन्निकटन का समामेलन सबसे आशाजनक दृष्टिकोणों में से एक हो सकता है। | ||
* जेनेटिक एल्गोरिदम जटिलता के साथ अच्छी तरह से स्केल नहीं करते हैं। यही है, जहां उत्परिवर्तन के संपर्क में आने वाले तत्वों की संख्या बड़ी है, वहां अधिकांश खोज स्थान के आकार में घातीय वृद्धि होती है। इससे इंजन, घर या विमान को डिजाइन करने जैसी समस्याओं पर तकनीक का उपयोग करना अधिक कठिन हो जाता | * जेनेटिक एल्गोरिदम जटिलता के साथ अच्छी तरह से स्केल नहीं करते हैं। यही है, जहां उत्परिवर्तन के संपर्क में आने वाले तत्वों की संख्या बड़ी है, वहां अधिकांश खोज स्थान के आकार में घातीय वृद्धि होती है। इससे इंजन, घर या विमान को डिजाइन करने जैसी समस्याओं पर तकनीक का उपयोग करना अधिक कठिन हो जाता है।{{Citation needed|date=December 2020}} विकासवादी खोज के लिए ऐसी समस्याओं को सुगम बनाने के लिए, उन्हें यथासंभव सरलतम प्रतिनिधित्व में विभाजित किया जाना चाहिए। इसलिए हम सामान्यतः विकासवादी एल्गोरिदम को इंजनों के अतिरिक्त पंखे के ब्लेड के लिए एन्कोडिंग डिज़ाइन देखते हैं, विस्तृत निर्माण योजनाओं और पूरे विमान डिज़ाइनों के अतिरिक्त एयरफ़ोइल के अतिरिक्त आकृतियों का निर्माण करते हैं। जटिलता की दूसरी समस्या यह है कि आगे विनाशकारी उत्परिवर्तन से अच्छे समाधान का प्रतिनिधित्व करने के लिए विकसित किए गए भागों की रक्षा कैसे की जाए, विशेषतः जब उनके उपयुक्तता मूल्यांकन के लिए उन्हें अन्य भागों के साथ अच्छी तरह से संयोजित करने की आवश्यकता होती है। | ||
* अन्य समाधानों की तुलना में ही उत्तम समाधान है। परिणामस्वरूप, रोक मानदंड हर समस्या में स्पष्ट नहीं है। | * अन्य समाधानों की तुलना में ही उत्तम समाधान है। परिणामस्वरूप, रोक मानदंड हर समस्या में स्पष्ट नहीं है। | ||
* कई समस्याओं में, | * कई समस्याओं में, जीए में समस्या के [[वैश्विक इष्टतम]] के अतिरिक्त [[स्थानीय इष्टतम]] या यहाँ तक कि स्वैच्छिक बिंदुओं की ओर अभिसरण करने की प्रवृत्ति होती है। इसका अर्थ यह है कि यह लंबी अवधि की उपयुक्तता प्राप्त करने के लिए अल्पकालिक उपयुक्तता का त्याग करना नहीं जानता है। ऐसा होने की संभावना [[फिटनेस परिदृश्य|उपयुक्तता परिदृश्य]] के आकार पर निर्भर करती है: कुछ समस्याएं वैश्विक इष्टतम की ओर एक आसान चढ़ाई प्रदान कर सकती हैं, अन्य कार्य के लिए स्थानीय ऑप्टिमा को ढूंढना आसान बना सकती हैं। इस समस्या को एक अलग उपयुक्तता फलन का उपयोग करके, उत्परिवर्तन की दर में वृद्धि करके, या चयन तकनीकों का उपयोग करके समाधान किया जा सकता है जो समाधान की विविध सरंध्रता को बनाए रखता है,<ref>{{cite journal|last1=Taherdangkoo|first1=Mohammad|last2=Paziresh |first2=Mahsa |last3=Yazdi |first3=Mehran |last4= Bagheri |first4=Mohammad Hadi |title=An efficient algorithm for function optimization: modified stem cells algorithm|journal=Central European Journal of Engineering|date=19 November 2012|volume=3|issue=1|pages=36–50|doi=10.2478/s13531-012-0047-8|doi-access=free}}</ref> चूंकि [[खोज और अनुकूलन में कोई मुफ्त लंच नहीं]]<ref>Wolpert, D.H., Macready, W.G., 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.</ref> सिद्ध करता है कि इस समस्या का कोई सामान्य समाधान नहीं है। विविधता को बनाए रखने के लिए एक सामान्य तकनीक एक आला दंड लगाना है, जिसमें, पर्याप्त समानता वाले व्यक्तियों के किसी भी समूह (आला त्रिज्या) में एक दंड जोड़ा जाता है, जो बाद की पीढ़ियों में उस समूह के प्रतिनिधित्व को कम कर देगा, अन्य (कम समान) व्यक्तियों को अनुमति देगा जनसंख्या में बनाए रखना है। चूँकि, समस्या के परिदृश्य के आधार पर, यह तरकीब प्रभावी नहीं हो सकती है। एक अन्य संभावित तकनीक जनसंख्या के हिस्से को अव्यवस्थित रूप से उत्पन्न व्यक्तियों के साथ बदलना होगा, जब अधिकांश सरंध्रता एक-दूसरे के समान होती है। आनुवंशिक एल्गोरिदम (और आनुवंशिक प्रोग्रामिंग) में विविधता महत्वपूर्ण है क्योंकि एक सजातीय सरंध्रता को पार करने से नए समाधान नहीं मिलते हैं। उत्क्रांति रणनीति और विकासवादी प्रोग्रामिंग में, उत्परिवर्तन पर अधिक निर्भरता के कारण विविधता आवश्यक नहीं है। | ||
* डायनेमिक | * डायनेमिक समुच्चय सेट पर काम करना कठिन है, क्योंकि जीनोम जल्दी समाधान की ओर अभिसरण करना प्रारंभ कर देते हैं जो बाद के समुच्चय के लिए मान्य नहीं हो सकता है। आनुवंशिक विविधता को किसी प्रकार बढ़ाकर और प्रारंभिक अभिसरण को रोककर, समाधान की गुणवत्ता में गिरावट आने पर उत्परिवर्तन की संभावना को बढ़ाकर (ट्रिगर हाइपरउत्परिवर्तन कहा जाता है), या कभी-कभी जीन पूल में पूरी तरह से नए, अव्यवस्थित रूप से उत्पन्न तत्वों को प्रस्तुत करके इसे दूर करने के लिए कई विधियों प्रस्तावित किए गए हैं। (यादृच्छिक आप्रवासी कहा जाता है)। फिर से, विकास रणनीति और विकासवादी प्रोग्रामिंग को एक तथाकथित अल्पविराम रणनीति के साथ प्रायुक्त किया जा सकता है जिसमें माता-पिता का रखरखाव नहीं किया जाता है और नए माता-पिता केवल संतानों में से चुने जाते हैं। यह गतिशील समस्याओं पर अधिक प्रभावी हो सकता है। | ||
* जीए उन समस्याओं को प्रभावी | * जीए उन समस्याओं को प्रभावी रूप से समाधान नहीं कर सकते हैं जिनमें एकमात्र उपयुक्तता उपाय एक सही/गलत उपाय है (जैसे [[निर्णय समस्या]]एं), क्योंकि समाधान पर अभिसरण करने का कोई विधि नहीं है (चढ़ने के लिए कोई पहाड़ी नहीं)। इन स्थितियों में, यादृच्छिक खोज से जीए जितनी जल्दी समाधान मिल सकता है। चूँकि, यदि स्थिति सफलता/असफलता परीक्षण को अलग-अलग परिणाम देने (संभवतः) देने की अनुमति देती है, तो सफलताओं से असफलताओं का अनुपात एक उपयुक्त उपयुक्तता उपाय प्रदान करता है। | ||
* विशिष्ट अनुकूलन समस्याओं और समस्या उदाहरणों के लिए, अभिसरण की गति के संदर्भ में अन्य अनुकूलन एल्गोरिदम आनुवंशिक एल्गोरिदम की तुलना में अधिक कुशल हो सकते हैं। वैकल्पिक और पूरक एल्गोरिदम में विकास रणनीति, विकासवादी प्रोग्रामिंग, [[तैयार किए हुयी धातु पे पानी चढाने की कला]], [[गॉसियन अनुकूलन]], पहाड़ी चढ़ाई, और [[झुंड खुफिया]] (जैसे: [[चींटी कॉलोनी अनुकूलन]], [[कण झुंड अनुकूलन]]) और [[पूर्णांक रैखिक प्रोग्रामिंग]] पर आधारित विधियों सम्मिलित हैं। आनुवंशिक एल्गोरिदम की उपयुक्तता समस्या के ज्ञान की मात्रा पर निर्भर करती है; प्रसिद्ध समस्याओं में अधिकांश उत्तम, अधिक विशिष्ट दृष्टिकोण होते हैं। | * विशिष्ट अनुकूलन समस्याओं और समस्या उदाहरणों के लिए, अभिसरण की गति के संदर्भ में अन्य अनुकूलन एल्गोरिदम आनुवंशिक एल्गोरिदम की तुलना में अधिक कुशल हो सकते हैं। वैकल्पिक और पूरक एल्गोरिदम में विकास रणनीति, विकासवादी प्रोग्रामिंग, [[तैयार किए हुयी धातु पे पानी चढाने की कला]], [[गॉसियन अनुकूलन]], पहाड़ी चढ़ाई, और [[झुंड खुफिया]] (जैसे: [[चींटी कॉलोनी अनुकूलन]], [[कण झुंड अनुकूलन]]) और [[पूर्णांक रैखिक प्रोग्रामिंग]] पर आधारित विधियों सम्मिलित हैं। आनुवंशिक एल्गोरिदम की उपयुक्तता समस्या के ज्ञान की मात्रा पर निर्भर करती है; प्रसिद्ध समस्याओं में अधिकांश उत्तम, अधिक विशिष्ट दृष्टिकोण होते हैं। | ||
| Line 93: | Line 93: | ||
=== गुणसूत्र प्रतिनिधित्व === | === गुणसूत्र प्रतिनिधित्व === | ||
{{main |आनुवंशिक प्रतिनिधित्व}} | {{main |आनुवंशिक प्रतिनिधित्व}} | ||
सबसे सरल एल्गोरिथ्म प्रत्येक गुणसूत्र को बिट सरणी के रूप में दर्शाता है। सामान्यतः, संख्यात्मक मापदंडों को [[पूर्णांक|पूर्णांकों]] द्वारा दर्शाया जा सकता है, चूंकि [[तैरनेवाला स्थल]] अभ्यावेदन का उपयोग करना संभव है। इवोल्यूशन रणनीति और विकासवादी प्रोग्रामिंग के लिए फ्लोटिंग पॉइंट प्रतिनिधित्व स्वाभाविक है। वास्तविक-मूल्यवान आनुवंशिक एल्गोरिदम की धारणा की प्रस्तुति की गई है किन्तु वास्तव में एक मिथ्या नाम है क्योंकि यह वास्तव में | सबसे सरल एल्गोरिथ्म प्रत्येक गुणसूत्र को बिट सरणी के रूप में दर्शाता है। सामान्यतः, संख्यात्मक मापदंडों को [[पूर्णांक|पूर्णांकों]] द्वारा दर्शाया जा सकता है, चूंकि [[तैरनेवाला स्थल]] अभ्यावेदन का उपयोग करना संभव है। इवोल्यूशन रणनीति और विकासवादी प्रोग्रामिंग के लिए फ्लोटिंग पॉइंट प्रतिनिधित्व स्वाभाविक है। वास्तविक-मूल्यवान आनुवंशिक एल्गोरिदम की धारणा की प्रस्तुति की गई है किन्तु वास्तव में एक मिथ्या नाम है क्योंकि यह वास्तव में रचक खंड सिद्धांत का प्रतिनिधित्व नहीं करता है जो 1970 के दशक में [[जॉन हेनरी हॉलैंड]] द्वारा प्रस्तावित किया गया था। सैद्धांतिक और प्रयोगात्मक परिणामों (नीचे देखें) के आधार पर, चूंकि यह सिद्धांत समर्थन के बिना नहीं है। मूलभूत एल्गोरिथ्म बिट स्तर पर पारगमन और उत्परिवर्तन करता है। अन्य वेरिएंट क्रोमोसोम को संख्याओं की एक सूची के रूप में मानते हैं जो एक निर्देश तालिका, एक लिंक की गई सूची में नोड्स, [[साहचर्य सरणी]], [[वस्तु (कंप्यूटर विज्ञान)]], या कोई अन्य कल्पनीय [[डेटा संरचना|समुच्चय संरचना]] में अनुक्रमित होते हैं। समुच्चय तत्व सीमाओं का सम्मान करने के लिए पारगमन और उत्परिवर्तन किया जाता है। अधिकांश समुच्चय प्रकारों के लिए, विशिष्ट भिन्नता प्रचालक को डिज़ाइन किया जा सकता है। अलग-अलग विशिष्ट समस्या डोमेन के लिए अलग-अलग क्रोमोसोमल समुच्चय प्रकार उत्तम या बदतर काम करते हैं। | ||
जब पूर्णांकों के बिट-स्ट्रिंग अभ्यावेदन का उपयोग किया जाता है, तो [[ग्रे कोडिंग]] को अधिकांश नियोजित किया जाता है। इस प्रकार, पूर्णांक में छोटे बदलाव | जब पूर्णांकों के बिट-स्ट्रिंग अभ्यावेदन का उपयोग किया जाता है, तो [[ग्रे कोडिंग]] को अधिकांश नियोजित किया जाता है। इस प्रकार, पूर्णांक में छोटे बदलाव उत्परिवर्तन या पारगमन के माध्यम से आसानी से प्रभावित हो सकते हैं। यह तथाकथित हैमिंग दीवारों पर समयपूर्व अभिसरण को रोकने में सहायता करने के लिए पाया गया है, जिसमें क्रोमोसोम को उत्तम समाधान में बदलने के लिए एक साथ कई उत्परिवर्तन (या पारगमन घटनाएं) होनी चाहिए। | ||
अन्य दृष्टिकोणों में गुणसूत्रों का प्रतिनिधित्व करने के लिए बिट स्ट्रिंग्स के अतिरिक्त वास्तविक-मूल्यवान संख्याओं की सरणियों का उपयोग करना सम्मिलित है। स्कीमाटा के सिद्धांत के परिणाम बताते हैं कि सामान्यतः वर्ण जितना छोटा होता है, प्रदर्शन उतना ही उत्तम होता है, किन्तु शोधकर्ताओं के लिए प्रारंभ में यह आश्चर्यजनक था कि वास्तविक-मानमूल्य वाले गुणसूत्रों का उपयोग करने से अच्छे परिणाम प्राप्त हुए। इसे क्रोमोसोम की एक परिमित | अन्य दृष्टिकोणों में गुणसूत्रों का प्रतिनिधित्व करने के लिए बिट स्ट्रिंग्स के अतिरिक्त वास्तविक-मूल्यवान संख्याओं की सरणियों का उपयोग करना सम्मिलित है। स्कीमाटा के सिद्धांत के परिणाम बताते हैं कि सामान्यतः वर्ण जितना छोटा होता है, प्रदर्शन उतना ही उत्तम होता है, किन्तु शोधकर्ताओं के लिए प्रारंभ में यह आश्चर्यजनक था कि वास्तविक-मानमूल्य वाले गुणसूत्रों का उपयोग करने से अच्छे परिणाम प्राप्त हुए। इसे क्रोमोसोम की एक परिमित सरंध्रता में वास्तविक मानों के सेट के रूप में समझाया गया था, क्योंकि फ्लोटिंग पॉइंट प्रतिनिधित्व से अपेक्षाकृत कम कार्डिनैलिटी के साथ वर्चुअल वर्णमाला (जब चयन और पुनर्मूल्यांकन प्रभावी होते हैं) बनाते हैं।<ref name=Goldberg1991>{{cite book|last=Goldberg|first=David E.|title=Parallel Problem Solving from Nature|chapter=The theory of virtual alphabets|journal=Parallel Problem Solving from Nature, Lecture Notes in Computer Science|year=1991|volume=496|pages=13–22|doi=10.1007/BFb0029726|series=Lecture Notes in Computer Science|isbn=978-3-540-54148-6}}</ref><ref name=Janikow1991>{{cite journal|last1=Janikow|first1=C. Z.|first2=Z. |last2=Michalewicz |title=An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms|journal=Proceedings of the Fourth International Conference on Genetic Algorithms|year=1991|pages=31–36|url=http://www.cs.umsl.edu/~janikow/publications/1991/GAbin/text.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.umsl.edu/~janikow/publications/1991/GAbin/text.pdf |archive-date=2022-10-09 |url-status=live|access-date=2 July 2013}}</ref> | ||
जेनेटिक एल्गोरिथम सुलभ समस्या डोमेन का विस्तार समाधान पूल के अधिक जटिल एन्कोडिंग के माध्यम से कई प्रकार के विषम एन्कोडेड जीनों को एक गुणसूत्र में जोड़कर प्राप्त किया जा सकता है।<ref name=Patrascu2014>{{cite journal|last1=Patrascu|first1=M.|last2=Stancu|first2=A.F.|last3=Pop|first3=F.|title=HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation|journal=Soft Computing|year=2014|volume=18|issue=12|pages=2565–2576|doi=10.1007/s00500-014-1401-y|s2cid=29821873}}</ref> यह विशेष दृष्टिकोण उन अनुकूलन समस्याओं को समाधान करने की अनुमति देता है जिनके लिए समस्या मापदंडों के लिए अत्यधिक भिन्न परिभाषा डोमेन की आवश्यकता होती है। उदाहरण के लिए, कैस्केड कंट्रोलर ट्यूनिंग की समस्याओं में, आंतरिक लूप नियंत्रक संरचना तीन मापदंडों के एक पारंपरिक नियामक से संबंधित हो सकती है, चूंकि बाहरी लूप एक भाषाई नियंत्रक (जैसे फ़ज़ी प्रणाली) को प्रायुक्त कर सकता है, जिसका एक अलग विवरण है। एन्कोडिंग के इस विशेष रूप के लिए एक विशेष | जेनेटिक एल्गोरिथम सुलभ समस्या डोमेन का विस्तार समाधान पूल के अधिक जटिल एन्कोडिंग के माध्यम से कई प्रकार के विषम एन्कोडेड जीनों को एक गुणसूत्र में जोड़कर प्राप्त किया जा सकता है।<ref name=Patrascu2014>{{cite journal|last1=Patrascu|first1=M.|last2=Stancu|first2=A.F.|last3=Pop|first3=F.|title=HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation|journal=Soft Computing|year=2014|volume=18|issue=12|pages=2565–2576|doi=10.1007/s00500-014-1401-y|s2cid=29821873}}</ref> यह विशेष दृष्टिकोण उन अनुकूलन समस्याओं को समाधान करने की अनुमति देता है जिनके लिए समस्या मापदंडों के लिए अत्यधिक भिन्न परिभाषा डोमेन की आवश्यकता होती है। उदाहरण के लिए, कैस्केड कंट्रोलर ट्यूनिंग की समस्याओं में, आंतरिक लूप नियंत्रक संरचना तीन मापदंडों के एक पारंपरिक नियामक से संबंधित हो सकती है, चूंकि बाहरी लूप एक भाषाई नियंत्रक (जैसे फ़ज़ी प्रणाली) को प्रायुक्त कर सकता है, जिसका एक अलग विवरण है। एन्कोडिंग के इस विशेष रूप के लिए एक विशेष पारगमन तंत्र की आवश्यकता होती है जो क्रोमोसोम को खंड द्वारा पुनर्संयोजित करता है, और यह जटिल अनुकूली प्रणालियों, विशेष रूप से विकास प्रक्रियाओं के मॉडलिंग और अनुकरण के लिए एक उपयोगी उपकरण है। | ||
=== अभिजात वर्ग === | === अभिजात वर्ग === | ||
एक नई | एक नई सरंध्रता के निर्माण की सामान्य प्रक्रिया का एक व्यावहारिक रूप वर्तमान पीढ़ी से सर्वोत्तम जीवों को अगले, अनछुए तक ले जाने की अनुमति देना है। इस रणनीति को अभिजात्य चयन के रूप में जाना जाता है और यह गारंटी देता है कि जीए द्वारा प्राप्त समाधान की गुणवत्ता एक पीढ़ी से दूसरी पीढ़ी तक कम नहीं होगी।<ref>{{cite conference |last1=Baluja |first1=Shumeet |first2=Rich |last2=Caruana |title=Removing the genetics from the standard genetic algorithm |conference=[[International Conference on Machine Learning|ICML]] |year=1995 |url=http://www.ri.cmu.edu/pub_files/pub2/baluja_shumeet_1995_1/baluja_shumeet_1995_1.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.ri.cmu.edu/pub_files/pub2/baluja_shumeet_1995_1/baluja_shumeet_1995_1.pdf |archive-date=2022-10-09 |url-status=live}}</ref> | ||
| Line 107: | Line 107: | ||
अनुवांशिक एल्गोरिदम के समांतर एल्गोरिदम कार्यान्वयन दो स्वादों में आते हैं। मोटे-दाने वाले समानांतर आनुवंशिक एल्गोरिदम प्रत्येक कंप्यूटर नोड पर जनसंख्या और नोड्स के बीच व्यक्तियों के प्रवासन को मानते हैं। सुक्ष्म समानांतर आनुवंशिक एल्गोरिदम प्रत्येक प्रोसेसर नोड पर एक व्यक्ति को ग्रहण करते हैं जो चयन और प्रजनन के लिए पड़ोसी व्यक्तियों के साथ कार्य करता है। | अनुवांशिक एल्गोरिदम के समांतर एल्गोरिदम कार्यान्वयन दो स्वादों में आते हैं। मोटे-दाने वाले समानांतर आनुवंशिक एल्गोरिदम प्रत्येक कंप्यूटर नोड पर जनसंख्या और नोड्स के बीच व्यक्तियों के प्रवासन को मानते हैं। सुक्ष्म समानांतर आनुवंशिक एल्गोरिदम प्रत्येक प्रोसेसर नोड पर एक व्यक्ति को ग्रहण करते हैं जो चयन और प्रजनन के लिए पड़ोसी व्यक्तियों के साथ कार्य करता है। | ||
अन्य प्रकार, जैसे [[ऑनलाइन अनुकूलन]] समस्याओं के लिए आनुवंशिक एल्गोरिदम, | अन्य प्रकार, जैसे [[ऑनलाइन अनुकूलन]] समस्याओं के लिए आनुवंशिक एल्गोरिदम, उपयुक्तता फलन में समय-निर्भरता या ध्वनी का परिचय देते हैं। | ||
=== अनुकूली जीए === | === अनुकूली जीए === | ||
अनुकूली मापदंडों के साथ आनुवंशिक एल्गोरिदम (अनुकूली आनुवंशिक एल्गोरिदम, | अनुकूली मापदंडों के साथ आनुवंशिक एल्गोरिदम (अनुकूली आनुवंशिक एल्गोरिदम, एजीएएस) आनुवंशिक एल्गोरिदम का एक और महत्वपूर्ण और आशाजनक संस्करण है। पारगमन (पीसी) और उत्परिवर्तन (अपराह्न) की संभावनाएं समाधान शुद्धता की डिग्री और अभिसरण गति को निर्धारित करती हैं जो आनुवंशिक एल्गोरिदम प्राप्त कर सकते हैं। पीसी और पीएम के निश्चित मानों का उपयोग करने के अतिरिक्त, एजीए प्रत्येक पीढ़ी में जनसंख्या की जानकारी का उपयोग करते हैं और जनसंख्या विविधता को बनाए रखने के साथ-साथ अभिसरण क्षमता को बनाए रखने के लिए पीसी और पीएम को अनुकूल रूप से समायोजित करते हैं। एजीए (अनुकूली आनुवंशिक एल्गोरिथम),<ref>{{Cite journal |last1=Srinivas |first1=M. |last2=Patnaik |first2=L. |title=Adaptive probabilities of crossover and mutation in genetic algorithms |journal=IEEE Transactions on System, Man and Cybernetics |volume=24 |issue=4 |pages=656–667 |year=1994 |doi=10.1109/21.286385 |url=http://eprints.iisc.ac.in/6971/2/adaptive.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://eprints.iisc.ac.in/6971/2/adaptive.pdf |archive-date=2022-10-09 |url-status=live }}</ref> में पीसी और पीएम का समायोजन समाधानों के उपयुक्तता मानों पर निर्भर करता है। सीएजीए (क्लस्टरिंग-आधारित अनुकूली आनुवंशिक एल्गोरिथम) में,<ref>{{cite journal |last1=Zhang |first1=J. |last2=Chung |first2=H. |last3=Lo, W. L. |title=Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms |journal=IEEE Transactions on Evolutionary Computation |volume=11 |issue=3 |pages=326–335 |year=2007 |doi=10.1109/TEVC.2006.880727 |s2cid=2625150 }}</ref> जनसंख्या के अनुकूलन राज्यों का न्याय करने के लिए क्लस्टरिंग विश्लेषण के उपयोग के माध्यम से, पीसी और पीएम का समायोजन इन अनुकूलन राज्यों पर निर्भर करता है। | ||
GA को अन्य अनुकूलन विधियों के साथ संयोजित करना अधिक प्रभावी हो सकता है। सामान्यतः अच्छे वैश्विक समाधान खोजने में एक जीए अधिक अच्छा होता है, किन्तु पूर्ण इष्टतम खोजने के लिए पिछले कुछ | GA को अन्य अनुकूलन विधियों के साथ संयोजित करना अधिक प्रभावी हो सकता है। सामान्यतः अच्छे वैश्विक समाधान खोजने में एक जीए अधिक अच्छा होता है, किन्तु पूर्ण इष्टतम खोजने के लिए पिछले कुछ उत्परिवर्तनों को खोजने में अधिक अक्षम है। अन्य तकनीकें (जैसे पहाड़ी चढ़ाई) एक सीमित क्षेत्र में पूर्ण इष्टतम खोजने में अधिक कुशल हैं। वैकल्पिक जीए और पहाड़ी चढ़ाई की शक्तिशालीी की कमी को दूर करते हुए पहाड़ी चढ़ाई जीए की दक्षता में सुधार कर सकते हैं।{{Citation needed|date=July 2016}} | ||
इसका अर्थ यह है कि प्राकृतिक स्थितियों में अनुवांशिक भिन्नता के नियमों का एक अलग अर्थ हो सकता है। उदाहरण के लिए - परन्तु चरणों को लगातार क्रम में संग्रहीत किया जाए - क्रॉसिंग ओवर मातृ डीएनए से कई चरणों का योग कर सकता है और पैतृक डीएनए से कई चरणों को जोड़ सकता है। यह उन सदिशों को जोड़ने के समान है जो लक्षणप्ररूपी भूदृश्य में एक रिज का अनुसरण कर सकते हैं। इस प्रकार, परिमाण के कई आदेशों से प्रक्रिया की दक्षता में वृद्धि हो सकती है। इसके अतिरिक्त, क्रोमोसोमल व्युत्क्रम में जीवित रहने या दक्षता के पक्ष में लगातार क्रम या किसी अन्य उपयुक्त क्रम में चरण रखने का अवसर होता है।<ref>See for instance [http://www.thisurlisfalse.com/evolution-in-a-nutshell/ Evolution-in-a-nutshell] {{Webarchive|url=https://web.archive.org/web/20160415193505/http://www.thisurlisfalse.com/evolution-in-a-nutshell/ |date=15 April 2016 }} or example in [[travelling salesman problem]], in particular the use of an [[edge recombination operator]].</ref> | इसका अर्थ यह है कि प्राकृतिक स्थितियों में अनुवांशिक भिन्नता के नियमों का एक अलग अर्थ हो सकता है। उदाहरण के लिए - परन्तु चरणों को लगातार क्रम में संग्रहीत किया जाए - क्रॉसिंग ओवर मातृ डीएनए से कई चरणों का योग कर सकता है और पैतृक डीएनए से कई चरणों को जोड़ सकता है। यह उन सदिशों को जोड़ने के समान है जो लक्षणप्ररूपी भूदृश्य में एक रिज का अनुसरण कर सकते हैं। इस प्रकार, परिमाण के कई आदेशों से प्रक्रिया की दक्षता में वृद्धि हो सकती है। इसके अतिरिक्त, क्रोमोसोमल व्युत्क्रम में जीवित रहने या दक्षता के पक्ष में लगातार क्रम या किसी अन्य उपयुक्त क्रम में चरण रखने का अवसर होता है।<ref>See for instance [http://www.thisurlisfalse.com/evolution-in-a-nutshell/ Evolution-in-a-nutshell] {{Webarchive|url=https://web.archive.org/web/20160415193505/http://www.thisurlisfalse.com/evolution-in-a-nutshell/ |date=15 April 2016 }} or example in [[travelling salesman problem]], in particular the use of an [[edge recombination operator]].</ref> | ||
| Line 118: | Line 118: | ||
एक भिन्नता, जहां एक पूरे के रूप में जनसंख्या अपने व्यक्तिगत सदस्यों के अतिरिक्त विकसित होती है, जीन पूल पुनर्संयोजन के रूप में जाना जाता है। | एक भिन्नता, जहां एक पूरे के रूप में जनसंख्या अपने व्यक्तिगत सदस्यों के अतिरिक्त विकसित होती है, जीन पूल पुनर्संयोजन के रूप में जाना जाता है। | ||
उपयुक्तता एपिस्टासिस के उच्च स्तर के साथ समस्याओं पर जीए के प्रदर्शन को उत्तम बनाने का प्रयास करने के लिए कई विविधताएं विकसित की गई हैं, अर्थात् जहां किसी समाधान की उपयुक्तता में इसके चर के अंतःक्रियात्मक सबसेट होते हैं। इस प्रकार के एल्गोरिदम का उद्देश्य इन लाभकारी लक्षणप्ररूपिक इंटरैक्शन को सीखना (शोषण करने से पहले) है। जैसे, वे विघटनकारी पुनर्संयोजन को अनुकूल रूप से कम करने में रचक खंड परिकल्पना के साथ संरेखित हैं। इस दृष्टिकोण के प्रमुख उदाहरणों में एमजीए,<ref>{{cite journal |url=http://www.complex-systems.com/issues/03-5.html |first1=D. E. |last1=Goldberg |first2=B. |last2=Korb |first3=K. |last3=Deb |title=Messy Genetic Algorithms : Motivation Analysis, and First Results |journal=Complex Systems |volume=5 |issue=3 |pages=493–530 |year=1989 }}</ref> जीईएम<ref>[https://www.osti.gov/servlets/purl/524858 Gene expression: The missing link in evolutionary computation]</ref> और एलएलजीए सम्मिलित है।<ref>{{cite thesis |last=Harik |first=G. |date=1997 |title=Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms |type=PhD |publisher=Dept. Computer Science, University of Michigan, Ann Arbour |url=http://portal.acm.org/citation.cfm?id=269517 }}</ref> | |||
== समस्या डोमेन == | == समस्या डोमेन == | ||
समस्याएं जो जेनेटिक एल्गोरिदम द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं उनमें [[जेनेटिक एल्गोरिदम शेड्यूलिंग]] सम्मिलित है, और कई शेड्यूलिंग सॉफ़्टवेयर पैकेज GAs पर आधारित हैं।{{Citation needed|date=December 2011}} | समस्याएं जो जेनेटिक एल्गोरिदम द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं उनमें [[जेनेटिक एल्गोरिदम शेड्यूलिंग]] सम्मिलित है, और कई शेड्यूलिंग सॉफ़्टवेयर पैकेज GAs पर आधारित हैं।{{Citation needed|date=December 2011}} जीए को [[अभियांत्रिकी]] में भी प्रायुक्त किया गया है।<ref>Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. [http://www.mdpi.com/1996-1073/6/3/1439/pdf Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II. ] Energies. 2013; 6(3):1439-1455.</ref> [[वैश्विक अनुकूलन]] समस्याओं को समाधान करने के लिए आनुवंशिक एल्गोरिदम को अधिकांश एक दृष्टिकोण के रूप में प्रायुक्त किया जाता है। | ||
थंब जेनेटिक एल्गोरिदम के एक सामान्य नियम के रूप में समस्या डोमेन में उपयोगी हो सकता है जिसमें मिश्रण के रूप में एक जटिल | थंब जेनेटिक एल्गोरिदम के एक सामान्य नियम के रूप में समस्या डोमेन में उपयोगी हो सकता है जिसमें मिश्रण के रूप में एक जटिल उपयुक्तता परिदृश्य है, अर्थात्, उत्परिवर्तन (जेनेटिक एल्गोरिदम) पारगमन (जेनेटिक एल्गोरिदम) के संयोजन में, सरंध्रता को [[स्थानीय ऑप्टिमा]] से दूर ले जाने के लिए डिज़ाइन किया गया है। एक पारंपरिक पहाड़ी चढ़ाई एल्गोरिथ्म में फंस सकता है। निरीक्षण करें कि सामान्यतः उपयोग किए जाने वाले पारगमन ऑपरेटर किसी भी समान सरंध्रता को नहीं बदल सकते हैं। अकेले उत्परिवर्तन समग्र आनुवंशिक एल्गोरिथम प्रक्रिया ([[मार्कोव श्रृंखला]] के रूप में देखा गया) की क्षुद्रता प्रदान कर सकता है। | ||
जेनेटिक एल्गोरिदम द्वारा समाधान की गई समस्याओं के उदाहरणों में सम्मिलित हैं: सूर्य के प्रकाश को सौर संग्राहक तक पहुंचाने के लिए डिज़ाइन किए गए दर्पण,<ref>{{cite web|last=Gross|first=Bill|title=A solar energy system that tracks the sun|url=https://www.ted.com/talks/bill_gross_a_solar_energy_system_that_tracks_the_sun|work=TED|date=2 February 2009 |access-date=20 November 2013}}</ref> अंतरिक्ष में रेडियो सिग्नल लेने के लिए डिज़ाइन किया गया एंटीना,<ref>{{citation |first1=G. S. |last1=Hornby |first2=D. S. |last2=Linden |first3=J. D. |last3=Lohn |url=http://ti.arc.nasa.gov/m/pub-archive/1244h/1244%20(Hornby).pdf |title=Automated Antenna Design with Evolutionary Algorithms}}</ref> कंप्यूटर के आंकड़ों के लिए चलने के विधियों,<ref>{{Cite web | url=http://goatstream.com/research/papers/SA2013/index.html | title=Flexible Muscle-Based Locomotion for Bipedal Creatures}}</ref> जटिल प्रवाहक्षेत्रों में वायुगतिकीय पिंडों का इष्टतम डिजाइन<ref>{{Cite journal|last1=Evans|first1=B.|last2=Walton|first2=S.P.|date=December 2017|title=Aerodynamic optimisation of a hypersonic reentry vehicle based on solution of the Boltzmann–BGK equation and evolutionary optimisation|journal=Applied Mathematical Modelling|volume=52|pages=215–240|doi=10.1016/j.apm.2017.07.024|issn=0307-904X|url=https://cronfa.swan.ac.uk/Record/cronfa34688|doi-access=free}}</ref> अपने एल्गोरिथम डिज़ाइन | जेनेटिक एल्गोरिदम द्वारा समाधान की गई समस्याओं के उदाहरणों में सम्मिलित हैं: सूर्य के प्रकाश को सौर संग्राहक तक पहुंचाने के लिए डिज़ाइन किए गए दर्पण,<ref>{{cite web|last=Gross|first=Bill|title=A solar energy system that tracks the sun|url=https://www.ted.com/talks/bill_gross_a_solar_energy_system_that_tracks_the_sun|work=TED|date=2 February 2009 |access-date=20 November 2013}}</ref> अंतरिक्ष में रेडियो सिग्नल लेने के लिए डिज़ाइन किया गया एंटीना,<ref>{{citation |first1=G. S. |last1=Hornby |first2=D. S. |last2=Linden |first3=J. D. |last3=Lohn |url=http://ti.arc.nasa.gov/m/pub-archive/1244h/1244%20(Hornby).pdf |title=Automated Antenna Design with Evolutionary Algorithms}}</ref> कंप्यूटर के आंकड़ों के लिए चलने के विधियों,<ref>{{Cite web | url=http://goatstream.com/research/papers/SA2013/index.html | title=Flexible Muscle-Based Locomotion for Bipedal Creatures}}</ref> जटिल प्रवाहक्षेत्रों में वायुगतिकीय पिंडों का इष्टतम डिजाइन<ref>{{Cite journal|last1=Evans|first1=B.|last2=Walton|first2=S.P.|date=December 2017|title=Aerodynamic optimisation of a hypersonic reentry vehicle based on solution of the Boltzmann–BGK equation and evolutionary optimisation|journal=Applied Mathematical Modelling|volume=52|pages=215–240|doi=10.1016/j.apm.2017.07.024|issn=0307-904X|url=https://cronfa.swan.ac.uk/Record/cronfa34688|doi-access=free}}</ref> अपने एल्गोरिथम डिज़ाइन स्वतः में, [[स्टीवन स्कीएना]] किसी भी कार्य के लिए आनुवंशिक एल्गोरिथम के विरुद्ध सलाह देता है: | ||
{{blockquote|[I] बिट स्ट्रिंग्स पर उत्परिवर्तन और क्रॉसओवर जैसे अनुवांशिक ऑपरेटरों के मामले में मॉडल अनुप्रयोगों के लिए काफी अप्राकृतिक है। छद्म जीव विज्ञान आपके और आपकी समस्या के बीच जटिलता का एक और स्तर जोड़ता है। दूसरा, अनुवांशिक एल्गोरिदम गैर-तुच्छ समस्याओं पर बहुत लंबा समय लेते हैं। [...] [टी] वह विकास के साथ सादृश्य-जहां महत्वपूर्ण प्रगति की आवश्यकता है [एसआईसी] लाखों साल-काफी उपयुक्त हो सकता है। | {{blockquote|[I] बिट स्ट्रिंग्स पर उत्परिवर्तन और क्रॉसओवर जैसे अनुवांशिक ऑपरेटरों के मामले में मॉडल अनुप्रयोगों के लिए काफी अप्राकृतिक है। छद्म जीव विज्ञान आपके और आपकी समस्या के बीच जटिलता का एक और स्तर जोड़ता है। दूसरा, अनुवांशिक एल्गोरिदम गैर-तुच्छ समस्याओं पर बहुत लंबा समय लेते हैं। [...] [टी] वह विकास के साथ सादृश्य-जहां महत्वपूर्ण प्रगति की आवश्यकता है [एसआईसी] लाखों साल-काफी उपयुक्त हो सकता है। | ||
| Line 135: | Line 135: | ||
== इतिहास == | == इतिहास == | ||
1950 में, [[एलन ट्यूरिंग]] ने एक सीखने की मशीन प्रस्तावित की जो विकास के सिद्धांतों के समानांतर होगी।<ref name="mind.oxfordjournals.org">{{cite journal|last1=Turing|first1=Alan M.|title=Computing machinery and intelligence|journal=Mind|volume=LIX|issue=238|pages=433–460|doi=10.1093/mind/LIX.236.433|date=October 1950}}</ref> विकास का कंप्यूटर सिमुलेशन 1954 में [[निल्स ऑल बरीज़]] के काम से प्रारंभ हुआ, जो प्रिंसटन, न्यू जर्सी में [[उन्नत अध्ययन संस्थान]] में कंप्यूटर का उपयोग कर रहे थे। | 1950 में, [[एलन ट्यूरिंग]] ने एक सीखने की मशीन प्रस्तावित की जो विकास के सिद्धांतों के समानांतर होगी।<ref name="mind.oxfordjournals.org">{{cite journal|last1=Turing|first1=Alan M.|title=Computing machinery and intelligence|journal=Mind|volume=LIX|issue=238|pages=433–460|doi=10.1093/mind/LIX.236.433|date=October 1950}}</ref> विकास का कंप्यूटर सिमुलेशन 1954 में [[निल्स ऑल बरीज़]] के काम से प्रारंभ हुआ, जो प्रिंसटन, न्यू जर्सी में [[उन्नत अध्ययन संस्थान]] में कंप्यूटर का उपयोग कर रहे थे। | ||
=== वाणिज्यिक उत्पाद === | === वाणिज्यिक उत्पाद === | ||
| Line 164: | Line 159: | ||
* विकास की रणनीति (ईएस, रेचेनबर्ग, 1994 देखें) व्यक्तियों को उत्परिवर्तन और मध्यवर्ती या असतत पुनर्संयोजन के माध्यम से विकसित करती है। ईएस एल्गोरिदम विशेष रूप से वास्तविक मान डोमेन में समस्याओं को समाधान करने के लिए डिज़ाइन किए गए हैं।<ref>{{cite book|last=Cohoon|first=J|display-authors=etal|title=Evolutionary algorithms for the physical design of VLSI circuits|url= https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf |archive-date=2022-10-09 |url-status=live|journal=Advances in Evolutionary Computing: Theory and Applications|publisher= Springer, pp. 683-712, 2003|isbn=978-3-540-43330-9|year=2002}}</ref> वे खोज के नियंत्रण मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं। स्व-अनुकूलन के डी-रैंडमाइजेशन ने समकालीन सहप्रसरण मैट्रिक्स अनुकूलन विकास रणनीति ([[CMA-ES|सीएमए-ईएस]]) को जन्म दिया है। | * विकास की रणनीति (ईएस, रेचेनबर्ग, 1994 देखें) व्यक्तियों को उत्परिवर्तन और मध्यवर्ती या असतत पुनर्संयोजन के माध्यम से विकसित करती है। ईएस एल्गोरिदम विशेष रूप से वास्तविक मान डोमेन में समस्याओं को समाधान करने के लिए डिज़ाइन किए गए हैं।<ref>{{cite book|last=Cohoon|first=J|display-authors=etal|title=Evolutionary algorithms for the physical design of VLSI circuits|url= https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf |archive-date=2022-10-09 |url-status=live|journal=Advances in Evolutionary Computing: Theory and Applications|publisher= Springer, pp. 683-712, 2003|isbn=978-3-540-43330-9|year=2002}}</ref> वे खोज के नियंत्रण मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं। स्व-अनुकूलन के डी-रैंडमाइजेशन ने समकालीन सहप्रसरण मैट्रिक्स अनुकूलन विकास रणनीति ([[CMA-ES|सीएमए-ईएस]]) को जन्म दिया है। | ||
* विकासवादी प्रोग्रामिंग (ईपी) में मुख्य रूप से उत्परिवर्तन और चयन और स्वैछिक प्रतिनिधित्व वाले समाधानों की | * विकासवादी प्रोग्रामिंग (ईपी) में मुख्य रूप से उत्परिवर्तन और चयन और स्वैछिक प्रतिनिधित्व वाले समाधानों की सरंध्रता सम्मिलित है। वे मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं, और अन्य विविधता संचालन सम्मिलित कर सकते हैं जैसे कि कई माता-पिता से जानकारी का संयोजन। | ||
* वितरण एल्गोरिथ्म ( | * वितरण एल्गोरिथ्म (इडीए) का अनुमान मॉडल-निर्देशित प्रचालक द्वारा पारंपरिक प्रजनन प्रचालक को प्रतिस्थापित करता है। इस प्रकार के मॉडल मशीन लर्निंग तकनीकों को नियोजित करके जनसंख्या से सीखे जाते हैं और संभाव्य चित्रात्मक प्रतिरूप के रूप में प्रस्तुत किए जाते हैं, जिनसे नए समाधानों का मानक लिया जा सकता है<ref>{{cite book|last1=Pelikan|first1=Martin|last2=Goldberg|first2=David E.|last3=Cantú-Paz|first3=Erick|title=BOA: The Bayesian Optimization Algorithm|journal=Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1|date=1 January 1999|pages=525–532|url=http://dl.acm.org/citation.cfm?id=2933973|isbn=9781558606111|series=Gecco'99}}</ref><ref>{{cite book|last1=Pelikan|first1=Martin|title=Hierarchical Bayesian optimization algorithm : toward a new generation of evolutionary algorithms|date=2005|publisher=Springer|location=Berlin [u.a.]|isbn=978-3-540-23774-7|edition=1st}}</ref> या निर्देशित-पारगमन से उत्पन्न।<ref>{{cite book|last1=Thierens|first1=Dirk|chapter=The Linkage Tree Genetic Algorithm|journal=Parallel Problem Solving from Nature, PPSN XI|date=11 September 2010|pages=264–273|doi=10.1007/978-3-642-15844-5_27|language=en|isbn=978-3-642-15843-8}}</ref> | ||
* जेनेटिक प्रोग्रामिंग (जीपी) [[जॉन बकरी]] द्वारा लोकप्रिय एक संबंधित तकनीक है जिसमें | * जेनेटिक प्रोग्रामिंग (जीपी) [[जॉन बकरी]] द्वारा लोकप्रिय एक संबंधित तकनीक है जिसमें फलन पैरामीटर के अतिरिक्त कंप्यूटर प्रोग्राम को अनुकूलित किया जाता है। जेनेटिक प्रोग्रामिंग अधिकांश ट्री (समुच्चय स्ट्रक्चर) | ट्री-आधारित आंतरिक समुच्चय स्ट्रक्चर का उपयोग करती है, जो जेनेटिक एल्गोरिदम की विशिष्ट [[सूची (कंप्यूटिंग)]] संरचनाओं के अतिरिक्त अनुकूलन के लिए कंप्यूटर प्रोग्राम का प्रतिनिधित्व करती है। [[कार्टेशियन जेनेटिक प्रोग्रामिंग]], जीन एक्सप्रेशन प्रोग्रामिंग सहित जेनेटिक प्रोग्रामिंग के कई प्रकार हैं।<ref>{{cite journal|last=Ferreira|first=C|title=Gene Expression Programming: A New Adaptive Algorithm for Solving Problems|url= http://www.gene-expression-programming.com/webpapers/GEP.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.gene-expression-programming.com/webpapers/GEP.pdf |archive-date=2022-10-09 |url-status=live|journal=Complex Systems |year=2001|volume=13 |issue=2 |pages=87–129|arxiv=cs/0102027|bibcode=2001cs........2027F}}</ref> [[व्याकरणिक विकास]], [[रैखिक आनुवंशिक प्रोग्रामिंग]], [[बहु अभिव्यक्ति प्रोग्रामिंग]] आदि। | ||
* [[समूहन आनुवंशिक एल्गोरिथम]] ( | * [[समूहन आनुवंशिक एल्गोरिथम]] (जीएजीए) जीए का एक विकास है, जहां फ़ोकस को अलग-अलग आइटम से स्थानांतरित किया जाता है, जैसे क्लासिकल जीए में, समूहों या आइटम के सबसेट पर।<ref name="Falkenauer">{{cite book|last=Falkenauer|first=Emanuel|author-link=Emanuel Falkenauer|year=1997|title=Genetic Algorithms and Grouping Problems|publisher=John Wiley & Sons Ltd|location=Chichester, England|isbn=978-0-471-97150-4}}</ref> [[इमैनुएल फल्केनाउर]] द्वारा प्रस्तावित इस जीए विकास के पीछे विचार यह है कि कुछ जटिल समस्याओं को समाधान करना, जैसे कि क्लस्टरिंग या विभाजन की समस्याएं जहां वस्तुओं के एक सेट को एक इष्टतम विधियों से वस्तुओं के अलग समूह में विभाजित किया जाना चाहिए, समूहों की विशेषताओं को बनाकर उत्तम विधियों से प्राप्त किया जा सकता है। जीन के समतुल्य वस्तुओं की। इस प्रकार की समस्याओं में बिन पैकिंग की समस्या, लाइन बैलेंसिंग, दूरी माप के संबंध में [[क्लस्टर विश्लेषण]], बराबर ढेर आदि सम्मिलित हैं, जिन पर क्लासिक जीए खराब प्रदर्शन करने वाले सिद्ध हुए। समूहों के समतुल्य जीन बनाने से तात्पर्य उन गुणसूत्रों से है जो सामान्य रूप से परिवर्तनशील लंबाई के होते हैं, और विशेष आनुवंशिक संचालक जो वस्तुओं के पूरे समूहों में हेरफेर करते हैं। विशेष रूप से बिन पैकिंग के लिए, मार्टेलो और टोथ के प्रभुत्व मानदंड के साथ संकरणित एक जीजीए यकीनन अब तक की सबसे अच्छी तकनीक है। | ||
* [[इंटरएक्टिव विकासवादी एल्गोरिदम]] विकासवादी एल्गोरिदम हैं जो मानव मूल्यांकन का उपयोग करते हैं। वे सामान्यतः उन डोमेन पर प्रायुक्त होते हैं जहां कम्प्यूटेशनल | * [[इंटरएक्टिव विकासवादी एल्गोरिदम|पारस्परिक विकासवादी एल्गोरिदम]] विकासवादी एल्गोरिदम हैं जो मानव मूल्यांकन का उपयोग करते हैं। वे सामान्यतः उन डोमेन पर प्रायुक्त होते हैं जहां कम्प्यूटेशनल उपयुक्तता फलन को डिज़ाइन करना कठिन होता है, उदाहरण के लिए, छवियों, संगीत, कलात्मक डिजाइनों और रूपों को उपयोगकर्ताओं की सौंदर्य पसंद को फिट करने के लिए विकसित करना। | ||
==== झुंड बुद्धि ==== | ==== झुंड बुद्धि ==== | ||
| Line 175: | Line 170: | ||
* एंट कॉलोनी ऑप्टिमाइज़ेशन (ACO) समाधान स्थान को पार करने और स्थानीय रूप से उत्पादक क्षेत्रों को खोजने के लिए फेरोमोन मॉडल से लैस कई चींटियों (या एजेंटों) का उपयोग करता है। | * एंट कॉलोनी ऑप्टिमाइज़ेशन (ACO) समाधान स्थान को पार करने और स्थानीय रूप से उत्पादक क्षेत्रों को खोजने के लिए फेरोमोन मॉडल से लैस कई चींटियों (या एजेंटों) का उपयोग करता है। | ||
*यद्यपि वितरण एल्गोरिथम का अनुमान माना जाता है,<ref>{{cite journal|last1=Zlochin|first1=Mark|last2=Birattari|first2=Mauro|last3=Meuleau|first3=Nicolas|last4=Dorigo|first4=Marco|title=Model-Based Search for Combinatorial Optimization: A Critical Survey|journal=Annals of Operations Research|date=1 October 2004|volume=131|issue=1–4|pages=373–395|doi=10.1023/B:ANOR.0000039526.52305.af|language=en|issn=0254-5330|citeseerx=10.1.1.3.427|s2cid=63137}}</ref> कण झुंड अनुकूलन (पीएसओ) बहु-पैरामीटर अनुकूलन के लिए एक कम्प्यूटेशनल विधि है जो जनसंख्या-आधारित दृष्टिकोण का भी उपयोग करती है। उम्मीदवार समाधान (कणों) की | *यद्यपि वितरण एल्गोरिथम का अनुमान माना जाता है,<ref>{{cite journal|last1=Zlochin|first1=Mark|last2=Birattari|first2=Mauro|last3=Meuleau|first3=Nicolas|last4=Dorigo|first4=Marco|title=Model-Based Search for Combinatorial Optimization: A Critical Survey|journal=Annals of Operations Research|date=1 October 2004|volume=131|issue=1–4|pages=373–395|doi=10.1023/B:ANOR.0000039526.52305.af|language=en|issn=0254-5330|citeseerx=10.1.1.3.427|s2cid=63137}}</ref> कण झुंड अनुकूलन (पीएसओ) बहु-पैरामीटर अनुकूलन के लिए एक कम्प्यूटेशनल विधि है जो जनसंख्या-आधारित दृष्टिकोण का भी उपयोग करती है। उम्मीदवार समाधान (कणों) की सरंध्रता (झुंड) खोज स्थान में चलती है, और कणों की गति उनकी अपनी सर्वश्रेष्ठ ज्ञात स्थिति और झुंड की वैश्विक सर्वोत्तम ज्ञात स्थिति दोनों से प्रभावित होती है। आनुवंशिक एल्गोरिथम की प्रकार, PSO विधि जनसंख्या सदस्यों के बीच सूचना साझा करने पर निर्भर करती है। कुछ समस्याओं में पीएसओ अधिकांश कम्प्यूटेशनल रूप से जीए की तुलना में, विशेष रूप से निरंतर चर के साथ अप्रतिबंधित समस्याओं में अधिक कुशल होता है।<ref>Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Vente | ||
r (2005) [https://www.mit.edu/~deweck/PDF_archive/3%20Refereed%20Conference/3_50_AIAA-2005-1897.pdf A comparison of particle swarm optimization and the genetic algorithm]</ref> | r (2005) [https://www.mit.edu/~deweck/PDF_archive/3%20Refereed%20Conference/3_50_AIAA-2005-1897.pdf A comparison of particle swarm optimization and the genetic algorithm]</ref> | ||
| Line 184: | Line 179: | ||
* [[MEME]] टिक एल्गोरिथम (MA), जिसे अधिकांश दूसरों के बीच हाइब्रिड जेनेटिक एल्गोरिथम कहा जाता है, एक जनसंख्या-आधारित पद्धति है जिसमें समाधान भी स्थानीय सुधार चरणों के अधीन होते हैं। [[मेमेटिक एल्गोरिदम]] का विचार मेम्स से आता है, जो जीन के विपरीत खुद को अनुकूलित कर सकते हैं। कुछ समस्या क्षेत्रों में उन्हें पारंपरिक विकासवादी एल्गोरिदम की तुलना में अधिक कुशल दिखाया गया है। | * [[MEME]] टिक एल्गोरिथम (MA), जिसे अधिकांश दूसरों के बीच हाइब्रिड जेनेटिक एल्गोरिथम कहा जाता है, एक जनसंख्या-आधारित पद्धति है जिसमें समाधान भी स्थानीय सुधार चरणों के अधीन होते हैं। [[मेमेटिक एल्गोरिदम]] का विचार मेम्स से आता है, जो जीन के विपरीत खुद को अनुकूलित कर सकते हैं। कुछ समस्या क्षेत्रों में उन्हें पारंपरिक विकासवादी एल्गोरिदम की तुलना में अधिक कुशल दिखाया गया है। | ||
* [[बैक्टीरियोलॉजिकल एल्गोरिदम]] (बीए) [[विकासवादी पारिस्थितिकी]] और विशेष रूप से बैक्टीरियोलॉजिक अनुकूलन से प्रेरित है। विकासवादी पारिस्थितिकी जीवित जीवों का उनके पर्यावरण के संदर्भ में अध्ययन है, जिसका उद्देश्य यह पता लगाना है कि वे कैसे अनुकूलन करते हैं। इसकी मूल अवधारणा यह है कि एक विषम वातावरण में, एक व्यक्ति ऐसा नहीं होता जो पूरे वातावरण के अनुकूल हो। इसलिए, जनसंख्या स्तर पर तर्क करने की जरूरत है। यह भी माना जाता है कि बीए को जटिल पोजिशनिंग समस्याओं (सेल फोन, शहरी नियोजन, और इसी प्रकार के एंटेना) या | * [[बैक्टीरियोलॉजिकल एल्गोरिदम]] (बीए) [[विकासवादी पारिस्थितिकी]] और विशेष रूप से बैक्टीरियोलॉजिक अनुकूलन से प्रेरित है। विकासवादी पारिस्थितिकी जीवित जीवों का उनके पर्यावरण के संदर्भ में अध्ययन है, जिसका उद्देश्य यह पता लगाना है कि वे कैसे अनुकूलन करते हैं। इसकी मूल अवधारणा यह है कि एक विषम वातावरण में, एक व्यक्ति ऐसा नहीं होता जो पूरे वातावरण के अनुकूल हो। इसलिए, जनसंख्या स्तर पर तर्क करने की जरूरत है। यह भी माना जाता है कि बीए को जटिल पोजिशनिंग समस्याओं (सेल फोन, शहरी नियोजन, और इसी प्रकार के एंटेना) या समुच्चय माइनिंग के लिए सफलतापूर्वक प्रायुक्त किया जा सकता है।<ref>{{cite journal|url=http://www.irisa.fr/triskell/publis/2005/Baudry05d.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.irisa.fr/triskell/publis/2005/Baudry05d.pdf |archive-date=2022-10-09 |url-status=live|first=Benoit|last=Baudry |author2=Franck Fleurey |author3-link=Jean-Marc Jézéquel|author3=Jean-Marc Jézéquel |author4=Yves Le Traon|title=Automatic Test Case Optimization: A Bacteriologic Algorithm|date=March–April 2005|pages=76–82|journal=IEEE Software|issue=2|doi=10.1109/MS.2005.30|volume=22|s2cid=3559602|access-date=9 August 2009}}</ref> | ||
* सांस्कृतिक एल्गोरिथम (सीए) में जनसंख्या घटक सम्मिलित होता है जो लगभग आनुवंशिक एल्गोरिथम के समान होता है और इसके अतिरिक्त, एक ज्ञान घटक जिसे विश्वास स्थान कहा जाता है। | * सांस्कृतिक एल्गोरिथम (सीए) में जनसंख्या घटक सम्मिलित होता है जो लगभग आनुवंशिक एल्गोरिथम के समान होता है और इसके अतिरिक्त, एक ज्ञान घटक जिसे विश्वास स्थान कहा जाता है। | ||
* सुपरऑर्गेनिज्म के प्रवास से प्रेरित [[विभेदक विकास]] (DE)।<ref>{{cite journal|last=Civicioglu|first=P.|title=Transforming Geocentric Cartesian Coordinates to Geodetic Coordinates by Using Differential Search Algorithm|journal=Computers &Geosciences|year=2012|volume=46|pages=229–247|doi=10.1016/j.cageo.2011.12.011|bibcode=2012CG.....46..229C}}</ref> | * सुपरऑर्गेनिज्म के प्रवास से प्रेरित [[विभेदक विकास]] (DE)।<ref>{{cite journal|last=Civicioglu|first=P.|title=Transforming Geocentric Cartesian Coordinates to Geodetic Coordinates by Using Differential Search Algorithm|journal=Computers &Geosciences|year=2012|volume=46|pages=229–247|doi=10.1016/j.cageo.2011.12.011|bibcode=2012CG.....46..229C}}</ref> | ||
* गॉसियन अनुकूलन (सामान्य या प्राकृतिक अनुकूलन, जीए के साथ भ्रम से बचने के लिए संक्षिप्त एनए) सिग्नल प्रोसेसिंग प्रणाली की विनिर्माण उपज को अधिकतम करने के लिए अभिप्रेत है। इसका उपयोग साधारण पैरामीट्रिक अनुकूलन के लिए भी किया जा सकता है। यह स्वीकार्यता के सभी क्षेत्रों और सभी गाऊसी वितरणों के लिए मान्य एक निश्चित प्रमेय पर निर्भर करता है। एनए की दक्षता सूचना सिद्धांत और दक्षता के एक निश्चित प्रमेय पर निर्भर करती है। इसकी दक्षता को सूचना प्राप्त करने के लिए आवश्यक कार्य से विभाजित सूचना के रूप में परिभाषित किया गया है।<ref>{{cite journal|last=Kjellström|first=G.|title= On the Efficiency of Gaussian Adaptation|journal=Journal of Optimization Theory and Applications|volume=71|issue=3|pages=589–597|date=December 1991|doi= 10.1007/BF00941405|s2cid=116847975}}</ref> क्योंकि एनए व्यक्ति [[मतलब फिटनेस|अर्थ | * गॉसियन अनुकूलन (सामान्य या प्राकृतिक अनुकूलन, जीए के साथ भ्रम से बचने के लिए संक्षिप्त एनए) सिग्नल प्रोसेसिंग प्रणाली की विनिर्माण उपज को अधिकतम करने के लिए अभिप्रेत है। इसका उपयोग साधारण पैरामीट्रिक अनुकूलन के लिए भी किया जा सकता है। यह स्वीकार्यता के सभी क्षेत्रों और सभी गाऊसी वितरणों के लिए मान्य एक निश्चित प्रमेय पर निर्भर करता है। एनए की दक्षता सूचना सिद्धांत और दक्षता के एक निश्चित प्रमेय पर निर्भर करती है। इसकी दक्षता को सूचना प्राप्त करने के लिए आवश्यक कार्य से विभाजित सूचना के रूप में परिभाषित किया गया है।<ref>{{cite journal|last=Kjellström|first=G.|title= On the Efficiency of Gaussian Adaptation|journal=Journal of Optimization Theory and Applications|volume=71|issue=3|pages=589–597|date=December 1991|doi= 10.1007/BF00941405|s2cid=116847975}}</ref> क्योंकि एनए व्यक्ति [[मतलब फिटनेस|अर्थ उपयुक्तता]] के अतिरिक्त माध्य उपयुक्तता को अधिकतम करता है, परिदृश्य को इस प्रकार चिकना किया जाता है कि चोटियों के बीच की घाटियाँ गायब हो सकती हैं। इसलिए उपयुक्तता परिदृश्य में स्थानीय चोटियों से बचने की एक निश्चित महत्वाकांक्षा है। पल मैट्रिक्स के अनुकूलन द्वारा तेज शिखर पर चढ़ने में एनए भी अच्छा है, क्योंकि एनए गाऊसी के विकार ([[औसत जानकारी]]) को एक साथ औसत उपयुक्तता स्थिर रखते हुए अधिकतम कर सकता है। | ||
==== अन्य मेटाह्यूरिस्टिक विधियों ==== | ==== अन्य मेटाह्यूरिस्टिक विधियों ==== | ||
| Line 193: | Line 188: | ||
मेटाह्यूरिस्टिक विधियों विस्तृत रूप से स्टोकेस्टिक ऑप्टिमाइज़ेशन ऑप्टिमाइज़ेशन विधियों के अंतर्गत आते हैं। | मेटाह्यूरिस्टिक विधियों विस्तृत रूप से स्टोकेस्टिक ऑप्टिमाइज़ेशन ऑप्टिमाइज़ेशन विधियों के अंतर्गत आते हैं। | ||
* सिम्युलेटेड एनीलिंग (एसए) एक संबंधित वैश्विक अनुकूलन तकनीक है जो एक व्यक्तिगत समाधान पर यादृच्छिक उत्परिवर्तन का परीक्षण करके खोज स्थान को पार करती है। | * सिम्युलेटेड एनीलिंग (एसए) एक संबंधित वैश्विक अनुकूलन तकनीक है जो एक व्यक्तिगत समाधान पर यादृच्छिक उत्परिवर्तन का परीक्षण करके खोज स्थान को पार करती है। उपयुक्तता बढ़ाने वाले उत्परिवर्तन को हमेशा स्वीकार किया जाता है। उपयुक्तता में अंतर और घटते तापमान पैरामीटर के आधार पर उपयुक्तता को कम करने वाले उत्परिवर्तन को संभाव्य रूप से स्वीकार किया जाता है। एसए की भाषा में, अधिकतम उपयुक्तता के अतिरिक्त सबसे कम ऊर्जा की मांग करने की बात की जाती है। एसए का उपयोग एक मानक जीए एल्गोरिथम के अन्दर उत्परिवर्तन की अपेक्षाकृत उच्च दर से प्रारंभ करके और एक निश्चित समय के साथ समय के साथ इसे कम करके भी किया जा सकता है। | ||
* [[तब्बू खोज]] (टीएस) सिम्युलेटेड एनीलिंग के समान है जिसमें दोनों एक व्यक्तिगत समाधान के | * [[तब्बू खोज]] (टीएस) सिम्युलेटेड एनीलिंग के समान है जिसमें दोनों एक व्यक्तिगत समाधान के उत्परिवर्तन का परीक्षण करके समाधान स्थान को पार करते हैं। सिम्युलेटेड एनीलिंग केवल एक उत्परिवर्तित समाधान उत्पन्न करता है, टैबू खोज कई उत्परिवर्तित समाधान उत्पन्न करता है और उन समाधानों की ओर जाता है जो उत्पन्न सबसे कम ऊर्जा के साथ होते हैं। समाधान स्थान के माध्यम से चक्रण को रोकने और अधिक गति को प्रोत्साहित करने के लिए, आंशिक या पूर्ण समाधानों की एक टैबू सूची बनाए रखी जाती है। टैबू सूची के तत्वों वाले समाधान में जाने से मना किया जाता है, जिसे समाधान के रूप में अद्यतन किया जाता है, समाधान स्थान को पार करता है। | ||
* [[चरम अनुकूलन]] (ईओ) जीए के विपरीत, जो उम्मीदवार समाधानों की | * [[चरम अनुकूलन]] (ईओ) जीए के विपरीत, जो उम्मीदवार समाधानों की सरंध्रता के साथ काम करते हैं, ईओ एक एकल समाधान विकसित करता है और सबसे खराब घटकों के लिए [[स्थानीय खोज (अनुकूलन)]] संशोधन करता है। इसके लिए आवश्यक है कि एक उपयुक्त प्रतिनिधित्व का चयन किया जाए जो व्यक्तिगत समाधान घटकों को एक गुणवत्ता माप (उपयुक्तता) असाइन करने की अनुमति देता है। इस एल्गोरिथम के पीछे शासी सिद्धांत यह है कि निम्न-गुणवत्ता वाले घटकों को उत्तम रूप से हटाकर और उन्हें अव्यवस्थित रूप से चयनित घटक के साथ बदलकर आकस्मिक सुधार किया जाता है। यह निश्चित रूप से जीए के विपरीत है जो उत्तम समाधान करने के प्रयास में अच्छे समाधानों का चयन करता है। | ||
==== अन्य स्टोचैस्टिक अनुकूलन विधियाँ ==== | ==== अन्य स्टोचैस्टिक अनुकूलन विधियाँ ==== | ||
* [[क्रॉस-एन्ट्रॉपी विधि]] | क्रॉस-एन्ट्रॉपी (सीई) विधि पैरामीटरयुक्त संभाव्यता वितरण के माध्यम से उम्मीदवार समाधान उत्पन्न करती है। मापदंडों को क्रॉस-एन्ट्रापी न्यूनीकरण के माध्यम से अद्यतन किया जाता है, जिससे अगले पुनरावृत्ति में उत्तम | * [[क्रॉस-एन्ट्रॉपी विधि]] | क्रॉस-एन्ट्रॉपी (सीई) विधि पैरामीटरयुक्त संभाव्यता वितरण के माध्यम से उम्मीदवार समाधान उत्पन्न करती है। मापदंडों को क्रॉस-एन्ट्रापी न्यूनीकरण के माध्यम से अद्यतन किया जाता है, जिससे अगले पुनरावृत्ति में उत्तम मानकों उत्पन्न किए जा सकें। | ||
* रिएक्टिव सर्च ऑप्टिमाइज़ेशन (RSO) जटिल ऑप्टिमाइज़ेशन समस्याओं को समाधान करने के लिए उप-प्रतीकात्मक मशीन लर्निंग तकनीकों को सर्च ह्यूरिस्टिक्स में एकीकृत करने की वकालत करता है। रिएक्टिव शब्द महत्वपूर्ण मापदंडों के स्व-ट्यूनिंग के लिए आंतरिक ऑनलाइन फीडबैक लूप के माध्यम से खोज के समय घटनाओं के लिए तैयार प्रतिक्रिया पर संकेत देता है। रिएक्टिव सर्च के लिए रुचि की कार्यप्रणालियों में मशीन लर्निंग और सांख्यिकी, विशेष रूप से [[सुदृढीकरण सीखना]], [[एक्टिव लर्निंग (मशीन लर्निंग)]], तंत्रिका नेटवर्क और [[मेटाह्यूरिस्टिक्स]] सम्मिलित हैं। | * रिएक्टिव सर्च ऑप्टिमाइज़ेशन (RSO) जटिल ऑप्टिमाइज़ेशन समस्याओं को समाधान करने के लिए उप-प्रतीकात्मक मशीन लर्निंग तकनीकों को सर्च ह्यूरिस्टिक्स में एकीकृत करने की वकालत करता है। रिएक्टिव शब्द महत्वपूर्ण मापदंडों के स्व-ट्यूनिंग के लिए आंतरिक ऑनलाइन फीडबैक लूप के माध्यम से खोज के समय घटनाओं के लिए तैयार प्रतिक्रिया पर संकेत देता है। रिएक्टिव सर्च के लिए रुचि की कार्यप्रणालियों में मशीन लर्निंग और सांख्यिकी, विशेष रूप से [[सुदृढीकरण सीखना]], [[एक्टिव लर्निंग (मशीन लर्निंग)]], तंत्रिका नेटवर्क और [[मेटाह्यूरिस्टिक्स]] सम्मिलित हैं। | ||
| Line 253: | Line 248: | ||
=== ट्यूटोरियल === | === ट्यूटोरियल === | ||
* [https://www2.econ.iastate.edu/tesfatsi/holland.gaintro.htm जेनेटिक एल्गोरिदम - कंप्यूटर प्रोग्राम जो ऐसे विधियों से विकसित होते हैं जो प्राकृतिक चयन के समान होते हैं, जटिल समस्याओं को समाधान कर सकते हैं, यहां तक कि उनके निर्माता भी पूरी तरह से समझ नहीं पाते हैं] एक उत्कृष्ट परिचय जॉन हॉलैंड द्वारा जीए और कैदी की दुविधा के लिए एक आवेदन के साथ | * [https://www2.econ.iastate.edu/tesfatsi/holland.gaintro.htm जेनेटिक एल्गोरिदम - कंप्यूटर प्रोग्राम जो ऐसे विधियों से विकसित होते हैं जो प्राकृतिक चयन के समान होते हैं, जटिल समस्याओं को समाधान कर सकते हैं, यहां तक कि उनके निर्माता भी पूरी तरह से समझ नहीं पाते हैं] एक उत्कृष्ट परिचय जॉन हॉलैंड द्वारा जीए और कैदी की दुविधा के लिए एक आवेदन के साथ | ||
* [http://www.i4ai.org/EA-demo/ GA कैसे काम करता है इसका अभ्यास करने या सीखने के लिए पाठक के लिए एक ऑनलाइन इंटरैक्टिव जेनेटिक एल्गोरिदम ट्यूटोरियल]: चरण दर चरण सीखें या बैच में वैश्विक अभिसरण देखें, जनसंख्या का आकार बदलें , | * [http://www.i4ai.org/EA-demo/ GA कैसे काम करता है इसका अभ्यास करने या सीखने के लिए पाठक के लिए एक ऑनलाइन इंटरैक्टिव जेनेटिक एल्गोरिदम ट्यूटोरियल]: चरण दर चरण सीखें या बैच में वैश्विक अभिसरण देखें, जनसंख्या का आकार बदलें , पारगमन दर / सीमा, उत्परिवर्तन दर / सीमा और चयन तंत्र, और बाधाएं जोड़ें। | ||
* [https://web.archive.org/web/20130615042000/http://samizdat.mines.edu/ga_tutorial/ga_tutorial.ps डैरेल व्हिटली कंप्यूटर साइंस डिपार्टमेंट कोलोराडो स्टेट यूनिवर्सिटी द्वारा एक जेनेटिक एल्गोरिथम ट्यूटोरियल] बहुत कुछ के साथ एक उत्कृष्ट ट्यूटोरियल लिखित | * [https://web.archive.org/web/20130615042000/http://samizdat.mines.edu/ga_tutorial/ga_tutorial.ps डैरेल व्हिटली कंप्यूटर साइंस डिपार्टमेंट कोलोराडो स्टेट यूनिवर्सिटी द्वारा एक जेनेटिक एल्गोरिथम ट्यूटोरियल] बहुत कुछ के साथ एक उत्कृष्ट ट्यूटोरियल लिखित | ||
* [http://cs.gmu.edu/~sean/book/metaheuristics/ Essentials of Metaheuristics ], 2009 (225 p)। सीन ल्यूक द्वारा मुक्त खुला पाठ। | * [http://cs.gmu.edu/~sean/book/metaheuristics/ Essentials of Metaheuristics ], 2009 (225 p)। सीन ल्यूक द्वारा मुक्त खुला पाठ। | ||
| Line 271: | Line 266: | ||
एसवी: जेनेटिक प्रोग्रामिंग # जेनेटिक एल्गोरिथम | एसवी: जेनेटिक प्रोग्रामिंग # जेनेटिक एल्गोरिथम | ||
[[Category:All articles lacking reliable references|Genetic Algorithm]] | |||
[[Category: | [[Category:All articles with self-published sources|Genetic Algorithm]] | ||
[[Category:Created On 13/02/2023]] | [[Category:All articles with unsourced statements|Genetic Algorithm]] | ||
[[Category:Articles lacking reliable references from January 2021|Genetic Algorithm]] | |||
[[Category:Articles with hatnote templates targeting a nonexistent page|Genetic Algorithm]] | |||
[[Category:Articles with self-published sources from February 2020|Genetic Algorithm]] | |||
[[Category:Articles with unsourced statements from December 2011|Genetic Algorithm]] | |||
[[Category:Articles with unsourced statements from December 2020|Genetic Algorithm]] | |||
[[Category:Articles with unsourced statements from July 2016|Genetic Algorithm]] | |||
[[Category:Articles with unsourced statements from November 2019|Genetic Algorithm]] | |||
[[Category:CS1 English-language sources (en)]] | |||
[[Category:CS1 errors]] | |||
[[Category:Created On 13/02/2023|Genetic Algorithm]] | |||
[[Category:Lua-based templates|Genetic Algorithm]] | |||
[[Category:Machine Translated Page|Genetic Algorithm]] | |||
[[Category:Pages with script errors|Genetic Algorithm]] | |||
[[Category:Short description with empty Wikidata description|Genetic Algorithm]] | |||
[[Category:Templates Vigyan Ready|Genetic Algorithm]] | |||
[[Category:Templates that add a tracking category|Genetic Algorithm]] | |||
[[Category:Templates that generate short descriptions|Genetic Algorithm]] | |||
[[Category:Templates using TemplateData|Genetic Algorithm]] | |||
[[Category:Webarchive template wayback links]] | |||
Latest revision as of 10:17, 24 February 2023
2006 नासा अंतरिक्ष प्रौद्योगिकी 5 अंतरिक्ष यान एंटीना। यह जटिल आकार एक विकासवादी कंप्यूटर डिजाइन प्रोग्राम द्वारा सर्वोत्तम विकिरण पैटर्न बनाने के लिए पाया गया था। इसे एक विकसित एंटीना के रूप में जाना जाता है।
कंप्यूटर विज्ञान और संचालन अनुसंधान में, एक आनुवंशिक एल्गोरिथम (जीए) प्राकृतिक चयन की प्रक्रिया से प्रेरित एक मेटाह्यूरिस्टिक है जो विकासवादी एल्गोरिदम (ईए) के बड़े वर्ग से संबंधित है। उत्परिवर्तन (जेनेटिक एल्गोरिथम), पारगमन (जेनेटिक एल्गोरिथम) और चयन (जेनेटिक एल्गोरिथम) जैसे जैविक रूप से प्रेरित प्रचालक पर विश्वाश करके अनुकूलन (गणित) और खोज एल्गोरिदम के उच्च-गुणवत्ता वाले समाधान उत्पन्न करने के लिए जेनेटिक एल्गोरिदम का सामान्यतः उपयोग किया जाता है।[1] जीए अनुप्रयोगों के कुछ उदाहरणों में उत्तम प्रदर्शन के लिए, सुडोकू पहेलियों को समाधान करने के लिये निर्णयावली का अनुकूलन,[2] हाइपरपैरामीटर अनुकूलन, आदि सम्मिलित हैं।
कार्यप्रणाली
अनुकूलन समस्याएं
एक आनुवंशिक एल्गोरिथम में, अनुकूलन समस्या के लिए उम्मीदवार समाधान (जिन्हें व्यक्ति, जीव, जीव, या लक्षणप्ररूप कहा जाता है) की सरंध्रता उत्तम समाधान की ओर विकसित होती है। प्रत्येक उम्मीदवार समाधान में गुणों का एक सेट होता है (इसके गुणसूत्र या जीनोटाइप) जिन्हें उत्परिवर्तित और परिवर्तित किया जा सकता है; परंपरागत रूप से, समाधान 0s और 1s की स्ट्रिंग्स के रूप में बाइनरी में प्रस्तुत किए जाते हैं, किन्तु अन्य कोडलेखन भी संभव हैं।[3]
विकास सामान्यतः अव्यवस्थित रूप से उत्पन्न व्यक्तियों की सरंध्रता से प्रारंभ होता है, और प्रत्येक पुनरावृत्ति में जनसंख्या के साथ एक पुनरावृत्त प्रक्रिया होती है जिसे एक पीढ़ी कहा जाता है। प्रत्येक पीढ़ी में, जनसंख्या में प्रत्येक व्यक्ति की उपयुक्तता (जीव विज्ञान) का मूल्यांकन किया जाता है; उपयुक्तता सामान्यतः पर अनुकूलन समस्या में उद्देश्य फलन का मान का समाधान किया जा रहा है। अधिक फिट व्यक्तियों को वर्तमान सरंध्रता से यादृच्छिक रूप से चुना जाता है और प्रत्येक व्यक्ति के जीनोम को एक नई पीढ़ी बनाने के लिए संशोधित (पुन: संयोजित और संभवतः यादृच्छिक रूप से उत्परिवर्तित) किया जाता है। नई पीढ़ी के उम्मीदवार समाधानों का उपयोग कलन विधि के अगले पुनरावृत्ति में किया जाता है। सामान्यतः, एल्गोरिथ्म समाप्त हो जाता है जब या तो अधिकतम पीढ़ियों का उत्पादन किया जाता है, या जनसंख्या के लिए एक संतोषजनक उपयुक्तता स्तर तक पहुंच जाता है।
एक विशिष्ट आनुवंशिक एल्गोरिथम की आवश्यकता होती है:
- समाधान डोमेन का एक आनुवंशिक प्रतिनिधित्व,
- समाधान डोमेन का मूल्यांकन करने के लिए एक उपयुक्तता कार्य
प्रत्येक उम्मीदवार समाधान का एक मानक प्रतिनिधित्व एक बिट सरणी (जिसे बिट सेट या बिट स्ट्रिंग भी कहा जाता है) के रूप में होता है।[3] अन्य प्रकार की सरणियों और संरचनाओं का अनिवार्य रूप से उसी प्रकार उपयोग किया जा सकता है। मुख्य गुण जो इन आनुवंशिक अभ्यावेदन को सुविधाजनक बनाती है, वह यह है कि उनके हिस्से उनके निश्चित आकार के कारण आसानी से संरेखित होते हैं, जो सरल पारगमन (आनुवांशिक एल्गोरिथम) संचालन की सुविधा प्रदान करता है। परिवर्तनीय लंबाई के प्रतिनिधित्व का भी उपयोग किया जा सकता है, किन्तु इस स्थितियों में पारगमन कार्यान्वयन अधिक जटिल है। आनुवंशिक प्रोग्रामिंग में ट्री-लाइक प्रतिनिधित्व का पता लगाया जाता है और विकासवादी प्रोग्रामिंग में आरेख-प्रपत्र प्रतिनिधित्व का पता लगाया जाता है; जीन अभिव्यक्ति प्रोग्रामिंग में रैखिक गुणसूत्रों और पेड़ों दोनों के मिश्रण का पता लगाया जाता है।
एक बार आनुवंशिक प्रतिनिधित्व और उपयुक्तता फलन परिभाषित हो जाने के बाद, एक जीए समाधानों की सरंध्रता को प्रारंभ करने के लिए आगे बढ़ता है और फिर उत्परिवर्तन, पारगमन, उलटा और चयन प्रचालक के दोहराव वाले आवेदन के माध्यम से इसे सुधारता है।
प्रारंभ
जनसंख्या का आकार समस्या की प्रकृति पर निर्भर करता है, किन्तु सामान्यतः कई सैकड़ों या हजारों संभावित समाधान होते हैं। प्राय: प्रारंभिक जनसंख्या अव्यवस्थित रूप से उत्पन्न होती है, जिससे संभावित समाधानों की पूरी श्रृंखला (संभव क्षेत्र) की अनुमति मिलती है। कभी-कभी, समाधान उन क्षेत्रों में लगाए जा सकते हैं जहां इष्टतम समाधान मिलने की संभावना है।
चयन
प्रत्येक क्रमिक पीढ़ी के समय, वर्तमान सरंध्रता का एक हिस्सा एक नई पीढ़ी के प्रजनन के लिए चयन (आनुवांशिक एल्गोरिथम) होता है। एक उपयुक्तता-आधारित प्रक्रिया के माध्यम से व्यक्तिगत समाधानों का चयन किया जाता है, जहां उपयुक्तता (जीव विज्ञान) समाधान (जैसा कि एक उपयुक्तता फलन द्वारा मापा जाता है) सामान्यतः चुने जाने की अधिक संभावना होती है। कुछ चयन विधियां प्रत्येक समाधान की उपयुक्तता को रेट करती हैं और अधिमानतः सर्वोत्तम समाधानों का चयन करती हैं। अन्य विधियाँ जनसंख्या के केवल एक यादृच्छिक मानकों का मूल्यांकन करती हैं, क्योंकि पूर्व प्रक्रिया बहुत समय लेने वाली हो सकती है।
उपयुक्तता फलन को आनुवंशिक प्रतिनिधित्व पर परिभाषित किया गया है और प्रतिनिधित्व किए गए समाधान की गुणवत्ता को मापता है। उपयुक्तता फलन हमेशा समस्या पर निर्भर होता है। उदाहरण के लिए, थैला समस्या में व्यक्ति उन वस्तुओं के कुल मान को अधिकतम करना चाहता है जिन्हें किसी निश्चित क्षमता के थैले में रखा जा सकता है। एक समाधान का प्रतिनिधित्व बिट्स की एक सरणी हो सकता है, जहां प्रत्येक बिट एक अलग वस्तु का प्रतिनिधित्व करता है, और बिट का मान (0 या 1) दर्शाता है कि वस्तु नैपसैक में है या नहीं। ऐसा हर प्रतिनिधित्व मान्य नहीं है, क्योंकि वस्तुओं का आकार थैला की क्षमता से अधिक हो सकता है। यदि निरूपण वैध है, या अन्यथा 0 है, तो समाधान की उपयुक्तता थैला में सभी वस्तुओं के मानों का योग है।
कुछ समस्याओं में, उपयुक्तता अभिव्यक्ति को परिभाषित करना कठिन या असंभव भी है; इन स्थितियों में, एक लक्षणप्ररूप के उपयुक्तता फलन मान को निर्धारित करने के लिए एक कंप्यूटर अनुकरण का उपयोग किया जा सकता है (उदाहरण के लिए कम्प्यूटेशनल द्रव गतिकी का उपयोग वाहन के वायु प्रतिरोध को निर्धारित करने के लिए किया जाता है जिसका आकार लक्षणप्ररूप के रूप में एन्कोड किया गया है), या यहां तक कि पारस्परिक विकासवादी संगणना का उपयोग किया जाता है .
जेनेटिक ऑपरेटर
अगला चरण आनुवंशिक ऑपरेटर पारगमन (जिसे पुनर्संयोजन भी कहा जाता है) और उत्परिवर्तन के संयोजन के माध्यम से चुने गए लोगों से समाधान की दूसरी पीढ़ी की सरंध्रता उत्पन्न करना है।
उत्पादित किए जाने वाले प्रत्येक नए समाधान के लिए, पहले से चयनित पूल से प्रजनन के लिए मूल समाधानों की एक जोड़ी का चयन किया जाता है। पारगमन और उत्परिवर्तन के उपरोक्त विधियों का उपयोग करके एक चाइल्ड समाधान तैयार करके, एक नया समाधान तैयार किया जाता है जो सामान्यतः अपने माता-पिता की कई विशेषताओं को साझा करता है। प्रत्येक नए बच्चे के लिए नए माता-पिता का चयन किया जाता है, और यह प्रक्रिया तब तक जारी रहती है जब तक कि उपयुक्त आकार के समाधानों की एक नई सरंध्रता उत्पन्न नहीं हो जाती है।
यद्यपि प्रजनन के विधियों जो दो माता-पिता के उपयोग पर आधारित हैं, अधिक जीव विज्ञान से प्रेरित हैं, कुछ शोध[4][5] सुझाव देता है कि दो से अधिक माता-पिता उच्च गुणवत्ता वाले गुणसूत्र उत्पन्न करते हैं।
इन प्रक्रियाओं के परिणामस्वरूप अंततः अगली पीढ़ी के गुणसूत्रों की सरंध्रता होती है जो प्रारंभिक पीढ़ी से अलग होती है। सामान्यतः, सरंध्रता के लिए इस प्रक्रिया से औसत उपयुक्तता में वृद्धि होगी, क्योंकि पहली पीढ़ी के केवल सबसे अच्छे जीवों को कम फिट समाधानों के एक छोटे अनुपात के साथ प्रजनन के लिए चुना जाता है। ये कम फिट समाधान माता-पिता के आनुवंशिक पूल के अन्दर आनुवंशिक विविधता सुनिश्चित करते हैं और इसलिए बाद की पीढ़ी के बच्चों की आनुवंशिक विविधता सुनिश्चित करते हैं।
पारगमन बनाम उत्परिवर्तन के महत्व पर राय बंटी हुई है। डेविड बी फोगेल (2006) में कई संदर्भ हैं जो उत्परिवर्तन-आधारित खोज के महत्व का समर्थन करते हैं।
चूंकि पारगमन और उत्परिवर्तन को मुख्य जेनेटिक ऑपरेटर के रूप में जाना जाता है, फिर भी जेनेटिक एल्गोरिदम में रीग्रुपिंग, कॉलोनाइजेशन-विलुप्त होने या माइग्रेशन जैसे अन्य प्रचालक का उपयोग करना संभव है।[citation needed]
समस्या वर्ग के लिए उचित सेटिंग्स खोजने के लिए उत्परिवर्तन (आनुवांशिक एल्गोरिदम) संभावना, पारगमन (जेनेटिक एल्गोरिदम) संभावना और जनसंख्या आकार जैसे ट्यूनिंग पैरामीटर के लायक है। बहुत कम उत्परिवर्तन दर से आनुवंशिक बहाव हो सकता है (जो प्रकृति में गैर-एर्गोडिसिटी है)। एक पुनर्संयोजन दर जो बहुत अधिक है, आनुवंशिक एल्गोरिथम के समय से पहले अभिसरण का कारण बन सकती है। एक उत्परिवर्तन दर जो बहुत अधिक है, अच्छे समाधानों के हानि का कारण बन सकती है, जब तक कि उत्कृष्टता कार्यरत न हो। एक पर्याप्त जनसंख्या आकार हाथ में समस्या के लिए पर्याप्त आनुवंशिक विविधता सुनिश्चित करता है, किन्तु आवश्यकता से अधिक मूल्य पर सेट होने पर कम्प्यूटेशनल संसाधनों की पतन हो सकती है।
आंकलन
ऊपर दिए गए मुख्य प्रचालक के अतिरिक्त, गणना को तेज या अधिक शक्तिशाली बनाने के लिए अन्य अनुमानों को नियोजित किया जा सकता है। परिकल्पना अनुमानवादी उम्मीदवार समाधानों के बीच पारगमन को दंडित करता है जो बहुत समान हैं; यह जनसंख्या विविधता को प्रोत्साहित करता है और कम इष्टतम समाधान के लिए समय से पहले अभिसरण (विकासवादी कंप्यूटिंग) को रोकने में सहायता करता है।[6][7]
समाप्ति
समाप्ति की स्थिति तक पहुंचने तक यह पीढ़ीगत प्रक्रिया दोहराई जाती है। सामान्य समाप्ति की स्थिति हैं:
- एक समाधान पाया जाता है जो न्यूनतम मानदंडों को पूरा करता है।
- पीढ़ियों की निश्चित संख्या पहुँची है।
- आवंटित बजट (गणना समय/पैसा) पहुंच गया है।
- उच्चतम रैंकिंग समाधान की उपयुक्तता पहुँच रही है या एक पठार पर पहुँच गई है जैसे कि क्रमिक पुनरावृत्तियाँ अब उत्तम परिणाम नहीं देती है।
- स्वतः निरीक्षण
- उपरोक्त का संयोजन
रचक खंड परिकल्पना
जेनेटिक एल्गोरिदम को प्रायुक्त करना आसान है, किन्तु उनके व्यवहार को समझना कठिन है। विशेष रूप से, यह समझना कठिन है कि व्यावहारिक समस्याओं पर प्रायुक्त होने पर ये एल्गोरिदम अधिकांश उच्च उपयुक्तता के समाधान उत्पन्न करने में क्यों सफल होते हैं। रचक खंड परिकल्पना (बीबीएच) में सम्मिलित हैं:
- एक अनुमानी का विवरण जो रचक खण्डों की पहचान और पुनर्संयोजन करके अनुकूलन करता है, अर्थात् कम क्रम, कम परिभाषित-लंबाई वाली स्कीमा (आनुवांशिक एल्गोरिदम) ऊपर औसत उपयुक्तता के साथ।
- एक परिकल्पना कि एक आनुवंशिक एल्गोरिथम इस अनुमानी को स्पष्ट रूप से और कुशलता से प्रायुक्त करके अनुकूलन करता है।
गोल्डबर्ग अनुमानी का वर्णन इस प्रकार करते हैं:
- कम, लो ऑर्डर, और अत्यधिक फिट स्कीमाटा का मानक लिया जाता है, पारगमन (जेनेटिक एल्गोरिथम) [क्रॉस ओवर], और संभावित उच्च उपयुक्तता के तार बनाने के लिए फिर से तैयार किया जाता है। एक प्रकार से, इन विशेष स्कीमाटा [रचक खण्डों] के साथ काम करके, हमने अपनी समस्या की जटिलता को कम किया है; प्रत्येक बोधगम्य संयोजन की कोशिश करके उच्च-प्रदर्शन स्ट्रिंग्स बनाने के अतिरिक्त, हम पिछले मानकों के सर्वोत्तम आंशिक समाधानों से उत्तम और उत्तम स्ट्रिंग्स का निर्माण करते हैं।
- क्योंकि कम परिभाषित लंबाई और निम्न क्रम के अत्यधिक फिट स्कीमाटा आनुवंशिक एल्गोरिदम की कार्रवाई में इतनी महत्वपूर्ण भूमिका निभाते हैं, हमने उन्हें पहले से ही एक विशेष नाम दिया है: रचक खण्डों। जिस प्रकार एक बच्चा लकड़ी के साधारण ब्लॉकों की व्यवस्था के माध्यम से शानदार किले बनाता है, उसी प्रकार एक आनुवंशिक एल्गोरिथ्म शॉर्ट, लो-ऑर्डर, हाई-परप्रपत्रेंस स्कीमाटा, या रचक खण्डों के संयोजन के माध्यम से इष्टतम प्रदर्शन की तलाश करता है।[8]
बिल्डिंग-ब्लॉक परिकल्पना की वैधता के संबंध में सामान्य सहमति की कमी के अतिरिक्त, इसका लगातार मूल्यांकन किया गया है और पूरे वर्षों में संदर्भ के रूप में इसका उपयोग किया गया है। वितरण एल्गोरिदम के कई अनुमान, उदाहरण के लिए, एक वातावरण प्रदान करने के प्रयास में प्रस्तावित किए गए हैं जिसमें परिकल्पना मान्य होगी।[9][10] चूंकि समस्याओं के कुछ वर्गों के लिए अच्छे परिणाम बताए गए हैं, जीए दक्षता के स्पष्टीकरण के रूप में बिल्डिंग-ब्लॉक परिकल्पना की विस्तृतता और/या व्यावहारिकता के संबंध में संदेह अभी भी बना हुआ है। वास्तविक में, वितरण एल्गोरिदम के अनुमान के परिप्रेक्ष्य से इसकी सीमाओं को समझने का प्रयास करने के लिए एक उचित मात्रा में काम है।[11][12][13]
सीमाएं
वैकल्पिक अनुकूलन एल्गोरिदम की तुलना में आनुवंशिक एल्गोरिथम के उपयोग की सीमाएँ हैं:
- जटिल समस्याओं के लिए बार-बार उपयुक्तता फलन का मूल्यांकन अधिकांश कृत्रिम विकासवादी एल्गोरिदम का सबसे निषेधात्मक और सीमित खंड होता है। जटिल उच्च-आयामी, बहुआयामी समस्याओं का इष्टतम समाधान खोजने के लिए अधिकांश बहुत महंगे उपयुक्तता फलन मूल्यांकन की आवश्यकता होती है। वास्तविक संसार की समस्याओं जैसे संरचनात्मक अनुकूलन समस्याओं में, एक एकल कार्य मूल्यांकन के लिए कई घंटों से लेकर कई दिनों तक पूर्ण अनुकरण की आवश्यकता हो सकती है। विशिष्ट अनुकूलन विधियाँ इस प्रकार की समस्या से नहीं निपट सकती हैं। इस स्थितियों में, एक त्रुटिहीन मूल्यांकन छोड़ना और एक उपयुक्तता सन्निकटन का उपयोग करना आवश्यक हो सकता है जो कम्प्यूटेशनल रूप से कुशल है। यह स्पष्ट है कि जटिल वास्तविक जीवन की समस्याओं को समाधान करने के लिए जीए का उपयोग करने के लिए उपयुक्तता सन्निकटन का समामेलन सबसे आशाजनक दृष्टिकोणों में से एक हो सकता है।
- जेनेटिक एल्गोरिदम जटिलता के साथ अच्छी तरह से स्केल नहीं करते हैं। यही है, जहां उत्परिवर्तन के संपर्क में आने वाले तत्वों की संख्या बड़ी है, वहां अधिकांश खोज स्थान के आकार में घातीय वृद्धि होती है। इससे इंजन, घर या विमान को डिजाइन करने जैसी समस्याओं पर तकनीक का उपयोग करना अधिक कठिन हो जाता है।[citation needed] विकासवादी खोज के लिए ऐसी समस्याओं को सुगम बनाने के लिए, उन्हें यथासंभव सरलतम प्रतिनिधित्व में विभाजित किया जाना चाहिए। इसलिए हम सामान्यतः विकासवादी एल्गोरिदम को इंजनों के अतिरिक्त पंखे के ब्लेड के लिए एन्कोडिंग डिज़ाइन देखते हैं, विस्तृत निर्माण योजनाओं और पूरे विमान डिज़ाइनों के अतिरिक्त एयरफ़ोइल के अतिरिक्त आकृतियों का निर्माण करते हैं। जटिलता की दूसरी समस्या यह है कि आगे विनाशकारी उत्परिवर्तन से अच्छे समाधान का प्रतिनिधित्व करने के लिए विकसित किए गए भागों की रक्षा कैसे की जाए, विशेषतः जब उनके उपयुक्तता मूल्यांकन के लिए उन्हें अन्य भागों के साथ अच्छी तरह से संयोजित करने की आवश्यकता होती है।
- अन्य समाधानों की तुलना में ही उत्तम समाधान है। परिणामस्वरूप, रोक मानदंड हर समस्या में स्पष्ट नहीं है।
- कई समस्याओं में, जीए में समस्या के वैश्विक इष्टतम के अतिरिक्त स्थानीय इष्टतम या यहाँ तक कि स्वैच्छिक बिंदुओं की ओर अभिसरण करने की प्रवृत्ति होती है। इसका अर्थ यह है कि यह लंबी अवधि की उपयुक्तता प्राप्त करने के लिए अल्पकालिक उपयुक्तता का त्याग करना नहीं जानता है। ऐसा होने की संभावना उपयुक्तता परिदृश्य के आकार पर निर्भर करती है: कुछ समस्याएं वैश्विक इष्टतम की ओर एक आसान चढ़ाई प्रदान कर सकती हैं, अन्य कार्य के लिए स्थानीय ऑप्टिमा को ढूंढना आसान बना सकती हैं। इस समस्या को एक अलग उपयुक्तता फलन का उपयोग करके, उत्परिवर्तन की दर में वृद्धि करके, या चयन तकनीकों का उपयोग करके समाधान किया जा सकता है जो समाधान की विविध सरंध्रता को बनाए रखता है,[14] चूंकि खोज और अनुकूलन में कोई मुफ्त लंच नहीं[15] सिद्ध करता है कि इस समस्या का कोई सामान्य समाधान नहीं है। विविधता को बनाए रखने के लिए एक सामान्य तकनीक एक आला दंड लगाना है, जिसमें, पर्याप्त समानता वाले व्यक्तियों के किसी भी समूह (आला त्रिज्या) में एक दंड जोड़ा जाता है, जो बाद की पीढ़ियों में उस समूह के प्रतिनिधित्व को कम कर देगा, अन्य (कम समान) व्यक्तियों को अनुमति देगा जनसंख्या में बनाए रखना है। चूँकि, समस्या के परिदृश्य के आधार पर, यह तरकीब प्रभावी नहीं हो सकती है। एक अन्य संभावित तकनीक जनसंख्या के हिस्से को अव्यवस्थित रूप से उत्पन्न व्यक्तियों के साथ बदलना होगा, जब अधिकांश सरंध्रता एक-दूसरे के समान होती है। आनुवंशिक एल्गोरिदम (और आनुवंशिक प्रोग्रामिंग) में विविधता महत्वपूर्ण है क्योंकि एक सजातीय सरंध्रता को पार करने से नए समाधान नहीं मिलते हैं। उत्क्रांति रणनीति और विकासवादी प्रोग्रामिंग में, उत्परिवर्तन पर अधिक निर्भरता के कारण विविधता आवश्यक नहीं है।
- डायनेमिक समुच्चय सेट पर काम करना कठिन है, क्योंकि जीनोम जल्दी समाधान की ओर अभिसरण करना प्रारंभ कर देते हैं जो बाद के समुच्चय के लिए मान्य नहीं हो सकता है। आनुवंशिक विविधता को किसी प्रकार बढ़ाकर और प्रारंभिक अभिसरण को रोककर, समाधान की गुणवत्ता में गिरावट आने पर उत्परिवर्तन की संभावना को बढ़ाकर (ट्रिगर हाइपरउत्परिवर्तन कहा जाता है), या कभी-कभी जीन पूल में पूरी तरह से नए, अव्यवस्थित रूप से उत्पन्न तत्वों को प्रस्तुत करके इसे दूर करने के लिए कई विधियों प्रस्तावित किए गए हैं। (यादृच्छिक आप्रवासी कहा जाता है)। फिर से, विकास रणनीति और विकासवादी प्रोग्रामिंग को एक तथाकथित अल्पविराम रणनीति के साथ प्रायुक्त किया जा सकता है जिसमें माता-पिता का रखरखाव नहीं किया जाता है और नए माता-पिता केवल संतानों में से चुने जाते हैं। यह गतिशील समस्याओं पर अधिक प्रभावी हो सकता है।
- जीए उन समस्याओं को प्रभावी रूप से समाधान नहीं कर सकते हैं जिनमें एकमात्र उपयुक्तता उपाय एक सही/गलत उपाय है (जैसे निर्णय समस्याएं), क्योंकि समाधान पर अभिसरण करने का कोई विधि नहीं है (चढ़ने के लिए कोई पहाड़ी नहीं)। इन स्थितियों में, यादृच्छिक खोज से जीए जितनी जल्दी समाधान मिल सकता है। चूँकि, यदि स्थिति सफलता/असफलता परीक्षण को अलग-अलग परिणाम देने (संभवतः) देने की अनुमति देती है, तो सफलताओं से असफलताओं का अनुपात एक उपयुक्त उपयुक्तता उपाय प्रदान करता है।
- विशिष्ट अनुकूलन समस्याओं और समस्या उदाहरणों के लिए, अभिसरण की गति के संदर्भ में अन्य अनुकूलन एल्गोरिदम आनुवंशिक एल्गोरिदम की तुलना में अधिक कुशल हो सकते हैं। वैकल्पिक और पूरक एल्गोरिदम में विकास रणनीति, विकासवादी प्रोग्रामिंग, तैयार किए हुयी धातु पे पानी चढाने की कला, गॉसियन अनुकूलन, पहाड़ी चढ़ाई, और झुंड खुफिया (जैसे: चींटी कॉलोनी अनुकूलन, कण झुंड अनुकूलन) और पूर्णांक रैखिक प्रोग्रामिंग पर आधारित विधियों सम्मिलित हैं। आनुवंशिक एल्गोरिदम की उपयुक्तता समस्या के ज्ञान की मात्रा पर निर्भर करती है; प्रसिद्ध समस्याओं में अधिकांश उत्तम, अधिक विशिष्ट दृष्टिकोण होते हैं।
प्रकार
गुणसूत्र प्रतिनिधित्व
सबसे सरल एल्गोरिथ्म प्रत्येक गुणसूत्र को बिट सरणी के रूप में दर्शाता है। सामान्यतः, संख्यात्मक मापदंडों को पूर्णांकों द्वारा दर्शाया जा सकता है, चूंकि तैरनेवाला स्थल अभ्यावेदन का उपयोग करना संभव है। इवोल्यूशन रणनीति और विकासवादी प्रोग्रामिंग के लिए फ्लोटिंग पॉइंट प्रतिनिधित्व स्वाभाविक है। वास्तविक-मूल्यवान आनुवंशिक एल्गोरिदम की धारणा की प्रस्तुति की गई है किन्तु वास्तव में एक मिथ्या नाम है क्योंकि यह वास्तव में रचक खंड सिद्धांत का प्रतिनिधित्व नहीं करता है जो 1970 के दशक में जॉन हेनरी हॉलैंड द्वारा प्रस्तावित किया गया था। सैद्धांतिक और प्रयोगात्मक परिणामों (नीचे देखें) के आधार पर, चूंकि यह सिद्धांत समर्थन के बिना नहीं है। मूलभूत एल्गोरिथ्म बिट स्तर पर पारगमन और उत्परिवर्तन करता है। अन्य वेरिएंट क्रोमोसोम को संख्याओं की एक सूची के रूप में मानते हैं जो एक निर्देश तालिका, एक लिंक की गई सूची में नोड्स, साहचर्य सरणी, वस्तु (कंप्यूटर विज्ञान), या कोई अन्य कल्पनीय समुच्चय संरचना में अनुक्रमित होते हैं। समुच्चय तत्व सीमाओं का सम्मान करने के लिए पारगमन और उत्परिवर्तन किया जाता है। अधिकांश समुच्चय प्रकारों के लिए, विशिष्ट भिन्नता प्रचालक को डिज़ाइन किया जा सकता है। अलग-अलग विशिष्ट समस्या डोमेन के लिए अलग-अलग क्रोमोसोमल समुच्चय प्रकार उत्तम या बदतर काम करते हैं।
जब पूर्णांकों के बिट-स्ट्रिंग अभ्यावेदन का उपयोग किया जाता है, तो ग्रे कोडिंग को अधिकांश नियोजित किया जाता है। इस प्रकार, पूर्णांक में छोटे बदलाव उत्परिवर्तन या पारगमन के माध्यम से आसानी से प्रभावित हो सकते हैं। यह तथाकथित हैमिंग दीवारों पर समयपूर्व अभिसरण को रोकने में सहायता करने के लिए पाया गया है, जिसमें क्रोमोसोम को उत्तम समाधान में बदलने के लिए एक साथ कई उत्परिवर्तन (या पारगमन घटनाएं) होनी चाहिए।
अन्य दृष्टिकोणों में गुणसूत्रों का प्रतिनिधित्व करने के लिए बिट स्ट्रिंग्स के अतिरिक्त वास्तविक-मूल्यवान संख्याओं की सरणियों का उपयोग करना सम्मिलित है। स्कीमाटा के सिद्धांत के परिणाम बताते हैं कि सामान्यतः वर्ण जितना छोटा होता है, प्रदर्शन उतना ही उत्तम होता है, किन्तु शोधकर्ताओं के लिए प्रारंभ में यह आश्चर्यजनक था कि वास्तविक-मानमूल्य वाले गुणसूत्रों का उपयोग करने से अच्छे परिणाम प्राप्त हुए। इसे क्रोमोसोम की एक परिमित सरंध्रता में वास्तविक मानों के सेट के रूप में समझाया गया था, क्योंकि फ्लोटिंग पॉइंट प्रतिनिधित्व से अपेक्षाकृत कम कार्डिनैलिटी के साथ वर्चुअल वर्णमाला (जब चयन और पुनर्मूल्यांकन प्रभावी होते हैं) बनाते हैं।[16][17] जेनेटिक एल्गोरिथम सुलभ समस्या डोमेन का विस्तार समाधान पूल के अधिक जटिल एन्कोडिंग के माध्यम से कई प्रकार के विषम एन्कोडेड जीनों को एक गुणसूत्र में जोड़कर प्राप्त किया जा सकता है।[18] यह विशेष दृष्टिकोण उन अनुकूलन समस्याओं को समाधान करने की अनुमति देता है जिनके लिए समस्या मापदंडों के लिए अत्यधिक भिन्न परिभाषा डोमेन की आवश्यकता होती है। उदाहरण के लिए, कैस्केड कंट्रोलर ट्यूनिंग की समस्याओं में, आंतरिक लूप नियंत्रक संरचना तीन मापदंडों के एक पारंपरिक नियामक से संबंधित हो सकती है, चूंकि बाहरी लूप एक भाषाई नियंत्रक (जैसे फ़ज़ी प्रणाली) को प्रायुक्त कर सकता है, जिसका एक अलग विवरण है। एन्कोडिंग के इस विशेष रूप के लिए एक विशेष पारगमन तंत्र की आवश्यकता होती है जो क्रोमोसोम को खंड द्वारा पुनर्संयोजित करता है, और यह जटिल अनुकूली प्रणालियों, विशेष रूप से विकास प्रक्रियाओं के मॉडलिंग और अनुकरण के लिए एक उपयोगी उपकरण है।
अभिजात वर्ग
एक नई सरंध्रता के निर्माण की सामान्य प्रक्रिया का एक व्यावहारिक रूप वर्तमान पीढ़ी से सर्वोत्तम जीवों को अगले, अनछुए तक ले जाने की अनुमति देना है। इस रणनीति को अभिजात्य चयन के रूप में जाना जाता है और यह गारंटी देता है कि जीए द्वारा प्राप्त समाधान की गुणवत्ता एक पीढ़ी से दूसरी पीढ़ी तक कम नहीं होगी।[19]
समानांतर कार्यान्वयन
अनुवांशिक एल्गोरिदम के समांतर एल्गोरिदम कार्यान्वयन दो स्वादों में आते हैं। मोटे-दाने वाले समानांतर आनुवंशिक एल्गोरिदम प्रत्येक कंप्यूटर नोड पर जनसंख्या और नोड्स के बीच व्यक्तियों के प्रवासन को मानते हैं। सुक्ष्म समानांतर आनुवंशिक एल्गोरिदम प्रत्येक प्रोसेसर नोड पर एक व्यक्ति को ग्रहण करते हैं जो चयन और प्रजनन के लिए पड़ोसी व्यक्तियों के साथ कार्य करता है।
अन्य प्रकार, जैसे ऑनलाइन अनुकूलन समस्याओं के लिए आनुवंशिक एल्गोरिदम, उपयुक्तता फलन में समय-निर्भरता या ध्वनी का परिचय देते हैं।
अनुकूली जीए
अनुकूली मापदंडों के साथ आनुवंशिक एल्गोरिदम (अनुकूली आनुवंशिक एल्गोरिदम, एजीएएस) आनुवंशिक एल्गोरिदम का एक और महत्वपूर्ण और आशाजनक संस्करण है। पारगमन (पीसी) और उत्परिवर्तन (अपराह्न) की संभावनाएं समाधान शुद्धता की डिग्री और अभिसरण गति को निर्धारित करती हैं जो आनुवंशिक एल्गोरिदम प्राप्त कर सकते हैं। पीसी और पीएम के निश्चित मानों का उपयोग करने के अतिरिक्त, एजीए प्रत्येक पीढ़ी में जनसंख्या की जानकारी का उपयोग करते हैं और जनसंख्या विविधता को बनाए रखने के साथ-साथ अभिसरण क्षमता को बनाए रखने के लिए पीसी और पीएम को अनुकूल रूप से समायोजित करते हैं। एजीए (अनुकूली आनुवंशिक एल्गोरिथम),[20] में पीसी और पीएम का समायोजन समाधानों के उपयुक्तता मानों पर निर्भर करता है। सीएजीए (क्लस्टरिंग-आधारित अनुकूली आनुवंशिक एल्गोरिथम) में,[21] जनसंख्या के अनुकूलन राज्यों का न्याय करने के लिए क्लस्टरिंग विश्लेषण के उपयोग के माध्यम से, पीसी और पीएम का समायोजन इन अनुकूलन राज्यों पर निर्भर करता है।
GA को अन्य अनुकूलन विधियों के साथ संयोजित करना अधिक प्रभावी हो सकता है। सामान्यतः अच्छे वैश्विक समाधान खोजने में एक जीए अधिक अच्छा होता है, किन्तु पूर्ण इष्टतम खोजने के लिए पिछले कुछ उत्परिवर्तनों को खोजने में अधिक अक्षम है। अन्य तकनीकें (जैसे पहाड़ी चढ़ाई) एक सीमित क्षेत्र में पूर्ण इष्टतम खोजने में अधिक कुशल हैं। वैकल्पिक जीए और पहाड़ी चढ़ाई की शक्तिशालीी की कमी को दूर करते हुए पहाड़ी चढ़ाई जीए की दक्षता में सुधार कर सकते हैं।[citation needed]
इसका अर्थ यह है कि प्राकृतिक स्थितियों में अनुवांशिक भिन्नता के नियमों का एक अलग अर्थ हो सकता है। उदाहरण के लिए - परन्तु चरणों को लगातार क्रम में संग्रहीत किया जाए - क्रॉसिंग ओवर मातृ डीएनए से कई चरणों का योग कर सकता है और पैतृक डीएनए से कई चरणों को जोड़ सकता है। यह उन सदिशों को जोड़ने के समान है जो लक्षणप्ररूपी भूदृश्य में एक रिज का अनुसरण कर सकते हैं। इस प्रकार, परिमाण के कई आदेशों से प्रक्रिया की दक्षता में वृद्धि हो सकती है। इसके अतिरिक्त, क्रोमोसोमल व्युत्क्रम में जीवित रहने या दक्षता के पक्ष में लगातार क्रम या किसी अन्य उपयुक्त क्रम में चरण रखने का अवसर होता है।[22]
एक भिन्नता, जहां एक पूरे के रूप में जनसंख्या अपने व्यक्तिगत सदस्यों के अतिरिक्त विकसित होती है, जीन पूल पुनर्संयोजन के रूप में जाना जाता है।
उपयुक्तता एपिस्टासिस के उच्च स्तर के साथ समस्याओं पर जीए के प्रदर्शन को उत्तम बनाने का प्रयास करने के लिए कई विविधताएं विकसित की गई हैं, अर्थात् जहां किसी समाधान की उपयुक्तता में इसके चर के अंतःक्रियात्मक सबसेट होते हैं। इस प्रकार के एल्गोरिदम का उद्देश्य इन लाभकारी लक्षणप्ररूपिक इंटरैक्शन को सीखना (शोषण करने से पहले) है। जैसे, वे विघटनकारी पुनर्संयोजन को अनुकूल रूप से कम करने में रचक खंड परिकल्पना के साथ संरेखित हैं। इस दृष्टिकोण के प्रमुख उदाहरणों में एमजीए,[23] जीईएम[24] और एलएलजीए सम्मिलित है।[25]
समस्या डोमेन
समस्याएं जो जेनेटिक एल्गोरिदम द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं उनमें जेनेटिक एल्गोरिदम शेड्यूलिंग सम्मिलित है, और कई शेड्यूलिंग सॉफ़्टवेयर पैकेज GAs पर आधारित हैं।[citation needed] जीए को अभियांत्रिकी में भी प्रायुक्त किया गया है।[26] वैश्विक अनुकूलन समस्याओं को समाधान करने के लिए आनुवंशिक एल्गोरिदम को अधिकांश एक दृष्टिकोण के रूप में प्रायुक्त किया जाता है।
थंब जेनेटिक एल्गोरिदम के एक सामान्य नियम के रूप में समस्या डोमेन में उपयोगी हो सकता है जिसमें मिश्रण के रूप में एक जटिल उपयुक्तता परिदृश्य है, अर्थात्, उत्परिवर्तन (जेनेटिक एल्गोरिदम) पारगमन (जेनेटिक एल्गोरिदम) के संयोजन में, सरंध्रता को स्थानीय ऑप्टिमा से दूर ले जाने के लिए डिज़ाइन किया गया है। एक पारंपरिक पहाड़ी चढ़ाई एल्गोरिथ्म में फंस सकता है। निरीक्षण करें कि सामान्यतः उपयोग किए जाने वाले पारगमन ऑपरेटर किसी भी समान सरंध्रता को नहीं बदल सकते हैं। अकेले उत्परिवर्तन समग्र आनुवंशिक एल्गोरिथम प्रक्रिया (मार्कोव श्रृंखला के रूप में देखा गया) की क्षुद्रता प्रदान कर सकता है।
जेनेटिक एल्गोरिदम द्वारा समाधान की गई समस्याओं के उदाहरणों में सम्मिलित हैं: सूर्य के प्रकाश को सौर संग्राहक तक पहुंचाने के लिए डिज़ाइन किए गए दर्पण,[27] अंतरिक्ष में रेडियो सिग्नल लेने के लिए डिज़ाइन किया गया एंटीना,[28] कंप्यूटर के आंकड़ों के लिए चलने के विधियों,[29] जटिल प्रवाहक्षेत्रों में वायुगतिकीय पिंडों का इष्टतम डिजाइन[30] अपने एल्गोरिथम डिज़ाइन स्वतः में, स्टीवन स्कीएना किसी भी कार्य के लिए आनुवंशिक एल्गोरिथम के विरुद्ध सलाह देता है:
[I] बिट स्ट्रिंग्स पर उत्परिवर्तन और क्रॉसओवर जैसे अनुवांशिक ऑपरेटरों के मामले में मॉडल अनुप्रयोगों के लिए काफी अप्राकृतिक है। छद्म जीव विज्ञान आपके और आपकी समस्या के बीच जटिलता का एक और स्तर जोड़ता है। दूसरा, अनुवांशिक एल्गोरिदम गैर-तुच्छ समस्याओं पर बहुत लंबा समय लेते हैं। [...] [टी] वह विकास के साथ सादृश्य-जहां महत्वपूर्ण प्रगति की आवश्यकता है [एसआईसी] लाखों साल-काफी उपयुक्त हो सकता है।
[...]
मुझे कभी भी किसी समस्या का सामना नहीं करना पड़ा जहां जेनेटिक एल्गोरिदम मुझे इस पर हमला करने का सही तरीका लगा। इसके अलावा, मैंने जेनेटिक एल्गोरिदम का उपयोग करके रिपोर्ट किए गए किसी भी कम्प्यूटेशनल परिणाम को कभी नहीं देखा है जिसने मुझे अनुकूल रूप से प्रभावित किया हो। अपनी अनुमानी खोज वूडू आवश्यकताओं के लिए नकली एनीलिंग पर टिके रहें।
— Steven Skiena[31]: 267
इतिहास
1950 में, एलन ट्यूरिंग ने एक सीखने की मशीन प्रस्तावित की जो विकास के सिद्धांतों के समानांतर होगी।[32] विकास का कंप्यूटर सिमुलेशन 1954 में निल्स ऑल बरीज़ के काम से प्रारंभ हुआ, जो प्रिंसटन, न्यू जर्सी में उन्नत अध्ययन संस्थान में कंप्यूटर का उपयोग कर रहे थे।
वाणिज्यिक उत्पाद
1980 के दशक के अंत में, जनरल इलेक्ट्रिक ने संसार का पहला जेनेटिक एल्गोरिथम उत्पाद बेचना प्रारंभ किया, जो औद्योगिक प्रक्रियाओं के लिए डिज़ाइन किया गया एक मेनफ्रेम-आधारित टूलकिट था।[33][circular reference] 1989 में, एक्सेलिस, इंक. ने डेस्कटॉप कंप्यूटरों के लिए संसार का पहला व्यावसायिक जीए उत्पाद, एवोल्वर (सॉफ्टवेयर) जारी दी न्यू यौर्क टाइम्स प्रौद्योगिकी लेखक जॉन मार्कोफ ने लिखा[34] 1990 में एवोल्वर के बारे में, और यह 1995 तक एकमात्र इंटरैक्टिव वाणिज्यिक आनुवंशिक एल्गोरिथम बना रहा।[35] Evolver को 1997 में Palisade को बेच दिया गया था, जिसका कई भाषाओं में अनुवाद किया गया, और वर्तमान में यह अपने 6वें संस्करण में है।[36] 1990 के दशक के बाद से, MATLAB ने तीन व्युत्पन्न-मुक्त अनुकूलन हेयुरिस्टिक एल्गोरिदम (नकली एनीलिंग, कण झुंड अनुकूलन, आनुवंशिक एल्गोरिथ्म) और दो प्रत्यक्ष खोज एल्गोरिदम (सिम्प्लेक्स खोज, पैटर्न खोज) में बनाया है।[37]
संबंधित तकनीकें
मूल क्षेत्र
जेनेटिक एल्गोरिदम एक उप-क्षेत्र हैं:
- विकासवादी एल्गोरिदम
- विकासवादी कंप्यूटिंग
- मेटाह्यूरिस्टिक्स
- स्टोकेस्टिक अनुकूलन
- अनुकूलन (गणित)
संबंधित क्षेत्र
विकासवादी एल्गोरिदम
विकासवादी एल्गोरिदम विकासवादी संगणना का एक उप-क्षेत्र है।
- विकास की रणनीति (ईएस, रेचेनबर्ग, 1994 देखें) व्यक्तियों को उत्परिवर्तन और मध्यवर्ती या असतत पुनर्संयोजन के माध्यम से विकसित करती है। ईएस एल्गोरिदम विशेष रूप से वास्तविक मान डोमेन में समस्याओं को समाधान करने के लिए डिज़ाइन किए गए हैं।[38] वे खोज के नियंत्रण मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं। स्व-अनुकूलन के डी-रैंडमाइजेशन ने समकालीन सहप्रसरण मैट्रिक्स अनुकूलन विकास रणनीति (सीएमए-ईएस) को जन्म दिया है।
- विकासवादी प्रोग्रामिंग (ईपी) में मुख्य रूप से उत्परिवर्तन और चयन और स्वैछिक प्रतिनिधित्व वाले समाधानों की सरंध्रता सम्मिलित है। वे मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं, और अन्य विविधता संचालन सम्मिलित कर सकते हैं जैसे कि कई माता-पिता से जानकारी का संयोजन।
- वितरण एल्गोरिथ्म (इडीए) का अनुमान मॉडल-निर्देशित प्रचालक द्वारा पारंपरिक प्रजनन प्रचालक को प्रतिस्थापित करता है। इस प्रकार के मॉडल मशीन लर्निंग तकनीकों को नियोजित करके जनसंख्या से सीखे जाते हैं और संभाव्य चित्रात्मक प्रतिरूप के रूप में प्रस्तुत किए जाते हैं, जिनसे नए समाधानों का मानक लिया जा सकता है[39][40] या निर्देशित-पारगमन से उत्पन्न।[41]
- जेनेटिक प्रोग्रामिंग (जीपी) जॉन बकरी द्वारा लोकप्रिय एक संबंधित तकनीक है जिसमें फलन पैरामीटर के अतिरिक्त कंप्यूटर प्रोग्राम को अनुकूलित किया जाता है। जेनेटिक प्रोग्रामिंग अधिकांश ट्री (समुच्चय स्ट्रक्चर) | ट्री-आधारित आंतरिक समुच्चय स्ट्रक्चर का उपयोग करती है, जो जेनेटिक एल्गोरिदम की विशिष्ट सूची (कंप्यूटिंग) संरचनाओं के अतिरिक्त अनुकूलन के लिए कंप्यूटर प्रोग्राम का प्रतिनिधित्व करती है। कार्टेशियन जेनेटिक प्रोग्रामिंग, जीन एक्सप्रेशन प्रोग्रामिंग सहित जेनेटिक प्रोग्रामिंग के कई प्रकार हैं।[42] व्याकरणिक विकास, रैखिक आनुवंशिक प्रोग्रामिंग, बहु अभिव्यक्ति प्रोग्रामिंग आदि।
- समूहन आनुवंशिक एल्गोरिथम (जीएजीए) जीए का एक विकास है, जहां फ़ोकस को अलग-अलग आइटम से स्थानांतरित किया जाता है, जैसे क्लासिकल जीए में, समूहों या आइटम के सबसेट पर।[43] इमैनुएल फल्केनाउर द्वारा प्रस्तावित इस जीए विकास के पीछे विचार यह है कि कुछ जटिल समस्याओं को समाधान करना, जैसे कि क्लस्टरिंग या विभाजन की समस्याएं जहां वस्तुओं के एक सेट को एक इष्टतम विधियों से वस्तुओं के अलग समूह में विभाजित किया जाना चाहिए, समूहों की विशेषताओं को बनाकर उत्तम विधियों से प्राप्त किया जा सकता है। जीन के समतुल्य वस्तुओं की। इस प्रकार की समस्याओं में बिन पैकिंग की समस्या, लाइन बैलेंसिंग, दूरी माप के संबंध में क्लस्टर विश्लेषण, बराबर ढेर आदि सम्मिलित हैं, जिन पर क्लासिक जीए खराब प्रदर्शन करने वाले सिद्ध हुए। समूहों के समतुल्य जीन बनाने से तात्पर्य उन गुणसूत्रों से है जो सामान्य रूप से परिवर्तनशील लंबाई के होते हैं, और विशेष आनुवंशिक संचालक जो वस्तुओं के पूरे समूहों में हेरफेर करते हैं। विशेष रूप से बिन पैकिंग के लिए, मार्टेलो और टोथ के प्रभुत्व मानदंड के साथ संकरणित एक जीजीए यकीनन अब तक की सबसे अच्छी तकनीक है।
- पारस्परिक विकासवादी एल्गोरिदम विकासवादी एल्गोरिदम हैं जो मानव मूल्यांकन का उपयोग करते हैं। वे सामान्यतः उन डोमेन पर प्रायुक्त होते हैं जहां कम्प्यूटेशनल उपयुक्तता फलन को डिज़ाइन करना कठिन होता है, उदाहरण के लिए, छवियों, संगीत, कलात्मक डिजाइनों और रूपों को उपयोगकर्ताओं की सौंदर्य पसंद को फिट करने के लिए विकसित करना।
झुंड बुद्धि
झुंड बुद्धि विकासवादी संगणना का एक उप-क्षेत्र है।
- एंट कॉलोनी ऑप्टिमाइज़ेशन (ACO) समाधान स्थान को पार करने और स्थानीय रूप से उत्पादक क्षेत्रों को खोजने के लिए फेरोमोन मॉडल से लैस कई चींटियों (या एजेंटों) का उपयोग करता है।
- यद्यपि वितरण एल्गोरिथम का अनुमान माना जाता है,[44] कण झुंड अनुकूलन (पीएसओ) बहु-पैरामीटर अनुकूलन के लिए एक कम्प्यूटेशनल विधि है जो जनसंख्या-आधारित दृष्टिकोण का भी उपयोग करती है। उम्मीदवार समाधान (कणों) की सरंध्रता (झुंड) खोज स्थान में चलती है, और कणों की गति उनकी अपनी सर्वश्रेष्ठ ज्ञात स्थिति और झुंड की वैश्विक सर्वोत्तम ज्ञात स्थिति दोनों से प्रभावित होती है। आनुवंशिक एल्गोरिथम की प्रकार, PSO विधि जनसंख्या सदस्यों के बीच सूचना साझा करने पर निर्भर करती है। कुछ समस्याओं में पीएसओ अधिकांश कम्प्यूटेशनल रूप से जीए की तुलना में, विशेष रूप से निरंतर चर के साथ अप्रतिबंधित समस्याओं में अधिक कुशल होता है।[45]
अन्य विकासवादी कंप्यूटिंग एल्गोरिदम
विकासवादी संगणना मेटाह्यूरिस्टिक विधियों का एक उप-क्षेत्र है।
- MEME टिक एल्गोरिथम (MA), जिसे अधिकांश दूसरों के बीच हाइब्रिड जेनेटिक एल्गोरिथम कहा जाता है, एक जनसंख्या-आधारित पद्धति है जिसमें समाधान भी स्थानीय सुधार चरणों के अधीन होते हैं। मेमेटिक एल्गोरिदम का विचार मेम्स से आता है, जो जीन के विपरीत खुद को अनुकूलित कर सकते हैं। कुछ समस्या क्षेत्रों में उन्हें पारंपरिक विकासवादी एल्गोरिदम की तुलना में अधिक कुशल दिखाया गया है।
- बैक्टीरियोलॉजिकल एल्गोरिदम (बीए) विकासवादी पारिस्थितिकी और विशेष रूप से बैक्टीरियोलॉजिक अनुकूलन से प्रेरित है। विकासवादी पारिस्थितिकी जीवित जीवों का उनके पर्यावरण के संदर्भ में अध्ययन है, जिसका उद्देश्य यह पता लगाना है कि वे कैसे अनुकूलन करते हैं। इसकी मूल अवधारणा यह है कि एक विषम वातावरण में, एक व्यक्ति ऐसा नहीं होता जो पूरे वातावरण के अनुकूल हो। इसलिए, जनसंख्या स्तर पर तर्क करने की जरूरत है। यह भी माना जाता है कि बीए को जटिल पोजिशनिंग समस्याओं (सेल फोन, शहरी नियोजन, और इसी प्रकार के एंटेना) या समुच्चय माइनिंग के लिए सफलतापूर्वक प्रायुक्त किया जा सकता है।[46]
- सांस्कृतिक एल्गोरिथम (सीए) में जनसंख्या घटक सम्मिलित होता है जो लगभग आनुवंशिक एल्गोरिथम के समान होता है और इसके अतिरिक्त, एक ज्ञान घटक जिसे विश्वास स्थान कहा जाता है।
- सुपरऑर्गेनिज्म के प्रवास से प्रेरित विभेदक विकास (DE)।[47]
- गॉसियन अनुकूलन (सामान्य या प्राकृतिक अनुकूलन, जीए के साथ भ्रम से बचने के लिए संक्षिप्त एनए) सिग्नल प्रोसेसिंग प्रणाली की विनिर्माण उपज को अधिकतम करने के लिए अभिप्रेत है। इसका उपयोग साधारण पैरामीट्रिक अनुकूलन के लिए भी किया जा सकता है। यह स्वीकार्यता के सभी क्षेत्रों और सभी गाऊसी वितरणों के लिए मान्य एक निश्चित प्रमेय पर निर्भर करता है। एनए की दक्षता सूचना सिद्धांत और दक्षता के एक निश्चित प्रमेय पर निर्भर करती है। इसकी दक्षता को सूचना प्राप्त करने के लिए आवश्यक कार्य से विभाजित सूचना के रूप में परिभाषित किया गया है।[48] क्योंकि एनए व्यक्ति अर्थ उपयुक्तता के अतिरिक्त माध्य उपयुक्तता को अधिकतम करता है, परिदृश्य को इस प्रकार चिकना किया जाता है कि चोटियों के बीच की घाटियाँ गायब हो सकती हैं। इसलिए उपयुक्तता परिदृश्य में स्थानीय चोटियों से बचने की एक निश्चित महत्वाकांक्षा है। पल मैट्रिक्स के अनुकूलन द्वारा तेज शिखर पर चढ़ने में एनए भी अच्छा है, क्योंकि एनए गाऊसी के विकार (औसत जानकारी) को एक साथ औसत उपयुक्तता स्थिर रखते हुए अधिकतम कर सकता है।
अन्य मेटाह्यूरिस्टिक विधियों
मेटाह्यूरिस्टिक विधियों विस्तृत रूप से स्टोकेस्टिक ऑप्टिमाइज़ेशन ऑप्टिमाइज़ेशन विधियों के अंतर्गत आते हैं।
- सिम्युलेटेड एनीलिंग (एसए) एक संबंधित वैश्विक अनुकूलन तकनीक है जो एक व्यक्तिगत समाधान पर यादृच्छिक उत्परिवर्तन का परीक्षण करके खोज स्थान को पार करती है। उपयुक्तता बढ़ाने वाले उत्परिवर्तन को हमेशा स्वीकार किया जाता है। उपयुक्तता में अंतर और घटते तापमान पैरामीटर के आधार पर उपयुक्तता को कम करने वाले उत्परिवर्तन को संभाव्य रूप से स्वीकार किया जाता है। एसए की भाषा में, अधिकतम उपयुक्तता के अतिरिक्त सबसे कम ऊर्जा की मांग करने की बात की जाती है। एसए का उपयोग एक मानक जीए एल्गोरिथम के अन्दर उत्परिवर्तन की अपेक्षाकृत उच्च दर से प्रारंभ करके और एक निश्चित समय के साथ समय के साथ इसे कम करके भी किया जा सकता है।
- तब्बू खोज (टीएस) सिम्युलेटेड एनीलिंग के समान है जिसमें दोनों एक व्यक्तिगत समाधान के उत्परिवर्तन का परीक्षण करके समाधान स्थान को पार करते हैं। सिम्युलेटेड एनीलिंग केवल एक उत्परिवर्तित समाधान उत्पन्न करता है, टैबू खोज कई उत्परिवर्तित समाधान उत्पन्न करता है और उन समाधानों की ओर जाता है जो उत्पन्न सबसे कम ऊर्जा के साथ होते हैं। समाधान स्थान के माध्यम से चक्रण को रोकने और अधिक गति को प्रोत्साहित करने के लिए, आंशिक या पूर्ण समाधानों की एक टैबू सूची बनाए रखी जाती है। टैबू सूची के तत्वों वाले समाधान में जाने से मना किया जाता है, जिसे समाधान के रूप में अद्यतन किया जाता है, समाधान स्थान को पार करता है।
- चरम अनुकूलन (ईओ) जीए के विपरीत, जो उम्मीदवार समाधानों की सरंध्रता के साथ काम करते हैं, ईओ एक एकल समाधान विकसित करता है और सबसे खराब घटकों के लिए स्थानीय खोज (अनुकूलन) संशोधन करता है। इसके लिए आवश्यक है कि एक उपयुक्त प्रतिनिधित्व का चयन किया जाए जो व्यक्तिगत समाधान घटकों को एक गुणवत्ता माप (उपयुक्तता) असाइन करने की अनुमति देता है। इस एल्गोरिथम के पीछे शासी सिद्धांत यह है कि निम्न-गुणवत्ता वाले घटकों को उत्तम रूप से हटाकर और उन्हें अव्यवस्थित रूप से चयनित घटक के साथ बदलकर आकस्मिक सुधार किया जाता है। यह निश्चित रूप से जीए के विपरीत है जो उत्तम समाधान करने के प्रयास में अच्छे समाधानों का चयन करता है।
अन्य स्टोचैस्टिक अनुकूलन विधियाँ
- क्रॉस-एन्ट्रॉपी विधि | क्रॉस-एन्ट्रॉपी (सीई) विधि पैरामीटरयुक्त संभाव्यता वितरण के माध्यम से उम्मीदवार समाधान उत्पन्न करती है। मापदंडों को क्रॉस-एन्ट्रापी न्यूनीकरण के माध्यम से अद्यतन किया जाता है, जिससे अगले पुनरावृत्ति में उत्तम मानकों उत्पन्न किए जा सकें।
- रिएक्टिव सर्च ऑप्टिमाइज़ेशन (RSO) जटिल ऑप्टिमाइज़ेशन समस्याओं को समाधान करने के लिए उप-प्रतीकात्मक मशीन लर्निंग तकनीकों को सर्च ह्यूरिस्टिक्स में एकीकृत करने की वकालत करता है। रिएक्टिव शब्द महत्वपूर्ण मापदंडों के स्व-ट्यूनिंग के लिए आंतरिक ऑनलाइन फीडबैक लूप के माध्यम से खोज के समय घटनाओं के लिए तैयार प्रतिक्रिया पर संकेत देता है। रिएक्टिव सर्च के लिए रुचि की कार्यप्रणालियों में मशीन लर्निंग और सांख्यिकी, विशेष रूप से सुदृढीकरण सीखना, एक्टिव लर्निंग (मशीन लर्निंग), तंत्रिका नेटवर्क और मेटाह्यूरिस्टिक्स सम्मिलित हैं।
यह भी देखें
- जेनेटिक प्रोग्रामिंग
- आनुवंशिक एल्गोरिथम अनुप्रयोगों की सूची
- कण फिल्टर | सिग्नल प्रोसेसिंग में जेनेटिक एल्गोरिदम (उर्फ पार्टिकल फिल्टर)
- स्कीमा का प्रचार
- सार्वभौम डार्विनवाद
- मेटाह्यूरिस्टिक्स
- लर्निंग क्लासिफायर प्रणाली
- नियम-आधारित मशीन लर्निंग
संदर्भ
- ↑ Mitchell 1996, p. 2.
- ↑ Gerges, Firas; Zouein, Germain; Azar, Danielle (2018-03-12). "Genetic Algorithms with Local Optima Handling to Solve Sudoku Puzzles". Proceedings of the 2018 International Conference on Computing and Artificial Intelligence. ICCAI 2018. New York, NY, USA: Association for Computing Machinery: 19–22. doi:10.1145/3194452.3194463. ISBN 978-1-4503-6419-5. S2CID 44152535.
- ↑ 3.0 3.1 Whitley 1994, p. 66.
- ↑ Eiben, A. E. et al (1994). "Genetic algorithms with multi-parent recombination". PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78–87. ISBN 3-540-58484-6.
- ↑ Ting, Chuan-Kang (2005). "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403–412. ISBN 978-3-540-28848-0.
- ↑ Deb, Kalyanmoy; Spears, William M. (1997). "C6.2: Speciation methods". Handbook of Evolutionary Computation. Institute of Physics Publishing. S2CID 3547258.
- ↑ Shir, Ofer M. (2012). "Niching in Evolutionary Algorithms". In Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.). Handbook of Natural Computing (in English). Springer Berlin Heidelberg. pp. 1035–1069. doi:10.1007/978-3-540-92910-9_32. ISBN 9783540929093.
- ↑ Goldberg 1989, p. 41.
- ↑ Harik, Georges R.; Lobo, Fernando G.; Sastry, Kumara (1 January 2006). Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA). pp. 39–61. doi:10.1007/978-3-540-34954-9_3. ISBN 978-3-540-34953-2.
{{cite book}}:|journal=ignored (help) - ↑ Pelikan, Martin; Goldberg, David E.; Cantú-Paz, Erick (1 January 1999). BOA: The Bayesian Optimization Algorithm. pp. 525–532. ISBN 9781558606111.
{{cite book}}:|journal=ignored (help) - ↑ Coffin, David; Smith, Robert E. (1 January 2008). Linkage Learning in Estimation of Distribution Algorithms. pp. 141–156. doi:10.1007/978-3-540-85068-7_7. ISBN 978-3-540-85067-0.
{{cite book}}:|journal=ignored (help) - ↑ Echegoyen, Carlos; Mendiburu, Alexander; Santana, Roberto; Lozano, Jose A. (8 November 2012). "On the Taxonomy of Optimization Problems Under Estimation of Distribution Algorithms". Evolutionary Computation. 21 (3): 471–495. doi:10.1162/EVCO_a_00095. ISSN 1063-6560. PMID 23136917. S2CID 26585053.
- ↑ Sadowski, Krzysztof L.; Bosman, Peter A.N.; Thierens, Dirk (1 January 2013). On the Usefulness of Linkage Processing for Solving MAX-SAT. pp. 853–860. doi:10.1145/2463372.2463474. hdl:1874/290291. ISBN 9781450319638. S2CID 9986768.
{{cite book}}:|journal=ignored (help) - ↑ Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad Hadi (19 November 2012). "An efficient algorithm for function optimization: modified stem cells algorithm". Central European Journal of Engineering. 3 (1): 36–50. doi:10.2478/s13531-012-0047-8.
- ↑ Wolpert, D.H., Macready, W.G., 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
- ↑ Goldberg, David E. (1991). "The theory of virtual alphabets". Parallel Problem Solving from Nature. pp. 13–22. doi:10.1007/BFb0029726. ISBN 978-3-540-54148-6.
{{cite book}}:|journal=ignored (help) - ↑ Janikow, C. Z.; Michalewicz, Z. (1991). "An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms" (PDF). Proceedings of the Fourth International Conference on Genetic Algorithms: 31–36. Archived (PDF) from the original on 2022-10-09. Retrieved 2 July 2013.
- ↑ Patrascu, M.; Stancu, A.F.; Pop, F. (2014). "HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation". Soft Computing. 18 (12): 2565–2576. doi:10.1007/s00500-014-1401-y. S2CID 29821873.
- ↑ Baluja, Shumeet; Caruana, Rich (1995). Removing the genetics from the standard genetic algorithm (PDF). ICML. Archived (PDF) from the original on 2022-10-09.
- ↑ Srinivas, M.; Patnaik, L. (1994). "Adaptive probabilities of crossover and mutation in genetic algorithms" (PDF). IEEE Transactions on System, Man and Cybernetics. 24 (4): 656–667. doi:10.1109/21.286385. Archived (PDF) from the original on 2022-10-09.
- ↑ Zhang, J.; Chung, H.; Lo, W. L. (2007). "Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms". IEEE Transactions on Evolutionary Computation. 11 (3): 326–335. doi:10.1109/TEVC.2006.880727. S2CID 2625150.
- ↑ See for instance Evolution-in-a-nutshell Archived 15 April 2016 at the Wayback Machine or example in travelling salesman problem, in particular the use of an edge recombination operator.
- ↑ Goldberg, D. E.; Korb, B.; Deb, K. (1989). "Messy Genetic Algorithms : Motivation Analysis, and First Results". Complex Systems. 5 (3): 493–530.
- ↑ Gene expression: The missing link in evolutionary computation
- ↑ Harik, G. (1997). Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms (PhD). Dept. Computer Science, University of Michigan, Ann Arbour.
- ↑ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II. Energies. 2013; 6(3):1439-1455.
- ↑ Gross, Bill (2 February 2009). "A solar energy system that tracks the sun". TED. Retrieved 20 November 2013.
- ↑ Hornby, G. S.; Linden, D. S.; Lohn, J. D., Automated Antenna Design with Evolutionary Algorithms (PDF)
- ↑ "Flexible Muscle-Based Locomotion for Bipedal Creatures".
- ↑ Evans, B.; Walton, S.P. (December 2017). "Aerodynamic optimisation of a hypersonic reentry vehicle based on solution of the Boltzmann–BGK equation and evolutionary optimisation". Applied Mathematical Modelling. 52: 215–240. doi:10.1016/j.apm.2017.07.024. ISSN 0307-904X.
- ↑ Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.
- ↑ Turing, Alan M. (October 1950). "Computing machinery and intelligence". Mind. LIX (238): 433–460. doi:10.1093/mind/LIX.236.433.
- ↑ Aldawoodi, Namir (2008). An Approach to Designing an Unmanned Helicopter Autopilot Using Genetic Algorithms and Simulated Annealing. p. 99. ISBN 978-0549773498 – via Google Books.
- ↑ Markoff, John (29 August 1990). "What's the Best Answer? It's Survival of the Fittest". New York Times. Retrieved 2016-07-13.
- ↑ Ruggiero, Murray A.. (1 August 2009) Fifteen years and counting Archived 30 January 2016 at the Wayback Machine. Futuresmag.com. Retrieved on 2013-08-07.
- ↑ Evolver: Sophisticated Optimization for Spreadsheets. Palisade. Retrieved on 2013-08-07.
- ↑ Benchmarks for Evaluating Optimization Algorithms and Benchmarking MATLAB Derivative-Free Optimizers for Practitioners’Rapid Access, IEEE Access, vol.7, 2019.
- ↑ Cohoon, J; et al. (2002). Evolutionary algorithms for the physical design of VLSI circuits (PDF). ISBN 978-3-540-43330-9. Archived (PDF) from the original on 2022-10-09.
{{cite book}}:|journal=ignored (help) - ↑ Pelikan, Martin; Goldberg, David E.; Cantú-Paz, Erick (1 January 1999). BOA: The Bayesian Optimization Algorithm. pp. 525–532. ISBN 9781558606111.
{{cite book}}:|journal=ignored (help) - ↑ Pelikan, Martin (2005). Hierarchical Bayesian optimization algorithm : toward a new generation of evolutionary algorithms (1st ed.). Berlin [u.a.]: Springer. ISBN 978-3-540-23774-7.
- ↑ Thierens, Dirk (11 September 2010). "The Linkage Tree Genetic Algorithm". pp. 264–273. doi:10.1007/978-3-642-15844-5_27. ISBN 978-3-642-15843-8.
{{cite book}}:|journal=ignored (help); Missing or empty|title=(help) - ↑ Ferreira, C (2001). "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems" (PDF). Complex Systems. 13 (2): 87–129. arXiv:cs/0102027. Bibcode:2001cs........2027F. Archived (PDF) from the original on 2022-10-09.
- ↑ Falkenauer, Emanuel (1997). Genetic Algorithms and Grouping Problems. Chichester, England: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
- ↑ Zlochin, Mark; Birattari, Mauro; Meuleau, Nicolas; Dorigo, Marco (1 October 2004). "Model-Based Search for Combinatorial Optimization: A Critical Survey". Annals of Operations Research (in English). 131 (1–4): 373–395. CiteSeerX 10.1.1.3.427. doi:10.1023/B:ANOR.0000039526.52305.af. ISSN 0254-5330. S2CID 63137.
- ↑ Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Vente r (2005) A comparison of particle swarm optimization and the genetic algorithm
- ↑ Baudry, Benoit; Franck Fleurey; Jean-Marc Jézéquel; Yves Le Traon (March–April 2005). "Automatic Test Case Optimization: A Bacteriologic Algorithm" (PDF). IEEE Software. 22 (2): 76–82. doi:10.1109/MS.2005.30. S2CID 3559602. Archived (PDF) from the original on 2022-10-09. Retrieved 9 August 2009.
- ↑ Civicioglu, P. (2012). "Transforming Geocentric Cartesian Coordinates to Geodetic Coordinates by Using Differential Search Algorithm". Computers &Geosciences. 46: 229–247. Bibcode:2012CG.....46..229C. doi:10.1016/j.cageo.2011.12.011.
- ↑ Kjellström, G. (December 1991). "On the Efficiency of Gaussian Adaptation". Journal of Optimization Theory and Applications. 71 (3): 589–597. doi:10.1007/BF00941405. S2CID 116847975.
ग्रन्थसूची
- Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetic Programming – An Introduction. San Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107.
- Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Sale, Mark E. (2006). "A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection". Journal of Pharmacokinetics and Pharmacodynamics. 33 (2): 196–221. doi:10.1007/s10928-006-9004-6. PMID 16565924. S2CID 39571129.
- 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. CiteSeerX 10.1.1.154.8314. doi:10.13176/11.44.
- Eiben, Agoston; Smith, James (2003). Introduction to Evolutionary Computing. Springer. ISBN 978-3540401841.
- Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction". Australian Journal of Biological Sciences. 10 (4): 484–491. doi:10.1071/BI9570484.
- Goldberg, David (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley Professional. ISBN 978-0201157673.
- Goldberg, David (2002). The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.
- Fogel, David (2006). Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (3rd ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.
- Hingston, Philip; Barone, Luigi; Michalewicz, Zbigniew (2008). Design by Evolution: Advances in Evolutionary Design. Springer. ISBN 978-3540741091.
- Holland, John (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press. ISBN 978-0262581110.
- Koza, John (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press. ISBN 978-0262111706.
- Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag. ISBN 978-3540606765.
- Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press. ISBN 9780585030944.
- 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.[self-published source?]
- Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.
- Schmitt, Lothar M.; Nehaniv, Chrystopher L.; Fujii, Robert H. (1998). "Linear analysis of genetic algorithms". Theoretical Computer Science. 208: 111–148.
- Schmitt, Lothar M. (2001). "Theory of Genetic Algorithms". Theoretical Computer Science. 259 (1–2): 1–61. doi:10.1016/S0304-3975(00)00406-0.
- Schmitt, Lothar M. (2004). "Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling". Theoretical Computer Science. 310 (1–3): 181–231. doi:10.1016/S0304-3975(03)00393-1.
- Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
- Vose, Michael (1999). The Simple Genetic Algorithm: Foundations and Theory. Cambridge, MA: MIT Press. ISBN 978-0262220583.
- Whitley, Darrell (1994). "A genetic algorithm tutorial" (PDF). Statistics and Computing. 4 (2): 65–85. CiteSeerX 10.1.1.184.3999. doi:10.1007/BF00175354. S2CID 3447126. Archived (PDF) from the original on 2022-10-09.
बाहरी संबंध
संसाधन
- [1] जेनेटिक एल्गोरिदम क्षेत्र में संसाधनों की एक सूची प्रदान करता है
- विकासवादी एल्गोरिदम के इतिहास और स्वादों का अवलोकन
ट्यूटोरियल
- जेनेटिक एल्गोरिदम - कंप्यूटर प्रोग्राम जो ऐसे विधियों से विकसित होते हैं जो प्राकृतिक चयन के समान होते हैं, जटिल समस्याओं को समाधान कर सकते हैं, यहां तक कि उनके निर्माता भी पूरी तरह से समझ नहीं पाते हैं एक उत्कृष्ट परिचय जॉन हॉलैंड द्वारा जीए और कैदी की दुविधा के लिए एक आवेदन के साथ
- GA कैसे काम करता है इसका अभ्यास करने या सीखने के लिए पाठक के लिए एक ऑनलाइन इंटरैक्टिव जेनेटिक एल्गोरिदम ट्यूटोरियल: चरण दर चरण सीखें या बैच में वैश्विक अभिसरण देखें, जनसंख्या का आकार बदलें , पारगमन दर / सीमा, उत्परिवर्तन दर / सीमा और चयन तंत्र, और बाधाएं जोड़ें।
- डैरेल व्हिटली कंप्यूटर साइंस डिपार्टमेंट कोलोराडो स्टेट यूनिवर्सिटी द्वारा एक जेनेटिक एल्गोरिथम ट्यूटोरियल बहुत कुछ के साथ एक उत्कृष्ट ट्यूटोरियल लिखित
- Essentials of Metaheuristics , 2009 (225 p)। सीन ल्यूक द्वारा मुक्त खुला पाठ।
- वैश्विक अनुकूलन एल्गोरिदम - सिद्धांत और अनुप्रयोग
- Python में जेनेटिक एल्गोरिदम GAs और Python कार्यान्वयन के पीछे के अंतर्ज्ञान के साथ ट्यूटोरियल।
- जेनेटिक एल्गोरिदम कैदी की दुविधा को समाधान करने के लिए विकसित होता है। रॉबर्ट एक्सलरोड द्वारा लिखित।
श्रेणी:आनुवंशिक एल्गोरिदम
श्रेणी:विकासवादी एल्गोरिदम
श्रेणी:खोज एल्गोरिदम
श्रेणी:साइबरनेटिक्स
श्रेणी:डिजिटल जीव
एसवी: जेनेटिक प्रोग्रामिंग # जेनेटिक एल्गोरिथम
