newops.c

遗传规划工具

                /* then cut point i falls within cut point j: return failure */
                return 0;
            }
        }
    }

    /* sort cut set in order to collapse code properly */
    for (i=0; i<num_cuts-1; i++) {
        for (j=i+1; j<num_cuts; j++) {
            if (cut_set[j][START] < cut_set[i][START]) {
                swap(cut_set[j][START], cut_set[i][START],  temp);
                swap(cut_set[j][END],   cut_set[i][END],    temp);
                swap(cut_set[j][INDEX], cut_set[i][INDEX],  temp);
            }
        }
    }


/* NOTE:  THIS NEXT FUNCTION NEEDS TO BE CHANGED TO REFLECT OUR DESRIE TO PERHAPS
HAVE DIFFERENT ADFS HAVE DIFFERENT FUNCTION VECTORS, AND PERHAPS EVEN ACCEPT DIFFERENT
ARGUMENTS.  SINCE THE INTENT OF BR-CREATE IS NOT TO MUCK WITH THE MAJORITY OF THE FUNCTION VECTOR OF
THE NEW ADF, THE F-VECTOR SHOULD LARGELY REMAIN AS IT WAS IN THE PARENT'S VERSION OF THE ADF.
 THE ADF AND ARG RELATED POSITIONS IN THE FUNCTION VECTOR MIGHT NEED TO CHANGE, BUT NOT THE
 SO-CALLED 'STATIC FUNCTIONS' SUCH AS THOSE
FOR THE GLOBALS OR THE MAIN FUNCTIONS, OR FOR THE RANDOM CONSTANTS.   THE ALLOWABILITY OF THESE
FUNCTIONS IS SPECIFIED BY THE USER AT THE OUTSET IN THE PROBLEM.C FILE, AND THESE VALUES ARE
PLACED INTO THE INITIAL VALUES FOR THE FUNCTION VECTOR.
*/


#if USE_CONSTRAINED_STRUCTURE

for (i=0;i<num_cuts;i++)
{
                CopyFVector(br->function_vector,fvector);
                ConstrainedSyntaxFilters(fvector,br, GetFuncNumber("adf0",&gpop), i,&gpop);
                /*Compare male_fvector with point fvector.  If no match, done=0*/
                 if (!ValidSubtreeGivenFVector(br, cut_set[i][START],fvector))
                    return(0);
}

#endif


/* This next loop is to insure that no 'unallowed' functions show up in the
   part that will become the new adf */
    for (i=0, j=0; i<size; i++) {
        if ((j<num_cuts) && (i == cut_set[j][START])) {
            i = cut_set[j][END]; /* skip over cut subexpression */
            j++;
        } else if (_function_arity(br->tree[i].opcode) == -1) {
            return 0;
        }
    }


/*This next is to prevent there from being dummy arguments in the non-cut
sub-expressions -- i.e., all dummy args from an adf must be in the cut-
expressions*/

 for (i=0, j=0; i<size; i++) {
        if ((j<num_cuts) && (i == cut_set[j][START])) {
            i = cut_set[j][END]; /* skip over cut subexpression */
            j++;
        } else if (IS_A_DUMMY_ARG(br->tree[i].opcode)) {
            return 0;
        }
    }

  return 1;
}

int count_terminals_in_subtree( Branch *br,
                                int subtree_start,
                                int subtree_size)
{
    int     i, subtree_end = subtree_start + subtree_size;
    int     term_count = 0;

    for (i=subtree_start; i<subtree_end; i++) {
        /* if arity of node is zero, it is a terminal for this purpose */
        if (!(_function_arity(br->tree[i].opcode))) {
            term_count++;
        }
    }
    return (term_count);
}
/* END OF brcreate.c: ********** CUT HERE ************ */


