newops.c

遗传规划工具

       function vector of RPB, setup function vector of new ADF, set
       number of arguments of new ADF. */
    adjust_created_branch_parameters(child, num_new_adf_args,from_branch);


    /* Done- normal termination. */
    if (ErrorInDude(child))
    {
        gpi_SendError("Error in brc, operation aborted, child set to parent\n");
        CopyIndividual(parent, child);
        return(1);
    }

    child->adf_type[child->current_number_of_adfs-1] = ADF_TYPE_IPB;
    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);

/*    printf("successful brc\n");*/
    return 0;




}
#endif

/*From BRCREATE.c*/

/* These new operations have a slight violation of Dave's original spec
   in the sense that they return int rather than void: a return
   value less than 0 indicates failure.  */

/* DoBranchCreation():
   This function creates a child which is semantically identical
   to its parent but with one extra ADF, which is created from a
   subexpression within the result producing branch.  The subexpression
   in the RPB is replaced by the appropriate call to the new ADF.  The
   new ADF is the highest-numbered ADF, and can contain calls to any
   functions and terminals which are present in the parent RPB.  The
   "parent" argument is a pointer to the existing parent, while the "child"
   argument is a pointer to a valid existing block of storage presumed
   large enough to hold an Individual.  In practice both locations
   presumably point to locations in the same array of Population
   Members, although there are cases (in some implementations of
   generational selection, for example) where that may not be true. */

