1  using System;
   2  using System.Collections.Generic;
   3  
   4  class Genome : IComparable<Genome> {
   5  
   6      public Genome() {  // Set value randomly
   7          for (int k = 0; k < N_; k++) genome_[k] = random();
   8          setFitness();
   9          }
  10  
  11      // Mutute by moving a random queen a random distance along its column
  12      public Genome(Genome genome) {
  13          for (int k = 0; k < N_; k++) genome_[k] = genome.genome_[k];
  14          mutate();
  15          }
  16  
  17      private void mutate() {
  18          // Select random queen and random newPosition:
  19          byte queen = random();
  20          byte oldPosition = genome_[queen];
  21          byte newPosition = random();
  22          while (newPosition == oldPosition) newPosition = random();
  23          genome_[queen] = newPosition;
  24          setFitness();
  25          }
  26  
  27      // Crossover at random point:
  28      public Genome(Genome parent1, Genome parent2) {        
  29          byte crossoverPoint = randomCrossover();
  30          for (int k = 0;              k < crossoverPoint; k++) genome_[k] = parent1.genome_[k];
  31          for (int k = crossoverPoint; k < N_;             k++) genome_[k] = parent2.genome_[k];
  32          setFitness();
  33          // Avoid inbreeding:
  34          if(ExactCompareTo(parent2)==0 || ExactCompareTo(parent1)==0) mutate();
  35          }
  36  
  37      public int CompareTo(Genome otherGenome) {return (int)fitness_ - (int)otherGenome.fitness_;}
  38  
  39      public int ExactCompareTo(Genome otherGenome) {
  40          int fitnessDifference = (int)fitness_ - (int)otherGenome.fitness_;
  41          if (fitnessDifference != 0) return fitnessDifference;
  42          for (int k = 0; k < N_; k++) {
  43              int difference = (int)genome_[k] - (int)otherGenome.genome_[k];
  44              if (difference != 0) return difference;
  45              }
  46          return 0;
  47      }
  48  
  49      public override string ToString() {
  50          string result = "Fitness:  " + fitness_ + "\nRows: ";
  51          foreach (byte col in genome_) result += " " + col;
  52          return result;
  53          }
  54  
  55      private byte random()          {return (byte)random_.Next(N_);}
  56      private byte randomCrossover() {return (byte)random_.Next(1, N_ - 1);}
  57  
  58      public uint getFitness() { return fitness_; }
  59  
  60      private void setFitness() {   
  61          fitness_ = 0;  // Zero fitness is best.
  62          for (uint n=0; n < N_; n++) {  // For each queen ...
  63              uint row1 = genome_[n];
  64              uint black1 = (row1 + n) & 1;  // Nonzero if queen is on black square.
  65              for (uint m = n + 1; m < N_; m++) {  // For each queen in a higher column ...
  66                  uint row2 = genome_[m];
  67                  // If in same row, or (on same color square and on same diagonal), increment fitness.
  68                  // (Test for same color square avoids expensive computation half the time.) 
  69                  if(row1==row2 || (black1==((row2+m)&1)) && (m-n == Math.Abs((int)row1-(int)row2))) fitness_++;
  70                  }                
  71              }
  72          }
  73  
  74      static public void initializeRandom(uint workerNumber) {random_ = new Random((int)workerNumber);}
  75  
  76      static public string parameters() {
  77          return string.Format("Genome Parameter:" 
  78              + "\n\tNumber of queens:       {0:##0}"
  79              + "\n\tNumber of genome bits:  {1:#0.##}"
  80              + "\n\tMaximum fitness value:  {2:###,##0}\n\n",   
  81          N_, getNumberOfBits(), getWorstFitness());
  82          }
  83  
  84      // Data
  85      private byte[] genome_ = new byte[N_];
  86      private uint fitness_;
  87  
  88      // Worst fitness is (N_-1) + (N_-2) + (N_-3) + ... + 1, or:
  89      static private int getWorstFitness() {return N_ * ((int)N_ - 1) / 2;}
  90      static public double getNumberOfBits() {return N_*Math.Log(N_, 2);}
  91      static public byte N_;
  92  
  93      // Random class is not thread safe.  Therefore, use a different
  94      // Random class instance for each thread, as explained in
  95      // http://blogs.msdn.com/b/pfxteam/archive/2009/02/19/9434171.aspx
  96      [ThreadStatic] static private Random random_;    
  97  }
  98  
  99  class ExactCompareGenome : Comparer<Genome> {  // Use for instrumentation only
 100      public override int Compare(Genome genome1, Genome genome2) {return genome1.ExactCompareTo(genome2);}
 101  }