Routenplanung

In unserem Projekt “Routenplanung” wollen wir zum einen über unsere eigenen definierten Knotenpunkte eine möglichst gute Route berechnen lassen können. Zum anderen können wir zwischen 2 Knotenpunkten die kürzeste/effizienteste Strecke berechnen und ausgeben lassen.

Genutzte Algorithmen sind z.B. der A*-Algorithmus und der “Ameisenalgorithmus”. Ersterer dient der Berechnung kürzester Strecken und letzterer der Berechnung einer optimalen (aber nicht zwingend der optimalsten) Tour der gewählten Knotenpunkte.

Verwendung des Programms

Das Programm wird durch einen Aufruf der main-Methode über ‘go run main.go’ aus dem Quellverzeichnis heraus gestartet, woraufhin sich eine GUI öffnet, mit der die beiden Algorithmen ausgeführt werden können.

1. GUI:
   • Punkte (Nodes) werden durch Linksclick auf der Oberfläche erstellt:

   

   • Kanten (Edges) zwischen zwei Punkten werden durch Rechtsclick auf die beiden Punkte realisiert.

   

   • Durch einen Click auf ‘Delete Edges’ wartet die GUI auf die Auswahl einer zu löschenden Kante durch den Anwender. So können Kanten mit einem Linksclick wieder entfernt werden.

   

2. A*:
   • Durch einen Click auf A* wartet das Programm auf die Auswahl von zwei Knoten durch den Anwender, für die A* berechnet werden soll.
   • Nach Auswahl des zweiten Knotens wird die Berechnung automatisch durchgeführt und das Ergebnis in blauer Farbe durch entsprechende Einfärbung der Linien dargestellt. In diesem Fall ist der Pfad von Node 0 zu Node 3 über die unteren Nodes der kürzeste.

   

3. AntTour:
   • Für den Ameisenalgorithmus wird der ‘Find Route’-Menüpunkt gewählt, woraufhin das Programm auf die Markierung der Tourpunkte durch den Anwender wartet. Markierte Nodes werden in rot dargestellt.

   

   • Nach erfolgter Auswahl muss ‘Select Nodes or click to leave’ ausgewählt werden, sodass die Berechnung ausgeführt wird. Daraufhin wird das Ergebnis für die Tour durch Einfärbung der Linien präsentiert.

Beschreibung A*-Algorithmus

A-Algorithmus wird zur Berechnung eines kürzesten Pfades zwischen zwei Knoten innerhalb eines Graphen mit positiven Kantengewichten verwednet. A kann als eine Erweiterung des Dijkstra-Algorithmus gesehen werden. A* verwendet eine Schätzfunktion, auch Heuristik genannt, mit der zielgerichtet gesucht und damit die Laufzeit verbessert werden kann. Es werden somit immer zuerst die Knoten untersucht, welche, am wahrscheinlich schnellsten, zum Ziel führen. Hierfür wird allen bekannten Knoten ein Wert f(x) zugeordnet, der eine Schätzung angibt, wie lang der Pfad von Start zu Ziel über diesen Knoten ist. Dieser Wert setzt sich aus den Pfadkosten vom Startknoten zu diesem Knoten und der geschätzten Kosten zum Zielknoten, ausgehend von diesem Knoten, zusammen.

Funktionsweise

Die Knoten werden während der Suche in drei verschiedene Klassen eingeteilt.

1. Unbekannte Knoten:\ Knoten die während der Suche noch nicht gefunden wurden. Zu diesen ist noch keine Weg weg bekannt.

2. Bekannte Knoten:\ Zu diesen ist bereits ein Weg bekannt, dieser muss jedoch nicht der optimalste sein. Diese Knoten werden mit ihrem f-Wert in der sogenannten Open List gespeichert. Jeder bekannte Knoten speichert zudem einen Zeiger auf seinen Vorgänger, über welchen er erreicht wird.

3. Abschließend untersuchte Knoten:\ Zu diesen ist der kürzeste Weg bekannt. Diese Knoten werden in der Closed List gespeichert. Dies verhindert eine Mehrfachuntersuchung bereits abgeschlossener Knoten.

Wurde ein kürzester Pfad gefunden, kann der Weg über die Zeiger auf die Vorgängerknoten rückverfolgt werden.

Heuristik

Folgendes muss für die Heuristik gelten:

• Die Kosten dürfen nie überschätzt werden. (Weg darf nicht kürzer als Schätzung sein)
• Für jeden Knoten k und jeden Nachfolgeknoten k′ muss gelten h(k) ≤ c(k,k′) + h(k′). Hierbei bezeichnet c(k,k′) die tatsächlichen Kosten, um von k nach k ′ zu kommen.

