newops.c

遗传规划工具

            /* the new segment to be inserted in place of the
               ADF call is new_subtree_seg */
               /*
            if (    brdel_make_new_seg(LEXUS, brnum, br, point, endpoint,
                                       new_subtree_seg, &new_subtree_size)
                    == 0) {}*/
                    /*Using PINTO -- THERE IS A BUG IN THE LEXUS VERSION!!!*/

                (void) brdel_make_new_seg(PINTO, brnum, br, point, endpoint,
                                            new_subtree_seg,
                                            &new_subtree_size);

            /* Must check the size to make sure the new expanded
               branch will not be made bigger than the max size: if it
               is, then we force the PINTO option, which replaces the
               ADF call with a single terminal, which cannot make the
               expanded branch bigger */
            /* NOTE: this condition should not be true if the routine above
               returned 0 and PINTO option was already forced above. */
            if (    (expanded_subtree_size +
                        (new_subtree_size - old_subtree_size )) >=
                    br->num_nodes-1) {
                (void) brdel_make_new_seg(PINTO, brnum, br, point, endpoint,
                                   new_subtree_seg, &new_subtree_size);
            }
            /* the new segement is inserted and the branch is
               resized appropriately */
            brdel_insert_seg(br, point, endpoint,
                               new_subtree_seg,
                               new_subtree_size);
        }
    }
point = TraverseSubtree(br,0);
}

static void brdel_insert_seg(
                   Branch    *br,
                   int              point,
                   int              endpoint,
                   Fnode            *new_subtree_seg,
                   int              new_subtree_size)
{
    int     br_endpt, i;

    br_endpt = TraverseSubtree(br,0);
    SafeCopySubtree(br, endpoint+1, br_endpt, br,
                        point+new_subtree_size);
    for (i=0; i<new_subtree_size; i++) {
        br->tree[point+i].opcode = new_subtree_seg[i].opcode;

    }
}

/* This routine returns a new segment to be inserted
   into the branch.  In the Pinto version, it is a
   random terminal (size one).  In the Cadillac (Lexus?)
   version it is the inline expanded call to the
   deleted branch code. */
static int brdel_make_new_seg(
                    int brdel_type, /* LEXUS or PINTO */
                    int brnum, /* branch num of deleted branch */
                    Branch *br, /* branch being modified */
                    int point,/*start of ADF call to be expanded (index in br)*/
                    int endpoint, /* end of ADF call to be expanded */
                    Fnode *new_subtree_seg,
                    int *new_subtree_size)
{
    static Branch    fake_branch;
    int     apar_start, apar_end, apar_len;
    int     fpar_point, current_endpoint, argnum;
    char str[256];

    if (brdel_type == PINTO) {
        *new_subtree_size = 1;
		#if SPICE_PROBLEM && USE_CONSTRAINED_STRUCTURE 			/* THIS IS TERRIBLE!! GET IT OUT OF HERE!! */
        new_subtree_seg[0].opcode = GetFuncNumber("dend",&gpop);
		#else
        new_subtree_seg[0].opcode = gen_random_legal_term(br,brnum);
        #endif

        return 1;
    } else {
        sprintf (str,"in brdel_make_new_seg(): WRONG brdel_type\n");
        gpi_SendError(str);
        exit(1001);
    }
}

static int gen_random_legal_term(Branch    *br,int brnum)
{
    int     random_atom;

    while(1) {
        random_atom = RandomInt(TOTAL_NUMBER_OF_FUNCTIONS);
        if (random_atom != brnum && br->function_vector[random_atom] ==   0)
        {
            if (random_atom != TOTAL_NUMBER_OF_FUNCTIONS-1)
                return random_atom;
            else
             {
            return(TOTAL_NUMBER_OF_FUNCTIONS-1 + RandomInt(_min(MAXNUMFORARANDOMCONSTANT,
                                                             gpop.num_constants) -
                                                         (gpop.num_general_functions-1)));
            }
        }
    }
}

/*===========================================================*/
/*=== end of routines supporting brdel_replace_adf_call() ===*/
/*===========================================================*/

