Random Recipe

Self-Organization FAQ

1997 Chris Lucas

version 1 (draft) 24 May 1997

1. Introduction

The scientific study of self-organising systems is a relatively recent field, although questions about how organisation arises have of course been raised since ancient times. The forms we see around us are just a minute sub-set of those theoretically possible, so why don't we see more variety ? It is to try to answer such questions that we study self-organisation. Many systems in nature show organisation e.g. galaxies, planets, compounds, cells, organisms and societies. Traditional scientific fields attempt to explain these features by reference to the micro properties or laws applicable to their component parts, for example gravitation or chemical bonds. Yet we can also approach the subject in a different way, looking instead for system properties that apply to all such collections of parts, regardless of size or nature. It is here that modern computers prove essential, by allowing us to investigate dynamic changes occuring over vast numbers of time steps, for large numbers of options.

Studying nature itself requires us to proceed at the timescale appropriate for the natural system, and to restrict our studies to what actually exists (or to what we can create quickly). This precludes our investigating the full range of possibilities that may be encountered. Mathematics, by contrast, does deal in generalised and abstract systems, and can generate theorems that should apply to all possible members of a class of systems. By creating a mathematical model and then running that as a computer simulation, we are able to quickly explore large numbers of possible starting positions and to analyse the common features that result. Relatively small systems can allow almost infinite initial options so, even with the fastest computers currently available, we can still only sample the possibility space. Yet this is enough for us to discover interesting properties, which can then be tested against real systems to generate new classes of scientific theories applicable to complex systems and their spontaneous organisation.

2. Definition of Self-Organisation

The essence of self-organisation is that system structure (at least in part) appears without explicit pressure or constraints from outside the system. In other words, the constraints on form are internal to the system and result from the interactions between the components, whilst being independant of the physical nature of those components. The organisation can evolve either in time or space, can maintain a stable form or can show transient phenomena. General resource flows into or out of the system are permitted, but are not critical to the concept.

The field of self-organisation seeks to discover the general rules under which such structure appears, the forms which it can take, and methods of predicting the changes to the structure that will result from changes to the underlying system. The results are expected to be applicable to any system exhibiting the same network characteristics.

3. What is a system ?

A system is a collection of interacting parts functioning as a whole. It is distinguishable from its surroundings with recognisable boundaries. The function depends upon the arrangement of the parts and will change in some way if parts are added, removed or rearranged. The system has properties that are emergent, that is they are not contained within any of the parts, they exist at a higher level of description.

4. What is a system property ?

If we connect a series of parts in a loop, then that loop does not exist as a property of the parts themselves. The parts can have any structure or form and yet the loop persists. If the loop shows an additional dynamic behaviour (maybe it oscillates) then this is an example of an emergent system property.

5. What is emergence ?

The appearance of a property or feature not previously seen. Generally, higher level properties are regarded as emergent - a car is an emergent property of the interconnected parts. That property disappears if the parts are disassembled and just placed in a heap.

6. What is organisation ?

The arrangement of parts in such a way as to be non-random. The restriction of the options available to a system in such a way as to confine it to a small volume of its state space.

7. What is state or phase space ?

The total arrangements (or combinations) available to the system. For a single coin toss this would be just two states (either heads or tails), but the possible states grow rapidly with complexity. If we take as an example 100 coins, then these can be arranged in over 1,000,000,000,000,000,000,000,000,000,000 different ways. We can view each coin as a separate parameter or dimension of the system, so one arrangement would be equivalent to specifying 100 binary digits (each one indicating a 1 for heads or 0 for tails for a specific coin). Generalising, any system has one dimension of state space for each variable that can change, mutation will change one or more variables and move the system a small distance in state space. State space is frequently called phase space, the two terms are interchangeable.

8. What is self-organisation ?

The evolution of a system into an organised form in the absence of external constraints. A move from a large region of state space to a persistent smaller one, under the control of the system itself.

9. Can things self-organise ?

Yes, any system that takes a form that is not imposed from outside (by walls, machines or forces) can be said to self-organise. The term is usually employed however in a more restricted sense by excluding physical laws (reductionist explanations), and suggesting that the properties that emerge are not explicable from a purely reductionist viewpoint.

10. Isn't this just the same as selection ?

