The second Continuous Assessment has now been set. There will be an extra "drop in" tutorial on Tuesday 8th December from 10-12 in room 245 for those who need help with their program.
Please note: the lectures on Wednesdays from 12-1 will now be held in LAW LT2.
Tutorials for MSc and ICY students will be held on Wednesdays at 10am in Computer Science room 245.
Week 1: Introduction
Summary: Introduction to the module and subject area. Comparison with Computational Biology and Artificial Life. Example: bluegill sunfish nesting in riverbank. De-centralised control (local rules). Interactions (non-linear - what does "linear" mean anyway?). Stochasticity (modelling uncertainty/unknowns). Criticality and phase transitions (governed by a particular parameter). Emergence of global pattern from local interactions. Exercise: how to implement such a simulation? Example: flocking and schooling. Rules: separation/avoidance, cohesion/attraction, alignment. Possible applications.
Further reading: Boids project. Chapter 11 of "Self-Organization in Biological Systems" (Camazine et al). Nissan are now using the "fish schooling" method to coordinate robot cars. See Robot cars to mimic shoals of fish
Exercises:
1. Check out the Mason web site. Try some of the example simulations. If you are interested in using this Java library, download it and experiment.
2. Implement a simple simulation of fish choosing a nesting location. Assume the fish arrive one at a time. They try several random positions. If they find a position near an existing nest they will settle there. If they don't find such a position, they just settle somewhere randomly. How long is it before a coherent pattern is established?
3. Try building your own fish! Visit the virtual fish-tank.
Week 2(a): Interactions and games
Summary: Pairwise interactions. Game matrices. Chicek example. Single dominant strategy. Asymmetric games. Nash equilibrium (can't improve payoff unilaterally). Mixed strategies. Analysis of Chicken (Hawk-Dove) example. Prisoner's Dilemma - optimal strategy is unstable. PD as a model of cooperation and altruism. Importance of repeated interactions.
Further reading: Chapters 28 and 29 of "Metamagical Themas" by Douglas Hofstadter (in Short-Term Loan collection of Main Library).
Exercises:
1. In the two-player game Caution, each player decides independently whether to act cautiously or take a risk. A player acting cautiously always gets a low pay-off. A player taking a risk gets a high pay-off if the other player also takes a risk. Otherwise, the risk-taker gets nothing. What is the Nash equilibrium? Is it optimal? Can you think of any real-world situations that are like this game?
2. A group of people have gone to dinner at a restaurant, and decide they will share the bill equally between them. Each person then decides whether to a) choose something cheap from the menu or b) choose something expensive. Express this situation as a game, and consider the possible strategies and their outcomes. What would you do in this situation?
Week 2(b): Populations and cellular automata
Summary: Populations of interacting elements. Perfectly mixed populations. Synchronous and asynchronous algorithms. Spatially structured populations. Cellular automata (definition). Moore and von Neumann neighbourhoods. Worlds that wrap-around (toroidal). Transition rules. Synchronous and asynchronous update. Simple infection model. Game of Life (Conway). Various configurations (block, blinker, glider). Web demo of Conway's Life. CA implementation of Spatial Prisoners Dilemma
Further reading: Type "game of life" into Google to find out more about Conway's game. Chris Langton invented a cellular automaton pattern that could self-replicate. This followed work by von Neumann. You can read about it, and other self-replicating CAs here.
Exercises:
1. Implement a simple cellular automaton to simulate the spread of an infection, as described in the lecture.
2. Use a "Game of Life" simulator from the web to experiment with various forms. If the world starts of with randomly assigned cell states, what happens when the system runs (as a function of the proportion of "live" cells)?
Week 3(a): Firefly co-ordination
Summary: A more detailed look at how a CA could be used to test a hypothesis about a natural system, and how such a system gives rise to a new algorithm which we can exploit. Male fireflies flash to attract mates. Different species have different periodicity. Some species flash in unison. Why? More likely to attract females. Example of co-operation/altruism. How? Experiment with coin tapping. Hypothesis about firefly oscillator sequence, with resets from neighbours. Testing with simulation. CA grid, states cycle around. Sensitive period when neighbours flash causes reset (lock step with neighbour). Assume simultaneous update. Empirical questions: do they synchronise? how long does this take? what parameters does this depend on? what happens with asynchronous update? Potential applications.
Further reading: See a video of firefly synchronisation. Read Chapter 10 of "Self-organization in Biological Systems". There is a book called "Sync" by Steven Strogatz that examines these phenomena (in Main Library).
Exercises:
The first Continuous Assessment has now been set. Here are some hints.
Week 3(b): Particle Swarm Optimisation
Summary: Optimisation as an application: we are not concerned with realism. The problem of function optimisation. Local search: single particle. Possible solutions correspond to positions in an abstract space. Swarms of interacting particles. Particle specified by position and velocity (vectors) initially random. Update velocity v := r1 v + r2 (p - x) + r3 (g - x). Update position x := x + v. Velocity is normally capped at some maximum. Variants: local best instead of global best. A nice visualisation tool.
Further reading: Chapter 7 of "Swarm Intelligence" by Kennedy and Eberhart.
Exercises:
1. Implement a Particle Swarm Optimisation algorithm for problems where there is just one variable (so the positions and velocities are single real numbers). Use it to try to minimise the following function: f(x) = x + (x cos(2x)), where x varies from 0 to 10.
2. Write a graphical front end to your code to display the positions of the current population at each time step.
Week 4(a): Small worlds
Summary: Characterising network topology. Ordered networks e.g. lattices. Random networks (with fixed degree). Social networks are "between order and chaos". Path length between nodes. Average path length for a node. Characteristic path length for graph is median of these. Ordered graphs: length scales linearly. Regular random graphs: length scales logarithmically. The small world effect. Cluster value of a node: probability that its neighbours are connected. Cluster coefficient: average of all cluster values. Ordered graph: large cluster coefficient. Regular random graphs. cluster coefficient tends to zero. Social networks have logarithmic length scaling, and large cluster coefficient. Model 1: lattice rewiring. Model 2: preferential attachment (scale-free). The Internet as an example of a scale-free network.
Further reading: Wikipedia has a nice article.
Exercises:
1. Make a list of people you know well. How many of them know each other? Work out your cluster value. Compare the result with other people.
2. Investigate the shortest path of aquaintances between yourself and various people round the world. Do you see a pattern in how such paths are constructed? What does this tell you about the topology of this social network.
3. Check out the Kevin Bacon Game which links movie actors together by films they have co-starred in.
Week 4(b): Propagation time in networks
Summary: The propagation problem - random transmissions. Stochasticity, discrete time, parallel updates. Example: chain (n-1)/p. Asymptotics and expectation. Example: hub log(n)/p. Star graph with s branches and branch length b. (b + log s)/p. General upper bounds for networks with diameter D: (D + log n)/p. General lower bound of D/p.
Further reading: Here is an interesting project on the prisoner's dilemma played by populations on a network..
Exercise:
1. Calculate the upper and lower bounds for a complete network (i.e. one in which each point is connected to every other point). Implement this system to see what the real propagation time is like.
2. Implement the propagation problem on a CA with von Neumann neighbourhood. See how the average time varies with the number of cells, and the transmission probability p.
Week 5(a): Random walks on spatial networks
Summary: Model of migration: random walk on graph. N.B. no interaction in this model. Define neighbourhood and degree of node. Theorem: steady-state depends only on degree of nodes. What kind of networks should we see for spatial networks? Distribution of nodes randomly in space, with connection range r. Expected number in range is mu = Pi r^2 N/W. Random distributions in space (or time) follow Poisson distribution. P(x) = mu^x exp(-mu)/x!, where mu is average. Example: probability of isolated node. Example: sum of all degrees in such a network.
Exercises:
1. Implement a population doing a random walk on a Cellular Automaton grid. Measure the population density at each cell on average over the run. What difference does the type of neighbourhood make? What difference does "wrapping round" the edges make?
2. Use the work we did in the lecture to mathematically predict the behaviour of the population in the previous exercise.
3. In a random spatial graph, investigate how big the population size N has to be so that the expected number of isolated nodes is less than 1.
Week 5(b): Random Boolean Networks
Summary: A general view of network interactions.What kind of behaviour is expected - ordered or unordered? The origins of order: Designed systems have certain characteristics. Natural systems share these (e.g. cell cycles, gene control). Could these arise without a designer? (N, K) Random Boolean net definition. Behaviour k=1: Fixed-points and very short cycles. Behaviour k=3 or more: very long cycles - not strictly random, but near enough. For k=2: some fixed-points, but many cycles of different lengths (average cycle length sqrt(N)). Basins of attractions (few for k >= 3,. Many for k=2). Hypothesis: change of state for a system corresponds to moving to different basin of attraction. Edge of chaos hypothesis - order for free.
Further reading: 2. If you are interested in the "Origins of Order" problem, then you might like to read "Investigations" by Stuart Kauffman (in the School Library).
Exercise:
1. Implement a Random Boolean Network simulator using a cellular automaton. Each cell picks k of its neighbours to be "connected to". Each cell has its own random update table. Try running the system from different starting configurations with k = 0, 1, 2, 3, 4.
Week 6(a): SIR model - perfect mixing
Summary: S = susceptible, I = infected, R = removed (recovered and immune). These are proportions, so S+I+R=1. Assumption: population size is large. Assumption: perfect mixing. Change in S = Births - deaths - move to infected (b-dS-aIS). Change in I = new infections - recovered - natural death - death from disease (aIS - cI - dI - vI). Change in R = recovered - natural deaths (vI - dR). Equilibrium from 2nd equation: S = (d+c+v)/a = psi/a. (psi = rate at which infecteds leave population). Equilibrium from 1st equation: I = b/psi - d/a. I > 0 if ab/(d psi) > 1. If birth rate = death rate, b=d. a/psi = R0, the basic reproductive rate of the infection.
Further reading: The Black Death (1347-1350) killed one third of the population of Europe. Find out more here.
Exercises:
1. Adapt the model to account for vaccinations (these make Susceptibles become immune). What proportion of the susceptible population should be vaccinated to prevent an epidemic?
2. In the case of animal diseases such as bird flu, infected individuals are killed. This is called "culling". Adapt the model to include culling - what proportion of the infected population must be culled to prevent an epidemic?
3. Find out how many people were killed in the Spanish Flu epidemic of 1918.
Week 6(b): Tutorial for first CA
Week 7(a): Epidemiology - spatial model
Summary: Modelling random spatial networks. Parameters: population size, world size and radius of infection. Data structures for connectivity. Asynchronous update algorithm. Disease Parameters: infection spread rate, recovery rate, mortality rate. Births and deaths. Hypotheses and experiments.
Further reading: Read about amorphous computing. Consider its relationship with the disease models we have been looking at.
Exercises:
The second Continuous Assessment has now been set.
Week 7(b): Perceptrons
Summary: Input grid (retina) and a population of detectors. Detectors may be bound by region, or by order. Each detector can send a message True (+1) or False (-1). Each detector is given a weight. The perceptron calculates the weighted sum of the detectors. If this is above a threshold, then the preceptron returns True, else False. Problem: what can be deduced about the global pattern on the retina from the population of local observers? Example: are more cells on than off? Example: are threequarters (or more) cells on? We can always assume the threshold is zero by introducing an extra detector that always returns +1. This is called the "bias". Problem: how to find the weights? You don't need to consider negative examples, just minus them and think of them as positive examples! Perceptron learning algorithm (start with random weights, any pattern that is below threshold add on to weights). Guaranteed to converge if there is an answer. Otherwise will eventually cycle (difficult theorem).
Further reading: Read about the history of perceptrons..
Exercises:
1. Construct an order-1 perceptron with two detectors to compute the logical AND function.
2. A shape is convex if a straight line between any two points in the shape is also in the shape. Work out the detailed design for an order-3 perceptron to recognise convex shapes.
3. Find out about neurons in the brain. What similarities are there with the perceptron architecture?
Week 8(a): Feed-forward neural nets
Summary: XOR can't be implemented with a single perceptron. But any computation can be done with enough layers or perceptrons. Problem: how to find the weights. First trick: smooth the activation function 1/(1 + exp(-a x.w)) Second trick: start at the end and work backwards. Present a pattern, work out result. Compare with target. Update weight from node i to node j by w_{i,j} := w_{i,j} + lambda slope_j error_j x_i (where lambda = learning rate). slope_j = a y_j (1 - y_j). For the output layer error_j = t_j - y_j For hidden layers error_j = slope_j r where r is the propagated error, r = \sum_k slope_k error_k w_{j,k} (we sum over all nodes k to which j feeds). This is the "backpropagation" algorithm. It is not guaranteed to converge to solution. You may have to iterate through many cycles. Often have to start again with new random weights.
Exercises:
1.Show how perceptrons can be chained together to compute the XOR function.
2.(Mathematical) If a node receives total input x, then its output is given by the activation function y = 1/(1 + exp(-a x)). Show that the slope of this function for a particular input x is given by a y (1-y).
Week 8(b): Self-organising maps
Summary: Supervised and unsupervised learning. Topological maps in the brain. Kohonen's SOM architecture. Use a 2D grid (like a CA) to hold the neurons. Each node in the grid has weighted links to all inputs. When an input is presented, node with closest weight vector is selected to catergorise it. Weights of all nodes are updated: w(k) := w(k) + r(k) lambda (x - w(k)). Lambda is a learning rate. It starts at 1 and slowly decreases to 0. r(k) takes account of how far node k is from winning node on grid. It is 1 for winning node and decreases to 0 for some maximum radius theta. The value of theta is reduced slowly to 0. Localised areas of the grid come to represent similar patterns. Distant parts of the gris represent very different patterns. Application: phonetic typewriter.
Further reading: Here is a very good tutorial.
Exercises:
1. How do you think the behaviour of the SOM is affected by the number of nodes in the grid?
2. Read about some application areas. Can you invent some more?
Week 9(a): Elementary genetics
Summary: DNA structure: sugar+phosphate backbone with nitrogen bases acting as steps on ladder. Adenine binds to thymine, cytosine binds to guanine. Twists into double helix. Sequence of bases specifies information about cell growth and behaviour. The genetic code specifies how sequences of 3 bases map to different amino acids. Amino acids group together to form proteins. Bodies are made of proteins and are run by proteins. Most cells in body reproduce by splitting and eventually die. In sexually reproducing species, DNA molecules occur in pairs called chromosomes. (E.g. humans have 23 pairs in each cell). In gametes (the germ cells) there is only one from each pair. Male gamete fertilises female gamete to create new set of pairs. Gametes are made by special splitting process which shuffles the DNA between pairs (crossover). Chromosome pairs may act as back-up copies for each other to protect against lethal mutations.
Further reading: Find out more about DNA structure.
Exercises:
1. How many bytes of memory could be stored in the DNA of a single human cell?
2. If your eyes are blue, then you must have recessive blue-eye genes. If they are brown, then there are various possibilities. Find out the colour of your parents' and grandparents' eyes and try to work out the possible combinations that could have arisen. (Click here for a more complex model that incorporates green eyes).
3. Write a computer program (in any language) so that, when it runs, it outputs an exact copy of its own source code.
Week 9(b): Lecture cancelled
Week 10(a): Elementary evolution
Summary: Darwin's principles: variation, inheritance, selection (survival of the fittest). Modern synthesis: Darwin + Mendel + genetics. Adaptation: what does survival of the fittest mean? Fit for what? Definitions of fitness. Measure of reproductive success. Success of gene/strategy/way of life depends on environment and who else is around. Speciation, e.g. through geographic separation. What kind of time scales? How many generations?
Further reading: Richard Dawkins has written some excellent books. Try "The Selfish Gene" and (more recent) "The Ancestor's Tale". Humans nearly went extinct: find out more here. Find out more about other human species here
Read the tutorial on the evolution of the eye.Exercises:
1. Find out how similar human and chimpanzee DNA is.
2. How quickly does the bacteria E. Coli repliate? Estimate how many generations of E. Coli occur within a typical human gut. Compare with how many generations have occured since the common ancestor of humans and chimpanzees.
Week 10(b): Genetic algorithms
Summary: 1. Artificial evolution - the idea. DNA = representation of solution. Populations assume fixed-size and perfect mixing. Fitness = objective function (depends on application). Generational algorithm (selection + reproduction). Tournament selection and fitness proportional selection. Reproduction: crossover and mutation. Example applications: real-valued parameter problems; combinatorial problems like Knapsack (Genetic Algorithms).
Further reading: A good introduction is Melanie Mitchell's book "An introduction to genetic algorithms". Here is a list of applications of genetic algorithms.
Exercises:
1. What key features of real evolution and genetics are missing from basic evolutionary algorithms? How might these be implemented, and what effects would they have?
2. Try implementing a genetic algorithm to solve randomly generated examples of the Knapsack problem.
Week 11(a): Applications of evolutionary algorithms
Summary: Four very different types of applications of evolutionary computation: evolution of spider webs (Krink), evolution of language (Steels), evolution of artificial motion control (Sims), evolution of improvised jazz music (Biles).
Further reading: Here are links for: Krink's original paper on spider webs, Luc Steels' talking heads project, Karl Sims' evolved virtual creatures, Al Biles' GenJam project.