Evolutionary Computation and Artificial Life (202-1-5171), Semester A, 2006-2007

Sample Exam Questions

Note: exam material includes everything we discussed in lectures + homework.

1. (TSP) Use order crossover to cross the parents:
   

      (1 2 3 4 5 6 7 8 9)
      (7 8 9 1 2 3 4 5 6)
   

2. What does the schema theorem say about the results of a GA run over several generations?
3. What is a coevolutionary algorithm? What are its advantages? Write the pseudocode.
4. What is "ramp half-and-half"?
5. We wish to solve the N-Queens Problem with a GA. Define a fitness function and a crossover operator for this problem.
6. Can the following mapping be learned by a single-layer perceptron. Explain.
   

       x y  output 
       0 0    0 
       0 1    1 
       1 0    0 
       1 1    1 
   

7. Consider the following two successive time steps of a 1D cellular automata (CA):

   t  :  0 1 0 0 1 0 1 1 1 0 0 
   t+1:  0 1 1 0 0 1 0 1 0 1 0
   

   Is this possible for an r=1 CA? How about an r=2 CA? Explain both cases.