الگوریتم جستجوی کاشف
در علوم کامپیوتر، هوش مصنوعی و بهینه‌سازی، الگوریتم جستجوی کاشف، هیوریستیک یا ابتکاری، روشی برای حل مسائلی است که راه‌های کلاسیک حل آن‌ها بسیار کند می‌باشند یا راه‌حل تقریبی برای مسائلی است که راه‌های کلاسیک نمی‌توانند برای آن‌ها جواب دقیقی پیدا کنند.
بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق می‌باشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. هیوریستیک‌ها با استفاده از روش‌های نیازمند ارزیابی‌های کمتر و ارائه جوابی‌هایی در محدودیت‌های زمانی قابل قبول دارای نقشی اثر بخش در حل چنین مسائل خواهند بود.
دلایل استفاده از هیوریستیک‌ها
علاوه بر لزوم پیدا کردن راه‌حل مناسب برای مسئله‌های پیچیده در زمان منطقی، به دلایل دیگر استفاده از روش‌های هیوریستیک در زیر اشاره شده‌است:
- هیچ راه‌حل بهینه‌ای برای حل مسئله کشف نشده باشد.
- با وجود این که راه‌حل مشخص و دقیقی برای حل مسئله وجود دارد اما سخت‌افزار مناسب و پیشرفته برای پیاده کردن این راه‌حل موجود نمی‌باشد.
- راه‌حل هیوریستیک مسئله از انعطاف‌پذیری بیشتری نسبت به راه‌حل دقیق آن برخوردار است که در نتیجه اجازه می‌دهد شروطی از مسئله که شبیه‌سازی آن‌ها در حالت عادی سخت است، در راه‌حل هیوریستیک مدل شوند.
خصوصیات هیوریستیک‌های خوب
یک الگوریتم هیوریستیک خوب باید شامل خصوصیات زیر باشد:
- به دست آوردن راه‌حل مسئله شامل محاسبات زیاد و بسیار پیچیده نباشد.
- احتمال بهینه بودن راه‌حل به دست آمده باید بالا باشد.
- احتمال به دست آوردن راه‌حل نامناسب باید بسیار پایین باشد.
انواع روش‌های هیوریستیک
روش‌های هیوریستیک متعددی وجود دارند که به علت تنوع بالا و تفاوت ذاتی آن‌ها دسته‌بندی کامل این روش‌ها ممکن نمی‌باشد. همچنین بسیاری از آن‌ها تنها جوابگوی مسئلهٔ خاصی هستند و نمی‌توان آن‌ها را به مسائل دیگر بسط داد. با این حال می‌توان دسته‌بندی زیر را به عنوان یک دسته‌بندی کلی برای هیوریستیک‌ها در نظر گرفت:
- روش تجزیه: در این روش مسئله به مسئله‌های کوچکتر شکسته می‌شود که حل آن‌ها ساده‌تر است.
- روش استقرائی: در این نوع هیوریستیک‌ها سعی می‌شود راه‌حل به دست آمده برای مسئله در حالت ساده یا مقیاس کوچکتر، به مسئله اصلی تعمیم داده شود.
- روش تقلیل: در این روش هدف، کاهش فضای راه‌حل‌های ممکن برای مسئله است. باید توجه داشت که در این صورت به علت حذف بخش قابل توجهی از فضای حالت ممکن است بعضی از جواب‌های بهینه نیز از دست بروند و در نهایت جواب شبه بهینه به دست آید یا اصلا جواب شبه بهینه‌ای برای مسئله پیدا نشود.
- روش سازنده: در این روش راه‌حل مسئله قدم به قدم و از صفر ساخته می‌شود. معمولاً راه‌حل‌های این دسته جزو الگوریتم‌های قطعی می‌باشند و به‌طور گسترده در بهینه‌سازی ترکیبیاتی استفاده می‌شوند.
- روش جستجوی محلی: الگوریتم‌های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل‌های پیش رو (فضای جستجو) با استفاده از تغییرات محدود حرکت می‌کنند تا یک راه حل به نظر مطلوب یافت شود. زمانی که راه‌حل بهتری یافت نشود، این الگوریتم پایان می‌پذیرد.
در بین این روش‌ها، دو روش سازنده و جستجوی محلی زمینه‌ساز به وجود آمدن الگوریتم‌های فراابتکاری یا متاهیوریستیک‌ها می‌باشند.
ارزیابی کیفی یک هیوریستیک
روش‌های بسیاری برای ارزیابی کیفیت یک الگوریتم جستجوی کاشف وجود دارد که در زیر به برخی از آن‌ها اشاره شده‌است:
- مقایسه با راه‌حل بهینه: در صورتی که راه‌حل بهینه‌ای برای حالت‌های محدودی از مسئله وجود داشته باشد، می‌توان با مقایسه هیوریستیک به دست آمده با این راه‌حل، کیفیت هیوریستیک را سنجید.
- مقایسه با کران: در حالاتی که هیچ راه حل بهینه‌ای حتی در حالت‌های محدود از مسئله وجود ندارد می‌توان از این روش استفاده کرد که جواب به دست آمده از هیوریستیک با کرانی از جواب مسئله مقایسه می‌شود. واضح است که این مقایسه وابسته به کیفیت کرانی است که استفاده می‌شود.
- مقایسه با هیوریستک‌های دیگر: این روش جزو رایج‌ترین روش‌ها برای ارزیابی هیوریستک مسائل پیچیده‌ای است که برای مدت طولانی روی آن‌ها کار شده و هیوریستک‌های خوبی برای آن‌ها به دست آمده‌است. همانند روش "مقایسه با کران"، کیفیت هیوریستیک انتخابی برای مقایسه، تأثیر مستقیم روی نتیجهٔ ارزیابی دارد.
- بررسی بدترین حالت: در این روش بدترین حالت الگوریتم هیوریستیک بررسی می‌شود. نکته منفی راجع به این روش این است که معمولاً بدترین حالت الگوریتم هیوریستیک نمایانگر خوبی از حالت متوسط آن نیست.
جستارهای وابسته
منابع
- Rafael Martí, Gerhard Reinelt.(2011),"The Linear Ordering Problem", Springer-Verlag Berlin Heidelberg
- F.K. Hwang, D.S. Richards and P. Winter.(1992)."The Steiner Tree Problem, Annals of Discrete Mathematics,Vol. 53", North-Holland
- مشارکت‌کنندگان ویکی‌پدیا. «Heuristic (computer science)». در دانشنامهٔ ویکی‌پدیای انگلیسی.