ThesisWiki : AntPheromones

ThesisHome :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register

Mierensystemen in de computerwereld

Zie ook

Terug naar feromoonverspreiding

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]:
image
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:
image
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.
image
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:
image
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


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:
image 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)
image

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)


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:

image
image

Ant Colony Systems


Formullekes:

image

Referentie

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

CategoryRequirements
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0272 seconds