ISSN 1320-0682
		Volume 3	April 1996

... promising lines of research are converging on an alternative to computing that thrives on complexity rather than chokes on it...

Johnson, R. Colin (1988) Cognizers: Neural Networks and Machines That Think, John Wiley and Sons, New York.

Johnson's quote of almost a decade ago, encapsulates the mood of excitement and anticipation that a focus on research in complex systems held for the future. That complex systems research has attracted considerable debate and discussion from diverse, cross-disciplinary areas, is perhaps indicative of its great potential for growth and development.

One of the key themes in complexity is the idea that global phenomena can arise out of local interactions. The structure and function of the working brain, for instance, arises out of interactions between millions of neurons. Likewise interactions between the cells that comprise a growing embryo give rise to the organs and limbs that make up higher organisms. These sorts of processes form the centre theme of this volume.

The work presented here runs the gamut of current research - from theoretical studies that seek to develop a framework for the entire field to practical applications in specialized areas. In compiling this volume we have tried to tease out some of the major themes and directions in complexity research by the way we have organized the material. However, one of the issues in complexity research at present is the great diversity of ideas, approaches and applications. It is a sign of vitality that complexity research now includes many overlapping subdisciplines. For instance, the areas of artificial life and evolutionary computation both lay claim to research on genetic algorithms. No doubt such difficulties will disappear in time, but in the meantime it is important to realize that a lot of research could be classified under several different headings with equal validity.

The categories we have adopted here are meant to draw out particular ideas and to serve as thought provoking indicators of current trends. Although not necessarily in any order of importance, the sections are intended to trace the discussion from fundamental and mathematical concepts of complexity through to practical applications for biological and artificial systems. The section topics are:

Organization and Behaviour of Computational Systems

An important new paradigm associated with complexity treats systems in the real world as forms of natural computation. When viewed in this light the organization and behaviour of such systems can provide valuable lessons about the nature of computation in general. Conversely, general theories of, say, computational complexity can provide insights about many natural and human systems.

Criticality and Complexity

Criticality is a central theme in complexity. Critical behaviour refers to situations where a system exhibits sudden shifts - phase changes - in its structure or behaviour. Phase changes are now recognized as important and crucial in determining long-range order in systems where interactions are only local (see, for example, the special IEEE issue on searching in spaces with phase changes).

Nonlinear Dynamics and Fractals

Nonlinear dynamics (NLD) and fractals are arguably the fields where complexity began. NLD concerns the behaviour of systems with non-linear terms and leads immediately to studies of chaos and related topics. Although NLD arises chiefly from quantitative studies, an immediate difficulty is that many systems are analytically intractable, so simulation (i.e. direct computation) is often the only way to determine the behaviour of nonlinear systems. Nonlinearity can arise in many ways, including interactions between objects. So NLD also encompasses systems that consist of many interacting elements. Fractals arise in the context of the behaviour of iterative systems. One link with nonlinear dynamics arises because determination of any systems involves iterative computation.

Computational Problem Solving with Genetic Algorithms and Cellular Automata

Genetic Algorithms (GAs) and Cellular Automata (CA) are two biologically based ideas that have found widespread applications. GAs, introduced by John Holland, emulate evolution to provide very robust methods of search and optimization. The development of Cas stems most directly from John Conway's invention of the game LIFE. CAs consist of arrays of "cells", each of which is an identically programmed automation. The behavior of the cells is determined not only by its own internal state and program, but also by the states of the cells in some neighbourhood around it.

Evolution, Learning and Artifical Neural Networks

Evolutionary computation (EC) is one of the fastest growing areas of computing research. It is now widely recognized that many computational problems cannot easily be solved directly. Therefore, EC methods attempt to derive solutions to complex problems by setting up an appropriate system and letting it adapt by training (or "evolving") with observations of the system concerned. Several traditions have already developed, including finite state automata and artifical neural networks (ANNs). Genetic algorithms (dealt with in details elsewhere in this volume) provide a popular training method.

From Biological Systems to Artifical Life

Artificial life is one of the most popular areas of complexity research. As the name implies, it refers to models that simulate living systems, and to algorithms that emulate living processes. On the one hand, there is much that we can learn about computation by observing living things. On the other hand, artifical life ("ALife") has the capacity to teach us much about the role of interactions in biology. Despite the obvious potential, a practical problem of this field has been a lock of communication between the computer scientists who study ALife and their biological counterparts.

Bohdan Durnota
Monash University

 

EMail Contact:  Complexity International Editor