int DoBranchCreation(Individual * child, Individual * parent)
{
    int             num_new_adf_args;
    int             donor_size;
    int             donor_index, donor_site, donor_segment_size,
                    num_terminals_in_donor_segment;
    Branch   *new_adf_branch;
    int             i,j,ct,done;
    Branch * from_branch;
    CompInd tind;
#if (USE_CONSTRAINED_STRUCTURE)
	int fvector[TOTAL_NUMBER_OF_FUNCTIONS];
#endif


/*	printf("In BRC\n");*/
    parent = parent; /* keeps the compiler from complaining */

    #if (USE_BRC_FAILURE_HOOK)
        if (BRCFailureHook(parent))
            return(2);
    #endif
    /* There's only room for so many ADFs, so return (with nonzero
       status) if there's no more space for ADFs */
    if (child->current_number_of_adfs == MAX_NUM_ADFS) return 1;

    /* Randomly pick number of args for ADF. */

    num_new_adf_args = _dmin(MAX_NUM_ADF_ARGS, (_dmin(1,MIN_NUM_ADF_ARGS) +
                                RandomInt(MAX_NUM_ADF_ARGS)));

    /* Pick which branch to choose from */
    donor_index = RandomInt(NUM_RPBS + parent->current_number_of_adfs);
    from_branch = GetRightBranch(child,donor_index);

    /* Pick a point within RPB to be the new ADF. */
     donor_size = TraverseSubtree(from_branch, 0) + 1;
#if USE_CONSTRAINED_STRUCTURE
	done =0;
	ct =0;
	while (!done  && ct < MAX_ATTEMPTS)
	{
		ct++;
        donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
		done =1;
            #if (USE_CONSTRAINED_STRUCTURE)
               if (done)
               {
				new_adf_branch = &(child->adfs[child->current_number_of_adfs]);
                CopyFVector(new_adf_branch->function_vector,fvector);
                ConstrainedSyntaxFilters(fvector,new_adf_branch,
												TOP_OF_TREE,0,&gpop);
                }
                /*Compare male_fvector with point fvector.  If no match, done=0*/
                 if (!ValidSubtreeGivenFVector(from_branch, donor_site,fvector))
                    done=0;

            #endif
	}
	if (!done)
	{
        CopyIndividual(parent, child);
/*        printf("Bailing on BRC\n");*/
        return 2;
		
	}
	else
/*		printf("BRC succeeded!\n");*/

#else
     donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
#endif	
    donor_segment_size =
        (TraverseSubtree(from_branch, donor_site)
            - donor_site) + 1;

    if (donor_segment_size >= GetBranchSize(NUM_RPBS+child->current_number_of_adfs)-1)
    {
        CopyIndividual(parent, child);
/*        printf("Bailing on BRC -- donor size too big\n");*/
        return 2;
    }
    num_terminals_in_donor_segment =
        count_terminals_in_subtree(from_branch,
                                   donor_site, donor_segment_size);
    if (num_terminals_in_donor_segment < num_new_adf_args) {
        num_new_adf_args = num_terminals_in_donor_segment;
    }

    /* Copy the "raw" code from the RPB into the appropriate ADF
       branch. */
    (child->current_number_of_adfs)++;
    new_adf_branch = &(child->adfs[child->current_number_of_adfs - 1]);
    CopySubtree(from_branch, donor_site,
                 (donor_site + donor_segment_size) - 1,
                 new_adf_branch, 0);

    /* Copy the function vector verbatim, for now.  This is not the
       same as the final contents of the adjusted function_vector of
       the new ADF, but it is usable, and does not produce errors as
       would using an uninitialized f.v.  (note, for example that the
       _function_arity() macro depends on the function vector to have
       arity of preexisting ADFs set right). */
       /*THIS IS WRONG!!!*/  /* AT BEST, COPY THE ADF_ARITIES INTO THE APPROPRIATE
       SPOTS -- BUT NOT THE WHOLE F-vector!!!*/
    CopyNonStaticFunctionVector(from_branch, new_adf_branch);  /*CHANGE*/

    /*SetJumpsAndVals(new_adf_branch);*/
    /* Perform the cut algorithm over and over until the right number of
       dangling subexpressions, which will be the arguments, is found.
       The cut algorithm is certainly the "area for improvement" in
       this operator.  Array cut_set[][2] contains starting and ending
       indices of subexpressions which will be the arguments, or
       "danglers" of the new ADF. */
    for (i=MAX_NUMBER_OF_CUTSETS_TO_TRY; i>0; i--) {
        if (compute_cut_set(new_adf_branch, donor_segment_size, num_new_adf_args)) {
            break;
        }
    }
    if (i == 0 || TraverseSubtree(from_branch,0) >= (from_branch->num_nodes-1))
    {
        CopyIndividual(parent, child);
/*        printf("Bailing on BRC\n");*/
        return 2;
    }

    /* Replace RPB code with ADF call, using "danglers" as arguments */
    replace_donor_with_adf_call(from_branch,
                                new_adf_branch,
                                (child->current_number_of_adfs) - 1,
                                donor_site, donor_segment_size,
                                num_new_adf_args);

    /* Replace danglers with appropriate formal parameters in the ADF
       branch code. */
    /* CAUTION: do this last, since it tweaks the contents of the cut
       set array.  */
    replace_danglers_with_parameters(new_adf_branch,num_new_adf_args);

    /* Adjust Individual and RPB parameters appropriately: change
       function vector of RPB, setup function vector of new ADF, set
       number of arguments of new ADF. */
    adjust_created_branch_parameters(child, num_new_adf_args,from_branch);


    /* Done- normal termination. */
    if (ErrorInDude(child))
    {
        gpi_SendError("Error in brc, operation aborted, child set to parent\n");
        CopyIndividual(parent, child);
        return(1);
    }
    #if (USE_BRC_END_HOOK)
        BRCEndHook(child);
    #endif
    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);

/*    printf("successful brc\n");*/
    return 0;
}

