Biological Concepts for Adaptive and Distributed Algorithms

Course Contents

Biological ideas can serve as sophisticated models for problem-solving strategies and the design and management of complex computing systems. This potential, found in biological systems, arises from Nature's characteristic capability of parallel processing, self-organisation, efficiency and robustness, i.e., effective behaviour under unpredictably changing conditions. Interestingly, there are various analogies between complex systems in computer science and biology, as for instance competition for resources, division of labour or concurrency. However, apart from evolutionary computing and artificial neural networks, there are surprisingly few studies into potential applications of other biological ideas that might be useful to IT problems and questions.

In this mini-course we will discuss various aspects of biology, which could be used for novel adaptive and distributed algorithms and introduce some existing biological models already used in artificial intelligence (AI) and artificial life (ALife). The aim of the course is to raise interest for these (yet) unused biological ideas and to point at problems related to their identification and application in computer science.

In particular, we will discuss:

• Introduction and overview (including general introduction and motivation, organisation and origin of life, and methods for identification of significant processes)
• Emergent properties and self-organisation (including concept of emergent properties, ALife, chaos theory, and virtual robotics)
• Adaptive and distributed information processing (including concepts and models of evolution and genetics)
• Means of interaction (including perception, communication, synchronisation, and decision making)
• Models for complex interactions in natural and artificial systems (including optimal foraging theory, game theory, coevolution, and organisation of social systems)

About the Lecturers

Thiemo Krink

Thiemo Krink is currently enrolled as a research assistant professor (Forskningsadjunkt) at the BRICS PhD school. He was trained as a computer scientist at the Universities of Erlangen-Nürnberg and Hamburg (Germany), with special focus on computer simulation, AI and object-oriented programming. Within these areas he had specific interests in interdisciplinary research, which were stimulated by his medicine studies and his free lance activity as a business consultant. As an MSc student, he conducted two interdisciplinary projects on modelling of animal behaviour in collaboration with the biologist prof. Fritz Vollrath at Oxford. In 1994, he received his MSc degree in computer science and continued his research at the Department of Zoology, Aarhus, where he was conferred his PhD degree (biology) in 1997. Most of his papers and conference talks were focused on the design and application of virtual robots for biological research. Apart from his own activity as a scientific author, his research has been published by public media such as newspapers (e.g., Berlingske Tidende), journals (New Scientist), books (R. Dawkins: Climbing Mount Improbable) and TV (e.g. Scientific American Frontiers). His current research interests are in the fields of (i) applications of biological concepts for computational ideas and (ii) theoretical biology concerning general models for coevolution and behavioural ecology.

Per Bak

Per Bak is professor at the Niels Bohr Institute, Copenhagen. His ground-breaking research on self-organised criticality (SOC) is concerned with principal mechanisms of complex phenomena found in various disciplines. Besides various other disciplines, Per Bak applied his research to biological questions in collaboration with Stuart Kauffman at the Santa Fé institute.

Freddy B. Christiansen

Freddy B. Christiansen is professor at the department of Genetics and Ecology in Aarhus. His research activities are focused on multi-locus theory. Interestingly, he is also involved in interdisciplinary research on genetic algorithms together with John Holland and Mark Feldman at the Santa Fé institute.

Erik Baatrup

Erik Baatrup is associate professor at the Institute of Biological Sciences, AU, with research in ecotoxicology. He has developed several computerized video-tracking systems used for describing animal behaviour in precise numerical terms. Changes in the behaviour of terrestrial and aquatic organisms are useful effect-biomarkers of environmental pollutants.

Programme

Monday November 9, 1998, 15:15-17:00 in Auditorium F

Per Bak (physics)

• Complexity and self-organised criticality

Thiemo Krink

• Ways to adaptive and distributed algorithms

Tuesday November 10, 1998, 14:15-16:00 in Meeting room R2

Freddy B. Christiansen (genetics)

• Multi-locus theory

Thiemo Krink

• DNA based computers

Wednesday November 11, 1998, 15:15-17:00 in Auditorium G1

Thiemo Krink

• Adaptation in natural systems
• Conceptual and physical models for adaptation

Monday November 16, 1998, 15:15-17:00 in Auditorium D4

Erik Baatrup (behaviour)

• Objective methods for behavioural analysis

Thiemo Krink

• Synchronisation, communication and decision making

Tuesday November 17, 1998, 14:15-16:00 in Auditorium G4

Thiemo Krink

• Ecological models for real and artificial agents
• Agent cooperation and organisation of social systems

References

General introduction to biology

• Biology: (Campbell et al. 1997)
• Zoology: (Dorit et al. 1991), (Storer et al. 1979)
• Henderson's dictionary of biological terms: (Lawrence 1997)

Specific topics ordered by the course sessions

(1) Self-organisation and complexity

Per Bak: Complexity and self-organised criticality

