अत्यधिक अनुकूलन (EO) एक मेटाह्यूरिस्टिक एल्गोरिथ्म है जो संयोजनात्मक अनुकूलन के लिए है, जिसे 1999 में स्टीफन बोएटचर और एलन जी. पर्कस द्वारा प्रस्तुत किया गया था। यह बाक-स्नैपेन मॉडल के स्व-संगठित क्रांतिकता से प्रेरित है, जो वर्णन करता है कि प्रकृति में सिस्टम कम-फिट घटकों के बार-बार हटाने के माध्यम से एक क्रांतिक अवस्था में कैसे विकसित होते हैं। अनुकूलन में, EO समस्याओं को बाइनरी या मूल्यवान चरों के सेट से एक उम्मीदवार समाधान बनाकर, फिर सबसे खराब स्थानीय फिटनेस वाले चर को बार-बार चुनकर और उसे यादृच्छिक मान से बदलकर हल करता है, जिससे समाधान स्थान को पक्षपाती, अत्यधिक प्रक्रिया के माध्यम से खोजा जाता है।
यह एल्गोरिथ्म अपनी सरलता और कठिन समस्याओं पर उच्च-गुणवत्ता वाले समाधान प्राप्त करने के लिए उल्लेखनीय है, बिना ग्रेडिएंट जानकारी पर निर्भर हुए। यह विकासवादी गणना विधियों के व्यापक वर्ग से संबंधित है, लेकिन आनुवंशिक एल्गोरिथ्म से भिन्न है, जो जनसंख्या प्रजनन और क्रॉसओवर का उपयोग करते हैं। इसके बजाय, EO एक एकल समाधान का उपयोग करता है और पावर-लॉ चयन संभावना के माध्यम से संचालित होता है, जिससे समाधान स्थान में कभी-कभी बड़े उछाल संभव होते हैं। यह स्टोकेस्टिक व्यवहार स्थानीय ऑप्टिमा से बचने में मदद करता है और अक्सर लगभग-इष्टतम परिणाम पाता है, विशेष रूप से यात्रा विक्रेता समस्या, ग्राफ विभाजन, और स्पिन ग्लास ग्राउंड स्टेट समस्या जैसी समस्याओं के लिए।
ऐतिहासिक विकास
यह विधि पहली बार 1999 में बोइस और पर्कस द्वारा प्रस्तुत की गई थी और "एक्सट्रीमल ऑप्टिमाइज़ेशन: मेथड्स डेरिव्ड फ्रॉम को-इवोल्यूशन" शीर्षक के तहत जर्नल फिजिकल रिव्यू लेटर्स में प्रकाशित हुई थी। उनका काम इस अवलोकन से प्रेरित था कि प्रकृति में सिस्टम, जैसे रेत के ढेर और जैविक पारिस्थितिकी तंत्र, खराब प्रदर्शन करने वाले तत्वों के उन्मूलन के माध्यम से एक क्रांतिक अवस्था की ओर स्व-संगठित होते हैं। इससे एक सरल, उत्परिवर्तन-आधारित ह्यूरिस्टिक का विकास हुआ, जो अधिक जटिल, जनसंख्या-संचालित दृष्टिकोणों के विपरीत है। प्रारंभिक प्रयोगों ने दिखाया कि EO बड़े पैमाने पर NP-कठिन समस्याओं पर सिम्युलेटेड एनीलिंग के प्रदर्शन को मिला सकता है या उससे आगे निकल सकता है, जिससे अनुकूलन साहित्य में इसका स्थान स्थापित हुआ।
अपनी शुरुआत के बाद से, EO को विभिन्न क्षेत्रों में विस्तारित और लागू किया गया है, जिसमें दो-तरफा ग्राफ विभाजन, ग्राफ रंग, और हाल ही में, मशीन लर्निंग में सुविधाओं का चयन शामिल है। विभिन्न रूपों ने बाधित समस्याओं को संभालने और अनुकूली संभावना वितरण के माध्यम से अभिसरण में सुधार करने के तरीके प्रस्तावित किए हैं। कार्य ने EO को स्व-संगठित क्रांतिकता की गतिशीलता से भी जोड़ा है, जो इसके व्यवहार के लिए सैद्धांतिक औचित्य प्रदान करता है।
मुख्य एल्गोरिथ्म और यांत्रिकी
मूल EO एल्गोरिथ्म निम्नानुसार काम करता है:
- समस्या को एक खोज स्थान के साथ परिभाषित करें जहां प्रत्येक संभावित समाधान चर (या स्पिन) के सेट से बना होता है जिसमें निर्दिष्ट मान होते हैं।
- प्रत्येक चर के लिए, एक स्थानीय फिटनेस मान की गणना की जाती है जो समाधान की कुल लागत या फिटनेस में उसके योगदान पर आधारित होती है।
- प्रत्येक पुनरावृत्ति पर, सबसे खराब (न्यूनतम) स्थानीय फिटनेस वाला चर, जिसे अत्यधिक चर कहा जाता है, चुना जाता है। फिर उसे एक नया यादृच्छिक मान दिया जाता है, जो संभावित असाइनमेंट के डोमेन से चुना जा सकता है।
- पावर लॉ के समानुपाती संभावना वितरण का उपयोग अक्सर अपडेट करने के लिए चर का चयन करने में किया जाता है, जो सबसे-खराब-केवल चयन से बचाता है जो प्रक्रिया को फंसा सकता है। रैंक r वाले चर के लिए एक विशिष्ट चयन संभावना p(r) ~ r^-τ है, जिसमें τ आमतौर पर लगभग 1 के मान पर सेट होता है।
- प्रत्येक अपडेट के बाद, प्रभावित चरों की स्थानीय फिटनेस की पुनर्गणना की जाती है, और प्रक्रिया निश्चित संख्या में पुनरावृत्तियों के लिए या रोक मानदंड पूरा होने तक दोहराई जाती है।
एक उल्लेखनीय विशेषता यह है कि EO किसी स्पष्ट स्थानीय खोज चरण या हिल क्लाइंबिंग का उपयोग नहीं करता है। इसके बजाय, एकल उत्परिवर्तन और टाउ-पैरामीटर अन्वेषण और दोहन के बीच संतुलन प्रदान करते हैं। एक छोटा τ अधिक यादृच्छिक परिवर्तनों की ओर ले जाता है, जबकि एक बड़ा τ चयन को सबसे खराब में से सर्वश्रेष्ठ की ओर पक्षपाती बनाता है, जो तब सहायक हो सकता है जब केवल कुछ खराब घटक समस्या का कारण बनते हैं। अंतिम समाधान की गुणवत्ता उच्चतम स्थानीय फिटनेस मान है जो रन के दौरान किसी भी बिंदु पर देखा गया है, जिसे अक्सर ट्रैक किया जाता है।
कंप्यूटिंग सिस्टम में अनुप्रयोग
EO को विभिन्न प्रकार की अनुकूलन चुनौतियों पर लागू किया गया है। Artificial intelligence के क्षेत्र में, इसका उपयोग तंत्रिका नेटवर्क टोपोलॉजी विकसित करने और हाइपरपैरामीटर ट्यून करने के लिए किया गया है, जो ग्रेडिएंट-आधारित विधियों का विकल्प प्रदान करता है। Machine learning में, इसे फीचर चयन पर लागू किया गया है, जहां लक्ष्य भविष्य कहनेवाला चरों का सर्वोत्तम उपसमुच्चय चुनना है; EO अच्छा प्रदर्शन करता है क्योंकि फीचर्स को घटकों के रूप में माना जा सकता है जिनकी स्थानीय फिटनेस सत्यापन सटीकता में उनके योगदान पर आधारित होती है।
इसके अलावा, EO का उपयोग अक्सर संयोजनात्मक अनुकूलन उदाहरणों जैसे बिन पैकिंग समस्या, जॉब-शॉप शेड्यूलिंग, और त्रुटि-सुधार कोड के निर्माण को हल करने के लिए किया जाता है। इसका उपयोग समानांतर और वितरित सिस्टम के डिजाइन में भी किया जाता है, उदाहरण के लिए, मेकस्पैन को कम करने के लिए प्रोसेसर को कार्य सौंपना। ग्रेडिएंट जानकारी की कमी का मतलब है कि इसे उन समस्याओं पर लागू किया जा सकता है जहां उद्देश्य असंतत या असतत है। ग्राफ बाइपार्टिशन पर लागू होने पर, EO को उत्कृष्ट समुदाय पहचान परिणाम उत्पन्न करते हुए दिखाया गया है, जो एक प्रमुख ग्राफ-विभाजन एल्गोरिथ्म से मेल खाता है।
अन्य मेटाह्यूरिस्टिक्स से संबंध
EO आनुवंशिक एल्गोरिथ्म और सिम्युलेटेड एनीलिंग के साथ परिवार समानता साझा करता है, लेकिन एक अलग तंत्र का उपयोग करता है। आनुवंशिक एल्गोरिथ्म समाधानों की एक जनसंख्या बनाए रखते हैं और पुनर्संयोजन और उत्परिवर्तन का उपयोग करते हैं; EO एक एकल समाधान का उपयोग करता है। सिम्युलेटेड एनीलिंग पूरे समाधान को यादृच्छिक गड़बड़ी से संशोधित करता है और तापमान के अनुसार परिवर्तन स्वीकार करता है; EO केवल सबसे खराब घटक को संशोधित करता है, जो स्थानीय फिटनेस द्वारा निर्देशित होता है। महत्वपूर्ण अंतर यह है कि EO में बदलने के लिए घटक का चयन रैंक के आधार पर नियतात्मक (या पावर-लॉ यादृच्छिक) है, न कि पूरे समाधान के उद्देश्य फ़ंक्शन मान पर।
स्व-संगठित क्रांतिकता (SOC) के साथ एक सैद्धांतिक संबंध का मतलब है कि EO प्राकृतिक प्रणालियों में देखे गए पावर-लॉ उतार-चढ़ाव को पुन: उत्पन्न करता है, जो इसे कई प्रकार के परिदृश्यों के लिए मजबूती देता है। क्लासिक बेंचमार्क (यात्रा विक्रेता समस्या) पर तुलना में, EO सिम्युलेटेड एनीलिंग के साथ प्रतिस्पर्धी है, लेकिन अक्सर कम फ़ंक्शन मूल्यांकन की आवश्यकता होती है। व्यावहारिक रूप से, उन समस्याओं के लिए जहां पड़ोस घटक फिटनेस की रैंक द्वारा परिभाषित होते हैं, EO एक सरल कार्यान्वयन के साथ भी कुशल हो सकता है।
विस्तार और विविधताएं
शोध ने कई विविधताएं उत्पन्न की हैं। सबसे आम टाउ-EO है, जहां पैरामीटर टाउ उच्च-रैंक चर चुनने की संभावना को नियंत्रित करता है। टाउ का मान और पावर-लॉ पूंछ की सीमा को स्थिरता में सुधार के लिए ट्यून किया जा सकता है। एक अन्य विविधता संभाव्य हिल-क्लाइंबिंग है जिसमें पूंछ में जिटर शामिल होता है। एक और दृष्टिकोण, सह-विकास, इंटरैक्टिंग घटकों वाली समस्याओं को संभालता है, जहां सह-अनुकूलन के आधार पर एक से अधिक चर उत्परिवर्तित होते हैं। हाल ही में, एल्गोरिथ्म को स्थानीय खोज ह्यूरिस्टिक्स के साथ जोड़ा गया है, जिससे हाइब्रिड EO उत्पन्न होता है जो EO खोज चरण के बाद अतिरिक्त फाइन-ट्यूनिंग करता है।
Deep learning अनुप्रयोगों में, मॉडल आर्किटेक्चर को स्वचालित रूप से ट्यून करने के लिए EO का एक रूप उपयोग किया गया है, विशेष रूप से Neural network खोजों में, हालांकि इसे अधिक जटिल विधियों द्वारा प्रतिस्थापित किया गया है। EO को ग्रेडिएंट की आवश्यकता नहीं होती है, जिससे यह उन मॉडलों पर लागू होता है जहां ग्रेडिएंट अनुपलब्ध या महंगे होते हैं, जैसे गैर-विभेदनीय हानि। यह सुदृढीकरण सीखने समस्याओं में असतत स्थानों की खोज के लिए भी उपयुक्त है।
सीमाएं और खुला शोध
EO के साथ एक प्रमुख चुनौती टाउ पैरामीटर और पावर-लॉ की मान सीमा निर्धारित करना है। एक खराब चुना गया टाउ खराब अभिसरण या अराजकता की ओर ले जा सकता है। इसके अलावा, क्योंकि यह प्रति समय केवल एक चर को संशोधित करता है, बहुत बाधित समस्याओं या चरों के बीच निर्भरता वाली समस्याओं को उच्च कम्प्यूटेशनल लागत से बचने के लिए फिटनेस के सावधानीपूर्वक औपचारिकरण की आवश्यकता होती है।
खुला शोध EO को अधिक अनुकूली बनाने पर केंद्रित है, जैसे उड़ान पर टाउ का अनुमान लगाना या टाउ के लिए एनीलिंग शेड्यूल का उपयोग करना। ऐसे कार्य भी हैं जिनमें चर के लिए यादृच्छिक मान प्रतिस्थापन चुनने के अधिक उन्नत तरीके शामिल हो सकते हैं, और वितरित सेटिंग में EO का उपयोग करना शामिल है।
हालांकि EO की सैद्धांतिक समझ अन्य मेटाह्यूरिस्टिक्स की तरह परिपक्व नहीं है, यह संयोजनात्मक अनुकूलन और प्रकृति-प्रेरित कंप्यूटिंग के टूल सेट के भीतर एक उल्लेखनीय अवधारणा है, क्योंकि इसे लागू करना सरल है और कई प्रकार की कठिन समस्याओं के लिए मजबूत है। भविष्य में विशेष ऑप्टिमाइज़र के साथ अधिक एकीकरण और व्यावहारिक शेड्यूलिंग और डिजाइन के लिए इसके पावर-लॉ आंकड़ों का आगे अध्ययन देखने की संभावना है।
प्रमुख शोधकर्ता और प्रभाव
मूल लेखक, स्टीफन बोएटचर और एल पर्कस (दोनों उस समय सांता फे इंस्टीट्यूट में), SOC परिप्रेक्ष्य को अनुकूलन में लाए। अन्य समूहों द्वारा बाद के कार्य, जिनमें ज़ेरॉक्स पार्क और बर्कले एआई रिसर्च शामिल हैं, ने विधि के ढांचे और विश्लेषण का विस्तार किया है। हालांकि यह आधुनिक मशीन-लर्निंग टूलिंग में अग्रणी नहीं है, यह प्रकृति-प्रेरित ह्यूरिस्टिक्स में एक संदर्भ बना हुआ है और अक्सर विकासवादी गणना पर पाठ्यक्रम सामग्री में शामिल किया जाता है।
संक्षेप में, अत्यधिक अनुकूलन कठिन संयोजनात्मक समस्याओं का अनुमान लगाने के लिए एक न्यूनतम, गैर-ग्रेडिएंट, स्टोकेस्टिक ढांचा प्रदान करता है, और इसका सैद्धांतिक शोध और उन अनुप्रयोगों दोनों में निरंतर मूल्य है जहां समस्या को एकल फिटनेस मान वाले घटकों में विघटित किया जा सकता है।
सीमाएं और नोट्स
व्यावहारिक उपयोग के लिए, जो लोग इसे आजमाते हैं उन्हें पता होना चाहिए कि विधि वैश्विक इष्टतमता की गारंटी प्रदान नहीं करती है, और कुछ समस्याओं को चयन संभावना वितरण के ट्यूनिंग की आवश्यकता हो सकती है। उचित सेटअप के साथ, यह एक सरल फिर भी प्रभावी अनुकूलन उपकरण हो सकता है।