विभेदक विकास: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:Ackley.gif|thumb|विभेदक विकास 2डी [[एकली समारोह]] को अनुकूलित करता है।]][[विकासवादी संगणना|विकासवादी गणना]] में, डिफरेंशियल इवोल्यूशन (विभेदक विकास) (डीई) ऐसी विधि है जो गुणवत्ता के दिए गए माप के संबंध में [[उम्मीदवार समाधान]] को सुधार करने का प्रयास कर समस्या का [[अनुकूलन (गणित)]] करती है। इस | [[File:Ackley.gif|thumb|विभेदक विकास 2डी [[एकली समारोह]] को अनुकूलित करता है।]][[विकासवादी संगणना|विकासवादी गणना]] में, डिफरेंशियल इवोल्यूशन (विभेदक विकास) (डीई) ऐसी विधि है जो गुणवत्ता के दिए गए माप के संबंध में [[उम्मीदवार समाधान]] को सुधार करने का प्रयास कर समस्या का [[अनुकूलन (गणित)]] करती है। इस प्रकार के तरीकों को सामान्यतः [[मेटाह्यूरिस्टिक|मेटाह्यूरिस्टिक्स]] के रूप में जाना जाता है क्योंकि वे समस्या को अनुकूलित करने के बारे में कुछ या कोई धारणा नहीं बनाते हैं और उम्मीदवार समाधानों के बहुत बड़े स्थान खोज सकते हैं। चूंकि, डीई जैसे मेटाह्यूरिस्टिक्स इस बात की गारंटी नहीं देते हैं कि इष्टतम समाधान कभी भी मिल जाएगा। | ||
डीई का उपयोग बहुआयामी वास्तविक-मूल्यवान | डीई का उपयोग बहुआयामी वास्तविक-मूल्यवान फलन (गणित) के लिए किया जाता है, लेकिन अनुकूलित होने वाली समस्या के [[ग्रेडियेंट|प्रवणता]] का उपयोग नहीं करता है, जिसका अर्थ है कि डीई को अलग-अलग कार्य करने के लिए अनुकूलन समस्या की आवश्यकता नहीं है, जैसा कि [[ढतला हुआ वंश|प्रवणता डिसेंट]] और [[अर्ध-न्यूटन तरीके|अर्ध-न्यूटन विधियों]] पारंपरिक अनुकूलन विधियों द्वारा आवश्यक है। इसलिए डीई का उपयोग अनुकूलन समस्याओं पर भी किया जा सकता है जो निरंतर भी नहीं हैं, शोर हैं, समय के साथ बदलते हैं, आदि।<ref name=elediadereview/> | ||
डीई उम्मीदवारों के समाधानों की आबादी को बनाए रखने और अपने सरल सूत्रों के अनुसार वर्तमान लोगों को जोड़कर नए उम्मीदवार समाधान बनाकर समस्या का अनुकूलन करता है, और फिर जो भी उम्मीदवार समाधान हाथ में अनुकूलन समस्या पर सबसे अच्छा स्कोर या फिटनेस रखता है। इस | डीई उम्मीदवारों के समाधानों की आबादी को बनाए रखने और अपने सरल सूत्रों के अनुसार वर्तमान लोगों को जोड़कर नए उम्मीदवार समाधान बनाकर समस्या का अनुकूलन करता है, और फिर जो भी उम्मीदवार समाधान हाथ में अनुकूलन समस्या पर सबसे अच्छा स्कोर या फिटनेस रखता है। इस प्रकार, अनुकूलन समस्या को ब्लैक बॉक्स के रूप में माना जाता है जो उम्मीदवार समाधान को दिए गए गुणवत्ता का उपाय प्रदान करता है और इसलिए प्रवणता की आवश्यकता नहीं होती है। | ||
डीई को 1990 के दशक में स्टोर्न एंड प्राइस द्वारा | डीई को 1990 के दशक में स्टोर्न एंड प्राइस द्वारा प्रस्तुत किया गया था।<ref name=storn97differential/><ref name=storn96usage/> पुस्तकें [[समानांतर कंप्यूटिंग]], [[बहुउद्देश्यीय अनुकूलन]], [[विवश अनुकूलन]] में डीई का उपयोग करने के सैद्धांतिक और व्यावहारिक पहलुओं पर प्रकाशित की गई हैं, और पुस्तकों में अनुप्रयोग क्षेत्रों के सर्वेक्षण भी सम्मिलित हैं।<ref name=price05differential/><ref name=feoktistov06differential/><ref>G. C. Onwubolu and B V Babu, {{cite web|url=https://www.springer.com/in/book/9783540201670|title=New Optimization Techniques in Engineering|access-date=17 September 2016}}</ref><ref name=chakraborty08advances/> डीई के बहुआयामी अनुसंधान स्थितियों पर सर्वेक्षण जर्नल लेखों में पाए जा सकते हैं।<ref>S. Das and P. N. Suganthan, "[https://www.researchgate.net/profile/Swagatam_Das/publication/220380793_Differential_Evolution_A_Survey_of_the_State-of-the-Art/links/00b7d52204106cb196000000/Differential-Evolution-A-Survey-of-the-State-of-the-Art.pdf Differential Evolution: A Survey of the State-of-the-art]", IEEE Trans. on Evolutionary Computation, Vol. 15, No. 1, pp. 4-31, Feb. 2011, DOI: 10.1109/TEVC.2010.2059031.</ref><ref>S. Das, S. S. Mullick, P. N. Suganthan, "[http://web.mysites.ntu.edu.sg/epnsugan/PublicSite/Shared%20Documents/PDFs/DE-Survey-2016.pdf Recent Advances in Differential Evolution - An Updated Survey]," Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.</ref> | ||
| Line 11: | Line 11: | ||
डीई एल्गोरिथम का मूल संस्करण [[उम्मीदवार समाधान|उम्मीदवार समाधानों]] (जिन्हें एजेंट कहा जाता है) की आबादी होने से काम करता है। जनसंख्या से वर्तमान एजेंटों की स्थिति को संयोजित करने के लिए सरल गणितीय सूत्रों का उपयोग करके इन एजेंटों को खोज-स्थान में इधर-उधर ले जाया जाता है। यदि किसी एजेंट की नई स्थिति में सुधार होता है तो उसे स्वीकार कर लिया जाता है और वह जनसंख्या का भाग बन जाता है, अन्यथा नई स्थिति को यूं ही छोड़ दिया जाता है। प्रक्रिया को दोहराया जाता है और ऐसा करने से यह आशा की जाती है, लेकिन इसकी गारंटी नहीं है कि अंत में संतोषजनक समाधान खोज लिया जाएगा। | डीई एल्गोरिथम का मूल संस्करण [[उम्मीदवार समाधान|उम्मीदवार समाधानों]] (जिन्हें एजेंट कहा जाता है) की आबादी होने से काम करता है। जनसंख्या से वर्तमान एजेंटों की स्थिति को संयोजित करने के लिए सरल गणितीय सूत्रों का उपयोग करके इन एजेंटों को खोज-स्थान में इधर-उधर ले जाया जाता है। यदि किसी एजेंट की नई स्थिति में सुधार होता है तो उसे स्वीकार कर लिया जाता है और वह जनसंख्या का भाग बन जाता है, अन्यथा नई स्थिति को यूं ही छोड़ दिया जाता है। प्रक्रिया को दोहराया जाता है और ऐसा करने से यह आशा की जाती है, लेकिन इसकी गारंटी नहीं है कि अंत में संतोषजनक समाधान खोज लिया जाएगा। | ||
औपचारिक रूप से, मान लो <math>f: \mathbb{R}^n \to \mathbb{R}</math> फिटनेस | औपचारिक रूप से, मान लो <math>f: \mathbb{R}^n \to \mathbb{R}</math> फिटनेस फलन हो जिसे न्यूनतम किया जाना चाहिए (ध्यान दें कि फलन पर विचार करके अधिकतमकरण किया जा सकता है <math>h := -f</math> अतिरिक्त)। फलन उम्मीदवार समाधान को [[वास्तविक संख्या]]ओं के पंक्ति वेक्टर के रूप में तर्क के रूप में लेता है और आउटपुट के रूप में वास्तविक संख्या उत्पन्न करता है जो दिए गए उम्मीदवार समाधान की उपयुक्तता को निरुपित करता है। <math>f</math> का प्रवणता ज्ञात नहीं है। लक्ष्य <math>\mathbf{m}</math> समाधान खोजना है जिसके लिए <math>f(\mathbf{m}) \leq f(\mathbf{p})</math> सभी के लिए <math>\mathbf{p}</math> खोज-स्थान में, जिसका अर्थ है की <math>\mathbf{m}</math> वैश्विक न्यूनतम है। | ||
मान ले <math>\mathbf{x} \in \mathbb{R}^n</math> जनसंख्या में उम्मीदवार समाधान (एजेंट) नामित करें। मूल डीई एल्गोरिथ्म को तब निम्नानुसार वर्णित किया जा सकता है: | मान ले <math>\mathbf{x} \in \mathbb{R}^n</math> जनसंख्या में उम्मीदवार समाधान (एजेंट) नामित करें। मूल डीई एल्गोरिथ्म को तब निम्नानुसार वर्णित किया जा सकता है: | ||
| Line 26: | Line 26: | ||
*** एजेंट की संभावित नई स्थिति <math>\mathbf{y} = [y_1, \ldots, y_n]</math> की गणना करें निम्नलिखितनुसार: | *** एजेंट की संभावित नई स्थिति <math>\mathbf{y} = [y_1, \ldots, y_n]</math> की गणना करें निम्नलिखितनुसार: | ||
**** प्रत्येक के लिए <math>i \in \{1,\ldots,n\}</math>, समान रूप से वितरित यादृच्छिक <math>r_i \sim U(0,1)</math>संख्या चुनें | **** प्रत्येक के लिए <math>i \in \{1,\ldots,n\}</math>, समान रूप से वितरित यादृच्छिक <math>r_i \sim U(0,1)</math>संख्या चुनें | ||
**** | **** यदि <math>r_i < CR </math> या <math>i = R</math> फिर सेट करें <math>y_i = a_i + F \times (b_i-c_i)</math> अन्यथा <math>y_i = x_i</math> सेट करें. (सूचकांक स्थिति <math>R</math> निश्चित रूप से प्रतिस्थापित किया गया है।) | ||
*** | *** यदि <math>f(\mathbf{y}) \leq f(\mathbf{x})</math> फिर एजेंट को बदलें <math>\mathbf{x}</math> बेहतर या समान उम्मीदवार समाधान <math>\mathbf{y}</math> के साथ जनसंख्या में . | ||
* उस आबादी से एजेंट चुनें जिसके पास सबसे अच्छी फिटनेस है और इसे सबसे अच्छे पाए गए उम्मीदवार समाधान के रूप में वापस करें। | * उस आबादी से एजेंट चुनें जिसके पास सबसे अच्छी फिटनेस है और इसे सबसे अच्छे पाए गए उम्मीदवार समाधान के रूप में वापस करें। | ||
== पैरामीटर चयन == | == पैरामीटर चयन == | ||
[[Image:DE Meta-Fitness Landscape (Sphere and Rosenbrock).JPG|thumb|प्रदर्शन परिदृश्य दिखा रहा है कि दो डीई मापदंडों को बदलते समय | [[Image:DE Meta-Fitness Landscape (Sphere and Rosenbrock).JPG|thumb|प्रदर्शन परिदृश्य दिखा रहा है कि दो डीई मापदंडों को बदलते समय मूलभूत डीई स्फेयर और रोसेनब्रॉक बेंचमार्क समस्याओं पर समग्र रूप से कैसा प्रदर्शन करता है <math>\text{NP}</math> और <math>\text{F}</math>, और स्थिर रखते हुए <math>\text{CR}</math>=0.9.]]डीई मापदंडों का विकल्प <math>\text{NP}</math>, <math>\text{CR}</math> और <math>F</math> अनुकूलन प्रदर्शन पर बड़ा प्रभाव पड़ सकता है। अच्छा प्रदर्शन देने वाले डीई मापदंडों का चयन इसलिए बहुत शोध का विषय रहा है। लियू और लैम्पिनेन<ref name="liu02setting" /> और स्टोर्न एट अल द्वारा पैरामीटर चयन के लिए अंगूठे के नियम तैयार किए गए थे।<ref name=storn96usage/><ref name=price05differential/> पैरामीटर चयन के संबंध में गणितीय अभिसरण विश्लेषण ज़हरी द्वारा किया गया था।<ref name=zaharie02critical/> | ||
Revision as of 16:08, 16 February 2023
विभेदक विकास 2डी एकली समारोह को अनुकूलित करता है।
विकासवादी गणना में, डिफरेंशियल इवोल्यूशन (विभेदक विकास) (डीई) ऐसी विधि है जो गुणवत्ता के दिए गए माप के संबंध में उम्मीदवार समाधान को सुधार करने का प्रयास कर समस्या का अनुकूलन (गणित) करती है। इस प्रकार के तरीकों को सामान्यतः मेटाह्यूरिस्टिक्स के रूप में जाना जाता है क्योंकि वे समस्या को अनुकूलित करने के बारे में कुछ या कोई धारणा नहीं बनाते हैं और उम्मीदवार समाधानों के बहुत बड़े स्थान खोज सकते हैं। चूंकि, डीई जैसे मेटाह्यूरिस्टिक्स इस बात की गारंटी नहीं देते हैं कि इष्टतम समाधान कभी भी मिल जाएगा।
डीई का उपयोग बहुआयामी वास्तविक-मूल्यवान फलन (गणित) के लिए किया जाता है, लेकिन अनुकूलित होने वाली समस्या के प्रवणता का उपयोग नहीं करता है, जिसका अर्थ है कि डीई को अलग-अलग कार्य करने के लिए अनुकूलन समस्या की आवश्यकता नहीं है, जैसा कि प्रवणता डिसेंट और अर्ध-न्यूटन विधियों पारंपरिक अनुकूलन विधियों द्वारा आवश्यक है। इसलिए डीई का उपयोग अनुकूलन समस्याओं पर भी किया जा सकता है जो निरंतर भी नहीं हैं, शोर हैं, समय के साथ बदलते हैं, आदि।[1]
डीई उम्मीदवारों के समाधानों की आबादी को बनाए रखने और अपने सरल सूत्रों के अनुसार वर्तमान लोगों को जोड़कर नए उम्मीदवार समाधान बनाकर समस्या का अनुकूलन करता है, और फिर जो भी उम्मीदवार समाधान हाथ में अनुकूलन समस्या पर सबसे अच्छा स्कोर या फिटनेस रखता है। इस प्रकार, अनुकूलन समस्या को ब्लैक बॉक्स के रूप में माना जाता है जो उम्मीदवार समाधान को दिए गए गुणवत्ता का उपाय प्रदान करता है और इसलिए प्रवणता की आवश्यकता नहीं होती है।
डीई को 1990 के दशक में स्टोर्न एंड प्राइस द्वारा प्रस्तुत किया गया था।[2][3] पुस्तकें समानांतर कंप्यूटिंग, बहुउद्देश्यीय अनुकूलन, विवश अनुकूलन में डीई का उपयोग करने के सैद्धांतिक और व्यावहारिक पहलुओं पर प्रकाशित की गई हैं, और पुस्तकों में अनुप्रयोग क्षेत्रों के सर्वेक्षण भी सम्मिलित हैं।[4][5][6][7] डीई के बहुआयामी अनुसंधान स्थितियों पर सर्वेक्षण जर्नल लेखों में पाए जा सकते हैं।[8][9]
एल्गोरिथम
डीई एल्गोरिथम का मूल संस्करण उम्मीदवार समाधानों (जिन्हें एजेंट कहा जाता है) की आबादी होने से काम करता है। जनसंख्या से वर्तमान एजेंटों की स्थिति को संयोजित करने के लिए सरल गणितीय सूत्रों का उपयोग करके इन एजेंटों को खोज-स्थान में इधर-उधर ले जाया जाता है। यदि किसी एजेंट की नई स्थिति में सुधार होता है तो उसे स्वीकार कर लिया जाता है और वह जनसंख्या का भाग बन जाता है, अन्यथा नई स्थिति को यूं ही छोड़ दिया जाता है। प्रक्रिया को दोहराया जाता है और ऐसा करने से यह आशा की जाती है, लेकिन इसकी गारंटी नहीं है कि अंत में संतोषजनक समाधान खोज लिया जाएगा।
औपचारिक रूप से, मान लो फिटनेस फलन हो जिसे न्यूनतम किया जाना चाहिए (ध्यान दें कि फलन पर विचार करके अधिकतमकरण किया जा सकता है अतिरिक्त)। फलन उम्मीदवार समाधान को वास्तविक संख्याओं के पंक्ति वेक्टर के रूप में तर्क के रूप में लेता है और आउटपुट के रूप में वास्तविक संख्या उत्पन्न करता है जो दिए गए उम्मीदवार समाधान की उपयुक्तता को निरुपित करता है। का प्रवणता ज्ञात नहीं है। लक्ष्य समाधान खोजना है जिसके लिए सभी के लिए खोज-स्थान में, जिसका अर्थ है की वैश्विक न्यूनतम है।
मान ले जनसंख्या में उम्मीदवार समाधान (एजेंट) नामित करें। मूल डीई एल्गोरिथ्म को तब निम्नानुसार वर्णित किया जा सकता है:
- पैरामीटर चुनें , , और .
- जनसंख्या का आकार है, अर्थात उम्मीदवारों के एजेंटों या माता-पिता की संख्या; विशिष्ट सेटिंग 10 है.
- पैरामीटर क्रॉसओवर संभावना और पैरामीटर कहा जाता है अंतर भार कहा जाता है। विशिष्ट सेटिंग्स और हैं.
- इन विकल्पों से अनुकूलन प्रदर्शन बहुत प्रभावित हो सकता है; नीचे देखें।
- खोज-स्थान में यादृच्छिक स्थिति के साथ सभी एजेंटों को प्रारंभ करें ।
- जब तक समाप्ति मानदंड पूरा नहीं हो जाता (उदाहरण के लिए किए गए पुनरावृत्तियों की संख्या, या पर्याप्त फिटनेस तक पहुंच गया), निम्नलिखित को दोहराएं:
- प्रत्येक एजेंट के लिए जनसंख्या में करते हैं:
- तीन एजेंट चुनें , और यादृच्छिक रूप से जनसंख्या से, उन्हें दूसरे के साथ-साथ एजेंट से भी अलग होना चाहिए. ( बेस वेक्टर कहा जाता है।)
- यादृच्छिक सूचकांक चुनें जहाँ समस्या का आयाम अनुकूलित किया जा रहा है।
- एजेंट की संभावित नई स्थिति की गणना करें निम्नलिखितनुसार:
- प्रत्येक के लिए , समान रूप से वितरित यादृच्छिक संख्या चुनें
- यदि या फिर सेट करें अन्यथा सेट करें. (सूचकांक स्थिति निश्चित रूप से प्रतिस्थापित किया गया है।)
- यदि फिर एजेंट को बदलें बेहतर या समान उम्मीदवार समाधान के साथ जनसंख्या में .
- प्रत्येक एजेंट के लिए जनसंख्या में करते हैं:
- उस आबादी से एजेंट चुनें जिसके पास सबसे अच्छी फिटनेस है और इसे सबसे अच्छे पाए गए उम्मीदवार समाधान के रूप में वापस करें।
पैरामीटर चयन
.JPG)
डीई मापदंडों का विकल्प , और अनुकूलन प्रदर्शन पर बड़ा प्रभाव पड़ सकता है। अच्छा प्रदर्शन देने वाले डीई मापदंडों का चयन इसलिए बहुत शोध का विषय रहा है। लियू और लैम्पिनेन[10] और स्टोर्न एट अल द्वारा पैरामीटर चयन के लिए अंगूठे के नियम तैयार किए गए थे।[3][4] पैरामीटर चयन के संबंध में गणितीय अभिसरण विश्लेषण ज़हरी द्वारा किया गया था।[11]
प्रकार
अनुकूलन प्रदर्शन को बेहतर बनाने के प्रयास में डीई एल्गोरिद्म के प्रकार लगातार विकसित किए जा रहे हैं। ऊपर दिए गए मूल एल्गोरिथम में एजेंटों के क्रॉसओवर और उत्परिवर्तन करने के लिए कई अलग-अलग योजनाएं संभव हैं, उदाहरण के लिए देखें[3]
यह भी देखें
संदर्भ
- ↑ Rocca, P.; Oliveri, G.; Massa, A. (2011). "Differential Evolution as Applied to Electromagnetics". IEEE Antennas and Propagation Magazine. 53 (1): 38–49. doi:10.1109/MAP.2011.5773566. S2CID 27555808.
- ↑ Storn, R.; Price, K. (1997). "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces". Journal of Global Optimization. 11 (4): 341–359. doi:10.1023/A:1008202821328. S2CID 5297867.
- ↑ 3.0 3.1 3.2 Storn, R. (1996). "On the usage of differential evolution for function optimization". Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523. doi:10.1109/NAFIPS.1996.534789. S2CID 16576915.
- ↑ 4.0 4.1 Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer. ISBN 978-3-540-20950-8.
- ↑ Feoktistov, V. (2006). Differential Evolution: In Search of Solutions. Springer. ISBN 978-0-387-36895-5.
- ↑ G. C. Onwubolu and B V Babu, "New Optimization Techniques in Engineering". Retrieved 17 September 2016.
- ↑ Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3
- ↑ S. Das and P. N. Suganthan, "Differential Evolution: A Survey of the State-of-the-art", IEEE Trans. on Evolutionary Computation, Vol. 15, No. 1, pp. 4-31, Feb. 2011, DOI: 10.1109/TEVC.2010.2059031.
- ↑ S. Das, S. S. Mullick, P. N. Suganthan, "Recent Advances in Differential Evolution - An Updated Survey," Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.
- ↑ Liu, J.; Lampinen, J. (2002). "On setting the control parameter of the differential evolution method". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 11–18.
- ↑ Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67.
