Tabu araması - Tabu search

Tabu araması , matematiksel optimizasyon için kullanılan yerel arama yöntemlerini kullanan bir meta-sezgisel arama yöntemidir . 1986'da Fred W. Glover tarafından yaratıldı ve 1989'da resmileştirildi.

Yerel (mahalle) aramalar, bir soruna potansiyel bir çözüm getirir ve iyileştirilmiş bir çözüm bulma umuduyla yakın komşularını (yani, çok az küçük ayrıntı dışında benzer çözümler) kontrol eder. Yerel arama yöntemleri, optimal olmayan bölgelerde veya birçok çözümün eşit derecede uygun olduğu platolarda sıkışıp kalma eğilimindedir.

Tabu araması, temel kuralını gevşeterek yerel aramanın performansını artırır. Birincisi, her adımda, iyileştirici bir hareket yoksa kötüleşen hamleler kabul edilebilir (arama sıkı bir yerel minimumda kaldığında olduğu gibi ). Ek olarak, aramanın daha önce ziyaret edilen çözümlere geri dönmesini engellemek için yasaklar (bundan böyle tabu terimi ) getirilir.

Tabu arama uygulaması, ziyaret edilen çözümleri veya kullanıcı tarafından sağlanan kural kümelerini tanımlayan bellek yapılarını kullanır. Potansiyel bir çözüm belirli bir kısa dönem içinde daha önce ziyaret edilmişse veya bir kuralı ihlal etmişse , algoritmanın bu olasılığı tekrar tekrar düşünmemesi için " tabu " (yasak) olarak işaretlenir .

Arka fon

Kelimesi tabu gelen Tonga çünkü onlar kutsaldır dokunulmaz olamaz şeyleri belirtmek için kelime.

Tabu arama (TS), kombinatoryal optimizasyon problemlerini (optimal sıralama ve seçenek seçiminin istendiği problemler) çözmek için kullanılabilen bir meta-sezgisel algoritmadır .

TS'nin mevcut uygulamaları, kaynak planlama , telekomünikasyon, VLSI tasarımı , finansal analiz, çizelgeleme, alan planlama, enerji dağıtımı, moleküler mühendislik, lojistik, model sınıflandırması , esnek üretim, atık yönetimi, maden arama, biyomedikal analiz, çevre koruma ve başkalarının puanları. Son yıllarda, çok çeşitli alanlardaki dergiler, etkili bir şekilde ele alınabilecek sorunların sınırını genişletmede tabu arama yoluyla başarıları belgeleyen öğretici makaleler ve hesaplama çalışmaları yayınladılar - kalitesi genellikle daha önce uygulanan yöntemlerle elde edilenleri önemli ölçüde aşan çözümler ortaya koydu. Pratik uygulamalardan elde edilen kazanımların özet tanımlarını içeren kapsamlı bir uygulama listesi, Son TS geliştirmelerinde bulunabilir ve uygulamalar da Tabu Arama Vinyetlerinde bulunabilir .

Temel açıklama

Tabu araması, bazı durdurma kriterleri (genellikle bir deneme limiti veya bir puan eşiği) karşılanana kadar , bir potansiyel çözümden mahalledeki geliştirilmiş bir çözüme yinelemeli olarak geçmek için yerel veya komşu bir arama prosedürü kullanır . Yerel arama prosedürleri genellikle düşük puan alan veya puanların plato olduğu alanlarda sıkışıp kalır. Bu tuzaklardan kaçınmak ve arama alanının diğer yerel arama prosedürleri tarafından keşfedilmeden bırakılan bölgelerini keşfetmek için , tabu arama, arama ilerledikçe her bir çözümün çevresini dikkatlice araştırır. Yeni mahalleye kabul edilen çözümler , bellek yapıları kullanılarak belirlenir. İteratif mevcut çözeltiden hareket ettirerek bu bellek yapıları, ara ilerledikçe kullanılarak geliştirilmiş bir çözeltiye olarak .

Her ikisi de olası yokuş aşağı hareketleri içerdiğinden, Tabu Search'ün Simüle tavlama ile birkaç benzerliği vardır . Aslında, Simüle tavlama , TS'nin özel bir biçimi olarak görülebilir, burada "dereceli görev süresi" kullanılır, yani hareket, belirli bir olasılıkla tabu olur.

