Mierensystemen in de computerwereld

Zie voor een uitgebreide beschrijving de literatuur:
Swarm-Intelligence, from natural to artificial systems, Dorigo et al, p. 40-56. Meer informatie∞
Solving Dynamic constraint optimization problems (Dyn COAA) p33-38 Download hier∞

DynCOAA

Pheromone weighting formula [CM95]:

Waarbij de r de hoeveelheid feromonen op een bepaalde boog is
Betha de osmotropotaxic sensitivity;
en 1/delta de sensory capacity.

Indien we gebruik maken van het bovenstaande gewicht van een boog, kan men de kans dat een boog i gekozen wordt omschrijven met:

waarbij k een mier aanduidt, A een node, i de boog die je kiest;
De kans om boog i te kiezen is zijn gewicht / totale gewicht van de boog. Hoe hoger het gewicht, hoe meer kans dat de boog gekozen wordt.

In DynCOAA werkt men met 2 soorten pheromonen: positieve die aangeven hoe graag een boog tov een andere boog geprefereerd wordt; en negatieve die aangeven hoe meer je een andere boog kunt overwegen.

Hierbij zijn r+ en r- respectievelijk de hoeveelheid positieve en negatieve feromonen op boog i. Betha en Delta zijn hetzelfde als hierboven.

Tenslotte kan een mier zijn verleden bekijken en op basis van het verleden de andere bogen evalueren (constraint checking, distance, ..). De uiteindelijke formule ziet er als volgt uit:

Hierbij is de gamma de geaccumuleerde kost van het verleden met de i-de boog.

Vastgestelde parameters

# mieren = # knopen
beta (osmotropotaxic capacity) = 3.5
1/delta (sensory capacity) = 0.2
eta_0 (weight cost vs pheromones) = 2
vee (decay of eta) = exp(ln(0.5)/total iterations)
roo (global evaporation) = 0.1
E (local evaporation) = 1 - sqrt(0.8)^(n)

Ant Systems

• alle mieren worden toegestaan feromonen te verspreiden
• de hoeveelheid feromonen is afhankelijk van de kwaliteit van het gevonden pad
• feromonen verdampen voordat de mieren opnieuw feromonen leggen (nadat elke mier een pad gevonden heeft)

De keuze van de mier wordt bepaald door de sterkte van het feromonenspoor op dat pad en hoe goed dat het pad bijdraagt tot de oplossing (cost van het pad minimaal).

Formullekes:

Keuze van een pad:
als j € N^k_i ; anders 0
In woorden: de kans van mier K om van knoop I naar knoop J te gaan (en dus boog IJ te kiezen) in iteratie T is gelijk aan:
ALS J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (heuristic desirability van IJ)^BETHA
en dit gedeeld door
totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en heuristic desirabilitys)

Vastgestelde parameters

In SI (Bonabeau) kiezen ze in algoritme AS-TSP op p 45 alfa = 1 en beta = 5. De beginferomoonwaarden voor elke boog wordt gelijk gesteld aan 10^(-6). Het aantal mieren wordt gelijkgesteld aan het aantal steden respectievelijk aantal knopen in de grafe.

Ant Max-Min System (Stützle en Hoos)

• enkel de mier die het beste pad gevonden heeft, mag feromonen verspreiden
• de hoeveelheid feromonen wordt beperkt: er wordt zowel een minimumwaarde als een maximumwaarde afgedwongen.
• de feromonen op alle bogen wordt bij initialisatie op max_feromoon gezet

Experimenten hebben aangetoond [] dat de resultaten beter zijn wanneer er ook het pad met de gemiddelde beste weg regelmatig feromonen krijgt. (Trail smoothing mechanism, p55 in boek Swarm Intelligence, Dorigo en co).

Formullekes:

Ant Colony Systems

• heeft een andere manier voor het kiezen van een bepaald pad (voor details, zie literatuur)
• enkel de feromonen op het gemiddelde beste pad worden versterkt
• feromonen verdampen enkel wanneer er een mier overloopt en nadat een mier een feromonenupdate gedaan heeft.

Formullekes:

Referentie

[]: Thomas St¨utzle. Local search algorithms for combinatorial problems: Analysis, improvements and new applications. PhD thesis, Fachbereich Informatik, TU Darmstadt, Germany, 1998.

CategoryRequirements