सिम्युलेटेड एनीलिंग

कॉम्बीनेटरियल समस्याओं को हल करने के लिए कृत्रिम अनीलन का उपयोग किया जा सकता है। यहां इसे विक्रेता यात्री की समस्या पर लागू किया जाता है ताकि सभी 125 बिंदुओं को जोड़ने वाले मार्ग की लंबाई को कम किया जा सके।

कृत्रिम अनीलन के साथ 120 बिंदुओं के लिए 3डी में विक्रेता यात्री की समस्या हल हो गई।

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

विधिकलन का नाम धातु विज्ञान के एनीलिंग से आता है एक ऐसी तकनीक है जिसमें सामग्री के भौतिक गुणों को परिवर्तित करने के लिए ऊष्मण और नियंत्रित शीतलन सम्मिलित है। दोनों सामग्री के गुण हैं जो उनकी ऊष्मागतिक मुक्त ऊर्जा पर निर्भर करते हैं। सामग्री को गर्म करने और शीतल करने से तापमान और ऊष्मागतिक मुक्त ऊर्जा या गिब्स ऊर्जा दोनों प्रभावित होते हैं।

कृत्रिम अनीलन का उपयोग बहुत जटिल संगणनीय अनुकूलन समस्याओं के लिए किया जा सकता है जहां सटीक विधिकलन विफल हो जाते हैं; भले ही यह सामान्यतः वैश्विक न्यूनतम के अनुमानित समाधान को प्राप्त करता है, यह कई व्यावहारिक समस्याओं के लिए उपयुक्त हो सकता है।

कृत्रिम अनीलन द्वारा हल की गई समस्याएं वर्तमान में कई चर के एक उद्देश्य फलन द्वारा तैयार की जाती हैं। व्यवहार में, उद्देश्य फलन के भाग के रूप में बाधा को दंडित किया जा सकता है।

पिंकस सहित कई अवसरों जैसे खाचतुर्यन एट अल (1979, 1981), किर्कपैट्रिक, गेलैट और वेची (1983), और सेर्नी (1985) पर इसी तरह की तकनीकों को स्वतंत्र रूप से प्रस्तुत किया गया है। 1983 में, किर्कपैट्रिक, गेलैट जूनियर, वेची, द्वारा इस उपागम का उपयोग विक्रेता यात्री की समस्या के समाधान के लिए किया गया था। उन्होंने इसका वर्तमान नाम 'कृत्रिम अनीलन' भी प्रस्तावित किया था।

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

अनुरूपण या तो घनत्व कार्यों के लिए गतिज समीकरणों के समाधान द्वारा या प्रसंभाव्य प्रतिदर्श विधि का उपयोग करके किया जा सकता है। यह विधि मेट्रोपोलिस-हेस्टिंग्स विधिकलन का एक अनुकूलन है। मेट्रोपोलिस एट अल द्वारा 1953 में प्रकाशित ऊष्मागतिक प्रणाली को प्रतिदर्श स्थितियों को उत्पन्न करने के लिए मोंटे कार्लो विधि का प्रयोग किया गया ।

संक्षिप्त विवरण

कुछ भौतिक प्रणालियों की ऊष्मप्रवैगिकी स्थिति, और फलन E(s) को न्यूनतम किया जाना, उस अवस्था में प्रणाली की आंतरिक ऊर्जा के अनुरूप है। जिसका लक्ष्य प्रणाली को यादृच्छिक प्रारंभिक अवस्था से, न्यूनतम संभव ऊर्जा वाले अवस्था में लाना है।

कृत्रिम अनीलन 'अधिकतम' खोज रहा है। यहां लक्ष्य उच्चतम बिंदु तक पहुंचना है। इस उदाहरण में, साधारण पहाड़ी चढ़ाई विधिकलन का उपयोग करना उपयुक्त नहीं है, क्योंकि कई पहाड़ी चढ़ाई विधिकलन स्थानिक उच्चिष्ठ हैं। तापमान को धीरे-धीरे शीतल करके 'वैश्विक अधिकतम' प्राप्त किया जाता है।

