Der vorliegende Band 5 "Die flexible S-Bahn: Nutzbarmachung Genetischer Algorithmen für die optimale Steuerung und Planung eines flexiblen Stadtschnellbahnbetriebes" ist methodischen Grundsatzfragen aus dem Teilprojekt AP 200 gewidmet. Zwei Problemkreise werden untersucht: 1) Die vollautomatische Ermittlung flexibler Fahrpläne, durch die eine nachfrageorientierte Optimierung des Beförderungsangebotes ermöglicht wird. 2) Energiekostenminimierende Flexiblilisierung von Fahr-, Halte- und Zugfolgezeiten für ein System von Stadtschnellbahnzügen. Vollständig erschliessen lassen sich dabei die Optimierungspotenziale nur unter den Bedingungen der Vollautomatisierung. Die vorliegende Arbeit widmet allerdings besondere Aufmerksamkeit möglichen Zwischenstufen auf dem Weg dahin, d.h. von der heute praktizierten konventionellen Betriebsweise über die Nutzung innovativer Fahrerassistenzsysteme bis zur Vision eines fahrer- und begleiterlosen Betriebsregimes. Geschaffen wird dazu ein neuartiges methodisches Instrumentarium, das sich auf die Nutzbarmachung Genetischer Algorithmen stützt. (Dresden, im Dezember 2004 / Prof. Dr.-Ing. habil. Dr. h. c. H. Strobel - Projektleiter TU Dresden)

Zugl.: Aachen, Techn. Hochsch., Diss., 2008.

The paper "Parallel Genetic Algorithms" discusses the theoretical basics of Evolutionary Algorithms concentrating on Genetic Algorithms. Possibilities for a parallelization of these algorithms are examined and explained on the basis of concepts of parallel programming. A concrete suggestion for a practical realization of a parallel Genetic Algorithm at different levels of complexity is presented. / Die Studienarbeit zum Thema "Parallele Genetische Algorithmen" befasst sich mit den theoretischen Grundlagen Evolutionärer Algorithmen, wobei die Konzentration bei Genetischen Algorithmen liegt, und untersucht die Möglichkeiten einer parallelen Realisierung dieser Algorithmen. Des weiteren werden Konzepte der Parallelen Programmierung diskutiert sowie ein konkreter Vorschlag zur praktischen Realisierung eines parallelen Genetischen Algorithmus' auf verschiedenen Komplexitätsebenen vorgestellt.

The diploma thesis with the subject ¨Parallel Genetic Algorithms with Applications¨ deals with the parallelization of Genetic Algorithms for the creation of efficient optimization methods especially for simulation based application problems. First, an introduction to Genetic Algorithms and an overview of possible parallelization approaches as well as already published results of research are given. This is followed by a detailed explanation of the conception and realization of own Parallel Genetic Algorithms. The paper is rounded off by an particularized description of the results of extensive test runs on the Chemnitzer Linux-Cluster (CLiC). / Die Diplomarbeit zum Thema ¨Parallele Genetische Algorithmen mit Anwendungen¨ befasst sich mit der Parallelisierung Genetischer Algorithmen zur Erzeugung effizienter Optimierungsverfahren für insbesondere simulationsbasierte Anwendungsprobleme. Zunächst werden eine Einführung in Genetische Algorithmen sowie ein Überblick über mögliche Parallelisierungsansätze und bereits veröffentlichte Forschungsergebnisse gegeben. Dem schließt sich eine detaillierte Erläuterung der Konzeption und Umsetzung eigener Paralleler Genetischer Algorithmen an. Abgerundet wird die Arbeit durch eine ausführliche Darstellung der Ergebnisse umfangreicher Testläufe auf dem Chemnitzer Linux-Cluster (CLiC).

