hdsepe

جستجوی تابو، در مقایسه با شبیه­سازی حرارتی و الگوریتم ژنتیک، فضای راه­حل را خیلی بیشتر جستجو می­کند (یعنی حریص­تر از آن­هاست). الگوریتم­های جستجوی تابو با یک پیکربندی (یا مجموعه­ای از پیکربندی­ها در زمانی که جستجو به شکل هم­روندانجام می­شوند) مقداردهی اولیه می­گردد، که پیکربندی جاری نامیده می­شود. در هر دور تکرار الگوریتم، یک ساختار همسایگی برای پیکربندی جاری تعریف می­شود؛ سپس یک حرکت انجام می­شود تا به سوی بهترین پیکربندی در این همسایگی حرکت کند (یعنی در یک مسئله­ی کمینه­سازی، الگوریتم راهش را به سوی پیکربندی­ای جهت می­دهد که گویای کم­ترین هزینه است). در حالت عادی، تنها همسایگان با امیدبخشی بیشتر مد نظر قرار می­گیرند، در غیر این صورت ممکن است نتوان مسئله را به راه درستش هدایت کرد (مسئله­ی رام نشدنی). بر خلاف انواع الگوریتم­های حساس به تغییر[16] (الگوریتم­های گرادیانی)، که برای جستجوی محلی استفاده می­شوند، در جستجوی تابو همسایگی به شکل پویا (دینامیک) به­روزرسانی می­گردد. تفاوت دیگر این که انتقال به پیکربندی­های با هزینه­ی بالاتر (حالت نامناسب برای مسئله) مجاز است (این ویژگی روش را قادر می­سازد تا از نقطه­ی کمینگی محلی رهایی یابد). یک ویژگی ضروری الگوریتم­های جستجوی تابو خارج کردن مستقیم گزینه­های جستجویی است که به­طور موقت در دسته­ی مسیرهای ممنوع (تابو) قرار گرفته­اند. نتیجه این­که، در این الگوریتم­ها استفاده از حافـظه به گونه­ای بسیار شدید صورت می­گیرد: که یکی از محدودیت­های تابو است.

از دیگر سازوکارهای جستجوی تابو تشدیدو تنوع است: با وسیله­ی تشدید، الگوریتم جستجوی فراگیرتری را در ناحیه­های که ممکن است منتهی به بهینگی محلی گردند، اما مسیر را به سوی خود می­کشند، انجام می­دهد؛ از سوی دیگر، توسط تنوع، الگوریتم به ســـوی ناحیه­هایی حرکت می­کند که پیش­تر ملاقات نکرده است، چیزی که برای جلوگیری از نقاط کمینگی محلی مهم است. جستجوی تابو دارای مجموعه­ای از اصول (یا کارکردها) است که در حالتی یک­پارچه در مسیری هوشمند برای حل مسئله به کار گرفته می­شوند.

ویژگی­های اصلی (یا کارکردهای) جستجوی تابو این­گون خلاصه شده­اند:

1. حافظه­ی سازگار شونده (شکل پویای حافظه)

2. به­گزینی ( که دارای استراتژی فراموشی است)

3. ساده­سازی و تجزیه (در طول حافظه­ی واضح و با دسترسی مستقیم)

4. تنظیم زمان (یعنی هم تاخیر و هم تعداد تکرار وقایع و تفاوت میان کوتاه­مدت و بلند­مدت)

5. کیفیت و فشردگی (یعنی قدرت کشش نسبی انتخاب­های موجود و بزرگی تغییرات در ساختار یا روابط بازدارنده)

6. سابقه (شامل سابقه­ی ناحیه­ای، ساختاری و وابستگی­های متقابل ترتیبی)

7. جستجوی قابل پیش­بینی

8. محدودیت­ها و وسیله­های تحمیل شده با توجه به موقعیت (یا، شرایط ممنوعه و سطوح پیش­ران)

9. تمرکز فراوان بر ناحیه­ها و راه­حل­های خوب (فرایند تشدید)

10. مشخص کردن و کشف ناحیه­های امیدبخش تازه (فرایند تنوع)

11. الگوی جستجوی غیریک­نواخت (نوسان متناسب با وضعیت)

12. یک­پارچه­سازی و تعمیم راه­حل­ها (اتصال دوباره­ی مسیرها)

فايل ضميمه

Tabu Search.rar (2.51 مگابايت, 2098 نمايش)