Introduction to Natural Computation
Lecture 1
Module Introduction and Examples1
Xin Yao
1
Notes adapted from Intro to NC Year 2010.
1 / 23
Lecturers
Professor Xin Yao
x.yao@cs.bham.ac.uk
Office hour: 9-10am on Mondays, room 211
Dr Leandro Minku
l.l.minku@cs.bham.ac.uk
Office hour: 1-2pm on Fridays, room 244
Dr Alberto Moraglio
a.moraglio@cs.bham.ac.uk
Office hour: 1-2pm on Wednesdays, room 244
2 / 23
Other Teaching Personnel
Guanzhou Lu
g.lu@cs.bham.ac.uk
Office hour: 2-3pm on Mondays, room 218
Teaching assistant
Khulood Alyahya
kya020@cs.bham.ac.uk
Office hour: 2-3pm on Tuesdays, room 218
Teaching assistant
Dr. Shuo Wang
s.wang@cs.bham.ac.uk
MSc and ICY students’ tutorials
Time and place: TBA
3 / 23
Office Hours
Questions on the topics of the lectures:
Come to see the corresponding lecturer.
Questions on exercises, marks, maths and programming:
Come to see a teaching assistant.
Please, email the corresponding lecturer / teaching assistant before coming.
4 / 23
Module Administration – Lectures
Lecture plan for the semester on the web site.
Two lectures per week:
Wednesdays 9-10am, LT3 Sports and Exercise Science
Thursdays 12-1pm, G15 Muirhead Tower
Lecture attendance: Required, but we won’t take a roll call.
Lecture notes:
Available after each lecture.
Lectures notes list keywords only, not to replace the required readings
Module web site: http://www.cs.bham.ac.uk/internal/courses/intro-nc
5 / 23
Module Administration – Assessment
70% examination (1.5 hours closed book), 30% continuous assessment
Continuous assessment:
Weekly exercises, total 18%
Released almost every Thursday
Deadline every Wednesday of the next week
Hand in to the CS reception before 12 noon
Mark zero for late submissions
If extension of deadline needed, email welfare
Coursework, 12%
Released on 05/11
Deadline at noon on 03/12
Resit: 100% examination (1.5 hours closed book)
Pass mark: 40% for undergraduates, 50% for masters students
6 / 23
What’s So Unnatural About CS Now?
Brittle and inflexible
Doesn’t learn and never grows up
Hopeless in dealing with noisy and inaccurate information
Hopeless in dealing with uncertain environments
...
7 / 23
Solution? Mother Nature
8 / 23
What Is Natural Computation?
It studies computational systems that get inspirations and borrow ideas from natural
systems, including biological, physical, chemical, social and economical systems. It
includes
Evolutionary Computation,
Neural Computation,
Social Computation,
Molecular Computation,
Quantum Computation,
...
9 / 23
Borrowing Ideas from Nature...
10 / 23
Natural Computation = Nature Inspired Computation
11 / 23
Evolutionary Algorithms
Select the best Parents
Combine
Population features of
parents
of solutions Make some
random
changes
(mutation)
Replace the worst
Offspring
12 / 23
Evolutionary Algorithms
Example: Factory Planning and Scheduling
i2 Technologies, USA: “The i2 Factory Planning and Scheduling solution...
“... proven best practice templates used in 12+ industries and more than 800
installs ...”
“... brings together the most advanced planning and scheduling engine, Factory
Planner, and i2’s patented genetic algorithms for solving the most tedious
scheduling problems ...”
Example: M&S Uses Genetic IT to Create Best Displays
High-street retailer Marks & Spencer is using genetic algorithm technology to
transform its in-store displays and improve stock management.
(ComputerWeekly, Tuesday 17 February 2004)
http://www.computerweekly.com/Articles/2004/02/16/200284/Mamp%3BS-uses-
genetic-IT-to-create-best-displays.htm
13 / 23
Artificial Neural Networks
Extremely simplified model of a brain
Artificial “neurons” connected to each
other
Can learn and generalise
Good at perception tasks
Fault tolerant
Noise resistant
14 / 23
Artificial Neural Networks
Example: Recognition, Classification and Prediction
Object recognition
Medical diagnosis
Credit card assessment
Fraud detection
Churn prediction
Water quality prediction
Traffic flow prediction
15 / 23
Agents and Social Systems
Human beings in markets follow different strategies in a parallel, decentralised and
asynchronous system.
Yet, the resource allocation
achieved is theoretically
optimal
Economists refer to this
emergent behaviour as Adam
Smith’s “invisible hand”
Similar ideas can be used for
any resource-allocation
problem
16 / 23
Swarm Intelligence
Example: Flocking / schooling of birds and fish
Craig Reynolds demonstrated with his Boids that even very
simple local rules and interactions can give rise to
apparently complex global behaviour.
The rules applied in the simplest Boids world are as follows:
separation: keep your distance from other boids,
alignment: steer towards the average heading of other
local boids
cohesion: steer to move toward the average position
(center of mass) of local boids
More complex rules can be added, such as obstacle
avoidance and goal seeking.
[1] Reynolds CW. Flocks, herds and schools: A distributed behavioral model. ACM
SIGGRAPH Computer Graphics. 1987 Aug;21(4):25–34
Also see http://www.red3d.com/cwr/boids/
17 / 23
Swarm Intelligence
Example: Swarm Intelligence for Animation
Flocking can be simulated in
computers
Flocking uses rapid short-range
communication
Behaviour governed by mutual
avoidance, alignment and affinity
Simple rules generate complex
behaviour
18 / 23
Swarm Intelligence
Example: Ant Colony Optimisation
Technique for solving problems which can
be expressed as finding good paths through
graphs.
Each ant tries to find a route between its
nest and a food source.
The behaviour of each ant is as follows:
Wander randomly at first.
If food is found, return to the nest
laying down a pheromone trail.
If pheromone is found, with some
increased probability follow the
pheromone trail.
Once back at the nest, go out again
in search of food.
Photo by Mehmet Karatay.
Pheromones evaporate over time, such
that unless they are reinforced by more
ants, they will disappear.
19 / 23
Swarm Intelligence
Example: Ant Colony Optimisation
1 The first ant wanders randomly until
it finds the food source (F), then it
returns to the nest (N), laying a
pheromone trail.
2 Other ants follow one of the four
possible paths at random, also laying
pheromone trails. Since the ants on
the shortest path lay pheromone trails
faster, this path gets reinforced with
more pheromone, making it more
appealing to future ants.
3 The ants become increasingly likely to
follow the shortest path since it has
the most pheromone. The pheromone
trails of the longer paths evaporate.
[2] Dorigo M, Stützle T. Ant Colony Optimization. The MIT Press; 2004
20 / 23
Other examples
Over the course of this module, we will look at:
Cellular automata
Coordination amongst fireflies
Swarm intelligence
Modelling the spread of diseases
Artificial life
Market-based control of computation systems
Neural networks
Evolutionary algorithms
...and more!
21 / 23
Why Natural Computation?
Flexible: applicable to different problems.
Robust: can deal with noise and uncertainty.
Adaptive: can deal with dynamic environments through self-adaptation.
Autonomous: can function without human intervention.
Decentralised: without a central authority.
22 / 23
Further Reading
Reynolds CW.
Flocks, herds and schools: A distributed behavioral model.
ACM SIGGRAPH Computer Graphics. 1987 Aug;21(4):25–34.
Dorigo M, Stützle T.
Ant Colony Optimization.
The MIT Press; 2004.
Floreano D, Mattiussi C.
Bio-Inspired Artificial Intelligence: Theories, Methods, and Technologies.
Mit Pr; 2008.
Shasha D, Lazere C. Natural Computing; 2010.
Available from:
http://www.drdobbs.com/high-performance-computing/223101723.
Marrow P.
Nature-inspired computing technology and applications.
BT Technology Journal. 2000;18(4):1323.
23 / 23
