Ameisenalgorithmus
Verfasst: 04.06.2005 22:02
Stichworte: Rundreise, Travelling-Salesman-Problem, TSP
Die (hoffentlich) fehlerlose Implementierung des Ameisenalgorithmus (siehe auch: https://de.wikipedia.org/wiki/Ameisenalgorithmus)
Was macht er?
Er findet, nach dem Prinzip der Ameisen, eine relativ kurze Rundreise zw.
den (hier 4) Städten.
greetz
Remi
PS: Benutzt diesen Code nicht für den Contest in der PureLounge, das würde
ich merken
// Edit: Nicht mehr funktionierende Link-Adresse angepasst (Kiffi)
Die (hoffentlich) fehlerlose Implementierung des Ameisenalgorithmus (siehe auch: https://de.wikipedia.org/wiki/Ameisenalgorithmus)
Code: Alles auswählen
;- Spielt etwas mit diesen Werten:
#BestAdapt = 35.0 ; zw. 0 und 100
#RandAdapt = 80.0 ; zw. 0 und 100
#N = 4 ; Anz. Städte
#A = 100 ; Anz. Ameisen
#D = 200 ; Anz. Durchläufe
Dim Distanzen.l(#N - 1, #N - 1)
Dim Pheromone.f(#N - 1, #N - 1)
Dim Ameisen(#A - 1, #N - 1)
; Distanzen einlesen
Restore distanzen
For y = 0 To #N - 1
For x = 0 To #N - 1
Read distanzen(x, y)
Next
Next
Procedure.l FindWay(Am.l, Von.l, Bis.l)
Protected z.l, Found.l, k.l, BestPh.f, BestStd.l
Repeat
BestPh = -1.0
BestStd = -1
; Zu allen Städten schauen (ohne 0 (Startpunkt))
For z = 1 To #N - 1
Found = #False
; Wurde Stadt schon besucht?
For k = 1 To Bis
If Ameisen(Am, k) = z
Found = #True
Break
EndIf
Next
If Found
Continue
EndIf
v.f = Random(100)
If (Pheromone(Von, z) > BestPh And v > #BestAdapt) Or v > #RandAdapt
BestPh = Pheromone(Von, z)
BestStd = z
EndIf
Next
Until BestStd <> -1
ProcedureReturn BestStd
EndProcedure
For n = 1 To #D
; Für jede Stadt
For z = 0 To #N - 2
For t = 0 To #A - 1
NStadt.l = FindWay(t, Ameisen(t, z), z)
Ameisen(t, z + 1) = NStadt
Next
Next
; Pheromone Updaten
For t = 0 To #A - 1
Dist.l = 0
; Distanz errechnen
For z = 0 To #N - 2
Dist + Distanzen(Ameisen(t, z), Ameisen(t, z + 1))
Next
; Pheromone setzen
For z = 0 To #N - 2
Pheromone(Ameisen(t, z), Ameisen(t, z + 1)) + 1.0 / Dist
Pheromone(Ameisen(t, z + 1), Ameisen(t, z)) + 1.0 / Dist
Next
Next
Next
Best.l = 9999999
BestAm = 0
For t = 0 To #A - 1
Dist.l = 0
; Distanz errechnen
For z = 0 To #N - 2
Dist + Distanzen(Ameisen(t, z), Ameisen(t, z + 1))
Next
Dist + Distanzen(Ameisen(t, #N - 1), 0)
If Dist < Best
Best = Dist
BestAm = t
EndIf
Next
For z = 0 To #N - 1
Debug Ameisen(BestAm, z)
Next
Debug 0
Debug "########"
Debug Best
CallDebugger
DataSection
distanzen:
Data.l 0, 2, 3, 5
Data.l 2, 0, 4, 1
Data.l 3, 4, 0, 8
Data.l 5, 1, 8, 0
EndDataSection
Er findet, nach dem Prinzip der Ameisen, eine relativ kurze Rundreise zw.
den (hier 4) Städten.
greetz
Remi
PS: Benutzt diesen Code nicht für den Contest in der PureLounge, das würde
ich merken
// Edit: Nicht mehr funktionierende Link-Adresse angepasst (Kiffi)