वैश्विक अनुकूलन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 4: Line 4:
एक संभावित गैर-रैखिक और गैर-उत्तल निरंतर कार्य दिया गया <math>f:\Omega\subset\mathbb{R}^n\to\mathbb{R}</math> वैश्विक न्यूनतम के साथ <math>f^*</math> और सभी ग्लोबल मिनिमाइज़र का समुच्चय <math>X^*</math> में <math>\Omega</math>, मानक न्यूनीकरण समस्या के रूप में दिया जा सकता है
एक संभावित गैर-रैखिक और गैर-उत्तल निरंतर कार्य दिया गया <math>f:\Omega\subset\mathbb{R}^n\to\mathbb{R}</math> वैश्विक न्यूनतम के साथ <math>f^*</math> और सभी ग्लोबल मिनिमाइज़र का समुच्चय <math>X^*</math> में <math>\Omega</math>, मानक न्यूनीकरण समस्या के रूप में दिया जा सकता है
:<math>\min_{x\in\Omega}f(x),</math>
:<math>\min_{x\in\Omega}f(x),</math>
अर्थात् खोजना <math>f^*</math> और एक वैश्विक न्यूनतमकर्ता <math>X^*</math>; जहा <math>\Omega</math> असमानताओं द्वारा परिभाषित एक (जरूरी नहीं उत्तल) कॉम्पैक्ट समुच्चय है <math>g_i(x)\geqslant0, i=1,\ldots,r</math>.
अर्थात् खोजना <math>f^*</math> और एक वैश्विक न्यूनतमकर्ता <math>X^*</math>; जहा <math>\Omega</math> असमानताओं द्वारा परिभाषित एक (आवश्यक  नहीं उत्तल) कॉम्पैक्ट समुच्चय है <math>g_i(x)\geqslant0, i=1,\ldots,r</math>.


ग्लोबल ऑप्टिमाइज़ेशन को स्थानीय ऑप्टिमाइज़ेशन से अलग किया जाता है, जो स्थानीय मिनिमा या मैक्सिमा खोजने के विरोध में दिए गए समुच्चय पर न्यूनतम या अधिकतम खोजने पर ध्यान केंद्रित करता है। शास्त्रीय स्थानीय अनुकूलन विधियों का उपयोग करके एक मनमानी स्थानीय न्यूनतम ढूँढना अपेक्षाकृत सरल है। किसी फलन का वैश्विक न्यूनतम पता लगाना अधिक कठिन है: विश्लेषणात्मक तरीके हमेशा लागू नहीं होते हैं, और संख्यात्मक समाधान रणनीतियों का उपयोग हमेशा बहुत कठिन चुनौतियों का कारण बनता है।
ग्लोबल ऑप्टिमाइज़ेशन को स्थानीय ऑप्टिमाइज़ेशन से अलग किया जाता है, जो स्थानीय मिनिमा या मैक्सिमा खोजने के विरोध में दिए गए समुच्चय पर न्यूनतम या अधिकतम खोजने पर ध्यान केंद्रित करता है। मौलिक स्थानीय अनुकूलन विधियों का उपयोग करके एक मनमानी स्थानीय न्यूनतम ढूँढना अपेक्षाकृत सरल है। किसी फलन का वैश्विक न्यूनतम पता लगाना अधिक कठिन है: विश्लेषणात्मक तरीके सदैव प्रयुक्त नहीं होते हैं, और संख्यात्मक समाधान रणनीतियों का उपयोग सदैव बहुत कठिन चुनौतियों का कारण बनता है।


== सामान्य सिद्धांत ==
== सामान्य सिद्धांत ==
Line 14: Line 14:
  |year = 2018
  |year = 2018
  |title = Minima distribution for global optimization
  |title = Minima distribution for global optimization
  |arxiv = 1812.03457}}</ref> इस काम में, किसी भी निरंतर कार्य के बीच संबंध <math>f</math> एक कॉम्पैक्ट समुच्चय पर <math>\Omega\subset\mathbb{R}^n</math> और इसकी वैश्विक न्यूनतम <math>f^*</math> कड़ाई से स्थापित किया गया है। एक विशिष्ट मामले के रूप में, यह इस प्रकार है
  |arxiv = 1812.03457}}</ref> इस काम में, किसी भी निरंतर कार्य के बीच संबंध <math>f</math> एक कॉम्पैक्ट समुच्चय पर <math>\Omega\subset\mathbb{R}^n</math> और इसकी वैश्विक न्यूनतम <math>f^*</math> कड़ाई से स्थापित किया गया है। एक विशिष्ट स्थितियों के रूप में, यह इस प्रकार है
