COSC-4P82-Final-Project/lib/lilgp/kernel_mod/populate.c

/*  lil-gp Genetic Programming System, version 1.0, 11 July 1995
 *  Copyright (C) 1995  Michigan State University
 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of version 2 of the GNU General Public License as
 *  published by the Free Software Foundation.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *  
 *  Douglas Zongker       (zongker@isl.cps.msu.edu)
 *  Dr. Bill Punch        (punch@isl.cps.msu.edu)
 *
 *  Computer Science Department
 *  A-714 Wells Hall
 *  Michigan State University
 *  East Lansing, Michigan  48824
 *  USA
 *  
 */
#include <lilgp.h>



/* Read in an individual from a file, skipping any text in between */
void mod_read_tree_recurse ( int space, ephem_const **eind, FILE *fil, int tree,
			     char *string, int skip )
{
  function *f;
  int i, j;
  ephem_const *ep;

  if( skip )
    {
      i = 0;
      /*Read up until we get the first parenthesies */
      while( i != '(' )
	{
	  if( feof(fil) )
	    {
	      fseek( fil, 0L, SEEK_SET );
	    }
	  i = fgetc(fil);
	}
      if( i != '(' )
	{
	  error( E_FATAL_ERROR, "Ran out of file space while reading in saved tree");
	}
    }
  /* read up until a nonwhitespace character in file.   the nonwhitespace
     character is saved in string[0]. */
  while ( isspace(string[0]=fgetc(fil)) );
  /* get the next character. */
  i = fgetc ( fil );
  if ( isspace(i) )
    /* if the next character is whitespace, then string[0] is a
       one-character function name.  null-terminate the string. */
    string[1] = 0;
  else
    {
      /** if the next character is not whitespace, then string[0]
	is either an open parenthesis or the first character of a
	multi-character function name. **/
	  
      /* push the next character back. */
      ungetc ( i, fil );
      /* read the function name.  skip over an open parenthesis, if there
	 is one. */
      fscanf ( fil, "%s ", string+(string[0]!='(') );
    }
#ifdef DEBUG_READTREE
  fprintf ( stderr, "function name is [%s]\n", string );
#endif

  /* look up the function name in this tree's function set.  if the
     function is an ERC terminal (the name is of the form "name:ERCindex"),
     then place the ERC address in ep. */
  f = get_function_by_name ( tree, string, &ep, eind );
  /* add an lnode to the tree. */
  gensp_next(space)->f = f;
     
  switch ( f->type )
    {
    case TERM_NORM:
    case TERM_ARG:
    case EVAL_TERM:
      break;
    case TERM_ERC:
      /* record the ERC address as the next lnode in the array. */
      gensp_next(space)->d = ep;
      break;
    case FUNC_DATA:
    case EVAL_DATA:
      /** recursively read child functions, no skip nodes needed. **/
      for ( i = 0; i < f->arity; ++i )
	mod_read_tree_recurse ( space, eind, fil, tree, string, 0 );
      break;
    case FUNC_EXPR:
    case EVAL_EXPR:
      /** recursively read child functions, recording skip values. **/
      for ( i = 0; i < f->arity; ++i )
	{
	  /* save an lnode for the skip value. */
	  j = gensp_next_int ( space );
	  /* read the child tree. */
	  mod_read_tree_recurse ( space, eind, fil, tree, string, 0);
	  /* figure out how big the child tree was, and save that
	     number in the skip node. */
	  gensp[space].data[j].s = gensp[space].used-j-1;
	}
      break;
    }
}


/* generate_random_population()
 *
 * fills a population with randomly generated members.
 */

