hangya kolónia optimalizáció

• IPA:

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.

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.

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:
    ${\displaystyle \tau _{ij}=(1-\rho )\cdot \tau _{ij}+\sum _{k}\Delta \tau _{ij}^{k}}$
    ahol:
    * ${\displaystyle \tau _{ij}}$: A \(i\)-ből \(j\)-be vezető út feromonértéke.
    * ${\displaystyle \rho }$: A párolgási arány (\(0 < \rho < 1\)).
    * ${\displaystyle \Delta \tau _{ij}^{k}}$: 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.

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

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 ** self.alpha
                heuristic = (1 / self.distances) ** 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]] += 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 = 
                visited = set(route)

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

                route.append(route)  # visszatérés a kezdő városba
                all_routes.append(route)
                distance = sum(self.distances]] 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([
    ,
    ,
    ,
    
])

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)

Adott távolságmátrix mellett:

Legjobb útvonal: 
Legjobb távolság: 11

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.

• 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.

• 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. ${\displaystyle \alpha }$, ${\displaystyle \beta }$, ${\displaystyle \rho }$) helyes megválasztásától.

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.

• hangya kolónia optimalizáció - Értelmező szótár (MEK)
• hangya kolónia optimalizáció - Etimológiai szótár (UMIL)
• hangya kolónia optimalizáció - Szótár.net (hu-hu)
• hangya kolónia optimalizáció - DeepL (hu-de)
• hangya kolónia optimalizáció - Яндекс (hu-ru)
• hangya kolónia optimalizáció - Google (hu-en)
• hangya kolónia optimalizáció - Helyesírási szótár (MTA)
• hangya kolónia optimalizáció - Wikidata
• hangya kolónia optimalizáció - Wikipédia (magyar)