:<math>
:<math>
\lim_{k\to\infty}\int_\Omega f(x)m^{(k)}(x) \, \mathrm{d}x=f^*,~~\textrm{where}~~m^{(k)}(x)=\frac{e^{-kf(x)}}{\int_\Omega e^{-kf(y)} \, \mathrm{d}y};
\lim_{k\to\infty}\int_\Omega f(x)m^{(k)}(x) \, \mathrm{d}x=f^*,~~\textrm{where}~~m^{(k)}(x)=\frac{e^{-kf(x)}}{\int_\Omega e^{-kf(y)} \, \mathrm{d}y};
Line 26: Line 26:
\end{array}\right.
\end{array}\right.
</math>
</math>
जहा  <math>\mu(X^*)</math> है <math>n</math>मिनिमाइज़र के समुच्चय का आयामी लेबेस्ग माप <math>X^*\in\Omega</math>. और अगर <math>f</math> स्थिर नहीं है <math>\Omega</math>, मोनोटोनिक संबंध
जहा  <math>\mu(X^*)</math> है <math>n</math>मिनिमाइज़र के समुच्चय का आयामी लेबेस्ग माप <math>X^*\in\Omega</math>. और यदि <math>f</math> स्थिर नहीं है <math>\Omega</math>, मोनोटोनिक संबंध
:<math>
:<math>
\int_\Omega f(x)m^{(k)}(x)\,\mathrm{d}x>
\int_\Omega f(x)m^{(k)}(x)\,\mathrm{d}x>
Line 41: Line 41:
<math>\Omega</math> में कॉम्पैक्ट समर्थन के साथ हर स्मूद फंक्शन <math>\varphi</math> के लिए रोक कर रखता  है। यहाँ <math>m_{f,\Omega}</math> के दो तात्कालिक गुण हैं,  
<math>\Omega</math> में कॉम्पैक्ट समर्थन के साथ हर स्मूद फंक्शन <math>\varphi</math> के लिए रोक कर रखता  है। यहाँ <math>m_{f,\Omega}</math> के दो तात्कालिक गुण हैं,  
: (1) <math>m_{f,\Omega}</math> पहचान को संतुष्ट करता है <math>\int_\Omega m_{f,\Omega}(x) \, \mathrm{d}x = 1</math>.
: (1) <math>m_{f,\Omega}</math> पहचान को संतुष्ट करता है <math>\int_\Omega m_{f,\Omega}(x) \, \mathrm{d}x = 1</math>.
: (2) अगर <math>f</math> निरंतर चालू है <math>\Omega</math>, तब <math>f^*=\int_\Omega f(x)m_{f,\Omega}(x) \, \mathrm{d}x</math>.
: (2) यदि <math>f</math> निरंतर चालू है <math>\Omega</math>, तब <math>f^*=\int_\Omega f(x)m_{f,\Omega}(x) \, \mathrm{d}x</math>.


एक तुलना के रूप में, किसी भी अलग-अलग उत्तल फलन और इसकी मिनीमा के बीच प्रसिद्ध संबंध ढाल द्वारा सख्ती से स्थापित किया जाता है।यदि f  उत्तल समुच्चय D  पर अवकलनीय है, तो f उत्तल है यदि और केवल यदि
एक तुलना के रूप में, किसी भी अलग-अलग उत्तल फलन और इसकी मिनीमा के बीच प्रसिद्ध संबंध ढाल द्वारा सख्ती से स्थापित किया जाता है।यदि f  उत्तल समुच्चय D  पर अवकलनीय है, तो f उत्तल है यदि और केवल यदि
Line 50: Line 50:


