tag KombinatoryelOptimizasyon

Bu sayfada KombinatoryelOptimizasyon etiketi ile işaretlenmiş 1 yapay zeka kavramını bulabilirsiniz.

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 (Tabu Arama)

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.

arrow_forward