Tabu Arama

#Optimizasyon #MetaSezgisel #KombinatoryelOptimizasyon #Algoritma

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

Tabu Arama (Tabu Search), Fred Glover tarafından 1986 yılında geliştirilen ve 1989'da ORSA Journal on Computing'de yayımlanan meta-sezgisel bir optimizasyon algoritmasıdır. Kombinatoryal optimizasyon problemlerinde yerel aramayı bir üst düzeye taşıyan bu yaklaşım, gezgin satıcı problemi (TSP), iş çizelgeleme ve araç rotalama gibi NP-zor problemlerde kaliteli çözümler üretmektedir. Algoritmanın çekirdeğinde tabu listesi mekanizması yatar. Her adımda mevcut çözümün komşuları değerlendirilir ve tabu listesinde yer almayan en iyi komşuya geçilir. Bu adım anlık çözüm kalitesini geçici olarak düşürebilir; ancak döngüsel arama tuzağının önüne geçer. Tabu listesinin uzunluğu (tabu tenure, genellikle 5–20 adım) kritik bir hiperparametredir: kısa liste çevik fakat döngüye açık, uzun liste ise aşırı kısıtlayıcı olabilir. Reaktif Tabu Arama varyantı bu dengeyi otomatik yöneterek döngü saptandığında tenure'ü uzatır, çeşitlilik arttığında kısaltır. Algoritma iki tür bellek yapısıyla çalışır. Kısa vadeli bellek (tabu listesi) son k hareketi yasaklayarak döngüyü engeller. Uzun vadeli bellek ise iki strateji barındırır: diversifikasyon az keşfedilen bölgelere yönlendirir; yoğunlaştırma umut vaat eden bölgeleri derinlemesine tarar. Bu bellek hiyerarşisi, simüle tavlama gibi tek bellekli yöntemlere kıyasla daha tutarlı sonuçlar ortaya koyar ve büyük arama uzaylarında bile etkin bir tarama gerçekleştirmeyi olanaklı kılar. Aspirasyon kriteri tabu listesinin katılığını yumuşatır: bir hareket tabu statüsünde olsa bile o ana kadar bulunan global en iyi çözümü geçiyorsa kabul edilir. Bu kural aşırı kısıtlamadan kaynaklanan fırsatçı kayıpları engeller ve algoritmanın yüksek kaliteli bölgelere erişimini korur. Tabu Arama, paralel uygulama ve derin öğrenme hibridleriyle de kullanılmaktadır. Paralel Tabu Arama birden fazla başlangıç noktasından eş zamanlı arama yaparak çözüm çeşitliliğini artırır. Günümüzde hiperparametre araması ve sinir mimarisi optimizasyonunda (NAS) Tabu Arama bileşenleri, gradyan tabanlı olmayan etkili bir alternatif olarak değer görmektedir.

Tabu Arama Nedir?

Tabu Arama (Tabu Search), Fred Glover tarafından 1986 yılında önerilen ve 1989'da ORSA Journal on Computing'de formalize edilen meta-sezgisel bir optimizasyon algoritmasıdır. Adını, arama sürecinde önceki hareketleri geçici olarak yasaklayan 'tabu listesi' bileşeninden alır. Standart yerel aramadan farklı olarak anlık çözüm kalitesini geçici olarak kötüleştirebilir; bu özellik yerel optimumlardan kaçmayı ve arama uzayının farklı bölgelerini keşfetmeyi mümkün kılar. Simüle tavlamanın olasılıksal kabulüne karşın Tabu Arama deterministik kurallarla çalışır; bu nedenle tekrarlanabilirlik gerektiren endüstriyel uygulamalarda tercih edilir.

Temel Bileşenler

  • check_circle Tabu Listesi: Son k hareketi veya çözümü geçici olarak yasaklar (tabu tenure genellikle 5–20 adım). Döngüsel aramayı önleyen kısa vadeli bellek işlevi görür.
  • check_circle Komşuluk Araması: Mevcut çözümün tüm (veya örneklenmiş) komşuları değerlendirilir; tabu listesinde bulunmayan en iyi komşuya geçilir, anlık kötüleşme göze alınabilir.
  • check_circle Aspirasyon Kriteri: Tabu statüsündeki bir hareket bile olsa global en iyi çözümü aşıyorsa listeyi delerek kabul edilir. Aşırı kısıtlamadan kaynaklanan fırsatçı kayıpları engeller.
  • check_circle Uzun Vadeli Bellek: Diversifikasyon az keşfedilen bölgelere yönlendirir; yoğunlaştırma umut vaat eden bölgeleri derinlemesine tarar. İki strateji birlikte uygulandığında arama kapsamı ve kalitesi artar.

