विभेदक विकास: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (6 intermediate revisions by 4 users not shown) | |||
| 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> | ||
== | == कलन विधि == | ||
डीई | डीई कलन विधि का मूल संस्करण [[उम्मीदवार समाधान|उम्मीदवार समाधानों]] (जिन्हें प्रतिनिधि कहा जाता है) की स्थिति होने से काम करता है। जनसंख्या से वर्तमान प्रतिनिधियों की स्थिति को संयोजित करने के लिए सरल गणितीय सूत्रों का उपयोग करके इन प्रतिनिधियों को खोज-स्थान में इधर-उधर ले जाया जाता है। यदि किसी प्रतिनिधि की नई स्थिति में सुधार होता है तो उसे स्वीकार कर लिया जाता है और वह जनसंख्या का भाग बन जाता है, अन्यथा नई स्थिति को यूं ही छोड़ दिया जाता है। प्रक्रिया को दोहराया जाता है और ऐसा करने से यह आशा की जाती है, लेकिन इसकी गारंटी नहीं है कि अंत में संतोषजनक समाधान खोज लिया जाएगा। | ||
औपचारिक रूप से, मान लो <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> जनसंख्या में उम्मीदवार समाधान (प्रतिनिधि) नामित करें। मूल डीई एल्गोरिथ्म को तब निम्नानुसार वर्णित किया जा सकता है: | ||
* पैरामीटर चुनें <math>\text{NP} \geq 4</math>, <math>\text{CR} \in [0,1]</math>, और <math>F \in [0,2]</math>. | * पैरामीटर चुनें <math>\text{NP} \geq 4</math>, <math>\text{CR} \in [0,1]</math>, और <math>F \in [0,2]</math>. | ||
** <math>\text{NP} </math> जनसंख्या का आकार है, अर्थात उम्मीदवारों के | ** <math>\text{NP} </math> जनसंख्या का आकार है, अर्थात उम्मीदवारों के प्रतिनिधियों या माता-पिता की संख्या; विशिष्ट सेटिंग 10<math>n</math> है. | ||
** पैरामीटर <math>\text{CR} \in [0,1]</math> क्रॉसओवर संभावना और पैरामीटर कहा जाता है <math>F \in [0,2]</math> अंतर भार कहा जाता है। विशिष्ट सेटिंग्स <math>F = 0.8</math> और <math>CR = 0.9</math> हैं. | ** पैरामीटर <math>\text{CR} \in [0,1]</math> क्रॉसओवर संभावना और पैरामीटर कहा जाता है <math>F \in [0,2]</math> अंतर भार कहा जाता है। विशिष्ट सेटिंग्स <math>F = 0.8</math> और <math>CR = 0.9</math> हैं. | ||
** इन विकल्पों से अनुकूलन प्रदर्शन बहुत प्रभावित हो सकता है; नीचे देखें। | ** इन विकल्पों से अनुकूलन प्रदर्शन बहुत प्रभावित हो सकता है; नीचे देखें। | ||
* खोज-स्थान में यादृच्छिक स्थिति के साथ सभी | * खोज-स्थान में यादृच्छिक स्थिति के साथ सभी प्रतिनिधियों <math>\mathbf{x}</math> को प्रारंभ करें । | ||
* जब तक समाप्ति मानदंड पूरा नहीं हो जाता (उदाहरण के लिए किए गए पुनरावृत्तियों की संख्या, या पर्याप्त फिटनेस तक पहुंच गया), निम्नलिखित को दोहराएं: | * जब तक समाप्ति मानदंड पूरा नहीं हो जाता (उदाहरण के लिए किए गए पुनरावृत्तियों की संख्या, या पर्याप्त फिटनेस तक पहुंच गया), निम्नलिखित को दोहराएं: | ||
** प्रत्येक | ** प्रत्येक प्रतिनिधि के लिए <math>\mathbf{x}</math> जनसंख्या में करते हैं: | ||
*** तीन | *** तीन प्रतिनिधि चुनें <math>\mathbf{a},\mathbf{b}</math>, और <math>\mathbf{c}</math> यादृच्छिक रूप से जनसंख्या से, उन्हें दूसरे के साथ-साथ <math>\mathbf{x}</math> प्रतिनिधि से भी अलग होना चाहिए. (<math>\mathbf{a}</math> बेस वेक्टर कहा जाता है।) | ||
*** यादृच्छिक <math>R \in \{1, \ldots, n\}</math> सूचकांक चुनें जहाँ <math>n</math> समस्या का आयाम अनुकूलित किया जा रहा है। | *** यादृच्छिक <math>R \in \{1, \ldots, n\}</math> सूचकांक चुनें जहाँ <math>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/> | ||
== प्रकार == | == प्रकार == | ||
अनुकूलन प्रदर्शन को बेहतर बनाने के प्रयास में डीई एल्गोरिद्म के प्रकार लगातार विकसित किए जा रहे हैं। ऊपर दिए गए मूल | अनुकूलन प्रदर्शन को बेहतर बनाने के प्रयास में डीई एल्गोरिद्म के प्रकार लगातार विकसित किए जा रहे हैं। ऊपर दिए गए मूल कलन विधि में प्रतिनिधियों के क्रॉसओवर और उत्परिवर्तन करने के लिए कई अलग-अलग योजनाएं संभव हैं, उदाहरण के लिए देखें<ref name=storn96usage/> | ||
| Line 167: | Line 166: | ||
{{Major subfields of optimization}} | {{Major subfields of optimization}} | ||
{{DEFAULTSORT:Differential Evolution}} | {{DEFAULTSORT:Differential Evolution}} | ||
[[Category:Collapse templates|Differential Evolution]] | |||
[[Category:Created On 13/02/2023|Differential Evolution]] | |||
[[Category: | [[Category:Machine Translated Page|Differential Evolution]] | ||
[[Category:Created On 13/02/2023]] | [[Category:Navigational boxes| ]] | ||
[[Category:Navigational boxes without horizontal lists|Differential Evolution]] | |||
[[Category:Pages with script errors|Differential Evolution]] | |||
[[Category:Sidebars with styles needing conversion|Differential Evolution]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats|Differential Evolution]] | |||
[[Category:Templates that are not mobile friendly|Differential Evolution]] | |||
[[Category:Templates using TemplateData|Differential Evolution]] | |||
[[Category:Wikipedia metatemplates|Differential Evolution]] | |||
[[Category:विकासवादी एल्गोरिदम|Differential Evolution]] | |||
Latest revision as of 10:32, 24 February 2023
File:Ackley.gif
विभेदक विकास 2डी एकली फलन को अनुकूलित करता है।
विकासवादी गणना में, विभेदक विकास (डीई) ऐसी विधि है जो गुणवत्ता के दिए गए माप के संबंध में उम्मीदवार समाधान को सुधार करने का प्रयास कर समस्या का अनुकूलन (गणित) करती है। इस प्रकार के विधियों को सामान्यतः मेटाह्यूरिस्टिक्स के रूप में जाना जाता है क्योंकि वे समस्या को अनुकूलित करने के बारे में कुछ या कोई धारणा नहीं बनाते हैं और उम्मीदवार समाधानों के बहुत बड़े स्थान खोज सकते हैं। चूंकि, डीई जैसे मेटाह्यूरिस्टिक्स इस बात की गारंटी नहीं देते हैं कि इष्टतम समाधान कभी भी मिल जाएगा।
डीई का उपयोग बहुआयामी वास्तविक-मूल्यवान फलन (गणित) के लिए किया जाता है, लेकिन अनुकूलित होने वाली समस्या के प्रवणता का उपयोग नहीं करता है, जिसका अर्थ है कि डीई को अलग-अलग कार्य करने के लिए अनुकूलन समस्या की आवश्यकता नहीं होती है, जैसा कि प्रवणता अवरोहण और अर्ध-न्यूटन विधियों पारंपरिक अनुकूलन विधियों द्वारा आवश्यक है। इसलिए डीई का उपयोग अनुकूलन समस्याओं पर भी किया जा सकता है जो निरंतर भी नहीं हैं, जैसे ध्वनी हैं, जो समय के साथ बदलते हैं, आदि।[1]
डीई उम्मीदवारों के समाधानों की स्थिति को बनाए रखने और अपने सरल सूत्रों के अनुसार वर्तमान लोगों को जोड़कर नए उम्मीदवार समाधान बनाकर समस्या का अनुकूलन करता है, और फिर जो भी उम्मीदवार समाधान हाथ में अनुकूलन समस्या पर सबसे अच्छा स्कोर या फिटनेस रखता है। इस प्रकार, अनुकूलन समस्या को समकालिंक प्रस्फुटन प्रक्रम के रूप में माना जाता है जो उम्मीदवार समाधान को दिए गए गुणवत्ता का उपाय प्रदान करता है और इसलिए प्रवणता की आवश्यकता नहीं होती है।
डीई को 1990 के दशक में स्टोर्न एंड प्राइस द्वारा प्रस्तुत किया गया था।[2][3] पुस्तकें समानांतर कंप्यूटिंग, बहुउद्देश्यीय अनुकूलन, विवश अनुकूलन में डीई का उपयोग करने के सैद्धांतिक और व्यावहारिक पहलुओं पर प्रकाशित की गई हैं, और पुस्तकों में अनुप्रयोग क्षेत्रों के सर्वेक्षण भी सम्मिलित हैं।[4][5][6][7] डीई के बहुआयामी अनुसंधान स्थितियों पर सर्वेक्षण जर्नल लेखों में पाए जा सकते हैं।[8][9]
कलन विधि
डीई कलन विधि का मूल संस्करण उम्मीदवार समाधानों (जिन्हें प्रतिनिधि कहा जाता है) की स्थिति होने से काम करता है। जनसंख्या से वर्तमान प्रतिनिधियों की स्थिति को संयोजित करने के लिए सरल गणितीय सूत्रों का उपयोग करके इन प्रतिनिधियों को खोज-स्थान में इधर-उधर ले जाया जाता है। यदि किसी प्रतिनिधि की नई स्थिति में सुधार होता है तो उसे स्वीकार कर लिया जाता है और वह जनसंख्या का भाग बन जाता है, अन्यथा नई स्थिति को यूं ही छोड़ दिया जाता है। प्रक्रिया को दोहराया जाता है और ऐसा करने से यह आशा की जाती है, लेकिन इसकी गारंटी नहीं है कि अंत में संतोषजनक समाधान खोज लिया जाएगा।
औपचारिक रूप से, मान लो फिटनेस फलन हो जिसे न्यूनतम किया जाना चाहिए (ध्यान दें कि फलन पर विचार करके अधिकतमकरण किया जा सकता है अतिरिक्त)। फलन उम्मीदवार समाधान को वास्तविक संख्याओं के पंक्ति वेक्टर के रूप में तर्क के रूप में लेता है और आउटपुट के रूप में वास्तविक संख्या उत्पन्न करता है जो दिए गए उम्मीदवार समाधान की उपयुक्तता को निरुपित करता है। का प्रवणता ज्ञात नहीं है। लक्ष्य समाधान खोजना है जिसके लिए सभी के लिए खोज-स्थान में, जिसका अर्थ है की वैश्विक न्यूनतम है।
मान ले जनसंख्या में उम्मीदवार समाधान (प्रतिनिधि) नामित करें। मूल डीई एल्गोरिथ्म को तब निम्नानुसार वर्णित किया जा सकता है:
- पैरामीटर चुनें , , और .
- जनसंख्या का आकार है, अर्थात उम्मीदवारों के प्रतिनिधियों या माता-पिता की संख्या; विशिष्ट सेटिंग 10 है.
- पैरामीटर क्रॉसओवर संभावना और पैरामीटर कहा जाता है अंतर भार कहा जाता है। विशिष्ट सेटिंग्स और हैं.
- इन विकल्पों से अनुकूलन प्रदर्शन बहुत प्रभावित हो सकता है; नीचे देखें।
- खोज-स्थान में यादृच्छिक स्थिति के साथ सभी प्रतिनिधियों को प्रारंभ करें ।
- जब तक समाप्ति मानदंड पूरा नहीं हो जाता (उदाहरण के लिए किए गए पुनरावृत्तियों की संख्या, या पर्याप्त फिटनेस तक पहुंच गया), निम्नलिखित को दोहराएं:
- प्रत्येक प्रतिनिधि के लिए