Genetische Algorithmen zur Parameteroptimierung von Simulationsmodellen am Beispiel einer "Grünen Welle" entlang einer Hauptverkehrsstraße


Studienarbeit, 2002

66 Seiten, Note: 0


Leseprobe

Page 1


Kapitel 1

Einführung

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.

1.1 Begriffe aus der Verkehrsplanung

Um Unklarheiten zu vermeiden, werden nachfolgend verschiedene Begriffe definiert. Sie entsprechen zum großen Teil den Festlegungen in [Ian94, S. 5ff].

Lichtzeichenanlage Eine Lichtzeichenanlage, im allgemeinen Sprachgebrauch auch Ampel genannt, ist eine technische Einrichtung, die durch Lichtsignale gemäß §37 StVO an Kreuzungen, Einmündungen oder anderen Straßenstellen den Verkehr regelt.

Page 3


1.2. PROBLEMSTELLUNG 3

Haltelinie Die Haltelinie gibt an einer durch Lichtzeichenanlagen geregelten Kreuzung die Stelle an, an der das erste wartende Fahrzeug zu halten hat, wenn diese Lichtzeichenanlage “ROT"´ signalisiert.

Stauraum Als Stauraum bezeichnet man den Raum vor einer Kreuzung, in dem Fahrzeuge während der Sperrzeit vor einer Lichtzeichenanlage auf das Freigabesignal warten. Er erstreckt sich von der Haltelinie bis zur davorliegenden Kreuzung.

Straße Mit Straße bezeichnet man einen Verkehrsweg, auf dem sich Fahrzeuge in eine bestimte Richtung bewegen.

Fahrstreifen oder Spur Der zum ungehinderten Fahren eines Fahrzeuges benötigte Teil der Straße ist der Fahrstreifen.

Kreuzung Eine Kreuzung ist ein Ort, an dem mindestens zwei Straßen zusammengeführt werden.

Verkehrsstrom Als Verkehrsstrom bezeichnet man eine Anzahl von Fahrzeugen, die sich auf einer Straße bewegen.

1.2 Problemstellung

Der Verkehrsplaner eines innerstädtischen Straßennetzes hat dafür zu Sorgen, daß der gesamte Verkehr möglichst reibungslos fließt. Besonders zu den sogenannten Stoßzeiten, dem morgendlichen und abendlichem Berufsverkehr, ist dies keine einfache Aufgabe. Ein ihm zur Verfügung stehendes Instrument zur kurzfristigen Steuerung des Verkehrsstroms sind die Lichtzeichenanlagen. An Stellen mit besonders hohem Verkehrsaufkommen ist es sicher sinnvoll, durch die Koordination der Lichtzeichenanlagen, eine Grüne Welle einzurichten. Typischerweise sind die Zentren besonders hohen Verkehrsaufkommens zu den Stoßzeiten die Straßen, welche das Stadtzentrum mit den Randbezirken verbinden. Nachdem der Verkehrsplaner auf diesen Hauptverkehrsstraßen eine Güne Welle eingerichtet hat, stellt sich natürlich die Frage, wie störungsfrei der Verkehrsfluß in der Gegenrichtung verläuft. Bei einer eingerichteten Grünen Welle auf einer Hauptverkehrsstraße muß die Gegenrichtung keinen optimalen Verkehrsfluß mehr aufweisen. Wie stark ist die Benachteiligung dieser Minderheit an Verkehrsteilnehmern? Falls die Benachteiligung dieser Verkehrsteilnehmer zu stark ausfällt, muß der Verkehrsplaner zur Erreichung eines optimalen Verkehrsflusses diese mit ins Kalkül aufnehmen. Schließlich müssen noch die Verkehrsteilnehmer der in die Hauptverkehrsstraße einmündenden Straßen bedacht werden.

Ianigro führt in [Ian94] eine Untersuchung verschiedener Optimierungskriterien zur Steigerung der Qualität des Verkehrsflußes an. Darin werden als be- sonders maßgeblich die Kriterien Reisezeit, Summe der Wartezeiten und die

Page 4


KAPITEL 1. EINFÜHRUNG 4

Anzahl der verkehrsbedingten Halte angesehen. Er kam zu dem Schluß, daß man sich auf die Minimierung der Reisezeit beschränken kann, da die anderen Kriterien sich mit der gleichen Tendenz ändern.

Als Ziele des Verkehrsplaners können daher die folgende Kriterien in der folgenden Reihenfolge festgehalten weden:

Minimierung der durchschnittlichen Fahrzeit der Fahrzeuge

 

image f1282e2a43ddedf5f7a7abe6e1947941

Zum Erreichen dieser Ziele wird das Problem der Optimierung der Signalprogramme der Lichtzeichenanlagen in mehrere Teilprobleme unterteilt:

Zunächst muß ein geeignetes Modell eines Straßenzuges gefunden wer-

 