static void adjust_created_branch_parameters_only(
                struct ind      *child,
                int             num_new_adf_args,
               Branch *  from_branch)
{
    int             i;
    int             br_size;
    Branch   *br;

    /* IMPORTANT NOTE ABOUT INDEXING THE NEW ADF:
       (child->current_number_of_adfs)-1 is the index of the last valid
       ADF in the Individuals poiinted to by "child."  Since new
       branches are now appended to the end of the ADF list regardless,
       then this newest ADF is the highest numbered one, last in the
       list. */

    /* br is just shorthand for the pointer to this ADF branch */
    br = &(child->adfs[(child->current_number_of_adfs)-1]);

    /* br_size is the size of the new ADF.  Executing
       TraverseSubtree() starting from element 0 of the branch returns
       the index of the last valid node in the linear array which
       represents the tree.  We add 1 since the array is numbered from
       0. */
    br_size = TraverseSubtree(br, 0)+1;

    /* set the arity of the new ADF */

/*NO_HARM    child->adf_arity[(child->current_number_of_adfs)-1] = num_new_adf_args;

    for (i=0;i<NUM_RPBS;i++)
        child->rpbs[i].function_vector[_FIRST_ADF+
                        (child->current_number_of_adfs)-1] =   num_new_adf_args;
NO HARM */

/*NO_HARM    from_branch->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] =
                                                             num_new_adf_args;
*/

    /* ADJUST THE FUNCTION VECTOR OF THE NEW ADF */

    /* PART 0: Set ADF references in the function vector to EMPTY */
/*
 Changed: see below
    for (i=_FIRST_ADF; i<=_LAST_ADF; i++) {
        br->function_vector[i] =  EMPTY;
    }
*/
    /* Modification: only disallow this ADF from calling itself */
    /* also, it cannot call any adfs that could 'call' it -- i.e. all
     those lower than the from_branch */

    br->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] = EMPTY;

    /* PART 1: This loop makes sure that all functions and terminals
       (well, particularly ADF calls- funcs and terms were taken care of
       in the calling troutine, which copied the RPB functiion vector))
       which were copied from the RPB into the new ADF branch are
       enabled in the ADF function vector, e.g., if the ADF contains
       "global" terminals, for example.   But that's not quite enough
       (see below). */
    for (i=0; i<br_size; i++) {
        br->function_vector[_fv_map(br->tree[i].opcode)] =
            from_branch->function_vector[_fv_map(br->tree[i].opcode)];
    }

    /* PART 2: The new ADF contains arguments (arg0, arg1, etc.) which
       were not enabled in the RPB (and therefore not enabled in the
       loop above).  Enable them, and for good measure make sure those
       args which should not be present in this branch are indeed
       disabled.  */
    for (i=_FIRST_ADF_ARG; i<=_LAST_ADF_ARG; i++) {
        if (i < (_FIRST_ADF_ARG+num_new_adf_args)) {
            br->function_vector[i] =   0;
        } else {
            br->function_vector[i] =  (-1);
        }
    }
}



static void adjust_created_branch_parameters(
                struct ind      *child,
                int             num_new_adf_args,
               Branch *  from_branch)
{
    int             i;
    int             br_size;
    Branch   *br;

    /* IMPORTANT NOTE ABOUT INDEXING THE NEW ADF:
       (child->current_number_of_adfs)-1 is the index of the last valid
       ADF in the Individuals poiinted to by "child."  Since new
       branches are now appended to the end of the ADF list regardless,
       then this newest ADF is the highest numbered one, last in the
       list. */

    /* br is just shorthand for the pointer to this ADF branch */
    br = &(child->adfs[(child->current_number_of_adfs)-1]);

    /* br_size is the size of the new ADF.  Executing
       TraverseSubtree() starting from element 0 of the branch returns
       the index of the last valid node in the linear array which
       represents the tree.  We add 1 since the array is numbered from
       0. */
    br_size = TraverseSubtree(br, 0)+1;

    /* set the arity of the new ADF */
    child->adf_arity[(child->current_number_of_adfs)-1] = num_new_adf_args;

    for (i=0;i<NUM_RPBS;i++)
        child->rpbs[i].function_vector[_FIRST_ADF+
                        (child->current_number_of_adfs)-1] =   num_new_adf_args;

    from_branch->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] =
                                                             num_new_adf_args;

    /* ADJUST THE FUNCTION VECTOR OF THE NEW ADF */

    /* PART 0: Set ADF references in the function vector to EMPTY */