Obwohl schon seit den 50er Jahren auf dem Gebiet der Automatischen Textzusammenfassung Forschung betrieben wird, wurden der Nutzen und die Notwendigkeit dieser Systeme erst mit dem Boom des Internets richtig erkannt. Das World Wide Web stellt eine täglich wachsende Menge an Informationen zu nahezu jedem Thema zur Verfügung. Um den Zeitaufwand zum Finden und auch zum Wiederfinden der richtigen Informationen zu minimieren, traten Suchmaschinen ihren Siegeszug an. Doch um einen Überblick zu einem ausgewählten Thema zu erhalten, ist eine einfache Auflistung aller in Frage kommenden Seiten nicht mehr adäquat. Zusätzliche Mechanismen wie Extraktionsalgorithmen für die automatische Generierung von Zusammenfassungen können hier helfen, Suchmaschinen oder Webkataloge zu optimieren, um so den Zeitaufwand bei der Recherche zu verringern und die Suche einfacher und komfortabler zu gestalten. In dieser Diplomarbeit wurde eine Analyse von Extraktionsalgorithmen durchgeführt, welche für die automatische Textzusammenfassung genutzt werden können. Auf Basis dieser Analyse als viel versprechend eingestufte Algorithmen wurden in Java implementiert und die mit diesen Algorithmen erstellten Zusammenfassungen in einer Evaluation verglichen.

Evolutionäre Algorithmen übertragen den natürlich-biologischen Evolutionsprozess auf die Lösung mathematischer, techn(olog)ischer oder ökonomischer Optimierungsprobleme aus Forschung, Industrie und Wirtschaft. Die als Vorbild dienenden Prinzipien und Mechanismen werden jedoch nicht direkt kopiert, sondern lediglich ihre Wirkungen abstrakt imitiert sowie algorithmisch implementiert, um dann für die jeweilige Aufgabenstellung immer bessere Individuen mittels Computer im Zeitraffer heranzuzüchten und schließlich (fast-)optimale Lösungspunkte aufzufinden. Dabei bedarf es keiner expliziten Richtungsinformation oder sonstiger Wegweiser, um die Züchtung bzw. Suche zielgerichtet zu dirigieren und dann erfolgreich zu konvergieren. Sukzessive orientieren sich Evolutionäre Algorithmen allein anhand von Lösungspunkt-Zielfunktionswert-Paaren, also am Erfolg oder Misserfolg bereits durchgeführter Suchschritte. Aufgrund dieser konzeptuellen Anspruchslosigkeit haben sie dem Selektionsdruck der Praxis standgehalten, viele Anwendungsgebiete erobert und sich als universell einsetzbare Lösungsverfahren / Optimierungswerkzeuge etabliert. Das für diese Dissertation entwickelte und hier eingehend dokumentierte Chemnitzer hybrid-evolutionäre Optimierungssystem CHEOPS ist konzipiert als leistungsstarker, universeller, anpassungsfähiger und erweiterbarer Evolutionärer Algorithmus zur statischen Parameteroptimierung deterministischer Probleme. Als numerischer Benchmark zur empirischen Beurteilung von Erfolgswahrscheinlichkeit und Fortschrittsgeschwindigkeit ist außerdem eine ausgewogene Schar schwierig zu optimierender mathematischer Testfunktionen zusammengestellt. Dabei sind sie bewusst so konstruiert, dass sie derartige charakteristische Merkmale besitzen, die auch bei praxisrelevanten Optimierungsproblemen oft vorliegen oder zu erwarten sind. Verschiedene topologische Funktionseigenschaften haben tatsächliche oder auch nur vermeintliche Schwierigkeiten bei der Optimierung besonders verdeutlicht. CHEOPS beinhaltet eine Vielzahl an Werkzeugen und Funktion(alität)en, wird aber weiterentwickelt hinsichtlich mehrkriterieller Optimierung sowie hybrider Optimierung als Themengebiete für zukünftige Herausforderungen.

