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

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

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

محل لوگو

آمار بازدید

  • بازدید امروز : 52
  • بازدید دیروز : 14
  • بازدید کل : 15572

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


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

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

 

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

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

 


 

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- افزودن برش در هر تکرار الگوریتم سیمپلکس در حل مسئله آزادسازی خطی. جهت مطالعه و آشنایی بیشتر با روش صفحات برش، پیشنهاد می‌شود به گزارش زیر مراجعه کنید.

 

صفحات برش

فضای عدد صحیح

 

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

 

 


 

  انتشار : ۱۹ مرداد ۱۳۹۹               تعداد بازدید : 106

برچسب های مهم

دیدگاه های کاربران (0)

کتاب بانکداری داخلی 1(بهمند - بهمنی)

کتاب بانکداری داخلی 1(بهمند - بهمنی)

عنوان : کتاب بانکداری 1 (بهمند - بهمنی) حوزه کاربرد: حسابداری، بانکداری، اقتصاد تعداد صفحات: 194 صفحه کتاب بانکداری داخلی 1 (تجهیز منابع داخلی) نوشته آقایان (بهمند - بهمنی) به صورت PDF و در 194 صفحه خدمت دانشجویان و علاقه مندان عزیز تقدیم می گردد. فایل های ارائه شده برای این مجموعه با ...

محاسبه وزن الکترود نسبت به سایز و ضخامت لوله

محاسبه وزن الکترود نسبت به سایز و ضخامت لوله

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

آموزش دفتر فنی پایپینگ (Piping Technical Office)

آموزش دفتر فنی پایپینگ (Piping Technical Office)

به نام خدا با سلام این مجموعه آموزشی وظایف مهم دفتر فنی پایپینگ رو معرفی و شرح داده است و شامل بخشهای : مدارک اصلی پایپینگ ، ایزومتریک ، سرجوش گذاری نقشه ها تهیه WORK FRONT ، برنامه دو هفتگی ، کنترل متریال ، MIV ،MRC ،MRV ، تست پکیج ، لاین چک ، پانچ لیست ، تست ، فلاشینگ و ...

روش ساخت شابلون برنج تی پیس و وای پیس (Stencil t and y

روش ساخت شابلون برنج تی پیس و وای پیس (Stencil t and y

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

آموزش گام به گام کنترل پروژه پریماورا (PRIMAVERA) به

آموزش گام به گام کنترل پروژه پریماورا (PRIMAVERA) به

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

مجموعه طرح های معرق و مشبک

مجموعه طرح های معرق و مشبک

مجموعه طرح های زیبا و حرفه ای معرق کاری و مشبک کاری این مجموعه شامل: بسم الله شجره طرح های مینیاتوری تصاویر نوشتار و ....................... ...

پروژه درس کنترل کیفیت آماری ویژه دانشجویان

پروژه درس کنترل کیفیت آماری ویژه دانشجویان

هدف از کنترل کیفیت هدف اصلي يك سيستم كنترل فرآيند ، اتخاذ تصميمات مقرون به صرفه جهت انجام اقدامـات تاثير گذار بر فرآيند مي باشد . كنترل فرآيند نشان ميدهد كه كجاي فرآيند نيازمند انجام كنتـــــــرل هاي دقيق تـــــــر ميباشد و كجاهاي فرآيند انجام كنترل كمتر مجاز است. ( ...

متن کامل انگلیسی _ استاندارد بین المللی ایزو 31000 -

متن کامل انگلیسی _ استاندارد بین المللی ایزو 31000 -

متن کامل انگلیسی _ استاندارد بین المللی ایزو 31000 - مدیریت ریسک خطوط راهنمای مدیریت ریسک ISO 31000 : 2018 Risk Management Guidelines ...

آموزش OPERCOM و ICAPS

آموزش OPERCOM و ICAPS

به نام خدا این مجموعه کاملی از آشنایی مفصل با مفاهیم و مزایای استفاده از متد OPERCOM و آموزش و آشنایی با نرم افزار ICAPS و همچنین شامل بخشهای : هدف از اجرای روش OPERCOM – معرفی و شرح اصلی ترین دستورالعمل های -- OPERCOMمزایای استفاده از روش OPERCOM به کمک نرم افزار ICAPS – مزایای تقسیم بندی ...

دریافت فایل : آموزش OPERCOM و ICAPS
نرم افزار انبارداری بدون محدودیت استفاده و سورس

نرم افزار انبارداری بدون محدودیت استفاده و سورس

نرم افزار بسیار کاربردی انبارداری اکسس با پیغامها و امکانات فارسی: امکانات : امکان تعریف کاربران با سطح دسترسی محدود کاربران امکان تعریف کالاهای با رده مختلف امکان تعریف مشتریان امکان تعریف پرسنل امکان تعریف تامین کنندگان اسناد خرید یا رسید اسناد ...

کد الگوریتم‌های فرا ابتکاری مسائل مشهور ریاضی را از ما بخواهید.

فید خبر خوان    نقشه سایت    تماس با ما