== अनुप्रयोग ==
== अनुप्रयोग ==
वैश्विक अनुकूलन अनुप्रयोगों के विशिष्ट उदाहरणों में शामिल हैं:
वैश्विक अनुकूलन अनुप्रयोगों के विशिष्ट उदाहरणों में सम्मिलित  हैं:
* प्रोटीन संरचना की भविष्यवाणी (ऊर्जा / मुक्त ऊर्जा समारोह को कम करें)
* प्रोटीन संरचना की भविष्यवाणी (ऊर्जा / मुक्त ऊर्जा समारोह को कम करें)
* [[कम्प्यूटेशनल फाइलोजेनेटिक्स]] (उदाहरण के लिए, पेड़ में वर्ण परिवर्तन की संख्या को कम करें)
* [[कम्प्यूटेशनल फाइलोजेनेटिक्स]] (उदाहरण के लिए, पेड़ में वर्ण परिवर्तन की संख्या को कम करें)
* [[ट्रैवलिंग सेल्समैन की समस्या]] और इलेक्ट्रिकल सर्किट डिजाइन (पथ की लंबाई कम करें)
* [[ट्रैवलिंग सेल्समैन की समस्या]] और इलेक्ट्रिकल परिपथ डिजाइन (पथ की लंबाई कम करें)
* [[केमिकल इंजीनियरिंग]] (जैसे, [[गिब्स मुक्त ऊर्जा]] का विश्लेषण)
* [[केमिकल इंजीनियरिंग]] (जैसे, [[गिब्स मुक्त ऊर्जा]] का विश्लेषण)
* सुरक्षा सत्यापन, [[सुरक्षा इंजीनियरिंग]] (जैसे, यांत्रिक संरचनाओं, भवनों की)
* सुरक्षा सत्यापन, [[सुरक्षा इंजीनियरिंग]] (जैसे, यांत्रिक संरचनाओं, भवनों की)
Line 59: Line 59:
* गणितीय समस्याएं (जैसे, केपलर अनुमान)
* गणितीय समस्याएं (जैसे, केपलर अनुमान)
* ऑब्जेक्ट पैकिंग (कॉन्फ़िगरेशन निर्माण) समस्याएं
* ऑब्जेक्ट पैकिंग (कॉन्फ़िगरेशन निर्माण) समस्याएं
* कई [[आणविक गतिकी]] सिमुलेशन के शुरुआती बिंदु में सिम्युलेटेड होने वाली प्रणाली की ऊर्जा का प्रारंभिक अनुकूलन होता है।
* कई [[आणविक गतिकी]] सिमुलेशन के प्राम्भिक बिंदु में सिम्युलेटेड होने वाली प्रणाली की ऊर्जा का प्रारंभिक अनुकूलन होता है।
* स्पिन चश्मा
* स्पिन चश्मा
* विज्ञान और इंजीनियरिंग में [[रेडियो प्रसार मॉडल]] और कई अन्य मॉडलों का अंशांकन
* विज्ञान और इंजीनियरिंग में [[रेडियो प्रसार मॉडल]] और कई अन्य मॉडलों का अंशांकन
Line 67: Line 67:
== नियतात्मक तरीके ==
== नियतात्मक तरीके ==
{{main article|नियतात्मक वैश्विक अनुकूलन}}
{{main article|नियतात्मक वैश्विक अनुकूलन}}
सबसे सफल सामान्य सटीक रणनीतियाँ हैं:
सबसे सफल सामान्य स्पष्ट रणनीतियाँ हैं:


=== भीतरी और बाहरी सन्निकटन ===
=== आंतरिक और बाहरी सन्निकटन ===
इन दोनों रणनीतियों में, जिस सेट पर एक फलन को अनुकूलित किया जाना है, वह पॉलीहेड्रा द्वारा अनुमानित है। आंतरिक सन्निकटन में, पॉलीहेड्रा सेट में समाहित होता है, जबकि बाहरी सन्निकटन में, पॉलीहेड्रा में सेट होता है।
इन दोनों रणनीतियों में, जिस समुच्चय पर एक फलन को अनुकूलित किया जाना है, वह पॉलीहेड्रा द्वारा अनुमानित है। आंतरिक सन्निकटन में, पॉलीहेड्रा समुच्चय में समाहित होता है, जबकि बाहरी सन्निकटन में, पॉलीहेड्रा में समुच्चय होता है।