मूल पुनरावृत्ति

प्रत्येक चरण पर, कृत्रिम अनीलन हेयुरिस्टिक वर्तमान स्थिति S के कुछ निकटवर्ती स्थितियों S* पर विचार करता है, और संभावित रूप से प्रणाली को स्थिति एस * या यथास्थिति S में स्थानांतरित करने के मध्य निर्णय लेता है। ये संभावनाएं अंततः प्रणाली को कम ऊर्जा वाले स्थितियों में ले जाने के लिए प्रेरित करती हैं। सामान्यतः यह चरण तब तक दोहराया जाता है जब तक कि प्रणाली उस स्थिति तक नहीं पहुंच जाता है जो उपयोग के लिए पर्याप्त है, या जब तक कि दिए गए गणना बजट समाप्त नहीं हो जाते।

स्थिति के निकटवर्ती

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

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

स्वीकृति संभाव्यता

स्थिति को वर्तमान स्थिति $s$ से परिवर्तित करने की संभावना एक उम्मीदवार नए स्थिति $s_{\mathrm {new} }$ के लिए स्वीकृति संभाव्यता फलन $P(e,e_{\mathrm {new} },T)$ द्वारा निर्दिष्ट किया गया है , यह दो स्थितियों $e=E(s)$ और $e_{\mathrm {new} }=E(s_{\mathrm {new} })$ की ऊर्जाओं पर निर्भर करता है और एक वैश्विक समय-भिन्न पैरामीटर पर तापमान $T$ कहते हैं। कम ऊर्जा वाले स्थिति अधिक ऊर्जा वाले स्थितियों से उपयुक्त हैं। संभाव्यता फलन $P$ तब भी सकारात्मक होना चाहिए $e_{\mathrm {new} }$, $e$ से बड़ा है यह सुविधा विधि को स्थानीय न्यूनतम पर अटकने से रोकती है जो वैश्विक स्थिति से भी खराब है।

कब $T$ शून्य हो जाता है, संभावना $P(e,e_{\mathrm {new} },T)$ यदि शून्य हो जाना चाहिए $e_{\mathrm {new} }>e$ और एक सकारात्मक मूल्य के लिए अन्यथा। पर्याप्त रूप से छोटे मूल्यों के लिए $T$, तब प्रणाली तेजी से उन चालों का पक्ष लेगा जो नीचे की ओर जाती हैं (यानी, ऊर्जा मूल्यों को कम करने के लिए), और उन लोगों से बचें जो ऊपर जाते हैं। साथ $T=0$ प्रक्रिया लालची विधिकलन तक कम हो जाती है, जो केवल डाउनहिल संक्रमण करती है।

कृत्रिम अनीलन के मूल विवरण में, प्रायिकता $P(e,e_{\mathrm {new} },T)$ 1 के बराबर था जब $e_{\mathrm {new} }<e$- यानी, तापमान के बावजूद, ऐसा करने का एक विधि मिलने पर प्रक्रिया सदैव डाउनहिल चली गई। कृत्रिम अनीलन के कई विवरण और कार्यान्वयन अभी भी इस स्थिति को विधि की परिभाषा के भाग के रूप में लेते हैं। यद्यपि, कार्य करने की विधि के लिए यह स्थिति आवश्यक नहीं है। $P$ h> फलन सामान्यतः चुना जाता है ताकि अंतर होने पर एक चाल को स्वीकार करने की संभावना कम हो जाए $e_{\mathrm {new} }-e$ बढ़ता है—अर्थात्, बड़े की अपेक्षा में छोटे चढाई की संभावना अधिक होती है। हालाँकि, यह आवश्यकता सख्ती से आवश्यक नहीं है, बशर्ते उपरोक्त आवश्यकताओं को पूरा किया जाए।

