منظور از بهینه محلی (Local Optimum) و بهینه سراسری (Global Optimum) چیست؟

مدرس: مسعود کاویانی

MasoudKaviani.ir

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

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

برای روشن‌تر شدنِ موضوع شکل زیر را نگاه کنید:

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

همان‌طور که در مثالِ بالا دیدید، در الگوریتمِ اینستاگرام امتیازهایی وجود دارند که برای پیدا کردنِ آن‌ها، بایستی تمامیِ اشخاص را جستجو کنیم ولی ما وقت نداریم. زیرا تعداد اشخاص بسیار زیاد است. یک راه ساده این است که یک شخص را به صورت تصادفی انتخاب کنیم و به صورتِ محلی به دنبالِ بیشترین امتیاز در حول و حوشِ آن باشیم. با این کار می‌توانیم به یک امتیاز معقول دست پیدا کنیم. البته این یک مثال خیلی ساده است. فرض کنید چندبار این کار را تکرا کنیم. یعنی به صورتِ تصادفی یک نقطه در فضا را انتخاب کنیم و بعد به دنبال بیشترین امتیازِ محلی در نزدیکی آن منطقه بگردیم. در اصطلاح به گشتن در تمامیِ نقاط Exploration (جستجو) و به صعود به سمت قله در یک منطقه Exploitation (بهره برداری) می‌گویند. به صورت خلاصه، یک الگوریتمِ خوب، نیاز دارد که ترکیبی از Exploration و Exploitation را داشته باشد تا با توجه به تابعِ برازش (Fitness Function) بتواند یک حالتِ بهینه را پیدا کند.