void generate_random_population ( population *p, int *mindepth,
				  int *maxdepth, int *method, FILE **dataum )
{
  int i, j, k, m;
  int attempts;
  int totalattempts = 0;
  int depth;
  int attempts_generation;
  tree *temp;
  int totalnodes = 0;
  int flag;
  char buf[2048];
  int ignore_limits;

  /* how many consecutive rejected trees we will tolerate before
     giving up. */
  attempts_generation = atoi ( get_parameter ( "init.random_attempts" ) );
  if ( attempts_generation <= 0 )
    error ( E_FATAL_ERROR,
	    "\"init.random_attempts\" must be positive." );

  ignore_limits = (get_parameter("init.ignore_limits")!=NULL);

  temp = (tree *)MALLOC ( tree_count * sizeof ( tree ) );
     
  k = 0;
  attempts = attempts_generation;
  while ( k < p->size )
    {
      /* total nodes in the individual being generated. */
      totalnodes = 0;
          
      for ( j = 0; j < tree_count; ++j )
	{
          
	  if ( attempts <= 0 )
	    error ( E_FATAL_ERROR,
		    "The last %d trees generated have been bad.  Giving up.",
		    attempts_generation );
               
	  --attempts;
	  ++totalattempts;

	  /* pick a depth on the depth ramp. */
	  depth = mindepth[j] + random_int ( &globrand, maxdepth[j] - mindepth[j] + 1 );

	  /* clear a generation space. */
	  gensp_reset ( 0 );

	  /** generate the tree. **/
	  switch ( method[j] )
	    {
	    case GENERATE_FULL:
	      generate_random_full_tree ( 0, depth, fset+tree_map[j].fset,
					  tree_map[j].return_type);
	      break;
	    case GENERATE_GROW:
	      generate_random_grow_tree ( 0, depth, fset+tree_map[j].fset,
					  tree_map[j].return_type);
	      break;
	    case GENERATE_HALF_AND_HALF:
	      if ( random_double(&globrand) < 0.5  )
		generate_random_full_tree ( 0, depth, fset+tree_map[j].fset,
					    tree_map[j].return_type);
	      else
		generate_random_grow_tree ( 0, depth, fset+tree_map[j].fset,
					    tree_map[j].return_type);
	      break;

	    case LOAD_FILE:
	      gensp_reset(0);
	      mod_read_tree_recurse( 0, NULL, dataum[j], j, buf, 1);
	      /* need to do something here about limit checking */
	      break;
	    }

	      /** throw away the tree if it's too big. **/
	      
	      /*printf("Attempted Tree: ");
		print_tree(gensp[0].data,stdout);*/
	      
	      /* first check the node limits. */
	      flag = 0;
	      m = tree_nodes ( gensp[0].data );


	  if (method[j]!=LOAD_FILE)
	    {
	      if ( tree_map[j].nodelimit > -1 && m > tree_map[j].nodelimit )
		{
		  --j;
		  continue;
		}
	      
	      /* now change the depth limits. */
	      if ( tree_map[j].depthlimit > -1 && tree_depth ( gensp[0].data ) > tree_map[j].depthlimit )
		{
		  --j;
		  continue;
		}
	      
	      /* count total nodes in the individual being created. */
	    }
	  totalnodes += m;
	  gensp_dup_tree ( 0, temp+j );
	}

      if (!ignore_limits)
	{
	  
	  /* is the individual over the total node limit (if one is set)? */
	  if ( ind_nodelimit > -1 && totalnodes > ind_nodelimit )
	    {
#ifdef DEBUG
	      printf ( "overall node limit violated.\n" );
#endif
	      /* yes, so delete it and try again. */
	      for ( j = 0; j < tree_count; ++j )
		free_tree ( temp+j );
	      continue;
	    }
	  
	  /* throw away the individual if it's a duplicate. */
	  for ( i = 0; i < k; ++i )
	    {
	      flag = 0;
	      for ( j = 0; j < tree_count && !flag; ++j )
		{
		  if ( temp[j].size == p->ind[i].tr[j].size )
		    {
		      if ( memcmp ( temp[j].data, p->ind[i].tr[j].data,
				    temp[j].size * sizeof ( lnode ) ) )
			{
			  flag = 1;
			}
		    }
		  else
		    flag = 1;
		}
	      if ( !flag )
		break;
	    }
	  if ( i < k )
	    {
#ifdef DEBUG
	      printf ( "duplicate individual: (same as %d)\n", i );
	      for ( j = 0; j < tree_count; ++j )
		{
		  printf ( "   tree %d: ", j );
		  print_tree ( temp[j].data, stdout );
		}
#endif
	      /* individual is a duplicate, throw it away. */
	      --attempts;
	      for ( j = 0; j < tree_count; ++j )
		free_tree ( temp+j );
	      continue;
	    }
	}

      /** we now have a good individual to put in the population. */

      /* copy the tree array. */
      memcpy ( p->ind[k].tr, temp, tree_count * sizeof ( tree ) );

      /* reference ERCs. */
      for ( j = 0; j < tree_count; ++j )
	reference_ephem_constants ( p->ind[k].tr[j].data, 1 );
          
#ifdef DUMP_POPULATION
      printf ( "individual %5d:\n", k );
      print_individual ( p->ind+k, stdout );
#endif
      /* mark individual as unevaluated. */
      p->ind[k].evald = EVAL_CACHE_INVALID;
      p->ind[k].flags = FLAG_NONE;

      attempts = attempts_generation;
      ++k;
          
    }

  FREE ( temp );
     
  oprintf ( OUT_SYS, 10,
	    "    %d trees were generated to fill the population of %d (%d trees).\n",
	    totalattempts, p->size, p->size * tree_count );

}

