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.

Prediction of new crystal structures under extreme conditions

One of the most important challenges in chemistry and material science is the connection between the contents of a compound and its chemical and physical properties. In solids, these are greatly influenced by the crystal structure.rnrnThe prediction of hitherto unknown crystal structures with regard to external conditions like pressure and temperature is therefore one of the most important goals to achieve in theoretical chemistry. The stable structure of a compound is the global minimum of the potential energy surface, which is the high dimensional representation of the enthalpy of the investigated system with respect to its structural parameters. The fact that the complexity of the problem grows exponentially with the system size is the reason why it can only be solved via heuristic strategies.rnrnImprovements to the artificial bee colony method, where the local exploration of the potential energy surface is done by a high number of independent walkers, are developed and implemented. This results in an improved communication scheme between these walkers. This directs the search towards the most promising areas of the potential energy surface.rnrnThe minima hopping method uses short molecular dynamics simulations at elevated temperatures to direct the structure search from one local minimum of the potential energy surface to the next. A modification, where the local information around each minimum is extracted and used in an optimization of the search direction, is developed and implemented. Our method uses this local information to increase the probability of finding new, lower local minima. This leads to an enhanced performance in the global optimization algorithm.rnrnHydrogen is a highly relevant system, due to the possibility of finding a metallic phase and even superconductor with a high critical temperature. An application of a structure prediction method on SiH12 finds stable crystal structures in this material. Additionally, it becomes metallic at relatively low pressures.

Palynologie und Sedimentologie der Interglazialprofile Döttingen, Bonstorf, Munster und Bilshausen

Palynologie und Sedimentologie der Interglazialprofile Döttingen, Bonstorf, Munster und Bilshausen Zusammenfassung In der vorliegenden Dissertation wurden vier dem Holstein-Interglazial zugehörige Bohrkerne sowie ein rhumezeitlicher Bohrkern palynologisch und sedimentologisch bearbeitet. Die holsteinzeitlichen Bohrkerne stammen aus Kieselgurlagerstätten der Lüneburger Heide (Bonstorf und Munster) und aus einem Trockenmaar (Döttingen) in der Eifel. Der rhumezeitliche Kern stammt aus der Typlokalität Bilshausen im Harzvorland. Neben Prozentwertdiagrammen werden Pollendichte- und wenn möglich Polleninfluxwerte vorgestellt, die insbesondere für die Lokalitäten Hetendorf/Bonstorf und Munster/Breloh bisher nicht verfügbar waren. Mit dem Profil Döttingen konnte erstmals eine sowohl vollständige als auch nicht innerhalb des klassischen Aufkommens holsteinzeitlicher Fundstellen im norddeutschen Tiefland positionierte Holsteinsequenz aus dem deutschen Mittelgebirge dokumentiert werden. Das erhaltene Pollendiagramm bestätigt die aus den norddeutschen Profilen bekannte holsteintypische Vegetationsabfolge, durch die das Holstein gegenüber anderen Interglazialen wie Holozän, Eem oder Rhume palynologisch definiert ist. Neben der grundsätzlichen Übereinstimmung der Pollensequenz unterscheidet sich das Profil Döttingen aber deutlich im prozentualen Aufkommen der beteiligten Taxa von den norddeutschen Profilen. So wird eine hohe Alnus-Präsenz als Merkmal deutscher Holsteinprofile bestätigt, jedoch ist die, in den norddeutschen Lokalitäten durchhaltend hohe oder dominante Beteiligung von Pinus im deutschen Mittelgebirge nicht vorhanden und muss daher auf die Standortbedingungen Norddeutschlands zurückgeführt werden. Abies dagegen ist im Holstein der Mittelgebirge wesentlich präsenter als im norddeutschen Flachland. Im Profil Döttingen wurden insgesamt 10 Tephralagen gefunden. Auf eine dieser Tephren folgt ein „Birken-Kiefern-Gräser Vorstoß“, der palynostratigraphisch dem älteren „Birken-Kiefern Vorstoß“ in Munster/Breloh entspricht. Als eine Typologie des Holstein kann das in den Profilen Döttingen und Munster bestätigte intraholsteinzeitliche Carpinus-Minimum verstanden werden. An Hand sedimentologischer und palynologischer Befunde aus dem Bohrkern MU 2 muss die Existenz zweier, in der Literatur postulierter, postholsteinzeitlicher, „Nachschwankungen“ in Munster/Breloh in Frage gestellt, wenn nicht abgelehnt werden. In Kern MU 2 fallen palynostratigraphische Grenzen häufig mit Sandeinschaltungen zusammen. Eine dieser Sandeinschaltungen, nämlich unmittelbar vor dem älteren „Birken-Kiefern-Vorstoß“, korreliert in ihrer stratigraphischen Position mit der den „Birken-Kiefern-Gräser-Vorstoß“ im Profil Döttingen einleitenden Tephralage. Es gelang die Dauer des intraholsteinzeitlichen Carpinus Minimums auf etwa 1500±100 Jahre zu bestimmen und eine interne Zweigliederung zu dokumentieren. Im rhumezeitlichen Kern von Bilshausen (BI 1) konnten zahlreiche Störungen nachgewiesen werden. Insbesondere im Teufenbereich des Bilshausener „Birken-Kiefern-Vorstoßes“ deuten diese auf eine möglicherweise verfälschte Überlieferung. Der palynologisch markante „Lindenfall“ von Bilshausen liegt im Bereich einer isoklinalen Schichtenverfaltung. Die in der Literatur im Horizont des „Lindenfalls“ beschriebene „Bilshausentephra“ wurde nicht gefunden. Warvenzählungen an den Kernen MU 1, MU 2 und BI 1 ermöglichten Pollenzonendauern in Holstein- und Rhume-Interglazial zu bestimmen. Dabei wurde mittels den Warvenzählungen, unter zu Hilfenahme von Literaturdaten und von Schätzwerten eine Dauer für das Holstein-Interglazial sensu stricto (Pollenzonen I-XIV) von 15400-17800 Jahren und für das Rhume-Interglazial von wahrscheinlich 22000 Jahren bis maximal 26000 Jahren ermittelt.

