खोज और अनुकूलन में कोई निःशुल्क लंच नहीं

This article is about mathematical analysis of computing. For associated folklore and broad implications of the theorem, see No free lunch theorem.

समस्या तेजी से उम्मीदवारों ए, बी, और सी के बीच एक समाधान ढूंढना है जो किसी भी अन्य के समान अच्छा हो, जहां अच्छाई या तो 0 या 1 है। समस्या के आठ उदाहरण (लंच प्लेट) हैं, जहां एक्स, वाई, और z क्रमशः a, b, और c की अच्छाई को दर्शाते हैं। प्रक्रिया (रेस्तरां) ए उम्मीदवारों का मूल्यांकन ए, बी, सी क्रम में करता है और बी उस क्रम के विपरीत उम्मीदवारों का मूल्यांकन करता है, लेकिन प्रत्येक 5 मामलों में 1 मूल्यांकन, 2 मामलों में 2 मूल्यांकन और 1 मामले में 3 मूल्यांकन का शुल्क लेता है।

कम्प्यूटेशनल जटिलता सिद्धांत और अनुकूलन (गणित) में नो फ्री लंच प्रमेय एक परिणाम है जो बताता है कि कुछ प्रकार की गणितीय समस्याओं के लिए, समाधान खोजने की कम्प्यूटेशनल लागत, कक्षा में सभी समस्याओं पर औसत, किसी भी समाधान विधि के लिए समान है . यह नाम इस कहावत की ओर संकेत करता है कि मुफ़्त लंच जैसी कोई चीज़ नहीं होती, अर्थात कोई भी तरीका शॉर्ट कट प्रदान नहीं करता। यह इस धारणा के तहत है कि खोज स्थान एक संभाव्यता घनत्व फ़ंक्शन है। यह उस मामले पर लागू नहीं होता है जहां खोज स्थान में अंतर्निहित संरचना होती है (उदाहरण के लिए, एक अलग कार्य है) जिसे यादृच्छिक खोज की तुलना में अधिक कुशलता से उपयोग किया जा सकता है (उदाहरण के लिए, अनुकूलन में न्यूटन की विधि) या यहां तक ​​कि बंद-फॉर्म समाधान भी हैं (उदाहरण के लिए, एक द्विघात बहुपद का चरम) जिसे बिना किसी खोज के निर्धारित किया जा सकता है। ऐसी संभाव्य धारणाओं के लिए, किसी विशेष प्रकार की समस्या को हल करने वाली सभी प्रक्रियाओं के आउटपुट सांख्यिकीय रूप से समान होते हैं। ऐसी परिस्थिति का वर्णन करने का एक रंगीन तरीका, खोज की समस्याओं के संबंध में डेविड वोल्पर्ट और विलियम जी. मैकरेडी द्वारा प्रस्तुत किया गया और अनुकूलन, कहने का तात्पर्य यह है कि TANSTAAFL. वोल्पर्ट ने पहले यंत्र अधिगम (सांख्यिकीय अनुमान) के लिए कोई मुफ्त लंच प्रमेय नहीं निकाला था। वोल्पर्ट का लेख प्रकाशित होने से पहले, कुलेन शेफ़र ने स्वतंत्र रूप से वोल्पर्ट के प्रमेयों में से एक का एक प्रतिबंधित संस्करण साबित किया और इसका उपयोग प्रेरण की समस्या पर मशीन लर्निंग अनुसंधान की वर्तमान स्थिति की आलोचना करने के लिए किया। मुफ्त लंच नहीं के रूपक में, प्रत्येक रेस्तरां (समस्या-समाधान प्रक्रिया) में प्रत्येक लंच प्लेट (समस्या) को मूल्य (समस्या को हल करने में प्रक्रिया का प्रदर्शन) के साथ जोड़ने वाला एक मेनू होता है। रेस्तरां के मेनू एक मामले को छोड़कर समान हैं - कीमतें एक रेस्तरां से दूसरे रेस्तरां में बदलती रहती हैं। एक सर्वाहारी के लिए जो किसी अन्य की तरह प्रत्येक प्लेट का ऑर्डर देने की संभावना रखता है, दोपहर के भोजन की औसत लागत रेस्तरां की पसंद पर निर्भर नहीं करती है। लेकिन एक शाकाहारी जो किफायत चाहने वाले मांसाहारी के साथ नियमित रूप से दोपहर के भोजन के लिए जाता है, उसे दोपहर के भोजन के लिए उच्च औसत लागत का भुगतान करना पड़ सकता है। औसत लागत को व्यवस्थित रूप से कम करने के लिए, किसी को पहले से पता होना चाहिए कि ए) वह क्या ऑर्डर करेगा और बी) विभिन्न रेस्तरां में ऑर्डर की लागत क्या होगी। अर्थात्, समस्या-समाधान में प्रदर्शन में सुधार प्रक्रियाओं को समस्याओं से मिलाने के लिए पूर्व सूचना का उपयोग करने पर निर्भर करता है। औपचारिक शब्दों में, कोई मुफ्त लंच नहीं होता है जब समस्या के उदाहरणों पर संभाव्यता वितरण ऐसा होता है कि सभी समस्या समाधानकर्ताओं के परिणाम समान रूप से वितरित होते हैं। खोज एल्गोरिदम के मामले में, इस संदर्भ में एक समस्या उदाहरण एक विशेष उद्देश्य फ़ंक्शन है, और परिणाम फ़ंक्शन के फ़ंक्शन डोमेन में उम्मीदवार समाधानों के मूल्यांकन में प्राप्त मूल्यों का एक अनुक्रम है। परिणामों की विशिष्ट व्याख्याओं के लिए, खोज एक अनुकूलन (गणित) प्रक्रिया है। खोज में कोई निःशुल्क लंच नहीं है यदि और केवल यदि उम्मीदवार समाधानों के स्थान के क्रमपरिवर्तन के तहत वस्तुनिष्ठ कार्यों पर वितरण अपरिवर्तनीय (गणित) है। यह स्थिति व्यवहार में सटीक रूप से लागू नहीं होती,लेकिन (लगभग) कोई निःशुल्क लंच प्रमेय यह नहीं सुझाता कि यह लगभग सही है।