=== कटिंग-प्लेन के तरीके ===
=== कटिंग-प्लेन के तरीके ===
Line 78: Line 78:
=== शाखा और बाध्य तरीके ===
=== शाखा और बाध्य तरीके ===
{{main article|शाखा और बंधन}}
{{main article|शाखा और बंधन}}
शाखा और बाउंड (बीबी या बी एंड बी) [[असतत अनुकूलन]] और संयोजी अनुकूलन समस्याओं के लिए एक [[कलन विधि]] डिजाइन प्रतिमान है। एक शाखा-और-बाध्य एल्गोरिथ्म में [[राज्य अंतरिक्ष खोज]] के माध्यम से उम्मीदवार समाधानों की एक व्यवस्थित गणना होती है: उम्मीदवार समाधानों के समुच्चय को रूट पर पूर्ण समुच्चय के साथ ट्री (ग्राफ़ सिद्धांत) बनाने के रूप में माना जाता है। एल्गोरिद्म इस पेड़ की ''शाखाओं'' की पड़ताल करता है, जो समाधान समुच्चय के सबसमुच्चय का प्रतिनिधित्व करती है। एक शाखा के उम्मीदवार समाधानों की गणना करने से पहले, शाखा को इष्टतम समाधान पर ऊपरी और निचले अनुमानित ''सीमा'' के खिलाफ जांचा जाता है, और अगर यह एल्गोरिथम द्वारा अब तक मिले सबसे अच्छे समाधान से बेहतर समाधान नहीं दे पाता है तो उसे छोड़ दिया जाता है।
शाखा और बाउंड (बीबी या बी एंड बी) [[असतत अनुकूलन]] और संयोजी अनुकूलन समस्याओं के लिए एक [[कलन विधि]] डिजाइन प्रतिमान है। एक शाखा-और-बाध्य एल्गोरिथ्म में [[राज्य अंतरिक्ष खोज]] के माध्यम से उम्मीदवार समाधानों की एक व्यवस्थित गणना होती है: उम्मीदवार समाधानों के समुच्चय को रूट पर पूर्ण समुच्चय के साथ ट्री (ग्राफ़ सिद्धांत) बनाने के रूप में माना जाता है। एल्गोरिद्म इस पेड़ की ''शाखाओं'' की पड़ताल करता है, जो समाधान समुच्चय के सबसमुच्चय का प्रतिनिधित्व करती है। एक शाखा के उम्मीदवार समाधानों की गणना करने से पहले, शाखा को इष्टतम समाधान पर ऊपरी और निचले अनुमानित ''सीमा'' के खिलाफ जांचा जाता है, और यदि यह एल्गोरिथम द्वारा अब तक मिले सबसे अच्छे समाधान से उत्तम समाधान नहीं दे पाता है तो उसे छोड़ दिया जाता है।


=== अंतराल के तरीके ===
=== अंतराल के तरीके ===
{{main article|अंतराल अंकगणित|}}
{{main article|अंतराल अंकगणित|}}
अंतराल अंकगणित, अंतराल गणित, अंतराल विश्लेषण, या अंतराल गणना, 1950 और 1960 के दशक से गणितज्ञों द्वारा विकसित एक विधि है जो संख्यात्मक विश्लेषण में गोल त्रुटियों और माप त्रुटियाँ पर सीमा लगाने के दृष्टिकोण के रूप में है और इस प्रकार विश्वसनीय परिणाम देने वाली संख्यात्मक विधियों का विकास करती है। अंतराल अंकगणित समीकरणों और अनुकूलन समस्याओं के विश्वसनीय और गारंटीकृत समाधान खोजने में मदद करता है।
अंतराल अंकगणित, अंतराल गणित, अंतराल विश्लेषण, या अंतराल गणना, 1950 और 1960 के दशक से गणितज्ञों द्वारा विकसित एक विधि है जो संख्यात्मक विश्लेषण में गोल त्रुटियों और माप त्रुटियाँ पर सीमा लगाने के दृष्टिकोण के रूप में है और इस प्रकार विश्वसनीय परिणाम देने वाली संख्यात्मक विधियों का विकास करती है। अंतराल अंकगणित समीकरणों और अनुकूलन समस्याओं के विश्वसनीय और गारंटीकृत समाधान खोजने में सहायता करता है।
 
'''अंतराल अंकगणित, अंतराल गणित, अंतराल विश्लेषण, या अंतराल गणना, 1950 और 1960 के दशक से गणितज्ञों द्वारा विकसित एक विधि है'''


=== वास्तविक बीजगणितीय ज्यामिति पर आधारित विधियाँ ===
=== वास्तविक बीजगणितीय ज्यामिति पर आधारित विधियाँ ===
{{main article|वास्तविक बीजगणितीय ज्यामिति}}
{{main article|वास्तविक बीजगणितीय ज्यामिति}}


