7.   Which of the following genotypes is a possible result of 1-point crossover between these two parents: [01110011] [11001100]

A.  [11111100]

B.  [01001101]

C.  [01110001]

D.  None of the above

8.   Consider a simple two-variable search problem in which each variable can

take one of five different values, A, B, C, D, or E. The two-dimensional search space can be viewed from above as a 5-by-5 grid with each cell containing the  score of the associated solution. Which of the following fitness landscapes is

deceptive (assuming local search changes one variable to its immediately adjacent value, e.g., a B can be changed to A or C)?

A.   A B C D E

A 5 4 5 4 4

B 4 4 5 4 4

C 4 4 5 4 4

D 4 5 4 4 4

E 5 4 4 4 5

B.        A B C D E

A 1 1 5 5 8

B 2 1 2 9 5

C 3 1 1 2 5

D 4 2 1 1 1

E 5 4 3 2 1

C.        A B C D E

A 1 0 1 5 9

B 2 1 0 1 5

C 3 2 1 0 1

D 4 3 2 1 0

E 5 4 3 2 1

D.        A B C D E

A 9 8 7 8 9

B 8 7 6 7 8

C 7 6 5 6 7

D 8 7 6 7 8

E 9 8 7 8 9

9.   Which of the following is NOT away of increasing diversity in a population?

A.  Restricted mating

B.  Discarding duplicate offspring

C.  Fitness sharing

D.  Decreasing mutation rate

II.1   Logic Programming and Search (this question has two sub-parts: a and b):

a)   Suppose  you  are  given  a  Prolog  program  consisting  of  ground  instances  of  the following five predicates, which represent facts about movie titles in terms of their release year, their directors, their cast of actors/actresses, and any Oscar nominations: movie(Title, Year),  director(Title, Name),  actor(Title, Name, Role), actress(Title,  Name,  Role) and  nominated(Title,  Category)  —  where Category is   a   Prolog   term    of   the   form:    best_picture,   best_director, best_actor(Name, Role) or  best_actress(Name, Role).

Note that the first four predicates are the same as the movie database in the lectures, while the  fifth predicate  associates  a  movie with  any  of the  four  possible  Oscar nomination categories listed above. Also note that, unlike actors/actresses (who will each  be  nominated  for  a  specific  role  in  a  particular  film),  a   best_director nomination will be implicitly shared by each of a film’s directors. Here is a sample encoding of a famous movie:

movie(sleuth, 1972).

director(sleuth, joseph_mankiewicz).

actor(sleuth, laurence_olivier, andrew_wyke).

actor(sleuth, michael_caine, milo_tindle).

nominated(sleuth, best_director).

nominated(sleuth, best_actor(laurence_olivier, andrew_wyke)). nominated(sleuth, best_actor(michael_caine, milo_tindle)).

You are now required to solve each of the following three tasks by writing a “simple” Prolog query that only contains variables, constants, the five predicates listed above  along with the standard operators for conjunction ( ,), disjunction (;), negation (\+),  term equality (==), integer comparison (<) and term comparison (@<). Each of your  queries should terminate after returning all correct answers (at most some finite number  of times) under default Prolog computation and search rules.

i     Write a simple Prolog query which returns any director D (like joseph_mankiewicz) who received at least one best_director nomination.   [1 mark]

ii    Write a simple Prolog query which returns any director D who received at least two best_director nominations (for any films in any years).  [2 marks]

iii   Write a simple Prolog query which returns any director D who has never received any nominations for a best_director award.  [3 marks]

b)   This part of the question concerns a search problem in which a knight chess piece must move from the bottom left corner to the top right corner of a 5x5 grid. On each turn, the knight must go two cells horizontally or vertically followed by one cell orthogonally (while staying on grid). As shown below, a knight at cell “x” has 6 possible moves to any of the cells “a-f” – which have been labelled in order of a particular tie-breaking strategy, assumed in this question, that gives precedence to rows closer to the top of the grid and columns closer to the left of the grid (in that order of priority):

i     Given that the knight initially starts in the bottom left corner of the grid, complete the following representation of the grid, which indicates the order in which cells would be added to  a  breadth-first  search  agenda  (under  the  tie-breaking  strategy  described above).  Note that you may assume the algorithm stops as soon as the goal cell in the top right corner has been added to the agenda.  [3 marks]

+----+----+----+----+----+

|  3 |    |    |    |    |

+----+----+----+----+----+

|       |       |    |    |    |

+----+----+----+----+----+

|    |  1 |    |    |    |

+----+----+----+----+----+

|    |    |  2 |    |    |

+----+----+----+----+----+

|   0 |    |    |    |    |

+----+----+----+----+----+

ii     Explain  how  breadth-first  search  would  compare  with  depth-first  search  on  this particular problem (assuming the same tie-breaking strategy) in terms of the length of the path computed, the number of nodes added to agenda (i.e. opened) and the number of nodes expanded (i.e. closed) before the goal is reached.  Justify your answer.    [3 marks]

iii    Explain  which,  if any, of these observations are guaranteed to hold in any search problem.  [1 mark]

iv    In order to use A* search on this problem, it is necessary to find an admissible heuristic for estimating the number of moves needed by the knight to reach the goal. Prove that the Manhattan distance is not admissible and state a simple variation that is admissible. [2 marks]

II.2      Genetic Algorithms

Bob and Sue are working on a genetic algorithm to solve a drug design problem. Each

genotype specifies the active chemical ingredient(s) in a new skin cream. The associated    fitness is how well the cream treats a particular skin rash. Currently their algorithm is only able to discover quite mediocre solutions to this problem.

a)    Name two potential features of the problem's fitness landscape that could be the reason for the poor performance.   [1 mark]

b)   Sue thinks the algorithm should employ Elitism, but Bob is not sure what that is and thinks it may slow the algorithm down. Explain to Bob exactly what Elitism is and

suggest whether it should be turned on or off and why.    [3 marks]

c)    Bob wants to improve the algorithm performance by increasing the mutation rate.    Sue thinks the mutation rate could already be too high. What advice would you give them? Make sure you give detailed explanations for why each of these ideas might   be good or bad.   [4 points]

d)   Sue explains that each genotype specifies the mix of different chemicals forming a    cream (e.g., a genotype that starts [1.2, 5.3, ...] might specify that the cream should contain 1.2% of chemical A, 5.3% of chemical B, etc.). Two similar genotypes will

specify a similar blend of ingredients that will often have a similar performance as a  skin cream, but sometimes a small change in the balance of the chemicals can make a big difference to the effectiveness of the cream. Bob is worried that the evolved     solution might be very sensitive to the exact balance of chemical ingredients and

that if the cream production process is not absolutely perfect the cream produced might not be effective or could even be harmful. Sue thinks that it shouldn't be a   problem. Help Sue to reassure Bobby explaining the concept of the quasi-species. [7 marks]