gpkernel.c

遗传规划工具

		cr2_size = TraverseSubtree(female_parent_branch,crosspt2) -
                                                                   crosspt2 +1;
		if ( (p2_size - cr2_size + cr1_size) <= child_branch->num_nodes)
			done=1;
                if ((DepthOfPointInBranch(female_parent_branch,crosspt2) +
                    DepthOfBranchFromPoint(male_parent_branch,crosspt1)) >
                        MAX_DEPTH_FOR_TREE)
                        done =0;
            #if (USE_CONSTRAINED_STRUCTURE)
               if (done)
               {
/*                printf("TEST -- JUST BEFORE GPAP\n");*/
                gpap(female_parent_branch,crosspt2,&pinfo);
                CopyFVector(female_parent_branch->function_vector,fvector);
                ConstrainedSyntaxFilters(fvector,female_parent_branch,TOP_OF_TREE,0,&gpop);
                for (i=pinfo.num_parents-1;i>=0;i--)
                {
                    ConstrainedSyntaxFilters(fvector,female_parent_branch,female_parent_branch->tree[pinfo.parents[i]].opcode,
                                                                          pinfo.branches[i],&gpop);
                }
                /*Compare male_fvector with point fvector.  If no match, done=0*/
                /*int FVectorSubsumeP(int * fvector_large, int * fvector_small)*/
                /*if (!FVectorSubsumeP(fvector,cross_frag_fvector))*/  /*This is, as far as I can tell, completely bogus*/
                 if (!ValidSubtreeGivenFVector(male_parent_branch, crosspt1,fvector))
                    done=0;
               }
            #endif
	}
        if (done)
        {
/*           fprintf(stdout,"DONE!\n");*/
	   if (crosspt2 != 0)
		CopySubtree(female_parent_branch, 0, crosspt2 -1, child_branch, 0);
	   CopySubtree(male_parent_branch, crosspt1, crosspt1 + cr1_size -1, \
						child_branch, crosspt2);
           if ( (crosspt2 + cr2_size -1) < (p2_size -1))
		CopySubtree(female_parent_branch, crosspt2 + cr2_size,
					p2_size-1, child_branch, crosspt2+cr1_size);
           #if (PRINT_CROSSOVER_INDS)
           fprintf(stdout,"CHILD (female crosspt %d)\n",crosspt2);
           PrintIndividual(child,stdout);
           #endif
        }
        else
        {
           #if (PRINT_CROSSOVER_INDS)
            printf("Bailed on Crossover\n");
           #endif
            CopyIndividual(&(gpop.parent2),child);
        }

}

/* DoCrossover actually performs crossover, copying the crossed over portions into the new children.
 It chooses the points, and performs the operation.  The 'level' argument refers to whether leaves or
 nodes will be chosen.  If it is 0, leaves will be chosen.  If it is 1, nodes will be chosen.
*/

