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

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

شرح گرافیکی نتایج براهین NFL برای الگوریتم‌های هیوریستیک: تمام هیوریستیک‌ها میانگین هزینه اجرای یکسانی دارند. یک هیوریستیک ممکن است از یک هیوریستیک دیگر در حل مسئله یا دامنه‌ای از مسائل بهتر عمل کند، اما در دامنه دیگری از مسائل بدتر باشد. علاوه بر این، هر چقدر در دامنه خودش بهتر باشد در باقی دامنه‌ها بدتر خواهد بود.

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

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

خلاصه

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

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

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

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

یک "مسئله"، یک تابع عینی است که پاسخ‌های کاندید را با مقادیر خوبی نسبت می‌دهد. یک الگوریتم جستجو یک تابع عینی را به عنوان ورودی می‌گیرد و پاسخ‌های کاندید را تک به تک ارزشیابی می‌کند. خروجی الگوریتم رشته مقادیر خوبی مشاهده شده‌است.

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

بعضی از ارزشیابی‌های هزینه اجرا نشان می‌دهد که الگوریتم‌های جستجو در بهینه سازی تابع عینی، خیلی خوب عمل می‌کنند. در واقع، به نظر می‌رسد که هیچ برنامه جالبی از الگوریتم‌های جستجو وجود ندارد که بهینه‌سازی نکند. یکی از روش‌های ارزشیابی اجرا به‌کارگیری کمترین شاخص از کمترین مقدار در رشته خروجی است. این تعداد ارزشیابی‌های لازم برای کمینه کردن تابع عینی است. برای بعضی از الگوریتم ها، زمان لازم برای یافتن کمینه به تعداد ارزشیابی‌ها بستگی دارد.

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

تفسیر واضح نقیض NFL قاعدتاً "ناهار مجانی وجود دارد" است. اما این گمراه‌کننده است. NFL یک درجه است نه یک گزاره صفر و یک منطقی. اگر شرایط NFL دقیقاً برقرار باشد آنگاه تمام الگوریتم‌ها برای تمام توابع عینی تقریباً نتایج یکسانی خواهند داشت. باید توجه داشت که نقیض NFL نشان می‌دهد که تنها آن الگوریتم‌ها روی هم رفته با اندازه‌گیری هزینه اجرا با هم برابر نیستند. برای اندازه‌گیری سود اجرا، الگوریتم‌ها ممکن است کاملاً یا تقریباً برابر بمانند.

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

در عمل تمام توابع عینی و الگوریتم‌ها از چنان پیچیدگی کولماگورافی برخوردارند که هیچ گاه بر انگیخته نمی‌شوند . در توابع عینی نمونه یا الگوریتم، اطلاعات بیشتری از آنچه ست لوید تخمین زده بود که جهان قابلیت نگهداری آن را دارد وجود دارد. به‌طور مثال، اگر هر پاسخ کاندید به شکل رشته‌ای از 300 0 و 1 کد شود، و مقادیر ارزش خوبی 0 و 1 باشند، آنگاه اکثر توابع عینی پیچیدگی کولماگوراف با اندازه حداقل 2 دارند، و این بزرگتر از مرز 2 لوید است. نتیجه می گیریم تمام برهان "هیچ ناهار مجانی" در دنیای فیزیکی صدق نمی‌کند. در حالت عملی، الگوریتم‌هایی که آنقدر کوچک هستند که در نرم‌افزارها به کار آیند در مقابل آن‌هایی که بزرگترند، اجرای بهتری دارند.

بیان ریاضی NFL

$Y^{X}$

مجموعه‌ای از تمام توابع عینی f:X→Y است، که

X

فضایی محدود از پاسخ هاست و

Y

مجموعه جزئاً مرتب و متناهی. مجموعه تمام جایگشت‌های

X

از

J

است. یک متغیر تصادفی مانند F روی

Y^{X}

توزیع شده‌است. برای تمام jهای در J، هر F o j متغیری تصادفی است که روی

Y^{X}

