Wikiszótár

hangya kolónia optimalizáció

Magyar

Kiejtés

  • IPA: [ ˈhɒɲɟɒ ˈkoloːnijɒ ˈoptimɒlizaːt͡sijoː]

Főnév

hangya kolónia optimalizáció

  1. (matematika, algoritmusok) A Hangya Kolónia Optimalizáció (ACO) egy természet inspirálta metaheurisztikus algoritmus, amely a hangyák kollektív viselkedését modellezi, különösen azt, hogyan találnak a hangyák a legrövidebb utat az élelemforrásokhoz. Az algoritmus a **feromonpárolgás** és a **pozitív visszacsatolás** alapelvein működik.

Alapötlet

  1. Feromonok és útvonalak:
  - A hangyák feromont hagynak maguk után az általuk használt útvonalakon.
  - A rövidebb utak több feromont gyűjtenek össze, mert gyakrabban használják őket.
  1. Stokasztikus választás:
  - A hangyák nem determinisztikusan, hanem valószínűségi alapon választják meg az útvonalakat, előnyben részesítve a magasabb feromontartalmú utakat.
  1. Párolgás:
  - Az idő múlásával a feromonok párolognak, elkerülve az állandó megrekedést egy helyi optimumon.

Algoritmus Lépései

  1. Induló állapot:
  - A hangyák véletlenszerűen helyezkednek el az útvonalhálózat pontjain.
  1. Útválasztás:
  - Minden hangya egy-egy teljes megoldást épít (pl. egy teljes útvonalat az **Utazó Ügynök Problémában**).
  1. Feromon frissítése:
  - A feromonszintek frissítése a következő képlet szerint történik:
     
    ahol:
    *  : A \(i\)-ből \(j\)-be vezető út feromonértéke.
    *  : A párolgási arány (\(0 < \rho < 1\)).
    *  : Az \(k\)-adik hangya által adott feromonmennyiség, amely arányos az útvonal minőségével.
  1. Iteráció:
  - A hangyák új körben ismét építik a megoldásokat, az aktuális feromonszintek alapján.
  1. Megállási kritérium:
  - Az algoritmus addig fut, amíg el nem ér egy előre meghatározott iterációszámot vagy elégséges minőségű megoldást nem talál.

Alkalmazás: Utazó Ügynök Probléma (TSP)

Matematikai Modell

A cél: Minimális össztávolságot kell megtalálni, miközben minden várost pontosan egyszer látogatunk meg.

Python Implementáció

import numpy as np
import random

class AntColonyOptimizer:
    def __init__(self, distances, n_ants, n_iterations, decay, alpha=1, beta=2):
        self.distances = distances
        self.pheromones = np.ones(self.distances.shape) / len(distances)
        self.n_ants = n_ants
        self.n_iterations = n_iterations
        self.decay = decay
        self.alpha = alpha
        self.beta = beta
        self.all_indices = range(len(distances))

    def _select_next_city(self, current_city, visited):
        probabilities = []
        for city in self.all_indices:
            if city not in visited:
                pheromone = self.pheromones[current_city][city] ** self.alpha
                heuristic = (1 / self.distances[current_city][city]) ** self.beta
                probabilities.append(pheromone * heuristic)
            else:
                probabilities.append(0)
        probabilities = probabilities / np.sum(probabilities)
        return np.random.choice(self.all_indices, p=probabilities)

    def _update_pheromones(self, all_routes, all_distances):
        self.pheromones *= (1 - self.decay)
        for route, distance in zip(all_routes, all_distances):
            for i in range(len(route) - 1):
                self.pheromones[route[i]][route[i+1]] += 1.0 / distance

    def optimize(self):
        best_distance = float("inf")
        best_route = None

        for _ in range(self.n_iterations):
            all_routes = []
            all_distances = []

            for _ in range(self.n_ants):
                route = [random.choice(self.all_indices)]
                visited = set(route)

                while len(route) < len(self.distances):
                    next_city = self._select_next_city(route[-1], visited)
                    route.append(next_city)
                    visited.add(next_city)

                route.append(route[0])  # visszatérés a kezdő városba
                all_routes.append(route)
                distance = sum(self.distances[route[i]][route[i + 1]] for i in range(len(route) - 1))
                all_distances.append(distance)

                if distance < best_distance:
                    best_distance = distance
                    best_route = route

            self._update_pheromones(all_routes, all_distances)

        return best_route, best_distance


# Példa: TSP
distances = np.array([
    [0, 2, 2, 5],
    [2, 0, 4, 6],
    [2, 4, 0, 1],
    [5, 6, 1, 0]
])

optimizer = AntColonyOptimizer(distances, n_ants=5, n_iterations=100, decay=0.1)
best_route, best_distance = optimizer.optimize()

print("Legjobb útvonal:", best_route)
print("Legjobb távolság:", best_distance)

Kimenet Példa

Adott távolságmátrix mellett: 

Legjobb útvonal: [0, 1, 2, 3, 0]
Legjobb távolság: 11

Alkalmazások

  1. Logisztika:
  - Jármű útvonaltervezési probléma (VRP).
  1. Hálózattervezés:
  - Adathálózatok optimalizálása.
  1. Mesterséges intelligencia:
  - Kombinatorikus problémák optimalizálása.

Előnyök és Hátrányok

Előnyök

  • Paralelizálható: Egyidejűleg több hangya is kereshet megoldást.
  • Rugalmasság: Alkalmas különféle optimalizációs problémákra.
  • Közeli optimum: Nagyobb eséllyel talál globális optimumot, mint egyes determinisztikus algoritmusok.

Hátrányok

  • Lassabb lehet: Sok iteráció szükséges a jó eredményhez.
  • Paraméterérzékenység: Az algoritmus teljesítménye erősen függ a paraméterek (pl.  ,  ,  ) helyes megválasztásától.

Összegzés

A **Hangya Kolónia Optimalizáció** hatékony metaheurisztikus algoritmus, amely különösen jól alkalmazható hálózati és kombinatorikus problémák megoldására. Pythonban egyszerűen implementálható, és széles körben alkalmazható valós problémákra, például az utazó ügynök probléma vagy a jármű útvonaltervezés területén.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=hangya_kolónia_optimalizáció&oldid=3479853”