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

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

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

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.

Modellparameter Die Modellparameter ermöglichen es dem Benutzer des Modells verschiedene Szenarien und Umgebungen zu charakterisieren. Folgende Parameter stehen in diesem Modell zur Verfügung:

Für alle Fahrzeuge

Page 16

KAPITEL 2. SIMULATION 16

kunde Null bis Sekunde r. Ab Sekunde r wird für eine kurze Zeitspanne z in beide Richtungen rot signalisiert. Ab Sekunde r+z ist in West-Ost-Richtung Grün-Phase bis Sekunde r+z+g. Danach ist bis r+z+g+z wieder in beide Richtungen Rot-Phase. Anschließend beginnt der Zyklus von neuem. Die Phasen in Nord-Süd-Richtung ergeben sich entsprechend. Die Sperrzeit z für beide Fahrtrichtungen modelliert die bei realen Kreuzungen verwendete Verzögerung der Freigabezeit für die neue Fahrtrichtung. In Abbildung 2.5 auf der nächsten Seite ist ein Diagramm zu sehen, welches diesen Zyklus veranschaulicht.

2.2.2 Grenzen, Einschränkungen und Erweiterbarkeit

Erweiterbarkeit Eine unmittelbare Erweiterbarkeit des Modells ist insofern gegeben, als es ohne größere Änderungen möglich ist, weitere Straßen und Kreuzungen an das in Abbildung 2.1 auf Seite 11 skizzierte Modell „anzuhängen“. Dabei ist strikt darauf zu achten, daß zwischen zwei Straßen immer eine Kreuzung sein muß und an Kreuzungen immer vier Straßen münden müssen. Eine Änderung des Kreuzungstyps - etwa eine T-Kreuzung ist zunächst nicht vorgesehen. Ebenso werden vom Modell bislang weder mehrere Spuren in einer Fahrtrichtung noch von Lichtzeichenanlagen abweichende Verkehrsleitzeichen unterstützt.

Mit etwas Entwicklungsaufwand sind derartige Erweiterungen jedoch jederzeit realisierbar. Um etwa eine Rechts-vor-Links Regelung einzuführen oder eine ausgefallene Ampel zu modellieren, ist lediglich ein Umschreiben der Klasse „Crossings“ notwendig. Die anderen Klassen des Modells wären von dieser Änderung nicht betroffen.

Modellvalidierung Die physikalische Korrektheit ist durch Abstraktion ein- geschränkt, da bei der Erstellung eines Modells generell auf viele Aspekte der

Page 17