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

Sağlam Tabu Araması — Belirsizliğe karşı sağlamlığa sahip tabu tabanlı meta-sezgisel yöntem

Ortaya koyan
Glover, F. (Tabu Search); robustness extensions by various authors
Yıl
1989 (TS); robust variant ~2000s
Tür
Metaheuristic with robustness mechanism
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Sağlam Tabu Araması (RTS), aday çözümleri yalnızca nominal amaç değerlerine göre değil, aynı zamanda belirsizlik altındaki performanslarına göre de değerlendirerek klasik Tabu Araması meta-sezgisel yöntemini genişletir.

Tek bir senaryo için en iyi çözümü aramak yerine, RTS bir dizi senaryo veya gerçekleşme boyunca iyi performans gösteren çözümler arar, zirve uygunluğu güvenilirlik için takas eder.

Yöntemin mantığı

Klasik Tabu Araması, yakın zamanda ziyaret edilen hamleleri yasaklayarak ve komşuluk yoluyla aramayı yönlendirerek mükemmel çözümler bulur. Ancak pratikte, gerçek dünya girdileri — maliyetler, talepler, seyahat süreleri — değişkenlik gösterir. Varsayılan değerler altında optimal görünen bir çözüm, gerçeklik saptığında zayıf performans gösterebilir. Sağlam Tabu Araması, sağlamlık kriterini doğrudan değerlendirme fonksiyonuna yerleştirir: her aday çözüm, birden çok senaryo (örneklenmiş veya numaralandırılmış) üzerinde değerlendirilir ve arama, kararlı, düşük varyanslı performansa sahip çözümleri tercih eder. Bu, son çözümü, sonradan yeniden optimize etmeye gerek kalmadan parametre dalgalanmalarına karşı dayanıklı hale getirir.

Tarih

Tabu Araması, 1989–1990'da Fred Glover tarafından, yakın zamanda tersine çevrilen hamleleri yasaklayarak yerel uygunluktan kaçan, hafıza tabanlı bir meta-sezgisel yöntem olarak tanıtıldı. Sağlam genişletmeler, sağlam optimizasyona olan ilginin artmasıyla birlikte 1990'ların sonlarında ve 2000'lerde ortaya çıktı; araştırmacılar, TS komşuluk değerlendirmesine senaryo tabanlı ve en kötü durum değerlendirmelerini dahil ederek, belirsizlik altındaki mühendislik ve lojistik problemleri için pratik bir araç olarak Sağlam Tabu Araması'nı ortaya çıkardılar.

Ne zaman kullanılır?

Temel girdi parametrelerinin belirsiz veya değişken olduğu — talep veya maliyet belirsizliği altında rota, çizelgeleme, atama veya ağ tasarımı problemleri — kombinatoryal veya ayrık optimizasyon problemiyle karşılaştığınızda Sağlam Tabu Araması'nı kullanın. Özellikle dağıtım sonrası yeniden optimizasyon maliyetinin yüksek olduğu veya uygulamadan önce çözümlerin güvenilir olarak onaylanması gerektiği durumlarda uygundur. Problem tamamen deterministik olduğunda (klasik Tabu Araması yeterlidir), belirsizlik kümesi kabul edilemez bir hesaplama olmadan tractably örneklenemeyecek kadar büyük olduğunda veya problem düzgün ve dışbükey olduğunda (gradyan tabanlı sağlam yöntemler daha hızlı ve daha güvenilir olacaktır) RTS'den kaçının.

Sınırlar ve dikkat edilmesi gerekenler

  • Büyük bir senaryo kümesi üzerinde sağlamlığı değerlendirmek, iterasyon başına hesaplama maliyetini |S| ile çarpar, bu da kabul edilemez olabilir.
  • Sağlamlığın kalitesi büyük ölçüde senaryo kümesinin kalitesine bağlıdır; zayıf senaryo kapsamı yanlış güven verebilir.
  • Sekme süresi ve komşuluk boyutu, ayar gerektiren probleme özgü hiperparametrelerdir.
  • Küresel uygunluk veya çözüm kalitesi sertifikası garanti etmez.

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

