Artificial Life Prep Questions Martin F. Krafft

Contacts

• Miriam Fend: fend at ifi.unizh.ch
• Martin F. Krafft: krafft at ifi.unizh.ch

Administrativa

The following questions are presented to aide you in exam preparation, and to solidify your understanding of the topics discussed in the lecture. You are encouraged to attempt to solve the questions on your own prior to discussing them with your peers via the discussion list. At the beginning of each lecture we shall seek a volunteer to present the answer to the question in front of the class.

We encourage everyone to submit interesting questions about the topics to us. We don't guarantee anything, but it is quite possible that your questions might turn up on the final exam. So use the opportunity, and submit your own questions, along with appropriate answers, to the assistants!

Questions

(I) Basics

1. Which of the following is NOT one of the characteristics of Artificial Life?
   1. Reproduction
   2. Intelligent individual behaviours
   3. Bi-directional escalation
   4. Emergent group behaviours

(II) Pattern Formation

(a) Cellular Automata

1. What is rule 101?
2. What is the configuration of cellular automaton defined by the starting pattern 01011, rule 101 with periodic boundaries, k=2, and r=1, after 5 iterations?
3. What is the effect of r? What would increasing r cause? How about k?

(b) The Game of Life

1. What is the configuration of the following square after two iterations of Conway's rules for the Game of Life (23-3) with a periodic boundary? x indicates the on state:

       o x o x x
       x o o o o
       o o o x o
       o o x o o
       x x x x x
       

2. What do you make out of the discussion on Universal Computation in the script on page 2.12? Can you spot an error in the text?
3. Which of Wolfram's classes of behaviour is most closely exhibited by the "Exploder" simulation in Conway's Game of Life?
   1. Static
   2. Repeating
   3. Chaotic
   4. Complex

(c) L-Systems

1. Draw the L-System described by the axiom A and rule A = F[-A][+FA] to recursion depth 3. Assume the angle to be approx. 20 degrees. You don't have to be very accurate about this.

(d) Sea shells

1. Why do activation and inhibition have to be balanced in reaction-diffusion systems? What is important about the diffusion constants of the activator and the inhibitor? And why do we need a spatially stable pattern over time?

(e) Sand piles

1. Think of a situation in everyday life when the sand pile model of self-organised criticality can be applied. Obviously, the "bureaucrats" are not an option, just as much as the poor dog pulled on its leash isn't either.

(f) Artificial evolution

1. What are the differences between the developmental process of artificial evolution and natural development?
2. Think about the similarities and differences of artificial evolution and exhaustive searches (e.g. non-heuristic depth-first search)? When would you use artificial evolution? When would an exhaustive search be better? Can you think of problems which can be solved by one but not the other?
3. What are the components of the process of evolution? What are the variables in each component, and what are their meanings? How do the components fit together into the whole, continuous process of evolution?
4. What happens during reproduction to change the genome of the offspring?
5. Is artificial evolution guaranteed to find an optimal solution? Why or why not?
6. What is the problem with the elitist selection strategy? How is this problem addressed? Can you think of other selection schemes?
7. What has to be encoded in the genotype for the evolution of a neural network?
8. What was the important innovation of Karl Sims? What is the advantage for the evolutionary process?
9. Think of differences between the robots evolved by the Golem project and the Blockpusher.
10. What is a genetic regulatory network? [not an exam question]
11. Refer to the various evolutionary projects we showed. What is fixed by the designer in each case, and what is left to evolutionary control?
12. What different artificial evolutionary schemes do you know? List them, and brainstorm a little about each.
13. How do evolutionary strategies differ from genetic algorithms?

(g) Distributed Intelligence

1. What are didabots? Which sensors do they have? What are they programmed to do, and in what way does the behaviour they exhibit differ? Could a single didabot complete the task as well, or would there be problems?
2. Think of an example where distributed processing "buys you something" that would otherwise require control power (some inherent advantageous feature or behaviour that you'd have to implement in a non-distributed system, but which derives from distributed processing for free).
3. What is stigmergic interaction?
4. What are the three rules that make up flocking? What happens when you turn each one off individually?
5. What are points of usefulness of randomness?
6. What are the differences between flocks and an individual bird?

(h) Ant-Based Control

1. Describe how ant-based control can be used to route calls in telephone networks.
2. How does ant-based control differ between strongly connected graphs and hierarchical networks?
3. For fun: Pick an NP-complete (NP-vollständig) problem of your choice (Travelling Salesman might be the easiest, but then any NP-complete problem can be reduced to that), convert it into an optimisation problem, and apply ant-based control. See how cool this is? [not an exam question]
4. What are advantages of ant-based control? What about real-time control? What are disadvantages or problems that cannot be overcome with ant-based control?

(i) Sugarscape Model

1. What is metabolism? What does it define in artificial systems?
2. What causes the migration waves?