Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Chemische Zusammensetzung der Aerosole : Design und Datenauswertung eines Einzelpartikel-Laserablationsmassenspektrometers

Atmosphärische Aerosolpartikel wirken in vielerlei Hinsicht auf die Menschen und die Umwelt ein. Eine genaue Charakterisierung der Partikel hilft deren Wirken zu verstehen und dessen Folgen einzuschätzen. Partikel können hinsichtlich ihrer Größe, ihrer Form und ihrer chemischen Zusammensetzung charakterisiert werden. Mit der Laserablationsmassenspektrometrie ist es möglich die Größe und die chemische Zusammensetzung einzelner Aerosolpartikel zu bestimmen. Im Rahmen dieser Arbeit wurde das SPLAT (Single Particle Laser Ablation Time-of-flight mass spectrometer) zur besseren Analyse insbesondere von atmosphärischen Aerosolpartikeln weiterentwickelt. Der Aerosoleinlass wurde dahingehend optimiert, einen möglichst weiten Partikelgrößenbereich (80 nm - 3 µm) in das SPLAT zu transferieren und zu einem feinen Strahl zu bündeln. Eine neue Beschreibung für die Beziehung der Partikelgröße zu ihrer Geschwindigkeit im Vakuum wurde gefunden. Die Justage des Einlasses wurde mithilfe von Schrittmotoren automatisiert. Die optische Detektion der Partikel wurde so verbessert, dass Partikel mit einer Größe < 100 nm erfasst werden können. Aufbauend auf der optischen Detektion und der automatischen Verkippung des Einlasses wurde eine neue Methode zur Charakterisierung des Partikelstrahls entwickelt. Die Steuerelektronik des SPLAT wurde verbessert, so dass die maximale Analysefrequenz nur durch den Ablationslaser begrenzt wird, der höchsten mit etwa 10 Hz ablatieren kann. Durch eine Optimierung des Vakuumsystems wurde der Ionenverlust im Massenspektrometer um den Faktor 4 verringert.rnrnNeben den hardwareseitigen Weiterentwicklungen des SPLAT bestand ein Großteil dieser Arbeit in der Konzipierung und Implementierung einer Softwarelösung zur Analyse der mit dem SPLAT gewonnenen Rohdaten. CRISP (Concise Retrieval of Information from Single Particles) ist ein auf IGOR PRO (Wavemetrics, USA) aufbauendes Softwarepaket, das die effiziente Auswertung der Einzelpartikel Rohdaten erlaubt. CRISP enthält einen neu entwickelten Algorithmus zur automatischen Massenkalibration jedes einzelnen Massenspektrums, inklusive der Unterdrückung von Rauschen und von Problemen mit Signalen die ein intensives Tailing aufweisen. CRISP stellt Methoden zur automatischen Klassifizierung der Partikel zur Verfügung. Implementiert sind k-means, fuzzy-c-means und eine Form der hierarchischen Einteilung auf Basis eines minimal aufspannenden Baumes. CRISP bietet die Möglichkeit die Daten vorzubehandeln, damit die automatische Einteilung der Partikel schneller abläuft und die Ergebnisse eine höhere Qualität aufweisen. Daneben kann CRISP auf einfache Art und Weise Partikel anhand vorgebener Kriterien sortieren. Die CRISP zugrundeliegende Daten- und Infrastruktur wurde in Hinblick auf Wartung und Erweiterbarkeit erstellt. rnrnIm Rahmen der Arbeit wurde das SPLAT in mehreren Kampagnen erfolgreich eingesetzt und die Fähigkeiten von CRISP konnten anhand der gewonnen Datensätze gezeigt werden.rnrnDas SPLAT ist nun in der Lage effizient im Feldeinsatz zur Charakterisierung des atmosphärischen Aerosols betrieben zu werden, während CRISP eine schnelle und gezielte Auswertung der Daten ermöglicht.

Phylogenie und Biogeographie der Linoideae (Linaceae) - Evolution von Heterostylie, Homostylie in Linum