static void brdel_fix_function_vector(int brnum, Branch *br)
{
    int i;

    for (   i=_FIRST_ADF+brnum+1;
            i<_FIRST_ADF+br->ind->current_number_of_adfs;
            i++  ) {
        br->function_vector[i-1] = br->function_vector[i];
    }

    br->function_vector[_FIRST_ADF+br->ind->current_number_of_adfs-1] =  EMPTY;
}

static void brdel_rename_refs(Branch *br, int  from, int    to)
{
    int i;

    for (i=0; i<br->num_nodes; i++) {
        if (br->tree[i].opcode == (_FIRST_ADF + from)) {
            br->tree[i].opcode =  _FIRST_ADF + to;
        }
    }
}

#if (USE_ITERATION_GROUP_CREATION)
int DoNoHarmIterationPerformingBranchCreation(Individual * child,Individual * parent)
{
    int i,j;
    int ipb_count;
    int nadf_count;
    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;
    Branch * from_branch;
    CompInd tind;

    ipb_count=0;
    nadf_count=0;
    for (i=0;i<MAX_NUM_ADFS;i++)
    {
        if (parent->adf_type[i] == ADF_TYPE_ADF)
            nadf_count++;
        else if (parent->adf_type[i] == ADF_TYPE_IPB)
            ipb_count++;
    }


    parent = parent; /* keeps the compiler from complaining */

    /* 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;
    }
    /*There is only room for so many ipbs*/
    if (ipb_count >= MAX_NUM_IPBS)
    {
        return(1);
    }
    /* Randomly pick number of args for ADF. */

    num_new_adf_args = 0; /*_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);
    from_branch = GetRightBranch(child,donor_index);

    /* Pick a point within RPB to be the new ADF. */
     donor_size = TraverseSubtree(from_branch, 0) + 1;
     donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
    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);
        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);
        return 2;
    }


/*THIS CODE IS COMMENTED OUT SO THAT THE PARENT BRANCH DOES NOT CHANGE*/
    /* 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);*/
/*END OF NO HARM REGION*/

    /* Adjust Individual and RPB parameters appropriately: change
       function vector of RPB, setup function vector of new ADF, set
       number of arguments of new ADF. */

       /*NO HARM VERSION*/
    adjust_created_branch_parameters_only(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



#if (USE_ITERATION_GROUP_CREATION)
int DoIterationGroupCreation(Individual * child,Individual * parent)
{
    int i,j;
    int ipb_count;
    int nadf_count;

    ipb_count=0;
    nadf_count=0;
    for (i=0;i<MAX_NUM_ADFS;i++)
    {
        if (parent->adf_type[i] == ADF_TYPE_ADF)
            nadf_count++;
        else if (parent->adf_type[i] == ADF_TYPE_IPB)
            ipb_count++;
    }

    /* 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;

    /*There is only room for so many ipbs*/
    if (ipb_count+4 > MAX_NUM_IPBS)
        return(1);
    for (i=0;i<3;i++)
    {
        j = DoNoHarmIterationPerformingBranchCreation(child,parent);/*&(gpop.parent2));           */
        if (j>0)
        {
            CopyIndividual(parent,child);
            return(1);
        }
    }
    j = DoIterationPerformingBranchCreation(child,parent);
    if (j>0)
    {
        CopyIndividual(parent,child);
        return(1);
    }
}
#endif


#if (USE_IPBCO || USE_ITERATION_GROUP_CREATION)
int DoIterationPerformingBranchCreation(Individual * child,Individual * parent)
{
    int i,j;
    int ipb_count;
    int nadf_count;
    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;
    Branch * from_branch;
    CompInd tind;

    ipb_count=0;
    nadf_count=0;
    for (i=0;i<MAX_NUM_ADFS;i++)
    {
        if (parent->adf_type[i] == ADF_TYPE_ADF)
            nadf_count++;
        else if (parent->adf_type[i] == ADF_TYPE_IPB)
            ipb_count++;
    }


    parent = parent; /* keeps the compiler from complaining */

    /* 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;

    /*There is only room for so many ipbs*/
    if (ipb_count >= MAX_NUM_IPBS)
        return(1);

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

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

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

    /* Pick a point within RPB to be the new ADF. */
     donor_size = TraverseSubtree(from_branch, 0) + 1;
     donor_site = ChoosePoint(from_branch, donor_size, 1);/*was 2*/
    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