جستجوی تابو

جستجوی تابو – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

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

 در جستجوهای موضعی یا محلی این ایده القا می‌گردد که راه حل ارائه شده S را ممکن است بتوان با  اعمال تغییرات اندکی بهبود بخشیده  و یا ارتقا داد. این راه‌حلها که از طریق اعمال تغییراتی در راه‌حل S بدست می‌آید بنام مجاورین یا همسایگان S خوانده می‌شود. نقطه آغازگر الگوریتم جستجوی محلی برخی از راه‌حلهای ابتدایی یا اولیه بوده و تا حد ممکن از یک ناحیه مجاور به ناحیه مجاور بعدی تعمیم یافته و یا حرکت نموده و در عین حال ارزش تابع هدف را کاهش می‌دهد. یکی از مشکلات اصلی این استراتژی فرار از مینیمای (حداقل مقدار ممکن) محلی است، جائیکه جستجو قادر به یافتن راه‌حل مجاور بیشتری که ارزش تابع هدف را کاهش دهد نمی‌باشد.استراتژیهای مختلفی به منظور حل این مشکل پیشنهاد شده است. یکی از موثرترین و کاراترین این استراتژیها جستجوی تابو می‌باشد. جستجوی تابو به تابع جستجو اجازه می‌دهد تا راه‌حلهایی را بررسی نماید که کاهش دهنده ارزش تابع هدف نمی‌باشند، البته در صورتی که این راه‌حلها بصورت ممنوعه نباشند. این امر معمولا بوسیله پیگیری آخرین راه‌حل، بر حسب عملکرد، بکار گرفته شده برای انتقال یک راه‌حل به به مورد بعدی محقق می‌شود. به هنگامی که یک عمل انجام می‌پذیرد، این عمل برای تکرارهای T بعدی بعنوان تابو در نظر گرفته می‌شود، جائیکه T طول وضعیت تابو می‌باشد. یک راه‌حل تنها در صورتی ممنوع می‌شود که آن را از طریق کاربرد یک عمل تابو در راه ‌حل جاری بدست آورده باشیم. جستجوی تابو با استفاده از استراتژی متا‌هیوریستیک بوسیله فرد‌گلوور تعریف و معرفی شده است. ایده ابتدایی TS بوسیبه پی‌هنسن پایه‌گذاری شده است.

الگوریتم پایه جستجوی تابو

k := 1.
generate initial solution
WHILE the stopping condition is not met DO
    Identify N(s). (Neighbourhood set)
    Identify T(s,k). (Tabu set)
    Identify A(s,k). (Aspirant set)
    Choose the best s’ Π N(s,k) = {N(s) – T(s,k)}+A(s,k).
    Memorize s’ if it improves the previous best known solution
    s := s’.
    k := k+1.
END WHILE

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

موارد زیر بخشی از قابلیتهای این جستجو را نشان می‌دهند:

• برنامه‌ریزی

• تعیین معادله درجه دوم یا کوادراتیک

• تعیین‌های تناوب یا تکرار

• ترددهای مکرر

• تطبیق حدمیانه-P

• برنامه‌ریزی پروژه با توجه به محدودیت منابع (RCPSP)

• مشکلات تردد و مسیریابی وسائط نقلیه

• گرف‌کالرینگ – الگوریتم رضایت محدودیت

• مشکلات مشخصه یا چارچوب بازیابی

• مشکلات گروههای ویژه خاص

• مشکلات مسافرات تجار و فروشندگان

• سیستمهای بانک‌اطلاعاتی

• مشکلات ثبت لیست پرستاران

• استنباط یا استنتاج گرامری

• مشکلات مربوط به کوله بار

• SAT، مشکلات رضایت محدودیت

• شبکه ارتباطات

• طراحی شبکه

• بهینه‌سازی جهانی یا کلی