इन गुणों को देखते हुए, तापमान $T$ स्थिति के विकास को नियंत्रित करने में महत्वपूर्ण भूमिका निभाता है $s$ प्रणाली की ऊर्जाओं की विविधताओं के प्रति इसकी संवेदनशीलता के संबंध में। सटीक होना, एक बड़े के लिए $T$, का विकास $s$ स्थूल ऊर्जा विविधताओं के प्रति संवेदनशील है, जबकि जब यह सूक्ष्म ऊर्जा विविधताओं के प्रति संवेदनशील होती है $T$ छोटा है।

एनीलिंग सारिणी

Fast

Slow

Example illustrating the effect of cooling schedule on the performance of simulated annealing. The problem is to rearrange the pixels of an image so as to minimize a certain potential energy function, which causes similar colors to attract at short range and repel at a slightly larger distance. The elementary moves swap two adjacent pixels. These images were obtained with a fast cooling schedule (left) and a slow cooling schedule (right), producing results similar to amorphous and crystalline solids, respectively.

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

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

छद्म कूट

जैसा कि ऊपर बताया गया है, निम्नलिखित स्यूडोकोड कृत्रिम अनीलन ह्यूरिस्टिक प्रस्तुत करता है। यह एक स्थिति से शुरू होता है s₀ और अधिकतम तक जारी रहता है k_max कदम उठाए गए हैं। इस प्रक्रिया में, कॉल neighbour(s) किसी दिए गए स्थिति के यादृच्छिक रूप से चुने गए निकटवर्ती को उत्पन्न करना चाहिए s; कॉल random(0, 1) सीमा में एक मान चुनना और वापस करना चाहिए [0, 1], समान वितरण (निरंतर)। एनीलिंग शेड्यूल को कॉल द्वारा परिभाषित किया गया है temperature(r), जिसे अंश दिए जाने पर उपयोग करने के लिए तापमान देना चाहिए r अब तक खर्च किए गए समय के बजट का।

Let s = s0

For k = 0 through kmax (exclusive):

T ← temperature( 1 - (k+1)/kmax )

Pick a random neighbour, snew ← neighbour(s)

If P(E(s), E(snew), T) ≥ random(0, 1):

s ← snew

Output: the final state s

मापदंडों का चयन

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

पर्याप्ततः निकटवर्ती के पास

कृत्रिम अनीलन को एक खोज ग्राफ पर एक यादृच्छिक चलने के रूप में तैयार किया जा सकता है, जिसका शिखर सभी संभावित स्थिति हैं, और जिनके किनारे उम्मीदवार चालें हैं। के लिए एक अनिवार्य आवश्यकता है neighbour() कार्य यह है कि इस ग्राफ पर प्रारंभिक अवस्था से किसी भी स्थिति तक पर्याप्त रूप से छोटा रास्ता प्रदान करना चाहिए जो कि वैश्विक इष्टतम हो सकता है – खोज ग्राफ़ का व्यास छोटा होना चाहिए। ऊपर दिए गए विक्रेता यात्री उदाहरण में, उदाहरण के लिए, n = 20 शहरों के लिए खोज स्थान में n! = 2,432,902,008,176,640,000 (2.4 क्विंटिलियन) स्थिति; अभी तक प्रत्येक शीर्ष के निकटवर्तियों की संख्या है $\sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190$ किनारे (एन से 2 चुनें), और ग्राफ का व्यास है $n-1$.

संक्रमण संभाव्यता