अवलोकन

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

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

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

प्रमेय

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

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

मूल नो फ्री लंच (एनएफएल) प्रमेय मानता है कि सभी वस्तुनिष्ठ कार्यों के खोज एल्गोरिदम में इनपुट होने की समान संभावना है।तब से यह स्थापित हो गया है कि एनएफएल तभी है जब, शिथिल रूप से कहें तो, वस्तुनिष्ठ कार्यों में फेरबदल का उनकी संभावनाओं पर कोई प्रभाव नहीं पड़ता है।यद्यपि एनएफएल के लिए यह स्थिति भौतिक रूप से संभव है, यह तर्क दिया गया है कि यह निश्चित रूप से सटीक रूप से लागू नहीं होती है।

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

कोलमोगोरोव यादृच्छिकता

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

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

लगभग सभी वस्तुनिष्ठ कार्य इतनी उच्च कोलमोगोरोव जटिलता के हैं कि उन्हें किसी विशेष कंप्यूटर में संग्रहीत नहीं किया जा सकता है।अधिक सटीक रूप से, यदि हम किसी दिए गए भौतिक कंप्यूटर को आधुनिक कंप्यूटर की यादों के क्रम में दिए गए आकार की मेमोरी के साथ एक रजिस्टर मशीन के रूप में मॉडल करते हैं, तो अधिकांश उद्देश्य कार्यों को उनकी यादों में संग्रहीत नहीं किया जा सकता है। विशिष्ट वस्तुनिष्ठ फ़ंक्शन या एल्गोरिदम में सेठ लॉयड के अनुमान से अधिक जानकारी है कि अवलोकन योग्य ब्रह्मांड पंजीकरण करने में सक्षम है। उदाहरण के लिए, यदि प्रत्येक उम्मीदवार समाधान को 300 0 और 1 के अनुक्रम के रूप में एन्कोड किया गया है, और अच्छाई मान 0 और 1 हैं, तो अधिकांश उद्देश्य कार्यों में कोलमोगोरोव जटिलता कम से कम 2 है³⁰⁰बिट्स, और यह लॉयड की 10 की सीमा से अधिक है⁹⁰ ≈ 2²⁹⁹बिट्स. इसका तात्पर्य यह है कि मूल नो फ्री लंच प्रमेय उस चीज़ पर लागू नहीं होता है जिसे भौतिक कंप्यूटर में संग्रहीत किया जा सकता है; इसके बजाय तथाकथित सख्त नो फ्री लंच प्रमेय को लागू करने की आवश्यकता है। यह भी दिखाया गया है कि एनएफएल परिणाम अतुलनीय कार्यों पर लागू होते हैं।

औपचारिक सारांश

