Tabu Arama

Tabu arama, Glover (1986, 1989, 1990) tarafından önerilen bellek-tabanlı bir metaheuristiktir; bağımsız olarak benzer bir fikir Hansen (1986) tarafından da ortaya konmuştur. Algoritmanın ayırt edici özelliği açık bir hafıza yapısı kullanmasıdır — tavlama benzetimi rastlantısallığa, genetik algoritma popülasyona dayanırken tabu arama son hamlelerin veya ziyaret edilen çözüm özniteliklerinin listesini tutarak aynı bölgeye dönmeyi yasaklar. Temel öğeleri: (1) komşuluk yapısı ve hamle değerlendirmesi; her iterasyonda mevcut çözümün en iyi komşusuna geçilir, kötüleşmeyi olsa bile (yerel optimumdan çıkış); (2) kısa-dönem bellek (tabu listesi) — son k hamle yasaklı, k tabu süresi (tenure) ile kontrol edilir; (3) aspirasyon kriteri — tabu hamle bile şimdiye dek bulunan en iyi çözümü geliştirirse kabul edilir; (4) orta-dönem bellek (yoğunlaşma) — sık ziyaret edilen iyi çözümler etrafında arama derinleştirilir; (5) uzun-dönem bellek (çeşitlendirme) — hiç ziyaret edilmemiş bölgelere yönelik atlamalar. Granular tabu search, reactive tabu search (Battiti ve Tecchiolli 1994; tenure'u otomatik ayarlar) ve adaptive memory programming yaygın uzantılardır. VRP, scheduling, çizelgeleme, atama problemlerinde en güçlü metaheuristiklerden biridir; Cordeau-Laporte VRP çalışmaları endüstri kıyaslamasıdır. Tavlama benzetimi ile karşılaştırıldığında daha deterministik ve hafıza-yoğundur; benzer kalite, daha az parametre hassasiyeti. Referanslar: Glover ve Laguna (1997), Gendreau ve Potvin (2010).