• (Bak 1997)

• (Sims 1994)
• (Rucker 1993)
• (Böcher 1967)
• (Krink & Vollrath 1998)

(2) Biochemical information encoding

• (Christiansen & Feldman 1998)

• (Campbell et al. 1997)
• (Adleman 1994)
• (Adleman 1995)
• (Beaver 1995)
• (Lipton & Baum 1995)

(3) Adaptive and distributed processing

• (Campbell et al. 1997)

• (Holland 1975)
• (Michalewicz 1992)
• (Funes & Pollack 1997)
• (Floreano & Nolfi 1997)
• (Thompson 1997)
• (Hebb 1949)

(4) Mechanisms for interaction and their analysis

Thiemo Krink: Synchronisation, communication and decision making

• (Manning & Dawkins 1998)
• (Drickamer et al. 1996)
• (Dorit et al. 1991)

(5) Models for multiagent interactions

• (Krebs & Davis 1993)
• (Dorit et al. 1991)

• (Maynard Smith 1998)
• (Campbell et al. 1997)

1. Adleman, L. M. 1994 Molecular Computation of Solutions to Combinatorial Problems. Science 266, 1021-1024.
2. Adleman, L. M. 1995 On constructing a molecular computer. In DNA Based Computers - DIMACS Workshop, vol. 27 (ed. R. J. Lipton & E. B. Baum). Princeton, USA: American Mathematical Society.
3. Bak, P. 1997 How nature works. Oxford: Oxford University Press.
4. Beaver, D. 1995 A universal molecular computer. In DNA Based Computers - DIMACS Workshop, vol. 27 (ed. R. J. Lipton & E. B. Baum). Princeton, USA: American Mathematical Society.
5. Böcher, T. W. 1967 Planternes Morofologi. Copenhagen: Akademisk Forlag København.
6. Campbell, N. A., Mitchell, L. & Reece, J. B. 1997 Biology - Concepts & Connections. Menlo Park: Benjamin/Cummings.
7. Christiansen, F. B. & Feldman, M. W. 1998 Algorithms, Genetics, and Populations: The Schemata Theorem Revisited. Complexity 3.
8. Dorit, Walker & Barnes. 1991 Zoology: Saunders College Publishing.
9. Drickamer, L. C., Vessey, S. H. & Meikle, D. 1996 Animal Behavior. Dubuque: Wm. C. Brown Publishers.
10. Floreano, D. & Nolfi, S. 1997 Adaptive Behavior in Competing Co-evolving Species. In Fourth European Conference on Artificial Life (ed. P. Husbands & I. Harvey). Brighton, UK: MIT Press.
11. Funes, P. & Pollack, J. 1997 Computer Evolution of Buildable Objects. In Fourth European Conference on Artificial Life (ed. P. Husbands & I. Harvey). Brighton, UK: MIT Press.
12. Hebb, D. 1949 Organisation of Behavior. New York: Wiley.
13. Holland, J. 1975 Adaptation in Natural and Artificial Systems: Ann Arbor: University of Michigan Press.
14. Krebs, J. R. & Davis, N. B. 1993 Behavioural Ecology. Oxford: Blackwell Science.
15. Krink, T. & Vollrath, F. 1998 Emergent properties in the behaviour of a virtual spider robot. Proc. Roy. Soc. 265, 2051-2055.
16. Lawrence, E. 1997 Henderson's Dictionary of Biological Terms. Essex, UK: Longman.
17. Lipton, R. J. & Baum, E. B. 1995 DNA Based Computers. In DNA Based Computers - DIMACS Workshop, vol. 27 (ed. R. J. Lipton & E. B. Baum). Princeton, USA: American Mathematical Society.
18. Manning, A. & Dawkins, M. S. 1998 An introduction to animal behaviour. Cambridge: Cambridge University Press. Maynard Smith, J. 1998 Evolutionary Genetics. Oxford: Oxford University Press.
19. Michalewicz, Z. 1992 Genetic Algorithms+Data Structures = Evolution Programs. Berlin: Springer.
20. Rucker, R. 1993 Artificial Life Lab. Corte Madera, USA: Waite Group Press.
21. Sims, K. 1994 Evolving 3D Morphology and Behavior by Competition. In Proceedings of the 4th International Workshop on the Synthesis and Simulation of Living Systems (Artificial Life IV) (ed. R. A. Brooks & P. Maes), pp. 28-39. Cambridge, MA: MIT Press.
22. Storer, T. I., Usinger, R. L., Stebbins, R. C. & Nybakken, J. W. 1979 General Zoology. New York: McGraw-Hill.
23. Thompson, A. 1997 Temperature in Natural and Artificial Systems. In Fourth European Conference on Artificial Life (ed. P. Husbands & I. Harvey). Brighton, UK: MIT Press.

    ---