k2.cc

贝叶斯优化算法是一种新的演化算法

// ################################################################################
//
// name:          K2.cc      
//
// author:        Martin Pelikan
//
// purpose:       functions for the initialization and use of the K2 metric
//
// last modified: February 1999
//
// ################################################################################

#include "K2.h"
#include "boa.h"
#include "population.h"
#include "memalloc.h"
#include "computeCounts.h"
#include "mymath.h"

// ================================================================================
//
// name:          initializeMetric
//
// function:      initializes the metric (do what is needed before the metric is
//                called for the first time)
//
// parameters:    boaParams....the parameters sent to the BOA
//
// returns:       (int) 0
//
// ================================================================================

int initializeMetric(BoaParams *boaParams)
{
  // precompute the cummulative logarithms

  precomputeCummulativeLogarithms(boaParams->N+3);

  // get back

  return 0;
};

// ================================================================================
//
// name:          computeLogGains
//
// function:      computes increases of the logarithm of the metric for the
//                additions of edges ending in a node i, starting in each of the
//                nodes given on input in the form of an array
//
// parameters:    i............the ending node of all edges for which the gain is
//                             to be recomputed
//                updateIdx....an array of nodes where the edges for which the gain
//                             is to be recomputed start
//                numUpdated...the number of nodes in the updateIdx array
//                parentList...the list of parents of the node i
//                numParents...the array of the parents of the node i
//                population...the current population of strings (a data set)
//
// returns:       (int) 0
//
// ================================================================================

int computeLogGains( int i, 
		     float **gain, 
		     int *updateIdx, 
		     int numUpdated, 
		     int *parentList,
		     int numParents, 
		     Population *population)
{
  long  j;
  int   k,l;
  long  **count;
  long  *tNwi,**Nwi;
  long  *tNPwi,**NPwi;
  long  *tNoi,**Noi;
  long  *tNPoi,**NPoi;
  long  numParentConfigurations;
  long  numParentConfigurations2;
  long  numParentConfigurations4;
  float result;

  // initialize some variables
  
  numParentConfigurations  = (long) 1<<numParents;
  numParentConfigurations2 = (long) numParentConfigurations<<1;
  numParentConfigurations4 = (long) numParentConfigurations2<<1;

  // allocate memory for counts of all n-ths

  if (numUpdated>0)
    count = (long**) Calloc(numUpdated,sizeof(long*));
  
  for (l=0; l<numUpdated; l++)
    count[l] = (long*) Calloc(numParentConfigurations4,sizeof(long));

  // allocate memory for N's and so (need only one of these)

  tNoi  = (long*) Calloc(numParentConfigurations,sizeof(long));
  tNPoi = (long*) Calloc(numParentConfigurations,sizeof(long));
  Noi   = (long**) Calloc(numParentConfigurations,sizeof(long*));
  NPoi  = (long**) Calloc(numParentConfigurations,sizeof(long*));  

  for (j=0; j<numParentConfigurations; j++)
    {
      Noi[j] = (long*) Calloc(2,sizeof(long));
      NPoi[j] = (long*) Calloc(2,sizeof(long));
    };

  tNwi  = (long*) Calloc(numParentConfigurations2,sizeof(long));
  tNPwi = (long*) Calloc(numParentConfigurations2,sizeof(long));
  Nwi   = (long**) Calloc(numParentConfigurations2,sizeof(long*));
  NPwi  = (long**) Calloc(numParentConfigurations2,sizeof(long*));  

  for (j=0; j<numParentConfigurations2; j++)
    {
      Nwi[j] = (long*) Calloc(2,sizeof(long));
      NPwi[j] = (long*) Calloc(2,sizeof(long));
    };

  // compute the counts -----------------------------------------------

  computeCountsForList(i,updateIdx,numUpdated,parentList,numParents,population,count);

  // for each element of the nodes to be updated update the gain

  for (l=0; l<numUpdated; l++)
    {      
      // compute the N's
      
      for (j=0; j<numParentConfigurations2; j++)
	{
	  tNwi[j]=0;
	  tNPwi[j]=0;
	  
	  for (k=0; k<2; k++)
	    {
	      Nwi[j][k] = count[l][(j<<1)+k];
	      NPwi[j][k]=1;
	      
	      tNwi[j]  += Nwi[j][k];
	      tNPwi[j] += NPwi[j][k];
	    }
	};

      for (j=0; j<numParentConfigurations; j++)
	{
	  tNoi[j]=0;
	  tNPoi[j]=0;
	  
	  for (k=0; k<2; k++)
	    {
	      Noi[j][k] = Nwi[j<<1][k]+Nwi[(j<<1)+1][k];
	      NPoi[j][k]=1;
	      
	      tNoi[j]  += Noi[j][k];
	      tNPoi[j] += NPoi[j][k];
	    }
	};
      
      // compute the resulting gain for the addition of an edge from updateIdx[l] to i

      result = 0;
      
      for (j=0; j<numParentConfigurations; j++)
	{
	  result += getPrecomputedCummulativeLog(tNPoi[j]+1,tNPoi[j]+tNoi[j]);
	  
	  for (k=0; k<2; k++)
	    result -= getPrecomputedCummulativeLog(NPoi[j][k]+1,NPoi[j][k]+Noi[j][k]);
	};
      
      for (j=0; j<numParentConfigurations2; j++)
	{
	  result -= getPrecomputedCummulativeLog(tNPwi[j]+1,tNPwi[j]+tNwi[j]);
	  
	  for (k=0; k<2; k++)
	    result += getPrecomputedCummulativeLog(NPwi[j][k]+1,NPwi[j][k]+Nwi[j][k]);
	};
      
      // update the gain

      gain[updateIdx[l]][i]=result;
    };

  // free the memory

  for (l=0; l<numUpdated; l++)
    Free(count[l]);

  if (numUpdated>0)
    Free(count);

  for (j=0; j<numParentConfigurations; j++)
    {
      Free(Noi[j]);
      Free(NPoi[j]);
    };
  
  Free(Noi);
  Free(NPoi);
  Free(tNoi);
  Free(tNPoi);

  for (j=0; j<numParentConfigurations2; j++)
    {
      Free(Nwi[j]);
      Free(NPwi[j]);
    };
  
  Free(Nwi);
  Free(NPwi);  
  Free(tNwi);
  Free(tNPwi);
  
  // get back

  return 0;
}

// ================================================================================
//
// name:          doneMetric
//
// function:      done method for the metric (do what is needed when the metric is
//                not to be used anymore)
//
// parameters:    (none)
//
// returns:       (int) 0
//
// ================================================================================

int doneMetric()
{
  // free the precomputed cummulative logarithms

  int freePrecomputedCummulativeLogarithms();

  // get back

  return 0;
};