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

Holger Hartmann

• Herausgeber: GRIN Verlag
• Sprache: Deutsch

Veröffentlichungsjahr: 2012

Beschreibung

Studienarbeit aus dem Jahr 2002 im Fachbereich Informatik - Angewandte Informatik, Note: 0, Universität Hamburg, Sprache: Deutsch, Abstract: 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.

Leseprobe

Inhaltsverzeichnis

Kapitel

1.1 Begriffe aus der Verkehrsplanung

1.2 Problemstellung

1.3 Überblick über bisherige Lösungsansätze

2.1 Grundlagen

2.1.1 Begriffsdefinitionen

2.1.2 Das Simulations-Framework DESMO-J

2.2.1 Beschreibung des Modells

2.2.2 Grenzen, Einschränkungen und Erweiterbarkeit

2.2.3 Klassendiagramm des Modells

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.1 Parameter

4.2 Verwendete Genetische Algorithmen

4.3 DISMO

4.4 Ergebnisse der Optimierungsläufe

4.5 Bewertung

4.6 Ausblick

Page 1

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].

LichtzeichenanlageEine 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 2

KAPITEL 1. EINFÜHRUNG2

LichtsignalEin Lichtsignal ist ein farbiges Lichtzeichen einer Lichtzeichenanlage, das in den Farben grün, gelb, rot sowie rot und gelb (zusammen) vorkommt.

SignalzeitAls Signalzeit bezeichnet man die Zeit in Sekunden, während der die Lichtzeichenanlage ein bestimmtes Signal zeigt.

SignalzeitenplanEin Signalzeitenplan ist ein Plan, der angibt, zu welchem Zeitpunkt an einer Lichtzeichenanlage und in welcher zeitlichen Reihenfolge ein bestimmtes Signal angezeigt wird.

PhaseUnter einer Phase versteht man denjenigen Teil einer Signalprogrammes, während dessen ein bestimmter Zustand der Signalisierung einer Lichtsignalanlage unverändert bleibt.

Freigabezeit oder GrünzeitMit Freigabezeit bezeichnet man die Zeit, während der eine Lichtzeichenanlage „GRÜN“ zeigt.

SperrzeitUnter Sperrzeit versteht man die Zeit in Sekunden, während der eine Lichtzeichenanlage „ROT“ zeigt.

Umlaufzeit oder ZykluslängeDie Umlaufzeit ist die Periodendauer für eine Lichtzeichenanlage.

ZyklusMit Zyklus bezeichnet man die Abfolge der verschiedenen Phasen des Signalprogrammes einer Lichtzeichenanlage.

SignalprogrammAls Signalprogramm bezeichnet man die zeitliche Verteilung der Signalzeiten für eine Lichtzeichenanlage. Das Signalprogramm ist eine zeitlich wiederkehrende Folge von Signalen, die an den einzelnen Sichtzeichenanlagen einer Kreuzung angezeigt wird. Es besteht in der Regel aus der Umlaufzeit, der Anzahl und Art der Phasen, der Phaseneinteilung und deren zeitlicher Abfolge sowie der Dauer der Freigabezeiten.

Phasenverschiebung oder VersatzzeitHiermit wird die zeitliche Verschiebung zwischen den Startzeitpunkten der Signalprogramme zweier Lichtzeichenanlagen bezeichnet.

Grüne WelleAls Grüne Welle bezeichnet man eine Schaltung von Lichtzeichenanlagen entlang einer bestimmten Strecke oder eines Straßenzuges so, daß die Verkehrsteilnehmer diese Strecke ohne anzuhalten mit konstanter Ge- schwindigkeit durchfahren können.

Page 3

1.2. PROBLEMSTELLUNG3

HaltelinieDie 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.

StauraumAls 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ßeMit Straße bezeichnet man einen Verkehrsweg, auf dem sich Fahrzeuge in eine bestimte Richtung bewegen.

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

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

VerkehrsstromAls 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ÜHRUNG4

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.

AlsZiele des Verkehrsplanerskö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 einemOptimierungslaufsind 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 KnotenpunktenNach [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:

VersatzzeitreduzierungDie Reduzierung der Versatzzeit zur nachfolgen-