Beschreibung gotk für GUI

Erstellen des Fensters und weitere GUI-Elemente

Erstellen des GUI-Fensters, die GUI-Elemente werden in einer Grid-Struktur mit Spalten und Zeilen angeordnet:

gtk.WindowNew(gtk.WINDOW_TOPLEVEL)
grid := gtk.GridNew()
grid.SetOrientation(gtk.ORIENTATION_VERTICAL)

/* Hinzufügen der Oberfläche zum Zeichnen des Graphen */
draw := gtk.DrawingAreaNew()
grid.Attach(draw, 2, 0, 4, 4)

/* Hinzufügen eines Buttons */
g.btnDeleteEdge = gtk.ButtonNewWithLabel("Delete Edges")
grid.Attach(g.btnDeleteEdge, 0, 1, 2, 1)

/* Hinzufügen weiterer GUI-Elemente */
...
/* Grid zum Fenster hinzufügen */
win.Add(grid)

Event-Handler Funktionen

Die Event-Handler-Funktion, die bei einem Button Click aufgerufen wird, kann man wie folgt hinzufügen:

g.btnDeleteEdge.Connect("clicked", onBtnDeleteEdgeClick, g)

Indem man eine Funktion in das draw-Event der Zeichenoberfläche einklinkt, kann man die das Zeichnen selbst bestimmen:

draw.Connect("draw", onDrawEvent, g)

Im onDrawEvent werden dann die Nodes und Edges des Kanten regelmäßig neu gezeichnet und bei Benutzereingaben aktualisiert:

func onDrawEvent(da *gtk.DrawingArea, cr *cairo.Context, g *Gui) {
    /* Zeichnen aller Nodes und definition der Farbe je nach Zustand */
    for _, point := range g.Nodes {
		cr.SetSourceRGB(0, 0, 0)
		if point.IsSelected {
			cr.SetSourceRGB(1, 0, 0)
		}
		cr.Rectangle(point.X-xOff, point.Y-yOff, g.UnitSize, g.UnitSize)
		cr.Fill()
		cr.MoveTo(point.X-xOff, point.Y-yOff)
		cr.SetSourceRGB(0, 0, 1)
		cr.ShowText(fmt.Sprintf("%v", point.IndexIn(g.Nodes)))
	}
    /* Zeichnen der Kanten die zwei Nodes verbindet... */
}

“Ameisenalgorithmus”

Der Ameisenalgorithmus, wie der Name schon erwähnt, wurde mit Hilfe der Ameisen als Vorbild kreiert. Ameisen scheiden bei ihrer Futtersuche einen Duftstoff, auch Pheromon genannt, aus. An diesem Duftstoff können sich die anderen Ameisen orientieren. Weist ein Weg eine hohe Pheromonkonzentration auf, werden mehr Ameisen diesen Weg benutzen, da er anscheinend eine relativ kurze Strecke bzw. gute Strecke vom Start zur Futterquelle ist.

Umso kürzer bzw. umso direkter ein Weg zum Ziel ist, desto mehr Ameisen können in selber Zeit zur Futterquelle und wieder zurück. Daraus lässt sich schließen, dass dieser Weg eine hohe Pheromonkonzentration aufweisen muss, da alle Ameisen währenddessen ihren Duftstoff hinterlassen haben und desto mehr Ameisen werden diesen “besseren” Weg nutzen, bis zufällig ein besserer Weg gefunden wird. Die Duftstoffe werden mit der Zeit auch immer schwächer, wenn ein Weg nicht mehr wirklich benutzt wird, d.h. die Wahrscheinlichkeit wird immer geringer, dass dieser Weg ausgewählt wird von den Ameisen.

Funktionsweise

Dieses Konzept wollen wir auch in unserer Routenfindung einsetzen.

Jede Kante bekommt eine eigene Pheromonkonzentration zugewiesen. Dieser gibt an, mit welcher Wahrscheinlichkeit unser Algorithmus diesen Weg einschlagen wird. Umso höher der Wert, desto wahrscheinlicher wird diese Kante ausgewählt. Zu Beginn haben alle Kanten die gleiche Konzentration, d.h. alle Kanten werden mit gleicher Wahrscheinlichkeit ausgewählt. Ausgewählte Kanten werden dementsprechend erhöht und alle Kanten werden mit der Zeit verringert, um die Pheromone wiederzuspieleln. Das Ganze wird in meheren Iterationen wiederholt, um so eine möglichst gute (nicht optimalste!) Route zu finden. Das Konzept findet in relativ kurzer Zeit eine gute Lösung.

