Tabu Arama algoritması, arama algoritmasının yerel bir minimumda takılıp kalmamasını sağlamak için, daha önce ziyaret edilen çözümleri bir "tabu listesi"nde saklar ve tekrar ziyaret edilmesini engeller. Bu, algoritmanın çözüm uzayında daha geniş bir arama yapabilmesine olanak sağlar. Ancak, bu yaklaşımın belirli bir zorluğu vardır. Tabu listesinin boyutunu (yani, kaç çözümün 'tabu' olarak kabul edileceğini) belirlemek zordur. Çok kısa bir liste, algoritmanın tekrar tekrar aynı çözümleri bulmasına ve dolayısıyla bir döngüye girmesine neden olabilir. Öte yandan, çok uzun bir liste, algoritmanın çözüm uzayındaki bazı potansiyel olarak iyi çözümleri kaçırmasına neden olabilir.

Reaktif Tabu Arama algoritması, bu sorunu çözmek için tabu listesinin boyutunu dinamik olarak ayarlar. Algoritma çalıştığı sürece, çözüm uzayındaki farklı bölgelerden alınan istatistiklere dayanarak tabu listesinin boyutunu artırır veya azaltır. Örneğin, eğer algoritma çözüm uzayının belirli bir bölgesinde çok fazla çözüm buluyorsa, tabu listesinin boyutu artırılır, böylece algoritmanın o bölgeyi tekrar ziyaret etmesi engellenir. Bu, algoritmanın yeni ve daha iyi çözümler bulabilmesi için çözüm uzayının diğer bölgelerine geçiş yapmasını sağlar.

Sonuç olarak, Reaktif Tabu Arama, çözüm uzayının dinamiklerine daha iyi uyum sağlamak ve daha etkili bir arama yapabilmek için tabu listesinin boyutunu adaptif olarak ayarlar.

N Kraliçe problemi, satranç tahtasında belirli bir sayıda kraliçenin birbirini tehdit etmeyecek şekilde nasıl yerleştirileceğini bulmak için bir bulmacadır. Bu, bir kraliçenin herhangi bir sayıda hücreye dikey, yatay veya çapraz hareket edebildiği satranç kurallarından kaynaklanmaktadır.

N Kraliçe problemi genellikle bir N x N satranç tahtası üzerinde ele alınır, burada N kraliçenin hiçbirini diğerinin tehdit etmeyecek şekilde yerleştirmek gerekmektedir. Bu problem, genellikle geriye dönük çözümleme, genetik algoritma veya yerel arama gibi optimizasyon veya arama algoritmalarının performansını test etmek için kullanılır.

Örneğin, 8 Kraliçe problemi, 8x8'lik bir satranç tahtası üzerine 8 kraliçeyi birbirlerini tehdit etmeyecek şekilde nasıl yerleştireceğinizi bulmayı içerir. Bu problemin birden çok çözümü vardır.

Bu tip problemler, çok sayıda potansiyel çözümü olan ve bu nedenle tüm çözüm alanını tarayarak çözüm bulmanın zor olduğu bir optimizasyon problemi türüdür. Bu nedenle, bu tür problemler genellikle heuristik veya metaheuristik algoritmaları kullanılarak çözülür. Bu algoritmalar, problemin çözümünü hızlı ve etkili bir şekilde bulmayı amaçlar.

import numpy as np
import random

class ReactiveTabuSearch:
    def __init__(self, n_queens):
        self.n_queens = n_queens
        self.tabu_list = np.zeros((n_queens, n_queens))
        self.state = list(np.random.randint(low=0, high=n_queens, size=n_queens))
        self.best_state = list(self.state)
        self.best_score = self.evaluate(self.best_state)
        self.TL_min = n_queens // 10
        self.TL_max = n_queens // 2
        self.frequency = np.zeros((n_queens, n_queens))

    def evaluate(self, state):
        score = 0
        for i in range(self.n_queens):
            for j in range(i+1, self.n_queens):
                if state[i] == state[j]:
                    score += 1
                elif state[i] - i == state[j] - j or state[i] + i == state[j] + j:
                    score += 1
        return score

    def neighbors(self, state):
        neighbors_list = []
        for i in range(self.n_queens):
            for j in range(self.n_queens):
                if state[i] != j:
                    new_state = list(state)
                    new_state[i] = j
                    neighbors_list.append(new_state)
        return neighbors_list

    def run(self, max_iter):
        for iter in range(max_iter):
            neighbors = self.neighbors(self.state)
            best_candidate = self.state
            best_score_candidate = self.best_score
            for neighbor in neighbors:
                if self.evaluate(neighbor) < best_score_candidate and self.tabu_list[self.state.index(neighbor)][neighbor.index(self.state)] == 0:
                    best_candidate = neighbor
                    best_score_candidate = self.evaluate(neighbor)
            self.state = best_candidate
            if best_score_candidate < self.best_score:
                self.best_score = best_score_candidate
                self.best_state = self.state
            self.tabu_list[self.state.index(best_candidate)][best_candidate.index(self.state)] += 1
            self.frequency[self.state.index(best_candidate)][best_candidate.index(self.state)] += 1
            if iter % self.n_queens == 0 and iter != 0:
                f_min = np.min(self.frequency)
                f_max = np.max(self.frequency)
                TL_average = (self.TL_min + self.TL_max) / 2
                if f_min > TL_average:
                    self.TL_min = TL_average
                    self.TL_max = 2 * TL_average
                elif f_max <= TL_average:
                    self.TL_max = TL_average
            self.tabu_list[self.tabu_list > self.TL_min] -= 1
        return self.best_state

