Tabu Arama Algoritması

Tabu Arama (TA) algoritması ilk defa F. Glover tarafından insan hafızasının çalışmasından esinlenilerek önerilmiş bir yerel arama yöntemidir. Tabu araştırması temel olarak belirli bir problem üzerine elde edilen ilk çözüm etrafındaki komşuluklar oluşturmaktır. Komşuluk mekanizması ele alınarak birbirini izleyen seçilmiş çözümlerden daha iyi olanı Tabu Listesi olarak atanır.

Tabu arama algoritmasında tabu listesi olarak oluşturulan ilk aday çözüm ve değişken komşu çözüm sayısı, bir tür tabulaştırma görevi yapmaktadır. Kötü sonuç veren bölgelerde daha fazla işlem yapılmaması (bu elemanların komşu sayılarının azaltılması), istenen çözüme daha az hesaplamayla, dolayısıyla daha hızlı ulaşmayla sağlamaktadır. iyi sonuç veren parametrelerin bir sonraki iterasyonda komşu sayıları artmakta, böylece algoritmanın verimliliği de artmış olmaktadır.

Tabu listesinin en önemli özelliklerinden birisi, mevcut tabu listesinin aday komşu çözümler ile karşılaştırıldıktan sonra bir sıralama ve karşılaştırma işlemi yaparak kendisini yenileyebilmesidir. Bu amaçla, geliştirilen algoritmada, önceki döngüler de elde edilen çözümlerin listesinin tutulduğu bir tabu listesi oluşturulmuştur. Eğer bir komşu çözüm adayı, tabu listesinde yer alan bir çözümle aynıysa (bu durumda aday çözüm, zaten daha önce denenmiştir), bu çözüm değerlendirme dışı bırakılmaktadır. Tabu listesi oluşturulurken her döngüdeki en iyi çözüm listeye alınmakta, listenin dolduğu durumda listedeki ilk kayıtlar (başlangıçtaki çözümler) listeden atılıp, son döngüler de elde edilen çözümler listeye alınmaktadır.

Tabu Listesi ilk en iyi çözüm kümesinin oluşturularak hafızaya alınma yöntemi ile oluşturulur. Tabu listesi oluşturmanın önemli bir kuralı da giriş değerleri oluşturulurken çeşitli filtrezizasyon işlemlerinden geçirilmesidir

Oluşturulan Tabu listesinin en temel özelliği yeni çözüm adaylarını değerlendirmeye alarak dairesel bir döngü içerisinde yol alarak her yeni döngüden sonra yeni özellikler kazanmasıdır.

Tabu listesinin yeni elde edilen çözümler ile liste uzunluğu artacak ve çözüm aramada büyük bir etki yaparak kısa çözümlerin daireselliği sayesinde nesnel bir çözüm arama tekniği olduğunu gösterecektir. Burada istenilen durum çözüm adaylarının mevcut bu döngüsü ile Tabu listesinin geliştirilmesidir. Tabu listesine dahil edilen yeni çözümler oluşturulurken eğer elde edilen çözüm tabu listesindeki çözümlerden daha iyi ise elde edilen çözüm tabu listesine eklenebilir. Bunun tersi durumunda, yani daha kötü bir çözüm ise tabu listesine eklenmeyecek ve doğal olarak belirli bir bellek kaplamayacaktır. En iyi çözüm bulunana kadar bu işlemler mevcut döngü ile devam edecektir.

TA ana olarak basit tepe tırmanma (BTT) yönteminin zaaflarını gidermek için düşünülmüştür. BTT eldeki aday çözüme, bir komşuluk işleci uygulayarak, yeni adaylar üretir. Yeni adaylar bir değerlendirmeye tabi tutulur. Değerlendirme çözümün sonuca yakınlığını ölçer. Yeni adaylar ile eldeki eski aday içerisinden çözüme en yakın olan eskinin yerine geçer. BTT bu haliyle kısır bir döngüye sebep olabilir. Komşuluklar kapsamında birbirine eşit değerdeki iki yada daha fazla komşu arasında BTT takılıp kalabilir. Arama yapılan alanın özellikleri yada BTT yönteminin iyi seçilmemesi, herhangi bir denetim mekanizması kullanılmadan yapılan aramayı yerel en iyi noktalara götürebilir. Fakat gerçek hayattaki problemler yerel en iyilerin bol olduğu, fakat global iyinin az, hatta tek olabildiği problemlerdir. Kısacası kısır döngü kaçınılmazdır. Tabu arama yöntemi kısır döngüden kurtulmak için hafıza kullanılmasını, hatırlamayı önerir. Daha önce ziyaret edilmiş ya da herhangi bir nedenle ziyaret edilmesi istenilmeyen aday çözümlerle ilgili özellikler, tabu listesi adı verilen, kısa dönem hafızaya benzer bir yapıda tutulur. Yöntem bu listedeki hamlelerin belirli bir süre yapılmasını yasaklar. Böylece arama yerel bir en iyi noktadan kurtularak asıl sonuca yakınsayabilir. Bu temel altyapının yanısıra, tabu arama yöntemlerinde aramayı belirli bir noktaya yönlendirebilecek uzun dönem hafıza yapıları da kullanılmıştır.

 

Kaynak:

Doç.Dr. Bilal ALATAŞ

Optimizasyon Teknikleri

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir