ant colony optimization

Angol

Főnév

ant colony optimization (tsz. ant colony optimizations)

(informatika) hangya kolónia optimalizáció

Ant Colony Optimization (ACO, magyarul: hangyakolóniás optimalizáció) egy metaheurisztikus algoritmus, amelyet kombinatorikus optimalizálási problémák megoldására használnak. A módszert Marco Dorigo vezette be 1992-ben, és inspirációját a valódi hangyák viselkedéséből nyerte, különösen abból, ahogyan feromonokat használnak az útvonalak megjelölésére.

🐜 1. Alapötlet: Mit csinálnak a hangyák?

A valódi hangyák:

Véletlenszerűen indulnak el élelmet keresve,
Ha találnak valamit, feromonnyomot hagynak visszafelé menet,
Más hangyák követik az erősebb feromonos útvonalakat,
Az optimális út lesz egyre népszerűbb (mert gyorsabban járható → több feromon).

🎯 2. ACO algoritmus lényege

Számítógépes modellben:

Több szimulált „hangya” felfedezi a megoldásteret,
Megoldásokat építenek lépésről lépésre (pl. útvonalak, sorrendek),
Feromon értékek és heurisztikus információk alapján döntenek,
A „jó megoldások” erősítik a hozzájuk tartozó útvonalakat.

📐 3. Alapfogalmak

Fogalom	Jelentés
Feromon	Mesterséges jel, ami a megoldások minőségét jelzi
Heurisztika	Problémaspecifikus érték (pl. távolság reciprok)
Tabu lista	Tiltólista a ciklusok elkerülésére
Párolgás	Feromon csökkenése idővel → diverzitás fenntartása

🧮 4. Matematikai modell

Valószínűség, hogy hangya ${\textstyle k}$ a ${\textstyle i\to j}$ élt választja:

$P_{ij}^{k}={\frac {[\tau _{ij}]^{\alpha }\cdot [\eta _{ij}]^{\beta }}{\sum _{l\in {\text{megengedett}}}[\tau _{il}]^{\alpha }\cdot [\eta _{il}]^{\beta }}}$

ahol:

${\textstyle \tau _{ij}}$ : feromon szint az ${\textstyle i\to j}$ élen
${\textstyle \eta _{ij}}$ : heurisztikus érték (pl. ${\textstyle 1/{\text{távolság}}_{ij}}$ )
${\textstyle \alpha ,\beta }$ : súlyozó paraméterek

🔁 5. ACO algoritmus lépései

Inicializálás – feromonértékek, paraméterek
Minden hangya megoldást épít – pl. egy útvonalat TSP-ben
Megoldások értékelése
Feromonfrissítés:
- Párolgás: minden ${\textstyle \tau _{ij}\gets (1-\rho )\tau _{ij}}$
- Letét: jó megoldások növelik ${\textstyle \tau _{ij}}$ -t
Ismétlés – új generáció, új utak

📦 6. Alkalmazások

Probléma	Leírás
Travelling Salesman Problem	Legrövidebb körút
Ütemezési problémák	Gyártás, iskolai beosztás
Routing problémák	Adathálózat, logisztika
Jármű útvonal	Vehicle Routing Problem (VRP)
Telepítési feladatok	Pl. vezeték tervezés

💻 7. Python példa (TSP-re, egyszerűsített)

import numpy as np

def distance_matrix(coords):
    return np.linalg.norm(coords[:, None, :] - coords[None, :, :], axis=-1)

def initialize_pheromones(n, initial=1.0):
    return np.full((n, n), initial)

def aco_tsp(coords, n_ants=10, n_iter=100, alpha=1, beta=5, rho=0.1, Q=100):
    n = len(coords)
    dist = distance_matrix(coords)
    pheromone = initialize_pheromones(n)
    best_path, best_len = None, np.inf

    for _ in range(n_iter):
        paths, lengths = [], []

        for _ in range(n_ants):
            visited = [0]
            while len(visited) < n:
                i = visited[-1]
                probs = []
                for j in range(n):
                    if j not in visited:
                        tau = pheromone[i][j] ** alpha
                        eta = (1 / dist[i][j]) ** beta
                        probs.append((j, tau * eta))
                total = sum(p for _, p in probs)
                probs = [(j, p / total) for j, p in probs]
                next_city = np.random.choice([j for j, _ in probs], p=[p for _, p in probs])
                visited.append(next_city)
            visited.append(0)  # vissza kezdővárosba
            length = sum(dist[visited[i]][visited[i+1]] for i in range(n))
            if length < best_len:
                best_len = length
                best_path = visited
            paths.append(visited)
            lengths.append(length)

        # Feromonfrissítés
        pheromone *= (1 - rho)
        for path, length in zip(paths, lengths):
            for i in range(n):
                pheromone[path[i]][path[i+1]] += Q / length

    return best_path, best_len

⚙️ 8. Paraméterek hatása

Paraméter	Jelentés	Hatás
${\textstyle \alpha }$	Feromon súlya	nagy → erősebb tanulás
${\textstyle \beta }$	Heurisztika súlya	nagy → mohóbb viselkedés
${\textstyle \rho }$	Párolgási arány	nagy → gyors felejtés
${\textstyle Q}$	Feromonmennyiség	kis érték → kevesebb tanulás

📈 9. Előnyök és hátrányok

✅ Előnyök:

Jó kombinatorikus optimalizálásra
Könnyen párhuzamosítható
Adaptív: tanul a korábbi eredményekből

❌ Hátrányok:

Sok paraméter, érzékeny beállítás
Lassabb konvergencia, mint pl. greedy módszereknél
Lokális optimum csapdája (megoldható párolgással)

🧾 10. Összefoglalás

Fogalom	Leírás
ACO	Véletlenszerű keresés + feromonos tanulás
Alkalmazások	TSP, VRP, ütemezés, routing
Fő komponensek	Feromon, heurisztika, párolgás
Előny	Adaptív, robusztus keresés
Eszközök	Python (ACO-Py), C++, MATLAB könyvtárak

További információk

ant colony optimization - Szótár.net (en-hu)
ant colony optimization - Sztaki (en-hu)
ant colony optimization - Merriam–Webster
ant colony optimization - Cambridge
ant colony optimization - WordNet
ant colony optimization - Яндекс (en-ru)
ant colony optimization - Google (en-hu)
ant colony optimization - Wikidata
ant colony optimization - Wikipédia (angol)