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