/* allocate_population()
 *
 * allocates a population structure with the given size.
 */

population *allocate_population ( int size )
{
  int i;
  population *p = (population *)MALLOC ( sizeof ( population ) );

  p->size = size;
  p->next = 0;
  /* allocate the array of individuals. */
  p->ind = (individual *)MALLOC ( size * sizeof ( individual ) );

  for ( i = 0; i < size; ++i )
    {
      /* each individual has a block of tree structures, allocate
	 those here. */
      p->ind[i].tr = (tree *)MALLOC ( tree_count * sizeof ( tree ) );
      p->ind[i].evald = EVAL_CACHE_INVALID;
      p->ind[i].flags = FLAG_NONE;
    }

  return p;
}

/* free_multi_population()
 *
 * frees the populations in a multipop structure.
 */

void free_multi_population ( multipop *mp )
{
  int i;
  for ( i = 0; i < mp->size; ++i )
    free_population ( mp->pop[i] );
  FREE ( mp->pop );
  FREE ( mp );
}

/* free_population()
 *
 * frees a population and all the individuals in it.
 */

void free_population ( population *p )
{
  int i, j;
  for ( i = 0; i < p->size; ++i )
    {
      for ( j = 0; j < tree_count; ++j )
	{
	  /* dereference ERCs. */
	  reference_ephem_constants ( p->ind[i].tr[j].data, -1 );
	  free_tree ( &(p->ind[i].tr[j]) );
	}
      FREE ( p->ind[i].tr );
    }
  FREE ( p->ind );
  FREE ( p );
}

/* initial_multi_population()
 *
 * randomly fills a multipop strcture with individuals.
 */

