در جستجو و بهینه‌سازی از ناهار مجانی خبری نیست

در علوم کامپیوتر مواقعی پیش می‌آید که خروجی تمام روندهایی که مشغول حل یک نوع مسئله خاص هستند از لحاظ آماری مشابه هم می‌باشند. دیوید ولپرت و ویلیام مک ردی بیان زیبایی را برای چنین وضعیتی در مسائل جستجو و بهینه‌سازی  ارائه داده‌اند، و آن هم این بود که از "ناهار مجانی خبری نیست". ولپرت قبلاً براهین "هیچ ناهار مجانی" را برای یادگیری ماشین (استنتاج آماری) به دست آورده بود. قبل از اینکه مقاله ولپرت منتشر شود، کالن شفر خلاصه‌ای از کار منتشر نشده ولپرت را با اصطلاحات متفاوت به جامعه علمی عرضه کرد.
در اصطلاح "هیچ ناهار مجانی"، هر رستوران (رویه حل مسئله) یک لیست غذا دارد که هر پرس غذا (مسئله) با یک قیمت (اجرای رویه برای حل مسئله) نسبت معینی دارد. لیست‌های غذای رستوران‌ها به جز در یک مورد خاص مشابه هم هستند، آن هم این است که ترتیب قیمت‌ها در یک رستوران نسبت به رستوران بعد به هم ریخته می‌شود. برای یک همه چیزخوار که احتمال انتخاب غذاها برای او یکسان است، هزینه میانگین به رستورانی که انتخاب می‌کند بستگی نخواهد داشت. اما یک گیاهخوار که به‌طور منظم با دوست گوشتخوارش که به دنبال هزینه کمتر است به رستوران می‌رود، برای هر پرس غذا میانگین هزینه بالایی را پرداخت می‌کند. برای اینکه هزینه میانگین را کاهش دهیم باید اطلاعات مناسبی در رابطه با الف) هر کس چه چیزی سفارش می‌دهد ، ب) آن سفارش در رستوران‌های مختلف قیمتش چقدر می‌شود، داشته باشیم. در واقع برای حل این نوع مسائل نیاز به اطلاعات پیش زمینه‌ای در رابطه با رویه داریم تا بتوانیم اجرا را بهینه تر کنیم.
به بیان دیگر، زمانی که توزیع احتمالی روی نمونه‌های مسئله، نتایج توزیع شده مشابهی داشته باشند، دیگر خبری از ناهار مجانی نیست. در مورد جستجو، مسئله مورد نظر یک تابع عینی است، و نتیجه رشته‌ای از مقادیر است که از بررسی پاسخ‌های کاندید در دامنه تابع به دست می آیند. برای توصیف نوعی از نتایج، بهینه‌سازی رویه، همان جستجو است. در جستجو هیچ ناهاری مجانی نیست اگر و فقط اگر توزیع روی توابع عینی تحت جابجایی فضای پاسخ‌های کاندید، ثابت باشد. این حالت دقیقاً در عمل وجود ندارد، اما برهان "(تقریباً) هیچ ناهار مجانی" نشان می‌دهد که تقریباً وجود دارد.

خلاصه

بعضی مسائل محاسباتی با جستجو در راه حل‌های مناسب در یک فضا از پاسخ‌های کاندید حل می‌شوند. انتخاب مکرر پاسخ‌های کاندید برای بررسی را الگوریتم جستجو می نامند. در مسائل متفاوت این الگوریتم نتایج متفاوتی خواهد داشت، اما روی تمام مسائل، غیرقابل تشخیص‌اند. از این نتیجه می گیریم که اگر یک الگوریتم روی یک سری از مسائل نتایج خوبی بدست آورد، باید به مسائل دیگر اهمیت کمتری بدهد. در این حالت هیچ ناهار مجانی در جستجو نداریم. به‌طور مشابه، همانطور که شفر گفته بود، هزینه اجرا ذخیره شده‌است. جستجو معمولاً با عنوان بهینه‌سازی شناخته می‌شود، پس می‌توان گفت که در بهینه سازی ناهار مجانی وجود ندارد.
"نظریه "هیچ ناهار مجانی" ولپرت و مک ردی"، آن طور که خودشان به زبان ساده بیان کرده‌اند به این صورت است، "هر دو الگوریتم دلخواهی برابرند زمانی که هزینه اجرایشان روی تمام مسائل ممکن میانگین گرفته شود. نتیجه "هیچ ناهار مجانی" نشان می‌دهد که اختصاص هر مسئله به یک الگوریتم خاص هزینه اجرا را نسبت به استفاده از یک الگوریتم ثابت کمتر می‌کند. ایجل، توسینت، و انگلیش شرط عمومی را برقرار کردند که تحت آن هیچ ناهار مجانی نخواهد بود. در حالی که به لحاظ فیزیکی ممکن است، اما دقیقاً قابل اجرا نیست. دراست، جنسن، و وگنر برهانی را اثبات کردند که آن طور که خودشان می گفتند در عمل نشان می‌دهد که "تقریباً" هیچ ناهار مجانی نیست.
برای اینکه بتوانیم بستر نظری مناسب تری فراهم کنیم، فردی را در نظر بگیرید که می‌خواهد یک مسئله را بهینه‌سازی کند. با در نظر داشتن این که چرا این مسئله به وجود آمده، آن فرد می‌تواند آز آن دانش پیش زمینه برای انتخاب الگوریتم مناسب برای حل مسئله استفاده کند. اگر آن فرد نداند که چطور از دانش پیش زمنیه خود استفاده کند، یا اگر دانش پیش زمینه‌ای نداشته باشد، آنگاه با این مسئله مواجه می‌شود که آیا بعضی الگوریتم‌ها در دنیای واقعی بهتر از دیگر الگوریتم‌ها عمل می‌کنند یا نه. نویسندگان برهان "(تقریباً) هیچ ناهار مجانی نیست" پاسخ این مسئله را منفی می دانند، اما فکر می‌کنند امکان کاربردی کردن الگوریتم وجود دارد.

