Evaluating fitness

Evaluating the fitness of a member of the population is a matter of testing each character to see if it is a 0 or a 1 and adding up the weights of the objects included in the packing. If the weight of object i is stored in w[i] then the weight of a packing given by gene g is simply:

private double eval(String g, 
                    double[] w,
                    double max, 
                    int n)
{
 //return fitness of g
 double tw = 0;
 for (int i = 0; i < n; i++)
 {
  if (g[i] == '1')
  {
    tw = tw + w[i];
  }
 }
 double e = 0;
 double d = max - tw;
 if (d >= 0)
 {
  e = tw / max * 100;
 }
 return e;
}

We have to use this to assign a fitness to each member of the population:

private double[] evalPop(String[] pop, 
                         double[] w, 
                         double max, 
                         int p, 
                         int n)
{
 //evaluate the fitness of all
 //members of the population
 double[] fit = new double[p];
 for (int i = 0; i < p; i++)
 {
  fit[i] = eval(pop[i], w, max, n);
 }
 return fit;
}

The next stage is technically the most difficult to describe. Method Breed uses select to pick members of the population with a probability proportional to their fitness, that is the higher the fitness the more likely a gene is to be selected.

This might at first seem like a difficult thing to do but it is surprisingly easy. If you work out the sum of all the fitness values for the population, popfit, then all you have to do is generate a number in the range 0 to totalfit. Then if you imagine a line marked off into intervals corresponding to the fitness of each gene then the gene that is selected corresponds to the interval that the random value falls in.

Confused?

Well a simple example will make everything clear. Suppose the fitness values are 10, 20 and 5. These can be marked off on a line as:

           10                   20    5

|----------|--------------------|-----|

0          10                   30    35

Now you should be able to see that if you generate a random number r in the range 0 to 35 then the probability of selecting each of the genes is proportional to the size of the corresponding interval - which is of course exactly what is required!

You can even tell which interval the random value r falls in by comparing it to the running sum of fitness values. Suppose r is 32, then r<10 is false, r<10+20 is false but r<10+20+5 is true so r is in the third interval.

This translates into:

private int select(double[] fitness)
{
 double totalFit = fitness.Sum();
 double r = Rnd.NextDouble() * totalFit;
 int i = 0;
 double sum = 0;
 do
 {
  sum += fitness[i];
  i++;
 }
 while (sum < r);
 return --i;
} 

The genes selected are stored in a new array breedPop. As select picks genes at random there is no need further to randomise the pairing off required for the next stage. As they are random we might as well pair adjacent genes and perform the necessary crossover operation  using method cross. 

>This is a simple exercise in string handling. A random point in the string is chosen, c, and the first c bits of the strings are swapped over.

private string cross(String n1, 
                       String n2, int n)
{
 int c = Rnd.Next(n);
 return n1.Substring(0, c) + 
                      n2.Substring(c);
}

To make things a little simpler the cross over is done in an asymmetrical way. That is gene i is replaced by a cross with gene i and gene i+1 and so on. 

private void breed(String[] population, 
          double[] fitness, int p, int n)
{
 String[] breedPop = new String[p];
 for (int i = 0; i < p; i++)
 {
  int j = select(fitness);
  breedPop[i] = population[j];
 } 
 for (int i = 0; i < p - 1; i++)
 {
  population[i] =cross(
    breedPop[i].ToString(), 
      breedPop[i + 1].ToString(), n);
 } 
 population[p - 1] = cross(
    breedPop[0].ToString(), 
     breedPop[p - 1].ToString(),n);
}