Wer hat noch nicht vor einer roten Ampel gestanden und sich gefragt, ob sich das ständige Warten nicht verkürzen ließe durch eine günstigere Ampelschaltung? Diese Fragestellung wird in der vorliegenden Arbeit am Beispiel eines Straßenzugmodells aufgegriffen.
Mit Hilfe eines Systems zur verteilten simulationsbasierten Optimierung mittels Genetischer Algorithmen werden die Ampelphasen des Modells optimiert.
Ein Straßenzug sowie der Verkehr darauf läßt sich mit Hilfe eines Modells im
Rechner darstellen. Mit Hilfe von Parametern kann die Schaltung der Ampeln
im Modell gesteuert werden. Nach einem Simulationslauf ist bekannt, wie gut
oder schlecht sich das Modell mit den gegebenen Parametern entwickelt hat.
Dieses Ergebnis kann von einem Optimierungsverfahren verwendet werden,
um bessere Parameter zu entwickeln. Die Simulation einer Vielzahl solcher
Straßenzug-Modelle ist relativ zeitaufwendig, bei den verwendeten Optimierungsverfahren aber unumgänglich. Verteilt man die Berechnung auf mehrere Rechner, ergibt sich eine nahezu lineare Beschleunigung gegenüber der Berechnungszeit auf einem Rechner. Daher ist eine Verteilung der Berechnungen auf mehrere Rechner erstrebenswert. Zur verteilten Optimierung bieten sich Genetische Algorithmen besonders an. Sie sind robuste, problemunabhängige heuristische Optimierungsverfahren.
Bevor näher auf Genetische Algorithmen und ihre Anwendung zur Lösung
der oben genannten Fragestellung eingegangen wird, soll zunächst im Folgenden die Problemstellung nächer beleuchtet werden.
Inhaltsverzeichnis
1 Einführung
1.1 Begriffe aus der Verkehrsplanung
1.2 Problemstellung
1.3 Überblick über bisherige Lösungsansätze
2 Simulation
2.1 Grundlagen
2.1.1 Begriffsdefinitionen
2.1.2 Das Simulations-Framework DESMO-J
2.2 Modell eines Straßenzuges mit Ampeln und Nebenstraßen
2.2.1 Beschreibung des Modells
2.2.2 Grenzen, Einschränkungen und Erweiterbarkeit
2.2.3 Klassendiagramm des Modells
3 Optimierung
3.1 Probleme und Lösungsverfahren
3.1.1 Optimierungsprobleme
3.1.2 Lösungsverfahren für diskrete Optimierungsprobleme
3.2 Genetische Algorithmen
3.2.1 Einführung
3.2.2 Vorbild Natur
3.2.3 Problemspezifische Kodierung
3.2.4 Ablauf eines einfachen GA
3.2.5 Kodierung
3.2.6 Das Gütemaß
3.2.7 Genetische Operatoren
3.2.8 Konvergenz
3.2.9 Variationen des einfachen GA
3.3 Theoretischer Hintergrund
3.3.1 Schemata
3.3.2 Hypercubes
3.3.3 Das Schema Theorem
3.3.4 Folgerungen
4 Simulationsbasierte Optimierung
4.1 Parameter
4.2 Verwendete Genetische Algorithmen
4.3 DISMO
4.4 Ergebnisse der Optimierungsläufe
4.5 Bewertung
4.6 Ausblick
Zielsetzung & Themen
Die vorliegende Arbeit untersucht die Optimierung von Ampelphasen in einem Verkehrsmodell mittels genetischer Algorithmen. Das primäre Ziel besteht darin, durch eine verteilte simulationsbasierte Optimierung eine möglichst effiziente Verkehrssteuerung ("Grüne Welle") zu erreichen und die resultierenden Wartezeiten sowie Fahrzeiten für die verschiedenen Verkehrsteilnehmer zu minimieren.
- Simulationsbasierte Modellierung von Straßenzügen mit Ampelsteuerung
- Einsatz und Vergleich verschiedener genetischer Algorithmen zur Parameteroptimierung
- Verteilte Optimierung mittels des Frameworks DISMO
- Analyse der Auswirkungen von Optimierungskriterien (Reisezeit vs. Wartezeit)
- Untersuchung der Konvergenz und Effizienz der gewählten Algorithmen
Auszug aus dem Buch
3.2.1 Einführung
In Nachahmung genetischer Prozesse biologischer Organismen sind Genetische Algorithmen (GA) eine heuristische Methode, die zur Lösung von Optimierungsproblemen verwendet werden kann. Über viele Generationen hinweg entwickeln sich natürliche Populationen nach den von Charles Darwin bekannten Prinzipien der „natürlichen Mutation und Selektion“. Indem Genetische Algorithmen diese Prinzipien imitieren, sind sie in der Lage, Lösungen zu schwierigen Problemen zu finden.
In der Natur stehen die Individuen einer Population miteinander in ständigem Wettbewerb um die Ressourcen, die sie zum Leben benötigen. Die Mitglieder einer Spezies ringen zudem miteinander um die besten Fortpflanzungspartner. Diejenigen Individuen, die am erfolgreichsten sind in ihrem Bemühen zu überleben und sich fortzupflanzen, werden im Vergleich zu den Schlechteren ein höhere Anzahl an Nachkommen. Dies bedeutet, daß sich die Gene der am besten angepassten Individuen über die Generationen hinweg in einer ansteigenden Zahl von Mitgliedern der Population befinden werden. Die Kombination von Genen einzelner guter Individuen wird auch zu solchen Nachfahren führen, die besser als Ihre Vorfahren an die Umweltbedingungen angepaßt sind. Durch die Wiederholung dieses Vorganges kommt es, daß sich eine ganze Population mit der Zeit immer besser an die Umwelt anpasst.
Zusammenfassung der Kapitel
1 Einführung: Grundlegende Begriffe der Verkehrsplanung werden definiert und die Problemstellung der Ampelphasenoptimierung sowie bisherige Lösungsansätze erläutert.
2 Simulation: Einführung in die Grundlagen der diskreten Simulation und Beschreibung des Modells eines Straßenzuges unter Verwendung von DESMO-J.
3 Optimierung: Vermittlung theoretischer Grundlagen zu Optimierungsproblemen, Vorstellung genetischer Algorithmen als heuristisches Verfahren sowie Erläuterung des Schema-Theorems.
4 Simulationsbasierte Optimierung: Praktische Anwendung und Evaluation der Algorithmen zur Parameteroptimierung am Straßenzugsmodell mittels des verteilten Systems DISMO.
Schlüsselwörter
Genetische Algorithmen, Verkehrssimulation, Ampelsteuerung, Grüne Welle, Parameteroptimierung, DISMO, DESMO-J, Optimierungsprobleme, Selektion, Rekombination, Mutation, Verkehrsplanung, Simulationsmodell, Fitnessfunktion, Konvergenz
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Es geht um die Anwendung von genetischen Algorithmen zur Optimierung von Ampelsteuerungen in einer simulierten städtischen Straßenumgebung, um den Verkehrsfluss zu verbessern.
Was sind die zentralen Themenfelder der Arbeit?
Die zentralen Themen sind die diskrete Simulation von Verkehrsflüssen, die Theorie und Anwendung genetischer Algorithmen sowie verteilte Systeme zur Optimierung von Simulationsparametern.
Was ist das primäre Ziel der Forschungsarbeit?
Das Ziel ist es, durch eine effiziente Parameterwahl der Lichtzeichenanlagen die durchschnittliche Reisezeit der Fahrzeuge auf einem Straßenzug zu minimieren und gleichzeitig Wartezeiten an Ampeln zu reduzieren.
Welche wissenschaftliche Methode wird primär verwendet?
Die Arbeit nutzt Simulations-Frameworks (DESMO-J) in Kombination mit heuristischen Optimierungsverfahren, speziell verschiedenen Ausprägungen genetischer Algorithmen (einfacher GA, generationaler GA, parameterloser GA).
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die Modellierung des Straßenzugs mit DESMO-J, die mathematisch-theoretische Einführung in die Optimierung und das Schema-Theorem sowie die konkrete Durchführung und Bewertung der Optimierungsläufe.
Welche Schlüsselwörter charakterisieren die Arbeit?
Schlüsselwörter wie Genetische Algorithmen, Verkehrssimulation, Ampelsteuerung, Parameteroptimierung und diskrete Simulation beschreiben den methodischen und inhaltlichen Kern.
Wie trägt das System DISMO zur Lösung bei?
DISMO ermöglicht die verteilte Durchführung der rechenintensiven Simulationsläufe auf mehreren Rechnern, was eine nahezu lineare Beschleunigung der Optimierungsprozesse erlaubt.
Welche Rolle spielt das "Schema-Theorem" für die Arbeit?
Das Schema-Theorem bildet die theoretische Basis zum Verständnis, warum genetische Algorithmen erfolgreich nach guten Lösungsklassen (Schemata) innerhalb des Suchraums suchen.
- Quote paper
- Diplom Informatiker Holger Hartmann (Author), 2002, Genetische Algorithmen zur Parameteroptimierung von Simulationsmodellen am Beispiel einer "Grünen Welle" entlang einer Hauptverkehrsstraße, Munich, GRIN Verlag, https://www.grin.com/document/81476