Bu bellek yapıları , arama tarafından keşfedilecek mahalleye hangi çözümlerin kabul edileceğini filtrelemek için kullanılan tabu listesi, bir dizi kural ve yasaklı çözümleri oluşturur . En basit şekliyle, bir tabu listesi, yakın geçmişte ziyaret edilen çözümlerin kısa vadeli bir kümesidir ( yinelemelerden daha kısa bir süre önce, depolanacak önceki çözümlerin sayısı - aynı zamanda tabu kullanım hakkı olarak da adlandırılır). Daha yaygın olarak, bir tabu listesi, bir çözümden diğerine geçme sürecinde değişen çözümlerden oluşur. Tanımlama kolaylığı açısından, kodlanacak ve bu tür niteliklerle temsil edilecek bir "çözümü" anlamak uygundur.

Bellek türleri

Tabu aramada kullanılan bellek yapıları kabaca üç kategoriye ayrılabilir:

  • Kısa vadeli: Yakın zamanda düşünülen çözümlerin listesi. Tabu listesinde olası bir çözüm görünürse, sona erme noktasına ulaşana kadar tekrar ziyaret edilemez.
  • Orta vadeli: Aramayı, arama alanının gelecek vaat eden alanlarına yönlendirmeyi amaçlayan yoğunlaştırma kuralları.
  • Uzun vadeli: Aramayı yeni bölgelere yönlendiren çeşitlendirme kuralları (yani, arama bir platoda veya yetersiz bir çıkmazda sıkışıp kaldığında sıfırlamalarla ilgili).

Kısa vadeli, orta vadeli ve uzun vadeli anılar pratikte örtüşebilir. Bu kategoriler içinde bellek, yapılan değişikliklerin sıklığı ve etkisi gibi ölçümlerle daha da farklılaştırılabilir. Orta vadeli bellek yapısının bir örneği, belirli öznitelikleri içeren çözümleri (ör., Belirli değişkenler için istenmeyen veya istenen değerleri içeren çözümler) veya belirli hareketleri engelleyen veya indükleyen bir bellek yapısını (ör. Frekans belleğine dayalı olarak) yasaklayan veya teşvik eden bir yapıdır. geçmişte bulunan çekici olmayan veya çekici çözümlerle ortak özellikleri paylaşan çözümlere uygulanır). Kısa süreli bellekte, yakın zamanda ziyaret edilen çözümlerde seçilen öznitelikler "tabu-aktif" olarak etiketlenir. Tabu aktif öğeler içeren çözümler yasaklanmıştır. Bir çözümün tabu durumunu geçersiz kılan ve böylece izin verilen sete başka türlü hariç tutulan çözümü dahil eden (çözümün bir kalite veya çeşitlilik ölçüsüne göre "yeterince iyi" olması koşuluyla) aspirasyon kriterleri kullanılır. Basit ve yaygın olarak kullanılan bir aspirasyon kriteri, şu anda bilinen en iyi çözümden daha iyi çözümlere izin vermektir.


Tek başına kısa süreli bellek, geleneksel yerel arama yöntemleriyle bulunanlardan daha üstün çözümler elde etmek için yeterli olabilir, ancak orta ve uzun vadeli yapılar genellikle daha zor problemleri çözmek için gereklidir. Tabu araması genellikle Simüle edilmiş tavlama , genetik algoritmalar , Karınca kolonisi optimizasyon algoritmaları , Reaktif arama optimizasyonu, Kılavuzlu Yerel Arama veya açgözlü rastgele uyarlamalı arama gibi diğer meta-sezgisel yöntemlerle karşılaştırılır . Ek olarak, tabu araması bazen hibrit yöntemler oluşturmak için diğer meta-sezgisellerle birleştirilir. En yaygın tabu arama karması, tabu arama ile ortak kökleri olan ve genellikle büyük doğrusal olmayan optimizasyon problemlerinin çözümünde kullanılan popülasyon tabanlı prosedürler sınıfı olan Dağılım Arama ile TS'nin birleştirilmesiyle ortaya çıkar.

Sözde kod

Aşağıdaki sözde kod , yukarıda açıklandığı gibi tabu arama algoritmasının basitleştirilmiş bir versiyonunu sunar. Bu gerçeklenim temel bir kısa süreli belleğe sahiptir, ancak orta ya da uzun süreli bellek yapıları içermez. "Uygunluk" terimi, matematiksel optimizasyon için nesnel bir fonksiyonda somutlaştırıldığı şekliyle aday çözümün bir değerlendirmesini ifade eder. 

sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(bestCandidate)
    bestCandidate ← sNeighborhood[0]
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
            bestCandidate ← sCandidate
        end
    end
    if (fitness(bestCandidate) > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest

1-4 satırları, sırasıyla bir başlangıç ​​çözümü (muhtemelen rastgele seçilir) oluşturan, bu ilk çözümü bugüne kadar görülen en iyi çözüm olarak ayarlayan ve bu ilk çözümle bir tabu listesi başlatan bazı başlangıç ​​kurulumlarını temsil eder. Bu örnekte, tabu listesi, ziyaret edilen durumların unsurlarının bir kaydını içerecek olan kısa süreli bir hafıza yapısıdır.

Çekirdek algoritmik döngü 5. satırda başlar. Bu döngü, kullanıcı tanımlı bir durdurma koşulu karşılanana kadar en uygun çözümü aramaya devam edecektir (bu tür koşulların iki örneği basit bir zaman sınırı veya uygunluk skorunda bir eşiktir). Komşu çözümler 9. satırdaki tabu öğeleri için kontrol edilir. Ek olarak, algoritma mahallede tabu olmayan en iyi çözümü izler.

Uygunluk işlevi genellikle bir puan döndüren matematiksel bir işlevdir veya aspirasyon kriterleri karşılanır - örneğin, yeni bir arama alanı bulunduğunda bir aspirasyon kriteri düşünülebilir). En iyi yerel aday mevcut en iyiden daha yüksek bir uygunluk değerine sahipse (satır 13), yeni en iyi olarak belirlenir (satır 14). Yerel en iyi aday her zaman tabu listesine eklenir (satır 16) ve tabu listesi doluysa (satır 17), bazı öğelerin süresinin dolmasına izin verilir (satır 18). Genellikle, elemanlar eklendikleri sırayla listeden çıkarlar. Prosedür, yerel optimalden kaçmak için en iyi yerel adayı seçecektir (sBest'ten daha kötü uygunluğa sahip olmasına rağmen).

Bu işlem, kullanıcının belirlediği durdurma kriteri karşılanıncaya kadar devam eder, bu noktada arama işlemi sırasında görülen en iyi çözüm döndürülür (satır 21).

Örnek: seyyar satıcı sorunu

Seyyar satıcı problemi (TSP) bazen tabu arama işlevselliğini göstermek için kullanılır. Bu problem basit bir soruyu gündeme getiriyor - şehirlerin bir listesi verildiğinde, her şehri ziyaret eden en kısa rota nedir? Örneğin, A şehri ve B şehri yan yana, C şehri daha uzaktaysa, C şehrini ziyaret etmeden önce A ve B şehirleri ardı ardına ziyaret edilirse, katedilen toplam mesafe daha kısa olacaktır. olan NP-zor , (örneğin, yerel aramalar gibi) sezgisel tabanlı yaklaşım yöntemleri-yakın uygun çözümleri oluşturulması için yararlıdır. İyi TSP çözümleri elde etmek için grafik yapısından yararlanmak önemlidir. Problem yapısından yararlanmanın değeri, meta-sezgisel yöntemlerde yinelenen bir temadır ve tabu araması buna çok uygundur. Ejeksiyon zinciri yöntemleri adı verilen tabu arama ile ilişkili bir strateji sınıfı, yüksek kaliteli TSP çözümlerini verimli bir şekilde elde etmeyi mümkün kılmıştır.

Öte yandan, seyyar satıcı problemine tatmin edici bir çözüm bulmak için basit bir tabu araştırması kullanılabilir (yani, grafik yapısından yararlanılarak elde edilen yüksek kalitede olmasa da, bir yeterlilik kriterini karşılayan bir çözüm). Arama, rastgele veya bir tür en yakın komşu algoritmasına göre oluşturulabilen bir ilk çözümle başlar . Yeni çözümler üretmek için, olası bir çözümde iki şehrin ziyaret edilmesi sırası değiştirilir. Tüm şehirler arasındaki toplam seyahat mesafesi, bir çözümün diğerine kıyasla ne kadar ideal olduğuna karar vermek için kullanılır. Döngüleri önlemek - yani belirli bir çözüm kümesini tekrar tekrar ziyaret etmek - ve yerel optimada takılıp kalmamak için, çözüm mahallesine kabul edilirse tabu listesine bir çözüm eklenir .

Rasgele sayıda yineleme gibi bazı durdurma kriterleri karşılanana kadar yeni çözümler yaratılır. Basit tabu araması durduğunda, yürütme sırasında bulunan en iyi çözümü döndürür.

Referanslar

Dış bağlantılar