/*
 Changed: see below
    for (i=_FIRST_ADF; i<=_LAST_ADF; i++) {
        br->function_vector[i] =  EMPTY;
    }
*/
    /* Modification: only disallow this ADF from calling itself */
    /* also, it cannot call any adfs that could 'call' it -- i.e. all
     those lower than the from_branch */

    br->function_vector[_FIRST_ADF+(child->current_number_of_adfs)-1] = EMPTY;

    /* PART 1: This loop makes sure that all functions and terminals
       (well, particularly ADF calls- funcs and terms were taken care of
       in the calling troutine, which copied the RPB functiion vector))
       which were copied from the RPB into the new ADF branch are
       enabled in the ADF function vector, e.g., if the ADF contains
       "global" terminals, for example.   But that's not quite enough
       (see below). */
    for (i=0; i<br_size; i++) {
        br->function_vector[_fv_map(br->tree[i].opcode)] =
            from_branch->function_vector[_fv_map(br->tree[i].opcode)];
    }

    /* PART 2: The new ADF contains arguments (arg0, arg1, etc.) which
       were not enabled in the RPB (and therefore not enabled in the
       loop above).  Enable them, and for good measure make sure those
       args which should not be present in this branch are indeed
       disabled.  */
    for (i=_FIRST_ADF_ARG; i<=_LAST_ADF_ARG; i++) {
        if (i < (_FIRST_ADF_ARG+num_new_adf_args)) {
            br->function_vector[i] =   0;
        } else {
            br->function_vector[i] =  (-1);
        }
    }
}

void replace_danglers_with_parameters(Branch * br, int num_cuts)
{
    int     i, j, point;

    for (i=0; i<num_cuts; i++) {

        point=cut_set[i][START];

        /* set node at point to formal parameter */
        br->tree[point].opcode = MAX_NUM_ADFS + i;

        point++;

        /* delete the rest of the cut branch */
        SafeCopySubtree(br, cut_set[i][END]+1, br->num_nodes, br, point);

        /* the next cut branch has been moved up by the number of deleted
           nodes, which is just the size of branch i minus 1 */
        for (j=i+1; j<num_cuts; j++) {
            cut_set[j][START] -= (cut_set[i][END] - cut_set[i][START]);
            cut_set[j][END] -= (cut_set[i][END] - cut_set[i][START]);
        }
    }
}

void replace_donor_with_adf_call(Branch *pbr,
                                 Branch *newbr,
                                 int opcode,
                      int site, int size, int num_cuts)
{
    int     total_new_size;
    int     point;
    int     i;

    /* total_new_size is the size of the ADF call inserted into the RPB:
       it is equal to 1 (the size of the ADF call itself) plus the size
       of expressions passed as arguments */
    total_new_size = 1;
    for (i=0; i<num_cuts; i++) {
        total_new_size += (cut_set[i][END] - cut_set[i][START]) + 1;
    }


    SafeCopySubtree(pbr, (site+size), TraverseSubtree(pbr, 0), pbr,
                 (site+total_new_size));

    pbr->tree[site].opcode = opcode;
    point = site+1;

    for (i=0; i<num_cuts; i++) {
        CopySubtree(newbr, cut_set[i][START], cut_set[i][END], pbr, point);
        point += (cut_set[i][END] - cut_set[i][START]) + 1;
    }
}


#define IS_A_DUMMY_ARG(index) \
        ((MAX_NUM_ADFS<=(index)) && ((index)<MAX_NUM_ADFS+MAX_NUM_ADF_ARGS))

#define swap(a,b,c) ((c)=(a),(a)=(b),(b)=(c))
int compute_cut_set(Branch * br, int size, int num_cuts)
{
    int     i, j, temp;
#if (USE_CONSTRAINED_STRUCTURE)
	int fvector[TOTAL_NUMBER_OF_FUNCTIONS];
#endif

    /* NOTE: This algorithm is exponentially hard in the number of
       cut points.  A version which disallows testing of points within
       existing danglers would be much more efficient, but probably
       much more complex to code.  */
    for (i=0; i<num_cuts; i++) {
        cut_set[i][START] = RandomInt(size);
        cut_set[i][END]   = TraverseSubtree(br, cut_set[i][START]);
        cut_set[i][INDEX] = i;
        for (j=i-1; j>=0; j--) {
            if ((cut_set[i][START] > cut_set[j][END]) ||
                (cut_set[i][END] < cut_set[j][START])) {
                /* then the two do not overlap */
            } else {