int DoCrossover(int level,              /*funcdef - dgpc - DoCrossover*/
                Individual * child,     /*funcdef - dgpc - DoCrossover*/
                Individual * parent,    /*funcdef - dgpc - DoCrossover*/
                int bnum)/*;*/          /*funcdef - dgpc - DoCrossover*/
{
	int p1_size, p2_size, cr1_size, cr2_size;
	int crosspt1, crosspt2;
	int done=0;
	int cross_frag_fvector[TOTAL_NUMBER_OF_FUNCTIONS];
	Branch * child_branch, *male_parent_branch, *female_parent_branch;

	int parent2,female_bnum;
        int ct=0;
	ct=ct;
	male_parent_branch = GetRightBranch(parent, bnum);


	p1_size = TraverseSubtree(male_parent_branch, 0) +1;
	crosspt1 = ChoosePoint(male_parent_branch, p1_size, level);

#if (POINT_TYPING   )
	cr1_size = MakeFunctionVector(male_parent_branch, crosspt1,
                                            cross_frag_fvector)- crosspt1 +1;
        if (!RandCullPopulation(cross_frag_fvector))
	   CullPopulation(cross_frag_fvector);
        #if (SEDUCTION == ON)
    	   parent2 = FindTreeFromCulledPop(!g_male_selection_method);
        #else
    	   parent2 = FindTreeFromCulledPop(0);
        #endif
#else
	cr1_size = TraverseSubtree(male_parent_branch,crosspt1) -
                                                            crosspt1 +1;
        #if (SEDUCTION == ON)
            parent2 = FindGoodTree(!g_male_selection_method);
        #else
            parent2 = FindGoodTree(0);
        #endif
#endif
        UnCompressIndividual(&(gpop.members[parent2]),&(gpop.parent2));	
	CopyIndividual(&(gpop.parent2),child);
	
#if (POINT_TYPING        )
#   ifdef SIZE_WEIGHTED_CROSSOVER_BRANCH_SELECTION
#     if (SIZE_WEIGHTED_CROSSOVER_BRANCH_SELECTION)
	female_bnum = FindGoodSWBranch(&(gpop.parent2), cross_frag_fvector);
#     else
	female_bnum = FindGoodBranch(&(gpop.parent2), cross_frag_fvector);
#     endif
#   else
	female_bnum = FindGoodBranch(&(gpop.parent2), cross_frag_fvector);
#   endif
#else
        female_bnum = bnum;
#endif
	female_parent_branch = GetRightBranch(&(gpop.parent2),female_bnum);
	child_branch = GetRightBranch(child,female_bnum);
	p2_size = TraverseSubtree(female_parent_branch,0) +1;
		
	while (!done  && ct < MAX_ATTEMPTS)
	{

                ct++;
		crosspt2 = ChoosePoint(female_parent_branch, p2_size, level);
		cr2_size = TraverseSubtree(female_parent_branch,crosspt2) -
                                                                   crosspt2 +1;
		if ( (p2_size - cr2_size + cr1_size) <= child_branch->num_nodes)
			done=1;
                if ((DepthOfPointInBranch(female_parent_branch,crosspt2) +
                    DepthOfBranchFromPoint(male_parent_branch,crosspt1)) >
                        MAX_DEPTH_FOR_TREE)
                        done =0;

	}
        if (done)
        {
	   if (crosspt2 != 0)
		CopySubtree(female_parent_branch, 0, crosspt2 -1, child_branch, 0);
	   CopySubtree(male_parent_branch, crosspt1, crosspt1 + cr1_size -1, \
						child_branch, crosspt2);
           if ( (crosspt2 + cr2_size -1) < (p2_size -1))
		CopySubtree(female_parent_branch, crosspt2 + cr2_size,
					p2_size-1, child_branch, crosspt2+cr1_size);
        }
        else
            CopyIndividual(&(gpop.parent2),child);
	return(parent2);
}

