Biologinen inspiraatio

Luonnossa muurahaiset pystyvät löytämään lyhyimmät reitit pesänsä ja ravinnonlähteiden välillä jättämällä ja seuraamalla feromonipolkuja. Muurahaisten kulkiessa ne laskevat feromoneja maahan, muodostaen kemiallisen polun, jota muut muurahaiset todennäköisesti seuraavat. Todennäköisyys, että muurahainen valitsee tietyn reitin, kasvaa kyseisen reitin feromonipitoisuuden myötä. Tämä mekanismi johtaa positiiviseen palautesilmukkaan: reittejä, joilla on enemmän feromonia, valitaan useammin, mikä puolestaan lisää feromonin määrää näillä reiteillä. Ajan myötä tämä kollektiivinen käyttäytyminen mahdollistaa yhdyskunnan löytää optimaalisia tai lähes optimaalisia ratkaisuja monimutkaisiin ongelmiin hajautetusti.

Esimerkki: Feromonin päivitysprosessi

# Pseudocode for updating pheromone trails in a simple graph

# Assume pheromone is a dictionary: pheromone[(i, j)] gives the pheromone value on edge (i, j)
# delta_pheromone is a dictionary: delta_pheromone[(i, j)] accumulates pheromone deposited by all ants

rho = 0.5  # Evaporation rate (0 < rho < 1)
for (i, j) in pheromone:
    # Evaporation: reduce existing pheromone
    pheromone[(i, j)] *= (1 - rho)
    # Deposit: add new pheromone from this iteration
    pheromone[(i, j)] += delta_pheromone.get((i, j), 0.0)

ACO:n sovellukset: Kauppamatkustajan ongelma

Ant Colony Optimization on erityisen tehokas kombinatoristen optimointiongelmien ratkaisemisessa, joissa tavoitteena on löytää paras järjestys tai valinta rajallisesta joukosta. Klassinen esimerkki on kauppamatkustajan ongelma (TSP), jossa tulee löytää lyhin mahdollinen reitti, joka vierailee jokaisessa kaupungissa täsmälleen kerran ja palaa lähtökaupunkiin. ACO:ssa jokainen keinotekoinen muurahainen rakentaa kierroksen valitsemalla seuraavan kaupungin todennäköisyyspohjaisesti, mihin vaikuttavat sekä feromonin määrä että etäisyys jokaiseen vierailemattomaan kaupunkiin. Kun kaikki muurahaiset ovat suorittaneet kierroksensa, feromonijälkiä päivitetään vahvistamaan lyhyempiä ja tehokkaampia reittejä, kun taas vähemmän optimaaliset polut menettävät feromonia haihtumisen kautta. Tämä iteratiivinen prosessi mahdollistaa ACO:n tehokkaan laajan hakutilan tutkimisen ja lähestymisen korkealaatuisiin ratkaisuihin monimutkaisissa reititys- ja aikataulutustehtävissä.