ThesisWiki : AntPheromones

ThesisHome :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register
Most recent edit on 2007-02-27 14:56:09 by MerelVeracx

Additions:

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


Deletions:

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]:
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 * (kost van het pad waarin IJ inzit)^BETHA
en dit gedeeld door
totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en kosten)
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.




Edited on 2006-12-10 14:38:48 by MerelVeracx

Deletions:

Goed, aangezien wij niet werken met negatieve feromonen (aka feromonen die iets vertellen over hoe slecht een boog het gedaan heeft in 't verleden), gaan we de formule een beetje aanpassen.
Neem het aantal negatieve feromonen constant gelijk aan 0:
dan blijft er over
image




Edited on 2006-12-10 14:37:03 by MerelVeracx

Additions:

Goed, aangezien wij niet werken met negatieve feromonen (aka feromonen die iets vertellen over hoe slecht een boog het gedaan heeft in 't verleden), gaan we de formule een beetje aanpassen.
Neem het aantal negatieve feromonen constant gelijk aan 0:
dan blijft er over
image




Edited on 2006-12-10 08:04:57 by MerelVeracx

Additions:

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


Deletions:

Ant Max-Min System

Experimenten hebben aangetoond [] dat de resultaten beter zijn wanneer er ook het pad met de gemiddelde beste weg regelmatig feromonen krijgt.




Edited on 2006-11-13 08:32:48 by MerelVeracx

Additions:

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)

Vastgestelde parameters





Edited on 2006-11-13 08:29:12 by MerelVeracx

Additions:
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.



Edited on 2006-11-01 13:12:04 by MerelVeracx

Additions:
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.




Edited on 2006-11-01 09:50:42 by MerelVeracx

Additions:
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.




Edited on 2006-11-01 09:44:42 by MerelVeracx

Additions:

DynCOAA

Pheromone weighting formula [CM95]:
image
image
image




Edited on 2006-10-17 15:03:03 by MerelVeracx

Additions:
totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en kosten)

Deletions:
de kost van het pad en de sterkte van het feromonenspoor erop voordat je IJ zou toevoegen.



Edited on 2006-10-17 14:23:01 by MerelVeracx

Additions:
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 * (kost van het pad waarin IJ inzit)^BETHA
en dit gedeeld door
de kost van het pad en de sterkte van het feromonenspoor erop voordat je IJ zou toevoegen.




Edited on 2006-10-17 13:58:35 by MerelVeracx

Additions:
image

Deletions:
image



Edited on 2006-10-17 13:56:22 by MerelVeracx

Additions:

Formullekes:

Keuze van een pad:

Formullekes:

image
image

Formullekes:

image


Deletions:

Keuze van een pad:





Edited on 2006-10-17 13:52:05 by MerelVeracx

Additions:
image



Edited on 2006-10-17 13:49:26 by MerelVeracx

Additions:
image als j € N^k_i ; anders 0

Deletions:
image



Edited on 2006-10-17 13:48:02 by MerelVeracx

Additions:

Keuze van een pad:

image




Edited on 2006-10-17 13:39:35 by MerelVeracx

Additions:

Referentie

CategoryRequirements




Edited on 2006-10-17 13:37:45 by MerelVeracx

Additions:
- heeft een andere manier voor het kiezen van een bepaald pad (voor details, zie literatuur)

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

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

Ant Max-Min System


Experimenten hebben aangetoond [] dat de resultaten beter zijn wanneer er ook het pad met de gemiddelde beste weg regelmatig feromonen krijgt.

Ant Colony Systems


[]: Thomas St¨utzle. Local search algorithms for combinatorial problems: Analysis, improvements and new applications. PhD thesis, Fachbereich Informatik, TU Darmstadt, Germany, 1998.
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.2
Page was generated in 0.0728 seconds