multipop *initial_multi_population ( void )
{
  char *param;
  char temp_name[256];
  char **tree_replace;
  multipop *mpop;
  int i;
  int *mindepth, *maxdepth, *method;
  char *cp;
  char pnamebuf[100];
  FILE **tree_data;
  FILE *fp;

  oputs ( OUT_SYS, 10, "creating initial population(s):\n" );

  mpop = (multipop *)MALLOC ( sizeof ( multipop ) );

  /* how many subpops are we supposed to have? */
  param = get_parameter ( "multiple.subpops" );
  mpop->size = atoi ( param );
  if ( mpop->size <= 0 )
    error ( E_FATAL_ERROR,
	    "\"%s\" is not a valid value for \"multiple.subpops\".",
	    param );

  /* allocate that many population pointers. */
  mpop->pop = (population **)MALLOC ( sizeof ( population* ) * mpop->size );

  /* read the depth ramp and generation method(s), which can be
     different for each tree. */
  tree_replace = (char **)MALLOC(sizeof(char *)*tree_count);
  tree_data = (FILE **)MALLOC( sizeof(FILE *)*tree_count);

  for( i = 0; i < tree_count; i++ )
    {
      sprintf( temp_name, "tree-replace[%d]", i );
      tree_replace[i] = get_parameter( temp_name );
    }

  for( i = 0; i < tree_count; i++ )
    {
      if( tree_replace[i] != NULL )
	{
	  tree_data[i] = fopen( tree_replace[i], "r" );
	  if( fp == NULL )
	    {
	      /* Error Handler */
	      error( E_FATAL_ERROR, "Unable to open file %s\n", tree_replace[i] );
	    }
	     
	} else {
	  tree_data[i] = NULL;
	}
    }

  mindepth = (int *)MALLOC ( tree_count * sizeof ( int ) );
  maxdepth = (int *)MALLOC ( tree_count * sizeof ( int ) );
  method = (int *)MALLOC ( tree_count * sizeof ( int ) );

  for ( i = 0; i < tree_count; ++i )
    {
      mindepth[i] = -1;
      maxdepth[i] = -1;

      /** read the depth ramp. **/
      sprintf ( pnamebuf, "init.tree[%d].depth", i );
      param = get_parameter ( pnamebuf );
      if ( !param )
	param = get_parameter ( "init.depth" );
      if ( param == NULL )
	error ( E_FATAL_ERROR, "\"init.tree[%d].depth\" must be specified.", i );

      /** parse the depth ramp ("min-max" or just "val"). **/
      mindepth[i] = strtol ( param, &cp, 10 );
      if ( *cp )
	{
	  if ( *cp == '-' )
	    {
	      maxdepth[i] = strtol ( cp+1, &cp, 10 );
	    }
	  if ( *cp )
	    {
	      error ( E_FATAL_ERROR, "\"init.tree[%d].depth\" is malformed.",
		      i );
	    }
	}
      if ( maxdepth[i] == -1 )
	maxdepth[i] = mindepth[i];

      if ( mindepth[i] > maxdepth[i] )
	error ( E_FATAL_ERROR, "\"init.tree[%d].depth\" is malformed.", i );

      /** read the method. **/
      sprintf ( pnamebuf, "init.tree[%d].method", i );
      param = get_parameter ( pnamebuf );
      if ( !param )
	param = get_parameter ( "init.method" );

      if ( param == NULL )
	error ( E_FATAL_ERROR, "\"init.tree[%d].method\" must be set.",
		i );

      if ( strcmp ( param, "half_and_half" ) == 0 )
	method[i] = GENERATE_HALF_AND_HALF;
      else if ( strcmp ( param, "full" ) == 0 )
	method[i] = GENERATE_FULL;
      else if ( strcmp ( param, "grow" ) == 0 )
	method[i] = GENERATE_GROW;
      else if ( strcmp ( param, "load" ) == 0 )
	method[i]= LOAD_FILE;
      else
	error ( E_FATAL_ERROR, "\"init.tree[%d].method\": \"%s\" is not a known generation method.",
		i, param );
    }

  /* generate each population. */
  for ( i = 0; i < mpop->size; ++i )
    mpop->pop[i] = initial_population ( mindepth, maxdepth, method, tree_data );

  for( i = 0; i < tree_count; i++ )
    {
      if( tree_data[i] != NULL )
	fclose(tree_data[i]);     
    }

  FREE ( mindepth );
  FREE ( maxdepth );
  FREE ( method );
  FREE ( tree_replace );
  FREE ( tree_data );

  oputs ( OUT_SYS, 10, "    initial population(s) complete.\n" );
          
  return mpop;
}

/* initial_population()
 *
 * creates a population structure and fills it with randomly
 * generated individuals.
 */

population *initial_population ( int *mindepth, int *maxdepth, int *method, FILE **dataum )
{
  population *pop;
  int pop_size;
  char *param;
     
  /* get the population size and allocate. */
     
  param = get_parameter ( "pop_size" );
  if ( param == NULL )
    error ( E_FATAL_ERROR,
	    "no value specified for \"pop_size\"." );
  pop_size = atoi ( param );
  pop = allocate_population ( pop_size );

  /* get the generation method and create the random population. */

  generate_random_population ( pop, mindepth, maxdepth, method, dataum );
     
  return pop;
}