توزیع شده‌است، با احتمال P(F o j = f) = P(F = f o j برای تمام f در

Y^{X}

.

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

براهین اصلی NFL

ولپرت و مک‌ردی دو برهان اصلی NFL ارائه دادند، اولی مربوط به توابع هدفی است که هنگام اجرای رویه تغییر نمی‌کنند، و دومی مربوط به آنهایی است که تغییر می‌کنند.

برهان 1: برای هر جفت الگوریتم a₁ و a₂ داریم:

\sum _{f}P(h_{m}^{y}|f,m,a_{1})=\sum _{f}P(h_{m}^{y}|f,m,a_{2}).

در واقع این تساوی می‌گوید اگر تمام توابع f دارای احتمال یکسان باشند، احتمال مشاهدهٔ رشته‌ای دلخواه از m مقدار در هنگام جستجو به الگوریتم جستجو بستگی ندارد. برهان 2 بیان دقیق‌تری از نتایج NFL را برای توابع عینی متغیر با زمان ارائه می‌کند.

بررسی نتایج NFL

یکی از تفاسیر قراردادی اما نه چندان دقیق از نتایج NFL این است که " یک استراتژی بهینه‌سازی همه کاره جهانی از لحاظ نظری غیرممکن است، و تنها راهی که یک الگوریتم در اجرای یک عمل می‌تواند از الگوریتم‌ها دیگر بهتر عمل کند این است که برای آن عمل خاص طراحی شده باشد"

یک استراتژی بهینه‌سازی تقریباً همه کاره جهانی به لحاظ نظری وجود دارد. هر الگوریتم جستجو رو تمام توابع عینی تقریباً خوب عمل می‌کند.

یک الگوریتم ممکن است در حل یک مسئله از الگوریتم دیگر بهتر عمل کند اگر هیچ‌کدام برای حل آن مسئله خاص طراحی نشده باشند. ممکن است هر دو از بدترین الگوریتم‌ها برای حل آن مسئله باشند. ولپرت و مک ردی یک درجه اندازه‌گیری برای "تطابق" بین یک مسئله و الگوریتم بدست آورده‌اند. اینکه بگوییم یک الگوریتم با یک مسئله بهتر از دیگری تطابق دارد بدین معنا نیست که بگوییم که یک از آن‌ها برای حل مسئله طراحی شده‌است.

در عمل، بعضی الگوریتم ها، پاسخ‌های کاندید را دوباره ارزشیابی می‌کنند. برتری الگوریتمی که هیچ گاه کاندیدها رو دوباره ارزشیابی نمی‌کند به آن که این کار را می‌کند هیچ ربطی به اینکه یکی از آن‌ها برای حل آن مسئله طراجی شده باشند را ندارد.

تقریباً برای تمام توابع عینی، طراحی مخصوص تقریباً تصادفی است. اگر یک تابع عینی تجزیه ناپذیر را به ما داده باشند، هیچ دلیلی ندارد که آن را بر الگوریتم دیگری ترجیح دهیم. اگر الگوریتم انتخاب شده بهتر از بقیه عمل کند، نتیجه یک روی داد شانسی است.

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

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

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

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

منابع

↑ Wolpert, D.H., Macready, W.G. (1995), No Free Lunch Theorems for Search, Technical Report SFI-TR-95-02-010 (Santa Fe Institute).
↑ Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization," IEEE Transactions on Evolutionary Computation 1, 67. http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf
↑ Wolpert, David (1996), "“The Lack of A Priori Distinctions between Learning Algorithms," Neural Computation, pp. 1341-1390.
↑ Schaffer, Cullen (1994), "A conservation law for generalization performance," International Conference on Machine Learning, H. Willian and W. Cohen, Editors. San Francisco: Morgan Kaufmann, pp.295-265.
↑ Streeter, M. (2003) "Two Broad Classes of Functions for Which a No Free Lunch Result Does Not Hold," Genetic and Evolutionary Computation—GECCO 2003, pp. 1418–1430.
↑ Igel, C., and Toussaint, M. (2004) "A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions," Journal of Mathematical Modelling and Algorithms 3, pp. 313–322.
↑ English, T. (2004) No More Lunch: Analysis of Sequential Search, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 227-234. http://BoundedTheoretics.com/CEC04.pdf بایگانی‌شده در ۱ مه ۲۰۱۵ توسط Wayback Machine
↑ S. Droste, T. Jansen, and I. Wegener. 2002. "Optimization with randomized search heuristics: the (A)NFL theorem, realistic scenarios, and difficult functions," Theoretical Computer Science, vol. 287, no. 1, pp. 131-144.
↑ Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches," IEEE Transactions on Evolutionary Computation, 9(6): 721-735
↑ A search algorithm also outputs the sequence of candidate solutions evaluated, but that output is unused in this article.
↑ English, T. M. 2000. "Optimization Is Easy and Learning Is Hard in the Typical Function," Proceedings of the 2000 Congress on Evolutionary Computation: CEC00, pp. 924-931. http://www.BoundedTheoretics.com/cec2000.pdf بایگانی‌شده در ۲۳ ژانویه ۲۰۱۷ توسط Wayback Machine
↑ Li, M., and Vitányi, P. (1997) An Introduction to Kolmogorov Complexity and Its Applications (2nd ed.), New York: Springer.
↑ Ho, Y.C., Pepyne, D.L. (2002), "Simple Explanation of the No-Free-Lunch Theorem and Its Implications," Journal of Optimization Theory and Applications 115, 549.

جستارهای وابسته

علوم اطلاعات تکاملی
بایاس استنتاجی
تیغ اوکام
سادگی
برهان جوجه اردک زشت

پیوند به بیرون

[WM95-1] Wolpert, D.H., Macready, W.G. (1995), No Free Lunch Theorems for Search, Technical Report SFI-TR-95-02-010 (Santa Fe Institute).

[WM97-2] Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization," IEEE Transactions on Evolutionary Computation 1, 67. http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf

[Wolpert96-3] Wolpert, David (1996), "“The Lack of A Priori Distinctions between Learning Algorithms," Neural Computation, pp. 1341-1390.

[Schaffer94-4] Schaffer, Cullen (1994), "A conservation law for generalization performance," International Conference on Machine Learning, H. Willian and W. Cohen, Editors. San Francisco: Morgan Kaufmann, pp.295-265.

[Streeter-5] Streeter, M. (2003) "Two Broad Classes of Functions for Which a No Free Lunch Result Does Not Hold," Genetic and Evolutionary Computation—GECCO 2003, pp. 1418–1430.

[Igel-6] Igel, C., and Toussaint, M. (2004) "A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions," Journal of Mathematical Modelling and Algorithms 3, pp. 313–322.

[English2004-7] English, T. (2004) No More Lunch: Analysis of Sequential Search, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 227-234. http://BoundedTheoretics.com/CEC04.pdf بایگانی‌شده در ۱ مه ۲۰۱۵ توسط Wayback Machine

[ANFL-8] S. Droste, T. Jansen, and I. Wegener. 2002. "Optimization with randomized search heuristics: the (A)NFL theorem, realistic scenarios, and difficult functions," Theoretical Computer Science, vol. 287, no. 1, pp. 131-144.

[WM-coev-9] Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches," IEEE Transactions on Evolutionary Computation, 9(6): 721-735

[10] A search algorithm also outputs the sequence of candidate solutions evaluated, but that output is unused in this article.

[English2000-11] English, T. M. 2000. "Optimization Is Easy and Learning Is Hard in the Typical Function," Proceedings of the 2000 Congress on Evolutionary Computation: CEC00, pp. 924-931. http://www.BoundedTheoretics.com/cec2000.pdf بایگانی‌شده در ۲۳ ژانویه ۲۰۱۷ توسط Wayback Machine

[LV-12] Li, M., and Vitányi, P. (1997) An Introduction to Kolmogorov Complexity and Its Applications (2nd ed.), New York: Springer.

[13] Ho, Y.C., Pepyne, D.L. (2002), "Simple Explanation of the No-Free-Lunch Theorem and Its Implications," Journal of Optimization Theory and Applications 115, 549.