یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
استراتژی‌های پیشرفته‌ جستجوی ممنوعه

ساختار کلی جستجوی ممنوعه، اغلب جوابگوی مسایل بزرگ نیست. بنابراین به منظور افزایش قدرت الگوریتم، از استراتژی‌های زیر که معروف به استراتژی‌های پیشرفته جستجوی ممنوعه هستند استفاده می‌شود [Gend03]:

  • استراتژی لیست کاندید (Candidate List Strategy): در یک TSعادی، برای حرکت از یک جواب فعلی به یک جواب همسایه، باید مقدار تابع هدف برای هر عنصر از همسایه‌ها ارزیابی شود. این کار می‌تواند از لحاظ محاسباتی بسیار هزینه­بر باشد. روشی دیگر، این است که به جای ان که تمامی همسایه‌ها بررسی شود، تنها یک زیرمجموعه‌ تصادفی از همسایه­ها در نظر گرفته شود که در نتیجه، هزینه‌ محاسباتی به طور قابل ملاحظه‌ای کاهش می‌یابد. انتخاب زیرمجموعه‌ای از جواب­های همسایه به صورت تصادفی، می‌تواند به عنوان یک مکانیزم ضد چرخه عمل کند؛ این کار اجازه می‌دهد که از لیست ممنوعه کوچکتری نسبت به کل همسایگی، استفاده شود. البته باید در نظر داشت که این کار یک عیب مهم دارد و ان احتمال از دست دادن جواب­های خوب است، بنابراین احتمال‌هایی را نیز می‌توان به کار برد تا معیارهای ممنوعه فعال شود.
  • استراتژی تقویت (Intensification Strategy): استراتژی تقویت به معنای یافتن حرکت‌های خوب و افزایش انجام ان حرکت‌ها در الگوریتم است. تقویت، در بسیاری از پیاده‌سازی‌های TSاستفاده می‌شود، اما همیشه ضروری نیست، زیرا حالت‌های بسیاری وجود دارد که در انها جستجوی معمولی کفایت می‌کند.
  • استراتژی تنوع بخشی (Diversification Strategy): روش‌های مبتنی بر جستجوی محلی، ان‌قدر محلی هستند که زمان زیادی و یا تمامی زمان خود را در بخش محدودی از فضای جستجو صرف می‌کنند. نتیجه‌ای که از این واقعیت می‌توان گرفت، این است که هر چند جواب‌های خوبی به وسیله این روش­ها به دست می‌اید، اما ممکن است جستجو از اکتشاف مناطق بهتر باز بماند و بنابراین به جواب‌هایی برسد که از جواب بهینه، بسیار دور هستند. تنوع‌بخشی، یک مکانیزم الگوریتمیک است که برای حل این مشکل تلاش می‌کند. برای انجام این کار، تنوع‌بخشی جستجو را مجبور می‌کند به سوی مناطقی که تاکنون کشف نشده، حرکت کند.
  • مجوز دادن به جواب­های نشدنی: در حالت‌هایی که محدودیت‌های مساله بسیار محدودکننده باشند و از جستجوی موثر فضای جواب جلوگیری کنند، از این استراتژی استفاده می‌شود. طی این استراتژی محدودیت‌های مساله ازاد شده و بجای ان­ها یک مقدار جریمه به تابع هدف اضافه می‌شود.
Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26