İçeriğe atla
Arama sonuçlarına dön

Stokastik Tabu Arama — Belleği Olan Rastgeleleştirilmiş Meta-Sezgisel Yöntem

Ortaya koyan
Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
Yıl
1990s
Tür
Stochastic metaheuristic optimizer
Aile
Simulation / optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

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.

Yöntemin mantığı

Klasik Tabu Arama, döngüyü önlemek için kısa süreli bir bellek (tabu listesi) kullanarak, her zaman izin verilen en iyi hamleye geçerek bir çözüm uzayında gezinir. Ancak pratikte, izin verilen en iyi hamle algoritmayı manzaranın bir bölgesine hapsedebilir. Stokastik Tabu Arama, kontrollü rastgelelik enjekte eder: bir sonraki hamle, açgözlüce yerine aday komşulardan oluşan bir kümeden olasılıksal olarak seçilir ve arayışı çeşitlendirmek için ara sıra rastgele pertürbasyonlar tanıtılır. Bu, TS'nin bellekle yönlendirilen disiplinini korurken, saf deterministik inişin eksik olduğu keşif gücünü ekler.

Tarih

Tabu Arama, 1986 yılında Fred Glover tarafından resmen tanıtıldı ve 1989-1990'daki dönüm noktası niteliğindeki makalelerde detaylandırıldı. Stokastik uzantılar, araştırmacılar büyük ölçekli problemlerin deterministik komşuluk değerlendirmesinin darboğaz olduğunu fark ettiklerinde 1990'larda ortaya çıktı. Çeşitlendirmeyi iyileştirmek için rastgele aday örnekleme, olasılıksal hamle kabulü ve gürültü enjeksiyonu dahil edildi ve bu da genel olarak Stokastik Tabu Arama olarak adlandırılan şeye yol açtı. Teknik, operasyon araştırmaları, mühendislik tasarımı ve makine öğrenimi hiperparametre optimizasyonunda yaygın olarak uygulanmaktadır.

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.

Sınırlar ve dikkat edilmesi gerekenler

  • 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.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • 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.

Uygulama alanları

  • Belirsiz talepler altında araç rotalama ve lojistik optimizasyonu
  • Stokastik işlem sürelerine sahip iş atölyesi ve açık atölye çizelgelemesi
  • Yüksek boyutlu makine öğrenimi veri kümelerinde özellik seçimi
  • Ağ tasarımı ve topoloji optimizasyonu
  • Kombinatoryal varlık seçimi kısıtlamalarına sahip portföy optimizasyonu
  • Karmaşık simülasyon modelleri için hiperparametre ayarlaması

Nasıl çalışır?

Nasıl çalışır?

1

Rastgele veya sezgisel olarak ilk bir x0 çözümü üretin. Tabu listesi T'yi boş olarak ayarlayın, tabu süresi tau, iterasyon sınırı I_max ve stokastik parametreleri (örneğin, aday liste boyutu k, pertürbasyon olasılığı p_perturb) tanımlayın.

2

Her iterasyonda, tüm komşuları değerlendirmek yerine tam komşuluk N(x_current)'nin rastgele bir alt kümesi N_s'yi örnekleyin. Bu, iterasyon başına maliyeti azaltır ve uzayın hangi bölgelerinin keşfedildiğine stokastiklik katar.

3

Bir sonraki çözüm x_next'i N_s'den seçin: ya (a) %1-p_perturb olasılıkla en iyi tabu olmayan adayı seçin veya (b) %p_perturb olasılıkla çeşitlendirmek için rastgele bir tabu olmayan aday seçin. x_next bilinen en iyi çözümü iyileştirirse, beklenti kriterleri tabu durumunu geçersiz kılabilir.

4

x_current'i (veya hamle özniteliğini) tabu listesi T'ye ekleyin. |T| > tau ise en eski girdiyi kaldırın. f(x_next) < f(x_best) ise mevcut en iyi çözümü x_best güncelleyin.

5

I_max iterasyona ulaşılana, hedef bir hedef değere ulaşılana veya bir sabır penceresi boyunca iyileşme olmayana kadar komşuluk_örnekleme yoluyla tabu_güncelleme işlemini tekrarlayın. Nihai çözüm olarak x_best'i döndürün.

Sık yapılan hatalar

  • Tabu süresini çok kısa ayarlamak, tabu listesine rağmen döngüye izin verir; çok uzun ayarlamak ise umut vadeden bölgeleri gereksiz yere engeller.
  • Çok küçük bir aday listesi kullanmak (agresif alt örnekleme), aramanın iyi komşuları tutarlı bir şekilde kaçırmasına neden olabilir.
  • Beklenti kriterlerini ihmal etmek, algoritmanın tabu olan küresel olarak iyileştirici hamleleri reddetmesine neden olur.
  • Birden fazla yeniden başlatma veya tohum olmadan yalnızca tek bir çalıştırmayı raporlamak, tipik çözüm kalitesi hakkında yanıltıcı bir resim verir.
  • Stokastik Tabu Arama'yı Tavlama Benzetimi ile karıştırmak: her ikisi de stokastiktir ancak temelden farklıdır — STS açık bellek kullanırken SA, bellek olmadan sıcaklığa dayalı olasılıksal kabul kullanır.

Sık sorulan sorular

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.

İlgili yöntemler

Kaynaklar

  1. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.

    DOI kaynağını aç
    Kopyalandı.
  2. 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 kaynağını aç
    Kopyalandı.