چمران-الكترو كامپ

وبلاگ جدید چمران الکتروکامپ

 جستجوی تابو (Tabu Search)

 تاریخچه

جستجوی تابو نخستین بار توسط فرد گلوور[1] در مقاله­ی منتشر شده در سال 1986]گلوور،1986[ بیان شد، البته این مقاله از بسیاری نظریه­های پیشنهادی در گذشته طی دهه­ی 60 استفاده کرده بود. دو مقاله­ای ]گلوور،1989،گلوور،1990[ که عنوان آنها جستجوی تابو بود بسیاری از اصولی را که امروزه شناخته شده­اند، بیان کردند. برخی از این اصول اقبال چندانی را برای مدت طولانی در میان جامعه­ی علمی به­دست نیاورد. در واقع، در نیمه­ی نخست دهه­ی 90، بیشتر کارهای تحقیقاتی در زمینه­ی جستجوی تابو، دامنه­ی کوچکی از اصول این روش[2] را به کار می­گرفت؛ که عموما محدود به یک لیست تابو[3]  و یک شرط تکاملی[4] ساده بود.

شهرت جستجوی تابو وام­دار کارهای پیش­گامانه­ای است که توسط گروه دی . دِ ورا[5] در سازمان فدرال تکنولوژی سوییس[6]،لاسن[7]، در اواخر دهه­ی 80 صورت گرفت. در حقیقت مقاله­ی گلوور، کاشف روش، در زمانی که هنوز «فرهنگ اکتشافی[8]»   وجود نداشت، به خوبی درک نشد. بنابراین عامل اعتباری مهم برای شهرت روش اصلی به هرتز و دِورا [هرتز[9] و دِ ورا، 1987، هرتز و دِ ورا، 1991، هرتز و دِ ورا، 1989]  مربوط می­شود که به طور قطع نقش بزرگی در انتشار روش ایفا کردند.

در همین زمان رقابتی میان روش شبیه­سازی حرارتی (که دارای یک نظریه­ی همگرایی قطعی به عنوان امتیاز نظری­اش بود) و جستجوی تابو ایجاد شد. در بسیاری کاربردها روش­های اکتشافی بر مبنای جستجوی تابو به روشنی نتایج موثرتری از خود نشان داد [تایرد[10]،1990، تایرد،1991،تایرد،1993،تایرد،1994]، که موجب افزایش اقبال جامعه­ی تحقیقاتی به این روش شد.

در آغاز دهه­ی90 این روش به کانادا و به طور دقیق­تر به مرکز تحقیقات ترابری در مونترال برده شد، جایی که پژوهش­گران فوق دکترا از از گروه دی.دِورا در این زمینه کار می­کردند. بدین­سان پایگاه دیگری از علاقه­مندی به زمینه­ی جستجوی تابو به­وجود آمد. از این پس روش به سرعت در میان جامعه­ی تحقیقاتی گسترش یافت و این گسترش با انتشار نخستین کتاب [گلوور اِت ال.،1993]، که کاملا به جستجوی تابو اختصاص داشت، به اوج خود رسید. در این بخش نمی­خواهیم بر روی اصول بسیار پیشرفته­ی جستجوی تابو، همچون اصول بیان شده در کتاب فرد گلوور و مانوئل لانگونا[11] [گلوور و لانگونا، 1997]، بپردازیم، بلکه قصد داریم روی مهم­ترین و عمومی ترین اصول تمرکز کنیم. در این­جا، لازم به گفتن است که گاهی نویسنده­ای دیگر به نظریه­ی اصلی جستجوی تابو نسبت داده می­شود. اما از ادعای چنین نسبتی ناشایست است: هیچ سند مکتوبی که آن نظریه­ها را بیان کند یافت نمی­شود، این نظریه­ها تنها در میان جمع کوچکی از حاضرین طی یک همایش در سال 1986 گفته شد و، بر اساس آن­چه در مورد آن ارائه شنیده­ شده است، شامل زیر مجموعه­ی محدودی از نظریه­های اصلی بوده است که پیش از آن توسط گلوور منتشر شده بود.

آن­چه که به طور قطع جستجوی تابو را از روش جستجوی محلی گفته شده در بخش پیشین متمایز می­سازد این است که جستجوی تابو دارای هوشمندی است.  در واقع، تمایل زیادی به هدایت یک جستجوی تکرارشونده[12] به سمت جلو، جهت مناسب، دارد به گونه­ای که جستجو تنها توسط احتمال و مقدار یک تابع هدف[13]، که باید بهینه شود، هدایت نگردد. توسعه­ی جستجوی تابو با دو چالش همراه است: نخست این­که، هم­چون هر جستجوی تکرارشونده­ای، نیاز است که موتور جستجو، یعنی همان رویه­ی سنجش راه­حل­های همسایه، عاملی موثر باشد؛ دوم این­که،  بخش­هایی از دانش ما در مورد مساله­ی تحت مطالعه باید به رویه­ی جستجو منتقل گردد تا این­که این رویه در ناحیه­ای نادرست از فضای راه­حل­ها محصور نشود. از سویی دیگر، روند باید به­طور هوشمند در فضای راه­حل هدایت گردد.

منشا نام جستجوی تابو

منشا نام این روش را می­توان از این نظریه یافت، که یک جستجوی محلی می­تواند با یک بهینگی محلی منتهی شود، با این اطمینان که به طور دوره­ای به یک بهینگی محلی یکسان بازنگردد، که نیازمند این است که از بازگشت جستجو به راه­حل­هایی که تاکنون بررسی شده­اند جلوگیری شود، به عبارت دیگر، برخی راه­حل­ها باید دارای یک وضعیت ممنوعه[14] باشند.

 توضیح روش

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1]  Fred Glover

[2]  technique

[3]   tabu list

[4]   aspiration condition

[5]   D.de Werra

[6]   Swiss Federal Institute of Technology

[7]   Lausanne

[8]   Metaheuristic culture

[9]  Hertz

[10] Taillard

[11] Manuel Languna

[12] Iterative

[13] Objective function

[14] tabu status

[15] Parallel

[16] Gradient type algorithms

[17] Intensification

[18] diversification