select.cc

PostsBayesian Optimization Algorithm with Decision Graphs in C++,

// ################################################################################
//
// name:          select.cc
//
// author:        Martin Pelikan
//
// purpose:       the definition of truncation selection and the divide and conquer
//                function it uses to separate the best
//
// last modified: February 1999
//
// ################################################################################

#include "population.h"
#include "select.h"
#include "random.h"

// ================================================================================
//
// name:          selectTheBest
//
// function:      performs truncation selection (selecting the best guys from the 
//                population); memory for the selected sad has to be allocated
//
// parameters:    population...the population where to select from
//                parents......the population where to put the selected to
//                M............a number of individuals to select
//
// returns:       (int) 0
//
// ================================================================================

int selectTheBest(Population *population, Population *parents, long M)
{
  register long i,j;
  long N;
  int n;

  // initialize some variables

  N = population->N;
  n = population->n;

  // shuffle the individuals a little

  for (i=0; i<N; i++)
    {
      j = (long) ((double)drand()*N);

      if (i!=j)
	swapIndividuals(population,i,j);
    };

  // perform quick-sort but only so that first M are better than the rest - no need for more

  divideBest(population,0,N-1,n,M);

  // copy M best to the population of selected strings

  for (i=0; i<M; i++)
    copyIndividual(parents,i,population->x[i],population->f[i]);

  // get back

  return 0;
}

// ================================================================================
//
// name:          divideBest
//
// function:      do divide-and-conquer until the first M individuals are better or 
//                equal than the rest
//
// parameters:    population...the population from which to separate the best M
//                left.........a pointer pointing to the left-most individual of
//                             the currently processed part of the population
//                right........a pointer pointing to the right-most individual of
//                             the currently processed part of the population
//                M............a number of individuals to separate
//
// returns:       (int) 0
//
// ================================================================================

int divideBest(Population *population, long left, long right, int n, long M)
{
  long l,r;
  float pivot;

  l = left;
  r = right;

  pivot = (population->f[l]+population->f[r])/2;

  while (l<=r)
    {
      while ((l<right)&&(population->f[l]>pivot)) l++;
      while ((r>left)&&(population->f[r]<pivot)) r--;

      if (l<=r)
	{
	  if (l!=r)
	    swapIndividuals(population,l,r);

	  l++;
	  r--;
	}
    };

  if ((l==M)||(r==(M-1)))
    return 0;
  
  if ((r>=M)&&(left<r))
    divideBest(population,left,r,n,M);

  if ((l<M)&&(l<right))
    divideBest(population,l,right,n,M);
  
  return 0;
};