Frugivores, seed dispersal and tree regeneration along a human disturbance gradient in East African tropical rainforests

Samenausbreitung und Regeneration von Bäumen sind wichtig für den langfristigen Bestand von Baum- und Frugivorengemeinschaften in tropischen Regenwäldern. Zunehmende Rohdung und Degradation gefährden den Ablauf dieser mutualistischen Prozesse in diesem Ökosystem. Um den Einfluss von kleinräumiger menschlicher Störung auf die Frugivorengemeinschaft und die zentralen Ökosystemprozesse Samenausbreitung und Regeneration zu erforschen, habe ich 1) die Frugivorengemeinschaft und die Samenausbreitungsrate von Celtis durandii (Ulmaceae) und 2) den Zusammenhang zwischen Baumarten mit fleischigen Früchten, Frugivoren und der Etablierung von Keimlingen dieser Baumarten in unterschiedlich stark gestörten Flächen dreier ostafrikanischer tropischer Regenwälder untersucht. Insgesamt konnte ich 40 frugivore Vogel- und Primatenarten in den drei untersuchten Waldgebieten nachweisen. Auf gering gestörten Flächen wurden mehr Frugivore als auf stark gestörten Flächen aufgenommen. Auch die Beobachtungen an C. durandii ergaben mehr frugivore Besucher in Bäumen auf gering gestörten als auf stark gestörten Flächen. Dies führte zu einer marginal signifikant höheren Samenausbreitungsrate auf den gering gestörten Flächen. Diese Ergebnisse waren auf regionaler Ebene in allen drei untersuchten Wäldern konsistent. Dies zeigt, dass kleinräumige Störung einen umfassenderen negativen Einfluss auf Frugivore und ihre Funktion als Samenausbreiter hat als zuvor angenommen. Bei der Vegetationserfassung nahm ich 131 verschiedene Baumarten mit fleischigen Früchten in den drei Regenwäldern auf. Kleinräumige menschliche Störung erhöhte den Artenreichtum dieser Baumarten marginal signifikant, hatte jedoch keinen direkten Einfluss auf die Frugivorendichte und den Artenreichtum von Keimlingen dieser Baumarten. Der Artenreichtum von Baumarten mit fleischigen Früchten zeigte einen marginal signifikant positiven Einfluss auf die Frugivorendichte, allerdings nicht auf die Keimlinge. Allerdings führte die Dichte der Frugivoren zu signifikant erhöhtem Artenreichtum der Keimlinge. Folglich scheint kleinräumige Störung die Keimlingsetablierung indirekt durch erhöhten Baumartenreichtum und erhöhte Frugivorendichte zu beeinflussen. Die Frugivorendichte hatte einen größeren Einfluss auf die Waldregeneration als kleinräumige Störung und Baumartenreichtum. Demnach scheint kleinräumige menschliche Störung sowohl positive als auch negative Effekte auf Samenausbreitung und Regeneration zu haben. Somit sind weitere Studien notwendig, die den Einfluss von kleinräumiger menschlicher Störung auf Mutualismen tropischer Regenwälder aufklären.

