Tabu Search — Yerel-Arama Meta-Sezgisel Yöntemi
- Ortaya koyan
- Fred Glover
- Yıl
- 1989
- Tür
- Local-search metaheuristic
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Tabu Search, Fred Glover tarafından 1989'da tanıtılan, döngüyü önlemek ve yerel optimumlardan kaçmak için tabu listesi — yakın zamanda ziyaret edilen çözümlerin kısa süreli belleği — kullanan bir yerel-arama meta-sezgisel yöntemidir.
Son kararları tersine çeviren hamleleri açıkça yasaklayarak, algoritma arama uzayını daha geniş bir şekilde keşfeder ve aspirasyon kriterleri gibi uzun süreli bellek yapıları aracılığıyla, büyük ve karmaşık kombinatoryal problemlerin bile küresel optimumuna yaklaşmayı hedefler.
Yöntemin mantığı
Karanlıkta dağlık bir arazide gezindiğinizi ve en yüksek zirveyi bulmaya çalıştığınızı hayal edin. Basit bir yerel-arama tırmanıcısı her zaman yokuş yukarı adım atar ve ulaştığı en yakın tepede takılıp kalır. Tabu Search, yakın zamanda ziyaret edilen yerlerin bir not defterini taşır ve geri dönmenin cazip görünse bile bu yerlere dönmeyi reddeder. Yakın hamleler hakkındaki bu zorunlu hafıza kaybı, aramayı çıkmaz sokaklardan çıkarıp keşfedilmemiş bölgelere yönlendirerek, düz bir yerel aramanın asla yapamayacağı kadar yüksek zeminler keşfetmesini sağlar.
Tarih
Tabu Search, ORSA Journal on Computing'de yer alan dönüm noktası niteliğindeki 1989 tarihli makalesinde Fred Glover tarafından tanıtıldı; burada yerel aramayı geçmiş hamlelerin belleğini kullanarak yönlendiren bir strateji olarak sunuldu. Temel fikirler, 1997'de Glover ve Laguna'nın Springer monografisinde pekiştirildi ve genişletildi; bu monografide, yöntemin merkezinde yer alan kanonik kısa süreli tabu listesi, aspirasyon kriterleri ve uzun süreli çeşitlendirme ve yoğunlaştırma stratejileri yer aldı. Tanıtılmasından bu yana Tabu Search, operasyon araştırması, çizelgeleme, lojistik ve kombinatoryal tasarım alanlarında yaygın olarak uygulanmıştır ve simüle tavlama ve genetik algoritmalarla birlikte standart bir referans meta-sezgisel yöntem olmaya devam etmektedir.
Ne zaman kullanılır?
Tabu Search, çözüm uzayı tam yöntemler için çok büyük olan ve problem yapısı anlamlı bir komşuluğun tanımlanmasına izin veren kombinatoryal ve ayrık optimizasyon problemleri için uygundur. Tipik uygulamalar arasında çizelgeleme, rotalama, atama ve sıralama problemleri bulunur. Özellikle arama manzarasının basit yöntemleri tuzağa düşüren çok sayıda yerel optimumu olduğu durumlarda etkilidir. Amaç fonksiyonunun türevlenebilir veya sürekli olmasını gerektirmez. Komşuluk tanımı ve tabu süresi, belirli probleme dikkatlice uyarlanmalıdır; kötü seçilmiş bir komşuluk veya çok kısa veya çok uzun bir süre performansı önemli ölçüde düşürebilir. Aramanın uzayı yeterince keşfetmesi için en az birkaç yüz — ve ideal olarak binden fazla — iterasyon gereklidir.
Sınırlar ve dikkat edilmesi gerekenler
- Performans, komşuluk tanımına ve tabu süresine duyarlıdır; kötü seçimler aramayı tuzağa düşürebilir veya tabu mekanizmasına rağmen döngüye girmesine neden olabilir.
- Arama uzayını yeterince keşfetmek için minimum bir iterasyon bütçesi gerektirir — tipik olarak 1.000'den fazla iterasyon; çok az iterasyonla sonuçlar basit yerel aramadan daha iyi değildir.
- Tabu listesi, tam çözümler yerine hamle özelliklerini saklar, bu nedenle aspirasyon kriteri, istemeden gerçekten iyi hamleleri engellememek için gereklidir.
- Tam çözücülerden farklı olarak, Tabu Search optimallik garantisi sunmaz ve başlangıç çözümü veya komşuluğu stokastik ise çalıştırmalar arasında sonuç kalitesi değişebilir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Tabu mekanizması aracılığıyla gradyan bilgisine gerek duymadan yerel optimumlardan kaçar.
- Kombinatoryal, karma türde ve hatta sürekli problemler için uygulanabilir — normalite veya herhangi bir dağılım özelliği varsaymaz.
- Çoklu zaman ölçeklerinde bellek içerir (kısa süreli tabu listesi, uzun süreli çeşitlendirme/yoğunlaştırma) ve arama uzayının ilkeli keşfine olanak tanır.
- Tam yöntemlere kıyasla büyük örneklerde nispeten mütevazı hesaplama bütçeleriyle genellikle yüksek kaliteli çözümler bulur.
Uygulama alanları
- İş-atölyesi ve akış-atölyesi çizelgeleme — iş tamamlama süresini veya gecikme süresini en aza indirmek için operasyon dizisini optimize etme.
- Araç rotalama — kapasite ve zaman penceresi kısıtlamalarına tabi olarak verimli teslimat rotaları bulma.
- Atama ve tesis yerleşimi — maliyeti en aza indirmek için görevleri kaynaklara atama veya tesisleri yerleştirme.
- Grafik renklendirme, ağ tasarımı ve telekomünikasyon — ayrık yapısal optimizasyon problemlerini çözme.
- Özellik seçimi ve hiperparametre arama — makine öğrenmesi işlem hatlarında ayrık yapılandırma uzaylarını keşfetme.
Nasıl çalışır?
Nasıl çalışır?
Arama, rastgele veya açgözlü bir sezgisel yöntemle oluşturulabilen başlangıç bir aday çözümden başlar. Tabu listesi boş, sabit uzunluklu bir kuyruk olarak ayarlanır ve şimdiye kadar bulunan en iyi çözüm kaydedilir. Komşuluk yapısı — mevcut çözümden bir adım uzaktaki çözümleri tanımlayan kural — belirli problem için anlamlı olacak şekilde tanımlanmalıdır.
Mevcut çözümden, tanımlanmış komşuluktaki tüm hamleler üretilir ve amaç fonksiyonuna göre değerlendirilir. Her hamle, bir dizideki iki öğeyi değiştirmek veya ikili bir değişkeni ters çevirmek gibi küçük bir pertürbasyona karşılık gelir. Komşuluk, anlamlı keşfe izin verecek kadar zengin ancak her iterasyonda yönetilebilir olacak kadar küçük olmalıdır.
Her aday hamle tabu listesine karşı test edilir. Hamle — veya onu karakterize eden özellik — listede görünüyorsa, tabu olarak sınıflandırılır ve yasaklanır, ancak bir aspirasyon kriterini karşılıyorsa: tipik olarak, sonuçta ortaya çıkan çözüm şimdiye kadar bulunan en iyi çözümden daha iyi olacaksa, tabu durumu geçersiz kılınır ve hamleye izin verilir. Bu aspirasyon mekanizması, algoritmanın döngü önleme disiplininden vazgeçmeden esneklik kazanmasını sağlar.
Tüm tabu olmayan hamleler (ve aspirasyon kriterini geçen herhangi bir tabu hamle) arasından, en iyi performans gösteren hamle seçilir ve yürütülür, hatta amaç değerini kötüleştirse bile. Bu bozulmayı kabul etme istekliliği, algoritmanın yerel optimumlardan kaçmasını sağlar; bu, basit tepe tırmanmasına kıyasla Tabu Search'ün tanımlayıcı özelliğidir.
Hamle yürütüldükten sonra, tabu listesi az önce yapılan hamlenin tersi (veya onu karakterize eden özelliği) eklenerek güncellenir ve liste doluysa en eski giriş kaldırılır, sabit uzunluğu — tabu süresi — korunur. Yeni çözüm kaydedilen en iyi çözümden daha iyiyse, en iyi çözüm güncellenir. İsteğe bağlı uzun süreli bellek yapıları, daha az ziyaret edilen bölgelere çeşitlendirmeyi veya umut verici bölgeler etrafında yoğunlaştırmayı yönlendirmek için çözüm sıklığını veya yakınlığını izleyebilir.
Algoritma, maksimum iterasyon sayısı, hedef amaç değeri veya iyileşme olmadan sabit sayıda iterasyon gibi bir durdurma kriteri karşılanana kadar devam eder. Tüm arama boyunca bulunan en iyi çözüm sonuç olarak döndürülür. Yeterli bir iterasyon bütçesi seçmek kritiktir — çok az iterasyon yeterli komşuluk keşfini engeller.
Sık yapılan hatalar
- Tabu süresini çok kısa ayarlamak, döngünün tekrarlanmasına izin vererek tabu mekanizmasının amacını boşa çıkarır; süre, problem boyutuna göre ayarlanmalıdır.
- Süreyi çok uzun ayarlamak, aramayı aşırı kısıtlar ve algoritmanın iyileştirmeler içerebilecek bölgeleri yeniden ziyaret etmesini engeller.
- Yaklaşık 1.000 iterasyondan az çalıştırmak, aramanın yeterince komşuluk keşfetmediği anlamına gelir — hesaplama sınırlıysa, daha az iterasyonla daha hızlı kullanışlı sonuçlar üretebilen simüle tavlamaya geri dönün.
- Çok dar bir komşuluk kullanmak (örneğin, karmaşık bir yapıda yalnızca tekli takas hamleleri) sığ bir aramaya yol açar; komşuluğun umut verici tüm çözüm uzayı bölgelerini bağlayacak kadar zengin olduğundan emin olun.
- Aspirasyon kriterini göz ardı etmek, o hamle tabu ise küresel optimuma giden yolu kalıcı olarak engelleyebilir; her zaman en azından standart en iyi çözüm geçersiz kılmasını uygulayın.
Sık sorulan sorular
Tabu Search, simüle tavlamadan nasıl farklıdır?
Her iki yöntem de yerel optimumlardan kaçmak için kötüleşen hamleleri kabul eder, ancak mekanizmalarında farklılık gösterirler. Simüle tavlama, soğutma sıcaklığı parametresi tarafından yönlendirilen kötü hamleleri olasılıksal olarak kabul eder. Tabu Search, açık hamle belleği tarafından yönlendirilen en iyi mevcut tabu olmayan hamleyi deterministik olarak kabul eder. Tabu Search, yapılandırılmış kombinatoryal problemler üzerinde genellikle daha etkilidir; simüle tavlama, sürekli veya sürekliye yakın manzaralara sahip problemler üzerinde ayarlanması daha kolay olabilir ve iterasyon bütçesinin küçük olduğu (yaklaşık 1.000 iterasyonun altında) durumlarda tercih edilir.
Tabu listesi ne kadar uzun olmalı?
Tabu süresi — bir hamlenin yasaklı kaldığı iterasyon sayısı — probleme bağlıdır. Yaygın olarak belirtilen bir başlangıç noktası, problem boyutunun kareköküyle orantılı bir süredir, ancak bu ampirik olarak ayarlanmalıdır. Çok kısa bir süre döngüye izin verir; çok uzun bir süre aramayı aşırı kısıtlar. Uyarlanabilir veya rastgeleleştirilmiş süre stratejileri bu seçime duyarlılığı azaltabilir.
Tabu Search, küresel optimumu bulmayı garanti eder mi?
Hayır. Tabu Search bir meta-sezgisel yöntemdir ve optimallik garantisi sunmaz. Yüksek kaliteli çözümleri verimli bir şekilde bulmayı hedefler, ancak sonuç komşuluk yapısına, süreye, iterasyon sayısına ve başlangıç çözümüne bağlıdır. Optimallik garantisi için, tam bir programlama gibi tam bir yöntem gereklidir, ancak tam yöntemler büyük örnekler için hesaplama açısından uygulanamayabilir.
Aspirasyon kriteri nedir ve neden gereklidir?
Aspirasyon kriteri, özel koşullar altında bir hamlenin tabu durumunu geçersiz kılan bir kuraldır. En yaygın kriter şudur: tabu bir hamlenin yürütülmesi, şimdiye kadar bulunan en iyi çözümden daha iyi bir çözüm üretecekse, tabu kısıtlaması kaldırılır ve hamleye izin verilir. Bu geçersiz kılma olmadan, tabu mekanizması, yol yakın zamanda ziyaret edilen bir hamleden geçiyorsa küresel optimuma giden yolu kalıcı olarak engelleyebilir.
İlgili yöntemler
Kaynaklar
Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Yayın kaynağını açKopyalandı.Glover, F. & Laguna, M. (1997). Tabu Search. Springer.
ISBN: 9780792349907Kopyalandı.