/*FROM ARGDUP.c*/
int DoArgumentDuplication(Individual *child, Individual * parent)
{
int     i,error;
int     bchoice,argchoice;
CompInd tind;

    /*Check to see if there are any adfs--if not, return*/
    if (child->current_number_of_adfs < 1)
        return(-1);

    /*Choose a branch in the Individual upon which to do arg
    duplication*/
    bchoice = RandomInt(child->current_number_of_adfs);

    /*Check to see if this adf has args, else return*/
    if (child->adf_arity[bchoice] < 1) {
        return(-1);
    } else if (child->adf_arity[bchoice] >= MAX_NUM_ADF_ARGS) {
        return(-1);
    }

    /*Choose an argument to duplicate*/
    argchoice = RandomInt(child->adf_arity[bchoice]);

    /*Duplicate the arguments in each place where the ADF is internally
    invoked*/
    error  = 0;
    for (i=0;i<NUM_RPBS;i++)
    {
         if (error == 0)
             error =  DuplicateArgument(bchoice,argchoice,
             &(child->rpbs[i]));
      if (error >0)
             error=0;
    }
    for (i=0;i<child->current_number_of_adfs;i++)
    {
        if (error ==0)
           if (parent->adfs[i].function_vector[bchoice] > -1 )
               error =  DuplicateArgument(bchoice, argchoice,
               &(child->adfs[i]));
        if (error >0)
             error=0;
    }

    /*error will be non-zero when there was an error in duplication,
    this will often be due to overwriting the space available for the
    Individual's branch b/c of the arg duplication, which can be
    exponentially explosive wrt memory*/
    if (error < 0)
    {
        CopyIndividual(parent,child);
        return(-1);
    }

    /*Tidy up the function_vectors and the adf_arity*/
    for (i=0;i< NUM_RPBS;i++)
        if (child->rpbs[i].function_vector[bchoice] > -1)
                (child->rpbs[i].function_vector[bchoice])++;
    for (i=0;i< child->current_number_of_adfs;i++)
        if (child->adfs[i].function_vector[bchoice] > -1)
                (child->adfs[i].function_vector[bchoice])++;
    (child->adf_arity[bchoice])++;
    child->adfs[bchoice].function_vector[MAX_NUM_ADFS + child->adf_arity[bchoice] -1 ] = 0;

     /*Switch half of the references of the arg being duplicated
     inside the branch upon which arg duplication is taking place*/
    SwitchOccurencesOfFunction(&(child->adfs[bchoice]),
        MAX_NUM_ADFS+argchoice,
        MAX_NUM_ADFS+(child->adf_arity[bchoice]-1),
        (float)PROB_SWITCH_ARG);
/*    i = TraverseSubtree(&(child->adfs[bchoice]),0);*/
    if (ErrorInDude(child))
    {
        gpi_SendError("Error in arg dup, operation aborted, child set to parent\n");
        CopyIndividual(parent, child);
        return(1);
    }
    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);

    return(0);
}

void  SwitchOccurencesOfFunction(Branch *br, int old,
                                             int new, float prob)
{
    int     br_size;
    int     i;
    br_size = TraverseSubtree(br, 0)+1;
    for (i=0; i<br_size; i++) {
        if (br->tree[i].opcode == old) {
            if (RandomFloat((float)1.0)<= prob) {
                br->tree[i].opcode = new;
            }
        }
    }
}

static int DuplicateArgument(int bchoice, int argchoice,
                             Branch * cbranch)
{

    int i;
    int size_error =0;
    Branch temp_tree;
    int end_of_br;


    temp_tree.branchnum = cbranch->branchnum;
    temp_tree.num_nodes = cbranch->num_nodes;
    temp_tree.ind = cbranch->ind;
    for (i=0;i<TOTAL_NUMBER_OF_FUNCTIONS;i++)
        temp_tree.function_vector[i] = cbranch->function_vector[i];
    temp_tree.tree = (Fnode *)calloc(temp_tree.num_nodes,sizeof(Fnode));
    end_of_br = TraverseSubtree(cbranch,0);
    size_error = doDuplicateArgument(bchoice, argchoice, cbranch,
                                                             &temp_tree, 0, &end_of_br);
    free(temp_tree.tree);

/*    i=TraverseSubtree(cbranch,0);    */
    return(size_error);
}

