موضوع مقاله: در جستجو و بهینه‌سازی از ناهار مجانی خبری نیست | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # در جستجو و بهینه‌سازی از ناهار مجانی خبری نیست | مقدمه: یک هیوریستیک ممکن است از یک هیوریستیک دیگر در حل مسئله یا دامنه‌ای از مسائل بهتر عمل کند، اما در دامنه دیگری از مسائل بدتر باشد. | ## بخش 1: در جستجو و بهینه‌سازی از ناهار مجانی خبری نیست | در علوم کامپیوتر مواقعی پیش می‌آید که خروجی تمام روندهایی که مشغول حل یک نوع مسئله خاص هستند از لحاظ آماری مشابه هم می‌باشند. در اصطلاح "هیچ ناهار مجانی"، هر رستوران (رویه حل مسئله) یک لیست غذا دارد که هر پرس غذا (مسئله) با یک قیمت (اجرای رویه برای حل مسئله) نسبت معینی دارد. لیست‌های غذای رستوران‌ها به جز در یک مورد خاص مشابه هم هستند، آن هم این است که ترتیب قیمت‌ها در یک رستوران نسبت به رستوران بعد به هم ریخته می‌شود. برای یک همه چیزخوار که احتمال انتخاب غذاها برای او یکسان است، هزینه میانگین به رستورانی که انتخاب می‌کند بستگی نخواهد داشت. اما یک گیاهخوار که به‌طور منظم با دوست گوشتخوارش که به دنبال هزینه کمتر است به رستوران می‌رود، برای هر پرس غذا میانگین هزینه بالایی را پرداخت می‌کند. برای اینکه هزینه میانگین را کاهش دهیم باید اطلاعات مناسبی در رابطه با الف) هر کس چه چیزی سفارش می‌دهد ، ب) آن سفارش در رستوران‌های مختلف قیمتش چقدر می‌شود، داشته باشیم. در واقع برای حل این نوع مسائل نیاز به اطلاعات پیش زمینه‌ای در رابطه با رویه داریم تا بتوانیم اجرا را بهینه تر کنیم. به بیان دیگر، زمانی که توزیع احتمالی روی نمونه‌های مسئله، نتایج توزیع شده مشابهی داشته باشند، دیگر خبری از ناهار مجانی نیست. در مورد جستجو، مسئله مورد نظر یک تابع عینی است، و نتیجه رشته‌ای از مقادیر است که از بررسی پاسخ‌های کاندید در دامنه تابع به دست می آیند. در جستجو هیچ ناهاری مجانی نیست اگر و فقط اگر توزیع روی توابع عینی تحت جابجایی فضای پاسخ‌های کاندید، ثابت باشد.Streeter, M. این حالت دقیقاً در عمل وجود ندارد، اما برهان "(تقریباً) هیچ ناهار مجانی" نشان می‌دهد که تقریباً وجود دارد. خلاصه بعضی مسائل محاسباتی با جستجو در راه حل‌های مناسب در یک فضا از پاسخ‌های کاندید حل می‌شوند. در مسائل متفاوت این الگوریتم نتایج متفاوتی خواهد داشت، اما روی تمام مسائل، غیرقابل تشخیص‌اند. از این نتیجه می گیریم که اگر یک الگوریتم روی یک سری از مسائل نتایج خوبی بدست آورد، باید به مسائل دیگر اهمیت کمتری بدهد. جستجو معمولاً با عنوان بهینه‌سازی شناخته می‌شود، پس می‌توان گفت که در بهینه سازی ناهار مجانی وجود ندارد. ایجل، توسینت، و انگلیش شرط عمومی را برقرار کردند که تحت آن هیچ ناهار مجانی نخواهد بود. دراست، جنسن، و وگنر برهانی را اثبات کردند که آن طور که خودشان می گفتند در عمل نشان می‌دهد که "تقریباً" هیچ ناهار مجانی نیست. برای اینکه بتوانیم بستر نظری مناسب تری فراهم کنیم، فردی را در نظر بگیرید که می‌خواهد یک مسئله را بهینه‌سازی کند. با در نظر داشتن این که چرا این مسئله به وجود آمده، آن فرد می‌تواند آز آن دانش پیش زمینه برای انتخاب الگوریتم مناسب برای حل مسئله استفاده کند. اگر آن فرد نداند که چطور از دانش پیش زمینه خود استفاده کند، یا اگر دانش پیش زمینه‌ای نداشته باشد، آنگاه با این مسئله مواجه می‌شود که آیا بعضی الگوریتم‌ها در دنیای واقعی بهتر از دیگر الگوریتم‌ها عمل می‌کنند یا نه. نویسندگان برهان "(تقریباً) هیچ ناهار مجانی نیست" پاسخ این مسئله را منفی می دانند، اما فکر می‌کنند امکان کاربردی کردن الگوریتم وجود دارد. هیچ ناهاری مجانی نیست(NFL) یک "مسئله"، یک تابع عینی است که پاسخ‌های کاندید را با مقادیر خوبی نسبت می‌دهد. | ## بخش 2: در جستجو و بهینه‌سازی از ناهار مجانی خبری نیست | یک الگوریتم جستجو یک تابع عینی را به عنوان ورودی می‌گیرد و پاسخ‌های کاندید را تک به تک ارزشیابی می‌کند. ولپرت و مک ردی تصریح می‌کنند که یک الگوریتم هیچ گاه یک پاسخ کاندید را دوباره ارزشیابی نمی‌کند، و هزینه اجرا الگوریتم روی خروجی‌ها محاسبه می‌شود. تحت این شرایط، وقتی یک الگوریتم جستجو روی تمام ورودی‌های ممکن اجرا می‌شود، هر پاسخ خروجی را دقیقاً یک بار تولید می‌کند. چون که هزینه اجرا روی خروجی‌ها محاسبه می‌شود، الگوریتم‌ها از این نظر که در چه بازه زمانی سطح خاصی از اجرا را بدست می‌آورند غیرقابل تشخیص‌اند. بعضی از ارزشیابی‌های هزینه اجرا نشان می‌دهد که الگوریتم‌های جستجو در بهینه سازی تابع عینی، خیلی خوب عمل می‌کنند. در واقع، به نظر می‌رسد که هیچ برنامه جالبی از الگوریتم‌های جستجو وجود ندارد که بهینه‌سازی نکند. یکی از روش‌های ارزشیابی اجرا به‌کارگیری کمترین شاخص از کمترین مقدار در رشته خروجی است. برای بعضی از الگوریتم ها، زمان لازم برای یافتن کمینه به تعداد ارزشیابی‌ها بستگی دارد. براهین اصلی هیچ ناهار مجانی نیست(NFL) فرض می‌کنند که تمام توابع عینی به‌طور مساوی احتمال ورودی گرفتن الگوریتم جستجو را دارند. بنابراین گفته می‌شود یک NFL وجود دارد اگر و فقط اگر به هم ریختن توابع عینی روی احتمال آن‌ها هیچ تأثیری نداشته باشد. اگر شرایط NFL دقیقاً برقرار باشد آنگاه تمام الگوریتم‌ها برای تمام توابع عینی تقریباً نتایج یکسانی خواهند داشت. باید توجه داشت که نقیض NFL نشان می‌دهد که تنها آن الگوریتم‌ها روی هم رفته با اندازه‌گیری هزینه اجرا با هم برابر نیستند. این یعنی اینکه یک الگوریتم با تعداد نسبتاً کمی از ارزشیابی ها، پاسخ‌های خوبی برای تقریباً تمام توابع عینی بدست می‌آورد. دلیلش این است که تقریباً تمام توابع عینی درجه بالایی از کلماگوراف از خود بروز می دهند. تمام سطوح خوبی‌ها به‌طور مساوی به تمام پاسخ‌های کاندید ارائه می‌شوند، و پاسخ‌های خوب در تمام فضای کاندیدها پراکنده می‌شوند. الگوریتم جستجو ندرتاً بیشتر از بخش کوچکی از کاندیدها را برای محل یابی یک پاسخ خیلی خوب ارزشیابی می‌کند. در عمل تمام توابع عینی و الگوریتم‌ها از چنان پیچیدگی کولماگورافی برخوردارند که هیچ گاه بر انگیخته نمی‌شوند . در توابع عینی نمونه یا الگوریتم، اطلاعات بیشتری از آنچه ست لوید تخمین زده بود که جهان قابلیت نگهداری آن را دارد وجود دارد. به‌طور مثال، اگر هر پاسخ کاندید به شکل رشته‌ای از 300 0 و 1 کد شود، و مقادیر ارزش خوبی 0 و 1 باشند، آنگاه اکثر توابع عینی پیچیدگی کولماگوراف با اندازه حداقل 2300 دارندLi, M., and Vitányi, P. در حالت عملی، الگوریتم‌هایی که آنقدر کوچک هستند که در نرم‌افزارها به کار آیند در مقابل آن‌هایی که بزرگترند، اجرای بهتری دارند. بیان ریاضی NFL مجموعه‌ای از تمام توابع عینی f:X→Y است، که فضایی محدود از پاسخ هاست و مجموعه جزئاً مرتب و متناهی. این شرط این امر را در نظر دارد که اگر و فقط اگر F و F o j به‌طور مشابه روی j برای تمام J‌ها توزیع شده باشند. | ## بخش 3: در جستجو و بهینه‌سازی از ناهار مجانی خبری نیست | به بیان دیگر، هیچ ناهار مجانی برای الگوریتم‌های جستجو نخواهد بود اگر و فقط اگر توزیع توابع عینی تحت جایگشت فضای پاسخ‌ها ثابت باشد. قسمت "فقط اگر" اولین بار توسط شوماخر در پایان‌نامه دکترایش با عنوان "جستجوی جعبه سیاه – چارچوب‌ها و روش‌ها" منتشر شد.(دانشگاه تنسی) براهین NFL اخیراً به شمارش‌های دلخواه X و Y عمومی‌سازی شده‌اند. براهین اصلی NFL ولپرت و مک‌ردی دو برهان اصلی NFL ارائه دادند، اولی مربوط به توابع هدفی است که هنگام اجرای رویه تغییر نمی‌کنند، و دومی مربوط به آنهایی است که تغییر می‌کنند. برهان 1: برای هر جفت الگوریتم a1 و a2 داریم: در واقع این تساوی می‌گوید اگر تمام توابع f دارای احتمال یکسان باشند، احتمال مشاهدهٔ رشته‌ای دلخواه از m مقدار در هنگام جستجو به الگوریتم جستجو بستگی ندارد. برهان 2 بیان دقیق‌تری از نتایج NFL را برای توابع عینی متغیر با زمان ارائه می‌کند. بررسی نتایج NFL یکی از تفاسیر قراردادی اما نه چندان دقیق از نتایج NFL این است که " یک استراتژی بهینه‌سازی همه کاره جهانی از لحاظ نظری غیرممکن است، و تنها راهی که یک الگوریتم در اجرای یک عمل می‌تواند از الگوریتم‌ها دیگر بهتر عمل کند این است که برای آن عمل خاص طراحی شده باشد"Ho, Y.C., Pepyne, D.L. یک الگوریتم ممکن است در حل یک مسئله از الگوریتم دیگر بهتر عمل کند اگر هیچ‌کدام برای حل آن مسئله خاص طراحی نشده باشند. ولپرت و مک ردی یک درجه اندازه‌گیری برای "تطابق" بین یک مسئله و الگوریتم بدست آورده‌اند. اینکه بگوییم یک الگوریتم با یک مسئله بهتر از دیگری تطابق دارد بدین معنا نیست که بگوییم که یک از آن‌ها برای حل مسئله طراحی شده‌است. برتری الگوریتمی که هیچ گاه کاندیدها رو دوباره ارزشیابی نمی‌کند به آن که این کار را می‌کند هیچ ربطی به اینکه یکی از آن‌ها برای حل آن مسئله طراجی شده باشند را ندارد. اگر یک تابع عینی تجزیه ناپذیر را به ما داده باشند، هیچ دلیلی ندارد که آن را بر الگوریتم دیگری ترجیح دهیم. در عمل، فقط توابع عینی تجزیه پذیر قابلیت ذخیره‌سازی در حافظه کامپیوترها را دارند، و چنین نیست که یک الگوریتم رو تمام توابع عینی تجزیه پذیر به خوبی عمل کند. عموماً به لحاظ هزینه اجرا بهتر است دانش پیش زمینه‌ای در رابطه با مسئله داشته باشیم. مواقع زیادی پیش می‌آید که یک شرکت ترجیح می‌دهد یک تابع را با یک برنامه کامپیوتری دستکاری نشده با سرعت کمی بهینه کند تا اینکه آن را به یک برنامه دستکاری شده توسط انسان و با سرعت بالا انجام دهد. هیچ کس تا به حال تعداد مسائل عملی که یک الگوریتم در آن سریعاً به جواب خوب می‌رسد را مشخص نکرده‌است. اجرا پیاده‌سازی یک الگوریتم در کامپیوتر در مقابل ارزش زمان انسان و سود یک جواب مناسب هزینه بسیار کمی دارد. اگر یک الگوریتم موفق به پیدا کردن راه حلی مناسب برای یک مسئله در زمانی مناسب باشد آنگاه با هزینه‌ای کم به سودی زیاد رسیده‌ایم، وگرنه چیزی از دست نداده ایم. ناهار مجانی هم تکاملی ولپرت و مک ردی اثبات کردند که در بهینه‌سازی هم تکاملی ها ناهار مجانی وجود دارد. تحلیل آن‌ها مسائل خود-بازی را پوشش می‌دهد که در آن مجموعه‌ای از بازیکنان با هم فعالیت می‌کنند تا یک قهرمان بدست آید، که بعداً یک یا چند رقیب را در بازی‌های بعد به کار می‌گیرد. این بدان معناست که، هدف این است که بازیکن خوبی بدست آوریم، اما بدون یک تابع عینی. ولپرت و مک ردی نشان دادند که بعضی از الگوریتم‌های هم تکاملی در انتخاب قهرمان نسبت به الگوریتم‌های دیگر بهتر عمل می‌کنند. تولید یک قهرمان از طریق خود-بازی یکی از مباحث مهم در محاسبات تکاملی و نظریه بازی هاست. | ## جمع‌بندی | نتایج روی هم تکاملی گونه‌های زیستی قابل اجرا نیست زیرا در این حالات قهرمانی وجود ندارد.