algorithm = ReactiveTabuSearch(8)
print(algorithm.run(500))

Bu kod örneğinde, bir ReactiveTabuSearch sınıfı oluşturduk. Sınıfın yapıcı metodu (__init__), başlangıç çözümünü ve en iyi çözümü belirler ve bir tabu listesi ve bir frekans matrisi oluşturur. evaluate fonksiyonu, bir durumun ne kadar iyi olduğunu (bu durumda, aynı çizgide kaç tane kral olduğunu) değerlendirir. neighbors fonksiyonu, verilen durumdan erişilebilen tüm komşu durumları üretir. run fonksiyonu, algoritmayı belirtilen sayıda iterasyon için çalıştırır, her iterasyonda en iyi komşuyu seçer, durumu ve en iyi çözümü günceller ve tabu listesini ve frekans matrisini günceller.

Lütfen bu kodun tamamen anlaşılmadığı takdirde hatalı çıktılar verebileceğini unutmayın. Yani, bu kodu çalıştırmadan önce gerekli bilgiye sahip olduğunuzdan emin olun. Ayrıca, bu örnek biraz daha karmaşık bir örnektir ve bu nedenle Python'da ve tabu arama algoritmalarında bir miktar deneyim gerektirir.

kodda kullanılan birkaç önemli kavramı aşağıda açıklıyorum:

n_queens: Bu, tahtadaki kraliçe sayısını belirler. Bu örnekte, klasik 8 kraliçe problemi çözülüyor.

Tabu Listesi: Tabu arama algoritmasının temel bileşenlerinden biridir. Yeni bir çözüm üretildiğinde, geçmişteki birkaç çözüm "tabu" olarak işaretlenir, yani algoritma belirli bir süre boyunca bu çözümlere geri dönmeyecek şekilde tasarlanmıştır. Bu, algoritmanın yerel minimumlara takılıp kalmamasını sağlar.

State (Durum): Bu, algoritmanın o anda bulunduğu çözümü temsil eder. Bir durum, her kraliçenin satırdaki konumunu belirleyen bir liste olarak temsil edilir.

Neighbor (Komşu): Bu, algoritmanın o anki durumundan bir hamleyle ulaşabileceği durumları temsil eder. Yani, bir kraliçenin pozisyonunu değiştirerek elde edilen yeni durumlar komşu olarak adlandırılır.

Evaluate (Değerlendirme): Bu fonksiyon, bir durumun ne kadar iyi olduğunu değerlendirir. Bu örnekte, değerlendirme fonksiyonu bir durumdaki çakışan kraliçe çiftlerinin sayısını hesaplar. İdeal çözüm, hiçbir kraliçenin bir diğerine saldıramadığı bir durumdur, bu nedenle bu durumun değerlendirmesi 0 olacaktır.

Run (Çalıştır): Bu, algoritmayı belirli sayıda adım (veya iterasyon) için çalıştırır. Her adımda, algoritma en iyi komşuyu bulur (en düşük değerlendirme skoruna sahip olanı), durumunu bu en iyi komşuya günceller, ve bu durumu ve ilgili hareketi tabu listesine ekler.

Frequency (Frekans): Bu matris, algoritmanın belirli bir hareketi kaç kere yaptığını takip eder. Bu bilgi, tabu listesinin boyutunu dinamik olarak ayarlamak için kullanılır (bu nedenle algoritmanın adı "Reaktif" Tabu Arama'dır).

Bu açıklamalar, kodun genel akışını ve tabu arama algoritmasının temel kavramlarını anlamanıza yardımcı olmalıdır. Ancak, her zaman olduğu gibi, bu tür bir algoritmayı tam olarak anlamak ve uygulamak için genellikle biraz deneyim ve algoritma üzerinde uygulamalı çalışma gereklidir. Bu nedenle, bu algoritmayı kendi başınıza uygulamayı denemekten çekinmeyin!