• جستجوي ممنوع

روشی عمومي است كه به وسيله گلوور (Glover) در سال 1989 پيشنهاد شده و در حل مسائل برنامه‌ريزي كاري ـ خريد کاربرد دارد.

روش جستجوي ممنوع (Tabu Search)، همانند روش آنيلينگ شبيه‌سازي شده بر اساس جستجوي همسايه بنا شده است. در اين روش عملكرد حافظه انسان شبيه‌سازي شده است. حافظه انسان با به كارگيري ساختماني مؤثر و در عين حال ساده از اطلاعات، آنچه را در قبل رؤيت شده، ذخيره مي‌كند. اين مركز همچنين فهرستی از حركات منع شده را تنظيم مي‌كند و اين فهرست همواره بر اساس آخرين جستجوها منظم مي‌شود. اين روش از انجام هر گونه عمليات مجدد و تكراري جلوگيري مي‌كند.

شكل نوين جستجوي ممنوع توسط گلوور مطرح شده است. روش جستجوي مبتني بر منع، با ايجاد تغييري كوچك در روش جستجوي همسايه به وجود مي‌آيد. هدف اين روش آن است كه بخش‌هايي از مجموعه جواب كه پيش از اين بررسي نشده است، مد نظر قرار گيرد. بدين منظور حركت به جواب‌هايي كه اخيراً جستجو شده، ممنوع خواهد بود.

ساختار كلي روش جستجوي ممنوع بدين صورت است كه ابتدا يك جواب اوليه امكان‌پذير انتخاب مي‌شود؛ سپس براي جواب مربوط، بر اساس يک معيار خاص مجموعه‌اي از جواب‌هاي همسايه امكان‌پذير در نظر گرفته مي‌شود.

در گام بعد، پس از ارزيابي جواب‌هاي همسايه تعيين شده، بهترين آنها انتخاب مي‌شود و جابه‌جايي از جواب جاري به جواب همسايه انتخابي صورت مي‌گيرد. اين فرايند به همين ترتيب تكرار مي‌شود تا زماني كه شرط خاتمه تحقق يابد.

در روش جستجوي ممنوع، فهرستي وجود دارد كه جابه‌جايي‌هاي منع شده را نگهداري مي‌كند و به فهرست تابو معروف است و كاربرد اصلي آن، پرهيز از همگرا شدن به جواب‌هاي بهينه محلي است. به عبارت ديگر، به كمك فهرست تابو جابه‌جايي به جواب‌هايي كه اخيراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هايي از مجموعه جواب كه پيش از اين مورد بررسي قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جايي از جواب جاري به جواب همسايه امكان‌پذير زماني انجام مي‌شود كه در فهرست تابو قرار نداشته باشد. در غير اين صورت، جواب همسايه ديگري كه در ارزيابي جواب‌هاي همسايه در رده بعدي قرار گرفته است، انتخاب شده و جابه‌جايي به آن صورت مي‌گيرد.

در روش جستجوي ممنوع بعد از هر جابه‌جايي، فهرست تابو بهنگام مي‌شود، به نحوي كه جابه‌جايي جديد به آن فهرست اضافه شده و جابه‌جايي كه تا n تكرار مشخص در فهرست بوده است، از آن حذف مي‌شود. نحوه انتخاب مي‌تواند با توجه به شرايط و نوع مسأله متفاوت باشد.