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

ग्लोबल ऑप्टिमाइज़ेशन अनुप्रयुक्त गणित और संख्यात्मक विश्लेषण की एक शाखा है जो किसी दिए गए सेट पर किसी फ़ंक्शन या फ़ंक्शन के सेट के ग्लोबल मैक्सिमा और मिनिमा को खोजने का प्रयास करता है। इसे सामान्यतया न्यूनतमकरण समस्या के रूप में वर्णित किया जाता है क्योंकि वास्तविक-मूल्यवान फ़ंक्शन का अधिकतमकरण $g(x)$ समारोह के न्यूनीकरण के बराबर है $f(x):=(-1)\cdot g(x)$.

एक संभावित गैर-रैखिक और गैर-उत्तल निरंतर कार्य दिया गया $f:\Omega \subset \mathbb {R} ^{n}\to \mathbb {R}$ वैश्विक न्यूनतम के साथ $f^{*}$ और सभी ग्लोबल मिनिमाइज़र का सेट $X^{*}$ में $\Omega$, मानक न्यूनीकरण समस्या के रूप में दिया जा सकता है

$\min _{x\in \Omega }f(x),$

अर्थात् खोजना $f^{*}$ और एक वैश्विक न्यूनतमकर्ता $X^{*}$; जहा $\Omega$ असमानताओं द्वारा परिभाषित एक (जरूरी नहीं उत्तल) कॉम्पैक्ट सेट है $g_{i}(x)\geqslant 0,i=1,\ldots ,r$.

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

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

वैश्विक अनुकूलन समस्या के लिए एक हालिया दृष्टिकोण मिनिमा वितरण के माध्यम से है . इस काम में, किसी भी निरंतर कार्य के बीच संबंध $f$ एक कॉम्पैक्ट सेट पर $\Omega \subset \mathbb {R} ^{n}$ और इसकी वैश्विक न्यूनतम $f^{*}$ कड़ाई से स्थापित किया गया है। एक विशिष्ट मामले के रूप में, यह इस प्रकार है