Güçlü yönleri

  • Girdi değişkenliğine karşı, sonradan sağlamlık kontrolü gerektirmeden sağlam çözümler bulur.
  • Zorlu kombinatoryal problemler (çizelgeleme, VRP, TSP varyantları) üzerinde Tabu Araması'nın güçlü ampirik performansını miras alır.
  • Esnek sağlamlık kriteri: minimax, beklenen değer, ortalama-varyans ve yüzdelik tabanlı amaçları destekler.
  • Problem dışbükeyliği veya türevlenebilirliği gerektirmez — kutu-dışı ve ayrık amaçlara uygulanabilir.
  • Sekme mekanizması, yerel olarak sağlam ancak küresel olarak vasat çözümlere takılıp kalmayı önler.

Uygulama alanları

  • Rastgele seyahat süreleri veya müşteri talepleri altında sağlam araç rotalama
  • Belirsiz işleme süreleri ile iş-dükkanı ve akış-dükkanı çizelgeleme
  • Talep dalgalanması altında ağ tasarımı ve kapasite planlama
  • Belirsiz tedarikçi teslim süreleri veya maliyetleri ile tedarik zinciri optimizasyonu
  • Girişim belirsizliği altında telekomünikasyonda frekans ataması
  • Kombinatoryal kısıtlamalar kullanarak belirsiz varlık getirileri ile portföy optimizasyonu

Nasıl çalışır?

Nasıl çalışır?

1

Kombinatoryal veya sürekli optimizasyon problemini tanımlayın, belirsiz parametreleri (örneğin, talepler, maliyetler, işleme süreleri) belirleyin ve makul gerçekleşmeleri temsil eden bir senaryo kümesi S belirleyin — dağılımlardan örnekleme yaparak veya ayrık bir belirsizlik kümesi oluşturarak. Sağlamlık amacını belirleyin: en kötü durum maliyetini minimize etmek, beklenen maliyeti minimize etmek veya ortalama ve varyansın ağırlıklı bir kombinasyonunu minimize etmek.

2

Arama sırasında karşılaşılan her aday çözüm x için, amaç fonksiyonunu f(x, s) her senaryo s in S altında değerlendirin. Sağlamlık ölçüsünü R(x) hesaplayın — örneğin, minimax sağlamlığı için R(x) = max_{s in S} f(x,s) veya ortalama-varyans sağlamlığı için R(x) = E[f(x,s)] + lambda * Var[f(x,s)]. Bu, klasik Tabu Araması'nda kullanılan tekil nominal değerlendirmenin yerini alır.

3