Um eine Route zu bilden wird dieser Algorithmus wie folgt ausgeführt:

1. Starte bei einem zufälligen ausgewählten Punkt der gewünschten angegebenen Route
2. Ermittle die Pheromonkonzentration aller Kanten von diesem Punkt zu allen anderen restlichen Zielpunkten
3. Wähle mit einer zufälligen Wahrscheinlichkeit, die die Pheromonkonzentration angibt, eine von diesen Kanten aus
4. Starte bei neuem ausgewählten Punkt erneut die Schritte 2.-3. solange, bis alle gewünschten Punkte der Route durchlaufen worden sind
5. Füge zum Schluss noch den Startpunkt am Ende hinzu, um eine geschlossene Route zu bilden

for idx, node := range tourNodes {
	antTours[idx] = calcAntTours(node, tourInfo, pheromonMap, distMap)
}

//Calculates one random tour with given startpoint
//startNode - begin of tour
//tourInfo - struct with the information about the connections, etc
//pherom - map with the pheromonevalues
//dist - map with the distances for each node
func calcAntTours(startNode int, tourInfo tourInformations, pherom map[string]float64, dist map[string]int) []int {

	antTours := make([]int, len(tourInfo.targetNodes)+1)
	antTours[0] = startNode
	currentNode := startNode

	for k := 1; k < len(antTours)-1; k++ {
		pNiv := make([]float64, len(antTours)-1)
		var sum float64

		for j, adjNode := range tourInfo.targetNodes {
			isIn, _ := inArray(adjNode, antTours)
			if !isIn && currentNode != adjNode {
				pheroAlpha := math.Pow(getPheromoneMapValue(pherom, currentNode, adjNode), alpha)
				adjBeta := math.Pow(float64(getDistMapValue(dist, currentNode, adjNode)), beta)
				pNiv[j] = pheroAlpha / adjBeta

				sum += pNiv[j]
			} else {
				pNiv[j] = 0
			}
		}
		for idx, val := range pNiv {
			pNiv[idx] = val / sum
		}

		//randVec is a vector that contains the node that we want to choose a random connection from the current node
		randVec := make([]int, 100)

		i := 0
		for idx, node := range tourInfo.targetNodes {
			pNivChance := int(math.Round(pNiv[idx] * 100))
			for k := 0; k < pNivChance; k++ {
				if i+k < 100 {
					randVec[i+k] = node
				}
			}
			i += pNivChance
		}
		rand.Seed(time.Now().UnixNano())
		currentNode = randVec[rand.Intn(99)]
		antTours[k] = currentNode

	}
	antTours[len(antTours)-1] = startNode
	return antTours
}

Die Pheromonkonzentration wird dann nachher anhand der berechneten Route geupdated.

for idx := range antTours {
	dist[idx] = calcDistForTour(distMap, antTours[idx])
}

idx, minVal := minDistAt(dist)

if bestDistance > minVal {
	bestTour = antTours[idx]
	bestDistance = minVal
}

updatePheromoneMap(bestTour, pheromonMap)

Dafür sind spezielle Variablen definiert worden, um die Erhöhung und Verminderung der Pheromonkonzentration, Anzahl an Iterationen, etc zu beschreiben.

//CONSTANTS

//ALPHA : How much influence should the pheromones have on the calculation?
const alpha = 1.0

//BETA : How much influence should the distances have on the calculation?
const beta = 1.0

//RHO : How much influence should the evaporation have on the (pheromone)matrix?
const rho = 0.5

//DELTA : How high should the bonus be that will be assigned to the best tour on the (pheromone)matrix?
const delta = 0.5

//MAX_ITERATION : The maximum number of iterations you want to make.
const maxIteration = 10

In dieser Implementation werden alle gewünschten Punkte dem Algorithmus übergeben, so dass wir am Ende einer Iteration n (#gewünschter Punkte) verschiedene Routen besitzen. Diese werden auf ihre Gesamtstrecke überprüft. Die mit der kürzesten Gesamtstrecke wird als finale Route dieser Iteration abgespeichert. Dessen Pheromonkonzentration wird ebenfalls erhöht und im Anschluss werden alle Pheromonkonzentrationen noch verringert. Dies Wiederholt man solange, bis man die maximale definierte Iterationgrenze oder ein anderes Abbruchkriterium erreicht hat.

Zum Schluss hat man die finale Route abgespeichert, mit der derzeit kürzesten/optimalsten gefundenen Gesamtstrecke.