/* 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 <lilgp.h>
#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; i<nhost; i++)
printf ("%3lds ", full_statistics->eval[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; i<nhost; i++)
{
if (full_statistics->eval[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; i<nhost; i++)
{
if (full_statistics->eval[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;x<NUMTYPES;x++)
{
fset[i].function_count_by_type[x]=0;
fset[i].terminal_count_by_type[x]=0;
fset[i].cset_by_type[x]=(function **)MALLOC (user_fset[i].size * sizeof (function *));
pos[x]=0;
}
oprintf ( OUT_SYS, 30, " set %d:", i );
/* allocate memory for the set. */
m = user_fset[i].size;
fset[i].cset = (function *)MALLOC ( m * sizeof ( function ) );
fset[i].num_args = 0;
k = 0;
/* Strong Typing: determine number of functions by type */
for (j=0;j<m;++j)
{
if (user_fset[i].cset[j].type == FUNC_DATA ||
user_fset[i].cset[j].type == FUNC_EXPR ||
user_fset[i].cset[j].type == EVAL_DATA ||
user_fset[i].cset[j].type == EVAL_EXPR ) /* non-terminals */
{
fset[i].function_count_by_type[user_fset[i].cset[j].return_type]++;
}
else fset[i].terminal_count_by_type[user_fset[i].cset[j].return_type]++;
}
for ( j = 0; j < m; ++j )
{
if ( user_fset[i].cset[j].type == FUNC_DATA ||
user_fset[i].cset[j].type == FUNC_EXPR ||
user_fset[i].cset[j].type == EVAL_DATA ||
user_fset[i].cset[j].type == EVAL_EXPR )
{
/** functions and evaluation tokens **/
cur = &(fset[i].cset[k]);
/* copy some stuff over. */
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 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;x<cur->arity;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;x<NUMTYPES;x++)
{
qsort (fset[i].cset_by_type[x], fset[i].function_count_by_type[x] +
fset[i].terminal_count_by_type[x], sizeof (function *),
function_compare2);
}
}
#ifdef DEBUG
/* dump the function sets to stdout. */
for ( i = 0; i < fset_count; ++i )
{
printf ( "FUNCTION SET %d\n", i );
printf ( " %d functions; %d terminals; %d arguments\n",
fset[i].function_count, fset[i].terminal_count,
fset[i].num_args );
for ( j = 0; j < fset[i].size; ++j )
printf ( "%10s %06x %06x %06x arity: %3d evaltree: %3d index: %3d type: %3d\n",
fset[i].cset[j].string,
fset[i].cset[j].code,
fset[i].cset[j].ephem_gen,
fset[i].cset[j].ephem_str,
fset[i].cset[j].arity,
fset[i].cset[j].evaltree,
fset[i].cset[j].index,
fset[i].cset[j].type );
}
#endif
#ifdef _PARALLEL_H
/* For sending the tree to other computing nodes we need to remap the
"functions" pointers. The "position" and "set" fields have been
defined for that purpose.
The "cset" is the offset in the function set defined by the
"fset" field.
*/
printf ( " Adapting function set for parallel operations:\n" );
for ( i = 0; i < fset_count; ++i )
{
printf ( " Function set %d : ", i );
for ( j = 0; j < fset[i].size; ++j )
{
fset[i].cset[j].fset = i;
fset[i].cset[j].cset = j;
printf ( "." );
fflush (stdout);
}
printf ( "\n" );
}
for ( i = 0; i < fset_count; ++i )
{
for (x=0;x<NUMTYPES;x++)
{
printf ("set %d, type %d : #function = %d #terminals = %d\n",
i,
x,
fset[i].function_count_by_type[x],
fset[i].terminal_count_by_type[x]
);
if ( (fset[i].function_count_by_type[x] == 0) && (fset[i].terminal_count_by_type[x] == 0) )
error (E_FATAL_ERROR, " -!- Function set number %d has no terminals or functions, please remove this type.", x);
}
}
#endif
oprintf ( OUT_SYS, 30, " function set complete.\n" );
return 0;
}
/* function_compare()
*
* comparison function for qsort() that puts all functions ahead of
* all terminals.
*/
int function_compare ( const void *a, const void *b )
{
int aa, ba;
aa = ((function *)a)->arity ? 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<nhost; i++)
if (population_map[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