Wikiszótár

tabu keresés

Magyar

Kiejtés

  • IPA: [ ˈtɒbukɛrɛʃeːʃ]

Főnév

tabu keresés

  1. (informatika, algoritmusok) A tabu keresés egy heurisztikus optimalizációs algoritmus, amelyet Fred Glover vezetett be 1986-ban. Az algoritmus célja, hogy lokális keresési módszerek korlátait legyőzze, például a lokális optimumokban való elakadást. Ennek érdekében tabulistát használ, amely megakadályozza, hogy az algoritmus visszatérjen korábban meglátogatott vagy nem kívánatos megoldásokhoz.


Algoritmus működése

  1. Inicializáció:
    • Kezdeti megoldás ((s_0)) kiválasztása.
    • Egy „tabulista” létrehozása, amely korlátozza a bizonyos megoldásokhoz való visszatérést.
    • Paraméterek inicializálása, például a tabulista mérete és a maximális iterációk száma.
  2. Szomszédos megoldások generálása:
    • A jelenlegi megoldásból ((s)) származtatott szomszédos megoldások halmazát ((N(s))) hozd létre.
  3. Legjobb szomszéd kiválasztása:
    • A szomszédos megoldások közül válaszd ki a legjobbat, figyelembe véve a tabulista korlátozásait.
    • Ha a megoldás tabu, de megfelel egy törekvési kritériumnak, engedélyezd.
  4. Frissítés:
    • Frissítsd az aktuális megoldást és a tabulistát.
    • A tabulista új megoldást ad hozzá, és eltávolítja a legrégebbi elemet, ha a mérete meghaladja a megengedettet.
  5. Megállási feltétel:
    • Az algoritmus addig iterál, amíg el nem éri a maximális iterációk számát vagy egy elfogadható megoldást.


Tabulista

A tabulista a már meglátogatott megoldásokat vagy bizonyos jellemzőiket (pl. lépéseket) tárolja. Célja, hogy: - Megakadályozza a ciklusokat. - Segítsen elkerülni a lokális optimumokat.


Algoritmus Pszeudokódja

TabuSearch(s_0, max_iter, tabu_size):
    s = s_0                # Inicializálás kezdő megoldással
    best_solution = s      # Kezdetben a legjobb megoldás a kezdő
    tabu_list = []         # Tabulista inicializálása

    for i = 1 to max_iter:
        neighbors = GenerateNeighbors(s)
        best_neighbor = SelectBestNeighbor(neighbors, tabu_list)

        if Fitness(best_neighbor) < Fitness(best_solution):
            best_solution = best_neighbor

        UpdateTabuList(tabu_list, s, tabu_size)
        s = best_neighbor

    return best_solution

Példa

Utazóügynök probléma (TSP)

Adott városok és az közöttük lévő távolságok. Találj egy minimális távolságú körutat.


Python implementáció

import random

def calculate_distance(route, distances):
    """Teljes távolság kiszámítása egy adott útvonalhoz."""
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distances[route[i]][route[i + 1]]
    total_distance += distances[route[-1]][route[0]]  # Körút
    return total_distance

def generate_neighbors(route):
    """Szomszédos megoldások generálása az útvonal cseréjével."""
    neighbors = []
    for i in range(len(route)):
        for j in range(i + 1, len(route)):
            neighbor = route[:]
            neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
            neighbors.append(neighbor)
    return neighbors

def tabu_search(distances, initial_route, max_iter, tabu_size):
    current_route = initial_route[:]
    best_route = initial_route[:]
    tabu_list = []

    for _ in range(max_iter):
        neighbors = generate_neighbors(current_route)
        best_neighbor = None
        best_distance = float('inf')

        for neighbor in neighbors:
            if neighbor not in tabu_list:
                distance = calculate_distance(neighbor, distances)
                if distance < best_distance:
                    best_neighbor = neighbor
                    best_distance = distance

        if best_neighbor is None:
            break

        if best_distance < calculate_distance(best_route, distances):
            best_route = best_neighbor

        tabu_list.append(best_neighbor)
        if len(tabu_list) > tabu_size:
            tabu_list.pop(0)

        current_route = best_neighbor

    return best_route, calculate_distance(best_route, distances)