$\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 }m^{(k)}(x)=\left\{{\begin{array}{cl}{\frac {1}{\mu (X^{*})}},&x\in X^{*},\\0,&x\in \Omega -X^{*},\end{array}}\right.$

जहा $\mu (X^{*})$ है $n$मिनिमाइज़र के सेट का आयामी लेबेस्ग माप $X^{*}\in \Omega$. और अगर $f$ स्थिर नहीं है $\Omega$, मोनोटोनिक संबंध

$\int _{\Omega }f(x)m^{(k)}(x)\,\mathrm {d} x>\int _{\Omega }f(x)m^{(k+\Delta k)}(x)\,\mathrm {d} x>f^{*}$

सभी $k\in \mathbb {R}$ और $\Delta k>0$ के लिए रोक कर रखता है, जो नीरस नियंत्रण संबंधों की एक श्रृंखला को दर्शाता है, और उनमें से एक है, उदाहरण के लिए

$\Omega \supset D_{f}^{(k)}\supset D_{f}^{(k+\Delta k)}\supset X^{*},{\text{ where }}D_{f}^{(k)}=\left\{x\in \Omega :f(x)\leqslant \int _{\Omega }f(t)m^{(k)}(t)\,\mathrm {d} t\right\}.$

और हम न्यूनतम वितरण को एक कमजोर सीमा $m_{f,\Omega }$ के रूप में परिभाषित करते हैं, जिससे कि पहचान

$\int _{\Omega }m_{f,\Omega }(x)\varphi (x)\,\mathrm {d} x=\lim _{k\to \infty }\int _{\Omega }m^{(k)}(x)\varphi (x)\,\mathrm {d} x$

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

(1) $m_{f,\Omega }$ पहचान को संतुष्ट करता है $\int _{\Omega }m_{f,\Omega }(x)\,\mathrm {d} x=1$.

(2) अगर $f$ निरंतर चालू है $\Omega$, तब $f^{*}=\int _{\Omega }f(x)m_{f,\Omega }(x)\,\mathrm {d} x$.

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

$f(y)\geqslant f(x)+\nabla f(x)(y-x),~~\forall x,y\in D;$

इस प्रकार, $\nabla f(x^{*})=0$ इसका आशय है $f(y)\geqslant f(x^{*})$ सभी के लिए रखता है $y\in D$, अर्थात।, $x^{*}$ का ग्लोबल मिनिमाइज़र है $f$ पर $D$.

अनुप्रयोग

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

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

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

Main article: नियतात्मक वैश्विक अनुकूलन

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

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

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

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

Main article: कटिंग प्लेन

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

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

Main article: शाखा और बंधन

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

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

Main article: अंतराल अंकगणित

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

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

Main article: वास्तविक बीजगणितीय ज्यामिति

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

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

Main article: स्टोचैस्टिक अनुकूलन

कई सटीक या अचूक मोंटे-कार्लो-आधारित एल्गोरिदम मौजूद हैं:

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

Main article: मोंटे कार्लो विधि

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

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

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

Main article: स्टोकेस्टिक टनलिंग

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

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

Main article: समानांतर तड़का

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

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

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

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

Main article: मेटाह्यूरिस्टिक

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

• चींटी कॉलोनी अनुकूलन एल्गोरिदम (एसीओ)
• तैयार किए हुयी धातु पे पानी चढाने की कला, एक सामान्य संभाव्य मेटाह्यूरिस्टिक
• तब्बू खोज, स्थानीय न्यूनतम से बचने में सक्षम स्थानीय खोज (अनुकूलन) का विस्तार
• विकासवादी एल्गोरिदम (उदाहरण के लिए, अनुवांशिक एल्गोरिदम और विकास रणनीतियां)
• विभेदक विकास, एक विधि जो अनुकूलन (गणित) पुनरावृत्त विधि द्वारा एक समस्या है जो गुणवत्ता के दिए गए माप के संबंध में एक उम्मीदवार समाधान में सुधार करने की कोशिश कर रही है
• झुंड बुद्धि | झुंड-आधारित अनुकूलन एल्गोरिदम (उदाहरण के लिए, कण झुंड अनुकूलन, सामाजिक संज्ञानात्मक अनुकूलन, बहु-झुंड अनुकूलन और चींटी कॉलोनी अनुकूलन)
• आनुवंशिक एल्गोरिदम, वैश्विक और स्थानीय खोज रणनीतियों का संयोजन
• रिएक्टिव बहु झुंड अनुकूलन (यानी उप-प्रतीकात्मक मशीन लर्निंग तकनीकों का सर्च ह्यूरिस्टिक्स में एकीकरण)
• स्नातक की उपाधि प्राप्त अनुकूलन, एक तकनीक जो शुरू में एक बहुत ही सरलीकृत समस्या को हल करके एक कठिन अनुकूलन समस्या को हल करने का प्रयास करती है, और उस समस्या को (अनुकूलन करते समय) उत्तरोत्तर तब तक रूपांतरित करती है जब तक कि यह कठिन अनुकूलन समस्या के बराबर न हो जाए।

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

• मुझे पता है स्व-संगठन पर आधारित अप्रत्यक्ष अनुकूलन
• बायेसियन अनुकूलन, बायेसियन सांख्यिकी का उपयोग करके ब्लैक-बॉक्स फ़ंक्शंस के वैश्विक ऑप्टिमाइज़ेशन के लिए एक अनुक्रमिक निर्माण रणनीति

यह भी देखें

• नियतात्मक वैश्विक अनुकूलन
• बहुआयामी डिजाइन अनुकूलन
• बहुउद्देश्यीय अनुकूलन
• अनुकूलन (गणित)

संदर्भ

Deterministic global optimization:

• R. Horst, H. Tuy, Global Optimization: Deterministic Approaches, Springer, 1996.
• R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization, Second Edition. Kluwer Academic Publishers, 2000.
• A.Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, pp. 271–369 in: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.
• M. Mongeau, H. Karsenty, V. Rouzé and J.-B. Hiriart-Urruty, Comparison of public-domain software for black box global optimization. Optimization Methods & Software 13(3), pp. 203–226, 2000.
• J.D. Pintér, Global Optimization in Action - Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Kluwer Academic Publishers, Dordrecht, 1996. Now distributed by Springer Science and Business Media, New York. This book also discusses stochastic global optimization methods.
• L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Applied Interval Analysis. Berlin: Springer.
• E.R. Hansen (1992), Global Optimization using Interval Analysis, Marcel Dekker, New York.

For simulated annealing:

• Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. (1983-05-13). "Optimization by Simulated Annealing". Science. American Association for the Advancement of Science (AAAS). 220 (4598): 671–680. Bibcode:1983Sci...220..671K. doi:10.1126/science.220.4598.671. ISSN 0036-8075. PMID 17813860. S2CID 205939.

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:

• A. Zhigljavsky. Theory of Global Random Search. Mathematics and its applications. Kluwer Academic Publishers. 1991.
• Hamacher, K (2006). "Adaptation in stochastic tunneling global optimization of complex potential energy landscapes". Europhysics Letters (EPL). IOP Publishing. 74 (6): 944–950. Bibcode:2006EL.....74..944H. doi:10.1209/epl/i2006-10058-0. ISSN 0295-5075. S2CID 250761754.
• Hamacher, K.; Wenzel, W. (1999-01-01). "Scaling behavior of stochastic minimization algorithms in a perfect funnel landscape". Physical Review E. 59 (1): 938–941. arXiv:physics/9810035. Bibcode:1999PhRvE..59..938H. doi:10.1103/physreve.59.938. ISSN 1063-651X. S2CID 119096368.
• Wenzel, W.; Hamacher, K. (1999-04-12). "Stochastic Tunneling Approach for Global Minimization of Complex Potential Energy Landscapes". Physical Review Letters. American Physical Society (APS). 82 (15): 3003–3007. arXiv:physics/9903008. Bibcode:1999PhRvL..82.3003W. doi:10.1103/physrevlett.82.3003. ISSN 0031-9007. S2CID 5113626.

For parallel tempering:

• Hansmann, Ulrich H.E. (1997). "Parallel tempering algorithm for conformational studies of biological molecules". Chemical Physics Letters. Elsevier BV. 281 (1–3): 140–150. arXiv:physics/9710041. Bibcode:1997CPL...281..140H. doi:10.1016/s0009-2614(97)01198-6. ISSN 0009-2614. S2CID 14137470.

For continuation methods:

• Zhijun Wu. The effective energy transformation scheme as a special continuation approach to global optimization with application to molecular conformation. Technical Report, Argonne National Lab., IL (United States), November 1996.

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

• Hamacher, Kay (2005). "On stochastic global optimization of one-dimensional functions". Physica A: Statistical Mechanics and Its Applications. Elsevier BV. 354: 547–557. Bibcode:2005PhyA..354..547H. doi:10.1016/j.physa.2005.02.028. ISSN 0378-4371.

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

बाहरी संबंध

• A. Neumaier’s page on Global Optimization
• Introduction to global optimization by L. Liberti
• Free e-book by Thomas Weise