Jump to content
  • entries
    55
  • comments
    2
  • views
    59,207

Tabu Arama (Tabu Search)


Doğuhan ELMA

130 views

Tabu Arama (Tabu Search), Fred Glover tarafından 1980'lerin başında geliştirilen, yerel optimumlardan kaçınmayı amaçlayan ve global optimuma ulaşmayı hedefleyen bir metaheuristik arama algoritmasıdır. Bu, özellikle NP-zor problemler gibi karmaşık ve zor optimizasyon problemlerini çözme yeteneği ile bilinir.

Algoritma, çözüm uzayındaki bir başlangıç noktasından hareket eder ve her bir iterasyonda, mevcut çözümün etrafındaki 'mahalle'deki (benzer çözümler kümesi) en iyi çözümü bulmaya çalışır. 

Farklılık, tabu aramanın yerel optimumlarda takılıp kalmamasıdır. Bunun yerine, hareket geçmişi (genellikle bir tabu listesi olarak adlandırılır) üzerinde bir kısıtlama getirerek, daha önce ziyaret edilen çözümleri geçici olarak yasaklar. Bu, algoritmanın daha önce keşfedilmemiş çözüm alanlarını keşfetmesine ve global bir optimuma ulaşma olasılığını arttırmasına olanak sağlar.

Tabu listesi, en son yapılan hareketlerin bir listesini tutar ve bu hareketlerin tersini yasaklar. Bu, algoritmanın en son yapılan hareketleri geri almasını ve potansiyel olarak bir yerel optima döngüsüne girme olasılığını azaltır. Aynı zamanda, belirli bir süre sonunda tabu listesinden hareketler kaldırılabilir, bu da algoritmanın uzun vadeli hafıza yeteneği kazanmasına olanak sağlar.

Sonuç olarak, Tabu Arama genellikle karmaşık optimizasyon problemlerinin çözümünde etkili bir yöntem olarak kabul edilir. Bununla birlikte, algoritmanın performansı büyük ölçüde problem, parametre ayarları ve kullanılan heuristiklere bağlıdır.

def tabu_arama(baslangic_cozumu, komsuluk_fonk, amac_fonk, tabu_liste_boyut, max_iterasyon):
    """
    Tabu Arama algoritmasını gerçekleştirir.

    Parametreler:
    baslangic_cozumu: Aramanın başlangıç çözümü.
    komsuluk_fonk: Bir çözüm verildiğinde, komsuluk (yani benzer çözümler kümesi) hesaplar.
    amac_fonk: Maksimize etmek için hedef fonksiyon.
    tabu_liste_boyut: Tabu listesinin maksimum boyutu.
    max_iterasyon: Gerçekleştirilecek maksimum iterasyon sayısı.

    Döndürür:
    Bulunan en iyi çözüm ve onun hedef değeri.
    """

    # Çözümü başlat
    simdiki_cozum = baslangic_cozumu
    simdiki_hedef = amac_fonk(simdiki_cozum)

    # En iyi çözümü başlat
    en_iyi_cozum = simdiki_cozum
    en_iyi_hedef = simdiki_hedef

    # Tabu listesini başlat
    tabu_listesi = []

    # İterasyonları gerçekleştir
    for _ in range(max_iterasyon):
        # Tabu listesinde olmayan ve maksimum hedef değerine sahip bir komsuyu bul
        komsuluk = komsuluk_fonk(simdiki_cozum)
        komsuluk = [k for k in komsuluk if k not in tabu_listesi]
        komsuluk_hedefleri = [amac_fonk(k) for k in komsuluk]

        # Şimdiki çözümü güncelle
        simdiki_cozum = komsuluk[komsuluk_hedefleri.index(max(komsuluk_hedefleri))]
        simdiki_hedef = max(komsuluk_hedefleri)

        # En iyi çözümü güncelle
        if simdiki_hedef > en_iyi_hedef:
            en_iyi_cozum = simdiki_cozum
            en_iyi_hedef = simdiki_hedef

        # Tabu listesini güncelle
        tabu_listesi.append(simdiki_cozum)
        if len(tabu_listesi) > tabu_liste_boyut:
            tabu_listesi.pop(0)

    # Bulunan en iyi çözüm ve onun hedef değerini döndür
    return en_iyi_cozum, en_iyi_hedef
  
def amac_fonk(c):
    return c

def komsuluk_fonk(c):
    return [c - 1, c + 1]

baslangic_cozumu = 0
tabu_liste_boyut = 5
max_iterasyon = 10

cozum, hedef = tabu_arama(baslangic_cozumu, komsuluk_fonk, amac_fonk, tabu_liste_boyut, max_iterasyon)

print("Bulunan en iyi çözüm:", cozum)
print("Onun hedef değeri:", hedef)

Bu kodu çalıştırdığınızda, en iyi çözümün 10 olduğunu ve hedef değerinin de 10 olduğunu göreceksiniz. Tabu arama algoritması, her bir adımda mevcut çözümü bir artırarak ve bir önceki çözümü tabu listesine ekleyerek, en büyük sayıyı bulur.

Bu kod örneği, genel bir Tabu Arama uygulamasını temsil eder ve şu işlevlere sahip olmalıdır:

baslangic_cozumu: Aramanın başlangıç noktası, genellikle rastgele bir çözüm.

komsuluk_fonk: Verilen bir çözümün komsuluklarını (yani, benzer çözümler kümesini) hesaplar.

amac_fonk: Verilen bir çözümün hedef fonksiyon değerini hesaplar. Bu algoritma, hedef fonksiyonu maksimize etmeye çalışır.

tabu_liste_boyut: Tabu listesinin maksimum boyutunu belirler. Listeye yeni bir çözüm eklenirken, liste bu boyutu aşıyorsa, en eski çözüm (liste başındaki çözüm) çıkarılır.

max_iterasyon: Algoritmanın gerçekleştireceği maksimum iterasyon sayısını belirler.

Bu kod, genellikle daha karmaşık ve belirli bir probleme uyum sağlamak için özelleştirilecek genel bir iskelet olacaktır. Herhangi bir gerçek uygulamada, başlangıç çözümü, komsuluk fonksiyonu, hedef fonksiyonu ve tabu listesinin boyutu, algoritmanın performansını ve sonuçlarını büyük ölçüde etkileyen problem özgü parametreler olacaktır.

İterasyon sayısı arttıkça, özellikle problemi çözme durumu karmaşık olduğunda, sonuçtaki değerler değişebilir. Tabu Arama algoritması, bir çözüm alanında arama yapar ve her iterasyonda çözümü iyileştirmeye çalışır. Ancak, belirli bir sayıda iterasyondan sonra, daha fazla iterasyon genellikle daha iyi sonuçlar üretmez.

Bunun nedeni, algoritmanın belirli bir noktadan sonra genellikle yerel optimuma ulaşması ve daha fazla iterasyonun bu optimumu aşmasına yardımcı olmamasıdır. Tabu Arama algoritmasının amacı, yerel optimumlara takılmadan global optimuma ulaşmaktır, ancak bu her zaman garantili değildir.

Iterasyon sayısının değeri, problemi çözme yeteneği üzerinde önemli bir etkiye sahiptir. Çok az iterasyon, algoritmanın optimum çözüme ulaşmasını engelleyebilir. Öte yandan, çok fazla iterasyon, gereksiz hesaplama zamanı ve kaynak kullanımına yol açabilir. İdeal iterasyon sayısını belirlemek genellikle bir dizi deneme ve hata gerektirir.

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...