A rigorous runtime analysis of different nature inspired meta-heuristics will be analysed in this projectin order to gain a deeper understanding of when and why a given meta-heuristic is expected to perform well or poorly. Various nature inspired meta-heuristics have been applied successfully to combinatorial optimisation in many scientific fields.However, their computational complexity is far from being understood in depth. It is still unclear how powerfulthey are for solving combinatorial optimisation problems, and where their real power is in comparison with the more traditional deterministic algorithms.Evolutionary Algorithms (EAs), Ant Colony Optimisation (ACO) and Artificial Immune System (AIS) algorithms will be studied in this project.Since the knowledge level of their computational complexity is at very different stages, two different types of results will be produced.One is the computational complexity results of realistic EAs, not (1+1)-EAs, on selected well-known combinatorial optimisation problems. A setup of complexity classes will be built revealing what classes of problems are hard (or easy) for which kind of EAs.The other is a setup of the first basis for a systematic computational complexity analysis of ACO and AIS other popular nature inspired meta-heuristics for which very few runtime results are available.The expected outcomes of this project will not only provide a solid foundation, but also insights and guidance in understandingwhich meta-heuristic should be preferred for a given problem and in the design of more efficient variants.

Bio-Inspired Search Heuristics (BISHs) are general purpose randomized search heuristics (RSHs). Well known BISHs are Evolutionary Algorithms, Ant Colony Optimisation and Artificial Immune Systems. They have been applied successfully to combinatorial optimization in many fields. However, their computational complexity is far from being understood in depth. In this project the mathematical methodology will be developed to reveal where the real power of BISHs is in comparison with the traditional problem-specific algorithms. The project impacts the field of BISHs in several ways. A feature that distinguishes BISHs from most other algorithms is their population of individuals that simultaneously explore the search space. The first objective is to explain the performance of realistic BISHs for well-known combinatorial optimization problems through runtime analyses, highlighting the relationships between the solution quality and the exploration capabilities of the population. The second objective is to theoretically explain how BISHs can take advantage of the parallelisation available inherently in new technologies to achieve the population diversity required to produce solutions of higher quality in shorter time. The third objective of this project is to create a mathematical basis to explain the working principles of Genetic Programming (GP) and allow the effective and efficient self-evolution of computer programs. The fourth objective is to devise a suitable computational complexity model for the problem classification of BISHs. The enlargement of the established computational complexity picture with BISH complexity classes will enable the understanding of the relationships between traditional problem-specific algorithms and BISHs. Through industrial collaborators, the final objective is the direct exploitation of the theoretical results in real-world applications related to the combinatorial optimization problems studied in this project.

Concerns are growing about how much melting occurs on the surface of the Greenland Ice Sheet (GrIS), and how much this melting will contribute to sea level rise (1). It seems that the amount of melting is accelerating and that the impact on sea level rise is over 1 mm each year (2). This information is of concern to governmental policy makers around the world because of the risk to viability of populated coastal and low-lying areas. There is currently a great scientific need to predict the amount of melting that will occur on the surface of the GrIS over the coming decades (3), since the uncertainties are high. The current models which are used to predict the amount of melting in a warmer climate rely heavily on determining the albedo, the ratio of how reflective the snow cover and the ice surface are to incoming solar energy. Surfaces which are whiter are said to have higher albedo, reflect more sunlight and melt less. Surfaces which are darker adsorb more sunlight and so melt more. Just how the albedo varies over time depends on a number of factors, including how wet the snow and ice is. One important factor that has been missed to date is bio-albedo. Each drop of water in wet snow and ice contains thousands of tiny microorganisms, mostly algae and cyanobacteria, which are pigmented - they have a built in sunblock - to protect them from sunlight. These algae and cyanobacteria have a large impact on the albedo, lowering it significantly. They also glue together dust particles that are swept out of the air by the falling snow. These dust particles also contain soot from industrial activity and forest fires, and so the mix of pigmented microbes and dark dust at the surface produces a darker ice sheet. We urgently need to know more about the factors that lead to and limit the growth of the pigmented microbes. Recent work by our group in the darkest zone of the ice sheet surface in the SW of Greenland shows that the darkest areas have the highest numbers of cells. Were these algae to grow equally well in other areas of the ice sheet surface, then the rate of melting of the whole ice sheet would increase very quickly. A major concern is that there will be more wet ice surfaces for these microorganisms to grow in, and for longer, during a period of climate warming, and so the microorganisms will grow in greater numbers and over a larger area, lowering the albedo and increasing the amount of melt that occurs each year. The nutrient - plant food - that the microorganisms need comes from the ice crystals and dust on the ice sheet surface, and there are fears that increased N levels in snow and ice may contribute to the growth of the microorganisms. This project aims to be the first to examine the growth and spread of the microorganisms in a warming climate, and to incorporate biological darkening into models that predict the future melting of the GrIS. References 1. Sasgen I and 8 others. Timing and origin of recent regional ice-mass loss in Greenland. Earth and Planetary Science Letters, 333-334, 293-303(2012). 2. Rignot, E., Velicogna, I., van den Broeke, M. R., Monaghan, A. & Lenaerts, J. Acceleration of the contribution of the Greenland and Antarctic ice sheets to sea level rise. Geophys. Res. Lett. 38, L05503, doi:10.1029/2011gl046583 (2011). 3. Milne, G. A., Gehrels, W. R., Hughes, C. W. & Tamisiea, M. E. Identifying the causes of sea-level change. Nature Geosci 2, 471-478 (2009).