hdsepe

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

فايل ضميمه

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

masood

سوال فنی شاید ضایع:
این N(x) و N*(x) چی بود؟

__________________
یک روز یک ماشین برای انتخابات ریاست جمهوری ثبت نام می کند
چه بخواهیم چه نخواهیم این اتفاق می افتد.

damaghderaz

سلام
من نمي تونم فايل هاي ضميمه رو دانلود كنم. دائما به يه صفحه منتقل ميشه كه بايد يوزر و پسورد رو دوباره وارد كنم.
لطفا راهنمايي كنيد
ممنون