gp.c

Genetic Programing of music

/*  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       ([e-mail])
 *  Dr. Bill Punch        ([e-mail])
 *
 *  Computer Science Department
 *  A-714 Wells Hall
 *  Michigan State University
 *  East Lansing, Michigan  48824
 *  USA
 *  
 */

#include <lilgp.h>

popstats *run_stats;
saved_ind *saved_head, *saved_tail;

#if !defined(POSIX_MT) && !defined(SOLARIS_MT)

   globaldata global_g;

#else

   #include <synch.h>

   static int                  numthreads = 0;

   struct thread_param_t {
      population *pop;
      int        startidx;
      int        endidx;
      globaldata g;
   };

   #ifdef POSIX_MT
   #include <pthread.h>
   static pthread_key_t        g_key;
   static pthread_attr_t       pthread_attr;
   #endif

   #ifdef SOLARIS_MT
   #include <thread.h>
   static thread_key_t         g_key;
   #endif

#endif /* !defined(POSIX_MT) && !defined(SOLARIS_MT) */

/* run_gp()
 *
 * the whole enchilada.  runs, from generation startgen, using population
 * mpop.  accumulates time spent evaluating and breeding in t_eval and t_breed.
 */

void run_gp ( multipop *mpop, int startgen,
             event *t_eval, event *t_breed, int startfromcheckpoint )
{

     char *param;
     int gen;
     int maxgen;
     int exch_gen;
     int i, j;
     int checkinterval;
     char *checkfileformat;
     char *checkfilename = NULL;
     event start, end, diff;
     int term = 0;
     int stt_interval;
     int bestn;

     if ( !startfromcheckpoint )
     {
	  
	  /* get the number of top individuals to track. */
	  bestn = atoi ( get_parameter ( "output.bestn" ) );
	  if ( bestn < 1 )
	  {
	       error ( E_WARNING, "\"output.bestn\" must be at least 1.  defaulting to 1." );
	       bestn = 1;
	  }
	  
	  /* allocate statistics for overall run. */
	  run_stats = (popstats *)MALLOC ( (mpop->size+1)*sizeof ( popstats ) );
	  for ( i = 0; i < mpop->size+1; ++i )
	  {
	       run_stats[i].bestn = bestn;
	       run_stats[i].size = -1;
	  }
	  
	  /* initialize the linked list of saved individuals. */
	  saved_head = (saved_ind *)MALLOC ( sizeof ( saved_ind ) );
	  saved_head->ind = NULL;
	  saved_head->refcount = 0;
	  saved_head->next = NULL;
	  saved_tail = saved_head;
     }

     /* get the maximum number of generations. */
     param = get_parameter ( "max_generations" );
     if ( param == NULL )
          error ( E_FATAL_ERROR,
                 "no value specified for \"max_generations\"." );
     maxgen = atoi ( param );
     if ( maxgen <= 0 )
          error ( E_FATAL_ERROR,
                 "\"max_generations\" must be greater than zero." );

     /* get the interval for subpopulation exchanges, if there is more than
	one subpopulation. */
     if ( mpop->size > 1 )
     {
          param = get_parameter ( "multiple.exch_gen" );
          if ( param == NULL )
               error ( E_FATAL_ERROR,
                      "no value specified for \"multiple.exch_gen\"." );
          exch_gen = atoi ( param );
          if ( exch_gen <= 0 )
               error ( E_FATAL_ERROR,
                      "\"multiple.exch_gen\" must be greater than zero." );
     }

     /* get the interval for doing checkpointing. */
     param = get_parameter ( "checkpoint.interval" );
     if ( param == NULL )
	  /* checkpointing disabled. */
          checkinterval = -1;
     else
          checkinterval = atoi ( param );

     /* get the format string for the checkpoint filenames. */
     checkfileformat = get_parameter ( "checkpoint.filename" );
     checkfilename = (char *)MALLOC ( strlen ( checkfileformat ) + 50 );

     /* get the interval for writing information to the .stt file. */
     stt_interval = atoi ( get_parameter ( "output.stt_interval" ) );
     if ( stt_interval < 1 )
          error ( E_FATAL_ERROR,
                 "\"output.stt_interval\" must be greater than zero." );
     
     oputs ( OUT_SYS, 10, "\n\nstarting evolution.\n" );

     /* print out how often we'll be doing checkpointing. */
     if ( checkinterval > 0 )
          oprintf ( OUT_SYS, 20,
                   "checkpointing will be done every %d generations and "\
                   "after the last generation.\n", checkinterval );
     else if ( checkinterval == 0 )
          oprintf ( OUT_SYS, 20,
                   "checkpointing will be done only after the last "\
                   "generation.\n" );
     else
          oprintf ( OUT_SYS, 20,
                   "no checkpointing will be done.\n" );

     /* the big loop. */
     for ( gen = startgen; gen <= maxgen && !term; ++gen )
     {
          oprintf ( OUT_SYS, 20,
                   "=== generation %d.\n", gen );

	  /* unless this is the first generation after loading a checkpoint
	     file... */
          if ( ! ( startfromcheckpoint && gen == startgen ) )
          {

	       /* evaluate the population. */
               event_mark ( &start );
               for ( i = 0; i < mpop->size; ++i )
                    evaluate_pop ( mpop->pop[i] );
               event_mark ( &end );
               event_diff ( &diff, &start, &end );

#ifdef TIMING_AVAILABLE
               oprintf ( OUT_SYS, 40, "    evaluation complete.  (%s)\n",
                        event_string ( &diff ) );
#else
               oprintf ( OUT_SYS, 40, "    evaluation complete.\n" );
#endif

               event_accum ( t_eval, &diff );

	       /* calculate and print statistics.  returns 1 if user termination
		  criterion was met, 0 otherwise. */
               term = generation_information ( gen, mpop, stt_interval,
					      run_stats[0].bestn );
               if ( term )
                    oprintf ( OUT_SYS, 30, "user termination criterion met.\n" );
               
               flush_output_streams();
          
          }

          /** write a checkpoint file if checkinterval is non-negative and:
            we've reached the last generation, or
            the user termination criterion has been met, or
            we've reached the specified checkpoint interval. **/
          if ( checkinterval >= 0 &&
              (gen == maxgen || term ||
              (checkinterval>0 && gen>startgen && (gen%checkinterval)==0)) )
          {
               sprintf ( checkfilename, checkfileformat, gen );
               write_checkpoint ( gen, mpop, checkfilename );
          }

          /** if this is not the last generation and the user criterion hasn't
            been met, then do breeding. **/
          if ( gen != maxgen && !term )
          {

               /** exchange subpops if it's time. **/
               if ( mpop->size>1 && gen && (gen%exch_gen)==0 )
               {
                    exchange_subpopulations ( mpop );
                    oprintf ( OUT_SYS, 10,
                             "    subpopulation exchange complete.\n" );
               }

	       /* breed the new population. */
               event_mark ( &start );
               for ( i = 0; i < mpop->size; ++i )
                    mpop->pop[i] = change_population ( mpop->pop[i], mpop->bpt[i] );
               event_mark ( &end );
               event_diff ( &diff, &start, &end );

	       /* call the application end-of-breeding callback. */
               app_end_of_breeding ( gen, mpop );
               
#ifdef TIMING_AVAILABLE
               oprintf ( OUT_SYS, 30, "    breeding complete.    (%s)\n",
                        event_string ( &diff ) );
#else
               oprintf ( OUT_SYS, 30, "    breeding complete.\n" );
#endif

               event_accum ( t_breed, &diff );
               
          }

	  /* free unused ERCs. */
          ephem_const_gc();

          flush_output_streams();
          
     }

     /** free up a lot of stuff before returning. */
     
     if ( checkfilename )
          FREE ( checkfilename );

     ephem_const_gc();

     for ( i = 0; i < mpop->size+1; ++i )
     {
          for ( j = 0; j < run_stats[i].bestn; ++j )
               --run_stats[i].best[j]->refcount;
          FREE ( run_stats[i].best );
     }
     FREE ( run_stats );

     saved_individual_gc();
     FREE ( saved_head );
}