static int doDuplicateArgument(int bchoice, int argchoice,
                        Branch * br,
                        Branch * tbr,
                        int index,
                        int * end_of_br)
{
	int i,num,start_pt,end_pt,tindex;

	if (br->tree[index].opcode == EMPTY)
        {
       		return(-1);
        }
	if (index >= br->num_nodes)
        {
    	        return(-1);
        }
	else
	{
    		num = index;
                for (i=0;i< _function_arity(br->tree[num].opcode);i++)
		{
                    if ((br->tree[num].opcode == bchoice) &&  i == argchoice)
                    {

                        start_pt = index+1;
                        end_pt = TraverseSubtree(br,start_pt);
                        if (((*end_of_br)+ 1 + end_pt-start_pt+1) >= br->num_nodes)
                                return(-1);

                         CopySubtree(br,start_pt,(*end_of_br),tbr,0);
                         CopySubtree(tbr,0,(*end_of_br)-start_pt, br,end_pt+1);
                         (*end_of_br) = (*end_of_br) +  (end_pt - start_pt) +1;
                         tindex = doDuplicateArgument(bchoice,argchoice,br,tbr,index+1,end_of_br);

                         if (tindex >= br->num_nodes || tindex == -1)
                            return(-1);
                         index = tindex;
                    }
                    index = doDuplicateArgument(bchoice, argchoice, br,tbr, index+1,end_of_br);
                    if (index+1 >= br->num_nodes || index == -1)
                        return(-1);
		}	
	}
	return(index);
}

/*from ARGDEL.c*/
int DoArgumentDeletion(Individual *child, Individual * parent)
{
int     i,error;
int     bchoice,argchoice;
char str[256];
CompInd tind;
    /* We assume that the parent has already been copied into the
       child */

    /*Check to see if there are any adfs--if not, return*/
    if (child->current_number_of_adfs < 1)
        return(-1);

    /*Choose a branch in the Individual upon which to do arg
    deletion*/
    bchoice = RandomInt(child->current_number_of_adfs);

    /*Check to see if this adf has enough args to delete one, else return*/
    if (child->adf_arity[bchoice] < 2) {
        return(-1);
    } else if (child->adf_arity[bchoice] > MAX_NUM_ADF_ARGS) {
         sprintf(str,"child->adf_arity is too high.\n");
         gpi_SendError(str);
         exit(-1);
    }

    /*Choose an argument to delete*/
    argchoice = RandomInt(child->adf_arity[bchoice]);

    /*Delete the arguments in each place where the ADF is internally
    invoked*/
    error  = 0;
    for (i=0;i<NUM_RPBS;i++)
    {
         if (error == 0)
             error =  DeleteArgument(bchoice,argchoice, &(child->rpbs[i]));
      if (error >0)
             error=0;
    }
    for (i=0;i<child->current_number_of_adfs;i++)
    {
        if (error ==0)
           if (parent->adfs[i].function_vector[bchoice] > -1 )
               error =  DeleteArgument(bchoice, argchoice, &(child->adfs[i]));
        if (error >0)
             error=0;
    }

    /*error will be not often be  non-zero when there was an error in deletion,
    but may occur */
    if (error < 0)
    {
        CopyIndividual(parent,child);
        return(-1);
    }

    /*Tidy up the function_vectors and the adf_arity*/
    for (i=0;i< NUM_RPBS;i++)
        if (child->rpbs[i].function_vector[bchoice] > -1)
                (child->rpbs[i].function_vector[bchoice])--;
    for (i=0;i< child->current_number_of_adfs;i++)
        if (child->adfs[i].function_vector[bchoice] > -1)
                (child->adfs[i].function_vector[bchoice])--;
    (child->adf_arity[bchoice])--;
    child->adfs[bchoice].function_vector[MAX_NUM_ADFS + (child->adf_arity[bchoice])] = -1;


    /*Replace all occurances of the arg to be deleted with a randomly chosen one of
    the other arguments (there must be one, due to the fact that only adfs with 2 args can
    undergo arg deletion */

    ReplaceArg(&(child->adfs[bchoice]),MAX_NUM_ADFS+argchoice,MAX_NUM_ADFS,(child->adf_arity[bchoice])+1);

     /*Rename any arguments ABOVE the once being deleted in the branch to one lower
     starting with moving n+1 to n, then n+2 to n+1, etc*/

    for (i=(MAX_NUM_ADFS+argchoice+1);i<(MAX_NUM_ADFS+child->adf_arity[bchoice] +1);i++)
        SwitchOccurencesOfFunction(&(child->adfs[bchoice]), i, i-1,(float) 1.0);
/*    i = TraverseSubtree(&(child->adfs[bchoice]),0);*/
    if (ErrorInDude(child))
    {
        gpi_SendError("Error in arg del, operation aborted, child set to parent\n");
        CopyIndividual(parent, child);
        return(1);
    }
/*    printf("right before compress ind in arg deletion\n");*/
    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);

    return(0);
}


