Transcript Artificial Life

Cognitive Computing
2012
The computer and the mind
LANGTON
Professor Mark Bishop
Artificial Life (AL)

What is Artificial Life?
 Life made by man rather than nature.

Traditional biology
 An attempt to explain the mechanics of life on Earth
 Defined by an ‘analytical approach’ to experimentation and theorising.

Conversely ‘Artificial Life’
 Is fundamentally ‘synthetic’


investigation by putting things together
Goes beyond ‘life as we know it’ to ‘life as it could be’


Hence it is not limited to investigating carbon chain chemistry;
Its aim is to study the dynamics of life itself.
(c) Bishop: The computer and the mind
Historical roots

The earliest devices that generated their own
behaviour were based on water transport e.g.
the Egyptian Clepsydra (around 135 BC)


Early Pneumatics from Hero of Alexandria (1st century
AD)
Later, the development of ‘Clockwork
Technology’ led to the construction of
Vaucanson’s duck

Flapped wings, ate, quacked & digested.

Cf. “If something flaps like a duck; quacks like a duck;
eats like a duck then it is a duck...”
(c) Bishop: The computer and the mind
Control mechanisms

Vaucanson’s duck had actions that were
‘sequenced’:

The development of sequential controllers led to
the development of programmable controllers;

Which in turn were an important step in the
development of general-purpose computers.
(c) Bishop: The computer and the mind
General purpose computers

Computers per se have no intrinsic behaviour, they must always
be instructed what to do.
 Cf. Lady Lovelace’s objection to machine intelligence.

A program ‘instructs’ the computer to behave like as some
‘machine’
 A program is a specification for a machine;
 We design specific Turing machines for specific tasks;

Universal Turing Machine
 Suitably programmed it can emulate any machine

Modern PCs.
(c) Bishop: The computer and the mind
Formal limits of machine
behaviours

Computability in principle:



Turing’s Halting problem;
Extended by Hopcroft & Ullman to demonstrate that we cannot
algorithmically decide any ‘non-trivial’ aspect of future program behaviour.
Computability in practice:

There are many areas in which we do not know how to specify algorithms to
generate certain behaviours;



E.g. How to translate perfectly between French and English.
Vehicle Identification number to registration plate number (cf. Searle’s error).
Practical computing:

There are many tasks for which we can specify an exact algorithmic solution
for simple problems but which for large scale problems take too long to
execute;

E.g. Exponential time programs (travelling salesman).
(c) Bishop: The computer and the mind
Universal constructors

Von Neumann imagined a machine
floating on a ‘pond’ surrounded by
lots of machine parts.

Given the description of any machine
it will locate the parts and construct
that machine.

Given a ‘description of itself’ it will
make itself.


Need not just to make the machine
but a copy of the description of the
machine.
C.f. The RepRap project (Dr. A.Bowyer
@ Bath University).
(c) Bishop: The computer and the mind
Cellular Automata (CA)

With each time step, the whole system is
updated

Every cell is updated by the same local rules

Context sensitive global behviours
(c) Bishop: The computer and the mind
‘Self’ reproduction

Game of life

Von Neumann’s CA model was proof that self-reproduction was
possible by machines


Demo - example of glider ‘reproduction’
Information in the description of the ‘reproducing machine’ is
typically used in two different ways:

Interpreted


Encodes the instructions executed to generate offspring.
Uninterpreted

Encodes the description given to offspring.
(c) Bishop: The computer and the mind
Linear versus non-linear systems

Linear Systems:



Behaviour of the whole is equal to sum of the
behaviour of its parts;
Relatively easy to analyse.
Non Linear Systems


Behaviour of the whole is more than the sum of
its parts;
Difficult to analyse.
(c) Bishop: The computer and the mind
Linear versus non-linear systems (2)

Linear Systems:


Full understanding of the whole system can be achieved
by the composition of the understanding of the separate
parts.
Non Linear Systems:


Interaction between component parts is key to system
behaviour;
System behaviour is not clear if component parts are
studied separately.
(c) Bishop: The computer and the mind
Non-linear systems

The basic building blocks in carbon
organisms - amino acids etc. - are not alive
themselves.

But when combined in the correct way the
system’s dynamic behaviour is life.
(c) Bishop: The computer and the mind
Recursively generated objects

E.g. Lindenmayer systems

Simple Linear growth



Context free
Simple mappings : A -> AB, B -> C, C->A etc
Branching growth (e.g. using these rules - GTYPE):





A -> C[B]D
B -> A
C -> C
D -> C(E)A
E -> D
(c) Bishop: The computer and the mind
Branching growth
(c) Bishop: The computer and the mind
Flocking

Flocking is a complex, emergent, non-centralised behaviour.

Flocking forms the basis mechanism in the Swarm Intelligence PSO
meta-heuristic.

Boids (Craig Reynolds) demonstrates a simulated A-Life flocking
behaviour

Boids demo

Each boid follows same behavioural tendencies:



Separation: steer to avoid crowding local flock-mates, but maintain minimum
distance
Alignment: steer towards the average heading of local flock-mates
Cohesion: steer to move toward the average position of local flock-mates.
(c) Bishop: The computer and the mind
Biological automata

Genotype:


Phenotype:


The specification of the system.
The observable physical characteristics and behaviour of the
system.
Morphogenesis

The development of the phenotype over time as directed by the
genotype.


Cf. Turing, On the chemical nature of morphogenesis (1952);
Explains ‘dappling patterns’.
(c) Bishop: The computer and the mind
Generalised
Genotypes and Phenotypes

In Artificial Life we need to generalise the notion of genotype and
phenotype to artificial systems:

Foundations of Genetic Algorithms/Evolutionary computing

GTYPES
 The unordered set of local rules.
 Global system behaviour is not specified.

PTYPES
 The behaviour and structures that emerge from the interactions of
the GTYPE and environment define the PTYPE.
(c) Bishop: The computer and the mind
Evolutionary and Genetic
Algorithms

Genetic Algorithms (GA) attempt to define the “logical form” of
natural selection processes.

Typically a GA implements natural selection by copying (and
sometimes varying in some way) the character strings (GTYPE) that
represent the fittest PTYPE;


the fittest individual(s) being defined by some ‘objective function’.
Varied GTYPES are produced by the application of genetic
operators:





Reproduction
Crossover
Mutation
Inversion
Duplication
(c) Bishop: The computer and the mind
Thomas Ray’s Tierra

No ‘engineer designed objective function’; instead computer
programs compete for resources: CPU time and memory space.

Their only task is to reproduce themselves.

Reproduction is not exact, and the better performers produce more
offspring.

Programs together in an area can increase or diminish each other’s
reproductive success.

Like nature there are long periods without change, followed by rapid
evolutionary change: see evolution of parasites and ‘anti-bodies’.
(c) Bishop: The computer and the mind
EvolutionZ

EVOLUTIONz allows a user to construct, compare, observe, and
explore dynamic artificial ecosystems through a 3D interface.

The inhabitants of these ecosystems are artificial animals, each
controlled by a neural net, which compete for limited resources
and evolve over time.

The program is meant as a fun tool for investigating learning and
open-ended evolution.

EvolutionZ demo
(c) Bishop: The computer and the mind