Problem 4.2

Problem 4.3

Problem 4.5

You do not have to draw a complete depth-first search tree. But do record your reasoning and justifications. Again, see the example below.

As an example, consider solving the the following problem:

   RA
  +AR
  ---
  AAH

The constraints are:

  A + R = H + 10 X
  R + A + X = A + 10 Y
  Y = A
  A not equal to 0 (leading zeros not allowed)
  AllDiff(A,R,H)

My reasoning is as follows:

• Choose the Y variable, because with domain {0,1} it has minimum remaining values (tied with X).
• Choose the value 1 for Y because choosing 0 would not survive forward checking: it forces A=0, but the leading digit must be non-zero.
• Choose the variable A because it has only one remaining value.
• Choose the value 1 for A.
• Now X has the minumum remaining values.
• Choosing 0 for X won't survive forward checking because with the assignments so far, the second contraint is R + 1 + X = 11, and choosing X equal 0 forces no remaining values for R.
• Choose 1 for X. Forward checking reduces the values for R to only 9.
• R now has only one remaing value.
• Choose the value 9 for R.
• The only variable left is H.
• Forward checking, the only vailue left for H is 0.
• This is a solution: Y=1, A=1, X=1, R=9, H=0.

Problem 4.6

Be reasonable in your choice of number of generations: a number between 20 and 50 should work well.

You can mutate before or after cross-over, your choice.

The function you are maximizing is a little different than one I used (which was set to zero between 0 and 0.3).

Problem 4.7

Below are some useful patterns/subroutines and portability notes. Here are some other hints to make your life easier:

• Random-restart hill climbing: For the hill-climbing part you need a way to generate all successors as well as a way to find on with the best fitness The random-restart part only requires picking a random encoding.
• Simulated annealing: Note that R&N provide pseudo-code in Figure 4.14, page 116. You might also see the Useful Subroutine metrop() below.

Useful Patterns/Subroutines

To obtain a random encoding, merely use the pattern

  int enc[8];
  mutate(enc,1.0); // mutation in place
  // OR use mutate2(enc,newenc,1.0); to store mutation in newenc array

The following routine is useful in a variety of local search algorithms. It returns the nth successor of an encoding, where n=1, ..., 56.

  void getsuccessor(int init[], int n, int succ[]) {
    n--;
    int remainder=(n%7);
    int quotient=(n-remainder)/7;
    // int newrow=1+((remainder+init[quotient]-1)%8);
    int newrow=init[quotient]+remainder+1;
    if (newrow>8) newrow-=8;
    for (int j=0; j<8; j++) {
      if (j==quotient) succ[j]=newrow;
      else succ[j]=init[j];
    }
  }

The following code generates all successors of 12345678, one-by-one, in order:

  int enc7[8]={1, 2, 3, 4, 5, 6, 7, 8};
  int enc8[8];
  for (int i=1; i<=56; i++) {
    getsuccessor(enc7, i, enc8);
  }

It can be modified to remember the best successor as follows:

  int bestE=0;
  int bestSuccIndex;   // to be index in {1, ..., 56} of highest fitness successor
  for (int i=1; i<=56; i++) {
    getsuccessor(enc7, i, enc8); 
    int f=fitness(enc8);
    if (f > bestE) { bestE=f; bestSuccIndex=i; }
    // The following line would add some randomness for equally-good ones
    // if ((f>bestE)||((f==bestE)&&(myrand()<0.1))) { bestE=f; bestSuccIndex=i; }
  } 

To obtain a random successor, just call the subroutine with a random integer between 1 and 56. Thus, the following code generates a random successor of 12345678:

  int enc7[8]={1, 2, 3, 4, 5, 6, 7, 8};
  int enc8[8];
  int RandomSuccIndex = (int) ceil(myrand()*56);
    getsuccessor(enc7, RandomSuccIndex, enc8);

The following subroutine is useful in simulated annealing:

  // Use: Metropolis Algorithm for Maximization
  //
  // Source: Based on the code and explanation
  // of a routine for minimization found in
  // Press et al., _Numerical_Recipes_in_C_,
  // Cambridge Univ. Press, 1988.  Page 351.
  //
  // Returns a boolean value on whether or not to
  // accept a reconfiguration which leads to a
  // change dE in the objective function E.
  // If dE>0, returns 1 (TRUE); if dE<=0, returns
  // 1 with probablity exp(dE/T), where T is a
  // temperature determined by the annealing schedule.
  //
  int metrop(double dE, double T) {
    double r=myrand();
    return ((dE > 0)||(r < exp(dE/T)));
  }

Portability Notes

  #include <sys/types.h>
  #include <unistd.h>

  srand48((long) getpid());

The function myrand() may be replaced by any function that provides a uniform random number between 0.0 and 1.0.

The function ceil() returns the integer greater than or equal to its argument. There are many way to replace its functionality, for example it could be replaced by round(x+0.5) (assuming, say, 1.5 rounds to 2).