# Példa adatok
distances = {
    0: {1: 10, 2: 15, 3: 20},
    1: {0: 10, 2: 35, 3: 25},
    2: {0: 15, 1: 35, 3: 30},
    3: {0: 20, 1: 25, 2: 30}
}
initial_route = [0, 1, 2, 3]

# Tabu keresés futtatása
best_route, best_distance = tabu_search(distances, initial_route, max_iter=100, tabu_size=5)
print(f"Legjobb útvonal: {best_route}, Távolság: {best_distance}")

Kimenet: 

Legjobb útvonal: [0, 1, 3, 2], Távolság: 80

C++ implementáció

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int calculate_distance(const vector<int>& route, const vector<vector<int>>& distances) {
    int total_distance = 0;
    for (size_t i = 0; i < route.size() - 1; ++i) {
        total_distance += distances[route[i]][route[i + 1]];
    }
    total_distance += distances[route.back()][route[0]];
    return total_distance;
}

vector<vector<int>> generate_neighbors(const vector<int>& route) {
    vector<vector<int>> neighbors;
    for (size_t i = 0; i < route.size(); ++i) {
        for (size_t j = i + 1; j < route.size(); ++j) {
            vector<int> neighbor = route;
            swap(neighbor[i], neighbor[j]);
            neighbors.push_back(neighbor);
        }
    }
    return neighbors;
}

pair<vector<int>, int> tabu_search(const vector<vector<int>>& distances, vector<int> initial_route, int max_iter, int tabu_size) {
    vector<int> current_route = initial_route;
    vector<int> best_route = initial_route;
    vector<vector<int>> tabu_list;

    for (int iter = 0; iter < max_iter; ++iter) {
        auto neighbors = generate_neighbors(current_route);
        vector<int> best_neighbor;
        int best_distance = INT_MAX;

        for (const auto& neighbor : neighbors) {
            if (find(tabu_list.begin(), tabu_list.end(), neighbor) == tabu_list.end()) {
                int distance = calculate_distance(neighbor, distances);
                if (distance < best_distance) {
                    best_neighbor = neighbor;
                    best_distance = distance;
                }
            }
        }

        if (best_neighbor.empty()) {
            break;
        }

        if (best_distance < calculate_distance(best_route, distances)) {
            best_route = best_neighbor;
        }

        tabu_list.push_back(best_neighbor);
        if (tabu_list.size() > tabu_size) {
            tabu_list.erase(tabu_list.begin());
        }

        current_route = best_neighbor;
    }

    return {best_route, calculate_distance(best_route, distances)};
}

int main() {
    vector<vector<int>> distances = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    vector<int> initial_route = {0, 1, 2, 3};

    auto [best_route, best_distance] = tabu_search(distances, initial_route, 100, 5);
    cout << "Legjobb útvonal: ";
    for (int city : best_route) {
        cout << city << " ";
    }
    cout << "\nTávolság: " << best_distance << endl;

    return 0;
}

Kimenet: 

Legjobb útvonal: 0 1 3 2 
Távolság: 80

Előnyök

  1. Elkerüli a lokális optimumokat a tabulista segítségével.
  2. Könnyen adaptálható különböző problémákhoz.
  3. Hatékony kombinatorikus optimalizációs problémákra.


Hátrányok

  1. Paraméterérzékeny (tabulista mérete, maximális iterációk száma).
  2. Nagy számítási költség sok szomszédos megoldás esetén.
  3. Globális optimumot nem garantálja.


Összegzés

A tabu keresés egy hatékony heurisztikus algoritmus, amely jól alkalmazható összetett kombinatorikus problémák megoldására, például az utazóügynök problémára vagy ütemezési feladatokra. Bár nem garantálja a globális optimum elérését, a lokális optimumok elkerülésére kiváló módszer.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=tabu_keresés&oldid=3479709”