Diese Arbeit ist ein Beitrag zur theoretischen Chemie sowie zur Oberflächenchemie. Durch Kombination von computergestützten und experimentellen Untersuchungen wird die atomare Struktur von dünnen SiO2-Filmen auf Ru(0001)-Unterlagen, von eisendotierten SiO2-Filmen auf diesen Unterlagen und von H2O-Filmen auf MgO(001)-Oberflächen bestimmt. Die atomaren Strukturmodelle wurden entweder mit dem neu entworfenen und im Paket DoDo implementierten genetischen Algorithmus oder mittels auf Sachkenntnis gestützter Vermutungen erhalten. Die simulierten Eigenschaften der so erhaltenen Strukturen stimmen sehr gut mit den experimentellen Daten (Raster-Tunnel-Mikroskopie, Infrarot-Spektroskopie) überein. Die erfolgreiche Strukturbestimmung mithilfe des DoDo-Programms zeigt, dass genetische Algorithmen zur systematischen und extensiven Erkundung der Energielandschaften 2D-periodischer Systeme geeignet sind. / This work is a contribution in the field of theoretical chemistry and surface science. The joint computational and experimental studies investigated the atomic structure of ultrathin silica and iron-doped silica films formed on the Ru(0001) surface and water films formed on the MgO(001) surface. The atomic structure models were obtained using either the educated guess approach or the genetic algorithm that was designed and implemented within the DoDo package. The properties simulated for the resulting models are in a very good agreement with the experimental data (scanning tunnelling microscopy, infrared spectroscopy). The successful structure determination using the DoDo program shows that the genetic algorithm technique is capable of systematic and extensive exploration of the energy landscapes for 2D-periodic systems.

The work deals with two problems of mass rapid transit system operation: The development of flexible timetables and the realisation of flexible timetables. In both cases, genetic algorithms are used. In the process of (flexible) timetabling in suburban railways, a transport offer perfectly adapted to demand is searched for (temporal and spatial adaptation of demand as well as adaptation of capacity of the trains). After determination of the number of train runs per line and hour and their capacity, optimal departure times have to be found (with a precision of a minute down to 10 s), which fulfil criterias of the passengers (short waiting times) as well as of the operator (small number of vehicles needed). Two different codings for use with genetic algorithms have therefore been developed. They are tested on several case studies of the Dresden suburban railway network, assuming different degrees of flexibilisation. In the process of realising a flexible timetable, transitions between train headways as well as running time and dwell time reserves (margins in the order of a few seconds) are slightly modified in order to coordinate braking and accelerating trains and thereby reduce energy costs of a system of trains. Genetic algorithms can be applied for this problem as well, the proposed methods are tested on several case studies (S-Bahn Berlin, Metro Lille). / Die Arbeit behandelt zwei Probleme der Betriebsplanung von Stadtschnellbahnen: Die Erstellung flexibler Fahrpläne und die Umsetzung flexibler Fahrpläne. In beiden Fällen werden zur Lösung Genetische Algorithmen verwendet. Bei der Ermittlung flexibler Fahrpläne von S-Bahnen wird ein bestmöglich an die Verkehrsnachfrage angepasstes Verkehrsangebot gesucht (zeitlich, räumlich und bezüglich der Kapazität der einzelnen Züge angepasst). Nach stundenfeiner Festlegung der Fahrtenhäufigkeiten und Kapazitäten der einzelnen, sich überlagernden Linien werden deren Abfahrtszeiten gesucht (mit einer Genauigkeit von Minuten bis etwa 10 s), so dass sowohl die Wünsche der Fahrgäste nach gleichmäßigen Zugfolgezeiten als auch Betreiberwünsche (geringe Fahrzeuganzahl) erfüllt werden. Hierzu werden zwei verschiedene Kodierungen für die Verwendung mit Genetischen Algorithmen vorgestellt und das geschaffene Verfahren an verschiedenen Flexibilisierungsszenarien für die S-Bahn Dresden erprobt. Bei der Umsetzung flexibler Fahrpläne, die sich im Bereich weniger Sekunden abspielt, werden Übergänge zwischen Zugfolgezeiten, Fahr- und Haltezeitreserven geringfügig modifiziert, so dass durch bestmögliche Koordination von Anfahr- und Bremsvorgängen eines Systems von Zügen die Energiekosten minimal werden. Methodisch werden wiederum Genetische Algorithmen verwendet, die Erprobung des Verfahrens erfolgt anhand von Linien der S-Bahn Berlin und der Metro in Lille.