No, selection is a choice between competing options such that one arrangement is preferred over another with reference to some external criteria - this represents a choice between two stable systems in state space. In self-organisation there is only one system which internally restricts the area of state space it occupies. In essence the system moves to an attractor that covers only a small area of state space, a dynamic pattern of expression that can persist even in the face of mutation and opposing selective forces. Alternative stable options are each self-organised attractors and selection may choose between them based upon their emergent properties.

11. What is an attractor ?

A preferred position for the system, such that if the system is started from another state it will evolve until it arrives at the attractor, and will then stay there in the absence of other factors. An attractor can be a point (e.g. the centre of a bowl containing a ball), a regular path (e.g. a planetary orbit), a complex series of states (e.g. the metabolism of a cell) or an infinite sequence (called a strange attractor). All specify a restricted volume of state space. The area of state space that leads to an attractor is called its basin of attraction.

12. How do attractors and self-organisation relate ?

Any system that moves to a fixed structure can be said to be drawn to an attractor. A complex system can have many attractors and these can alter with changes to the system interconnections (mutations). Studying self-organisation is equivalent to investigating the attractors of the system, their form and dynamics.

13. What is criticality ?

A point at which system properties change suddenly, e.g. where a matrix goes from non-percolating to percolating or vice versa. This is often regarded as a phase change.

14. What is Self-Organised Criticality (SOC) ?

The ability of a system to evolve in such a way as to approach a critical point and then maintain itself at that point.

15. What is the edge of chaos ?

This is the name given to the critical point of the system, where a small change can either push the system into chaotic behaviour or lock the system into a fixed behaviour. It is regarded as a phase change.

16. What is a phase change ?

A point at which the appearance of the system changes suddenly. In physical systems the change from solid to liquid is a good example. Non-physical systems can also exhibit phase changes, although this use of the term is more controversial. Generally we regard our system as existing in one of three phases. If the system exhibits a fixed behaviour then we regard it as being in the solid realm, if the behaviour is chaotic then we assign it to the gas realm. For systems on the 'Edge of Chaos' the properties match those seen in liquid systems.

17. How does percolation relate to SOC ?

Percolation is an arrangement of parts (usually visualised as a matrix) such that a property can arise that connects the opposite sides of the structure. This can be regarded as making a path in a disconnected matrix or making an obstruction in a fully connected one. The boundary at which the system goes from disconnected to connected is a sudden one, a step or phase change in the properties of the system. This is the same boundary that we arrive at in SOC. The main feature is that at this boundary a system has a correlation length that just spans the entire system, with a power law distribution of shorter lengths.

18. What is a power law ?

We plot the logarithm of the number of times a certain property value is found against the log of the value itself. If the result is a straight line then we have a power law. Essentially what we are saying is that there is a distribution of results such that the larger the effect the less frequently it is seen. A good example is earthquake activity where many small quakes are seen but few large ones, the Richter scale is based upon such a law. A system subject to power law dynamics exhibits the same structure over all scales. This self- similarity or scale independant (fractal) behaviour is typical of self-organising systems.

19. How does natural selection fit in ?

Selection is a bias to move through state space in a particular direction, maximising some external fitness function - choosing between mutant neighbours. Self-organisation drives the system to an internal attractor, we can call this an internal fitness fuction. The two concepts are complementary and can either mutually assist or oppose. In the context of self-organising systems, the attractors are the only stable states the system has, selection pressure is a force on the system attempting to perturb it to a different attractor. It may take many mutations to cause a system to switch to a new attractor, since each simply moves the starting position across the basin of attraction. Only when a boundary between two basins is crossed will an attractor change occur.

20. What is a mutant neighbour ?

In the world of possible systems (the state space for the system) two possibilities are neighbours if a change or mutation to one parameter can change the first system into the second or vice versa. Any two options can then be classified by a chain of possible mutations converting between them (via intermediate states). Note that there can be many ways of doing this, depending on the order the mutations take place. The process of moving from one possibility to another is called an adaptive walk.

21. What is an adaptive walk ?

A process by which a system changes from one state to another by gradual steps. The system 'walks' across the fitness landscape, each step is assumed to lead to an improvement in the performance of the system against some criteria (adaption).

22. What is a fitness landscape ?

If we rate every option in state space by its achievement against some criteria then we can plot that rating as a fitness value on another dimension, a height that gives the appearance of a landscape. The result may be a single smooth hill (a correlated landscape), many smaller peaks (a rugged landscape) or something in between.

23. How many parts are necessary for self-organisation ?

As few as two (in magnetic or gravitational attraction) can suffice, but generally we use the term to classify more complex phenomena than point attractors, the richness of possible behaviour increases rapidly with the number of interconnections.

