Tabu Arama

#optimizasyon #meta-sezgisel #kombinatoryal #algoritma #yerel arama

Yerel aramayı tabu listesi kullanarak yerel minimumlardan kaçıran meta-sezgisel optimizasyon algoritması.

Tabu Arama, Fred Glover tarafından 1986 yılında geliştirilen ve kombinatoryal optimizasyon problemlerini çözmek için kullanılan meta-sezgisel bir arama algoritmasıdır. Temel fikir, yerel arama sırasında daha önce ziyaret edilen çözümleri veya yapılan hareketleri geçici olarak yasaklayan bir 'tabu listesi' tutmaktır. Bu mekanizma algoritmanın yerel optimumlardan kaçmasını ve arama uzayını daha geniş biçimde keşfetmesini sağlar. Algoritma, komşuluk araması yaparak mevcut çözümün komşularını değerlendirir ve tabu listesinde yer almayan en iyi komşuya geçer; bu nedenle çözüm kalitesini geçici olarak kötüleştiren adımlar da atılabilir. Uzun vadeli bellek yapıları (diversifikasyon) ile arama uzayının az keşfedilen bölgelerine yönelme ve yoğunlaştırma stratejileriyle umut vaat eden bölgelerdeki aramanın derinleştirilmesi mümkündür. Tabu Arama; gezgin satıcı problemi (TSP), çizelgeleme, araç rotalama, grafik renklendirme ve ağ tasarımı gibi NP-zor problemlerde yaygın olarak kullanılır.

Tabu Arama Nedir?

Tabu Arama (Tabu Search), Fred Glover tarafından 1986 yılında önerilen ve kombinatoryal optimizasyon problemlerini çözmek için tasarlanmış güçlü bir meta-sezgisel algoritmadır. Adını, arama süreci boyunca tutulan ve önceki hareketleri geçici olarak yasaklayan 'tabu listesi'nden alır.

Temel Bileşenler

Algoritmanın üç temel bileşeni vardır: (1) Komşuluk araması: Mevcut çözümün yakın komşuları değerlendirilir. (2) Tabu listesi: Son k hareket veya çözüm geçici olarak yasaklanır, bu sayede daha önce incelenen bölgelere geri dönülmez. (3) Aspirasyon kriteri: Tabu statüsünde olan bir hareket bile olsa sonuç şimdiye kadar bulunan en iyi çözümü geçiyorsa kabul edilir.

Yerel Optimumlardan Kaçış

Standart yerel arama algoritmaları yerel minimuma takılır ve oradan çıkamazlar. Tabu Arama ise tabu listesi sayesinde komşu çözümler kötü olsa bile aramaya devam edebilir; bu özellik algoritmanın daha geniş bir çözüm uzayını taramasına olanak tanır.

Bellek Yapıları

Tabu Arama iki tür bellek kullanır: Kısa vadeli bellek (tabu listesi) son yapılan hareketleri yasaklayarak döngüyü önler. Uzun vadeli bellek ise diversifikasyon (az keşfedilen bölgelere yönelme) ve yoğunlaştırma (umut veren bölgeleri derinlemesine inceleme) stratejileriyle aramanın kalitesini artırır.

Uygulama Alanları

Tabu Arama; gezgin satıcı problemi (TSP), iş çizelgeleme, araç rotalama, grafik renklendirme, ağ tasarımı, portföy optimizasyonu ve VLSI yerleşim problemlerinde başarıyla uygulanmaktadır. Özellikle NP-zor kombinatoryal problemlerde pratik sürede yüksek kaliteli çözümler üretmesiyle öne çıkar.