$Y^{X}$ सभी वस्तुनिष्ठ फलनों का समुच्चय f:X→Y है, जहाँ $X$ एक परिमित समाधान स्थान है और $Y$ एक परिमित स्थिति है. X के सभी क्रमपरिवर्तनों का समुच्चय J है। एक यादृच्छिक चर F वितरित किया गया है $Y^{X}$. जे में सभी जे के लिए, एफ ओ जे एक यादृच्छिक चर वितरित किया गया है $Y^{X}$, P(F o j = f) = P(F = f o j के साथ⁻¹) सभी एफ के लिए $Y^{X}$.

मान लीजिए a(f) इनपुट f पर खोज एल्गोरिदम a के आउटपुट को दर्शाता है। यदि a(F) और b(F) को सभी खोज एल्गोरिदम a और b के लिए समान रूप से वितरित किया जाता है, तो F के पास NFL वितरण है। यह शर्त तभी लागू होती है जब एफ और एफ ओ जे को जे में सभी जे के लिए समान रूप से वितरित किया जाता है।दूसरे शब्दों में, खोज एल्गोरिदम के लिए कोई मुफ्त लंच नहीं है यदि और केवल यदि समाधान स्थान के क्रमपरिवर्तन के तहत उद्देश्य कार्यों का वितरण अपरिवर्तनीय है। सेट-सैद्धांतिक एनएफएल प्रमेयों को हाल ही में मनमानी कार्डिनैलिटी के लिए सामान्यीकृत किया गया है $X$ और $Y$.

उत्पत्ति

वोल्पर्ट और मैकरेडी दो प्रमुख एनएफएल प्रमेय देते हैं, पहला वस्तुनिष्ठ कार्यों के बारे में जो खोज जारी रहने के दौरान नहीं बदलते हैं, और दूसरा वस्तुनिष्ठ कार्यों के बारे में जो बदल सकते हैं।

प्रमेय 1: एल्गोरिदम की किसी भी जोड़ी के लिए₁ और ए₂

$\sum _{f}P(d_{m}^{y}|f,m,a_{1})=\sum _{f}P(d_{m}^{y}|f,m,a_{2}),$ कहाँ $d_{m}^{y}$ आकार के क्रमबद्ध सेट को दर्शाता है $m$ लागत मूल्यों का $y\in Y$ इनपुट मानों से संबद्ध $x\in X$, $f:X\rightarrow Y$ क्या फ़ंक्शन को अनुकूलित किया जा रहा है और $P(d_{m}^{y}|f,m,a)$ एल्गोरिथम से लागत मूल्यों के दिए गए अनुक्रम को प्राप्त करने की सशर्त संभावना है $a$ दौड़ना $m$ समारोह में कई बार $f$.

संक्षेप में, यह कहता है कि जब सभी फ़ंक्शन f समान रूप से संभावित होते हैं, तो खोज के दौरान m मानों के मनमाने अनुक्रम को देखने की संभावना खोज एल्गोरिदम पर निर्भर नहीं होती है।

दूसरा प्रमेय समय-भिन्न उद्देश्य कार्यों के लिए अधिक सूक्ष्म एनएफएल परिणाम स्थापित करता है।

परिणामों की व्याख्या

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

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

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

• व्यवहार में, कुछ एल्गोरिदम उम्मीदवार समाधानों का पुनर्मूल्यांकन करते हैं। केवल पहले कभी मूल्यांकन न किए गए उम्मीदवारों के प्रदर्शन पर विचार करने का कारण यह सुनिश्चित करना है कि एल्गोरिदम की तुलना करते समय सेब की तुलना सेब से की जा रही है। इसके अलावा, किसी एल्गोरिदम की श्रेष्ठता जो कभी भी किसी अन्य एल्गोरिदम पर उम्मीदवारों का पुनर्मूल्यांकन नहीं करती है जो किसी विशेष समस्या पर करता है, उसका समस्या की विशेषज्ञता से कोई लेना-देना नहीं हो सकता है।

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

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

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

सहविकास

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

यह भी देखें

• विकासवादी सूचना विज्ञान
• आगमनात्मक पूर्वाग्रह
• ओकाम का उस्तरा
• सादगी
• बदसूरत बत्तख का बच्चा प्रमेय

बाहरी संबंध

• http://www.no-free-lunch.org
• Radcliffe and Surry, 1995, "Fundamental Limitations on Search Algorithms: Evolutionary Computing in Perspective" (an early published paper on NFL, appearing soon after Schaffer's ICML paper, which in turn was based on Wolpert's preprint; available in various formats)
• NFL publications by Thomas English
• NFL publications by Christian Igel and Marc Toussaint
• NFL and "free lunch" publications by Darrell Whitley
• Old list of publications by David Wolpert, William Macready, and Mario Koeppen on optimization and search