24. What interconnections are necessary ?

In general terms for self-organisation to occur the system must be neither too sparsely connected (so most units are independent) nor too richly connected (so that every unit affects every other). Most studies of Boolean Networks suggest that having about two connections for each unit leads to optimum organisational and adaptive properties. If more connections exist then the same effect can be obtained by using canalysing functions or other constraints on the interaction dynamics.

25. What is a Boolean Network or NK model ?

Taking a collection (N) of logic gates (AND, OR, NOT etc.) each with K inputs and interconnecting them gives us a Boolean Network. Depending upon the number of inputs (K) to each gate we can generate a collection of possible logic functions that could be used. By allocating these to the nodes (N) at random we have a Random Boolean Network and this can be used to investigate whether organisation appears for different sets of parameters. Some possible logic functions are canalysing and it seems that this type of function is the most likely to generate self-organisation. This arrangement is also called biologically an NK model where N is seen as the number of genes (with 2 alleles each - the output states) and K denotes their inter-dependancies.

26. What are canalysing functions and forcing structures ?

A function is canalysing if a single input being in a fixed state is sufficient to force the output to a fixed state, regardless of the state of any other input. For example, for an AND gate if any input is held low then the output is forced, low, so this function is canalysing. An XOR gate, in contrast, is not since the state can always change by varying another input. The result of connecting a series of canalysing functions can be to force chunks of the network to a fixed state (an initial fixed input can ripple through and lock up part of the network - a forcing structure). Such fixed divisions (barriers to change) can break up the network into active and passive structures and this allows complex behaviours to develop.

27. How does connectivity affect landscape shape ?

In general the higher the connectivity the more rugged the landscape becomes. Simply connected landscapes have a single peak, a change to one parameter has little effect on the others so a smooth change in properties is found during adaptive walks. High connectivity means that variables interact and we have to settle for compromise fitnesses, many lower peaks are found and the system becomes stuck at local optima or attractors, rather than being able to reach a global optima.

28. What is an NKC Network ?

If we allow each node (N) to be itself a complex arrangement of interlinked parts (K) then we can regard the connections between nodes (C) as a further layer of control. This can best be seen by visualising an ecosystem, where the nodes are species each consisting of a collection of genes, the interactions between species form the ecosystem. Thus the local connection K specifies how the genes interact with each other and the distant connection C how the genes interact with other species. This model then allows co-evolutionary development and organisation to be studied.

29. What is an autocatalytic set ?

If a collection of interacting entities are brought together then they may react in certain ways only, e.g. entity A may be able to affect B but not C. D may only affect E. For a sufficently large collection of different entities a situation may arise where a complete network of interconnections can be established - the entities become part of one system. This is called an autocatalytic set, after the ability of molecules to catalyse each other's formation in the chemical equivalent of this arrangement.

30. How can self-organisation be studied ?

Since we are seeking general properties that apply to topologically equivalent systems, any physical system or model that provides those connections can be used. Much work has been done using Cellular Automata and Boolean Networks, with Alife, Genetic Algorithms, Neural Networks and similar techniques also widely used. In general we start with a set of rules specifying how the interconnections are allowed to behave, the network is randomly initiated and then iterated (stepped) continually following the ruleset. The stable pattern obtained (if any) is noted and the sequence repeated. After many trials generalisations from the results can be attempted, with some statistical probability.

31. What results are there so far ?

For systems with high connectivity K=N, the number of attractors is N/e (linear), the number of states within an attractor averages 0.5 * 2 ** N/2 (exponentially large). These systems are highly sensitive to disturbance, and swap amongst the attractors easily.

For K=1, attractor numbers are exponential on N, state lengths increase only as root N, but again are sensitive to disturbance and easily swap between attractors.

For K=2 we have a phase transition, number of attractors drops to root N, average length is also root N. The system is stable to disturbance and has few paths between the attractors.

Systems that are able to change their number of connections (by mutation) are found to move from the chaotic (K high) or static (K low) regions spontaneously to that of the phase transition and stability - the self-organising criticality.

32. How applicable is self-organisation ?

The above results seem to indicate that such system properties can be ascribed to all manner of natural systems, from physical, chemical, biological, psychological to cultural. Much work is yet needed to determine to what extent the system properties relate to the actual features of these systems and how they vary with underlying constraints. Power laws are common in natural systems and an underlying SOC cannot be ruled out as a possible cause of this situation.

