====== Protokoll: ====== ===== Vorlauf für Formalitäten ===== Es musste sich darüber abgestimmt werden, wie das Programm agieren soll, aus welchen Bestandteilen es bestehen soll usw. ===== Donnerstag 3.12.2015 ===== - Um zuerst einmal eine Grundlage zu schaffen, wurde ein simples Auswertungsprogramm geschrieben. def auswertung(zreihe): verspaetung=0 for zug in zreihe: verspaetung=verspaetung+(zug["ankunft"]-zug["ankunftplan"]) return verspaetung - Dazu definierten wir zuerst die Variable //verspaetung//, die die Gesamtverspätung eines Fahrplans angibt. - Anschließend ließen wir die Verspätung für jeden Zug aus der Differenz von geplanter und tatsächlicher Ankunftszeit berechnen und addierten sie für alle Züge. - Danach erstellten wir ein Programm, um vorgefertigte Daten zu Zügen aus einer Textdatei einzulesen def einlesen(datei): text = open(datei, "r") zuege = list(text.read().split('\n')) #splittet Text in Zuege ausgabe = [] for zug in zuege: zug=list(zug.split(',')) #splittet Zuege in Zugdaten wbzug = {"vmax" : zug[0], "vist" : zug[1], "vziel" : zug[2], "abfahrt" : zug[3], "ankunft" : zug[4], "nummer" : zug[5], "ort" : zug[6], "beschl" : zug[7]} print wbzug ausgabe.append(wbzug) return ausgabe text.close() print einlesen("zuege.txt") - Zuerst wird eine Textdatei eingelesen. - Anschließend wird diese gesplittet, sodass jede Zeile einen Zug darstellt. - Dann wird jeder Zug erneut gespalten, um für jeden Zug eine Liste aus einzelnen Eigenschaften zu erhalten. - Danach erstellen wir ein Wörterbuch für jeden Zug, in dem jeder Eigenschaft der Name zugeordnet wird, unter der sie aufgerufen werden kann. - Die Wörterbücher aller Züge werden dann in der Liste //ausgabe// zusammengefasst - Außerdem haben wir ein Programm für einen Algorithmus, der alle Möglichkeiten für die Ankuftsmöglichkeiten und Verspätungen der Züge, geschrieben import itertools import simulation import auswertungsprogramm zug1={"vavg":20,"vist":20,"abfahrt":0,"besetzung":100,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":595,"ort":2000} zug2={"vavg":30,"vist":30,"abfahrt":2,"besetzung":50,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":123,"ort":0} zug3={"vavg":30,"vist":20,"abfahrt":4,"besetzung":20,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":987,"ort":0} zuege = [zug1, zug2, zug3] def bruteforce(zugliste): #minimumzeit = auswertungsprogramm.auswertung(list(itertools.permutations(zugliste)[1])) for perm in itertools.permutations(zugliste): # Permutationen werden ermittelt temp = simulation.simuliere(list(perm)) # Permutationen werden gefahren bruteforce(zuege) - Als drittes haben die schon vorhandenen Programme (Simulation, Auswertung, Algorithmus) ===== Donnerstag 10.12.2015 ===== - Programme wurden wieder zum Laufen gebracht - es wurde erreicht, dass der Algorithmus für das Durchprobieren die beste Möglichkeit und die dazugehörige Reihenfolge ausgibt - Ein neues Auswertungsprogramm wurde begonnen - Eine kurze Zusammenfassung der bereits vorhandenen Programme wurde erstellt ==== Programme und ihre Unterprogramme ==== * Simulation: * enthalten sind: Streckenoptionen bestehend aus: Länge, Abstand, Zugdichte. * Es kann (soll können): simulieren und auswerten * Algorithmus: * enthalten sind: * Es kann (soll können): einlesen * Masterprogramm: * liest die anderen Programme (Klassen) ein und gibt dann die "Lösung" und die Auswertung aus from auswertungsprogramm import auswertung #from awneu import auswertung from simulation import * from read import * from nfaq import * from tauschheuristik import * import time import logging import sys # create logger logger = logging.getLogger('simple_example') logger.setLevel(logging.DEBUG) # create console handler and set level to debug ch = logging.StreamHandler(stream=sys.stdout) ch.setLevel(logging.DEBUG) # create formatter formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s') # add formatter to ch ch.setFormatter(formatter) # add ch to logger logger.handlers=[] logger.addHandler(ch) fh=logging.FileHandler("mylog2.log") fh.setLevel(logging.DEBUG) # create formatter formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s') # add formatter to ch fh.setFormatter(formatter) # add ch to logger logger.addHandler(fh) ###### def timeit(method): def timed(*args, **kw): ts = time.time() result = method(*args, **kw) te = time.time() print "#####################" print '%r (%r, %r) %2.5f sec' % \ (method.__name__, args, kw, te-ts) print "#####################" return result return timed anschlussdaten = [{"minute": 0, "intervall": 20}, {"minute": 13, "intervall": 30}, {"minute": 42, "intervall": 60}] streckendaten = {"abstand": 1500, "streckenlaenge": 20000} # print(simulieren(folge,streckendaten["abstand"],streckendaten["streckenlaenge"]),anschlussdaten) #folge = tauschalgorithmus(reader("zuege.txt"),streckendaten, anschlussdaten) #simuliert = simulieren(folge, streckendaten["abstand"], streckendaten["streckenlaenge"]) @timeit def brutal(): return auswertung(simulieren(nfaq(reader("zuege.txt"),streckendaten, anschlussdaten)),anschlussdaten) @timeit def tausch(): #return auswertung(simulieren(tauschalgorithmus(reader("zuege.txt"),streckendaten, anschlussdaten, 50,3)),anschlussdaten) return auswertung(simulieren(tauschalgorithmus(reader("zuege.txt"),streckendaten, anschlussdaten, 50,3)),anschlussdaten) print(tausch()) print(brutal()) ===== Donnerstag 17.12.2015 ===== Heute haben wir die Zeit genutzt, um die Arbeit der letzten Wochen mithilfe von Code-Teilen in der Wiki zu dokumentieren.\\ Außerdem haben wir schon einen ersten Blick in das Buch **Automatische Erzeugung und Optimierung von Taktfahrplänen in Schienenverkehrsnetzen** geworfen. ===== Semesterferien ===== Jakob hat sich mit der Dissertation beschäftigt, die aufgrund ihrer Auslegung auf den ITF und die Erstellung von Taktknoten nur bedingt Hilfestellung für unsere Problemstellung liefert. Auf der Rückfahrt nach Berlin bot sich "dank" spielender Kinder im Gleisbereich der Geislinger Steige ein regelrechter Zugstau in und um Ulm Hbf, das optimale Anwendungsszenario für unser Programm. =====Donnerstag, 14.01.2016 ===== Nachdem aus ungeklärten Gründen nur ältere Versionen der Dateien verfügbar waren, war das Programm nicht mehr lauffähig. Deswegen wurden die Programmteile von Jakob weitestgehend neu geschrieben und um Funktionen erweitert. Das Programm ist nun in der Lage, alle Kombinationen stupide durchzurechnen und die beste Reihenfolge, so wie die Gesamtverspätung auszugeben. Die Rechnung mit der Gesamtreisezeitverlängerung kann nach der Fertigstellung dieses Moduls durch Ricardo ohne Probleme eingefügt werden. Es wurden erste Messungen durchgeführt, um zu zeigen wie schnell diese Methode an ihre Grenzen stößt. Hierzu wurden willkürliche Züge erstellt und die Rechenzeit gemessen (Ubuntu 15.10, i5-760)(Je nur ein Versuch. Deshalb nicht repräsentativ, aber als Größenordnung okay.): Mit Ausgabe: - 3 Züge: 0m00,073s - 6 Züge: 0m12,757s - 7 Züge: 2m04,064s - 8 Züge: 20m55,436s Das Einleseprogramm funktioniert nun auch wieder, aus bisher ungeklärten Gründen jedoch nicht in Verbindung mit dem Simulator. ===== Donnerstag, 21.01.2016 ===== Nächstes Ziel ist die Implementierung eines Tauschalgorithmus. Dieser wählt zwei zufällige Züge aus, tauscht deren Positionen aus und ermittelt, ob die neue Situation eine Verbesserung erzielt. Ist dem so, wird diese übernommen und der Algorithmus beginnt von vorne. Eine solche Tauschheuristik ist bei steigender Zugzahl sehr viel schneller als das Testen der n! Möglichkeiten. Wichtig für weitere Algorithmen ist folgendes Modell zur Vorstellung: Alle Möglichen Lösungen (=ausgewertete Zugreihenfolgen) befinden sich auf einer Ebene. Nun wird je nach "Score" der Auswertung diese Lösungen angehoben, es entsteht eine Hügellandschaft. Ziel eines jeden Algorithmus ist es nun, das "tiefste Tal", also den geringsten Verspätungswert zu erreichen. Große Gefahr besteht nun beim 2er-Tauschalgorithmus, in ein lokales Tal hineinzurutschen, da man aus ihm nie wieder hinaus gerät (Der Algorithmus geht ja nur Schritte bergab). Deshalb ist nächstes Ziel ein 3er-Tauschalgorithmus, der ggf. Optimierungen erzielen kann, die durch den 2er-Algorithmus nicht erreicht werden können. Beispiel der Effizienz des 2er-Algorithmus: ##################### 'tausch' ((), {}) 0.97001 sec ##################### 8409.2 ##################### 'brutal' ((), {}) 14.91523 sec ##################### 7184.0 ===== Donnerstag, 28.01.2016 ===== Ricardo hat am Auswertungsprogramm weiter gearbeitet. Jakob hat die Fehler im Einleseprogramm gefunden, Problem war eine Inkonsistenz der Typen. Die 3er- Tauscheuristik wurde beinahe fertiggestellt. ===== Donnerstag 4.02.2016 ===== auswertung_neu: def auswertung (ankunft, anschluss): #ZUWEISUNGEN summe = 0 #Summe der Wartezeiten key = "" #Umsteigeanteile auf Anschlusszuege for ank in ankunft: #fuer jeden ankommenden Zug for i in range (0,len(anschluss)): #gehe jeden Anschlusszug durch # ZUWEISUNGEN anschl = anschluss[i] key = "auf" + str(i+1) abfahrt = 0 #suche Zug, der als naechstes kommt n = 0 while ank["ankunft"] >= abfahrt: abfahrt = anschl["minute"] + n* anschl["intervall"] n = n+1 # BERECHNUNG time = (abfahrt - ank["ankunft"]) #Wartezeit pro Person summe += ank[key] * ank["besetzung"] * time # Umsteigeanteil * Personen im Ankunftszug * Wartezeit pro Person return summe Seit dem letzten Eintrag wurde die auswertung()-Funktion neu geschrieben. Zudem wurde das auswertung_neu-File um Funktionen wie die Ermittlung der maximalen Wartezeit, der gesamten Verspätung und der maximalen Verspätung erweitert. Jakob hat die 3er-Tauschheuristik prinzipiell fertig programmiert, welche 3 aufeinanderfolgende Züge nimmt, die beste Reihenfolge der drei Züge ermittelt, und dann diese wieder einsetzt. Eine andere Variante wäre, 3 komplett zufällige Züge zu wählen. Jedoch tauchte ein -bis dato ungelöster- Bug auf: Das Simulationsprogramm spielte absolut verrückt und ließ zB Züge fahren, die angekommen sind indem ihre Orte zurückgesetzt wurden und hängte sich in einer Endlosschleife auf, sämtliche Debug-Versuche schlugen fehl. Ruft man die Simulation von extern mit -identischen- Argumenten auf, funktioniert alles. ===== Donnerstag, 11.02.2016 ===== Aufgrund von mangelnder Priorität wurde das Debuggen zurückgestellt und Jakob hat sich dem "Simulated Annealing" angenommen. Wir erinnern uns zurück an das Modell der Landschaft: Der Algorithmus arbeitet nun ähnlich dem 2er-Tauschalgorithmus, mit einer entscheidenden Änderung: Ähnlich des Abkühlens von Metallen oder Kristallisierung ist es dem Algorithmus möglich, auch Schritte "bergauf" zu Springen um einem Möglichen lokalen Minimum zu entkommen. Die Sprungwahrscheinlichkeit ist abhängig von der "Temperatur" des Systems, die abhängig von der Laufzeit ist. Die Geschwindigkeit und Form dieser Abkühlung ist nun imminent wichtig für den Erfolg des Annealing-Algorithmus. Die sehr ähnliche Programmstruktur ergibt ähnliche Laufzeiten mit identischen Ergebnissen bei selber Tauschanzahl: SimAnn: 175 Tauschversuche durchgeführt ##################### 'anneal' ((), {}) 3.93680 sec ##################### 8409.2 Tauschalgorithmus: 176 Tauschversuche durchgeführt ##################### 'tausch' ((), {}) 3.38647 sec ##################### 8409.2 Zum Vergleich die optimale Lösung mit n! Simulationen: ##################### 'brutal' ((), {}) 15.64856 sec ##################### 7184.0 ===== Mathesis-Blockveranstaltung ===== Im Mathesis-Block konnte Ricardo leider nur kurz anwesend sein, um die Präsentationen zu hören. Der erste Tag wurde auf das erstellen der Präsentationen verwendet, der Rest floss in die Erstellung der Dokumentation und damit das Erstellen der Statistiken und Testen des Annealing.