/* 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 * * This parallel version based on PVM is an extension of version 1.1 * of Lil-gp. * * Johan Parent (johan@info.vub.ac.be) * * Faculty of Applied Sciences (Engineering Faculty) * Building K, Computer Science Department * Vrije Universiteit Brussel * Pleinlaan 2, 1050 Etterbeek * Belgium * */ #include #ifdef MEMORY_LOG FILE *mlog; #endif /* do we dup OUT_SYS to stdout? */ int quietmode = 0; /* tree generation spaces. */ genspace gensp[GENSPACE_COUNT]; /* internal copy of function set(s). */ function_set *fset; int fset_count; /* information about each tree--which function set it uses, its name, size limits, etc. */ treeinfo *tree_map; int tree_count; /* maximum number of nodes per individual. -1 if no limit is enforced. */ int ind_nodelimit; #ifdef _PARALLEL_H /* Parallel operation related information */ int operation_mode; int sync_mode; int spawn_mode; int low; int high; int *tids; int nhost; int *population_map; int working_nodes; int wait_for_everybody; int debug_spawns; int debug_all; event start, end, diff; event first_end, shortest_run; #endif int main ( int argc, char **argv ) { multipop *mpop; int startgen; event eval, breed; #ifndef _PARALLEL_H event start, end, diff; #endif int startfromcheckpoint; #ifdef _PARALLEL_H int my_tid; int narch; int i; int number_of_populations; int real_populations; int remaining_populations; int populations; int tmp; int dot_count; int gen; int info; int tid; int non_stop; int msgtg; int bytes; int bufid; int parent_id; int remote_low; int remote_high; int max_gen; int min_gen; int max_time; int last_report; Popstats_list *statistics_list = NULL; Popstats_list *full_statistics = NULL; event intermediate; char **args; char name[100]; char error_type[30]; char buffer[200]; struct pvmhostinfo *hostp; /* Installing signal handler */ signal (SIGINT, &user_stop); signal (SIGSEGV, &crash_stop); /* Do not debugging all the processes in the first place */ debug_all = 0; /* Set the number of nodes (nhost) to zero */ nhost = 0; /* We did not yet put any dots on screen */ dot_count = 0; /* The highest generation so far is '0' */ max_gen = 0; /* The oldest generation so far is '0' */ min_gen = 0; /* Generation of the last report we got */ last_report = -1; wait_for_everybody = 0; operation_mode = SEQUENTIAL; sync_mode = SYNC; #endif #ifdef MEMORY_LOG /* dump all memory allocations to a file. */ mlog = fopen ( "memory.log", "w" ); #endif /* mark the start time, and zero the accumulators for evaluation and breeding time. */ event_init(); event_mark ( &start ); event_zero ( &eval ); event_zero ( &breed ); event_zero ( &shortest_run ); if ( app_create_output_streams() ) error ( E_FATAL_ERROR, "app_create_output_streams() failure." ); initialize_output_streams(); /* print copyright message and such. */ initial_message(); /* some initialization. */ oprintf ( OUT_SYS, 30, "initialization:\n" ); initialize_parameters(); initialize_ephem_const(); initialize_genspace(); #ifndef _PARALLEL_H #endif /* process the command line. if starting from a checkpoint file, this function will load the population. */ startfromcheckpoint = process_commandline ( argc, argv, &startgen, &mpop ); /* After processing the command line the "operation mode" is known */ if (operation_mode != SEQUENTIAL) { /* Enroll in the PVM, has to be done before invoking get_parameter()*/ my_tid = pvm_mytid(); if (nhost == 0) /* What is the configuration of the PVM */ info = pvm_config( &nhost, &narch, &hostp ); } number_of_populations = atoi ( get_parameter ( "multiple.subpops" ) ); if (operation_mode == SEQUENTIAL) { low = 0; high = number_of_populations; if (high <= 0) high = 0; } /* open the files associated with each stream. */ if (operation_mode != SLAVE) open_output_streams(); /* make internal copies of function set(s), if it hasn't already been done. */ if ( !startfromcheckpoint ) if ( app_build_function_sets() ) error ( E_FATAL_ERROR, "app_build_function_sets() failure." ); if ((operation_mode == SLAVE) || (operation_mode == SEQUENTIAL)) { /* SLAVE and SEQUENTIAL are almost identical :) but in SLAVE mode the low and high are obtained from the command line. Were as in SEQUENTIAL mode they take default values. */ #ifdef _PARALLEL_H_XXXXXX /* some initialization. */ initialize_ephem_const(); initialize_genspace(); #endif /* read parameters limiting tree node count and/or depth. */ read_tree_limits(); /* if not starting from a checkpoint, seed the random number generator. */ if ( !startfromcheckpoint ) initialize_random(); if ( app_initialize ( startfromcheckpoint ) ) error ( E_FATAL_ERROR, "app_initialize() failure." ); /* if not starting from a checkpoint, create a random population. */ if ( !startfromcheckpoint ) mpop = initial_multi_population( low, high); /* build the breeding table and the subpop exchange table from the parameter database. */ initialize_topology ( mpop ); initialize_breeding ( mpop ); #ifdef _PARALLEL_H if (operation_mode == SLAVE) { /* Initialisations */ event_zero(get_tree_send_event()); event_zero(get_tree_receive_event()); event_zero(get_individual_send_event()); event_zero(get_individual_receive_event()); /* Wait for some information from the MASTER node */ parent_id = pvm_parent(); if (parent_id == PvmNoParent) error (E_FATAL_ERROR, "No parent found in main()" ); /* Build arrays needed to resolve the population to node mapping */ population_map = (int *) MALLOC ( nhost * sizeof(int) ); tids = (int *) MALLOC ( nhost * sizeof(int) ); /* Request the arrays */ pvm_send(parent_id, MAPPING_REQUEST_TAG); /* Unpack the array */ pvm_recv(parent_id, MAPPING_ANSWER_TAG); if (pvm_upkint(&sync_mode, 1, 1)) pvm_perror ("main() error unpacking \"sync\""); if (pvm_upkint(tids, nhost, 1)) pvm_perror ("main() error unpacking \"tids\""); if (pvm_upkint(population_map, nhost, 1)) pvm_perror ("main() error unpacking \"population_map\""); printf ("[ Program invoked in slave mode.\n"); printf ("[ This node will compute the populations from %d to %d\n", get_low(), get_high()-1); } #endif /* do the GP. */ run_gp ( mpop, startgen, &eval, &breed, startfromcheckpoint ); /* free app stuff. */ app_uninitialize(); #ifdef _PARALLEL_H if (operation_mode == SLAVE) { FREE(tids); FREE(population_map); free_exchange_lists(); /* Leave the group */ pvm_lvgroup( PARALLEL_GROUP ); /* Quit the PVM */ pvm_exit(); } #endif /* free lots of stuff. */ free_breeding ( mpop ); free_topology ( mpop ); } else { /* MASTER */ printf ("\n"); printf ("[\tWARNING -!- WARNING -!- WARNING \n"); printf ("[ ---------------------------------------------------------\n"); printf ("[ The kernel has been invoked in PARALLEL mode! \n"); printf ("[ The communication between the computing nodes will be %s.\n", ((sync_mode== SYNC) ? "SYNCHRONOUS" : "ASYNCHRONOUS")); printf ("[\n"); printf ("[ The parallel version is based on the original code (V1.1).\n"); printf ("[ Changed by Johan Parent (johan@info.vub.ac.be)\n"); printf ("\n"); /* Initialize the random number generator */ initialize_random(); /* First a little check: are their more nodes than populations? */ if (number_of_populations < nhost) nhost = number_of_populations; /* Some unavoidable allocations */ /* Allocate a multipop */ mpop = initial_minimal_multi_population(); /* Allocate some space for the task to population mapping */ population_map = (int *) MALLOC ( nhost * sizeof(int) ); tids = (int *) MALLOC ( nhost * sizeof(int) ); /* Allocate some space for the argument list used by PVM */ args = (char **) MALLOC ( 6 * sizeof (char *) ); /* Some space for each of the arguments */ for (i=0; i<5; i++) args[i] = (char *) MALLOC (20); /* Some default values and NULL termination */ strcpy ( args[0], "-s" ); strcpy ( args[3], "-h" ); sprintf( args[4], "%d", nhost); args[5] = NULL; /* How many populations will be simulated per machine */ populations = number_of_populations; /* This a estimation, it can be corrected later */ real_populations = populations / nhost; /* Populations that need to be forced together with other populations */ remaining_populations = populations % nhost; /* Start the different SLAVE tasks and in the meanwhile: 1) We also try to balance the load equally over the different slaves. It is extremely crude and simple ;> Suppose you have 14 populations and 3 hosts, the mapping would be: 5 5 4 2) Build map for the populations to task mapping. */ printf ("\n"); printf (" The distribution of subpopulation on the different\n"); printf (" computing nodes is reported underneath.\n"); printf ("-------------------------------\n"); printf ("\n"); for (i=0; (i< nhost) && populations; i++) { /* Lowest population number => parameter for the SLAVE */ sprintf (args[1], "%d", number_of_populations - populations); tmp = real_populations; if (remaining_populations) { tmp++; remaining_populations--; } populations -= tmp; /* Fill in the population_map (this is used together with the tids array for mapping populations to task ID's => see function population_mapping() */ population_map[i] = (number_of_populations - populations) - 1; /* Highest population number => parameter for the SLAVE */ sprintf (args[2], "%d", population_map[i]+1); printf (" node %d : population %s to %d\n", i, args[1], atoi(args[2])-1); /* Set spawn mode to the 'normal' mode */ spawn_mode = PvmTaskDefault; if (debug_spawns || debug_all) { spawn_mode = PvmTaskDebug; } info = pvm_spawn( argv[0], (char **)args, spawn_mode, "", 1, &tids[i] ); if (info != 1) { pvm_perror("Error in main() while spawning task"); error ( E_FATAL_ERROR, "Could not start task number %d", i ); } if (debug_spawns) { debug_spawns--; } #ifdef PDEBUG_MAIN printf("Spawn %d\n", info); #endif } #ifdef _PARALLEL_H event_mark( &intermediate ); #endif /* Number of host we really use */ nhost = i; working_nodes = nhost; /* Impossible generation */ gen = -1; printf ("-------------------------------\n\n"); printf (" Using %d nodes to simulate %d populations.\n", nhost, number_of_populations); /* Loop until termination */ non_stop = 1; while (non_stop) { bufid = pvm_recv(-1, -1); pvm_bufinfo( bufid, &bytes, &msgtg, &tid); switch ( msgtg ) { case ERROR_TAG: { if (pvm_upkstr(error_type)) pvm_perror ("main error unpacking \"error_type\" in switch"); if (pvm_upkstr(buffer)) pvm_perror ("main error unpacking \"buffer\" in switch"); if (pvm_upkint(&remote_low, 1, 1)) pvm_perror ("main error unpacking \"remote_low\" in switch (I)"); if (pvm_upkint(&remote_high, 1, 1)) pvm_perror ("main() error unpacking \"remote_high\" in switch (II)"); printf ("\n"); printf ("Error from node containing subpops %d to %d\n", remote_low, remote_high-1); printf ("%s %s\n", error_type, buffer); break; } case PARAMETER_NAME_TAG: { if (pvm_upkstr(name)) pvm_perror("main() error unpacking \"name\" in switch"); send_parameter (name, tid); break; } case TERM_ENDED_TAG: { #ifdef PDEBUG_MAIN printf ("Got a signal from a node it finished computing\n"); #endif /* Some display */ if (working_nodes == nhost) { event_mark ( &first_end ); event_diff ( &shortest_run, &start, &first_end ); printf ("\n"); if (pvm_upkint(&remote_low, 1, 1)) pvm_perror ("main error unpacking \"remote_low\" in switch (III)"); if (pvm_upkint(&remote_high, 1, 1)) pvm_perror ("main() error unpacking \"remote_high\" in switch (IV)"); printf ("\n"); #ifdef PDEBUG_MAIN printf ("Termination signaled by node containing subpops %d to %d\n", remote_low, remote_high-1); #endif printf (" Waiting for %d nodes to stop \n", nhost); printf ("------------------------------\n"); printf ("Count down: %d ", working_nodes-1); } else printf ("-> %d ", working_nodes-1); /*Not sure about this pvm_initsend(ENCODING); pvm_mcast(tids, nhost, TERM_REQUEST_TAG); */ /* Push this thing on screen */ fflush(stdout); /* Decrement the number of working nodes */ working_nodes--; if (working_nodes == 0) { non_stop = 0; printf("\n"); } break; } case TERM_CRITERION_TAG: { printf ("\n"); if (pvm_upkint(&remote_low, 1, 1)) pvm_perror ("main error unpacking \"remote_low\" in switch (III)"); if (pvm_upkint(&remote_high, 1, 1)) pvm_perror ("main() error unpacking \"remote_high\" in switch (IV)"); printf ("The user specified criterion was met on node with subpops %d to %d\n", remote_low, remote_high-1); if (wait_for_everybody) break; /* Oh oh, a solution was found! We ask nodes to stop working */ pvm_initsend(ENCODING); pvm_mcast(tids, nhost, TERM_REQUEST_TAG); break; } case MAPPING_REQUEST_TAG: { #ifdef PDEBUG_MAIN printf ("Sd MAPP to %d\n", tid); fflush(stdout); #endif /* Send some general information to the SLAVE node */ pvm_initsend(ENCODING); if (pvm_pkint(&sync_mode, 1, 1)) pvm_perror("main() error packing \"sync_mode\" in switch"); /* Pack the population to node map */ if (pvm_pkint(tids, nhost, 1)) pvm_perror("main() error packing \"tids\" in switch"); if (pvm_pkint(population_map, nhost, 1)) pvm_perror("main() error unpacking \"population_map\" in switch"); pvm_send(tid, MAPPING_ANSWER_TAG); break; } case STATS_TAG: { full_statistics = receive_generation_information ( mpop, &gen, &statistics_list ); dot_count++; /* Determine a possible new highest generation */ if (gen > max_gen) max_gen = gen; if (working_nodes != nhost) break; if (get_sync_mode() == ASYNC) { #if 0 /* Each time we receive some statistics we will put a dot on screen */ putchar('.'); if ((dot_count%DOTS_PER_LINE) == 0) printf(" [%8d reports ]\n", dot_count); #endif if ( full_statistics == NULL ) break; printf ("=== generation %4d. \t( ", gen); for (i=0; ieval[i].wall); printf (" // parallel) !! Intermediate report !!\n"); } else { if ( full_statistics != NULL ) { /* We moved to the next generation */ last_report = full_statistics->gen; event_mark ( &end ); event_diff ( &intermediate, &intermediate, &end ); printf ("\n"); printf ("=== generation %4d. \t(%s)\n" ,full_statistics->gen , event_string(&intermediate)); printf (" evaluation complete. \t( "); tmp = 0; max_time = 0; for (i=0; ieval[i].wall > max_time) max_time = full_statistics->eval[i].wall; tmp += full_statistics->eval[i].wall; printf ("%3lds ", full_statistics->eval[i].wall); } printf (" // parallel)\t [warp %f]\n", tmp / (float)max_time); printf (" breeding complete. \t( "); tmp = 0; max_time = 0; for (i=0; ieval[i].wall > max_time) max_time = full_statistics->eval[i].wall; tmp += full_statistics->breeding[i].wall; printf ("%3lds ", full_statistics->breeding[i].wall); } printf (" // parallel)\t [warp %f]\n", tmp / (float)max_time); statistics_list = remove_statistics( statistics_list, full_statistics, mpop ); /* The oldest generation increased */ min_gen++; /* New reference */ intermediate = end; } else { printf (" Generation %d : waiting for %d more subpopulations (%d)\r", min_gen, (mpop->size - find_popstats (&statistics_list, min_gen)->count), max_gen); fflush(stdout); } } break; } default: } } #ifdef _PARALLEL_H /* Free some space from each of the arguments */ for (i=0; i<5; i++) FREE(args[i]); FREE(args); FREE(tids); FREE(population_map); dealloc_popstats_list(statistics_list, mpop); free_gen_stats(mpop); if (get_operation_mode() == MASTER) { printf ("End of PARALLEL operation in %s mode. Total number of generations computed is %d\n", ((sync_mode== SYNC) ? "SYNCHRONOUS" : "ASYNCHRONOUS"), max_gen); printf ("The first node to finished working after %ld seconds.\n", shortest_run.wall); printf ("\n"); printf ("This software is provided without any warranty either expressed or implied.\n"); printf ("Parallel version by Johan Parent (contact johan@info.vub.ac.be).\n"); } #endif } /* Free stuff both of MASTER and SLAVE */ free_multi_population ( mpop ); free_ephem_const(); free_genspace(); free_function_sets(); free_parameters(); /* mark the finish time. */ event_mark ( &end ); event_diff ( &diff, &start, &end ); /* print memory/time statistics and close output files. */ output_system_stats ( &diff, &eval, &breed ); #ifdef PDEBUG_MAIN printf ("Closing output_streams... "); fflush(stdout); #endif close_output_streams(); #ifdef PDEBUG_MAIN printf ("Output_streams closed\n"); #endif #ifdef PDEBUG_MEM_PARALLEL memory_short_report(); // memory_report(); printf ("This report has been generated after a succesful run.\n"); #endif #ifdef MEMORY_LOG fclose ( mlog ); #endif /* all done. */ return 0; } void localSort (void *base, unsigned long len, unsigned long width, int (*compar) (const void *, const void *)) { int index1, index2; void *record1, *record2, *temp; temp = MALLOC (width); for (index1 = 0; index1 < len-1; index1++) { record1 = (void*) ((char*)base + width * index1); for (index2 = index1+1; index2 < len; index2++) { record2 = (void*) ((char*)base + width * index2); if (compar((const void*)record2, (const void*) record1) < 0) { /* swap two structures */ memcpy (temp, record1, width); memcpy (record1, record2, width); memcpy (record2, temp, width); } } } FREE (temp); } /* function_sets_init() * * this function is called from user code and passed the function sets * and tree maps and names. it makes internal copies and does some * validation. */ int function_sets_init ( function_set *user_fset, int user_fcount, user_treeinfo *user_tree_map, int user_tcount ) { int i, j, k, m, n, p; int x; int errors = 0; function *cur; /* Strongly Typed... */ int pos[NUMTYPES]; /* Current position to place a function/terminal in the cset by type */ /* allocate internal copies. */ fset = (function_set *)MALLOC ( user_fcount * sizeof ( function_set ) ); tree_map = (treeinfo *)MALLOC ( user_tcount * sizeof ( treeinfo ) ); fset_count = user_fcount; tree_count = user_tcount; oprintf ( OUT_SYS, 30, "building function set(s):\n" ); /* for each set of functions... */ for ( i = 0; i < fset_count; ++i ) { /* Initialize counts */ for (x=0;xcode = user_fset[i].cset[j].code; cur->ephem_gen = user_fset[i].cset[j].ephem_gen; cur->ephem_str = user_fset[i].cset[j].ephem_str; cur->arity = user_fset[i].cset[j].arity; cur->type = user_fset[i].cset[j].type; cur->evaltree = user_fset[i].cset[j].evaltree; /* copy the name string. */ n = strlen ( user_fset[i].cset[j].string ); cur->string = (char *)MALLOC ( n+1 ); for ( p = 0; p < n; ++p ) { if ( isspace(user_fset[i].cset[j].string[p]) || user_fset[i].cset[j].string[p] == ':' || user_fset[i].cset[j].string[p] == ')' || user_fset[i].cset[j].string[p] == '(' || user_fset[i].cset[j].string[p] == '[' || user_fset[i].cset[j].string[p] == ']' ) { error ( E_WARNING, "illegal character(s) in function name changed to '_'." ); cur->string[p] = '_'; } else cur->string[p] = user_fset[i].cset[j].string[p]; } cur->string[n] = 0; /* fill in the index field with this function's position in the set. */ cur->index = k; /* the ERC-related fields should be NULL. */ if ( cur->ephem_gen || cur->ephem_str ) { ++errors; error ( E_ERROR, "function has non-NULL ephem_gen and/or ephem_str field(s)." ); } /* do some type-specific checking. */ switch ( cur->type ) { case FUNC_DATA: case FUNC_EXPR: if ( cur->code == NULL ) { ++errors; error ( E_ERROR, "ordinary function has NULL code field." ); } if ( cur->arity < 1 ) { ++errors; error ( E_ERROR, "ordinary function has arity of %d.", cur->arity ); } if ( cur->evaltree != -1 ) { error ( E_WARNING, "ordinary function has evaltree field of %d; this will be ignored.", cur->evaltree ); } break; case EVAL_DATA: case EVAL_EXPR: if ( cur->code != NULL ) { ++errors; error ( E_ERROR, "eval function function has non-NULL code field." ); } if ( cur->arity != -1 ) { error ( E_WARNING, "eval function has arity field of %d; this will be ignored.", cur->arity ); } if ( cur->evaltree < 0 || cur->evaltree >= tree_count ) /* evaluation token refers to a tree that doesn't exist. */ error ( E_FATAL_ERROR, "eval function refers to nonexistent tree (%d).", cur->evaltree ); break; default: ++errors; error ( E_ERROR, "unknown function type %d.", cur->type ); } /* strong typing...*/ cur->return_type = user_fset[i].cset[j].return_type; for (x=0;xarity;x++) { cur->argument_type[x]=user_fset[i].cset[j].argument_type[x]; } (fset[i].cset_by_type[cur->return_type])[pos[cur->return_type]++] = cur; ++k; } else if ( user_fset[i].cset[j].type == TERM_NORM || user_fset[i].cset[j].type == TERM_ERC || user_fset[i].cset[j].type == TERM_ARG ) { /** terminals (all kinds). **/ /* "cur" is so much easier to type. :) */ cur = &(fset[i].cset[k]); /* copy stuff. */ cur->code = user_fset[i].cset[j].code; cur->ephem_gen = user_fset[i].cset[j].ephem_gen; cur->ephem_str = user_fset[i].cset[j].ephem_str; cur->arity = user_fset[i].cset[j].arity; cur->type = user_fset[i].cset[j].type; cur->evaltree = user_fset[i].cset[j].evaltree; /* copy terminal name. */ n = strlen ( user_fset[i].cset[j].string ); cur->string = (char *)MALLOC ( n+1 ); strcpy ( cur->string, user_fset[i].cset[j].string ); cur->string[n] = 0; /* fill in the index field. */ cur->index = k; if ( cur->arity != 0 ) { ++errors; error ( E_ERROR, "terminal has nonzero arity." ); } /* check for correctness of type-dependent fields. */ switch ( cur->type ) { case TERM_NORM: if ( cur->code == NULL ) { ++errors; error ( E_ERROR, "normal terminal has NULL code field." ); } if ( cur->ephem_gen != NULL || cur->ephem_str != NULL ) { ++errors; error ( E_ERROR, "normal terminal has non-NULL ephem_gen and/or ephem_str field(s)." ); } if ( cur->evaltree != -1 ) { error ( E_WARNING, "normal terminal has evaltree field of %d; this will be ignored." ); } break; case TERM_ERC: if ( cur->code != NULL ) { ++errors; error ( E_ERROR, "ERC terminal has non-NULL code field." ); } if ( cur->ephem_gen == NULL || cur->ephem_str == NULL ) { ++errors; error ( E_ERROR, "ERC terminal has NULL ephem_hen and/or ephem_str field(s)." ); } if ( cur->evaltree != -1 ) { error ( E_WARNING, "ERC terminal has evaltree field of %d; this will be ignored." ); } break; case TERM_ARG: ++fset[i].num_args; if ( cur->code != NULL ) { ++errors; error ( E_ERROR, "argument terminal has non-NULL code field." ); } if ( cur->ephem_gen != NULL || cur->ephem_str != NULL ) { ++errors; error ( E_ERROR, "argument terminal has non-NULL ephem_hen and/or ephem_str field(s)." ); } if ( cur->evaltree < 0 ) { ++errors; error ( E_ERROR, "argument terminal should have nonnegative evaltree field." ); } break; } /* strong typing...*/ cur->return_type = user_fset[i].cset[j].return_type; (fset[i].cset_by_type[cur->return_type])[pos[cur->return_type]++] = cur; ++k; } oputs ( OUT_SYS, 30, " " ); oputs ( OUT_SYS, 30, fset[i].cset[k-1].string ); } fset[i].size = k; oputs ( OUT_SYS, 30, "\n" ); } /* if there were any errors, stop now. */ if ( errors ) { error ( E_FATAL_ERROR, "error(s) occurred while processing function set(s)." ); } /* build the internal tree map. */ for ( i = 0; i < tree_count; ++i ) { /* the function set used for this tree. */ tree_map[i].fset = user_tree_map[i].fset; if ( tree_map[i].fset < 0 || tree_map[i].fset >= fset_count ) error ( E_FATAL_ERROR, "tree %d uses a nonexistent function set.\n", i ); tree_map[i].return_type = user_tree_map[i].return_type; if ( tree_map[i].return_type < 0 || tree_map[i].return_type >= NUMTYPES) error ( E_FATAL_ERROR, "tree %d uses an invalid return type: %d.\n", i, tree_map[i].return_type); oprintf ( OUT_SYS, 30, " tree %d uses function set %d.\n", i, tree_map[i].fset ); /* these will be filled in by read_tree_limits(). */ tree_map[i].nodelimit = -1; tree_map[i].depthlimit = -1; /* copy the tree name. */ j = strlen ( user_tree_map[i].name ); tree_map[i].name = (char *)MALLOC ( (j+1) * sizeof ( char ) ); strcpy ( tree_map[i].name, user_tree_map[i].name ); } /* now some more processing on each function set. */ for ( i = 0; i < fset_count; ++i ) { fset[i].function_count = 0; fset[i].terminal_count = 0; for ( j = 0; j < fset[i].size; ++j ) { if ( fset[i].cset[j].arity == -1 ) { /* change the arity of evaluation tokens from -1 to the number of argument tokens in the called tree. */ fset[i].cset[j].arity = fset[tree_map[fset[i].cset[j].evaltree].fset].num_args; if ( fset[i].cset[j].arity == 0 ) /* if there are no argument tokens in the tree, mark this as a terminal. */ fset[i].cset[j].type = EVAL_TERM; } /* update count of functions and terminals. */ if ( fset[i].cset[j].arity ) ++fset[i].function_count; else ++fset[i].terminal_count; } /* now sort the function set so that all the functions come first. */ /* qsort ( fset[i].cset, fset[i].size, sizeof ( function ), function_compare ); */ for (x=0;xarity ? 1 : 0; ba = ((function *)b)->arity ? 1 : 0; return ba-aa; } /* function_compare2() * * comparison function for qsort() that puts all functions ahead of * all terminals. */ int function_compare2 ( const void *a, const void *b ) { int aa, ba; aa = (*(function **)a)->arity ? 1 : 0; ba = (*(function **)b)->arity ? 1 : 0; return ba-aa; } /* free_function_sets() * * free up internal copies of function sets and tree maps. */ void free_function_sets ( void ) { int i, j; for ( i = 0; i < fset_count; ++i ) { for ( j = 0; j < fset[i].function_count + fset[i].terminal_count; ++j ) FREE ( fset[i].cset[j].string ); FREE ( fset[i].cset ); /* Strong Typing */ for (j = 0; j < NUMTYPES ; ++j ) { FREE(fset[i].cset_by_type[j]); } } FREE ( fset ); for ( i = 0; i < tree_count; ++i ) FREE ( tree_map[i].name ); FREE ( tree_map ); fset = NULL; tree_map = NULL; } /* read_tree_limits() * * read limits on tree node count and/or depth from the parameter * database and fill in the appropriate fields of the tree_map * array. */ void read_tree_limits ( void ) { int i, j; char pnamebuf[100]; char *param; for ( i = 0; i < tree_count; ++i ) { /* read the node limit for this tree. */ sprintf ( pnamebuf, "tree[%d].max_nodes", i ); param = get_parameter ( pnamebuf ); if ( param == NULL ) tree_map[i].nodelimit = -1; else tree_map[i].nodelimit = atoi ( param ); /* read the depth limit for this tree. */ sprintf ( pnamebuf, "tree[%d].max_depth", i ); param = get_parameter ( pnamebuf ); if ( param == NULL ) tree_map[i].depthlimit = -1; else tree_map[i].depthlimit = atoi ( param ); } /* read the node limit for the whole individual. */ param = get_parameter ( "max_nodes" ); if ( param == NULL ) ind_nodelimit = -1; else ind_nodelimit = atoi ( param ); /* read the depth limit for the whole individual. note that this is implemented just as a cap on the maximum depth of any single tree in the individual. */ param = get_parameter ( "max_depth" ); if ( param ) { j = atoi ( param ); if ( j >= 0 ) for ( i = 0; i < tree_count; ++i ) if ( tree_map[i].depthlimit < 0 || tree_map[i].depthlimit > j ) tree_map[i].depthlimit = j; } } /* initialize_random() * * initialize the random number generator. */ void initialize_random ( void ) { char *param; long seed; /* look for a seed parameter. */ param = get_parameter ( "random_seed" ); if ( param == NULL ) { /* if it's not found... */ #ifdef RANDOMSEEDTIME /* ...use the current time. */ seed = time(NULL); #else /* ...use 1. */ seed = 1; #endif /* print out what we're using. */ oprintf ( OUT_SYS, 20, " no random number seed specfied; using %d.\n", seed ); } else { /* the parameter was found; use it. */ seed = atol ( param ); oprintf ( OUT_SYS, 20, " seeding random number generator with %d.\n", seed ); } random_seed ( seed ); } /* pre_parameter_defaults() * * used to place values into the parameter database before any application * code is called or any command line options are processed. */ void pre_parameter_defaults ( void ) { add_parameter ( "output.basename", "lilgp", PARAM_COPY_NONE ); add_parameter ( "output.stt_interval", "1", PARAM_COPY_NONE ); add_parameter ( "output.detail", "50", PARAM_COPY_NONE ); add_parameter ( "output.bestn", "1", PARAM_COPY_NONE ); add_parameter ( "output.digits", "4", PARAM_COPY_NONE ); add_parameter ( "init.method", "half_and_half", PARAM_COPY_NONE ); add_parameter ( "init.depth", "2-6", PARAM_COPY_NONE ); add_parameter ( "init.random_attempts", "100", PARAM_COPY_NONE ); add_parameter ( "checkpoint.filename", "gp%06d.ckp", PARAM_COPY_NONE ); /* default problem uses a single population. */ add_parameter ( "multiple.subpops", "1", PARAM_COPY_NONE ); } /* post_parameter_defaults() * * add/change values in the parameter database after all command line options * are parsed. can be used to set defaults based on values of other * parameters. */ void post_parameter_defaults ( void ) { binary_parameter ( "probabilistic_operators", 1 ); } /* process_commandline() * * parses the command line. */ int process_commandline ( int argc, char **argv, int *gen, multipop **mpop ) { int i; int errorflag = 0; int startfromcheckpoint = 0; *mpop = NULL; *gen = 0; /* if there are no arguments, print out a brief statement of usage and exit. */ if ( argc < 2 ) { fprintf ( stderr, "usage: %s options\nValid options are:\n", argv[0] ); fprintf ( stderr, " [-f parameterfile] read named parameter file\n" ); fprintf ( stderr, " [-c checkpointfile] restart from name checkpoint file\n" ); fprintf ( stderr, " [-p name=value] set parameter name to value\n" ); fprintf ( stderr, " [-q] run in quiet mode\n" ); fprintf ( stderr, " [-d symbol] define symbol\n" ); fprintf ( stderr, " [-u symbol] undefine symbol\n" ); #ifdef _PARALLEL_H fprintf ( stderr, " [-m] start as 'm'aster in parallel operation\n"); fprintf ( stderr, " [-w] force progam to 'w'ait for termination of all the nodes\n"); fprintf ( stderr, " [-s low high] start as SLAVE in parallel operation\n" ); fprintf ( stderr, " this is not meant for command line purposes\n" ); fprintf ( stderr, " [-b number] de'b'ug number PVM processes the others\n"); fprintf ( stderr, " processes will run normally.\n"); fprintf ( stderr, " try this to tune the granularity\n" ); fprintf ( stderr, " a number equal to 0 means all the processes(Good luck)\n" ); fprintf ( stderr, " [-h #nodes] impose a number of nodes ('h'osts)\n" ); fprintf ( stderr, " try this to tune the granularity\n" ); fprintf ( stderr, " [-a] force 'a'synchronuous communication between nodes\n"); #endif exit(1); } /* load hardcoded defaults into database. */ pre_parameter_defaults(); for ( i = 1; i < argc; ++i ) { /* all options begin with '-' and have two characters, except "-d" and "-u" which may have more. */ if ( argv[i][0] != '-' || ( argv[i][1] != 'd' && argv[i][1] != 'u' && argv[i][2] != 0 ) ) { error ( E_ERROR, "unrecognized command line option: \"%s\".", argv[i] ); errorflag = 1; continue; } switch ( argv[i][1] ) { case 'f': /* load a parameter file, named in the next argument. */ read_parameter_file ( argv[++i] ); break; case 'p': /* parse a single parameter, in the next argument. */ if ( parse_one_parameter ( argv[++i] ) ) { errorflag = 1; error ( E_ERROR, "malformed parameter: \"%s\".", argv[i] ); } break; case 'c': /* load a checkpoint file, named in the next argument. */ if ( startfromcheckpoint ) { /* error if a checkpoint has already been loaded. */ error ( E_ERROR, "can't load multiple checkpoint files." ); errorflag = 1; continue; } read_checkpoint ( argv[++i], gen, mpop ); startfromcheckpoint = 1; break; case 'q': /* turn on quiet mode (don't dup OUT_SYS to stdout). */ quietmode = 1; break; case 'd': /* define a symbol. */ if ( argv[i][2] ) /* of the form "-dsymbol". */ define_directive ( argv[i]+2 ); else /* of the form "-d symbol". */ define_directive ( argv[++i] ); break; case 'u': /* undefine a symbol. */ if ( argv[i][2] ) /* of the form "-usymbol". */ undefine_directive ( argv[i]+2 ); else /* of the form "-u symbol". */ undefine_directive ( argv[++i] ); break; #ifdef _PARALLEL_H case 'm': /* start as master */ operation_mode = MASTER; break; case 's': /* start as slave */ operation_mode = SLAVE; /* Remove all the default parameters, this will force the SLAVE to get it from the MASTER node */ free_parameters(); if (argv[++i]) low = atoi (argv[i]); else error ( E_ERROR, "No lower bound for the population!" ); if (argv[++i]) high = atoi (argv[i]); else error ( E_ERROR, "No upper bound for the population!" ); if (low > high) error ( E_ERROR, "Lower bound bigger than upper bound." ); break; case 'b': /* spawn a xxgdb (or equivalent) for 'debug_spawns' tasks */ /* specify the number of computing nodes */ if (argv[++i]) debug_spawns = atoi (argv[i]); else error ( E_ERROR, "Specify the number of processes to debug." ); if (debug_spawns == 0) debug_all = 1; if (debug_spawns < 0) { debug_spawns = -debug_spawns; printf ("Assuming a small typo, debugging %d processes\n", debug_spawns); } break; case 'h': /* specify the number of computing nodes */ if (argv[++i]) nhost = atoi (argv[i]); else error ( E_ERROR, "Specify the number of computing nodes." ); break; case 'a': /* Impose asynchronuous communication */ sync_mode = ASYNC; break; case 'w': /* Force the program to wait for termination of every task */ wait_for_everybody = 1; break; #endif default: error ( E_ERROR, "unrecognized command line option: \"%s\".", argv[i] ); errorflag = 1; break; } } if ((spawn_mode == PvmTaskDebug) && (operation_mode == SEQUENTIAL)) error ( E_FATAL_ERROR, "Debugging can only be used for parallel operations." ); if ((nhost != 0) && (operation_mode == SEQUENTIAL)) error ( E_ERROR, "The number of nodes has no meaning in sequential operations." ); if (startfromcheckpoint && (operation_mode != SEQUENTIAL)) error ( E_FATAL_ERROR, "Can not combine checkpoint and parallel operation at the moment :-(" ); if ( errorflag ) error ( E_FATAL_ERROR, "command line errors occurred. dying." ); if ( !startfromcheckpoint && (operation_mode != SLAVE)) post_parameter_defaults(); return startfromcheckpoint; } /* output_system_stats() * * print statistics about memory use, execution time, etc. to OUT_SYS * at conclusion of run. */ void output_system_stats ( event *t_total, event *t_eval, event *t_breed ) { int total, free, max, mallocc, reallocc, freec; int ercused, ercfree, ercblocks, ercalloc; int i; get_ephem_stats ( &ercused, &ercfree, &ercblocks, &ercalloc ); oprintf ( OUT_SYS, 30, "\nSYSTEM STATISTICS\n" ); #ifdef TRACK_MEMORY /* if memory tracking available, then get and print the numbers. */ get_memory_stats ( &total, &free, &max, &mallocc, &reallocc, &freec ); oprintf ( OUT_SYS, 30, "\n------- memory -------\n" ); oprintf ( OUT_SYS, 30, " allocated: %d\n", total ); oprintf ( OUT_SYS, 30, " freed: %d\n", free ); oprintf ( OUT_SYS, 30, " not freed: %d\n", total-free ); oprintf ( OUT_SYS, 30, " max allocated: %d\n", max ); oprintf ( OUT_SYS, 30, " malloc'ed blocks: %d\n", mallocc ); oprintf ( OUT_SYS, 30, " realloc'ed blocks: %d\n", reallocc ); oprintf ( OUT_SYS, 30, " free'ed blocks: %d\n", freec ); #endif #ifdef TIMING_AVAILABLE /* if timing is available, the get and print the numbers. */ oprintf ( OUT_SYS, 30, "\n------- time -------\n" ); oprintf ( OUT_SYS, 30, " overall: %s\n", event_string ( t_total ) ); oprintf ( OUT_SYS, 30, " evaluation: %s\n", event_string ( t_eval ) ); oprintf ( OUT_SYS, 30, " breeding: %s\n", event_string ( t_breed ) ); #endif /* show how large the generation spaces grew. */ oprintf ( OUT_SYS, 30, "\n------- generation spaces -------\n" ); for ( i = 0; i < GENSPACE_COUNT; ++i ) oprintf ( OUT_SYS, 30, " space %3d size: %d\n", i, gensp[i].size ); /* if any ERCs were used, then show these stats. */ if ( ercused > 0 ) { oprintf ( OUT_SYS, 30, "\n------- ephemeral random constants -------\n" ); oprintf ( OUT_SYS, 30, " used: %d\n", ercused ); oprintf ( OUT_SYS, 30, " freed: %d\n", ercfree ); oprintf ( OUT_SYS, 30, " allocated: %d\n", ercalloc ); oprintf ( OUT_SYS, 30, " blocks: %d\n", ercblocks ); } } /* initial_message() * * show startup and copyright messages. */ void initial_message ( void ) { oputs ( OUT_SYS, 0, "\n[ lil-gp Genetic Programming System.\n" ); #ifndef _PARALLEL_H /* Commented out after consulting with the authors */ oputs ( OUT_SYS, 0, "[ Portions copyright (c) 1995 Michigan State University. All rights reserved.\n" ); #else oputs ( OUT_SYS, 0, "[ Original version created at the Michigan State University.\n" ); #endif oputs ( OUT_SYS, 0, "[ kernel version 1.1; September 1998.\n\n\n" ); } #ifdef _PARALLEL_H /* get_nhost() * * returns the number of nodes */ int get_nhost( void ) { return nhost; } /* get_operation_mode() * * returns the operations mode */ int get_operation_mode( void ) { return operation_mode; } /* get_low() * * returns the number of the first population computed here */ int get_low( void ) { return low; } /* get_operation_mode() * * returns the number of the first population number not computed here */ int get_high( void ) { return high; } /* get_sync_mode() * * returns the synchronisation mode [sync|async] */ int get_sync_mode( void ) { return sync_mode; } /* population_mapping() * * returns the task ID of the task simulating the population. */ int population_mapping ( int population_number ) { int i; for (i = 0; i= population_number) return tids[i]; error ( E_FATAL_ERROR, "Unable to map population %d to a task", population_number ); return -1; } /* get_function_set() * * return the pointer to the function set. */ function_set *get_function_set() { return fset; } /* user_stop() * * invoke in case of a user interruption */ void user_stop (int signal) { if (get_operation_mode() == MASTER) { /* First ask everyone to stop */ printf ("=================================================================\n"); printf (" Oh oh, you stopped the master process! There are problably some\n"); printf (" slave tasks still floating around in the PVM.\n"); printf (" \n"); printf (" 1) invoke the PVM console\n"); printf (" 2) reset or terminate your parallel virtual machine\n"); printf ("\tpvm> reset\n"); printf (" OR\n"); printf ("\tpvm> halt\n"); printf ("=================================================================\n\n"); } printf (" End of operations, have a nice day.\n"); exit (1); } /* crash_stop() * * attempt to get some post mortem information about the memory usage */ void crash_stop (int signal) { static char lock = 0; if (lock) { printf ("BREAKING LOOP in crash_stop()\n"); exit (-3); } lock = 1; printf ("Segmentation Fault\n"); /*memory_report(); */ printf (" Report generated after SEGMENTATION FAULT.\n"); /* Let the master know about our failure :-( */ /* if (get_operation_mode() == SLAVE) error (E_FATAL_ERROR, "Segmentation Fault in slave"); */ exit(-2); } #endif