Most recent edit on 2007-05-02 06:16:10 by MerelVeracx

Deletions:
We zien dus dat hoe groter het verschil tussen alfa en beta, hoe beter het algoritme presteert. Hierbij is het belangrijk dat alfa kleiner is dan beta. Dit zou te verklaren kunnen zijn door het grote verschil tussen de waarden van theta en eta (het totaal aantal feromonen op een pad en de heuristiek van een pad).
Deze experimenten laten uitschijnen dat een toenemende alfa GEEN goede rol speelt in het algoritme.

1. Indien we de heuristiek van een pad scaleren (betere verspreiding van de waarden tussen 0 en 1 ipv tussen 0 en 0.01) ?
2. Indien we de globale verdamping verminderen ?
   
   

   ---

   
   Edited on 2007-03-21 10:11:37 by MerelVeracx
   
   Deletions:
   

   Doel

Keuze van een pad

als j € N^k_i ; anders 0
Als boog J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (heuristic desirability van IJ)^BETA
en dit gedeeld door totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en heuristic desirabilities)

Heuristic desirability van IJ

Hierbij is $\psi$ de extra kost die per schending geteld wordt en $nbv(game_j)$ het aantal schendingen van de constaints wanneer de wedstrijd $j$ toegevoegd zou worden aan de kalender. Indien wedstrijd $j$ A-B is, zal de kost afhankelijk zijn van de kalender die de mier al opgesteld heeft. Als geweten is van A dat ze eerder uit speelde tegen C, dan is $travelingdistance(A) = distance(C, A)$. Als A thuis speelde is dit 0. Dezelfde redenering voor B: indien ze eerder uitspeelde tegen D, dan is $travelingdistance(B) = distance(D, A)$. Als hij thuis speelde is dit $distance(B, A)$.

Feromoon evoluering

Hierbij is het versterken van het feromonenspoor gelijk aan:
(optimale kost kalender)/(kost kalender)

Numerieke resultaten (maxima en minima)

Zie hiervoor een overzicht (vergeleken met de numerieke waarden zoals beschreven in Swarm Intelligence, Bonnabeau) op numerieke resultaten van Ant System

Afstellen parameters

1. alfa:
2. beta:
3. globale evaporatie:

---

Edited on 2007-03-21 10:11:06 by MerelVeracx

Additions:

Experiment AS: vier ploegen

Zie voor gebruikte formules bij
Ant System experiments

Deletions:

Experiment AS: parameter optimalisatie

---

Oldest known version of this page was edited on 2007-03-21 09:47:11 by MerelVeracx [Cloned from ExpAB]

Experiment AS: parameter optimalisatie

Doel

Keuze van een pad

als j € N^k_i ; anders 0

Als boog J nog bezocht moet worden:
(de sterkte van het feromonenspoor)^ALFA * (heuristic desirability van IJ)^BETA
en dit gedeeld door totale kost van alle uitgaande bogen uit knoop I (som van alle feromonen en heuristic desirabilities)

Heuristic desirability van IJ

Hierbij is $\psi$ de extra kost die per schending geteld wordt en $nbv(game_j)$ het aantal schendingen van de constaints wanneer de wedstrijd $j$ toegevoegd zou worden aan de kalender. Indien wedstrijd $j$ A-B is, zal de kost afhankelijk zijn van de kalender die de mier al opgesteld heeft. Als geweten is van A dat ze eerder uit speelde tegen C, dan is $travelingdistance(A) = distance(C, A)$. Als A thuis speelde is dit 0. Dezelfde redenering voor B: indien ze eerder uitspeelde tegen D, dan is $travelingdistance(B) = distance(D, A)$. Als hij thuis speelde is dit $distance(B, A)$.

Feromoon evoluering

Hierbij is het versterken van het feromonenspoor gelijk aan:
(optimale kost kalender)/(kost kalender)

Numerieke resultaten (maxima en minima)

Zie hiervoor een overzicht (vergeleken met de numerieke waarden zoals beschreven in Swarm Intelligence, Bonnabeau) op numerieke resultaten van Ant System

Afstellen parameters

1. alfa:
2. beta:
3. globale evaporatie:

Uitgevoerde experimenten

Alle experimenten werden 3 keer herhaald, uitgevoerd op omgeving 1 voor het probleem van 4 ploegen met telkens 6 mieren.

TacticName	TacticMethod	ParamName	Value
AntDiedPheromoneTactic	Ant_died_is_linear_more	min_amount	0.01
AntDiedPheromoneTactic	Ant_died_is_linear_more	max_amount	0.3
AntEnhancePheromoneTactic	Pheromone_enh_AS	near_optimal	8276
CalenderCostTotalTactic	VARIABLE (cost)	-	-
EdgeSelectionTactic	Edgeselection_AS	alfa	VARIABLE (a)
EdgeSelectionTactic	Edgeselection_AS	beta	VARIABLE (b)
ElitePheromoneTactic	Max_m_times_enhancing	max_elite	5
GlobalEvaporationTactic	AS_global_evaporation	global_evaporation_rate	VARIABLE (p)

Experiment voor het te bestuderen van de feromonen in de omgeving.

Voor feromonengedrag analoog aan experiment 184∞ zie experiment 252∞, grafiek te bekijken op deze pagina.

Voor feromonengedrag analoog aan experiment 195∞ zie experiment 253∞, grafiek te bekijken op deze pagina.

4 teams					100 iteraties
Expn	ants	a	b	p	cost	gem optimal	all optimal?	optimal in run	improvementstop
184	6	1	5	0.5	R	1.000564	2 / 3	4 / 5	5 / 4 / 17
185	6	0	5	0.5	R	1.000564	2 / 3	5 / 34	14 / 5 / 34
186	6	3	1	0.5	R	1.018407	0 / 3	0	1 / 1 / 1
195	6	3	2	0.5	R	1.038465	0 / 3	0	2 / 1 / 6
196	6	2	3	0.5	R	1.009062	0 / 3	0	9 / 4 / 1
205	6	1	5	0.2	R	1.001692	0 / 3	0	34 / 30 / 3
206	6	1	5	0.4	R	1.000564	0 / 3	0	5 / 1 / 3
207	6	1	5	0.6	R	1.001128	1 / 3	22	22 / 8 / 30
208	6	1	5	0.7	R	1.000564	2 / 3	3 / 6	3 / 6 / 12
231	6	2	4	0.5	SR	1.021236	0 / 4	0	5 / 6 / 11 / 7

CalenderCostTotalTactic	R = Totalcost_ref	dead_penalty	30
CalenderCostTotalTactic	R = Totalcost_ref	constraint_penalty	0.3
Edgeselection scaled	R = no scaling	scalingfactor	1
Edgeselection scaled	SR = scaling	scalingfactor	0.001

We zien dus dat hoe groter het verschil tussen alfa en beta, hoe beter het algoritme presteert. Hierbij is het belangrijk dat alfa kleiner is dan beta. Dit zou te verklaren kunnen zijn door het grote verschil tussen de waarden van theta en eta (het totaal aantal feromonen op een pad en de heuristiek van een pad).

Deze experimenten laten uitschijnen dat een toenemende alfa GEEN goede rol speelt in het algoritme.

1. Indien we de heuristiek van een pad scaleren (betere verspreiding van de waarden tussen 0 en 1 ipv tussen 0 en 0.01) ?
2. Indien we de globale verdamping verminderen ?