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

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

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

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

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

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

1. الگوریتم‌های Bracketing

الگوریتم‌های بهینه سازی Bracketing برای مشکلات بهینه سازی با یک متغیر ورودی در نظر گرفته شده است که در آن optima در محدوده خاصی وجود دارد.

الگوریتم‌های Bracketing  می‌توانند به طور موثر در محدوده شناخته شده حرکت کرده و بهترین‌ها را تعیین کنند، اگرچه آن‌ها فرض می‌کنند که تنها یک Optima  وجود دارد. اگر الگوریتم‌های bracketing در دسترس نباشند، می‌توانند بدون اطلاعات مشتق نیز استفاده شوند.

نمونه‌هایی از الگوریتم‌های bracketing عبارتند از:

• جستجوی فیبوناچی
•  جستجوی بخش طلایی
•  روش تقسیم بندی

2. الگوریتم‌های نزول محلی

الگوریتم‌های بهینه سازی نزول محلی برای حل مشکلات بهینه سازی با بیش از یک متغیر ورودی در نظر گرفته شده است. شاید متداول ترین مثال الگوریتم نزول محلی ، الگوریتم جستجوی خط باشد. تغییرات زیادی در جستجوی خط وجود دارد به عنوان مثال الگوریتم Brent Dekker، اما این روش به طور کلی شامل انتخاب جهت حرکت در فضای جستجو و سپس انجام جستجوی نوع bracketing  در جهت انتخاب شده است.

این روند تا زمانی که پیشرفت‌های بیشتری انجام نشود، تکرار می‌شود. محدودیت این است که بهینه سازی هر حرکت جهت‌دار در فضای جستجو از نظر محاسباتی می‌تواند بسیار گران باشد.

3. الگوریتم‌های مرتبه اول

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

اندازه گام یک فوق پارامتر است که میزان حرکت در فضای جستجو را کنترل می‌کند و بر خلاف "الگوریتم‌های نزول محلی" که یک جستجوی کامل را برای هر حرکت جهت دار انجام می‌دهند است.

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

• نزول گرادیان
• تکانه
•  آداگراد
• RMSProp 
•  آدم

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

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

•  نزول گرادیان تصادفی
•  نزول دسته‌ای گرادیان
•  نزول گرادیان مینی بچ

4. الگوریتم‌های مرتبه دوم

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

•  روش نیوتن
•  روش ثانویه

روش‌های مرتبه دوم برای توابع هدف چند متغیره، روش‌های شبه نیوتنی نامیده می‌شوند. روش‌های شبه نیوتن زیادی وجود دارد که معمولاً برای توسعه دهندگان الگوریتم نامگذاری شده است.

5. الگوریتم‌های مستقیم

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

• جستجوی مختصات چرخه ای
•  روش پاول
•  روش هوک جیوز
•  Nelder-Mead Simplex Search 

6. الگوریتم‌های تصادفی

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

•  پخت شبیه سازی شده
•  استراتژی تکامل
• روش آنتروپی متقابل

7. الگوریتم‌های جمعیت

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

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

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

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

نتایج مقایسه نشان می‌دهد که بهینه سازی پی در پی روشی است که بهترین تعادل بین دقت و تعداد ارزیابی عملکردها را دارد. این امر با بهینه سازی مسئله مهندسی تأیید می‌شود. این مقایسه همچنین نشان می‌دهد که روش جدید بهتر از روش قدیمی است.