هیچ ناهاری مجانی نیست(NFL)

یک "مسئله"، یک تابع عینی است که پاسخ‌های کاندید را با مقادیر خوبی نسبت می‌دهد. یک الگوریتم جستجو یک تابع عینی را به عنوان ورودی می‌گیرد و پاسخ‌های کاندید را تک به تک ارزشیابی می‌کند. خروجی الگوریتم رشته مقادیر خوبی مشاهده شده‌است.
ولپرت و مک ردی تصریح می‌کنند که یک الگوریتم هیچ گاه یک پاسخ کاندید را دوباره ارزشیابی نمی‌کند، و هزینه اجرا الگوریتم روی خروجی‌ها محاسبه می‌شود. برای آسانی کار، هیچ عمل تصادفی در الگوریتم‌های قائل نمی‌شویم. تحت این شرایط، وقتی یک الگوریتم جستجو روی تمام ورودی‌های ممکن اجرا می‌شود، هر پاسخ خروجی را دقیقاً یک بار تولید می‌کند. چون که هزینه اجرا روی خروجی‌ها محاسبه می‌شود، الگوریتم‌ها از این نظر که در چه بازه زمانی سطح خاصی از اجرا را بدست می‌آورند غیرقابل تشخیص‌اند.
بعضی از ارزشیابی‌های هزینه اجرا نشان می‌دهد که الگوریتم‌های جستجو در بهینه سازی تابع عینی، خیلی خوب عمل می‌کنند. در واقع، به نظر می‌رسد که هیچ برنامه جالبی از الگوریتم‌های جستجو وجود ندارد که بهینه‌سازی نکند. یکی از روش‌های ارزشیابی اجرا به‌کارگیری کمترین شاخص از کمترین مقدار در رشته خروجی است. این تعداد ارزشیابی‌های لازم برای کمینه کردن تابع عینی است. برای بعضی از الگوریتم ها، زمان لازم برای یافتن کمینه به تعداد ارزشیابی‌ها بستگی دارد.
براهین اصلی هیچ ناهار مجانی نیست(NFL) فرض می‌کنند که تمام توابع عینی به‌طور مساوی احتمال ورودی گرفتن الگوریتم جستجو را دارند. بنابراین گفته می‌شود یک NFL وجود دارد اگر و فقط اگر به هم ریختن توابع عینی روی احتمال آن‌ها هیچ تأثیری نداشته باشد. با اینکه این شرط NFL از لحاظ فیزیکی ممکن است، اما در عمل به کار نمی‌آید.
تفسیر واضح نقیض NFL قاعدتاً "ناهار مجانی وجود دارد" است. اما این گمراه‌کننده است. NFL یک درجه است نه یک گزاره صفر و یک منطقی. اگر شرایط NFL دقیقاً برقرار باشد آنگاه تمام الگوریتم‌ها برای تمام توابع عینی تقریباً نتایج یکسانی خواهند داشت. باید توجه داشت که نقیض NFL نشان می‌دهد که تنها آن الگوریتم‌ها روی هم رفته با اندازه‌گیری هزینه اجرا با هم برابر نیستند. برای اندازه‌گیری سود اجرا، الگوریتم‌ها ممکن است کاملاً یا تقریباً برابر بمانند.
در حالت نظری، تمام الگوریتم‌ها همیشه در بهینه‌سازی خیلی خوب اجرا می‌شوند. این یعنی اینکه یک الگوریتم با تعداد نسبتاً کمی از ارزشیابی ها، پاسخ‌های خوبی برای تقریباً تمام توابع عینی بدست می‌آورد. دلیلش این است که تقریباً تمام توابع عینی درجه بالایی از کلماگوراف از خود بروز می دهند. این نشان دهنده یک بی نظمی و غیرقابل پیش‌بینی بودن شدید است. تمام سطوح خوبی‌ها به‌طور مساوی به تمام پاسخ‌های کاندید ارائه می‌شوند، و پاسخ‌های خوب در تمام فضای کاندیدها پراکنده می‌شوند. الگوریتم جستجو ندرتاً بیشتر از بخش کوچکی از کاندیدها را برای محل یابی یک پاسخ خیلی خوب ارزشیابی می‌کند.
در عمل تمام توابع عینی و الگوریتم‌ها از چنان پیچیدگی کولماگورافی برخوردارند که هیچ گاه بر انگیخته نمی‌شوند . در توابع عینی نمونه یا الگوریتم، اطلاعات بیشتری از آنچه ست لوید تخمین زده بود که جهان قابلیت نگهداری آن را دارد وجود دارد. به‌طور مثال، اگر هر پاسخ کاندید به شکل رشته‌ای از 300 0 و 1 کد شود، و مقادیر ارزش خوبی 0 و 1 باشند، آنگاه اکثر توابع عینی پیچیدگی کولماگوراف با اندازه حداقل 2³⁰⁰ دارند، و این بزرگتر از مرز 2²⁹⁹ لوید است. نتیجه می گیریم تمام برهان "هیچ ناهار مجانی" در دنیای فیزیکی صدق نمی‌کند. در حالت عملی، الگوریتم‌هایی که آنقدر کوچک هستند که در نرم‌افزارها به کار آیند در مقابل آن‌هایی که بزرگترند، اجرای بهتری دارند.