static void ReplaceArg(Branch *br, int ArgToBeReplaced,
                       int FirstArg, int NumArgs)
{


    int br_size;
    int i;
    int temp;
    FirstArg = FirstArg;
    br_size = TraverseSubtree(br,0)+1;
    for (i=0;i<br_size;i++)
    {
        if (br->tree[i].opcode == ArgToBeReplaced)
        {
             temp = RandomInt(NumArgs-1);
             if (temp == ArgToBeReplaced)
                temp = NumArgs-1;
             br->tree[i].opcode = temp+MAX_NUM_ADFS;
        }
    }
}

static int DeleteArgument(int bchoice, int argchoice,
                             Branch * cbranch)
{

    int i;
    int size_error =0;
    Branch temp_tree;
    int end_of_br;

    temp_tree.branchnum = cbranch->branchnum;
    temp_tree.num_nodes = cbranch->num_nodes;
    temp_tree.ind = cbranch->ind;
    for (i=0;i<TOTAL_NUMBER_OF_FUNCTIONS;i++)
        temp_tree.function_vector[i] = cbranch->function_vector[i];
    temp_tree.tree = (Fnode *)calloc(temp_tree.num_nodes,sizeof(Fnode));
    end_of_br = TraverseSubtree(cbranch,0);
    size_error = doDeleteArgument(bchoice, argchoice, cbranch,
                                                             &temp_tree, 0, &end_of_br);
    free(temp_tree.tree);
/*    i = TraverseSubtree(cbranch,0);*/
    return(size_error);
}

static int doDeleteArgument(int bchoice, int argchoice,
                        Branch * br,
                        Branch * tbr,
                        int index,
                        int * end_of_br)
{
	int i,num,start_pt,end_pt;

	if (br->tree[index].opcode ==  EMPTY)
        {
       		return(-1);
        }
	if (index >= br->num_nodes)
        {
    	        return(-1);
        }
	else
	{
    		num = index;
                for (i=0;i< _function_arity(br->tree[num].opcode);i++)
		{
                    if ((br->tree[num].opcode == bchoice) &&  i == argchoice)
                    {
                        start_pt = index+1;
                        end_pt = TraverseSubtree(br,start_pt);
                         SafeCopySubtree(br,end_pt+1,(*end_of_br),br,start_pt);

                         (*end_of_br) = (*end_of_br) - ( (end_pt - start_pt) +1);
                    }
                    else
                    {
                    index = doDeleteArgument(bchoice, argchoice, br,tbr, index+1,end_of_br);
                    }
                    if (index+1 >= br->num_nodes || index == -1)
                        return(-1);

		}	
	}
	return(index);
}