जेनेटिक एल्गोरिद्म: Difference between revisions

From Vigyanwiki
No edit summary
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> [[हाइपरपैरामीटर अनुकूलन]], आदि सम्मिलित हैं।
[[कंप्यूटर विज्ञान]] और संचालन अनुसंधान में, एक आनुवंशिक एल्गोरिथम (जीए) [[प्राकृतिक चयन]] की प्रक्रिया से प्रेरित एक [[मेटाह्यूरिस्टिक]] है जो [[विकासवादी एल्गोरिदम]] (ईए) के बड़े वर्ग से संबंधित है। उत्परिवर्तन (जेनेटिक एल्गोरिथम), पारगमन (जेनेटिक एल्गोरिथम) और चयन (जेनेटिक एल्गोरिथम) जैसे जैविक रूप से प्रेरित ऑपरेटरों पर विश्वाश करके [[अनुकूलन (गणित)]] और [[खोज एल्गोरिदम]] के उच्च-गुणवत्ता वाले समाधान उत्पन्न करने के लिए जेनेटिक एल्गोरिदम का सामान्यतः उपयोग किया जाता है।{{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> [[हाइपरपैरामीटर अनुकूलन]], आदि सम्मिलित हैं।


== कार्यप्रणाली ==
== कार्यप्रणाली ==
Line 11: Line 11:
एक आनुवंशिक एल्गोरिथम में, अनुकूलन समस्या के लिए [[उम्मीदवार समाधान]] (जिन्हें व्यक्ति, जीव, जीव, या [[फेनोटाइप]] कहा जाता है) की आबादी उत्तम समाधान की ओर विकसित होती है। प्रत्येक उम्मीदवार समाधान में गुणों का एक सेट होता है (इसके गुणसूत्र या [[जीनोटाइप]]) जिन्हें उत्परिवर्तित और परिवर्तित किया जा सकता है; परंपरागत रूप से, समाधान 0s और 1s की स्ट्रिंग्स के रूप में बाइनरी में प्रस्तुत किए जाते हैं, किन्तु अन्य एनकोडिंग भी संभव हैं।{{sfn|Whitley|1994|p=66}}
एक आनुवंशिक एल्गोरिथम में, अनुकूलन समस्या के लिए [[उम्मीदवार समाधान]] (जिन्हें व्यक्ति, जीव, जीव, या [[फेनोटाइप]] कहा जाता है) की आबादी उत्तम समाधान की ओर विकसित होती है। प्रत्येक उम्मीदवार समाधान में गुणों का एक सेट होता है (इसके गुणसूत्र या [[जीनोटाइप]]) जिन्हें उत्परिवर्तित और परिवर्तित किया जा सकता है; परंपरागत रूप से, समाधान 0s और 1s की स्ट्रिंग्स के रूप में बाइनरी में प्रस्तुत किए जाते हैं, किन्तु अन्य एनकोडिंग भी संभव हैं।{{sfn|Whitley|1994|p=66}}


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


एक विशिष्ट आनुवंशिक एल्गोरिथम की आवश्यकता होती है:
एक विशिष्ट आनुवंशिक एल्गोरिथम की आवश्यकता होती है:
Line 18: Line 18:
# समाधान डोमेन का मूल्यांकन करने के लिए एक [[फिटनेस कार्य]]
# समाधान डोमेन का मूल्यांकन करने के लिए एक [[फिटनेस कार्य]]


प्रत्येक उम्मीदवार समाधान का एक मानक प्रतिनिधित्व एक [[बिट सरणी]] (जिसे बिट सेट या बिट स्ट्रिंग भी कहा जाता है) के रूप में होता है।{{sfn|Whitley|1994|p=66}} अन्य प्रकार की सरणियों और संरचनाओं का अनिवार्य रूप से उसी प्रकार उपयोग किया जा सकता है। मुख्य गुण जो इन आनुवंशिक अभ्यावेदन को सुविधाजनक बनाती है, वह यह है कि उनके हिस्से उनके निश्चित आकार के कारण आसानी से संरेखित होते हैं, जो सरल क्रॉसओवर (आनुवांशिक एल्गोरिथम) संचालन की सुविधा प्रदान करता है। परिवर्तनीय लंबाई के प्रतिनिधित्व का भी उपयोग किया जा सकता है, किन्तु इस स्थितियों में क्रॉसओवर कार्यान्वयन अधिक जटिल है। [[आनुवंशिक प्रोग्रामिंग]] में ट्री-लाइक रिप्रेजेंटेशन का पता लगाया जाता है और [[विकासवादी प्रोग्रामिंग]] में ग्राफ-फॉर्म रिप्रेजेंटेशन का पता लगाया जाता है; [[जीन अभिव्यक्ति प्रोग्रामिंग]] में रैखिक गुणसूत्रों और पेड़ों दोनों के मिश्रण का पता लगाया जाता है।
प्रत्येक उम्मीदवार समाधान का एक मानक प्रतिनिधित्व एक [[बिट सरणी]] (जिसे बिट सेट या बिट स्ट्रिंग भी कहा जाता है) के रूप में होता है।{{sfn|Whitley|1994|p=66}} अन्य प्रकार की सरणियों और संरचनाओं का अनिवार्य रूप से उसी प्रकार उपयोग किया जा सकता है। मुख्य गुण जो इन आनुवंशिक अभ्यावेदन को सुविधाजनक बनाती है, वह यह है कि उनके हिस्से उनके निश्चित आकार के कारण आसानी से संरेखित होते हैं, जो सरल पारगमन (आनुवांशिक एल्गोरिथम) संचालन की सुविधा प्रदान करता है। परिवर्तनीय लंबाई के प्रतिनिधित्व का भी उपयोग किया जा सकता है, किन्तु इस स्थितियों में पारगमन कार्यान्वयन अधिक जटिल है। [[आनुवंशिक प्रोग्रामिंग]] में ट्री-लाइक रिप्रेजेंटेशन का पता लगाया जाता है और [[विकासवादी प्रोग्रामिंग]] में ग्राफ-फॉर्म रिप्रेजेंटेशन का पता लगाया जाता है; [[जीन अभिव्यक्ति प्रोग्रामिंग]] में रैखिक गुणसूत्रों और पेड़ों दोनों के मिश्रण का पता लगाया जाता है।


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


==== प्रारंभ ====
==== प्रारंभ ====
Line 35: Line 35:
==== जेनेटिक ऑपरेटर ====
==== जेनेटिक ऑपरेटर ====
{{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&ndash;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&ndash;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&ndash;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&ndash;412. {{ISBN|978-3-540-28848-0}}.</ref> सुझाव देता है कि दो से अधिक माता-पिता उच्च गुणवत्ता वाले गुणसूत्र उत्पन्न करते हैं।
Line 43: Line 43:
इन प्रक्रियाओं के परिणामस्वरूप अंततः अगली पीढ़ी के गुणसूत्रों की आबादी होती है जो प्रारंभिक पीढ़ी से अलग होती है। सामान्यतः, आबादी के लिए इस प्रक्रिया से औसत फिटनेस में वृद्धि होगी, क्योंकि प्रजनन के लिए पहली पीढ़ी के केवल सबसे अच्छे जीवों का चयन किया जाता है, साथ ही कम फिट समाधानों के एक छोटे से अनुपात के साथ। ये कम फिट समाधान माता-पिता के आनुवंशिक पूल के अन्दर आनुवंशिक विविधता सुनिश्चित करते हैं और इसलिए बाद की पीढ़ी के बच्चों की आनुवंशिक विविधता सुनिश्चित करते हैं।
इन प्रक्रियाओं के परिणामस्वरूप अंततः अगली पीढ़ी के गुणसूत्रों की आबादी होती है जो प्रारंभिक पीढ़ी से अलग होती है। सामान्यतः, आबादी के लिए इस प्रक्रिया से औसत फिटनेस में वृद्धि होगी, क्योंकि प्रजनन के लिए पहली पीढ़ी के केवल सबसे अच्छे जीवों का चयन किया जाता है, साथ ही कम फिट समाधानों के एक छोटे से अनुपात के साथ। ये कम फिट समाधान माता-पिता के आनुवंशिक पूल के अन्दर आनुवंशिक विविधता सुनिश्चित करते हैं और इसलिए बाद की पीढ़ी के बच्चों की आनुवंशिक विविधता सुनिश्चित करते हैं।


क्रॉसओवर बनाम म्यूटेशन के महत्व पर राय बंटी हुई है। डेविड बी फोगेल (2006) में कई संदर्भ हैं जो उत्परिवर्तन-आधारित खोज के महत्व का समर्थन करते हैं।
पारगमन बनाम म्यूटेशन के महत्व पर राय बंटी हुई है। डेविड बी फोगेल (2006) में कई संदर्भ हैं जो उत्परिवर्तन-आधारित खोज के महत्व का समर्थन करते हैं।


चूंकि क्रॉसओवर और म्यूटेशन को मुख्य जेनेटिक ऑपरेटर के रूप में जाना जाता है, फिर भी जेनेटिक एल्गोरिदम में रीग्रुपिंग, कॉलोनाइजेशन-विलुप्त होने या माइग्रेशन जैसे अन्य ऑपरेटरों का उपयोग करना संभव है।{{citation needed|date=November 2019}}
चूंकि पारगमन और म्यूटेशन को मुख्य जेनेटिक ऑपरेटर के रूप में जाना जाता है, फिर भी जेनेटिक एल्गोरिदम में रीग्रुपिंग, कॉलोनाइजेशन-विलुप्त होने या माइग्रेशन जैसे अन्य ऑपरेटरों का उपयोग करना संभव है।{{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>
ऊपर दिए गए मुख्य ऑपरेटरों के अतिरिक्त, गणना को तेज या अधिक शक्तिशाली बनाने के लिए अन्य [[अनुमानी]]्स को नियोजित किया जा सकता है। अटकलबाजी अनुमानवादी उम्मीदवार समाधानों के बीच पारगमन को दंडित करता है जो बहुत समान हैं; यह जनसंख्या विविधता को प्रोत्साहित करता है और कम इष्टतम समाधान के लिए समय से पहले [[अभिसरण (विकासवादी कंप्यूटिंग)]] को रोकने में सहायता करता है।<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 72: Line 72:
गोल्डबर्ग अनुमानी का वर्णन इस प्रकार करते हैं:
गोल्डबर्ग अनुमानी का वर्णन इस प्रकार करते हैं:


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


: क्योंकि कम परिभाषित लंबाई और निम्न क्रम के अत्यधिक फिट स्कीमाटा आनुवंशिक एल्गोरिदम की कार्रवाई में इतनी महत्वपूर्ण भूमिका निभाते हैं, हमने उन्हें पहले से ही एक विशेष नाम दिया है: बिल्डिंग ब्लॉक्स। जिस प्रकार एक बच्चा लकड़ी के साधारण ब्लॉकों की व्यवस्था के माध्यम से शानदार किले बनाता है, उसी प्रकार एक आनुवंशिक एल्गोरिथ्म शॉर्ट, लो-ऑर्डर, हाई-परफॉर्मेंस स्कीमाटा, या बिल्डिंग ब्लॉक्स के संयोजन के माध्यम से इष्टतम प्रदर्शन की तलाश करता है।{{sfn|Goldberg|1989|p=41}}
: क्योंकि कम परिभाषित लंबाई और निम्न क्रम के अत्यधिक फिट स्कीमाटा आनुवंशिक एल्गोरिदम की कार्रवाई में इतनी महत्वपूर्ण भूमिका निभाते हैं, हमने उन्हें पहले से ही एक विशेष नाम दिया है: बिल्डिंग ब्लॉक्स। जिस प्रकार एक बच्चा लकड़ी के साधारण ब्लॉकों की व्यवस्था के माध्यम से शानदार किले बनाता है, उसी प्रकार एक आनुवंशिक एल्गोरिथ्म शॉर्ट, लो-ऑर्डर, हाई-परफॉर्मेंस स्कीमाटा, या बिल्डिंग ब्लॉक्स के संयोजन के माध्यम से इष्टतम प्रदर्शन की तलाश करता है।{{sfn|Goldberg|1989|p=41}}
Line 93: Line 93:
=== गुणसूत्र प्रतिनिधित्व ===
=== गुणसूत्र प्रतिनिधित्व ===
{{main |आनुवंशिक प्रतिनिधित्व}}
{{main |आनुवंशिक प्रतिनिधित्व}}
सबसे सरल एल्गोरिथ्म प्रत्येक गुणसूत्र को बिट सरणी के रूप में दर्शाता है। सामान्यतः, संख्यात्मक मापदंडों को [[पूर्णांक|पूर्णांकों]] द्वारा दर्शाया जा सकता है, चूंकि [[तैरनेवाला स्थल]] अभ्यावेदन का उपयोग करना संभव है। इवोल्यूशन रणनीति और विकासवादी प्रोग्रामिंग के लिए फ्लोटिंग पॉइंट प्रतिनिधित्व स्वाभाविक है। वास्तविक-मूल्यवान आनुवंशिक एल्गोरिदम की धारणा की प्रस्तुति की गई है किन्तु वास्तव में एक मिथ्या नाम है क्योंकि यह वास्तव में बिल्डिंग ब्लॉक सिद्धांत का प्रतिनिधित्व नहीं करता है जो 1970 के दशक में [[जॉन हेनरी हॉलैंड]] द्वारा प्रस्तावित किया गया था। सैद्धांतिक और प्रयोगात्मक परिणामों (नीचे देखें) के आधार पर, चूंकि यह सिद्धांत समर्थन के बिना नहीं है। मूलभूत एल्गोरिथ्म बिट स्तर पर क्रॉसओवर और म्यूटेशन करता है। अन्य वेरिएंट क्रोमोसोम को संख्याओं की एक सूची के रूप में मानते हैं जो एक निर्देश तालिका, एक लिंक की गई सूची में नोड्स, [[साहचर्य सरणी]], [[वस्तु (कंप्यूटर विज्ञान)]], या कोई अन्य कल्पनीय [[डेटा संरचना]] में अनुक्रमित होते हैं। डेटा तत्व सीमाओं का सम्मान करने के लिए क्रॉसओवर और म्यूटेशन किया जाता है। अधिकांश डेटा प्रकारों के लिए, विशिष्ट भिन्नता ऑपरेटरों को डिज़ाइन किया जा सकता है। अलग-अलग विशिष्ट समस्या डोमेन के लिए अलग-अलग क्रोमोसोमल डेटा प्रकार उत्तम या बदतर काम करते हैं।
सबसे सरल एल्गोरिथ्म प्रत्येक गुणसूत्र को बिट सरणी के रूप में दर्शाता है। सामान्यतः, संख्यात्मक मापदंडों को [[पूर्णांक|पूर्णांकों]] द्वारा दर्शाया जा सकता है, चूंकि [[तैरनेवाला स्थल]] अभ्यावेदन का उपयोग करना संभव है। इवोल्यूशन रणनीति और विकासवादी प्रोग्रामिंग के लिए फ्लोटिंग पॉइंट प्रतिनिधित्व स्वाभाविक है। वास्तविक-मूल्यवान आनुवंशिक एल्गोरिदम की धारणा की प्रस्तुति की गई है किन्तु वास्तव में एक मिथ्या नाम है क्योंकि यह वास्तव में बिल्डिंग ब्लॉक सिद्धांत का प्रतिनिधित्व नहीं करता है जो 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=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> यह विशेष दृष्टिकोण उन अनुकूलन समस्याओं को समाधान करने की अनुमति देता है जिनके लिए समस्या मापदंडों के लिए अत्यधिक भिन्न परिभाषा डोमेन की आवश्यकता होती है। उदाहरण के लिए, कैस्केड कंट्रोलर ट्यूनिंग की समस्याओं में, आंतरिक लूप नियंत्रक संरचना तीन मापदंडों के एक पारंपरिक नियामक से संबंधित हो सकती है, चूंकि बाहरी लूप एक भाषाई नियंत्रक (जैसे फ़ज़ी प्रणाली) को प्रायुक्त कर सकता है, जिसका एक अलग विवरण है। एन्कोडिंग के इस विशेष रूप के लिए एक विशेष पारगमन तंत्र की आवश्यकता होती है जो क्रोमोसोम को खंड द्वारा पुनर्संयोजित करता है, और यह जटिल अनुकूली प्रणालियों, विशेष रूप से विकास प्रक्रियाओं के मॉडलिंग और अनुकरण के लिए एक उपयोगी उपकरण है।


=== अभिजात वर्ग ===
=== अभिजात वर्ग ===
Line 110: Line 110:


=== अनुकूली जीए ===
=== अनुकूली जीए ===
अनुकूली मापदंडों के साथ आनुवंशिक एल्गोरिदम (अनुकूली आनुवंशिक एल्गोरिदम, AGAs) आनुवंशिक एल्गोरिदम का एक और महत्वपूर्ण और आशाजनक संस्करण है। क्रॉसओवर (पीसी) और म्यूटेशन (अपराह्न) की संभावनाएं समाधान शुद्धता की डिग्री और अभिसरण गति को निर्धारित करती हैं जो आनुवंशिक एल्गोरिदम प्राप्त कर सकते हैं। पीसी और पीएम के निश्चित मानों का उपयोग करने के अतिरिक्त, एजीए प्रत्येक पीढ़ी में जनसंख्या की जानकारी का उपयोग करते हैं और जनसंख्या विविधता को बनाए रखने के साथ-साथ अभिसरण क्षमता को बनाए रखने के लिए पीसी और पीएम को अनुकूल रूप से समायोजित करते हैं। AGA (अनुकूली आनुवंशिक एल्गोरिथम),<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> में पीसी और पीएम का समायोजन समाधानों के फिटनेस मानों पर निर्भर करता है। CAGA (क्लस्टरिंग-आधारित अनुकूली आनुवंशिक एल्गोरिथम) में,<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&ndash;335 |year=2007 |doi=10.1109/TEVC.2006.880727 |s2cid=2625150 }}</ref> जनसंख्या के अनुकूलन राज्यों का न्याय करने के लिए क्लस्टरिंग विश्लेषण के उपयोग के माध्यम से, पीसी और पीएम का समायोजन इन अनुकूलन राज्यों पर निर्भर करता है।
अनुकूली मापदंडों के साथ आनुवंशिक एल्गोरिदम (अनुकूली आनुवंशिक एल्गोरिदम, AGAs) आनुवंशिक एल्गोरिदम का एक और महत्वपूर्ण और आशाजनक संस्करण है। पारगमन (पीसी) और म्यूटेशन (अपराह्न) की संभावनाएं समाधान शुद्धता की डिग्री और अभिसरण गति को निर्धारित करती हैं जो आनुवंशिक एल्गोरिदम प्राप्त कर सकते हैं। पीसी और पीएम के निश्चित मानों का उपयोग करने के अतिरिक्त, एजीए प्रत्येक पीढ़ी में जनसंख्या की जानकारी का उपयोग करते हैं और जनसंख्या विविधता को बनाए रखने के साथ-साथ अभिसरण क्षमता को बनाए रखने के लिए पीसी और पीएम को अनुकूल रूप से समायोजित करते हैं। AGA (अनुकूली आनुवंशिक एल्गोरिथम),<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> में पीसी और पीएम का समायोजन समाधानों के फिटनेस मानों पर निर्भर करता है। CAGA (क्लस्टरिंग-आधारित अनुकूली आनुवंशिक एल्गोरिथम) में,<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&ndash;335 |year=2007 |doi=10.1109/TEVC.2006.880727 |s2cid=2625150 }}</ref> जनसंख्या के अनुकूलन राज्यों का न्याय करने के लिए क्लस्टरिंग विश्लेषण के उपयोग के माध्यम से, पीसी और पीएम का समायोजन इन अनुकूलन राज्यों पर निर्भर करता है।


GA को अन्य अनुकूलन विधियों के साथ संयोजित करना अधिक प्रभावी हो सकता है। सामान्यतः अच्छे वैश्विक समाधान खोजने में एक जीए अधिक अच्छा होता है, किन्तु पूर्ण इष्टतम खोजने के लिए पिछले कुछ म्यूटेशनों को खोजने में अधिक अक्षम है। अन्य तकनीकें (जैसे पहाड़ी चढ़ाई) एक सीमित क्षेत्र में पूर्ण इष्टतम खोजने में अधिक कुशल हैं। वैकल्पिक जीए और पहाड़ी चढ़ाई की शक्तिशालीी की कमी को दूर करते हुए पहाड़ी चढ़ाई जीए की दक्षता में सुधार कर सकते हैं।{{Citation needed|date=July 2016}}  
GA को अन्य अनुकूलन विधियों के साथ संयोजित करना अधिक प्रभावी हो सकता है। सामान्यतः अच्छे वैश्विक समाधान खोजने में एक जीए अधिक अच्छा होता है, किन्तु पूर्ण इष्टतम खोजने के लिए पिछले कुछ म्यूटेशनों को खोजने में अधिक अक्षम है। अन्य तकनीकें (जैसे पहाड़ी चढ़ाई) एक सीमित क्षेत्र में पूर्ण इष्टतम खोजने में अधिक कुशल हैं। वैकल्पिक जीए और पहाड़ी चढ़ाई की शक्तिशालीी की कमी को दूर करते हुए पहाड़ी चढ़ाई जीए की दक्षता में सुधार कर सकते हैं।{{Citation needed|date=July 2016}}  
Line 125: Line 125:
समस्याएं जो जेनेटिक एल्गोरिदम द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं उनमें [[जेनेटिक एल्गोरिदम शेड्यूलिंग]] सम्मिलित है, और कई शेड्यूलिंग सॉफ़्टवेयर पैकेज GAs पर आधारित हैं।{{Citation needed|date=December 2011}} GA को [[अभियांत्रिकी]] में भी प्रायुक्त किया गया है।<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> [[वैश्विक अनुकूलन]] समस्याओं को समाधान करने के लिए आनुवंशिक एल्गोरिदम को अधिकांश एक दृष्टिकोण के रूप में प्रायुक्त किया जाता है।
समस्याएं जो जेनेटिक एल्गोरिदम द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं उनमें [[जेनेटिक एल्गोरिदम शेड्यूलिंग]] सम्मिलित है, और कई शेड्यूलिंग सॉफ़्टवेयर पैकेज GAs पर आधारित हैं।{{Citation needed|date=December 2011}} GA को [[अभियांत्रिकी]] में भी प्रायुक्त किया गया है।<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> अपने एल्गोरिथम डिज़ाइन मैनुअल में, [[स्टीवन स्कीएना]] किसी भी कार्य के लिए आनुवंशिक एल्गोरिथम के विरुद्ध सलाह देता है:
Line 160: Line 160:
* विकास की रणनीति (ईएस, रेचेनबर्ग, 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|सीएमए-ईएस]]) को जन्म दिया है।
* विकासवादी प्रोग्रामिंग (ईपी) में मुख्य रूप से उत्परिवर्तन और चयन और स्वैछिक प्रतिनिधित्व वाले समाधानों की आबादी सम्मिलित है। वे मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं, और अन्य विविधता संचालन सम्मिलित कर सकते हैं जैसे कि कई माता-पिता से जानकारी का संयोजन।
* विकासवादी प्रोग्रामिंग (ईपी) में मुख्य रूप से उत्परिवर्तन और चयन और स्वैछिक प्रतिनिधित्व वाले समाधानों की आबादी सम्मिलित है। वे मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं, और अन्य विविधता संचालन सम्मिलित कर सकते हैं जैसे कि कई माता-पिता से जानकारी का संयोजन।
* वितरण एल्गोरिथ्म (EDA) का अनुमान मॉडल-निर्देशित ऑपरेटरों द्वारा पारंपरिक प्रजनन ऑपरेटरों को प्रतिस्थापित करता है। इस प्रकार के मॉडल मशीन लर्निंग तकनीकों को नियोजित करके जनसंख्या से सीखे जाते हैं और संभाव्य ग्राफिकल मॉडल के रूप में प्रस्तुत किए जाते हैं, जिनसे नए समाधानों का नमूना लिया जा सकता है<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>
* वितरण एल्गोरिथ्म (EDA) का अनुमान मॉडल-निर्देशित ऑपरेटरों द्वारा पारंपरिक प्रजनन ऑपरेटरों को प्रतिस्थापित करता है। इस प्रकार के मॉडल मशीन लर्निंग तकनीकों को नियोजित करके जनसंख्या से सीखे जाते हैं और संभाव्य ग्राफिकल मॉडल के रूप में प्रस्तुत किए जाते हैं, जिनसे नए समाधानों का नमूना लिया जा सकता है<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>{{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> [[व्याकरणिक विकास]], [[रैखिक आनुवंशिक प्रोग्रामिंग]], [[बहु अभिव्यक्ति प्रोग्रामिंग]] आदि।
* [[समूहन आनुवंशिक एल्गोरिथम]] (GGA) GA का एक विकास है, जहां फ़ोकस को अलग-अलग आइटम से स्थानांतरित किया जाता है, जैसे क्लासिकल GA में, समूहों या आइटम के सबसेट पर।<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> [[इमैनुएल फल्केनाउर]] द्वारा प्रस्तावित इस जीए विकास के पीछे विचार यह है कि कुछ जटिल समस्याओं को समाधान करना, जैसे कि क्लस्टरिंग या विभाजन की समस्याएं जहां वस्तुओं के एक सेट को एक इष्टतम विधियों से वस्तुओं के अलग समूह में विभाजित किया जाना चाहिए, समूहों की विशेषताओं को बनाकर उत्तम विधियों से प्राप्त किया जा सकता है। जीन के समतुल्य वस्तुओं की। इस प्रकार की समस्याओं में बिन पैकिंग की समस्या, लाइन बैलेंसिंग, दूरी माप के संबंध में [[क्लस्टर विश्लेषण]], बराबर ढेर आदि सम्मिलित हैं, जिन पर क्लासिक जीए खराब प्रदर्शन करने वाले सिद्ध हुए। समूहों के समतुल्य जीन बनाने से तात्पर्य उन गुणसूत्रों से है जो सामान्य रूप से परिवर्तनशील लंबाई के होते हैं, और विशेष आनुवंशिक संचालक जो वस्तुओं के पूरे समूहों में हेरफेर करते हैं। विशेष रूप से बिन पैकिंग के लिए, मार्टेलो और टोथ के प्रभुत्व मानदंड के साथ संकरणित एक जीजीए यकीनन अब तक की सबसे अच्छी तकनीक है।
* [[समूहन आनुवंशिक एल्गोरिथम]] (GGA) GA का एक विकास है, जहां फ़ोकस को अलग-अलग आइटम से स्थानांतरित किया जाता है, जैसे क्लासिकल GA में, समूहों या आइटम के सबसेट पर।<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 248: 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)। सीन ल्यूक द्वारा मुक्त खुला पाठ।

Revision as of 10:36, 18 February 2023

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

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

कार्यप्रणाली

अनुकूलन समस्याएं

एक आनुवंशिक एल्गोरिथम में, अनुकूलन समस्या के लिए उम्मीदवार समाधान (जिन्हें व्यक्ति, जीव, जीव, या फेनोटाइप कहा जाता है) की आबादी उत्तम समाधान की ओर विकसित होती है। प्रत्येक उम्मीदवार समाधान में गुणों का एक सेट होता है (इसके गुणसूत्र या जीनोटाइप) जिन्हें उत्परिवर्तित और परिवर्तित किया जा सकता है; परंपरागत रूप से, समाधान 0s और 1s की स्ट्रिंग्स के रूप में बाइनरी में प्रस्तुत किए जाते हैं, किन्तु अन्य एनकोडिंग भी संभव हैं।[3]

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

एक विशिष्ट आनुवंशिक एल्गोरिथम की आवश्यकता होती है:

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

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

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

प्रारंभ

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

चयन

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

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

कुछ समस्याओं में, फिटनेस अभिव्यक्ति को परिभाषित करना कठिन या असंभव भी है; इन स्थितियों में, एक फेनोटाइप के फिटनेस फलन मान को निर्धारित करने के लिए एक कंप्यूटर सिमुलेशन का उपयोग किया जा सकता है (उदाहरण के लिए कम्प्यूटेशनल द्रव गतिकी का उपयोग वाहन के वायु प्रतिरोध को निर्धारित करने के लिए किया जाता है जिसका आकार फ़िनोटाइप के रूप में एन्कोड किया गया है), या यहां तक ​​​​कि इंटरएक्टिव विकासवादी संगणना का उपयोग किया जाता है .

जेनेटिक ऑपरेटर

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

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

यद्यपि प्रजनन के विधियों जो दो माता-पिता के उपयोग पर आधारित हैं, अधिक जीव विज्ञान से प्रेरित हैं, कुछ शोध[4][5] सुझाव देता है कि दो से अधिक माता-पिता उच्च गुणवत्ता वाले गुणसूत्र उत्पन्न करते हैं।

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

पारगमन बनाम म्यूटेशन के महत्व पर राय बंटी हुई है। डेविड बी फोगेल (2006) में कई संदर्भ हैं जो उत्परिवर्तन-आधारित खोज के महत्व का समर्थन करते हैं।

चूंकि पारगमन और म्यूटेशन को मुख्य जेनेटिक ऑपरेटर के रूप में जाना जाता है, फिर भी जेनेटिक एल्गोरिदम में रीग्रुपिंग, कॉलोनाइजेशन-विलुप्त होने या माइग्रेशन जैसे अन्य ऑपरेटरों का उपयोग करना संभव है।[citation needed]

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

आंकलन

ऊपर दिए गए मुख्य ऑपरेटरों के अतिरिक्त, गणना को तेज या अधिक शक्तिशाली बनाने के लिए अन्य अनुमानी्स को नियोजित किया जा सकता है। अटकलबाजी अनुमानवादी उम्मीदवार समाधानों के बीच पारगमन को दंडित करता है जो बहुत समान हैं; यह जनसंख्या विविधता को प्रोत्साहित करता है और कम इष्टतम समाधान के लिए समय से पहले अभिसरण (विकासवादी कंप्यूटिंग) को रोकने में सहायता करता है।[6][7]


समाप्ति

समाप्ति की स्थिति तक पहुंचने तक यह पीढ़ीगत प्रक्रिया दोहराई जाती है। सामान्य समाप्ति की स्थिति हैं:

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

बिल्डिंग ब्लॉक परिकल्पना

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

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

गोल्डबर्ग अनुमानी का वर्णन इस प्रकार करते हैं:

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

बिल्डिंग-ब्लॉक परिकल्पना की वैधता के संबंध में सामान्य सहमति की कमी के अतिरिक्त, इसका लगातार मूल्यांकन किया गया है और पूरे वर्षों में संदर्भ के रूप में इसका उपयोग किया गया है। वितरण एल्गोरिदम के कई अनुमान, उदाहरण के लिए, एक वातावरण प्रदान करने के प्रयास में प्रस्तावित किए गए हैं जिसमें परिकल्पना मान्य होगी।[9][10] चूंकि समस्याओं के कुछ वर्गों के लिए अच्छे परिणाम बताए गए हैं, जीए दक्षता के स्पष्टीकरण के रूप में बिल्डिंग-ब्लॉक परिकल्पना की विस्तृतता और/या व्यावहारिकता के संबंध में संदेह अभी भी बना हुआ है। दरअसल, वितरण एल्गोरिदम के अनुमान के परिप्रेक्ष्य से इसकी सीमाओं को समझने का प्रयास करने के लिए एक उचित मात्रा में काम है।[11][12][13]


सीमाएं

वैकल्पिक अनुकूलन एल्गोरिदम की तुलना में आनुवंशिक एल्गोरिथम के उपयोग की सीमाएँ हैं:

  • जटिल समस्याओं के लिए बार-बार फिटनेस फलन का मूल्यांकन अधिकांश कृत्रिम विकासवादी एल्गोरिदम का सबसे निषेधात्मक और सीमित खंड होता है। जटिल उच्च-आयामी, बहुआयामी समस्याओं का इष्टतम समाधान खोजने के लिए अधिकांश बहुत महंगे फिटनेस फलन मूल्यांकन की आवश्यकता होती है। वास्तविक संसार की समस्याओं जैसे संरचनात्मक अनुकूलन समस्याओं में, एक एकल कार्य मूल्यांकन के लिए कई घंटों से लेकर कई दिनों तक पूर्ण अनुकरण की आवश्यकता हो सकती है। विशिष्ट अनुकूलन विधियाँ इस प्रकार की समस्या से नहीं निपट सकती हैं। इस स्थितियों में, एक त्रुटिहीन मूल्यांकन छोड़ना और एक फिटनेस सन्निकटन का उपयोग करना आवश्यक हो सकता है जो कम्प्यूटेशनल रूप से कुशल है। यह स्पष्ट है कि जटिल वास्तविक जीवन की समस्याओं को समाधान करने के लिए GA का उपयोग करने के लिए फिटनेस सन्निकटन का समामेलन सबसे आशाजनक दृष्टिकोणों में से एक हो सकता है।
  • जेनेटिक एल्गोरिदम जटिलता के साथ अच्छी तरह से स्केल नहीं करते हैं। यही है, जहां उत्परिवर्तन के संपर्क में आने वाले तत्वों की संख्या बड़ी है, वहां अधिकांश खोज स्थान के आकार में घातीय वृद्धि होती है। इससे इंजन, घर या विमान को डिजाइन करने जैसी समस्याओं पर तकनीक का उपयोग करना अधिक कठिन हो जाता है[citation needed]. विकासवादी खोज के लिए ऐसी समस्याओं को सुगम बनाने के लिए, उन्हें यथासंभव सरलतम प्रतिनिधित्व में विभाजित किया जाना चाहिए। इसलिए हम सामान्यतः विकासवादी एल्गोरिदम को इंजनों के अतिरिक्त पंखे के ब्लेड के लिए एन्कोडिंग डिज़ाइन देखते हैं, विस्तृत निर्माण योजनाओं के अतिरिक्त आकृतियों का निर्माण करते हैं, और पूरे विमान डिज़ाइनों के अतिरिक्त एयरफ़ोइल। जटिलता की दूसरी समस्या यह है कि आगे विनाशकारी उत्परिवर्तन से अच्छे समाधान का प्रतिनिधित्व करने के लिए विकसित किए गए भागों की रक्षा कैसे की जाए, खासकर जब उनके फिटनेस मूल्यांकन के लिए उन्हें अन्य भागों के साथ अच्छी तरह से संयोजित करने की आवश्यकता होती है।
  • अन्य समाधानों की तुलना में ही उत्तम समाधान है। परिणामस्वरूप, रोक मानदंड हर समस्या में स्पष्ट नहीं है।
  • कई समस्याओं में, GA में समस्या के वैश्विक इष्टतम के अतिरिक्त स्थानीय इष्टतम या यहाँ तक कि स्वैच्छिक बिंदुओं की ओर अभिसरण करने की प्रवृत्ति होती है। इसका अर्थ यह है कि यह लंबी अवधि की फिटनेस प्राप्त करने के लिए अल्पकालिक फिटनेस का त्याग करना नहीं जानता है। ऐसा होने की संभावना फिटनेस परिदृश्य के आकार पर निर्भर करती है: कुछ समस्याएं वैश्विक इष्टतम की ओर एक आसान चढ़ाई प्रदान कर सकती हैं, अन्य कार्य के लिए स्थानीय ऑप्टिमा को ढूंढना आसान बना सकती हैं। इस समस्या को एक अलग फिटनेस फलन का उपयोग करके, उत्परिवर्तन की दर में वृद्धि करके, या चयन तकनीकों का उपयोग करके समाधान किया जा सकता है जो समाधान की विविध आबादी को बनाए रखता है,[14] चूंकि खोज और अनुकूलन में कोई मुफ्त लंच नहीं[15] सिद्ध करता है कि इस समस्या का कोई सामान्य समाधान नहीं है। विविधता को बनाए रखने के लिए एक सामान्य तकनीक एक आला दंड लगाना है, जिसमें, पर्याप्त समानता वाले व्यक्तियों के किसी भी समूह (आला त्रिज्या) में एक दंड जोड़ा जाता है, जो बाद की पीढ़ियों में उस समूह के प्रतिनिधित्व को कम कर देगा, अन्य (कम समान) व्यक्तियों को अनुमति देगा जनसंख्या में बनाए रखना है। चूँकि, समस्या के परिदृश्य के आधार पर, यह तरकीब प्रभावी नहीं हो सकती है। एक अन्य संभावित तकनीक जनसंख्या के हिस्से को अव्यवस्थित रूप से उत्पन्न व्यक्तियों के साथ बदलना होगा, जब अधिकांश आबादी एक-दूसरे के समान होती है। आनुवंशिक एल्गोरिदम (और आनुवंशिक प्रोग्रामिंग) में विविधता महत्वपूर्ण है क्योंकि एक सजातीय आबादी को पार करने से नए समाधान नहीं मिलते हैं। उत्क्रांति रणनीति और विकासवादी प्रोग्रामिंग में, उत्परिवर्तन पर अधिक निर्भरता के कारण विविधता आवश्यक नहीं है।
  • डायनेमिक डेटा सेट पर काम करना कठिन है, क्योंकि जीनोम जल्दी समाधान की ओर अभिसरण करना प्रारंभ कर देते हैं जो बाद के डेटा के लिए मान्य नहीं हो सकता है। आनुवंशिक विविधता को किसी प्रकार बढ़ाकर और प्रारंभिक अभिसरण को रोककर, समाधान की गुणवत्ता में गिरावट आने पर उत्परिवर्तन की संभावना को बढ़ाकर (ट्रिगर हाइपरम्यूटेशन कहा जाता है), या कभी-कभी जीन पूल में पूरी तरह से नए, अव्यवस्थित रूप से उत्पन्न तत्वों को प्रस्तुत करके इसे दूर करने के लिए कई विधियों प्रस्तावित किए गए हैं। (यादृच्छिक आप्रवासी कहा जाता है)। फिर से, विकास रणनीति और विकासवादी प्रोग्रामिंग को एक तथाकथित अल्पविराम रणनीति के साथ प्रायुक्त किया जा सकता है जिसमें माता-पिता का रखरखाव नहीं किया जाता है और नए माता-पिता केवल संतानों में से चुने जाते हैं। यह गतिशील समस्याओं पर अधिक प्रभावी हो सकता है।
  • जीए उन समस्याओं को प्रभावी रूप से समाधान नहीं कर सकते हैं जिनमें एकमात्र फिटनेस उपाय एक सही/गलत उपाय है (जैसे निर्णय समस्याएं), क्योंकि समाधान पर अभिसरण करने का कोई विधि नहीं है (चढ़ने के लिए कोई पहाड़ी नहीं)। इन स्थितियों में, यादृच्छिक खोज से GA जितनी जल्दी समाधान मिल सकता है। चूँकि, यदि स्थिति सफलता/असफलता परीक्षण को अलग-अलग परिणाम देने (संभवतः) देने की अनुमति देती है, तो सफलताओं से असफलताओं का अनुपात एक उपयुक्त फिटनेस उपाय प्रदान करता है।
  • विशिष्ट अनुकूलन समस्याओं और समस्या उदाहरणों के लिए, अभिसरण की गति के संदर्भ में अन्य अनुकूलन एल्गोरिदम आनुवंशिक एल्गोरिदम की तुलना में अधिक कुशल हो सकते हैं। वैकल्पिक और पूरक एल्गोरिदम में विकास रणनीति, विकासवादी प्रोग्रामिंग, तैयार किए हुयी धातु पे पानी चढाने की कला, गॉसियन अनुकूलन, पहाड़ी चढ़ाई, और झुंड खुफिया (जैसे: चींटी कॉलोनी अनुकूलन, कण झुंड अनुकूलन) और पूर्णांक रैखिक प्रोग्रामिंग पर आधारित विधियों सम्मिलित हैं। आनुवंशिक एल्गोरिदम की उपयुक्तता समस्या के ज्ञान की मात्रा पर निर्भर करती है; प्रसिद्ध समस्याओं में अधिकांश उत्तम, अधिक विशिष्ट दृष्टिकोण होते हैं।

प्रकार

गुणसूत्र प्रतिनिधित्व

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

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

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

अभिजात वर्ग

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


समानांतर कार्यान्वयन

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

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

अनुकूली जीए

अनुकूली मापदंडों के साथ आनुवंशिक एल्गोरिदम (अनुकूली आनुवंशिक एल्गोरिदम, AGAs) आनुवंशिक एल्गोरिदम का एक और महत्वपूर्ण और आशाजनक संस्करण है। पारगमन (पीसी) और म्यूटेशन (अपराह्न) की संभावनाएं समाधान शुद्धता की डिग्री और अभिसरण गति को निर्धारित करती हैं जो आनुवंशिक एल्गोरिदम प्राप्त कर सकते हैं। पीसी और पीएम के निश्चित मानों का उपयोग करने के अतिरिक्त, एजीए प्रत्येक पीढ़ी में जनसंख्या की जानकारी का उपयोग करते हैं और जनसंख्या विविधता को बनाए रखने के साथ-साथ अभिसरण क्षमता को बनाए रखने के लिए पीसी और पीएम को अनुकूल रूप से समायोजित करते हैं। AGA (अनुकूली आनुवंशिक एल्गोरिथम),[20] में पीसी और पीएम का समायोजन समाधानों के फिटनेस मानों पर निर्भर करता है। CAGA (क्लस्टरिंग-आधारित अनुकूली आनुवंशिक एल्गोरिथम) में,[21] जनसंख्या के अनुकूलन राज्यों का न्याय करने के लिए क्लस्टरिंग विश्लेषण के उपयोग के माध्यम से, पीसी और पीएम का समायोजन इन अनुकूलन राज्यों पर निर्भर करता है।

GA को अन्य अनुकूलन विधियों के साथ संयोजित करना अधिक प्रभावी हो सकता है। सामान्यतः अच्छे वैश्विक समाधान खोजने में एक जीए अधिक अच्छा होता है, किन्तु पूर्ण इष्टतम खोजने के लिए पिछले कुछ म्यूटेशनों को खोजने में अधिक अक्षम है। अन्य तकनीकें (जैसे पहाड़ी चढ़ाई) एक सीमित क्षेत्र में पूर्ण इष्टतम खोजने में अधिक कुशल हैं। वैकल्पिक जीए और पहाड़ी चढ़ाई की शक्तिशालीी की कमी को दूर करते हुए पहाड़ी चढ़ाई जीए की दक्षता में सुधार कर सकते हैं।[citation needed]

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

एक भिन्नता, जहां एक पूरे के रूप में जनसंख्या अपने व्यक्तिगत सदस्यों के अतिरिक्त विकसित होती है, जीन पूल पुनर्संयोजन के रूप में जाना जाता है।

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


समस्या डोमेन

समस्याएं जो जेनेटिक एल्गोरिदम द्वारा समाधान के लिए विशेष रूप से उपयुक्त प्रतीत होती हैं उनमें जेनेटिक एल्गोरिदम शेड्यूलिंग सम्मिलित है, और कई शेड्यूलिंग सॉफ़्टवेयर पैकेज GAs पर आधारित हैं।[citation needed] GA को अभियांत्रिकी में भी प्रायुक्त किया गया है।[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] वे खोज के नियंत्रण मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं। स्व-अनुकूलन के डी-रैंडमाइजेशन ने समकालीन सहप्रसरण मैट्रिक्स अनुकूलन विकास रणनीति (सीएमए-ईएस) को जन्म दिया है।
  • विकासवादी प्रोग्रामिंग (ईपी) में मुख्य रूप से उत्परिवर्तन और चयन और स्वैछिक प्रतिनिधित्व वाले समाधानों की आबादी सम्मिलित है। वे मापदंडों को समायोजित करने के लिए स्व-अनुकूलन का उपयोग करते हैं, और अन्य विविधता संचालन सम्मिलित कर सकते हैं जैसे कि कई माता-पिता से जानकारी का संयोजन।
  • वितरण एल्गोरिथ्म (EDA) का अनुमान मॉडल-निर्देशित ऑपरेटरों द्वारा पारंपरिक प्रजनन ऑपरेटरों को प्रतिस्थापित करता है। इस प्रकार के मॉडल मशीन लर्निंग तकनीकों को नियोजित करके जनसंख्या से सीखे जाते हैं और संभाव्य ग्राफिकल मॉडल के रूप में प्रस्तुत किए जाते हैं, जिनसे नए समाधानों का नमूना लिया जा सकता है[39][40] या निर्देशित-पारगमन से उत्पन्न।[41]
  • जेनेटिक प्रोग्रामिंग (जीपी) जॉन बकरी द्वारा लोकप्रिय एक संबंधित तकनीक है जिसमें फलन पैरामीटर के अतिरिक्त कंप्यूटर प्रोग्राम को अनुकूलित किया जाता है। जेनेटिक प्रोग्रामिंग अधिकांश ट्री (डेटा स्ट्रक्चर) | ट्री-आधारित आंतरिक डेटा स्ट्रक्चर का उपयोग करती है, जो जेनेटिक एल्गोरिदम की विशिष्ट सूची (कंप्यूटिंग) संरचनाओं के अतिरिक्त अनुकूलन के लिए कंप्यूटर प्रोग्राम का प्रतिनिधित्व करती है। कार्टेशियन जेनेटिक प्रोग्रामिंग, जीन एक्सप्रेशन प्रोग्रामिंग सहित जेनेटिक प्रोग्रामिंग के कई प्रकार हैं।[42] व्याकरणिक विकास, रैखिक आनुवंशिक प्रोग्रामिंग, बहु अभिव्यक्ति प्रोग्रामिंग आदि।
  • समूहन आनुवंशिक एल्गोरिथम (GGA) GA का एक विकास है, जहां फ़ोकस को अलग-अलग आइटम से स्थानांतरित किया जाता है, जैसे क्लासिकल GA में, समूहों या आइटम के सबसेट पर।[43] इमैनुएल फल्केनाउर द्वारा प्रस्तावित इस जीए विकास के पीछे विचार यह है कि कुछ जटिल समस्याओं को समाधान करना, जैसे कि क्लस्टरिंग या विभाजन की समस्याएं जहां वस्तुओं के एक सेट को एक इष्टतम विधियों से वस्तुओं के अलग समूह में विभाजित किया जाना चाहिए, समूहों की विशेषताओं को बनाकर उत्तम विधियों से प्राप्त किया जा सकता है। जीन के समतुल्य वस्तुओं की। इस प्रकार की समस्याओं में बिन पैकिंग की समस्या, लाइन बैलेंसिंग, दूरी माप के संबंध में क्लस्टर विश्लेषण, बराबर ढेर आदि सम्मिलित हैं, जिन पर क्लासिक जीए खराब प्रदर्शन करने वाले सिद्ध हुए। समूहों के समतुल्य जीन बनाने से तात्पर्य उन गुणसूत्रों से है जो सामान्य रूप से परिवर्तनशील लंबाई के होते हैं, और विशेष आनुवंशिक संचालक जो वस्तुओं के पूरे समूहों में हेरफेर करते हैं। विशेष रूप से बिन पैकिंग के लिए, मार्टेलो और टोथ के प्रभुत्व मानदंड के साथ संकरणित एक जीजीए यकीनन अब तक की सबसे अच्छी तकनीक है।
  • इंटरएक्टिव विकासवादी एल्गोरिदम विकासवादी एल्गोरिदम हैं जो मानव मूल्यांकन का उपयोग करते हैं। वे सामान्यतः उन डोमेन पर प्रायुक्त होते हैं जहां कम्प्यूटेशनल फिटनेस फलन को डिज़ाइन करना कठिन होता है, उदाहरण के लिए, छवियों, संगीत, कलात्मक डिजाइनों और रूपों को उपयोगकर्ताओं की सौंदर्य पसंद को फिट करने के लिए विकसित करना।

झुंड बुद्धि

झुंड बुद्धि विकासवादी संगणना का एक उप-क्षेत्र है।

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


अन्य विकासवादी कंप्यूटिंग एल्गोरिदम

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

  • MEME टिक एल्गोरिथम (MA), जिसे अधिकांश दूसरों के बीच हाइब्रिड जेनेटिक एल्गोरिथम कहा जाता है, एक जनसंख्या-आधारित पद्धति है जिसमें समाधान भी स्थानीय सुधार चरणों के अधीन होते हैं। मेमेटिक एल्गोरिदम का विचार मेम्स से आता है, जो जीन के विपरीत खुद को अनुकूलित कर सकते हैं। कुछ समस्या क्षेत्रों में उन्हें पारंपरिक विकासवादी एल्गोरिदम की तुलना में अधिक कुशल दिखाया गया है।
  • बैक्टीरियोलॉजिकल एल्गोरिदम (बीए) विकासवादी पारिस्थितिकी और विशेष रूप से बैक्टीरियोलॉजिक अनुकूलन से प्रेरित है। विकासवादी पारिस्थितिकी जीवित जीवों का उनके पर्यावरण के संदर्भ में अध्ययन है, जिसका उद्देश्य यह पता लगाना है कि वे कैसे अनुकूलन करते हैं। इसकी मूल अवधारणा यह है कि एक विषम वातावरण में, एक व्यक्ति ऐसा नहीं होता जो पूरे वातावरण के अनुकूल हो। इसलिए, जनसंख्या स्तर पर तर्क करने की जरूरत है। यह भी माना जाता है कि बीए को जटिल पोजिशनिंग समस्याओं (सेल फोन, शहरी नियोजन, और इसी प्रकार के एंटेना) या डेटा माइनिंग के लिए सफलतापूर्वक प्रायुक्त किया जा सकता है।[46]
  • सांस्कृतिक एल्गोरिथम (सीए) में जनसंख्या घटक सम्मिलित होता है जो लगभग आनुवंशिक एल्गोरिथम के समान होता है और इसके अतिरिक्त, एक ज्ञान घटक जिसे विश्वास स्थान कहा जाता है।
  • सुपरऑर्गेनिज्म के प्रवास से प्रेरित विभेदक विकास (DE)।[47]
  • गॉसियन अनुकूलन (सामान्य या प्राकृतिक अनुकूलन, जीए के साथ भ्रम से बचने के लिए संक्षिप्त एनए) सिग्नल प्रोसेसिंग प्रणाली की विनिर्माण उपज को अधिकतम करने के लिए अभिप्रेत है। इसका उपयोग साधारण पैरामीट्रिक अनुकूलन के लिए भी किया जा सकता है। यह स्वीकार्यता के सभी क्षेत्रों और सभी गाऊसी वितरणों के लिए मान्य एक निश्चित प्रमेय पर निर्भर करता है। एनए की दक्षता सूचना सिद्धांत और दक्षता के एक निश्चित प्रमेय पर निर्भर करती है। इसकी दक्षता को सूचना प्राप्त करने के लिए आवश्यक कार्य से विभाजित सूचना के रूप में परिभाषित किया गया है।[48] क्योंकि एनए व्यक्ति अर्थ फिटनेस के अतिरिक्त माध्य फिटनेस को अधिकतम करता है, परिदृश्य को इस प्रकार चिकना किया जाता है कि चोटियों के बीच की घाटियाँ गायब हो सकती हैं। इसलिए फिटनेस परिदृश्य में स्थानीय चोटियों से बचने की एक निश्चित महत्वाकांक्षा है। पल मैट्रिक्स के अनुकूलन द्वारा तेज शिखर पर चढ़ने में एनए भी अच्छा है, क्योंकि एनए गाऊसी के विकार (औसत जानकारी) को एक साथ औसत फिटनेस स्थिर रखते हुए अधिकतम कर सकता है।

अन्य मेटाह्यूरिस्टिक विधियों

मेटाह्यूरिस्टिक विधियों विस्तृत रूप से स्टोकेस्टिक ऑप्टिमाइज़ेशन ऑप्टिमाइज़ेशन विधियों के अंतर्गत आते हैं।

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

अन्य स्टोचैस्टिक अनुकूलन विधियाँ

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

यह भी देखें

संदर्भ

  1. Mitchell 1996, p. 2.
  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. 3.0 3.1 Whitley 1994, p. 66.
  4. 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.
  5. 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.
  6. Deb, Kalyanmoy; Spears, William M. (1997). "C6.2: Speciation methods". Handbook of Evolutionary Computation. Institute of Physics Publishing. S2CID 3547258.
  7. 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.
  8. Goldberg 1989, p. 41.
  9. 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)
  10. 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)
  11. 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)
  12. 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.
  13. 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)
  14. 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.
  15. Wolpert, D.H., Macready, W.G., 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  16. 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)
  17. 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.
  18. 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.
  19. Baluja, Shumeet; Caruana, Rich (1995). Removing the genetics from the standard genetic algorithm (PDF). ICML. Archived (PDF) from the original on 2022-10-09.
  20. 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.
  21. 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.
  22. 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.
  23. Goldberg, D. E.; Korb, B.; Deb, K. (1989). "Messy Genetic Algorithms : Motivation Analysis, and First Results". Complex Systems. 5 (3): 493–530.
  24. Gene expression: The missing link in evolutionary computation
  25. Harik, G. (1997). Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms (PhD). Dept. Computer Science, University of Michigan, Ann Arbour.
  26. 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.
  27. Gross, Bill (2 February 2009). "A solar energy system that tracks the sun". TED. Retrieved 20 November 2013.
  28. Hornby, G. S.; Linden, D. S.; Lohn, J. D., Automated Antenna Design with Evolutionary Algorithms (PDF)
  29. "Flexible Muscle-Based Locomotion for Bipedal Creatures".
  30. 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.
  31. Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.
  32. Turing, Alan M. (October 1950). "Computing machinery and intelligence". Mind. LIX (238): 433–460. doi:10.1093/mind/LIX.236.433.
  33. 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.
  34. Markoff, John (29 August 1990). "What's the Best Answer? It's Survival of the Fittest". New York Times. Retrieved 2016-07-13.
  35. 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.
  36. Evolver: Sophisticated Optimization for Spreadsheets. Palisade. Retrieved on 2013-08-07.
  37. Benchmarks for Evaluating Optimization Algorithms and Benchmarking MATLAB Derivative-Free Optimizers for Practitioners’Rapid Access, IEEE Access, vol.7, 2019.
  38. 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)
  39. 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)
  40. 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.
  41. 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)
  42. 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.
  43. Falkenauer, Emanuel (1997). Genetic Algorithms and Grouping Problems. Chichester, England: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
  44. 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.
  45. Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Vente r (2005) A comparison of particle swarm optimization and the genetic algorithm
  46. 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.
  47. 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.
  48. 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.


ग्रन्थसूची


बाहरी संबंध

संसाधन

ट्यूटोरियल


श्रेणी:आनुवंशिक एल्गोरिदम श्रेणी:विकासवादी एल्गोरिदम श्रेणी:खोज एल्गोरिदम श्रेणी:साइबरनेटिक्स श्रेणी:डिजिटल जीव

एसवी: जेनेटिक प्रोग्रामिंग # जेनेटिक एल्गोरिथम