Tabu Search — Yerel-Arama Meta-Sezgisel Yöntemi

Her iki yöntem de yerel optimumlardan kaçmak için kötüleşen hamleleri kabul eder, ancak mekanizmalarında farklılık gösterirler. Simüle tavlama, soğutma sıcaklığı parametresi tarafından yönlendirilen kötü hamleleri olasılıksal olarak kabul eder. Tabu Search, açık hamle belleği tarafından yönlendirilen en iyi mevcut tabu olmayan hamleyi deterministik olarak kabul eder. Tabu Search, yapılandırılmış kombinatoryal problemler üzerinde genellikle daha etkilidir; simüle tavlama, sürekli veya sürekliye yakın manzaralara sahip problemler üzerinde ayarlanması daha kolay olabilir ve iterasyon bütçesinin küçük olduğu (yaklaşık 1.000 iterasyonun altında) durumlarda tercih edilir.

Tabu süresi — bir hamlenin yasaklı kaldığı iterasyon sayısı — probleme bağlıdır. Yaygın olarak belirtilen bir başlangıç noktası, problem boyutunun kareköküyle orantılı bir süredir, ancak bu ampirik olarak ayarlanmalıdır. Çok kısa bir süre döngüye izin verir; çok uzun bir süre aramayı aşırı kısıtlar. Uyarlanabilir veya rastgeleleştirilmiş süre stratejileri bu seçime duyarlılığı azaltabilir.

Hayır. Tabu Search bir meta-sezgisel yöntemdir ve optimallik garantisi sunmaz. Yüksek kaliteli çözümleri verimli bir şekilde bulmayı hedefler, ancak sonuç komşuluk yapısına, süreye, iterasyon sayısına ve başlangıç çözümüne bağlıdır. Optimallik garantisi için, tam bir programlama gibi tam bir yöntem gereklidir, ancak tam yöntemler büyük örnekler için hesaplama açısından uygulanamayabilir.

Aspirasyon kriteri, özel koşullar altında bir hamlenin tabu durumunu geçersiz kılan bir kuraldır. En yaygın kriter şudur: tabu bir hamlenin yürütülmesi, şimdiye kadar bulunan en iyi çözümden daha iyi bir çözüm üretecekse, tabu kısıtlaması kaldırılır ve hamleye izin verilir. Bu geçersiz kılma olmadan, tabu mekanizması, yol yakın zamanda ziyaret edilen bir hamleden geçiyorsa küresel optimuma giden yolu kalıcı olarak engelleyebilir.