Stokastik Tabu Arama — Belleği Olan Rastgeleleştirilmiş Meta-Sezgisel Yöntem
Stochastic Tabu Search — Randomized metaheuristic optimization with tabu memory · Ayrıca şöyle bilinir: STS, Randomized Tabu Search, Probabilistic Tabu Search, Noisy Tabu Search
Stokastik Tabu Arama (STS), klasik Tabu Arama'nın komşuluk keşfi ve hamle seçimi aşamalarına rastgelelik katan bir uzantısıdır. Son ziyaret edilen çözümleri yasaklayan tabu belleğini, olasılıksal kabul veya rastgele aday örnekleme ile birleştirerek STS, yerel optimumlardan daha etkili bir şekilde kaçar ve deterministik TS'nin aşmakta başarısız olabileceği engebeli çözüm manzaralarını keşfeder.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Deterministik yerel aramanın sürekli olarak takılıp kaldığı engebeli, çok modlu manzaralara sahip kombinatoryal veya sürekli kara kutu optimizasyon problemlerini çözerken Stokastik Tabu Arama'yı kullanın (örneğin, çizelgeleme, rotalama, özellik seçimi). Özellikle tam komşuluk değerlendirmesinin hesaplama açısından pahalı olduğu ve rastgele alt örneklemenin gerekli olduğu durumlarda değerlidir. Problemin dışbükey veya tek modlu olduğu durumlarda KULLANMAYIN — gradyan tabanlı veya kesin yöntemler daha hızlı ve optimaldir. Küresel optimalliği garanti etmeniz gerektiğinde bundan kaçının, çünkü STS sezgisel olarak bulunan en iyi çözümlerin ötesinde bir yakınsama garantisi sunmaz. Ayrıca, hedef fonksiyonun tamamen değerlendirilmesinin ucuz olduğu ve kapsamlı komşu araması olan deterministik bir TS'nin mümkün olduğu durumlarda bundan kaçının.
Güçlü yönler & sınırlılıklar
- Belleği olasılıksal keşifle birleştirerek deterministik Tabu Arama'dan daha etkili bir şekilde yerel optimumlardan kaçar.
- Adayları alt örnekleyerek büyük komşuluk yapılarına ölçeklenir, iterasyon başına hesaplama maliyetini azaltır.
- Tabu belleği, saf stokastik yöntemlerin yaygın bir başarısızlık modu olan döngüyü önler, örneğin rastgele yeniden başlatma tepe tırmanışı.
- Esnek çerçeve: yoğunlaştırma ve çeşitlendirme arasında denge kurmak için pertürbasyon olasılığı ve tabu süresi ayarlanabilir.
- Kombinatoryal problemler (TSP, çizelgeleme) ve küçük adaptasyonla sürekli optimizasyon için uygulanabilir.
- Küresel optimumu bulmak için teorik bir garanti yoktur; çözüm kalitesi büyük ölçüde parametre ayarlarına bağlıdır.
- Tabu süresi ve aday liste boyutu probleme özgü ayarlama gerektirir; yanlış seçimler erken yakınsamaya veya yavaş ilerlemeye yol açar.
- Stokastik çalıştırmalar, sabit bir rastgele tohum olmadan tekrarlanamaz, bu da karşılaştırmalı analiz ve denetimi karmaşıklaştırır.
- Bellek yükü, tabu listesi boyutuyla artar; büyük çözüm uzayları için öznitelik tabanlı tabu temsilleri gereklidir.
SSS
Stokastik Tabu Arama, Tavlama Benzetimi'nden nasıl farklıdır?
Her ikisi de stokastik meta-sezgisel yöntemlerdir, ancak STS, son ziyaret edilen hamleleri yasaklamak için açık bir tabu belleği kullanır ve döngüyü önler. SA'nın belleği yoktur — zamanla azalan bir olasılıkla (sıcaklık çizelgesi) daha kötü çözümleri kabul eder. STS, genellikle hamleleri tekrar ziyaret etmenin açık bir tehlike olduğu kombinatoryal problemler üzerinde daha güçlüdür.
Kaç iterasyon (I_max) çalıştırmalıyım?
Evrensel bir kural yoktur. Yaygın bir uygulama, problem boyutuna orantılı bir bütçeyle birden fazla bağımsız deneme (örneğin, 10-30 yeniden başlatma) çalıştırmak ve ardından en iyi ve ortalama sonuçları raporlamaktır. Karşılaştırmalı analiz için, rakip yöntemler tarafından kullanılan toplam fonksiyon değerlendirme bütçesini eşleştirin.
Stokastik Tabu Arama sürekli değişkenleri işleyebilir mi?
Evet, ancak sürekli bir komşuluk (örneğin, mevcut çözüm etrafında Gauss pertürbasyonu) ve tabu listesi için uygun bir öznitelik (örneğin, bir bölge veya yön) tanımlamayı gerektirir. Çoğu STS literatürü kombinatoryal problemleri hedefler; sürekli uzaylar için, Diferansiyel Evrim veya CMA-ES genellikle daha doğal alternatiflerdir.
Beklenti kriterlerinin rolü nedir?
Beklenti kriterleri, kabul edilmesi şimdiye kadar bulunan en iyi çözüme daha iyi bir çözüm sağlarsa, bir hamlenin tabu durumunu geçersiz kılar. Beklenti olmadan, algoritma tabu olan küresel olarak iyileştirici hamleleri kalıcı olarak reddedebilir, bu da çözüm kalitesini ciddi şekilde sınırlar.
Tekrarlanabilirlik için rastgele tohumu sabitlemeli miyim?
Evet, tekrarlanabilirliği sağlamak için araştırma sonuçlarını raporlarken tohumu sabitleyin. Pratikte, birden fazla tohumla çalıştırın ve stokastik manzara boyunca algoritma performansının güvenilir bir resmini vermek için istatistikleri (ortalama, en iyi, standart sapma) raporlayın.
Kaynaklar
- Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94. DOI: 10.1287/inte.20.4.74 ↗
- Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568. DOI: 10.1287/opre.1060.0367 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Stochastic Tabu Search — Randomized metaheuristic optimization with tabu memory. ScholarGate. https://scholargate.app/tr/simulation/stochastic-tabu-search
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Genetik AlgoritmaOptimizasyon↔ karşılaştır
- Parçacık Sürü Optimizasyonu (PSO)Optimizasyon↔ karşılaştır
- Simulated AnnealingOptimizasyon↔ karşılaştır
- Rastgele Evrimsel Optimizasyon AramaSimülasyon↔ karşılaştır
- Tabu SearchOptimizasyon↔ karşılaştır