ant colony optimization

ant colony optimization (tsz. ant colony optimizations)

1. (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.

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

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.

$${\displaystyle P_{ij}^{k}={\frac {^{\alpha }\cdot ^{\beta }}{\sum _{l\in {\text{megengedett}}}^{\alpha }\cdot ^{\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

1. Inicializálás – feromonértékek, paraméterek
2. Minden hangya megoldást épít – pl. egy útvonalat TSP-ben
3. Megoldások értékelése
4. 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
5. Ismétlés – új generáció, új utak

import numpy as np

def distance_matrix(coords):
    return np.linalg.norm(coords - coords, 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 = 
            while len(visited) < n:
                i = visited
                probs = 
                for j in range(n):
                    if j not in visited:
                        tau = pheromone ** alpha
                        eta = (1 / dist) ** beta
                        probs.append((j, tau * eta))
                total = sum(p for _, p in probs)
                probs = 
                next_city = np.random.choice(, p=)
                visited.append(next_city)
            visited.append(0)  # vissza kezdővárosba
            length = sum(dist]] 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]] += Q / length

    return best_path, best_len

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

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

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

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