वास्तविक बीजगणित बीजगणित का वह भाग है जो वास्तविक बीजगणितीय (और अर्ध-बीजगणितीय) ज्यामिति के लिए प्रासंगिक है। यह ज्यादातर ऑर्डर किए गए क्षेत्र और ऑर्डर किए गए रिंगों (विशेष रूप से वास्तविक बंद क्षेत्र) और [[सकारात्मक बहुपद|सकारात्मक बहुपदो]] और [[बहुपद एसओएस]] के अध्ययन के लिए उनके अनुप्रयोगों से संबंधित है। बहुपदों के वर्गों का योग। इसका उपयोग उत्तल अनुकूलन में किया जा सकता है
वास्तविक बीजगणित बीजगणित का वह भाग है जो वास्तविक बीजगणितीय (और अर्ध-बीजगणितीय) ज्यामिति के लिए प्रासंगिक है। यह अधिकतर ऑर्डर किए गए क्षेत्र और ऑर्डर किए गए रिंगों (विशेष रूप से वास्तविक बंद क्षेत्र) और [[सकारात्मक बहुपद|सकारात्मक बहुपदो]] और [[बहुपद एसओएस]] के अध्ययन के लिए उनके अनुप्रयोगों से संबंधित है। बहुपदों के वर्गों का योग। इसका उपयोग उत्तल अनुकूलन में किया जा सकता है


== स्टोकेस्टिक तरीके ==
== स्टोकेस्टिक तरीके ==
{{Main article|स्टोचैस्टिक अनुकूलन}}
{{Main article|स्टोचैस्टिक अनुकूलन}}
कई सटीक या अचूक मोंटे-कार्लो-आधारित एल्गोरिदम मौजूद हैं:
कई स्पष्ट या अचूक मोंटे-कार्लो-आधारित एल्गोरिदम उपस्थितहैं:


===डायरेक्ट मोंटे-कार्लो सैंपलिंग===
===डायरेक्ट मोंटे-कार्लो सैंपलिंग===
Line 99: Line 97:
इस पद्धति में, अनुमानित समाधान खोजने के लिए यादृच्छिक सिमुलेशन का उपयोग किया जाता है।
इस पद्धति में, अनुमानित समाधान खोजने के लिए यादृच्छिक सिमुलेशन का उपयोग किया जाता है।


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


=== स्टोकेस्टिक टनलिंग ===
=== स्टोकेस्टिक टनलिंग ===
Line 126: Line 124:
|bibcode=1999CPL...314..141S}}</ref> इसे सामान्यतयः प्रतिकृति-विनिमय आणविक गतिशीलता या आरईएमडी के रूप में जाना जाता है।
|bibcode=1999CPL...314..141S}}</ref> इसे सामान्यतयः प्रतिकृति-विनिमय आणविक गतिशीलता या आरईएमडी के रूप में जाना जाता है।


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


इस तरह, ऊष्मप्रवैगिकी गुण जैसे कि विशिष्ट ऊष्मा, जो सामान्य रूप से विहित पहनावे में अच्छी तरह से गणना नहीं की जाती है, तथा इसकी गणना बड़ी सटीकता के साथ की जा सकती है।
इस तरह, ऊष्मप्रवैगिकी गुण जैसे कि विशिष्ट ऊष्मा, जो सामान्य रूप से विहित पहनावे में अच्छी तरह से गणना नहीं की जाती है, तथा इसकी गणना बड़ी स्पष्टता के साथ की जा सकती है।