Im bisherigen Auslegungsprozess wird ein Bahnsystem in der Regel in Teilsysteme zerlegt, die nacheinander und für sich betrachtet entworfen werden. Das Verhalten des Gesamtsystems im geplanten täglichen Betrieb wird nur für wenige Varianten mittels Simulation überprüft. In dieser Arbeit wird der Ansatz vorgestellt, ein elektrisches Bahnsystem als Optimierungsaufgabe zu modellieren und diese mit einem geeigneten mathematischen Suchverfahren zu lösen, um Wechselwirkungen im Gesamtsystem bereits während der Dimensionierung berücksichtigen zu können. Zu diesem Zweck wird ein mehrkriterieller genetischer Algorithmus mit Zugfahrtsimulation und Netzberechnung gekoppelt, um ein für elektrische Bahnen entwickeltes Optimierungsmodell zu lösen. Am Beispiel einer realen Metrostrecke wird das Verfahren auf seine Eignung getestet und die erzielten Ergebnisse bewertet. / In the previous design process the electric railway system was subdivided into subsystems that are conceived one after the other and independent of each other. The performance of the complete railway system under realistic operation conditions can only be verified for some very few variants using simulation tools. The paper presents an approach to formulate an electric railway system as a self-contained optimization problem solved by means of a mathematical optimization method in order to consider interactions within the system in the early stage of the design process. Therefore a multi-objective genetic algorithm is coupled with both train simulation and electrical network calculation solving an optimization model specially designed for electrical railway systems. The proposed method is tested on an actual metro system. The results of this case study are presented and evaluated.

The work deals with two problems of mass rapid transit system operation: The development of flexible timetables and the realisation of flexible timetables. In both cases, genetic algorithms are used. In the process of (flexible) timetabling in suburban railways, a transport offer perfectly adapted to demand is searched for (temporal and spatial adaptation of demand as well as adaptation of capacity of the trains). After determination of the number of train runs per line and hour and their capacity, optimal departure times have to be found (with a precision of a minute down to 10 s), which fulfil criterias of the passengers (short waiting times) as well as of the operator (small number of vehicles needed). Two different codings for use with genetic algorithms have therefore been developed. They are tested on several case studies of the Dresden suburban railway network, assuming different degrees of flexibilisation. In the process of realising a flexible timetable, transitions between train headways as well as running time and dwell time reserves (margins in the order of a few seconds) are slightly modified in order to coordinate braking and accelerating trains and thereby reduce energy costs of a system of trains. Genetic algorithms can be applied for this problem as well, the proposed methods are tested on several case studies (S-Bahn Berlin, Metro Lille). / Die Arbeit behandelt zwei Probleme der Betriebsplanung von Stadtschnellbahnen: Die Erstellung flexibler Fahrpläne und die Umsetzung flexibler Fahrpläne. In beiden Fällen werden zur Lösung Genetische Algorithmen verwendet. Bei der Ermittlung flexibler Fahrpläne von S-Bahnen wird ein bestmöglich an die Verkehrsnachfrage angepasstes Verkehrsangebot gesucht (zeitlich, räumlich und bezüglich der Kapazität der einzelnen Züge angepasst). Nach stundenfeiner Festlegung der Fahrtenhäufigkeiten und Kapazitäten der einzelnen, sich überlagernden Linien werden deren Abfahrtszeiten gesucht (mit einer Genauigkeit von Minuten bis etwa 10 s), so dass sowohl die Wünsche der Fahrgäste nach gleichmäßigen Zugfolgezeiten als auch Betreiberwünsche (geringe Fahrzeuganzahl) erfüllt werden. Hierzu werden zwei verschiedene Kodierungen für die Verwendung mit Genetischen Algorithmen vorgestellt und das geschaffene Verfahren an verschiedenen Flexibilisierungsszenarien für die S-Bahn Dresden erprobt. Bei der Umsetzung flexibler Fahrpläne, die sich im Bereich weniger Sekunden abspielt, werden Übergänge zwischen Zugfolgezeiten, Fahr- und Haltezeitreserven geringfügig modifiziert, so dass durch bestmögliche Koordination von Anfahr- und Bremsvorgängen eines Systems von Zügen die Energiekosten minimal werden. Methodisch werden wiederum Genetische Algorithmen verwendet, die Erprobung des Verfahrens erfolgt anhand von Linien der S-Bahn Berlin und der Metro in Lille.