اُپتی‌کد، مرجع کدهای الگوریتم فرا ابتکاری مسائل ریاضی

بهینه‌سازی یعنی چه؟

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

دسته‌بندی‌های الگوریتم‌های بهینه‌سازی؟

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

1- روش‌های دقیق

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

برخی از الگوریتم‌های دقیق به‌کار رفته در مسائل بهینه‌سازی عبارتند از:

1.1- روش‌های تحلیلی (Analytical methods)

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

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

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

2.1- روش‌های عددی (Numerical methods)

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

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

روش گرادیان:

روش نیوتن-رافسون:

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

روش گرادیان نزولی

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

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

3.1- الگوریتم سیمپلکس (Simplex): این الگوریتم توسط دانتزیگ در سال 1947 توسعه یافت. روش سیمپلکس، مدل به فرم استاندارد یک مسئله خطی پیوسته را دریافت کرده و خروجی آن جواب بهینه مسئله است. علی‌رغم اینکه این روش پیچیدگی بدترین حالت نمایی را دارد، ولی بسیار روش کارآمدی برای دسته مسائل LP بشمار می‌رود.

نمونه جدول سیمپلکس

4.1- الگوریتم نقطه درونی (Interior Point): این روش توسط خاچیان در سال 1979 ارائه شد و بعدها توسط کارمارکار و سایر پژوهشگران بهبودهایی یافت. ویژگی مهم این الگوریتم، پیچیدگی بدترین حالت چندجمله‌ای آن است. هرچند که از نظر کارایی همسطح روش سیمپلکس است.

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

در کنار مسائل خطی پیوسته، با مسائل بهینه‌سازی گسسته (Discrete Optimization Problem) مواجه‌ایم که در این مسائل همه (IP) یا برخی (MIP) از متغیرهای تصمیم ماهیت عدد صحیح دارند. به مسئله‌ای که در آن همه متغیرها گسسته بوده و تعداد پاسخ‌ها محدود باشد، بطوریکه بتوانیم تمام پاسخ‌های موجه مسئله را بشماریم، مسئله بهینه‌سازی ترکیبی (Combinatorial Optimization Problem) گویند. اولین راهی که در حل این مسائل به ذهن می‌رسد، حل آزادسازی خطی مسئله با حذف محدودیت‌های عددصحیح مسئله توسط الگوریتم‌های خطی پیوسته است. هرچند پاسخ بدست آمده به احتمال بالایی مناسب مسئله اصلی نیست که در این صورت از تکنیک‌های گرد کردن پاسخ مسئله آزادسازی خطی (Rounding) یا جست‌وجوی محلی اطراف این پاسخ است. هرچند باید توجه شود لزوماً این تکنیک‌ها نیز تضمین کننده‌ی دست‌یابی به پاسخ بهینه عدد نیستند و می‌توان مثال‌هایی یافت که جواب بهینه مسئله اصلی با جواب بهینه مسئله آزادسازی فاصله زیادی دارند.

از روش‌ها و الگوریتم‌هایی که در حل مسائل گسسته استفاده می‌شوند می‌توان به موارد زیر اشاره کرد:

5.1- روش درخت جست‌وجو: در صورتی که فضای جست‌وجوی پاسخ‌های مسئله گسسته یا ترکیبی محدود و کوچک باشد، می‌توان با استفاده از ساختار درختی و در قالب رأس‌ها و یال‌های یک گراف مسئله را مدل کرده و با استفاده از یک سیاست جست‌وجوی کارآمد جواب مناسب را بیابیم.

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

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

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

فضای عدد صحیح

آشنایی با صفحات برش