33. What are levels of organisation ?

The smallest parts of a system produce their own emergent properties, these are the lowest system features and form the next level of structure in the system. These components then in turn form the building blocks for a new higher level of organistion, with different emergent properties and this process can proceed to higher levels in turn. The various levels can all exhibit their own self-organisation (e.g. cell chemistry, organs, societies) or may be manufactured (e.g. piston, engine, car).

34. How is energy related to these concepts ?

Energy considerations are often regarded as an explanation for organisation, it is said that minimising energy causes the organisation. Yet there are often alternative arrangements that require the same energy. To account for the choice between these requires other factors. Organisation still appears in computer simulations that do not use the concept of energy, although other criteria may exist. This system property suggests that we still have much to learn in this area.

35. How does it relate to chaos ?

In nonlinear studies we find much structure for very simple systems, as seen in the self-similar structure of fractals and the bifurcation structure seen in chaotic systems. This form of system exhibits complex behaviour from simple rules. In contrast, for self-organising systems we have complex assemblies generating simple emergent behaviour, so in essence the two concepts are complementary. For our collective systems, we can regard the solid state as equivalent to the predictable behaviour of a formula, the gaseous state as corresponding to the statistical realm and the liquid state as being the bifurcation or fractal realm.

36. What are dissipative systems ?

Systems that use energy flow to maintain their form are said to be dissipative systems, these would include atmospheric vortices, living systems and similar. The term can also be used more generally for systems that consume energy to keep going e.g. engines or stars. Such systems are generally open to their environment.

37. What is bifurcation ?

A phenomenon that results in a system splitting into two possible behaviours with a small change in a parameter, further changes then cause further splits at regular intervals until finally the system enters a chaotic phase.

38. What are autopoiesis, extropy and the like ?

Several other terms are loosely used with regard to self-organising systems, many in terms of human behaviour. Autopoiesis is self- reproduction, maintenance of form with time and flows, Extropy is organisational growth.

39. Is any software available to study self-organisation ?

Few software packages relate to self-organisation as such, but many do show self-organised behaviour in the context of more specialised topics. These include cellular automata (Game of Life), neural networks (artificial learning), genetic algorithms (evolution), artificial life (agent behaviour), fractals (mathematical art) and physics (spin glasses). These can be found via the relevant newsgroup FAQs.

40. Where can I find online information ?

CALResCo, home of this FAQ
Links to SOS online papers/sites
Complex Systems virtual library
Complex Adaptive Systems
VCU complexity research group
Artificial Life links
Complex Systems & Chaos Theory
SOS bib
Measures of Complexity
Self-org measures
SOS on the Web
What is complexity ?
The Avida Group
Santa Fe Institute

41. What books can I read on this subject ?

