Imitating Nature in Computer Science: Novel Ideas for Solving Hard Problems and Learning From Computer Simulations
Dr Christine Zarges, Birmingham Fellow, School of Computer Science
Natural computing is the study of computational systems that borrow ideas from a large variety of natural systems such as Darwinian evolution (evolutionary algorithms), the immune systems of vertebrates (artificial immune systems), the nervous system (artificial neural networks), or the foraging behaviour of ants (ant colony optimisation). My research in this field is in particular concerned with the theoretical analysis of artificial immune systems and evolutionary algorithms used for optimisation.
Artificial Immune Systems
Artificial immune systems (AIS) are a relatively new and emerging interdisciplinary area of research, which comprises two main branches: on one hand immune modelling, which aims at understanding the natural immune system by means of mathematics and computer science; on the other hand problem solving by immune-inspired methods, capturing certain properties of the natural immune system such as self-organisation, learning, classification and adaptation capabilities, diversity, robustness and scalability, e.g., by mimicking the development of the immune repertoire through different observed immune functions.
AIS are a promising alternative to other nature-inspired techniques with potential impact in many areas. While classification and pattern recognition are probably the most natural applications for AIS, they have been applied in many different fields over the last decade, giving rise to large variety of different types of AIS used for problem solving. They have been very effectively used in areas such as fault diagnosis and tolerance in swarm and collective robotic systems, problems in bioinformatics, chemical detection, intrusion detection, learning as well as optimisation in static and dynamic environments.
Solving Hard Problems
Nature-inspired optimisation techniques are often referred to as general randomised search heuristics (RSH) since they implement a general idea of search, rely on random decisions and are applicable in many very different situations. They are used in practical settings where there is no time or expertise to develop problem-specific algorithms. They can be used in scenarios where standard techniques cannot be applied and the only way of obtaining knowledge about the problem at hand is to sample and evaluate candidate solutions. In many of these cases, RSH are applied very successfully and thus, they provide a powerful and flexible way of tackling different difficult and large-scale problems, which are omnipresent in all areas of science, in engineering and in real-world applications.
Why Do We Need RSH Theory?
RSH are typically very easy to implement and apply. While the general idea is to apply a RSH `right out of the box', in practice it is almost always necessary to adjust it to the concrete problem at hand by adding more complex mechanisms and modifying the search strategies to achieve acceptable performance. It is therefore highly desirable to obtain a clear understanding of the working principles of different mechanisms and algorithms. Without adequate theoretical foundations it is difficult to accurately assess their strength and weaknesses. This makes the theoretical analysis of RSH a modern and important area of research in theoretical computer science.
While for many RSH there is a growing body of useful theoretical results, it is widely agreed that there is a serious lack of a theoretical basis for AIS and that its development is one of the most important challenges for the future of the field. Much work so far has concentrated on the direct application of immune principles rather than following an informed and structured approach for the development of new AIS. My research addresses this challenge by providing rigorous analysis of common concepts in AIS such as immune-inspired mutation and mechanisms based on cell apoptosis (planned cell death). It adds to the overall research area of theory of RSH by comparing AIS to other RSH and pointing out benefits and drawbacks of different approaches. Ultimately, this will help practitioners to design and apply more effective RSH and thus find better solutions to their problems more effectively.
Learning From Computer Simulations
Nature-inspired systems cannot only be used to solve computational problems, but can also be seen as models that help understanding the natural systems themselves. Since immunology is far from having a complete understanding of all aspects of the immune system it is an interesting question to ask if our analyses can help gaining insights here, too. However, most current AIS only incorporate very abstract and limited aspects of immunology. Thus, in many cases it is necessary to revise the system in order to yield potentially interesting results from the perspective of immunology. My future research will explore possible routes in this innovative research direction.
Slides to a tutorial on the topic are available online:
Image Source: Dr. Triche. National Cancer Institute, Sep 20 1976