Mevcut çözüm x'in komşuluğunu N(x), tüm geçerli hamleleri (değiştirmeler, eklemeler, ters çevirmeler vb.) uygulayarak oluşturun. Sekme listesinde olmayan her komşu x'in R(x') değerini değerlendirin, ancak bir beklenti kriteri karşılanırsa sekme listesindeki hamleler hariç. En iyi sağlamlık değerine R(x*) sahip komşuyu x* seçin.

4

x*'e geçin ve uygulanan hamlenin tersini sekme listesine t süresiyle (genellikle 5–20 iterasyon) kaydedin. Sekme listesi döngüyü önler ve keşfi teşvik eder. Sekme kısıtlamasını geçersiz kılabilecek beklenti kriterleri — örneğin, küresel olarak en iyi sağlam çözümü üreten bir sekme hamlesini kabul etmek gibi — kullanılabilir.

5

R(x*) mevcut en iyi çözümü iyileştirirse en iyi bilinen sağlam çözümü güncelleyin. Bir durdurma kriteri karşılanana kadar yineleyin: maksimum iterasyon, geçen süre veya belirli sayıda adımda iyileşme olmaması. Bulunan en iyi sağlam çözümü senaryo bazlı performans profiliyle birlikte döndürün.

Sık yapılan hatalar

  • Çok az senaryo kullanmak gerçek belirsizliği hafife alır ve pratikte başarısız olacak çözümler üretir.
  • Sağlam Tabu Araması ile Stokastik Tabu Araması'nı karıştırmak: sağlam optimizasyon en kötü durumlara maruz kalmayı en aza indirir, oysa stokastik TS beklenen değeri tahmin etmek için örnekleme yapar — amaçlar ve yorumlar farklıdır.
  • Olasılığı ihmal edilebilir olan en kötü durum senaryosunda minimax sağlamlığı uygulamak, gereksiz maliyetle aşırı muhafazakar çözümlere yol açar.
  • Beklenti kriterlerini göz ardı etmek, aramanın sekme hamleleri içeren küresel olarak sağlam çözümleri kaçırmasına neden olabilir.
  • Sekme süresini çok yüksek ayarlamak aşırı kısıtlama yaratır; çok düşük ayarlamak döngüye neden olur — her ikisi de çözüm kalitesini düşürür.

Sık sorulan sorular

Sağlam Tabu Araması, Stokastik Tabu Araması'ndan nasıl farklıdır?

Stokastik Tabu Araması, beklenen değerleri tahmin etmek için tipik olarak arama prosedürünün kendisinde rastgele örnekleme kullanır (örneğin, olasılıksal kabul veya rastgele komşuluk örneklemesi). Sağlam Tabu Araması, tanımlanmış bir belirsizlik kümesi üzerinde değerlendirilen en kötü durum veya ortalama-varyans performansı gibi bir sağlamlık kriterini açıkça optimize eder. Sağlam TS'deki amaç, yalnızca beklenen performans değil, senaryolar boyunca çözüm stabilitesidir.

Senaryo kümesi S ne kadar büyük olmalı?

Evrensel bir kural yoktur. Ayrık belirsizlik kümeleri için, mümkünse tüm güvenilir senaryoları numaralandırın. Sürekli dağılımlar için, 50–500 örneklenmiş senaryo genellikle yeterli kapsama sağlar; Latin hiperküp örneklemesi gibi varyans azaltma teknikleri verimliliği artırabilir. Nihai senaryo sayısına karar vermeden önce |S| üzerindeki duyarlılık analizi tavsiye edilir.

Sağlam Tabu Araması çok amaçlı problemleri ele alabilir mi?

Evet. Çok amaçlı Tabu Araması çerçeveleriyle birleştirildiğinde, sağlamlık ek bir amaç veya kısıtlama haline gelir. (nominal performans, sağlamlık) Pareto cepheleri keşfedilebilir, bu da uygunluğu güvenilirlik için takas eden bir çözüm kümesi üretir — paydaşların risk toleranslı ve riskten kaçınan seçenekler arasında seçim yapması gerektiğinde kullanışlıdır.

Hangi sağlamlık ölçüsünü seçmeliyim?

Minimax (en kötü durum), arızaların feci olduğu ve düşük olasılıklı kötü sonuçların bile kabul edilemez olduğu durumlarda uygundur. Beklenen değer, risk-nötr karar vericilere uyar. Ortalama-varyans, ortalama performansı ve değişkenliği dengeler ve mühendislik tasarımında yaygındır. Değer-Risk (VaR) veya Koşullu VaR metrikleri, yüzdelik tabanlı garantilerin önemli olduğu finansal ve lojistik uygulamalarda kullanılır.

Sağlam Tabu Araması çok büyük örnekler için uygun mudur?

Senaryo değerlendirme maliyetine bağlıdır. Her bir f(x,s) değerlendirmesi ucuzsa (milisaniyeler), yüzlerce senaryo üzerindeki sağlamlık, büyük örnekler için bile tractably kalır. Her değerlendirme bir simülasyon veya pahalı bir çözücü çağrısı gerektiriyorsa, agresif senaryo azaltma veya vekil modelleri gerekli hale gelir. Senaryoların iş parçacıkları veya makineler arasında paralel değerlendirilmesi yaygın bir azaltma yöntemidir.

İlgili yöntemler

Kaynaklar

  1. Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    DOI kaynağını aç
    Kopyalandı.
  2. Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.

    Yayın kaynağını aç
    Kopyalandı.