بیان ریاضی NFL

مجموعه‌ای از تمام توابع عینی f:X→Y است، که  فضایی محدود از پاسخ هاست و  مجموعه جزئاً مرتب و متناهی. مجموعه تمام جایگشت‌های  از  است. یک متغیر تصادفی مانند F روی  توزیع شده‌است. برای تمام jهای در J، هر F o j متغیری تصادفی است که روی  توزیع شده‌است، با احتمال P(F o j = f) = P(F = f o j–1 برای تمام f در .
فرض کنید (a(f خروجی الگوریتم جستجوی a برای ورودی f باشد. اگر (a(F و (b(F به‌طور یکسان برای تمام الگوریتم‌های جستجو a و b توزیع شده باشند، آنگاه F یک توزیع NFL دارد. این شرط این امر را در نظر دارد که اگر و فقط اگر F و F o j به‌طور مشابه روی j برای تمام J‌ها توزیع شده باشند. به بیان دیگر، هیچ ناهار مجانی برای الگوریتم‌های جستجو نخواهد بود اگر و فقط اگر توزیع توابع عینی تحت جایگشت فضای پاسخ‌ها ثابت باشد.
قسمت "فقط اگر" اولین بار توسط شوماخر در پایان‌نامه دکترایش با عنوان "جستجوی جعبه سیاه – چارچوب‌ها و روش‌ها" منتشر شد.(دانشگاه تنسی) براهین NFL اخیراً به شمارش‌های دلخواه X و Y عمومی‌سازی شده‌اند.

ناهار مجانی هم تکاملی

ولپرت و مک ردی اثبات کردند که در بهینه‌سازی هم تکاملی ها ناهار مجانی وجود دارد. تحلیل آن‌ها مسائل خود-بازی را پوشش می‌دهد که در آن مجموعه‌ای از بازیکنان با هم فعالیت می‌کنند تا یک قهرمان بدست آید، که بعداً یک یا چند رقیب را در بازی‌های بعد به کار می‌گیرد. این بدان معناست که، هدف این است که بازیکن خوبی بدست آوریم، اما بدون یک تابع عینی. خوبی هر بازیکن(پاسخ کاندید) با مشاهده نحوه رقابتش با دیگران ارزیابی می‌شود. الگوریتم بازیکن‌ها و کیفیت بازی آن‌ها را می‌گیرد تا بازیکنان بهتری انتخاب کند. بازیکنی که الگوریتم اول قرار دهد قهرمان می‌شود. ولپرت و مک ردی نشان دادند که بعضی از الگوریتم‌های هم تکاملی در انتخاب قهرمان نسبت به الگوریتم‌های دیگر بهتر عمل می‌کنند. تولید یک قهرمان از طریق خود-بازی یکی از مباحث مهم در محاسبات تکاملی و نظریه بازی هاست. نتایج روی هم تکاملی گونه‌های زیستی قابل اجرا نیست زیرا در این حالات قهرمانی وجود ندارد.