Die Linaceae-Linoideae, vor allem die Gattung Linum, wurden unter Verwendung von zwei molekularen Markern (rbcL und ITS) bzgl. ihrer Phylogenie und Biogeographie untersucht. Die Linaceae entstanden während der mittleren Kreide in den frühen tropischen Regenwäldern, von wo aus sich die monophyletischen Linoideae vor etwa 51-46 Mill. Jahren über die temperaten Gebiete der Nordhemisphäre ausbreiteten. Während die drei basal abspaltenden Gattungen Anisadenia, Reinwardtia und Tirpitzia bzgl. ihrer Verbreitung auf Südostasien beschränkt sind, ist die Gattung Linum heute auf allen Kontinenten vertreten. Der Ursprung von Linum liegt wahrscheinlich in Südwestasien bzw. dem östlichen Mediterraneum, wo es im Oligozän zur Aufspaltung in zwei Entwicklungslinien kam ('Blaue Gruppe' und 'Gelbe Gruppe'). Während die überwiegend blaublühenden Linum-Arten ('Blaue Gruppe') vor allem in Europa und Südwestasien vorkommen, weisen die Vertreter der 'Gelben Gruppe' ein wesentlich größeres Verbreitungsgebiet auf. Gelbblühende Linum Arten findet man auf allen Kontinenten mit Diversitätszentren in Nordostamerika und Südwestasien. Interessanterweise wurde Amerika zweimal unabhängig voneinander besiedelt. Während die gelbblühenden Arten vor etwa 22-20 Mill. Jahren von Westeuropa über den Atlantik den amerikanischen Kontinent erreichten, wanderten Vertreter der 'Blauen Gruppe' im Pliozän (vor 3.78-3.33 Mill Jahren) über die Bering-Landbrücke in die Neue Welt ein. Auch in Südafrika sind einige gelbblühende Linum-Arten zu verzeichnen, die nicht über Nordafrika (wo einige Arten der 'Gelben Gruppe' beheimatet sind) die südliche Spitze des Kontinents erreichten, sondern von Amerika aus. Die molekularphylogenetischen Ergebnisse legen eine Eingliederung der Gattungen Cliococca, Hesperolinon, Radiola und Sclerolinon in Linum nahe, die durch morphologische Merkmale gestützt wird. Linopsis, die artenreichste Sektion der Gattung Linum, bedarf einiger Umstrukturierungen auf der Basis der molekularen und morphologischen Daten. Ein interessantes Phänomen innerhalb der Linaceae ist das Vorkommen von heterostylen und homostylen Arten innerhalb der Familie. Die Kombination der molekular-phylogenetischen Ergebnisse mit morphologischen Beobachtungen des Reproduktionssystems lassen darauf schließen, dass sich Homostylie innerhalb von Linum mehrfach unabhängig voneinander entwickelt hat. Das Modell von Primula wurde als Grundlage verwendet, um Aufschluss über die Entstehung der Homostylie innerhalb von Linum zu erlangen. Aus Primula ist bekannt, dass eine Kopplungsgruppe aus mindestens drei Genen an der Vererbung von Heterostylie beteiligt ist: G/g kodiert hierbei die Griffellänge und die Selbstinkompatibilitäts-reaktion der Narbe, A/a die Länge der Filamente und P/p die Selbst-inkompatibilitätsreaktion des Pollens. Umfangreiche Kreuzungs-experimente einer homostylen und einer heterostylen Linum-Art deuten darauf hin, dass die Genotypen der beiden Blütenformen in heterostylen Linum-Arten denen in Primula entsprechen. Langgriffel sind hiernach homozygot rezessiv (gpa/gpa), während die Kurzgriffel heterozygot sind (GPA/gpa). Selbstkompatible, homostyle Arten können theoretisch durch verschiedene Rekombinations-ereignisse entstehen. Erste Ergebnisse der rasterelektronen-mikroskopischen Betrachtung der Pollenkornoberflächen und Narbenpapillen deuten darauf hin, dass innerhalb von Linum Homostylie durch unterschiedliche Rekombinations-ereignisse mehrfach aus heterostylen Arten entstanden ist. So besitzt die homostyle Linum leonii den Genotyp gPA/gPA, während für die homostylen L. tenuifolium und L. nodiflorum der Genotyp Gpa/Gpa wahrscheinlich ist.