/* generation_information()
 *
 * calculates and prints population statistics.
 */

int generation_information ( int gen, multipop *mpop, int stt_interval,
                            int bestn )
{
     int i, j;
     int newbest;
     static int fd = -1;
     popstats *gen_stats;
     int ret = 0;
     FILE *bout, *hout;

     /* number of decimal digits to use when printing fitness values. */
     if ( fd == -1 )
          fd = atoi ( get_parameter ( "output.digits" ) );

     /* allocate stats records for the current generation. */
     gen_stats = (popstats *)MALLOC ( (mpop->size+1)*sizeof ( popstats ) );
     for ( i = 0; i < mpop->size+1; ++i )
     {
          gen_stats[i].bestn = bestn;
          gen_stats[i].size = -1;
     }

     oprintf ( OUT_GEN, 90, "=== GENERATION %d ===\n", gen );
     oprintf ( OUT_PRG, 90, "=== GENERATION %d ===\n", gen );

     /* for each subpopulation... */
     for ( i = 0; i < mpop->size; ++i )
     {
	  /* calculate stats for subpopulation. */
          calculate_pop_stats ( gen_stats+i+1, mpop->pop[i], gen, i );
	  /* accumulate that into stats for whole popluation... */
          accumulate_pop_stats ( gen_stats, gen_stats+i+1 );
	  /* ...and stats for this subpopulation over the whole run. */
          accumulate_pop_stats ( run_stats+i+1, gen_stats+i+1 );

	  /* if only one subpop, don't print out the subpop stuff. */
          if ( mpop->size == 1 )
               continue;

	  /** print much stuff to .gen, .prg, and .stt files. */
	  
          if ( test_detail_level ( 90 ) )
          {
               oprintf ( OUT_GEN, 90, "    subpopulation %d:\n", i+1 );
               oprintf ( OUT_GEN, 90, "        generation:\n" );
               oprintf ( OUT_GEN, 90, "            mean:   nodes: %.3lf (%d-%d); depth: %.3lf (%d-%d)\n",
                        (double)gen_stats[i+1].totalnodes/gen_stats[i+1].size,
                        gen_stats[i+1].minnodes, gen_stats[i+1].maxnodes,
                        (double)gen_stats[i+1].totaldepth/gen_stats[i+1].size,
                        gen_stats[i+1].mindepth, gen_stats[i+1].maxdepth );
               oprintf ( OUT_GEN, 90, "            best:   nodes: %d; depth: %d\n",
                        gen_stats[i+1].bestnodes, gen_stats[i+1].bestdepth );
               oprintf ( OUT_GEN, 90, "            worst:  nodes: %d; depth: %d\n",
                        gen_stats[i+1].worstnodes, gen_stats[i+1].worstdepth );
               oprintf ( OUT_GEN, 90, "        run:   (%d trees)\n",
                        run_stats[i+1].size );
               oprintf ( OUT_GEN, 90, "            mean:   nodes: %.3lf (%d-%d); depth: %.3lf (%d-%d)\n",
                        (double)run_stats[i+1].totalnodes/run_stats[i+1].size,
                        run_stats[i+1].minnodes, run_stats[i+1].maxnodes,
                        (double)run_stats[i+1].totaldepth/run_stats[i+1].size,
                        run_stats[i+1].mindepth, run_stats[i+1].maxdepth );
               oprintf ( OUT_GEN, 90, "            best:   nodes: %d; depth: %d\n",
                        run_stats[i+1].bestnodes, run_stats[i+1].bestdepth );
               oprintf ( OUT_GEN, 90, "            worst:  nodes: %d; depth: %d\n",
                        run_stats[i+1].worstnodes, run_stats[i+1].worstdepth );
          }

          if ( test_detail_level ( 90 ) )
          {
               oprintf ( OUT_PRG, 90, "    subpopulation %d:\n", i+1 );
               oprintf ( OUT_PRG, 90, "        generation stats:\n" );
               oprintf ( OUT_PRG, 90, "            mean:   hits: %.3lf (%d-%d); standardized fitness: %.*lf\n",
                        (double)gen_stats[i+1].totalhits/gen_stats[i+1].size,
                        gen_stats[i+1].minhits, gen_stats[i+1].maxhits,
                        fd, (double)gen_stats[i+1].totalfit/gen_stats[i+1].size );
               oprintf ( OUT_PRG, 90, "            best:   hits: %d; standardized fitness: %.*lf\n",
                        gen_stats[i+1].besthits, fd,
                        (double)gen_stats[i+1].bestfit );
               oprintf ( OUT_PRG, 90, "            worst:  hits: %d; standardized fitness: %.*lf\n",
                        gen_stats[i+1].worsthits, fd,
                        (double)gen_stats[i+1].worstfit );
               oprintf ( OUT_PRG, 90, "        run stats:     (%d trees)\n",
                        run_stats[i+1].size );
               oprintf ( OUT_PRG, 90, "            mean:   hits: %.3lf (%d-%d); standardized fitness: %.*lf\n",
                        (double)run_stats[i+1].totalhits/run_stats[i+1].size,
                        run_stats[i+1].minhits, run_stats[i+1].maxhits,
                        fd, (double)run_stats[i+1].totalfit/run_stats[i+1].size );
               oprintf ( OUT_PRG, 90, "            best:   hits: %d; standardized fitness: %.*lf; generation: %d\n",
                        run_stats[i+1].besthits, fd, (double)run_stats[i+1].bestfit,
                        run_stats[i+1].bestgen );
               oprintf ( OUT_PRG, 90, "            worst:  hits: %d; standardized fitness: %.*lf; generation: %d\n",
                        run_stats[i+1].worsthits, fd,
                        (double)run_stats[i+1].worstfit, run_stats[i+1].worstgen );
          }

          if ( gen%stt_interval == 0 )
          {
               oprintf ( OUT_STT, 50, "%d %d ", gen, i+1 );
               oprintf ( OUT_STT, 50, "%.*lf %.*lf %.*lf ",
                        fd, gen_stats[i+1].totalfit/gen_stats[i+1].size,
                        fd, gen_stats[i+1].bestfit,
                        fd, gen_stats[i+1].worstfit );
               oprintf ( OUT_STT, 50, "%.3lf %.3lf %d %d %d %d ",
                        (double)gen_stats[i+1].totalnodes/gen_stats[i+1].size,
                        (double)gen_stats[i+1].totaldepth/gen_stats[i+1].size,
                        gen_stats[i+1].bestnodes, gen_stats[i+1].bestdepth,
                        gen_stats[i+1].worstnodes, gen_stats[i+1].worstdepth );
               oprintf ( OUT_STT, 50, "%.*lf %.*lf %.*lf ",
                        fd, run_stats[i+1].totalfit/run_stats[i+1].size,
                        fd, run_stats[i+1].bestfit,
                        fd, run_stats[i+1].worstfit );
               oprintf ( OUT_STT, 50, "%.3lf %.3lf %d %d %d %d ",
                        (double)run_stats[i+1].totalnodes/run_stats[i+1].size,
                        (double)run_stats[i+1].totaldepth/run_stats[i+1].size,
                        run_stats[i+1].bestnodes, run_stats[i+1].bestdepth,
                        run_stats[i+1].worstnodes, run_stats[i+1].worstdepth );
               oprintf ( OUT_STT, 50, "\n" );
          }
            
     }

     /* merge stats for current generation into overall run stats. */
     newbest = accumulate_pop_stats ( run_stats, gen_stats );

     /** more printing. **/
     
     if ( test_detail_level ( 90 ) )
     {
          oprintf ( OUT_GEN, 90, "    total population:\n" );
          oprintf ( OUT_GEN, 90, "        generation:\n" );
          oprintf ( OUT_GEN, 90, "            mean:   nodes: %.3lf (%d-%d); depth: %.3lf (%d-%d)\n",
                   (double)gen_stats[0].totalnodes/gen_stats[0].size,
                   gen_stats[0].minnodes, gen_stats[0].maxnodes,
                   (double)gen_stats[0].totaldepth/gen_stats[0].size,
                   gen_stats[0].mindepth, gen_stats[0].maxdepth );
          oprintf ( OUT_GEN, 90, "            best:   nodes: %d; depth: %d\n",
                   gen_stats[0].bestnodes, gen_stats[0].bestdepth );
          oprintf ( OUT_GEN, 90, "            worst:  nodes: %d; depth: %d\n",
                   gen_stats[0].worstnodes, gen_stats[0].worstdepth );
          oprintf ( OUT_GEN, 90, "        run:    (%d trees)\n",
                   run_stats[0].size );
          oprintf ( OUT_GEN, 90, "            mean:   nodes: %.3lf (%d-%d); depth: %.3lf (%d-%d)\n",
                   (double)run_stats[0].totalnodes/run_stats[0].size,
                   run_stats[0].minnodes, run_stats[0].maxnodes,
                   (double)run_stats[0].totaldepth/run_stats[0].size,
                   run_stats[0].mindepth, run_stats[0].maxdepth );
          oprintf ( OUT_GEN, 90, "            best:   nodes: %d; depth: %d\n",