در سالهای اخیر روشهای مکاشفه ای (Heuristic) زیادی برای مسایل بهینه سازی ترکیبی (Combinatorial) پدید آمده است.

یکی از توانمند ترین روشهای فراکاوشی روش جستجوی ممنوعه (Tabu search) می باشد.

 

به این روشها فرا کاوشی گفته می شود زیرا می توان انها را با روشهای جستجوی محلی (Local search) ترکیب کرد تا بدین وسیله الگوریتم جستجو را به همسایگی های مطلوبتری هدایت کرد.

 

روشهای فراکاوشی (Meta Heuristic) اغلب با الهام گرفتن از طبیعت یا هوش بشری سعی در غلبه بر پیچیدگی های مسایل می نمایند.

با استفاده از این روشها در زمان محاسباتی معقول جوابهایی نزدیک جواب بهینه مطلق بدست می اید لیکن هیچ کدام از این روشها تضمینی برای یافتن جواب بیهنه مطلق بدست نمی دهد.

مفاهیم اولیه روش جستجوی ممنوعه توسط هنسن وجامارد (Hansen) در سال 1987 میلادی و فرد گلاور (F. Glover) در سال 1989 میلادی بیان شد و پس از ان به عنوان یکی از روشهای قدرتمند در حل مسایل بهینه سازی ترکیبی شناخته شده است.


 روش جستجوی ممنوعه (Tabu Search)


منشا روش جستجوی ممنوعه روش جستجوی محلی نزولی (Descend local search) می باشد. در این روش به صورت تصادفی یک نقطه به عنوان جواب اولیه تولید می شود، سپس با یک الگوریتم معین تعدادی جواب در همسایگی نقطه جاری تولید می شود و جستجو به بهترین جواب همسایگی که مقدار تابع هدف را بهبود بخشد انتقال می یابد، این مراحل تا زمانی تکرار می شود که به طور نسبی دیگر بهبودی در تابع هدف مشاهده نگردد. مشکل عمده این روش مواجهه با بهینه های محلی است که جستجو را متوقف کرده و بهینه محلی را به عنوان مقدار کمینه تابع معرفی می کند.
روش جستجوی ممنوعه برای یافتن جوابهای مطلوب در اینده، حتی مسیر های سر بالایی (Uphill Climbing) را به امید اینکه از بهینه های محلی فرار کند انتخاب می کند. در فرایند انتخاب بهترین جواب در همسایگی نقطه جاری، ابتدا مقادیر تابع هدف در تمامی نقاط همسایگی محاسبه و سپس به ترتیب مطلوبیت تابع هدف مرتب می گردند. در صورتی که بهترین جواب موجود در همسایگی در فهرست ممنوعه (Tabu List) موجود نباشد، ان نقطه انتخاب می گردد و در غیر این صورت جواب بعدی را با فهرست ممنوعه مقایسه می نماید و این روند تا پیدا شدن جوابی که در فهرست ممنوعه نباشد تکرار می شود.

کاربردهای جستجوی ممنوعه

از ابتدای ابداع روش جستجوی ممنوعه تا کنون این روش برای حل مسایل متفاوتی در زمینه های مختلف با موفقیت استفاده شده است در ادامه این قسمت چندین نمونه از کاربردهای مختلف این روش ارائه شده است.
1- الگوریتم های جستجوی محلی برای مساله درخت k-cardinality
2- استفاده از جستجوی ممنوعه تکرارشونده برای مساله توالی ماشین
3- یک الگوریتم جستجوی ممنوعه برای مساله طراحی سراسری3 برای نسل سوم شبکه های سیار
4- یک جستجوی ممنوعه و یک الگوریتم ژنتیک برای حل مساله عمومی دو معیاره زمانبندی کاری فروشگاه
5- یک الگوریتم جستجوی ممنوعه برای تست ساختاری نرم افزار
6- یک روش جستجوی ممنوعه برای مساله جمع اوری احشام7
7- جستجوی مکاشفه ای ممنوعه برای مساله تخصیص حافظه پویا
8- یک روش تکاملی برای مسائل رنگ امیزی چندتایی پهنای باند
9- بهینه سازی ساختاری و انتخاب ورودی از یک شبکه عصبی مصنوعی برای پیش بینی سطح رودخانه

نوشتن دیدگاه


 

آموزش های گام به گام

چهارمین کارگاه ارتباطات و نظریه اطلاعات برگزار می شود

چهارمین کارگاه ارتباطات و نظریه اطلاعات
چهارمین کارگاه ارتباطات و نظریه اطلاعات

ادامه مطلب...

سمینار پردازش زبان طبیعی

سمینار پردازش زبان طبیعی
سمینار پردازش زبان طبیعی

ادامه مطلب...

سمینار خانه های هوشمند برای دوران پیری

سمینار خانه های هوشمند برای دوران پیری

ادامه مطلب...

سمینار خانه های هوشمند برای دوران پیری

سمینار خانه های هوشمند برای دوران پیری

ادامه مطلب...