== ह्यूरिस्टिक्स और मेटाह्यूरिस्टिक्स ==
== ह्यूरिस्टिक्स और मेटाह्यूरिस्टिक्स ==
{{main|मेटाह्यूरिस्टिक}}
{{main|मेटाह्यूरिस्टिक}}
अन्य दृष्टिकोणों में खोज स्थान को अधिक या कम बुद्धिमान तरीके से खोजने के लिए अनुमानी रणनीतियाँ शामिल हैं, जिनमें शामिल हैं:
अन्य दृष्टिकोणों में खोज स्थान को अधिक या कम बुद्धिमान तरीके से खोजने के लिए अनुमानी रणनीतियाँ सम्मिलित  हैं, जिनमें सम्मिलित  हैं:
* [[चींटी कॉलोनी अनुकूलन]] एल्गोरिदम (एसीओ)
* [[चींटी कॉलोनी अनुकूलन]] एल्गोरिदम (एसीओ)
* [[तैयार किए हुयी धातु पे पानी चढाने की कला]], एक सामान्य संभाव्य मेटाह्यूरिस्टिक
* [[तैयार किए हुयी धातु पे पानी चढाने की कला]], एक सामान्य संभाव्य मेटाह्यूरिस्टिक
Line 140: Line 138:
* झुंड बुद्धि | झुंड-आधारित अनुकूलन एल्गोरिदम (उदाहरण के लिए, [[कण झुंड अनुकूलन]], [[सामाजिक संज्ञानात्मक अनुकूलन]], बहु-झुंड अनुकूलन और चींटी कॉलोनी अनुकूलन)
* झुंड बुद्धि | झुंड-आधारित अनुकूलन एल्गोरिदम (उदाहरण के लिए, [[कण झुंड अनुकूलन]], [[सामाजिक संज्ञानात्मक अनुकूलन]], बहु-झुंड अनुकूलन और चींटी कॉलोनी अनुकूलन)
* [[आनुवंशिक एल्गोरिदम]], वैश्विक और स्थानीय खोज रणनीतियों का संयोजन
* [[आनुवंशिक एल्गोरिदम]], वैश्विक और स्थानीय खोज रणनीतियों का संयोजन
* रिएक्टिव [[बहु झुंड अनुकूलन]] (यानी उप-प्रतीकात्मक मशीन लर्निंग तकनीकों का सर्च ह्यूरिस्टिक्स में एकीकरण)
* रिएक्टिव [[बहु झुंड अनुकूलन]] (अर्थात उप-प्रतीकात्मक मशीन लर्निंग विधि का सर्च ह्यूरिस्टिक्स में एकीकरण)
* [[स्नातक की उपाधि प्राप्त अनुकूलन]], एक तकनीक जो शुरू में एक बहुत ही सरलीकृत समस्या को हल करके एक कठिन अनुकूलन समस्या को हल करने का प्रयास करती है, और उस समस्या को (अनुकूलन करते समय) उत्तरोत्तर तब तक रूपांतरित करती है जब तक कि यह कठिन अनुकूलन समस्या के बराबर न हो जाए।<ref>{{cite book |first1=Neil |last1=Thacker |first2=Tim |last2=Cootes |chapter-url=http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/BMVA96Tut/node29.html |chapter=Graduated Non-Convexity and Multi-Resolution Optimization Methods |title=Vision Through Optimization |year=1996}}</ref><ref>{{cite book |first1=Andrew |last1=Blake |first2=Andrew |last2=Zisserman |url=http://research.microsoft.com/en-us/um/people/ablake/papers/VisualReconstruction/ |title=Visual Reconstruction |publisher=MIT Press |year=1987 |isbn=0-262-02271-0}}{{page needed|date=October 2011}}</ref><ref name="mobahi2015">Hossein Mobahi, John W. Fisher III.  
* [[स्नातक की उपाधि प्राप्त अनुकूलन]], एक विधि  जो प्रारम्भ में एक बहुत ही सरलीकृत समस्या को हल करके एक कठिन अनुकूलन समस्या को हल करने का प्रयास करती है, और उस समस्या को (अनुकूलन करते समय) उत्तरोत्तर तब तक रूपांतरित करती है जब तक कि यह कठिन अनुकूलन समस्या के बराबर न हो जाए।<ref>{{cite book |first1=Neil |last1=Thacker |first2=Tim |last2=Cootes |chapter-url=http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/BMVA96Tut/node29.html |chapter=Graduated Non-Convexity and Multi-Resolution Optimization Methods |title=Vision Through Optimization |year=1996}}</ref><ref>{{cite book |first1=Andrew |last1=Blake |first2=Andrew |last2=Zisserman |url=http://research.microsoft.com/en-us/um/people/ablake/papers/VisualReconstruction/ |title=Visual Reconstruction |publisher=MIT Press |year=1987 |isbn=0-262-02271-0}}{{page needed|date=October 2011}}</ref><ref name="mobahi2015">Hossein Mobahi, John W. Fisher III.  
[http://people.csail.mit.edu/hmobahi/pubs/gaussian_convenv_2015.pdf On the Link Between Gaussian Homotopy Continuation and Convex Envelopes], In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.</ref>
[http://people.csail.mit.edu/hmobahi/pubs/gaussian_convenv_2015.pdf On the Link Between Gaussian Homotopy Continuation and Convex Envelopes], In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.</ref>



Revision as of 00:55, 17 February 2023

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

एक संभावित गैर-रैखिक और गैर-उत्तल निरंतर कार्य दिया गया वैश्विक न्यूनतम के साथ और सभी ग्लोबल मिनिमाइज़र का समुच्चय में , मानक न्यूनीकरण समस्या के रूप में दिया जा सकता है

अर्थात् खोजना और एक वैश्विक न्यूनतमकर्ता ; जहा असमानताओं द्वारा परिभाषित एक (आवश्यक नहीं उत्तल) कॉम्पैक्ट समुच्चय है .

ग्लोबल ऑप्टिमाइज़ेशन को स्थानीय ऑप्टिमाइज़ेशन से अलग किया जाता है, जो स्थानीय मिनिमा या मैक्सिमा खोजने के विरोध में दिए गए समुच्चय पर न्यूनतम या अधिकतम खोजने पर ध्यान केंद्रित करता है। मौलिक स्थानीय अनुकूलन विधियों का उपयोग करके एक मनमानी स्थानीय न्यूनतम ढूँढना अपेक्षाकृत सरल है। किसी फलन का वैश्विक न्यूनतम पता लगाना अधिक कठिन है: विश्लेषणात्मक तरीके सदैव प्रयुक्त नहीं होते हैं, और संख्यात्मक समाधान रणनीतियों का उपयोग सदैव बहुत कठिन चुनौतियों का कारण बनता है।

सामान्य सिद्धांत

वैश्विक अनुकूलन समस्या के लिए एक हालिया दृष्टिकोण मिनिमा वितरण के माध्यम से है.[1] इस काम में, किसी भी निरंतर कार्य के बीच संबंध एक कॉम्पैक्ट समुच्चय पर और इसकी वैश्विक न्यूनतम कड़ाई से स्थापित किया गया है। एक विशिष्ट स्थितियों के रूप में, यह इस प्रकार है

इस दौरान,

जहा है मिनिमाइज़र के समुच्चय का आयामी लेबेस्ग माप . और यदि स्थिर नहीं है , मोनोटोनिक संबंध

सभी और के लिए रोक कर रखता है, जो नीरस नियंत्रण संबंधों की एक श्रृंखला को दर्शाता है, और उनमें से एक है, उदाहरण के लिए

और हम न्यूनतम वितरण को एक कमजोर सीमा के रूप में परिभाषित करते हैं, जिससे कि पहचान

में कॉम्पैक्ट समर्थन के साथ हर स्मूद फंक्शन के लिए रोक कर रखता है। यहाँ के दो तात्कालिक गुण हैं,

(1) पहचान को संतुष्ट करता है .
(2) यदि निरंतर चालू है , तब .

एक तुलना के रूप में, किसी भी अलग-अलग उत्तल फलन और इसकी मिनीमा के बीच प्रसिद्ध संबंध ढाल द्वारा सख्ती से स्थापित किया जाता है।यदि f उत्तल समुच्चय D पर अवकलनीय है, तो f उत्तल है यदि और केवल यदि

इस प्रकार, इसका आशय है सभी के लिए रखता है , अर्थात।, का ग्लोबल मिनिमाइज़र है पर .

अनुप्रयोग

वैश्विक अनुकूलन अनुप्रयोगों के विशिष्ट उदाहरणों में सम्मिलित हैं:

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

नियतात्मक तरीके

सबसे सफल सामान्य स्पष्ट रणनीतियाँ हैं:

आंतरिक और बाहरी सन्निकटन

इन दोनों रणनीतियों में, जिस समुच्चय पर एक फलन को अनुकूलित किया जाना है, वह पॉलीहेड्रा द्वारा अनुमानित है। आंतरिक सन्निकटन में, पॉलीहेड्रा समुच्चय में समाहित होता है, जबकि बाहरी सन्निकटन में, पॉलीहेड्रा में समुच्चय होता है।

कटिंग-प्लेन के तरीके

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

शाखा और बाध्य तरीके

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

अंतराल के तरीके

अंतराल अंकगणित, अंतराल गणित, अंतराल विश्लेषण, या अंतराल गणना, 1950 और 1960 के दशक से गणितज्ञों द्वारा विकसित एक विधि है जो संख्यात्मक विश्लेषण में गोल त्रुटियों और माप त्रुटियाँ पर सीमा लगाने के दृष्टिकोण के रूप में है और इस प्रकार विश्वसनीय परिणाम देने वाली संख्यात्मक विधियों का विकास करती है। अंतराल अंकगणित समीकरणों और अनुकूलन समस्याओं के विश्वसनीय और गारंटीकृत समाधान खोजने में सहायता करता है।

वास्तविक बीजगणितीय ज्यामिति पर आधारित विधियाँ

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

स्टोकेस्टिक तरीके

कई स्पष्ट या अचूक मोंटे-कार्लो-आधारित एल्गोरिदम उपस्थितहैं:

डायरेक्ट मोंटे-कार्लो सैंपलिंग

इस पद्धति में, अनुमानित समाधान खोजने के लिए यादृच्छिक सिमुलेशन का उपयोग किया जाता है।

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

स्टोकेस्टिक टनलिंग

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

समानांतर तड़के

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

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

इस तरह, ऊष्मप्रवैगिकी गुण जैसे कि विशिष्ट ऊष्मा, जो सामान्य रूप से विहित पहनावे में अच्छी तरह से गणना नहीं की जाती है, तथा इसकी गणना बड़ी स्पष्टता के साथ की जा सकती है।

ह्यूरिस्टिक्स और मेटाह्यूरिस्टिक्स

अन्य दृष्टिकोणों में खोज स्थान को अधिक या कम बुद्धिमान तरीके से खोजने के लिए अनुमानी रणनीतियाँ सम्मिलित हैं, जिनमें सम्मिलित हैं:


प्रतिक्रिया सतह कार्यप्रणाली-आधारित दृष्टिकोण


यह भी देखें

फुटनोट्स

  1. Xiaopeng Luo (2018). "Minima distribution for global optimization". arXiv:1812.03457. {{cite journal}}: Cite journal requires |journal= (help)
  2. Swendsen RH and Wang JS (1986) Replica Monte Carlo simulation of spin glasses Physical Review Letters 57 : 2607–2609
  3. C. J. Geyer, (1991) in Computing Science and Statistics, Proceedings of the 23rd Symposium on the Interface, American Statistical Association, New York, p. 156.
  4. Marco Falcioni and Michael W. Deem (1999). "A Biased Monte Carlo Scheme for Zeolite Structure Solution". J. Chem. Phys. 110 (3): 1754–1766. arXiv:cond-mat/9809085. Bibcode:1999JChPh.110.1754F. doi:10.1063/1.477812. S2CID 13963102.
  5. David J. Earl and Michael W. Deem (2005) "Parallel tempering: Theory, applications, and new perspectives", Phys. Chem. Chem. Phys., 7, 3910
  6. Y. Sugita and Y. Okamoto (1999). "Replica-exchange molecular dynamics method for protein folding". Chemical Physics Letters. 314 (1–2): 141–151. Bibcode:1999CPL...314..141S. doi:10.1016/S0009-2614(99)01123-9.
  7. Thacker, Neil; Cootes, Tim (1996). "Graduated Non-Convexity and Multi-Resolution Optimization Methods". Vision Through Optimization.
  8. Blake, Andrew; Zisserman, Andrew (1987). Visual Reconstruction. MIT Press. ISBN 0-262-02271-0.[page needed]
  9. Hossein Mobahi, John W. Fisher III. On the Link Between Gaussian Homotopy Continuation and Convex Envelopes, In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.
  10. Jonas Mockus (2013). Bayesian approach to global optimization: theory and applications. Kluwer Academic.


संदर्भ

Deterministic global optimization:

For simulated annealing:

For reactive search optimization:

  • Roberto Battiti, M. Brunato and F. Mascia, Reactive Search and Intelligent Optimization, Operations Research/Computer Science Interfaces Series, Vol. 45, Springer, November 2008. ISBN 978-0-387-09623-0

For stochastic methods:

For parallel tempering:

For continuation methods:

For general considerations on the dimensionality of the domain of definition of the objective function:

For strategies allowing one to compare deterministic and stochastic global optimization methods


बाहरी संबंध