Date: Tue, 03 Jun 1997 18:00:46 GMT
From: clucas@calresco.force9.net (Chris Lucas)
Organization: CALResCo
Newsgroups: comp.theory.dynamic-sys, comp.ai.alife, comp.ai.genetic, comp.ai.neural-nets, comp.theory.cell-automata,
sci.fractals, sci.nonlinear
Subject: Self-Organising Systems FAQ
Self-Organising Systems (SOS)
FAQ 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 suchlike ?
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.
Some self-organisation programs are available from this site:
CALResCo - http://members.aol.com/calresco/sos/calressw.zip
(in QBasic) Programs for Order from Chaos, Boolean Networks
and Self-Organised Criticality are currently available.
40. Where can I find online information ?
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) - see http://bambi.ccs.fau.edu/kelso/
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 ?
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.
Copyright 1997 Chris Lucas, all rights reserved.
E-Mail: clucas@calresco.force9.net (Chris Lucas)
The reason that I have taken the time to mark up Chris Lucas's FAQ on
Self-Organising Systems is because it represents a good and concise
introductory summary to a brand new and emergent field of science.
While its classification as a science today must recognise its infancy,
it will be in the future that research in this field
will assist the return of the reconception of a more foundational
natural science - one which will unify many currently disparate
interdisciplinary fields of the traditional sciences.
Self-Organising systems is a study of processes which exist at many and various
levels within the manifestation of natural phenomena, from the simple turbulent
flow of water through to the nature of living systems, ecologies, societies and
global processes. It is a baby in the arena of the sciences. Yet while vast sums
of hopeful investment is being placed into traditional research (such as that
concerning fundamental particle theories), the full extent of self-organising
systems theory has yet to be explored in all its depth.
Due to the evolutionary nature of human thought, fired by scientific
research, it is not inconceivable that the next breakthrough in the human quest
for the ultimate specifications of the laws of nature will not come from
one of the more traditional fields of science, but from one of the newly
emergent fields, such as this one ... the scientific study of Self-Organising
Systems.
It is for this reason that I am happy to publicise the work of Chris Lucas,
and to gratefully achnowledge his authorship and research in the preparation
of the above version of the Self-Organising Systems FAQ as at Empire Day,
in the year of 1997. The basic outline of this field of study is given
quite clearly above, and is of immeasureable assistance to the interested thinker,
or student, in the consideration of the application of the sciences
in their approach to the understanding of the natural condition which man
has found, and continues to find, both external to his living being,
and also internal thereto.
After some time has passed, and the document is maintained according to the
naturally emergent evolution of this new science over the years ahead, readers
of this archive document are encouraged to seek out the updated versions which
are presently resident at the locations outlined above:
In the summation of Ilya Prigogine, man has commenced a new dialogue with
nature in the pursuit of scientific investigation of the nature of systems
which are far-from-equilibrium and in the nature of systems which express
some measure of self-organisation. This new dialogue may have the potential
to introduce a deep and unifying harmonic into the western scientific
program which seems at present to be stalled in its reconciliation of the
paths of general relativity and quantum theory. Time will tell.
My appreciation is to Chris Lucas for his efforts in the presentation
of the above introductory summary of the field, and to the nature of
the pioneering spirit of honest research and collaboration of ideas,
through which - it is hoped - the emergent evolution of man shall
continue to continue.
And my encouragement is especially reserved for those who see
themselves as the students of life.
All the best for now,
PRF Brown
Mountain Man Graphics,
Newport Beach, Australia
Southern Winter of 1997