در داخل رده NP، مسائلی از رده NP-complete وجود دارد. یک مسئله تصمیم که عضوی از NP است زمانی NP-complete محسوب می­گردد که تمامی مسائل دیگر رده NP، در زمان چند­جمله­ای قابل کاهش به آن مسئله باشد.

مسائل NP-hard، مسائل بهینه­ سازی می‌باشند که مسائل تصمیم مرتبط با آن ها از نوع NP-hard می‌باشند و الگوریتم مؤثر اثبات شده­ای برای حل آن ها وجود ندارد. زمان حل بهینه آن ها، در رده زمان نمایی ‌می‌باشد که متاهیورستیک­ها گزینه مناسب و با اهمیتی برای حل این دسته از مسائل می­باشند. در زیر دسته­ای از مسائل NP-hard آورده شده است:

    • مسائل زمان­بندی و تعیین توالی مانند زمان­بندی جریان کارگاهی، زمان­بندی تولید کارگاهی و مسائل زمان­بندی کارگاهی باز.

    • مسائل تخصیص و جانمایی از قبیل مسئله تخصیص درجه دو[۹]، مسئله تخصیص تعمیم­یافته[۱۰]، جانمایی تسهیلات، مسئله P-median.

    • مسائل گروه­بندی مانند خوشه ­بندی داده ­ها، افراز گراف و رنگ­آمیزی گراف.

    • مسائل مسیر­یابی و پوشش­دهی از قبیل مسئله مسیر­یابی وسایل حمل­و­نقل[۱۱]، مسائل پوشش­دهی مجموعه[۱۲] و مسائل تور پوشاننده.

  • مسائل برش، بسته­بندی، کوله­پشتی و غیره (فتاحی، ۱۳۹۰).

۲-۲-۳- روش­های بهینه­ سازی

دو دسته کلی از روش­های حل مسائل بهینه­ سازی شامل روش­های دقیق[۱۳] و روش­های تقریبی[۱۴] وجود دارد. روش­های دقیق راه حل­های بهینه را به دست آورده و شرایط بهینگی را تضمین می­نمایند. روش­های تقریبی (هیوریستیکی)، راه ­حل­های با کیفیت بالا در زمان معقولی، تولید می­نمایند، اما تضمینی برای یافتن راه حل بهینه مطلق ندارند.

۲-۲-۳-۱- روش­های دقیق

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

روش­هایی که در این قالب دسته بندی می شود به شرح زیرند:

    • برنامه­ ریزی خطی عدد صحیح

  • روش تولید (ایجاد) ستون

در این روش همه مسیرهای ممکن به عنوان جواب­های اولیه تولید می­شوند و سپس به کمک یکی از روش­های بهبود مسیرهای پرهزینه حذف و مسیرهای کم­هزینه باقی می­مانند.

  • برنامه­ ریزی پویا (دینامیک)

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

  • روش انشعاب و تحدید

ابتدا مسئله در حالت پیوسته حل می­ شود و در صورتی­که جواب شرط صحیح بودن را برآورده نکند، شروط یا محدودیت­هایی که تأمین­کننده صحیح شدن متغیرها می­ شود به مسئله اضافه می­ شود.

این الگوریتم اولین بار در سال ۱۹۸۱ توسط لاپورته و نوبرت با یک انبار و تعداد ثابت وسایل نقلیه به کار گرفته شد (کارگری، ۱۳۹۰).

  • الگوریتم شاخه و برش

در این روش ایده کلی ‌به این صورت است که ابتدا باید مسئله برنامه­ ریزی خطی آزاد شده و سپس مسئله برنامه­ ریزی عدد صحیح را حل کرد (طه،۱۳۸۸).

  • مدل­های آزادسازی ضرایب لاگرانژ

برای حل مشکل برنامه­ ریزی با اعداد صحیح از یک سری محدودیت­های جانبی برای ساده­سازی استفاده می­ شود. که با نوشتن مزدوج این محدودیت­ها یک مسئله لاگرانژ که حل ساده­تری دارد به دست می ­آید.

۲-۲-۳-۲- روش­های تقریبی

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

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

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

برخی از این روش­ها به شرح زیر است:

  • الگوریتم ژنتیک[۱۵]

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

  • روش تبرید شبیه­سازی­شده[۱۶]

این الگوریتم، روشی تصادفی است که با جستجوی محلی، فضای حل را به صورت تصادفی و مؤثر جستجو می­ کند. این الگوریتم تلاش می­ کند در صورتی که حل در تکرارها به جواب بهتری دست نیابد، با پذیرش جواب­های بدتر که با احتمالی کاهشی همراه است از افتادن در دام بهینه محلی خودداری کند.

  • روش جستجوی ممنوعه[۱۷]

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

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...