/*MUST STILL BE FIXED FOR WVA CODE*/
void DoMutation(Branch * parent, Branch * child)/*;*/ /*funcdef - dgpc - DoMutation*/
{
	Branch mbranch;
	int p_size;
	int inspt;
	int c_size;
	int n_size;
	int done=0;
	int i;
        #if (USE_CONSTRAINED_STRUCTURE)
            ParentInfo pinfo;
            int        fvector[TOTAL_NUMBER_OF_FUNCTIONS];
        #endif
	int ct=0;
        ct=ct;
	mbranch.tree = (Fnode *) calloc(6000, sizeof(Fnode));
	mbranch.branchnum = child->branchnum;
	mbranch.num_nodes = child->num_nodes;
	mbranch.ind = child->ind;
	for (i=0;i<TOTAL_NUMBER_OF_FUNCTIONS;i++)
		mbranch.function_vector[i] = child->function_vector[i];
	
	 p_size = TraverseSubtree(parent, 0) +1;
	 inspt = ChoosePoint(parent, p_size, 2);
	c_size = TraverseSubtree(parent, inspt)  - inspt +1;
	while (!done && ct < MAX_ATTEMPTS)
	{

                ct++;
		if (parent->branchnum < NUM_RPBS)
                {
                   #if (USE_CONSTRAINED_STRUCTURE)
                    gpap(parent,inspt,&pinfo);
                    CopyFVector(parent->function_vector,fvector);
                    ConstrainedSyntaxFilters(fvector,parent,TOP_OF_TREE,0,&gpop);
                    for (i=pinfo.num_parents-1;i>=0;i--)
                    {
                        ConstrainedSyntaxFilters(fvector,parent,parent->tree[pinfo.parents[i]].opcode,
                                                                              pinfo.branches[i],&gpop);
                    }
                    n_size = doCreateRandomCSSTree(&mbranch,0,(gpop.pop_startup_info.max_depth_for_mutation),0,0,fvector);
                                        /*Okay -- going to have to calculate parents and apply filters to get new
                        correct function vector to pass in --(both for adfs and here)*/
                    #else
			n_size = CreateRandomTree(&mbranch,0, (gpop.pop_startup_info.max_depth_for_mutation), 0,0) ;
                    #endif
                }
		else
                {
                    #if (USE_CONSTRAINED_STRUCTURE)
                    gpap(parent,inspt,&pinfo);
                    CopyFVector(parent->function_vector,fvector);
                    ConstrainedSyntaxFilters(fvector,parent,TOP_OF_TREE,0,&gpop);
                    for (i=pinfo.num_parents-1;i>=0;i--)
                    {
                        ConstrainedSyntaxFilters(fvector,parent,parent->tree[pinfo.parents[i]].opcode,
                                                                              pinfo.branches[i],&gpop);
                    }
                    n_size = doCreateRandomCSSTree(&mbranch,0,(gpop.pop_startup_info.max_depth_for_mutation),0,0,fvector);
                    /*Okay -- going to have to calculate parents and apply filters to get new
                        correct function vector to pass in --(both for adfs and here)*/

                    #else
			n_size = CreateRandomTree(&mbranch,0, (gpop.pop_startup_info.max_depth_for_mutation), 0,0);
                    #endif
                }
		if (p_size + n_size - c_size < child->num_nodes)
			done =1;
                if ((DepthOfPointInBranch(parent,inspt) +
                    depth_of_branch(&mbranch)) >=  MAX_DEPTH_FOR_TREE)
                        done =0;
	}
        if (done)
        {
	   if (inspt != 0)
		CopySubtree(parent, 0, inspt -1, child, 0);     	
           CopySubtree(&mbranch, 0, n_size, child, inspt);
	   if ( (inspt + c_size -1) < (p_size -1))
		CopySubtree(parent, inspt + c_size, p_size-1, child, inspt + n_size);
                /*
            printf("done, and completed mutation.\n");
            printf("parent\n");
            PrintIndividual((parent->ind),stdout);
            printf("child\n");
            PrintIndividual((child->ind),stdout);
            */
        }
        else
        {
/*            CopyTree(parent,child);        */
            CopyIndividual(parent->ind, child->ind);
            /*
            printf("bailed due to too many attempts");
            */
        }
	free(mbranch.tree);		
}

/* ReproducePopulation replaces the current population with the next generation of
Individuals.  */

void ReproducePopulation(int early, int counter)/*;*/ /*funcdef - dgpc - ReproducePopulation*/
{
    int i;

    for (i=0;i<(gpop.pop_startup_info.num_individuals);i++)
    {
        gpop.members[i].usage =0;
        gpop.members[i].forward=NULL;
        gpop.members[i].backward=NULL;
        gpop.members[i].op_list = NULL;
        gpop.repro_op_list[i].repro_op_type = -1;
        gpop.repro_op_list[i].parent1 = -1;
        gpop.repro_op_list[i].parent2 = -1;
        gpop.repro_op_list[i].brnum1 = -1;
        gpop.repro_op_list[i].brnum2 = -1;
        gpop.repro_op_list[i].point1 = -1;
        gpop.repro_op_list[i].next_for_parent1 = NULL;
        gpop.repro_op_list[i].next_for_parent2 = NULL;
    }

    for (i=0;i<(gpop.pop_startup_info.num_individuals);i++)
    {
        ChooseOneReproduction( early, counter, i);
    }
    ExecuteOperations();
}