Yerel Optimumlardan Kaçış

Standart yerel arama algoritmaları ilk karşılaştıkları yerel minimuma takılır. Tabu Arama'da tabu listesi bu sorunu çözer: komşu çözümler mevcut çözümden daha kötü olsa bile arama, liste dışında kalan en iyi komşuya yönlenir. Böylece algoritma 'tepeyi aşma' ve 'vadiden çıkma' gibi olumsuz adımları göze alabilir.

Benzetimli tavlama kötü adımları olasılıksal kabul ederken, Tabu Arama kötü adımları deterministik kurallarla yönetir: hangi hareketlerin yasaklanacağı, hangi durumlarda yasağın kaldırılacağı açıkça belirlenir. Bu netlik özellikle mühendislik ve lojistik gibi tekrarlanabilirlik gerektiren alanlarda avantaj oluşturur.

Bellek Hiyerarşisi ve Varyantlar

Tabu Arama'yı diğer meta-sezgisel yöntemlerden ayıran en belirgin özellik çoklu bellek hiyerarşisidir. Tabu tenure kritik bir parametredir: küçük değerler arama esnekliğini artırırken büyük değerler çeşitliliği kısıtlar. Reaktif Tabu Arama varyantı bu dengeyi otomatik yönetir: döngü saptandığında listeyi uzatır, çeşitlilik arttığında kısaltır.

Paralel Tabu Arama birden fazla başlangıç noktasından eş zamanlı arama yaparak çözüm çeşitliliğini artırır. Hibrit modeller ise Tabu Arama'yı genetik algoritmalar veya parçacık sürüsü optimizasyonuyla birleştirerek büyük ölçekli problemlerde daha etkili çözümler üretir.

Uygulama Alanları

  • check_circle Gezgin Satıcı Problemi (TSP): En yaygın test ortamı; Tabu Arama 1990'larda büyük ölçekli TSP örneklerinde rekabetçi çözümler üretmiştir.
  • check_circle İş Çizelgeleme: İş akış çizelgeleme (job shop scheduling) problemlerinde makine sürelerini ve kısıtları gözeterek optimal iş ataması.
  • check_circle Araç Rotalama (VRP): Lojistik ve dağıtım optimizasyonunda kapasite kısıtlı araç rotalama problemlerinde pratik sürede yüksek kaliteli rotalar üretir.
  • check_circle Grafik Renklendirme: Minimum renk sayısıyla komşu düğümlerin farklı renklendirildiği NP-zor grafik problemlerinde etkin çözümler bulur.
  • check_circle Sinir Mimarisi Araması (NAS): Hiperparametre araması ve mimari optimizasyonunda gradyan tabanlı olmayan arama bileşeni olarak kullanılmaktadır.

Sık Sorulan Sorular

  • check_circle Tabu Arama ile Simüle Tavlama arasındaki temel fark nedir? Simüle Tavlama kötü adımları sıcaklık parametresine bağlı olasılıksal kural ile kabul eder. Tabu Arama ise tabu listesi ve aspirasyon kriteri gibi deterministik kurallar kullanır; tekrarlanabilirlik ve yorumlanabilirlik açısından avantajlıdır.
  • check_circle Tabu tenure (listenin uzunluğu) nasıl seçilir? Genellikle 5–20 arasında deneme-yanılma ile belirlenir. Reaktif Tabu Arama varyantı döngü saptandığında listeyi dinamik uzatır, çeşitlilik arttığında kısaltır; böylece parametre ayarı otomatikleşir.
  • check_circle Aspirasyon kriteri olmadan ne olur? Tabu listesi global en iyi çözüme götürecek hareketi de engelleyebilir. Aspirasyon kriteri olmayan Tabu Arama bu durumda daha kötü sonuçlar üretir; kural listenin aşırı kısıtlayıcı davranışını dengeler.
  • check_circle Tabu Arama hangi durumlarda iyi bir seçimdir? Gradient bilgisi olmayan, süreksiz veya kombinatoryal çözüm uzaylarında; özellikle TSP, çizelgeleme ve VLSI yerleşim gibi NP-zor problemlerde güçlü bir seçenektir.
  • check_circle Tabu Arama derin öğrenme ile birlikte kullanılır mı? Evet. Hiperparametre araması ve Sinir Mimarisi Araması (NAS) alanlarında gradyan tabanlı olmayan arama bileşeni olarak Tabu Arama aktif biçimde kullanılmaktadır.