वैश्विक अनुकूलन

From Vigyanwiki

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

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

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

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

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

वैश्विक अनुकूलन समस्या के लिए नवीनतम दृष्टिकोण न्यूनतम वितरण के माध्यम से है।[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


बाहरी संबंध