Ross Ashby, An Introduction to Cybernetics (1964 Methuen)
Ross Ashby, Design for a Brain - The Origin of Adaptive Behaviour (1960 Chapman & Hall).
Per Bak, How Nature Works - The Science of Self-Organised Criticality (1996 Copernicus). Power Laws and widespread applications, approachable.
Margaret Boden (ed), The Philosophy of Artificial Life (1996 OUP).
John Casti, Complexification: explaining a paradoxical world through the science of surprise (1994 HarperCollins).
Cameron and Yovits (Eds.), Self-Organizing Systems (1960 Pergamon Press)
Cohen and Stewart, The Collapse of Chaos - Discovering Simplicity in a Complex World (1994 Viking). Excellent and approachable analysis.
Manfred Eigen, The Self Organization of Matter (?)
Eigen and Schuster, The Hypercycle: A principle of natural self- organization (1979 Springer)
Eigen and Winkler-Oswatitsch, Steps Toward Life: a perspective on evolution (1992 Oxford University Press)
Claus Emmeche, The Garden in the Machine: The Emerging Science of Artificial Life (1994 Princeton)
von Foerster and Zopf (Eds.), Principles of Self-Organization (1962 Pergamon)
John Formby, An Introduction to the Mathematical Formulation of Self-organizing Systems (1965 ?)
Forrest S.(ed), Emergent Computation: Self-organising, Collective and Cooperative Phenomena in Natural & Artifical Computings Networks (1991 MIT)
Murray Gell-Mann, Quark and the Jaguar - Adventures in the simple and the complex (1994 Little, Brown & Company). From a quantum viewpoint, popular.
James Gleick, Chaos - Making a New Science (1987 Cardinal). The most popular science book related to the subject, simple but a good start.
Goldstein, Jacobi & Yovits (Eds.), Self-Organizing Systems (1962 Spartan)
John Holland, Adaption in Natural and Artificial Systems: An Introductory Analysis with applications to Biology, Control & AI (1992 MIT Press)
John Holland, Hidden Order - How adaption builds complexity (1995 Addison Wesley). Complex Adaptive Systems and Genetic Algorithms, approachable.
Erich Jantsch, The Self-Organizing Universe: Scientific and Human Implications of the Emerging Paradigm of Evolution (1979 Oxford)
George Kampis, Self-modifying systems in biology and cognitive science: A new framework for dynamics, information, and complexity (1991 Pergamon)
Stuart Kauffman, At Home in the Universe - The Search for the Laws of Self-Organisation and Complexity (1995 OUP). An approachable summary
Stuart Kauffman, The Origins of Order - Self-Organisation and Selection in Evolution (1993 OUP). Technical masterpiece
Kevin Kelly, Out of Control - The New Biology of Machines (1994 Addison Wesley). General popular overview of the future implications of adaption.
Scott Kelso, Dynamic Patterns: The Self-Organisation of Brain and Behaviour (? MIT Press)
George Klir, Facets of Systems Science (1991 Plenum Press)
Kohonen T., Self-Organisation and Associative Memory (1984 Springer-Verlag)
Christopher Langton (ed.), Artificial Life - Proceedings of the first ALife conference at Santa Fe (1989 Addison Wesley). Technical (several later volumes are available but this is the best introduction).
Steven Levy, Artificial Life - The Quest for a New Creation (1992 Jonathan Cape). Excellent popular introduction.
Roger Lewin, Complexity - Life at the Edge of Chaos (1993 Macmillan). An excellent introduction to the general field.
Benoit Mandelbrot, The Fractal Geometry of Nature (1983 Freeman). A classic covering percolation and self-similarity in many areas.
Nicolis and Prigogine, Self-Organization in Non-Equilibrium Systems (1977 Wiley)
Nicolis and Prigogine, Exploring Complexity (1989 Freeman)
Pines D.(ed), Emerging Syntheses in Science, (1985 Addison-Wesley)
Pribram K.H. (ed), Origins: Brain and Self-organization (1994 Lawrence Ealbaum)
Prigogine & Stengers, Order out of Chaos (1985 Flamingo) Non-equilibrium & dissipative systems, an early classic.
Manfred Schroeder, Fractals,Chaos,Power Laws - Minutes from an Infinite Paradise (1991 Freeman & Co.). Self-similarity in all things, technical.
John von Neumann, Theory of Self Reproducing Automata (1966 Univ.Illinois)
Mitchell Waldrop, Complexity - The Emerging Science at the Edge of Order and Chaos (1992 Viking). Popular scientific introduction.
Stephen Wolfram, Cellular Automata and Complexity: Collected Papers, (1994 Addison-Wesley)

42. How does self-organisation relate to other areas of complex systems ?

Many studies of complex systems assume that the systems self-organise into emergent states which are not predictable from the parts. Artificial Life, Evolutionary Computing (incl Genetic Algorithms), Cellular Automata and Neural Networks are the main fields directly associated with this idea.

43. Which Newsgroups are relevant ?

comp.theory.self-org-sys - self organising systems & sponsor of this FAQ
comp.ai.alife - artificial life
comp.ai.genetic - genetic algorithms and evolutionary computation
comp.ai.neural-nets - neural networks
comp.theory.cell-automata - cellular automata
comp.theory.dynamic-sys - dynamic systems
sci.bio.evolution - natural organisation and evolution
sci.fractals - fractal and self-similar systems
sci.nonlinear - nonlinear and chaotic systems

44. Updates to this FAQ

This FAQ has been compiled and is maintained by Chris Lucas at CALResCo. Comments, suggestions, requests for additions and particularly criticisms and corrections are warmly welcomed. Please feel free to EMail me anytime at calresco@aol.com or post relevant messages to the comp.theory.self-org-sys Usenet newsgroup for discussion.

45. Disclaimers

Usual get out clauses, I take no responsibility for any errors contained in the information presented here or any damages resulting from its use. The information is accurate however as far as I can tell.

This FAQ may be posted in any newsgroup , mail list or BBS as long as it remains intact and contains the following copyright notice. This document may not be used for financial gain or included in commercial products without the express permission of the author.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !