विभेदक विकास

File:Ackley.gif

विभेदक विकास 2डी एकली समारोह को अनुकूलित करता है।

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

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

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

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

एल्गोरिथम

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

औपचारिक रूप से, मान लो $f:\mathbb {R} ^{n}\to \mathbb {R}$ फिटनेस फ़ंक्शन हो जिसे न्यूनतम किया जाना चाहिए (ध्यान दें कि फ़ंक्शन पर विचार करके अधिकतमकरण किया जा सकता है $h:=-f$ बजाय)। फ़ंक्शन उम्मीदवार समाधान को वास्तविक संख्याओं के पंक्ति वेक्टर के रूप में तर्क के रूप में लेता है और आउटपुट के रूप में वास्तविक संख्या उत्पन्न करता है जो दिए गए उम्मीदवार समाधान की उपयुक्तता को इंगित करता है। $f$ का प्रवणता ज्ञात नहीं है। लक्ष्य $\mathbf {m}$ समाधान खोजना है जिसके लिए $f(\mathbf {m} )\leq f(\mathbf {p} )$ सभी के लिए $\mathbf {p}$ खोज-स्थान में, जिसका अर्थ है की $\mathbf {m}$ वैश्विक न्यूनतम है।

मान ले $\mathbf {x} \in \mathbb {R} ^{n}$ जनसंख्या में उम्मीदवार समाधान (एजेंट) नामित करें। मूल डीई एल्गोरिथ्म को तब निम्नानुसार वर्णित किया जा सकता है:

• पैरामीटर चुनें ${\text{NP}}\geq 4$, ${\text{CR}}\in [0,1]$, और $F\in [0,2]$.
  • ${\text{NP}}$ जनसंख्या का आकार है, अर्थात उम्मीदवारों के एजेंटों या माता-पिता की संख्या; विशिष्ट सेटिंग 10$n$ है.
  • पैरामीटर ${\text{CR}}\in [0,1]$ क्रॉसओवर संभावना और पैरामीटर कहा जाता है $F\in [0,2]$ अंतर भार कहा जाता है। विशिष्ट सेटिंग्स $F=0.8$ और $CR=0.9$ हैं.
  • इन विकल्पों से अनुकूलन प्रदर्शन बहुत प्रभावित हो सकता है; नीचे देखें।
• खोज-स्थान में यादृच्छिक स्थिति के साथ सभी एजेंटों $\mathbf {x}$ को प्रारंभ करें ।
• जब तक समाप्ति मानदंड पूरा नहीं हो जाता (उदाहरण के लिए किए गए पुनरावृत्तियों की संख्या, या पर्याप्त फिटनेस तक पहुंच गया), निम्नलिखित को दोहराएं:
  • प्रत्येक एजेंट के लिए $\mathbf {x}$ जनसंख्या में करते हैं:
    • तीन एजेंट चुनें $\mathbf {a} ,\mathbf {b}$, और $\mathbf {c}$ यादृच्छिक रूप से जनसंख्या से, उन्हें दूसरे के साथ-साथ $\mathbf {x}$ एजेंट से भी अलग होना चाहिए. ($\mathbf {a}$ बेस वेक्टर कहा जाता है।)
    • यादृच्छिक $R\in \{1,\ldots ,n\}$ सूचकांक चुनें जहाँ $n$ समस्या का आयाम अनुकूलित किया जा रहा है।
    • एजेंट की संभावित नई स्थिति $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ की गणना करें निम्नलिखितनुसार:
      • प्रत्येक के लिए $i\in \{1,\ldots ,n\}$, समान रूप से वितरित यादृच्छिक $r_{i}\sim U(0,1)$संख्या चुनें
      • अगर $r_{i}<CR$ या $i=R$ फिर सेट करें $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ अन्यथा $y_{i}=x_{i}$ सेट करें. (सूचकांक स्थिति $R$ निश्चित रूप से प्रतिस्थापित किया गया है।)
    • अगर $f(\mathbf{y})\le <!--\; \le \; -->$