Hallo,
freut mich, dass Du Interesse hast.
Zum evolutiven Modell der Optimierung:
Optimiert werden sollen die Schaltphasen der Ampeln, um einen möglichst guten Verkehrsfluß zu erreichen (also wenig Standzeiten, wenig stop-and-go, hohe mittlere Geschwindigkeit).
Zunächst mußt du die Zielgröße vernünftig festlegen. Die drei o.g. Kriterien spielen wohl sicher eine Rolle, wobei sich das letztgenannte eigentlich aus den beiden anderen ergibt. Diese Zielgröße soll dann minimiert (bzw. maximiert - je nach Definition) werden.
Dann musst du die Schaltphasen der Ampeln, ihre Reaktionszeiten auf herannahende bzw. wartende Fahrzeuge („Kontaktschwellen“) und - was nicht ganz einfach ist - ihre Interaktionen („Grüne Welle“) so programmieren, dass das Verhalten parametrisiert ist (also wählbare Parameter für alle wichtigen Eigenschaften der Ampelschaltung). Ich will als weiterführenden Tipp noch die Messung der Verkehrsdichte geben: In der rush hour könnte für die Ampel der Hauptstraße zB. eine längere Grünphase auch dann insgesamt den Verkehrsfluß verbessern, wenn gerade mal kein Auto kommt.
Diese Amplen stehen natürlich an Kreuzungen. Du brauchst also ein Modell von Straßen und Kreuzungen, auf denen der Verkehr fließen soll. Das geht vom einfachen Modell einer Kreuzung über eine Kreuzung mit schaltbarer Fußgängerampel bis hin zu einem System von Straßen durch eine Stadt mit Ein- und Ausfallstraßen, Wohngebiet, Industriegebiet und Einkaufszentrum.
Aus diesen Straßen fahren Fahrzeuge. In der Simulation setzt du im Rahmen der Modellvorgaben Fahrzeuge zufällig mit zufälligem Start- und Zielpunkt auf die Straße. Bei Alternativen Wegen kannst du für das Fahrzeug würfeln, welchen weg es nimmt (dabei muß es nicht eine 1:1 Chance für die Alternativen geben). Die Fahrzeuge müssen beschleunigen und verzögern, je nach Verkehrslage und eben Ampeln. Das ist nicht einfach, denn jedes Fahrzeug muss erkennen, welches Fahrzeug vor ihm fährt und in welchem Abstand. Bedenke, eine Reaktionszeit einzubauen beim Gasgeben und beim Bremsen. Tipp: Ein guter Ansatz ist schonmal, den (minimalen) Abstand zum vorausfahrenden Fahrzeug von der eigenen Geschwindigkeit abhängig zu machen. Das ergibt schon eine realistische Modellation des Verhaltens an Ampeln. Bedenke auch, dass ein abbiegendes Fahrzeug vor der Kurve verzögert, langsam abbiegt und dann wieder beschleunigt. Dieser ganze Teil mit den Autos ist programmtechnisch einer der anspruchsvollsten!
Die Gesamtheit aller Straßen, Ampeln, Fahrzeuge und Einstellungen für die Parameter zur Wahl von Start- und Zielpunkten der Autos nenne ich „Szenario“.
Jetzt erst kann man an’s Optimieren gehen.
Du nimmst dein Szenario, stellst die Parameter für alle Ampeln ein und lässt für eine bestimmte Zeit Fahrzeuge fahren, wobei du die jeweiligen Standzeiten und mittleren Geschwindigkeiten auszeichnest. Am ende der Simulation berechnest du die Zielgröße. Das machst du nicht nur einmal, sondern so oft wie möglich (sagen wir N mal; N>50 wäre gut), und zwar jedes mal mit etwas anderen Parameterwerten für die Ampeln. Wie stark die Parameter dabei variieren sollten, ist Erfahrungssache, da mußt du experimentieren. Diese N Simulationen sind jetzt praktisch N Individuen einer Population. Die Gesamtheit der Parameterwerte einer Simulation entspricht dem Genom des Individuums. Die Zielgröße ist ein Maß für die „biologische Fitnes“ des Individuums und damit für den Reproduktionserfolg. Genau das machen wir jetzt: Die fittesten n der insgesamt N Simulationen werden ausgewählt („Selektion“).
Im einfachen Fall ohne Sex werden nun ausgehend von den n Simulationen wieder N durchgeführt. Die Anzahl der neuen Simulationen mit den Parameterwerten der i. ausgewählten Simulation sollten der relativen Fitness der i. Simulation entsprechen. Als Beispiel: Es wurden n=3 aus N=50 Simulationen gewählt. f1,f2,f3 sind die Fitnesswerte, F ist die Summe f1+f2+f3, dann sind r1=f1/F, r2=f2/f und r3=f3/F die relativen Fitnesswerte. In der neuen Generation bekommen also r1*N Simulationen die Parameter der 1. ausgew. Simulation, r2*N die der 2. und r3*N die der 3. (jeweils als ganzzahlige Größen). Klar?
Bei der Zusammenstellung der neuen Generation werden nun alle Parameter ein wenig verändert („Mutation“). Die Stärke der Änderung kann eine Konstante sein, besser ist es aber, sie bei jeder Generation etwas zu verringern, damit die Optimierung konvergiert. Man könnte die Anderungsstärke auch von der Homogenität der Fitnesswerte abhängig machen…
Mit Sex wird die Sache etwas komplexer: Nach der Selektion folgt die Rekombination, also das Mischen von Teilen der Genome. Regeln dafür gibt es auch wieder beliebig viele. Ein Vorschlag: Für jedes der n ausgew. Individuen: Nimm einen zufälligen Anteil (in der Größe aber 50%) der Parameterwerte und ersetzte diese durch die entsprechenden Parameterwerte eines zufällig ausgewählten der anderen (n-1) Individuen. Wiederhole das ri*N mal für das i. Individuum. So bekommst du N neue Individuen mit gemischten Genomen, die dann auch wieder mutiert werden.
Neue Generation - neues Glück: wieder werden die Simulationen durchgeführt, die Fittness berechnet, die n besten ausgewählt usw.
Stelle dar, wie sich die Fittness von Runde zu Runde verändert. Brich ab, wenn die Änderungen vernachlässigbar werden.
Zum letzten Punkt: Was ein Szenario ist, habe ich ja erklärt. Damit sollte auch klar sein, was ich unter dem letzten Punkt verstehe.
Beste Grüße und viel Erfolg,
Jochen