den. Das verwendete Modell eines Straßenzuges mit vier Lichtzeichenanlagen wird nach einer kurzen Einführung in die Grundlagen der Simulation in Kapitel 2.2 auf Seite 10 beschrieben.

Ein geeignetes Optimierungsverfahren muss gefunden werden. Auf-

 

grund der breiten Anwendbarkeit könnte sich ein Genetischer Algorithmus für die gegebene Fragestellung gut eignen. In Kapitel 3 auf Seite 19 wird auf verschiedene Optimierungsmethoden hingewiesen und auf die Technik der Genetischen Algorithmen näher eingegangen.

Es müssen verschiedene Optimierungsläufe am Modell des Straßenzu-  

ges in verschiedenen Szenarien durchgeführt werden. Unter einem Optimierungslauf sind viele Optimierungsiterationen mit jeweils vielen Experimenten zu verstehen. Dies wird in Kapitel 4 auf Seite 43 beschrieben.

Schließlich wird in Kapitel 4.5 auf Seite 56 bewertet, inwieweit die Gene-

 

tischen Algorithmen in der Lage sind, die gegebenen Probleme zu lösen.

1.3 Überblick über bisherige Lösungsansätze

Staubekämpfung an Lichtsignalgesteuerten Knotenpunkten Nach [Ian94, S. 30f] gibt [Bie87] einige Hinweise zur Staubekämpfung an lichtsignalgesteuerten Knotenpunkten. Dabei werden maximal zwei hintereinander liegende Kreuzungen betrachtet. Die untersuchten Maßnahmen sind:

Versatzzeitreduzierung Die Reduzierung der Versatzzeit zur nachfolgen-  

den Lichtzeichenanlage wird dahingehend untersucht, ob sie das Problem lösen kann, wenn an einer Kreuzung ein Rückstau entsteht, der so lang ist, daß er den Verkehrsablauf an einer davorliegenden Kreuzung behindert. Nach Ansicht des Autors muß in jedem Einzelfall geprüft werden, ob durch diese Maßnahme der Gegenverkehr zu stark behin- dert wird.

Page 7


Kapitel 2

Simulation

2.1 Grundlagen

Dieses Kapitel gibt eine kurze Einführung in die Grundbegriffe der Simulation. Kapitel 2.2 auf Seite 10 geht daran anschließend auf die Umsetzung eines konkreten Modells mit Hilfe von DESMO-J in Java ein. Eine detaillierte Einführung zu den Grundlagen der diskreten Simulation ist etwa in [Pag91] zu finden.

2.1.1 Begriffsdefinitionen

Was ist ein System?

„Die Umwelt des Menschen besteht nicht nur aus einer Anhäufung von Einzelobjekten, sondern auch aus einem Netz von Beziehungen, das die Objekte untereinander verbindet. Ausschnitte aus dieser Gesamtmenge der Objekte und Beziehungen werden vom Menschen abgegrenzt und als Systeme bezeichnet.“ [Pag91, S. 1]

Nach dieser Definition ist das größtmögliche System das Universum. Wann immer man einen Teil des Universums betrachtet und genau sagt, was zu diesem Teil gehört, was nicht und wie es mit seiner Umgebung interagiert, so hat man ein neues System definiert. Dieser Betrachtung liegt eine Hierarchie der Systeme zugrunde: Aus einem System kann man einen kleineren Teil betrachten, wodurch dieser als neues System definiert ist. Als Element eines Systems bezeichnet man ein als nicht weiter teilbar angesehenes Objekt eines Systems. Systeme stehen gewöhnlich mit ihrer Umgebung über ihren Systemeingang bzw. -ausgang in interaktiver Beziehung. Ein Beobachter kann von außen auf ein System einwirken und Änderungen der Ausgabe des Systems beobachten. Derartige Systeme bezeichnet man als offene Systeme. Geschlossene Systeme haben keine interaktive Beziehung mit der Umgebung. Sie sind meist gedankliche Vereinfachungen realer offener Systeme (vgl. [Pag91, S. 2-3]).

Was ist ein Modell? Ein Modell ist ein System, welches ein anderes System abstrahiert und idealisiert darstellt. Durch Modelle wird die Untersuchung

Page 10


KAPITEL 2. SIMULATION 10

vorhergesagt. Aus dieser Überlegung heraus ist es sicher ratsam, wo es geht, auf Simulation und die dadurch entstehenden zusätzlichen Schwierigkeiten zu verzichten. Stattdessen sollte man zunächst versuchen, analytische Techniken einzusetzen. Ihre Anwendungsgebiete sind wesentlich begrenzter. Aber dort, wo sie möglich sind, sollte man sie der Simulation vorziehen. In vielen Fällen ist jedoch Simulation das Mittel der Wahl - eventuell gemeinsam mit analytischen Ansätzen. Ohne Anspruch auf Vollständigkeit können gerade für die Verwendung von Simulation einige Gründe sprechen:

Das zu untersuchende System steht nicht zur Verfügung. Eventuell soll

 

es nach erfolgreicher Simulation überhaupt erst gebaut werden.

Das Experimentieren mit dem zu untersuchenden System ist zu gefähr-  

lich.

Die Kosten für ein Experiment am zu untersuchenden System sind zu

 

hoch.

Das Experiment am zu untersuchenden System dauert eine zu kurze

 

oder zu lange Zeitspanne.

Parameter des zu untersuchenden Systems sind nicht einstellbar oder

 

können nicht gut ermittelt werden.

In der Simulation können einzelne Effekte bewußt ausgeklammert oder

 

separat betrachtet werden, die im zu untersuchenden System nur gemeinsam auftreten.

2.1.2 Das Simulations-Framework DESMO-J

DESMO-J ist die Abkürzung von "Discrete Event Simulation and MOdeling in Java". Es ist ein Framework, daß aus einer Reihe von Java-Klassen besteht, welche die Entwicklung von Modellen zur Simulation unterstützen. Die für jede diskrete Simulation notwendigen Funktionalitäten wie Erzeugung von Zufallszahlen, Statistikfunktionen, Berichterstattung sowie Ablaufplanung der Simulation werden von DESMO-J bereitgestellt. Es sind verschiedene Modellierungskomponenten enthalten, die zur Erstellung des eigenen Modells verwendet werden können. Detaillierte Dokumentation sowie die DESMO-J Klassen können im Internet unter [PLCN00] eingesehen und herunter geladen werden.

Es wird sowohl der ereignis- als auch der prozeßorientierte Ansatz durch die DESMO-J Klassen unterstützt. Bei der Modellierung macht DESMO-J keinerlei Einschränkungen. Der volle Funktionsumfang von Java kann genutzt werden.

2.2 Modell eines Straßenzuges mit Ampeln und Neben-

straßen

Das nachfolgend beschriebene Modell eines Straßenzuges mit mehreren Am- peln und Nebenstrßen hat einen idealisierten Straßenzug zum Vorbild. Ziel

Page 11


2.2. MODELL EINES STRASSENZUGES MIT AMPELN UND NEBENSTRASSEN11

image 0e5514609c3784e091b6deb9daeeda0a

Abbildung 2.1: Das Modell des Straßenzuges mit vier Kreuzungen

des Modells ist es, für eine gegebene Belastung der verschiedenen Zufahrtswege durch Fahrzeuge die durchschnittliche Verweildauer der Fahrzeuge auf einigen Routen im Modell zu ermitteln. Durch geeignete Wahl der Modellparameter könnte das Modell an einen real existierenden Straßenzug angepaßt werden. Hierbei ist natürlich zu prüfen, ob die im Modell vorgenommenen Vereinfachungen die Realität ausreichend genau abbilden.

2.2.1 Beschreibung des Modells

Das Modell „Crossings“ ist unter Verwendung von DESMO-J in Java geschrieben. Wie in Abbildung 2.1 zu sehen ist, bildet das Modell vier einfache Straßenkreuzungen, die durch drei Straßen in gerader Linie verbunden sind, ab. Die so entstandene Achse liegt in West-Ost Richtung. Zu den übrigen Zufahrtsmöglichkeiten der Kreuzungen führt jeweils eine Straße. Der Eingang des Modells ist durch sogenannte „Auto-Erzeuger“ (bzw. „CarGenerator“) realisiert. Durch sie wird das Eintreten der Fahrzeuge in das System modelliert. Je einer steht am Anfang einer jeden Straße. Die Ausrichtung der Straßen an den Himmelsrichtungen ist gewählt worden, um eine eingängige Bezeichnungsweise der Straßen und Fahrtrichtungen zu ermöglichen.

Ende der Leseprobe aus 66 Seiten

Details

Titel
Genetische Algorithmen zur Parameteroptimierung von Simulationsmodellen am Beispiel einer "Grünen Welle" entlang einer Hauptverkehrsstraße
Hochschule
Universität Hamburg
Note
0
Autor
Jahr
2002
Seiten
66
Katalognummer
V186390
ISBN (eBook)
9783869437347
ISBN (Buch)
9783656993360
Dateigröße
8356 KB
Sprache
Deutsch
Schlagworte
genetische, algorithmen, parameteroptimierung, simulationsmodellen, beispiel, grünen, welle, hauptverkehrsstraße
Arbeit zitieren
Holger Hartmann (Autor), 2002, Genetische Algorithmen zur Parameteroptimierung von Simulationsmodellen am Beispiel einer "Grünen Welle" entlang einer Hauptverkehrsstraße, München, GRIN Verlag, https://www.grin.com/document/186390

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Genetische Algorithmen zur Parameteroptimierung von Simulationsmodellen am Beispiel einer "Grünen Welle" entlang einer Hauptverkehrsstraße



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden