بهینه سازی به پیدا کردن مجموعه از ورودی ها برای یک تابع هدف گفته می شود که استفاده از آنها منجر به بیشینه یا کمینه شدن مقدار خروجی تابع هدف می شوند (ورودی ها می توانند پارامترها و وزن های دخیل و غیره باشند).

بسیار متداول است که در مسائل، بهینه سازی را در قالب دو عنوان محلی یا Local و سراسری یا Global  توصیف کنند. به طریق مشابه، متداول است که در تحقیقات و الگوریتم های جستجویی که برای یافتن جواب بهینه ایجاد شده اند، دو شیوه متفاوت Local و Global مطرح باشد.

در این آموزش شما تفاوت های عملکردی دو شیوه بهینه سازی Local و Global را در می یابید.

پس از مطالعه کامل این مطلب، انتظار می رود شما اینها را یاد گرفته باشید:

1. بهینه سازی محلی شامل پیدا کردن جواب بهینه برای یک ناحیه خاص از جستجو است. همچنین جواب بهینه محلی می تواند همان جواب بهینه Global مسئله باشد اگر در فضای آن مسئله نقطه بهینه محلی وجود نداشته باشد.
2. بهینه سازی Global پیدا کردن بهینه ترین حالت مجموعه ورودی هاست (در مسائلی که نقاط بهینه متعدد محلی داریم).
3.  چطور و چه زمانی از الگوریتم های بهینه سازی Local یا Global استفاده کنیم و چطور هر دو را همزمان استفاده کنیم.

بیایید شروع کنیم!

مرور موضوعات

این مطلب آموزشی در سه بخش تقسیم شده است. آن سه بخش اینها هستند:

1. بهینه سازی محلی یا Local Optimization
2. بهینه سازی سراسری یا Global Optimization
3. بهینه سازی Local در مقابل Global

بهینه سازی محلی یا Local Optimization

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

… در بهینه سازی محلی ما به دنبال نقطه ای هستیم که در واقع فقط به صورت محلی بهینه است، یعنی تابع هدف را فقط نسبت به نقاط نزدیک به خود کمینه یا بیشینه می کند…

— Page 9, Convex Optimization, 2004.

نوع تعریف یک تابع هدف، می تواند در فضای مسئله تعداد زیادی نقطه بهینه محلی داشته باشد؛ و حتی ممکن است تنها یک نقطه محلی بهینه در کل فضای مسئله ایجاد کند که در آن صورت همان نقطه بهینه عمومی یا Global است.

• تعریف بهینه سازی محلی یا Local Optimization : این نوع بهینه سازی تلاش می کند تا با شروع جستجو از نقطه ای، اولین نقطه بهینه ای را مکان یابی کند که تابع هدف را بیشینه یا کمینه می کند.

بنابراین، عنوان Local optimization یا local search در واقع به جستجو برای یافتن نقطه بهینه محلی اشاره می کند.

یک الگوریتم بهینه سازی یا جستجوی محلی، الگوریتمی است که یه ناحیه جستجوی را می پیماید تا به بهینه محلی تابع هدف نزدیک شود (یا دقیقاً آن را پیدا کند).

… روش های بهینه سازی محلی به صورت گسترده ای در کاربردهایی استفاده می شوند که در آنها پیدا کردن یک نقطه بهینه با ارزش است هر چند که آن نقطه بهترین نقطه در فضای مسئله نباشد.

— Page 9, Convex Optimization, 2004.

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

الگوریتم های جستجوی محلی هم می توانند نقطه بهینه سراسری را پیدا کنند، اگر :

• نقطه بهینه محلی یکتا باشد و همان نقطه بهینه سراسری باشد. و یا
• مسیر یا ناحیه جستجو شده شامل نقطه بهینه سراسری باشد و الگوریتم در همان نقطه توقف کند.

این دو حالت، حالت های ایده آل و بهینه در استفاده از بهینه سازی محلی هستند.

ممکن است بحث هایی روی این باشد که چه چیزی یک الگوریتم بهینه سازی محلی را شکل می دهد؛ با این حال، با تعاریفی که ما ارائه کردیم، سه نمونه از الگوریتم های جستجوی محلی اینها هستند:

• Nelder-Mead Algorithm
• BFGS Algorithm
• Hill-Climbing Algorithm

حالا که با تعریف و مفهوم بهینه سازی محلی آشنا شدیم، بیایید نگاهی به بهینه سازی سراسری بیاندازیم.

بهینه سازی سراسری یا Global Optimization

یک بهینه ترین نقطه سراسری، نقطه ای است که در آن مقدار تابع هدف برای تمام فضای ورودی مسئله بهترین می شود (بیشتری یا کمترین).

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

— Page 37, Computational Intelligence: An Introduction, 2007.

یک تابع هدف در فضای ورودی های یک مسئله می تواند یکی یا بیشتر نقطه بهینه سراسری ایجاد کند. اگر نقاط بهینه سراسری در مسئله بیشتر از یکی باشد، آنگاه با یک مسئله multimodal optimization روبرو هستیم که هر نقطه optimum با ورودی های متفاوت به دست می آید اما ارزیابی و مقدار یکسانی را در تابع هدف ایجاد می کند.

تعریف بهینه سازی سراسری یا Global Optimization : این بهینه سازی، بهترین نقطه ای را پیدا می کند که در آن تابع هدف بهترین ارزیابی را داشته باشد (بیشترین یا کمترین باشد).

یک تابع هدف همیشه یک نقطه بهینه سراسری دارد (در غیر این صورت ما اصلاً علاقه مند به بهینه مقدار آن نخواهیم بود)، همچنین همانطور که قبل تر گفتیم، می تواند نقاط بهینه محلی هم داشته باشد که در آنها مقدار تابع هدف به خوبی مقدار در بهینه سراسری نیست.

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

Global optimization یا جستجوی سراسری هر دو به جستجو در فضای مسئله می پردازد تا نقطه بهینه سراسری را پیدا کند. الگوریتم جستجوی سراسری تمام یا بخش بسیار بزرگی از فضای ورودی های مسئله به تابع هدف را جستجو می کند تا بهترین نقطه را پیدا کند (به آن نزدیک شود یا دقیقاً خود آن را پیدا کند).

بهینه سازی سراسری برای مسائلی استفاده می شود که تعداد کمی متغیر دارند و طول زمان پردازش برای آنها محدود و بحرانی نیست، و همچنین پیدا کردن بهترین حالت مسئله ارزش و اهمیت بسیار بالایی دارد.

— Page 9, Convex Optimization, 2004.

الگوریتم های جستجوی سراسری ممکن است که یک راه حل یا جمعیتی از راه حل را استفاده کنند؛ اما در هر صورت به دنبال تغییر و بهبود مداوم راه حل (های) کاندید هستند و به طور مداوم نمونه جدید یا نسل و جمعیت جدیدی را شکل می دهند و به عنوان کاندید بعدی برای ادامه جستجو استفاده می کنند.

طبق تعریف هایی که ما بیان کردیم، می توان سه نمونه زیر را از دسته الگوریتم های بهینه سازی و جستجوی سراسری نام برد:

• Genetic Algorithm
• Simulated Annealing
• Particle Swarm Optimization

حالا بیایید این دو نوع بهینه سازی را در مقابل همدیگر قرار دهیم و مقایسه کنیم.

بهینه سازی Local در مقابل Global

الگوریتم های جستجوی محلی سراسری مسائل مختلفی را حل می کنند.

یک الگوریتم بهینه سازی محلی زمانی می تواند استفاده شود که شما می‌دانید که ناحیه  یا راه رسیدن به نقطه بهینه سراسری را می شناسید یا اینکه  تابع هدف شما ما تنها یک نقطه بهینه دارد.

 یک الگوریتم بین سازی سراسری هم زمانی می تواند استفاده شود که شما دانش بسیار محدودی درباره ساختار فضایی که تابع هدف روی ورودی ایجاد می کند دارید (مجبورید همه آن را جستجو کنید) و یا اینکه می دانید فضای آن تابع شامل نقاط بهینه محلی هم میشود (بیم گیر افتادن در یک نقطه بهینه محلی وجود دارد).

بهینه سازی محلی را زمانی استفاده کنید که می دانید ممکن است الگوریتم جستجو در یک نقطه بهینه محلی گیر کند و دیگر نقطه بهینه سراسری مسئله را پیدا نکند.

— Page 37, Computational Intelligence: An Introduction, 2007.

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

• جستجوی محلی: زمانی که شما در ناحیه ای هستید که نقطه بهینه سراسری در آن قرار دارد یا تنها یک نقطه بهینه وجود دارد.
• جستجوی سراسری: زمانی که شما می دانید در فضای ایجاد شده نقطه یا نقاط بهینه دیگری غیر از نقطه بهینه سراسری وجود دارند که به اندازه نقطه بهینه سراسری خوب نیستند (بهینه محلی).

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

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

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

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

بهینه سازی محلی یک مسئله ساده تر نسبت به بهینه سازی سراسری است. به همین جهت اکثریت تحقیقات در بهینه سازی های ریاضیاتی، روی بهینه سازی محلی متمرکز شده است.

کسر بزرگی از تحقیقات در موضوع برنامه ریزی عمومی غیر خطی، روی روشهای بهینه سازی محلی متمرکز شده است که باعث شده این نوع برنامه‌ریزی به خوبی توسعه یابد.

— Page 9, Convex Optimization, 2004.

الگوریتم های جستجوی سراسری در مسیریابی خود در جستجوی فضا مسئله بسیار فراگیر عمل می کنند.

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

— Page 162, Algorithms for Optimization, 2019.

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

تکنیک های بهینه سازی محلی و سراسری می‌توانند با هم ترکیب شوند تا الگوریتم های هیبرید آموزش یادگیری ماشین را تشکیل دهند.

— Page 37, Computational Intelligence: An Introduction, 2007.

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

مطالعه بیشتر

کتاب ها

• Convex Optimization, 2004.
• Computational Intelligence: An Introduction, 2007.
• Algorithms for Optimization, 2019.

مقالات

• Local search (optimization), Wikipedia.
• Global optimization, Wikipedia.

خلاصه

در این مطلب آموزشی شما تفاوت های کاربردی بین بهینه سازی محلی و سراسری را دریافتید.

 به طور مشخص شما یاد گرفتید که:

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

منبع

این مطلب ترجمه و تلخیصی از مطلب زیر است:

Local Optimization Versus Global Optimization

نوشته بهینه سازی Local در مقابل Global اولین بار در اوپن مایند. پدیدار شد.