ReproOpInfo * GetUnDoneOp(CompInd * dude) /*;*/ /*funcdef*/
{
    ReproOpInfo * rtemp;
    rtemp = dude->op_list;
    while (rtemp != NULL)
    {
        if (rtemp->repro_op_type != OP_DONE)
            return(rtemp);
        else
        {
            if (&(gpop.members[rtemp->parent1]) == dude)
                rtemp = rtemp->next_for_parent1;
            else if (&(gpop.members[rtemp->parent2]) == dude)
                rtemp = rtemp->next_for_parent2;
            else
            {
                gpi_SendError("Oops, Error in getundone op, none matching dude\n");
            }
        }
    }
    gpi_SendError("Huge error in get undone op, no ops undone!\n");
    #ifdef _ICC
        __asm{seterr;};
	 #endif
	 exit(1);
    return(NULL);
}

CompInd * RemoveFromCindList(CompInd * dude, CompInd * list)/*;*/ /*funcdef*/
{
    if (dude->backward != NULL)
        dude->backward->forward = dude->forward;
    else
        list = dude->forward;
    if (dude->forward != NULL)
        dude->forward->backward = dude->backward;
    dude->backward = NULL;
    dude->forward = NULL;
    return(list);
}

CompInd * PlaceOnCindList(CompInd * dude, CompInd * list)/*;*/ /*funcdef*/
{
    dude->forward = list;
    dude->backward = NULL;
    if (list != NULL)
        list->backward = dude;
    list = dude;
    return(list);
}

void ExecuteOperations(void)/*;*/ /*funcdef*/
{
    int i;
    int from_list;
    Individual * indtemp;
    CompInd * free_dude;
    CompInd *tind;
    ReproOpInfo * op_todo;
    indtemp = &(gpop.tempind);
    gpop.free1 = &(gpop.childx1);
    gpop.free2 = &(gpop.childx2);
    gpop.free1->usage = 0;
    gpop.free2->usage = 0;
    CreateIndividual(indtemp);
    InitializeIndividual(indtemp);
    gpop.free_list = NULL;
    gpop.one_list = NULL;
    gpop.two_list = NULL;
    gpop.more_list = NULL;


     gpop.free_list =PlaceOnCindList(gpop.free1,gpop.free_list);
     gpop.free_list =PlaceOnCindList(gpop.free2,gpop.free_list);
     for (i=0;i<gpop.pop_startup_info.num_individuals;i++)
     {
/*            gpop.members[i].hits = i;*/
             if (gpop.members[i].usage == 0)
                 gpop.free_list = PlaceOnCindList(&(gpop.members[i]),gpop.free_list);
             else if (gpop.members[i].usage == 1)
                 gpop.one_list = PlaceOnCindList(&(gpop.members[i]),gpop.one_list);
             else if (gpop.members[i].usage == 2)
                 gpop.two_list = PlaceOnCindList(&(gpop.members[i]),gpop.two_list);
             else if (gpop.members[i].usage > 2)
                 gpop.more_list = PlaceOnCindList(&(gpop.members[i]),gpop.more_list);
     }
     for (i=0;i<gpop.pop_startup_info.num_individuals;i++)
     {
        if (gpop.one_list != NULL)
        {
            op_todo = GetUnDoneOp(gpop.one_list);
            from_list =1;
        }
        else if (gpop.two_list != NULL)
        {
            op_todo = GetUnDoneOp(gpop.two_list);
            from_list =2;
        }
        else
        {
            op_todo = GetUnDoneOp(gpop.more_list);
            from_list =3;
        }
        CreateIndividual(indtemp);
        InitializeIndividual(indtemp);
        DoReproductiveOp(op_todo, indtemp, i);
        /*
        printf("in main repro loop\n");
        PrintIndividual(&(gpop.tempind),stdout);
        */
        /*
        printf("just after repro.  parent 1 %d, parent 2 %d, op %d\n",
                                             op_todo->parent1,
                                             op_todo->parent2,
                                             op_todo->repro_op_type);
        */
        UpDateDude(op_todo->parent1,from_list);