الگوریتم شبیه سازی تبرید و جستجوی ممنوعه

پاورپوینت به کارگیری الگوریتم شبیه سازی تبرید (SA) و جستجوی ممنوعه (TS) برای حل مسائل چیدمان تسهیلات. چيدمان تسهيلات مساله‌‌‌‌‌‌‌‌‌‌‌‌‌‌اي است که به نحوه قرارگیری دپارتمان‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌ها در منطقه کاري مي‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌پردازد.

انواع مسائل چیدمان

• تخصیص کوآدراتیک
• برنامه‌‌‌‌‌‌‌‌‌ریزی عدد صحیح خطی
• برنامه‌ریزی عدد صحیح مختلط
• نظریه گراف

مراحل الگوریتم شبیه سازی تبرید (SA) استاندارد

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

• ورود اطلاعات مساله و تنظیم پارامترهای الگوریتم
• تشکیل یک جواب در همسایگی جواب فعلی (بررسی 3 حالت ممکن)
• ارزیابی جواب همسایگی
• به روز رسانی پارامترهای الگوریتم و مساله
• بهترین جواب را حفظ کنیم و حرکت به گام اول

الگوریتم جستجوی ممنوعه

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

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

مراحل الگوریتم جستجوی ممنوعه

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

استراتژی های پیشرفته جستجوی ممنوعه

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