COMP3411 Artificial Intelligence
Session 1, 2016

Week 9 Tutorial - Constraint Satisfaction, Evolution

1. Use Forward Checking to show that the Australia map-colouring problem has no solution with WA=green, V=Red, NT=Red. If we apply Arc Consistency as well, can the inevitable failure be detected further up the tree?

2. Local Search

   Consider the following state for the 8-queens problem:

   

   1. is this a solution?
   2. what is the value of h?
   3. explain why Hill-climbing with Min Conflicts would get stuck in this state, but Simulated Annealing may be able to "escape" and eventually find a solution.

3. 6.6 Consider the following logic puzzle: In five houses, each with a different color, live five persons of different nationalities, each of whom prefers a different brand of candy, a different drink, and a different pet. Given the following facts, the questions to answer are "Where does the zebra live, and in which house do they drink water?".
   • The Englishman lives in the red house.
   • The Spaniard owns a dog.
   • The Norwegian lives in the first house on the left.
   • The Green house is immediately to the right of the ivory house.
   • The man who eats Hershey bars lives in the house next to the man with the fox.
   • Kit Kats are eaten in the yellow house.
   • The Norwegian lives next to the blue house.
   • The Smarties eater owns snails.
   • The Snickers eater drinks orange juice.
   • The Ukranian drinks tea.
   • The Japanese eats Milky Ways.
   • Kit Kats are eaten in a house next to the house where the horse is kept.
   • Coffee is drunk in the green house.
   • Milk is drunk in the middle house.

   Discuss different representations of this problem as a CSP. Why might we prefer one representation over another?
   Bonus Challenge: Write a Prolog program to solve this puzzle.

4. Evolution (If time permits)

   Consider the following four algorithms applied to the task of searching through the space of bitstrings of length 20 to find the bitstring which maximizes a given fitness function:

   1. completely random search
   2. hillclimbing
   3. genetic algorithm (GA) using mutation only (no crossover)
   4. genetic algorithm using one-point crossover as well as mutation

   For concreteness, let's assume that the GA has a population of 200, with 100 individuals replaced at each generation.

   For each of the fitness functions listed below, which of the four algorithms would find the solution fastest? which would be slowest? or would two of them take about the same amount of time?

   1.	f(x) =	the number of 1's in x.
   2.	f(x) =	100, if x = 00000000000000000000,
   		0, otherwise.
   3.	f(x) =	100, if x = 00000000000000000000,
   		the number of 1's in x, otherwise.
   4.	f(x) =	14, if x contains 7 consecutive 1's and 7 consecutive 0's,
   		7, if x contains 7 consecutive 1's or   7 consecutive 0's,
   		0, otherwise.