Genetic dynamics across early life stages in the tropical tree Prunus africana (Rosaceae)

In many plant species, the genetic template of early life-stages is formed by animal-mediated pollination and seed dispersal and has profound impact on further recruitment and population dynamics. Understanding the impact of pollination and seed dispersal on genetic patterns is a central issue in plant population biology. In my thesis, I investigated (i) contemporary dispersal and gene flow distances as well as (ii) genetic diversity and spatial genetic structure (SGS) across subsequent recruitment stages in a population of the animal-pollinated and dispersed tree Prunus africana in Kakamega Forest, West Kenya. Using microsatellite markers and parentage analyses, I inferred distances of pollen dispersal (father-to-mother), seed dispersal/maternal gene flow (mother-to-offspring) as well as paternal gene flow (father-to-offspring) for four early life stages of the species (seeds and fruits, current year seedlings, seedlings ≤ 3yr, seedlings > 3yr). Distances of pollen and seed dispersal as well as paternal gene flow were significantly shorter than expected from the spatial arrangement of trees and sampling plots. They were not affected by the density of conspecific trees in the surrounding. At the propagule stage, mean pollen dispersal distances were considerably (23-fold) longer than seed dispersal distances, and paternal gene flow distances exceeded maternal gene flow by a factor of 25. Seed dispersal distances were remarkably restricted, potentially leading to a strong initial SGS. The initial genetic template created by pollination and seed dispersal was extensively altered during later recruitment stages. Potential Janzen-Connell effects led to markedly increasing distances between offspring and both parental trees in older life stages. This showed that distance and density-dependent mortality factors are not exclusively related to the mother tree, but also to the father. Across subsequent recruitment stages, the pollen to seed dispersal ratio and the paternal to maternal gene flow ratio dropped to 2.1 and 3.4, respectively, in seedlings > 3yr. The relative changes in effective pollen dispersal, seed dispersal, and paternal gene flow distances across recruitment stages elucidate the mechanisms affecting the contribution of the two processes pollen and seed dispersal to overall gene flow. Using the same six microsatellite loci, I analyzed genetic diversity and SGS across five life stages, from seed rain to adults. Levels of genetic diversity within the studied P. africana population were comparable to other Prunus species and did not vary across life stages. In congruence with the short seed dispersal distances, I found significant SGS in all life stages. SGS decreased from seed and early seedling stages to older juvenile stages, and it was higher in adults than in late juveniles of the next generation. A comparison of the data with direct assessments of contemporary gene flow patterns indicate that distance- or density-dependent mortality, potentially due to Janzen-Connell effects, led to the initial decrease in SGS. Intergeneration variation in SGS could have been driven by variation in demographic processes, the effect of overlapping generations, and local selection processes. Overall, my study showed that complex sequential processes during recruitment contribute to the spatial genetic structure of tree populations. It highlights the importance of a multistage perspective for a comprehensive understanding of the impact of animal-mediated pollen and seed dispersal on spatial population dynamics and genetic patterns of trees.