Estimation of distribution algorithm
वितरण एल्गोरिदम (ईडीए) का अनुमान, जिसे कभी-कभी संभावित मॉडल-निर्माण आनुवंशिक एल्गोरिदम (पीएमबीजीए) कहा जाता है, यादृच्छिक अनुकूलन विधियां हैं जो आशाजनक उम्मीदवार समाधानों के स्पष्ट संभावित मॉडल का निर्माण और नमूना लेकर इष्टतम के लिए खोज का मार्गदर्शन करती हैं। अनुकूलन को एक संभावित मॉडल के वृद्धिशील अद्यतनों की एक श्रृंखला के रूप में देखा जाता है, जो स्वीकार्य समाधानों पर एक गैर-सूचनात्मक पूर्व एन्कोडिंग मॉडल से शुरू होता है और उस मॉडल के साथ समाप्त होता है जो केवल वैश्विक ऑप्टिमा उत्पन्न करता है। ईडीए विकासवादी एल्गोरिदम के वर्ग से संबंधित हैं। ईडीए और अधिकांश पारंपरिक विकासवादी एल्गोरिदम के बीच मुख्य अंतर यह है कि विकासवादी एल्गोरिदम एक या अधिक भिन्नता ऑपरेटरों द्वारा परिभाषित एक अंतर्निहित वितरण का उपयोग करके नए उम्मीदवार समाधान उत्पन्न करते हैं, जबकि ईडीए एक बायेसियन नेटवर्क, एक बहुभिन्न सामान्य वितरण, या किसी अन्य मॉडल वर्ग द्वारा एन्कोड किए गए एक स्पष्ट संभावना वितरण का उपयोग करते हैं। इसी तरह अन्य विकासवादी एल्गोरिदम की तरह, ईडीए का उपयोग वैक्टर से लेकर एलआईएसपी शैली एस अभिव्यक्तियों तक कई प्रतिनिधित्वों पर परिभाषित अनुकूलन समस्याओं को हल करने के लिए किया जा सकता है, और उम्मीदवार समाधानों की गुणवत्ता का मूल्यांकन अक्सर एक या अधिक वस्तुनिष्ठ कार्यों का उपयोग करके किया जाता है। ई. डी. ए. की सामान्य प्रक्रिया को निम्नलिखित में रेखांकित किया गया हैः टीः = 0 मॉडल एम (0) को स्वीकार्य समाधानों पर समान वितरण का प्रतिनिधित्व करने के लिए आरंभ करें जबकि (समाप्ति मानदंड पूरा नहीं हुआ) पीः = एम (टी) एफः = नमूना लेकर एन> 0 उम्मीदवार समाधान उत्पन्न करें पी. एम. में सभी उम्मीदवार समाधानों का मूल्यांकन करें (टी + 1): = एडजस्ट मॉडल (पी, एफ, एम (टी)) टीः = टी + 1 अनुकूलन में स्पष्ट संभावित मॉडल का उपयोग करने से ई. डी. ए. को अनुकूलन समस्याओं को हल करने की अनुमति मिली जो अधिकांश पारंपरिक विकासवादी एल्गोरिदम और पारंपरिक अनुकूलन तकनीकों के लिए कुख्यात रूप से कठिन थीं, जैसे कि उच्च स्तर के एपिस्टेसिस के साथ समस्याएं। फिर भी, ईडीए का लाभ यह भी है कि ये एल्गोरिदम संभावित मॉडल की एक श्रृंखला के साथ एक अनुकूलन व्यवसायी प्रदान करते हैं जो हल की जा रही समस्या के बारे में बहुत सारी जानकारी प्रकट करते हैं। इस जानकारी का उपयोग स्थानीय खोज के लिए समस्या-विशिष्ट पड़ोस ऑपरेटरों को डिजाइन करने के लिए किया जा सकता है, किसी समान समस्या पर ईडीए के भविष्य के संचालन को पूर्वाग्रहित करने के लिए, या समस्या का एक कुशल कम्प्यूटेशनल मॉडल बनाने के लिए किया जा सकता है। उदाहरण के लिए, यदि जनसंख्या को लंबाई 4 के बिट स्ट्रिंग्स द्वारा दर्शाया जाता है, तो ईडीए चार संभावनाओं (पी1, पी2, पी3, पी4) के एकल वेक्टर का उपयोग करके आशाजनक समाधान की जनसंख्या का प्रतिनिधित्व कर सकता है, जहां पी का प्रत्येक घटक उस स्थिति के 1 होने की संभावना को परिभाषित करता है। इस संभाव्यता सदिश का उपयोग करके उम्मीदवार समाधानों की एक मनमाना संख्या बनाना संभव है। वितरण एल्गोरिदम का अनुमान (ई. डी. ए.) यह खंड जटिलता के विभिन्न स्तरों के कुछ प्रसिद्ध ई. डी. ए. द्वारा निर्मित मॉडल का वर्णन करता है। यह हमेशा पीढ़ी में एक जनसंख्या, एक चयन ऑपरेटर, एक मॉडल-निर्माण ऑपरेटर और एक नमूना ऑपरेटर माना जाता है। सबसे सरल ई. डी. ए. मानते हैं कि निर्णय चर स्वतंत्र हैं, अर्थात। .. इसलिए, यूनिवेरिएट ईडीए केवल यूनिवेरिएट सांख्यिकी पर निर्भर करते हैं और मल्टीवेरिएट वितरण को यूनिवेरिएट प्रायिकता वितरण के उत्पाद के रूप में फैक्टराइज़ किया जाना चाहिए, इस तरह के फैक्टराइजेशन का उपयोग कई अलग-अलग ईडीए में किया जाता है, इसके बाद हम उनमें से कुछ का वर्णन करते हैं। यूनिवेरिएट मार्जिनल डिस्ट्रीब्यूशन एल्गोरिदम (यू. एम. डी. ए.) यू. एम. डी. ए. एक सरल ई. डी. ए. है जो एक चयनित आबादी से सीमांत संभावनाओं का अनुमान लगाने के लिए एक प्रचालक का उपयोग करता है। यह मानते हुए कि इसमें तत्व शामिल हैं, संभावनाएं पैदा करते हैंः यू. एम. डी. ए. के प्रत्येक चरण को जनसंख्या-आधारित वृद्धिशील शिक्षा (पी. बी. आई. एल.) के रूप में वर्णित किया जा सकता है। पी. बी. आई. एल. अपने मॉडल द्वारा जनसंख्या का प्रतिनिधित्व करता है, जिससे यह नए समाधानों का नमूना लेता है और मॉडल को अद्यतन करता है। प्रत्येक पीढ़ी में, व्यक्तियों का नमूना लिया जाता है और उनका चयन किया जाता है। फिर ऐसे व्यक्तियों का उपयोग मॉडल को निम्नानुसार अद्यतन करने के लिए किया जाता है जहां सीखने की दर को परिभाषित करने वाला एक पैरामीटर है, एक छोटा मूल्य निर्धारित करता है कि पिछले मॉडल को नए समाधानों के नमूने द्वारा केवल थोड़ा संशोधित किया जाना चाहिए। पी. बी. आई. एल. को कॉम्पैक्ट जेनेटिक एल्गोरिदम (सी. जी. ए.) के रूप में वर्णित किया जा सकता है सी. जी. ए., अविभाज्य वितरण द्वारा परिभाषित अंतर्निहित आबादी पर भी निर्भर करता है। प्रत्येक पीढ़ी में, दो व्यक्तियों का नमूना लिया जाता है। आबादी को तब स्वास्थ्य के घटते क्रम में क्रमबद्ध किया जाता है, जिसमें सबसे अच्छा और सबसे खराब समाधान होता है। सी. जी. ए. निम्नलिखित रूप से अविभाज्य संभावनाओं का अनुमान लगाता है जहाँ, सीखने की दर को परिभाषित करने के लिए एक निरंतरता है, जिसे आमतौर पर निर्धारित किया जाता है। सी. जी. ए. को बाइवेरिएट फैक्टराइजेशन के रूप में परिभाषित किया जा सकता है, हालांकि यूनिवेरिएट मॉडल की गणना कुशलता से की जा सकती है, कई मामलों में वे जी. ए. की तुलना में बेहतर प्रदर्शन प्रदान करने के लिए पर्याप्त प्रतिनिधि नहीं हैं। इस तरह की कमी को दूर करने के लिए, ईडीए समुदाय में द्वि-भिन्न गुणनखंडन का उपयोग प्रस्तावित किया गया था, जिसमें चर के जोड़े के बीच निर्भरता को मॉडल किया जा सकता है। एक द्विभिन्नरूपी गुणनखंडन को निम्नानुसार परिभाषित किया जा सकता है, जहां एक संभावित चर निर्भर करता है, अर्थात। .. द्विभिन्नरूपी और बहुभिन्नरूपी वितरणों को आमतौर पर संभावित चित्रमय मॉडल (ग्राफ) के रूप में दर्शाया जाता है, जिसमें किनारे सांख्यिकीय निर्भरताओं (या सशर्त संभावनाओं) को दर्शाते हैं और शीर्ष चर को दर्शाते हैं। पी. जी. एम. की संरचना को जानने के लिए डेटा लिंकेज-लर्निंग का उपयोग किया जाता है। म्यूचुअल इन्फॉर्मेशन मैक्सिमाइज़िंग इनपुट क्लस्टरिंग (एम. आई. एम. आई. सी.) एम. आई. एम. आई. सी. चरों के बीच क्रमिक निर्भरताओं का प्रतिनिधित्व करने वाले श्रृंखला जैसे मॉडल में संयुक्त संभावना वितरण को फैक्टराइज़ करता है। यह निर्णय चर का एक क्रमपरिवर्तन पाता है, जैसे कि वास्तविक संभाव्यता वितरण के संबंध में कुलबैक-लीबलर विचलन को कम करता है, अर्थात। .. एम. आई. एम. आई. सी. मॉडल एक वितरण नए समाधानों का नमूना सबसे बाएँ से सबसे दाएँ चर तक लिया जाता है, पहला स्वतंत्र रूप से उत्पन्न होता है और अन्य सशर्त संभावनाओं के अनुसार। चूँकि अनुमानित वितरण की प्रत्येक पीढ़ी को फिर से गणना की जानी चाहिए, एम. आई. एम. आई. सी. निम्नलिखित तरीके से ठोस आबादी का उपयोग करता है बाइवेरिएट मार्जिनल डिस्ट्रीब्यूशन एल्गोरिदम (बी. एम. डी. ए.) बी. एम. डी. ए. बाइवेरिएट डिस्ट्रीब्यूशन में संयुक्त संभावना वितरण को फैक्टराइज़ करता है। सबसे पहले, एक यादृच्छिक रूप से चुने गए चर को ग्राफ में एक नोड के रूप में जोड़ा जाता है, ग्राफ में उनमें से एक के लिए सबसे अधिक निर्भर चर को उन लोगों के बीच चुना जाता है जो अभी तक ग्राफ में नहीं हैं, इस प्रक्रिया को तब तक दोहराया जाता है जब तक कि कोई भी शेष चर ग्राफ में किसी भी चर पर निर्भर नहीं करता है (एक सीमा मूल्य के अनुसार सत्यापित)। परिणामी मॉडल एक जंगल है जिसमें कई पेड़ों की जड़ें हैं। गैर-मूल चर को ध्यान में रखते हुए, बीएमडीए एक फैक्टराइज्ड वितरण का अनुमान लगाता है जिसमें मूल चर को स्वतंत्र रूप से नमूना लिया जा सकता है, जबकि अन्य सभी को मूल चर के लिए अनुकूलित किया जाना चाहिए। बी. एम. डी. ए. के प्रत्येक चरण को निम्नलिखित रूप में परिभाषित किया गया है बहुभिन्नरूपी गुणनखंडन ई. डी. ए. के विकास का अगला चरण बहुभिन्नरूपी गुणनखण्डन का उपयोग था। इस मामले में, संयुक्त संभाव्यता वितरण को आमतौर पर सीमित आकार के कई घटकों में फैक्टराइज़ किया जाता है। बहुभिन्नरूपी वितरणों को कूटबद्ध करने वाले पी. जी. एम. को सीखना एक कम्प्यूटेशनल रूप से महंगा काम है, इसलिए, ई. डी. ए. के लिए द्विभिन्नरूपी आंकड़ों से बहुभिन्नरूपी आंकड़ों का अनुमान लगाना सामान्य है। इस तरह की छूट पी. जी. एम. को बहुपद समय में बनाने की अनुमति देती है; हालाँकि, यह ऐसे ई. डी. ए. की व्यापकता को भी सीमित करता है। एक्सटेंडेड कॉम्पैक्ट जेनेटिक एल्गोरिदम (ई. सी. जी. ए.) ई. सी. जी. ए. मल्टीवेरिएट फैक्टराइजेशन को नियोजित करने वाले पहले ई. डी. ए. में से एक था, जिसमें निर्णय चर के बीच उच्च-क्रम निर्भरताओं को मॉडल किया जा सकता है। इसका दृष्टिकोण बहुभिन्नरूपी सीमांत वितरण के उत्पाद में संयुक्त संभाव्यता वितरण को कारक बनाता है। मान लीजिए कि यह उपसमुच्चय का एक समूह है, जिसमें प्रत्येक एक संयोजन समूह है, जिसमें चर होते हैं। फैक्टराइज्ड ज्वाइंट प्रोबेबिलिटी डिस्ट्रीब्यूशन को निम्नानुसार दर्शाया गया है ईसीजीए ने "लिंकेज-लर्निंग" शब्द को उन प्रक्रियाओं को दर्शाने के रूप में लोकप्रिय बनाया जो लिंकेज सेट की पहचान करते हैं। इसकी लिंकेज-लर्निंग प्रक्रिया दो उपायों पर निर्भर करती हैः (1) मॉडल जटिलता (एमसी) और (2) संपीड़ित जनसंख्या जटिलता (सीपीसी)। एमसी सभी सीमांत संभावनाओं को संग्रहीत करने के लिए आवश्यक बिट्स की संख्या के संदर्भ में मॉडल प्रतिनिधित्व के आकार की मात्रा निर्धारित करता है दूसरी ओर सीपीसी, सभी विभाजनों पर सीमांत वितरण की एन्ट्रापी के संदर्भ में डेटा संपीड़न की मात्रा निर्धारित करता है, जहां चयनित जनसंख्या का आकार है, लिंकेज सेट में निर्णय चर की संख्या है और वेरिएबल्स की संयुक्त एन्ट्रापी है। ईसीजीए में लिंकेज-लर्निंग इस प्रकार काम करती हैः (1) प्रत्येक चर को एक समूह में डालें, (2) वर्तमान लिंकेज सेट के सीसीसी = एमसी + सीपीसी की गणना करें, (3) समूहों के जोड़े को जोड़कर प्रदान किए गए सीसीसी पर वृद्धि को सत्यापित करें, (4) प्रभावी रूप से उच्चतम सीसीसी सुधार वाले समूहों में शामिल हों। इस प्रक्रिया को तब तक दोहराया जाता है जब तक कि कोई सी. सी. सी. सुधार संभव नहीं होता है और एक लिंकेज मॉडल का उत्पादन नहीं होता है। ई. सी. जी. ए. ठोस आबादी के साथ काम करता है, इसलिए, ई. सी. जी. ए. द्वारा फैक्टराइज्ड वितरण मॉडल का उपयोग करके, इसे बायेसियन अनुकूलन एल्गोरिदम (बी. ओ. ए.) के रूप में वर्णित किया जा सकता है। बी. ओ. ए. आशाजनक समाधानों को मॉडल और नमूना बनाने के लिए बायेसियन नेटवर्क का उपयोग करता है। बायेसियन नेटवर्क चक्रीय ग्राफ निर्देशित होते हैं, जिसमें चर का प्रतिनिधित्व करने वाले नोड्स और चर की जोड़ी के बीच सशर्त संभावनाओं का प्रतिनिधित्व करने वाले किनारे होते हैं। एक चर का मूल्य अधिकतम अन्य चर पर निर्धारित किया जा सकता है, जिसमें परिभाषित किया गया है। बी. ओ. ए. एक पी. जी. एम. एन्कोडिंग बनाता है जो एक फैक्टराइज्ड संयुक्त वितरण है, जिसमें नेटवर्क के मापदंड, अर्थात। सशर्त संभावनाओं का अनुमान, अधिकतम संभावना अनुमानक का उपयोग करके चयनित आबादी से लगाया जाता है। दूसरी ओर, बायेसियन नेटवर्क संरचना को बार-बार (लिंकेज-लर्निंग) बनाया जाना चाहिए। यह किनारों के बिना एक नेटवर्क के साथ शुरू होता है और प्रत्येक चरण में, किनारे को जोड़ता है जो कुछ स्कोरिंग मीट्रिक में बेहतर सुधार करता है (जैसे। बायेसियन सूचना मानदंड (बी. आई. सी.) या संभावना समतुल्यता (बी. डी. ई.) के साथ बायेसियन-डिरिचलेट मीट्रिक। स्कोरिंग मीट्रिक चयनित आबादी के मॉडलिंग में इसकी सटीकता के अनुसार नेटवर्क संरचना का मूल्यांकन करता है। निर्मित नेटवर्क से, बी. ओ. ए. निम्नानुसार नए आशाजनक समाधानों का नमूना लेता हैः (1) यह प्रत्येक चर के लिए पैतृक क्रम की गणना करता है, प्रत्येक नोड अपने माता-पिता से पहले होता है; (2) प्रत्येक चर को अपने माता-पिता के लिए सशर्त रूप से नमूना लिया जाता है। इस तरह के परिदृश्य को देखते हुए, प्रत्येक बी. ओ. ए. चरण को लिंकेज-ट्री जेनेटिक एल्गोरिदम (एल. टी. जी. ए.) के रूप में परिभाषित किया जा सकता है एल. टी. जी. ए. अधिकांश ई. डी. ए. से इस अर्थ में अलग है कि यह स्पष्ट रूप से एक संभाव्यता वितरण का मॉडल नहीं है, बल्कि केवल एक लिंकेज मॉडल है, जिसे लिंकेज-ट्री कहा जाता है। एक लिंकेज लिंकेज सेट का एक समूह है जिसमें कोई प्रायिकता वितरण नहीं जुड़ा हुआ है, इसलिए, सीधे नए समाधानों का नमूना लेने का कोई तरीका नहीं है। लिंकेज मॉडल एक लिंकेज-ट्री है जिसे सेटों के परिवार (एफ. ओ. एस.) के रूप में संग्रहीत किया जाता है। लिंकेज-ट्री लर्निंग प्रक्रिया एक पदानुक्रमित क्लस्टरिंग एल्गोरिदम है, जो निम्नानुसार काम करती है। प्रत्येक चरण में दो निकटतम समूहों का विलय हो जाता है, यह प्रक्रिया तब तक दोहराई जाती है जब तक कि केवल एक समूह नहीं रह जाता है, प्रत्येक उप-वृक्ष को एक उपसमुच्चय के रूप में संग्रहीत किया जाता है। एल. टी. जी. ए. एक "इष्टतम मिश्रण" प्रक्रिया का मार्गदर्शन करने के लिए उपयोग करता है जो एक पुनर्संयोजन प्रचालक जैसा दिखता है लेकिन केवल सुधार की चालों को स्वीकार करता है। हम इसे इस रूप में दर्शाते हैं, जहां संकेतन से अनुक्रमित आनुवंशिक सामग्री के हस्तांतरण को इंगित करता है। इनपुटः उपसमुच्चय और जनसंख्या का एक परिवार आउटपुटः एक जनसंख्या। एल. टी. जी. ए. विशिष्ट चयन प्रचालक को लागू नहीं करता है, इसके बजाय, चयन पुनर्संयोजन के दौरान किया जाता है। इसी तरह के विचारों को आमतौर पर स्थानीय-खोज शोध विज्ञान में लागू किया गया है और इस अर्थ में, एल. टी. जी. ए. को एक संकर विधि के रूप में देखा जा सकता है। संक्षेप में, एल. टी. जी. ए. के एक चरण को अन्य संभाव्यता समूह (पी. सी.) सीखने के साथ पहाड़ी चढ़ाई (एच. सी. डब्ल्यू. एल.) बहुभिन्न सामान्य एल्गोरिदम (ई. एम. एन. ए.) का अनुमान बायेसियन नेटवर्क एल्गोरिदम (ई. बी. एन. ए.) का अनुमान सामान्य वितरण के वैक्टरों द्वारा सीखने के साथ यादृच्छिक पहाड़ी चढ़ाई (एस. एच. सी. एल. वी. एन. डी.) वास्तविक-कोडित पी. बी. आई. एल. स्वार्थी जीन एल्गोरिदम (एस. जी.) कॉम्पैक्ट पार्टिकल डिफरेंशियल इवोल्यूशन (सी. डी. ई.) और इसके रूपों कॉम्पैक्ट पार्टिकल स्वार्म ऑप्टिमाइजेशन (सी. पी. एस. ओ.) कॉम्पैक्ट बैक्टीरियल फोर्जिंग ऑप्टिमाइजेशन (सी. बी. एफ. ओ.) संभाव्यता वृद्धि कार्यक्रम विकास (पी. आई. पी. ई.) गौसियन का अनुमान के रूप में परिभाषित किया गया है।