किसी विशेष समस्या पर कृत्रिम अनीलन के व्यवहार की जांच करने के लिए, विधिकलन के कार्यान्वयन में किए गए विभिन्न डिज़ाइन विकल्पों के परिणामस्वरूप होने वाली संक्रमण संभावनाओं पर विचार करना उपयोगी हो सकता है। प्रत्येक किनारे के लिए $(s,s')$ खोज ग्राफ में, संक्रमण की संभावना को इस संभावना के रूप में परिभाषित किया गया है कि कृत्रिम अनीलन विधिकलन स्थिति में स्थानांतरित हो जाएगा $s'$ जब इसकी वर्तमान स्थिति है $s$. यह संभाव्यता द्वारा निर्दिष्ट वर्तमान तापमान पर निर्भर करती है temperature(), जिस क्रम में उम्मीदवार चलता है, उसके द्वारा उत्पन्न होता है neighbour() कार्य, और स्वीकृति संभाव्यता फलन पर P(). (ध्यान दें कि संक्रमण संभावना सरल नहीं है $P(e,e',T)$, क्योंकि उम्मीदवारों का क्रमिक रूप से परीक्षण किया जाता है।)

स्वीकृति संभाव्यता

की विशिष्टता neighbour(), P(), और temperature() आंशिक रूप से बेमानी है। व्यवहार में, समान स्वीकृति फलन का उपयोग करना सामान्य है P() कई समस्याओं के लिए, और अन्य दो कार्यों को विशिष्ट समस्या के अनुसार समायोजित करें।

किर्कपैट्रिक एट अल द्वारा विधि के निर्माण में, स्वीकृति संभाव्यता फलन $P(e,e',T)$ 1 अगर के रूप में परिभाषित किया गया था $e'<e$, और $\exp(-(e'-e)/T)$ अन्यथा। भौतिक प्रणाली के संक्रमण के साथ सादृश्य द्वारा इस सूत्र को सतही रूप से उचित ठहराया गया था; यह मेट्रोपोलिस-हेस्टिंग्स विधिकलन से मेल खाता है, उस मामले में जहां टी = 1 और मेट्रोपोलिस-हेस्टिंग्स का प्रस्ताव वितरण सममित है। हालाँकि, इस स्वीकृति संभावना का उपयोग प्रायः कृत्रिम अनीलन के लिए भी किया जाता है, जब भी neighbour() फलन, जो मेट्रोपोलिस-हेस्टिंग्स में प्रस्ताव वितरण के अनुरूप है, सममित नहीं है, या संभाव्य नहीं है। नतीजतन, कृत्रिम अनीलन विधिकलन की संक्रमण संभावनाएं समान भौतिक प्रणाली के संक्रमण के अनुरूप नहीं होती हैं, और निरंतर तापमान पर स्थितियों का दीर्घकालिक वितरण $T$ किसी भी तापमान पर उस भौतिक प्रणाली के स्थितियों पर ऊष्मागतिक संतुलन वितरण के लिए कोई समानता नहीं होनी चाहिए। पुनः भी, कृत्रिम अनीलन के अधिकांश विवरण मूल स्वीकृति फलन को मानते हैं, जो शायद एसए के कई कार्यान्वयनों में हार्ड-कोडेड है।

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

कुशल उम्मीदवार उत्पादन

उम्मीदवार जनरेटर चुनते समय neighbour(), किसी को यह विचार करना चाहिए कि कृत्रिम अनीलन विधिकलन के कुछ पुनरावृत्तियों के बाद, वर्तमान स्थिति में एक यादृच्छिक स्थिति की अपेक्षा में बहुत कम ऊर्जा होने की उम्मीद है। इसलिए, एक सामान्य नियम के रूप में, किसी को जनरेटर को उम्मीदवार की ओर तिरछा करना चाहिए जहां गंतव्य स्थिति की ऊर्जा होती है $s'$ वर्तमान स्थिति के समान होने की संभावना है। यह अनुमानी (जो कि मेट्रोपोलिस-हेस्टिंग्स विधिकलन का मुख्य सिद्धांत है) बहुत अच्छे उम्मीदवारों की चालों के साथ-साथ बहुत खराब चालों को बाहर करने की प्रवृत्ति रखता है; हालाँकि, पूर्व सामान्यतः बाद वाले की अपेक्षा में बहुत कम होते हैं, इसलिए अनुमानी सामान्यतः काफी प्रभावी होते हैं।

उपरोक्त विक्रेता यात्री समस्या में, उदाहरण के लिए, कम ऊर्जा वाले दौरे में लगातार दो शहरों की अदला-बदली से इसकी ऊर्जा (लंबाई) पर मामूली प्रभाव पड़ने की उम्मीद है; जबकि दो यादृच्छिक शहरों की अदला-बदली करने से इसकी लंबाई घटने की अपेक्षा में कहीं अधिक होने की संभावना है। इस प्रकार, लगातार-स्वैप निकटवर्ती जनरेटर से यादृच्छिक-स्वैप एक की अपेक्षा में उपयुक्त प्रदर्शन करने की उम्मीद की जाती है, भले ही बाद वाला इष्टतम के लिए कुछ छोटा रास्ता प्रदान कर सके (के साथ) $n-1$ इसके अतिरिक्त स्वैप करें $n(n-1)/2$).

अनुमानी का एक अधिक सटीक बयान यह है कि किसी को पहले उम्मीदवार स्थितियों का प्रयास करना चाहिए $s'$ जिसके लिए $P(E(s),E(s'),T)$ बड़ी है। मानक स्वीकृति फलन के लिए $P$ ऊपर, इसका मतलब है $E(s')-E(s)$ के आदेश पर है $T$ या कम। इस प्रकार, ऊपर दिए गए विक्रेता यात्री उदाहरण में, कोई एक का उपयोग कर सकता है neighbour() फलन जो दो यादृच्छिक शहरों की अदला-बदली करता है, जहां एक शहर-जोड़ी चुनने की संभावना गायब हो जाती है क्योंकि उनकी दूरी आगे बढ़ जाती है $T$.

बाधा निवारण

उम्मीदवार जनरेटर चुनते समय neighbour() किसी को भी गहरे स्थानीय मिनीमा-स्थितियों (या जुड़े स्थितियों के समुच्चय) की संख्या को कम करने का प्रयास करना चाहिए, जिनके पास अपने सभी निकटवर्ती स्थितियों की अपेक्षा में बहुत कम ऊर्जा है। ऊर्जा कार्य के इस तरह के बंद जल निकासी बेसिन बेसिन उच्च संभावना (बेसिन में स्थितियों की संख्या के अनुपात में) के साथ कृत्रिम अनीलन विधिकलन को फंसा सकते हैं और बहुत लंबे समय के लिए (आस-पास के स्थितियों और नीचे के मध्य ऊर्जा अंतर पर मोटे तौर पर घातीय) बेसिन का)।

एक नियम के रूप में, उम्मीदवार जनरेटर को डिजाइन करना असंभव है जो इस लक्ष्य को पूरा करेगा और समान ऊर्जा वाले उम्मीदवारों को प्राथमिकता भी देगा। दूसरी ओर, जनरेटर में अपेक्षाकृत सरल परिवर्तन करके प्रायः कृत्रिम अनीलन की दक्षता में काफी सुधार किया जा सकता है। यात्रा विक्रेता समस्या में, उदाहरण के लिए, दो दौरों को प्रदर्शित करना कठिन नहीं है $A$, $B$, लगभग समान लंबाई के साथ, जैसे कि (1) $A$ इष्टतम है, (2) शहर-जोड़ी स्वैप का हर क्रम जो परिवर्तित होता है $A$ को $B$ ऐसे दौरों से गुजरता है जो दोनों की अपेक्षा में अधिक लंबे होते हैं, और (3) $A$ में परिवर्तित किया जा सकता है $B$ लगातार शहरों के एक समुच्चय को फ़्लिप करके (क्रम को उलट कर)। इस उदाहरण में, $A$ और $B$ यदि जनरेटर केवल यादृच्छिक जोड़ी-स्वैप करता है तो विभिन्न गहरे घाटियों में झूठ बोलना; परंतु वे एक ही बेसिन में होंगे यदि जनरेटर यादृच्छिक सेगमेंट-फ्लिप करता है।

शीतलन सूची

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

पुनरारंभ

कभी-कभी ऐसे समाधान पर वापस जाना उपयुक्त होता है जो वर्तमान स्थिति से सदैव आगे बढ़ने के अतिरिक्त, अत्यधिक उपयुक्त था। इस प्रक्रिया को कृत्रिम अनीलन को पुनः प्रारंभ करना कहा जाता है। ऐसा करने के लिए हम समुच्चय s और e को sbest और ebest करते हैं और संभवतः एनीलिंग सूची को पुनः प्रारंभ करते है। पुनरारंभ करने का निर्णय कई मानदंडों पर आधारित हो सकता है। इनमें से उल्लेखनीय चरणों की एक निश्चित संख्या के आधार पर कि वर्तमान ऊर्जा अब तक प्राप्त सर्वोत्तम ऊर्जा की अपेक्षा में बहुत अधिक है।

संबंधित विधियाँ

• मेट्रोपोलिस-हेस्टिंग्स विधिकलन अर्थात अनुक्रमिक मोंटे कार्लो विधि एक अंतःक्रियात्मक पुनरावर्तन तंत्र से युक्त सर्वोत्तम फिट व्यक्तियों की स्वीकृति-अस्वीकृति के साथ कृत्रिम अनीलन चालों को युग्मित करती है।
• लक्ष्य फलन में उच्च परंतु पतली बाधाओं के माध्यम से प्राप्त करने के लिए क्वांटम अनीलन तापीय उतार-चढ़ाव के अतिरिक्त क्वांटम उतार-चढ़ाव का उपयोग करता है।
• बाधाओं के माध्यम से 'सुरंगन' द्वारा तापमान घटने के साथ-साथ कृत्रिम अनीलन की बढ़ती कठिनाई को दूर करने के लिए प्रसंभाव्य सुरंगन प्रयासों को स्थानीय न्यूनतम से बचने में मदद मिलती है।
• तब्बू खोज सामान्यतः कम ऊर्जा वाले निकटवर्ती स्थितियों में जाती है, परंतु जब वह स्वयं को स्थानीय न्यूनतम में फंसा हुआ पाती है तो वह जटिल कदम उठाती है; और पहले से देखे गए समाधानों की वर्जित सूची बनाकर चक्रों से बचती है।
• दोहरे चरण का विकास विधिकलन और प्रक्रियाओं का एक परिवार है जो खोज स्थान में चरण परिवर्तन का प्रयोग करके स्थानीय और वैश्विक खोज के मध्य मध्यस्थता करता है।
• प्रतिक्रियाशील खोज अनुकूलन यंत्र अधिगम को अनुकूलन के साथ , समस्या की विशेषताओं और वर्तमान समाधान के समीप स्थानीय स्थिति के लिए एक विधिकलन के मुक्त मापदंडों को स्व-समस्वरित करने के लिए एक आंतरिक प्रतिक्रिया चक्र को जोड़कर संयोजित करने पर ध्यान केंद्रित करता है।
• आनुवंशिक विधिकलन केवल एक समाधान के अतिरिक्त समाधानों का एक निकाय बनाए रखते हैं। नए उम्मीदवार समाधान न केवल उत्परिवर्तन द्वारा उत्पन्न होते हैं, बल्कि निकाय से दो समाधानों के पुनर्संयोजन द्वारा भी उत्पन्न होते हैं। संभाव्य मानदंड, कृत्रिम अनीलन में उपयोग किए जाने वाले समान, उत्परिवर्तन या संयोजन के लिए उम्मीदवारों का चयन करने के लिए और निकाय से अतिरिक्त समाधानों को हटाने के लिए उपयोग किया जाता है।
• मेमेटिक विधिकलन कर्ताओ के एक समुच्चय को नियोजित करके समाधान खोजते हैं जो प्रक्रिया में सहयोग और प्रतिस्पर्धा दोनों करते हैं; कभी-कभी कर्ताओ की रणनीतियों में उन्हें पुनर्संयोजित करने से पूर्व उच्च गुणवत्ता वाले समाधान प्राप्त करने के लिए कृत्रिम अनीलन प्रक्रियाएं सम्मिलित होती हैं। खोज की विविधता बढ़ाने के लिए एक तंत्र के रूप में एनीलिंग का भी सुझाव दिया गया है।
• अंशांकित अनुकूलक, अनुकूलन करते समय लक्ष्य फलन को धीरे-धीरे सुचारू करता है।
• एंट कॉलोनी अनुकूलन समाधान स्थान को पार करने और स्थानीय रूप से उत्पादक क्षेत्रों को खोजने के लिए कई चींटियों या एजेंटों का उपयोग करता है।
• संकर-एन्ट्रॉपी विधि पैरामिट्रीकृत संभाव्यता वितरण के माध्यम से उम्मीदवारों के समाधान को उत्पन्न करती है। मापदंडों को संकर-एन्ट्रॉपी न्यूनीकरण के माध्यम से अद्यतन किया जाता है, जिससे की अगले पुनरावृत्ति में उपयुक्त प्रतिरूप उत्पन्न किए जा सकें।
• सामंजस्य खोज संगीतकारों को तात्कालिक प्रक्रिया में प्रतिरूपित करता है जहां प्रत्येक संगीतकार सभी को एक साथ सर्वश्रेष्ठ सद्भाव खोजने के लिए एक धुन बजाता है।
• प्रसंभाव्य अनुकूलन विधियों का एक छत्र समुच्चय है जिसमें कृत्रिम अनीलन और कई अन्य उपागम सम्मिलित हैं।
• कण समूह अनुकूलन समूह अधिगम पर आधारित एक विधिकलन है जो खोज स्थान, या प्रतिरूप में अनुकूलन समस्या का समाधान खोजता है और उद्देश्यों की उपस्थिति में सामाजिक व्यवहार का अनुमान करता है।
• रनर-रूट विधिकलन एक मेटाह्यूरिस्टिक अनुकूलित विधिकलन है, जो प्रकृति में पौधों के रनर्स और जड़ों से प्रेरित एकलप्रतिरूप और बहुप्रतिरूप समस्याओं को हल करने के लिए है।
• मेधावी जल बूँद विधिकलन जो अनुकूलन समस्याओं को हल करने के लिए प्राकृतिक पानी की बूंदों के व्यवहार का प्रतिरूपण करता है
• समानांतर पायन संभावित बाधाओं को दूर करने के लिए विभिन्न तापमानों या हैमिल्टनियन क्वांटम यांत्रिकी पर प्रतिरूपों का अनुकरण है।
• बहुउद्देश्यीय कृत्रिम अनीलन विधिकलन का उपयोग बहुउद्देश्यीय अनुकूलन में किया गया है।

यह भी देखें

• Adaptive simulated annealing
• Automatic label placement
• Combinatorial optimization
• Dual-phase evolution
• Graph cuts in computer vision
• Intelligent water drops algorithm
• Markov chain
• Molecular dynamics
• Multidisciplinary optimization
• Particle swarm optimization
• Place and route
• Quantum annealing
• Traveling salesman problem

अग्रिम पठन

• A. Das and B. K. Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)
• Weinberger, E. (1990). "Correlated and uncorrelated fitness landscapes and how to tell the difference". Biological Cybernetics. 63 (5): 325–336. doi:10.1007/BF00202749. S2CID 851736.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.12. Simulated Annealing Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Strobl, M.A.R.; Barker, D. (2016). "On simulated annealing phase transitions in phylogeny reconstruction". Molecular Phylogenetics and Evolution. 101: 46–55. doi:10.1016/j.ympev.2016.05.001. PMC 4912009. PMID 27150349.
• V.Vassilev, A.Prahova: "The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems", International Journal INFORMATION THEORIES & APPLICATIONS, VOLUME 6/1999

बाहरी संबंध

• Simulated Annealing A Javascript app that allows you to experiment with simulated annealing. Source code included.
• "General Simulated Annealing Algorithm" An open-source MATLAB program for general simulated annealing exercises.
• Self-Guided Lesson on Simulated Annealing A Wikiversity project.
• Google in superposition of using, not using quantum computer Ars Technica discusses the possibility that the D-Wave computer being used by Google may, in fact, be an efficient simulated annealing co-processor.
• [1] A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA.