newops.c

遗传规划工具

/*======================================================================+
| PGPC: Parallel Genetic Programming in C                               |
| (c) 1994 Genetic Algorithm Technology Corp. all rights reserved       |
   written by David Andre
+======================================================================*/
/*======================================================================+
| FILE: newops.c                                                        |
| DESCRIPTION: Implements adaptive ADF architecture operators for       |
| the DGPC module.                                                      |
| REVISIONS:                                                            |
| Nov 30, 1994:  Fixed to make it work with all the changes.            |
| Jan 24, 1995:  Works as of today, no known bugs.                      |
+======================================================================*/

/*==============================+
| HEADERS                       |
+==============================*/

/* System headers */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "gp.h"


/*#ifndef __BORLANDC__
#include <misc.h>
#endif*/

#ifdef _ICC
#include <iocntrl.h>
#include <process.h>
#include <channel.h>
#include <semaphor.h>
#include "mncommon.h"
#endif

/* User headers */
#include "proto.h"
#include "newops.h"
#ifdef _ICC
#include "gpi.h"
#else
#include "gpi_stub.h"
#endif
extern Population gpop;
/*==============================+
| LOCAL DECLARATIONS            |
+==============================*/
/*from newops.c*/
static void modify_adf_references(Branch *br, int new, int old);
/*from brdelete.c*/
static void brdel_replace_adf_call(int brnum, Branch *br);

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

static int brdel_make_new_seg(
                    int brdel_type, /* LEXUS or PINTO */
                    int             brnum,
                    Branch   *br,
                    int             point,
                    int             endpoint,
                    Fnode           *new_subtree_seg,
                    int             *new_subtree_size);

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

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

static void brdel_rename_refs(Branch *br, int  from, int    to);
/*from brcreate.c*/
#define ALLOW_GLOBALS_IN_CREATED_BRANCHES   1
#define FALSE                               0
#define MAX_NUMBER_OF_CUTSETS_TO_TRY        64

/* START OF brcreate.c: ********** CUT HERE ************ */
static int  count_terminals_in_subtree(
                    Branch   *br,
                    int             subtree_start,
                    int             subtree_size);

static int  compute_cut_set(
                    Branch   *br,
                    int             size,
                    int             num_cuts);

static void replace_donor_with_adf_call(
                    Branch   *pbr,
                    Branch   *newbr,
                    int             opcode,
                    int             site,
                    int             size,
                    int             num_cuts);

static void replace_danglers_with_parameters(
                    Branch   *br,
                    int             num_args);

static void adjust_created_branch_parameters(
                    struct ind      *child,
                    int             num_new_adf_args,
                    Branch * from_branch);

static void adjust_created_branch_parameters_only(
                    struct ind      *child,
                    int             num_new_adf_args,
                    Branch * from_branch);


/* symbolic names for cut_set indices */
#define START   0
#define END     1
#define INDEX   2
#define     MAXARGS     20
static int  cut_set[MAXARGS][3];
/*from argdup.c*/
#define PROB_SWITCH_ARG 0.50

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

void  SwitchOccurencesOfFunction(
                            Branch *br, int old,
                            int new, float prob);

static int doDuplicateArgument(
                        int bchoice, int argchoice,
                        Branch * br,
                        Branch * tbr,
                        int index, int * end_of_br);
/*from argdel.c*/
static int DeleteArgument(
                            int bchoice, int argchoice,
                            Branch * cbranch);

static void ReplaceArg(Branch *br, int ArgChoice, int FirstArg, int NumArgs);

static int doDeleteArgument(
                        int bchoice, int argchoice,
                        Branch * br,
                        Branch * tbr,
                        int index, int * end_of_br);
/*END OF DECLARATIONS*/



/*FROM NEWOPS.c*/

/* NOTE: this operation may do nothing if the Individual already has a
   full complement of ADFs or if it has no ADFs to duplicate */
int DoBranchDuplication(Individual * child, Individual * parent)
{
    int             i;
    int             dup_branch_index, new_branch_index;
    Branch   *dup_branch_ptr, *new_branch_ptr;
    CompInd tind;


    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);


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

    if (child->current_number_of_adfs == MAX_NUM_ADFS) {
        /* Can't do branch duplication: Individual is maxed out on ADFs */
        return 1;
    } else if (child->current_number_of_adfs == 0) {
        /* Can't do branch duplication: no branches to duplicate */
        return 2;
    }


    /* Randomly select an ADF branch for duplication */
    dup_branch_index = RandomInt(child->current_number_of_adfs);

     #if (USE_BRDUP_FAILURE_HOOK)
     if (BRDUPFailureHook(parent,dup_branch_index))
        return(1);
     #endif



    dup_branch_ptr   = &(child->adfs[dup_branch_index]);

    /* The new branch will be located at the end of the list (which
       will therefore need to be incremented in size). */
    new_branch_index = child->current_number_of_adfs;
    new_branch_ptr   = &(child->adfs[new_branch_index]);
    (child->current_number_of_adfs)++;

    /* Copy the old branch into the new... */
    CopyTree(dup_branch_ptr, new_branch_ptr);


    child->adf_arity[new_branch_index] = child->adf_arity[dup_branch_index];
    child->rpbs[0].function_vector[_FIRST_ADF+new_branch_index] =
                                        child->adf_arity[new_branch_index];

    for (i=_FIRST_ADF; i<=_LAST_ADF; i++) {
        child->adfs[new_branch_index].function_vector[i] =
            child->adfs[dup_branch_index].function_vector[i];
    }
    for (i=_FIRST_ADF_ARG; i<=_LAST_ADF_ARG; i++) {
        child->adfs[new_branch_index].function_vector[i] =
            child->adfs[dup_branch_index].function_vector[i];
    }
    for (i=0; i<child->current_number_of_adfs; i++) {
        modify_adf_references(&(child->adfs[i]),
                                    _FIRST_ADF+new_branch_index,
                                    _FIRST_ADF+dup_branch_index);
    }

    for (i=0; i<NUM_RPBS; i++) {
        modify_adf_references(&(child->rpbs[i]),
                                    _FIRST_ADF+new_branch_index,
                                    _FIRST_ADF+dup_branch_index);
    }

    /* Normal termination */
/*    i = TraverseSubtree(new_branch_ptr,0);*/
    if (ErrorInDude(child))
    {
        gpi_SendError("Error in branch duplication, operation aborted, child set to parent\n");
        CopyIndividual(parent, child);
        return(1);
    }
    #if (USE_BRDUP_END_HOOK)
        BRDUPEndHook(child, dup_branch_index);
    #endif

    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);
    return 0;

}

static void modify_adf_references(Branch *br, int new, int old)
{
    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 (RandomInt(2)) {
                br->tree[i].opcode = new;
            }
        }
    }

    /* Whether or not there were any actual references, any branch which
       was allowed to call the old ADF is allowed to call the new one as
       well.    */
    br->function_vector[new] = br->function_vector[old];

}

/* utility function copies a function_vector from one branch to another */
void CopyFunctionVector(Branch *br1, Branch *br2)
{
    int     i;

    for (i=0; i<TOTAL_NUMBER_OF_FUNCTIONS; i++) {
        br2->function_vector[i] = br1->function_vector[i];
    }
}

void CopyNonStaticFunctionVector(Branch *br1, Branch *br2)
{
    int     i;

    for (i=_FIRST_ADF; i<_LAST_ADF_ARG; i++) {
        br2->function_vector[i] = br1->function_vector[i];
    }
}

/* utility function copies a subtree from one place to another, using
   an intermediate buffer so that if from_br and to_br are in the same
   tree then the operation will not get clobbered */
#define SAFE_COPY_SIZE_LIMIT    4096
static Fnode safe_copy_buf[SAFE_COPY_SIZE_LIMIT];
void SafeCopySubtree(Branch * from_br, int from_start, int from_end,
                       Branch * to_br,   int to_start)
{

    int i,j;
    char str[256];

    if (((from_end - from_start)+1)>SAFE_COPY_SIZE_LIMIT) {
        sprintf(str,
            "Error,oops, in SafeCopySubtree(): block size greater than limit ");
        gpi_SendError(str);
        sprintf(str,"(%d)\nUsing regular CopySubtree() instead...",
            SAFE_COPY_SIZE_LIMIT);
        gpi_SendError(str);
        CopySubtree (from_br, from_start, from_end, to_br, to_start);
    }
    for (i=from_start, j=from_start; i <= from_end; i++,j++) {
        safe_copy_buf[j].opcode = from_br->tree[i].opcode;
    }
    for (i=from_start, j=to_start; i <= from_end; i++,j++) {
        to_br->tree[j].opcode = safe_copy_buf[i].opcode;
    }
}

/* yet another handy utility function */
void MoveBranch(Branch *src, Branch *dest)
{
    dest->num_nodes = src->num_nodes;

#if (USE_MULTI_TYPED_ADFS)
    dest->ind->adf_type[dest->branchnum - NUM_RPBS] = src->ind->adf_type[src->branchnum - NUM_RPBS];
#endif
    CopyTree(src, dest);
    CopyFunctionVector(src, dest);

}

/*FROM brdelete.c*/

int DoBranchDeletion(Individual * child, Individual * parent)
{
    int     del_brnum, i, j;
    CompInd tind;

    parent = parent;
    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);
    /* can't delete branches if there are no branches... */
    if (child->current_number_of_adfs == 0) return 1;

    /* randomly (?) pick ADF to delete */
    /* Comment: ultimately, it is probably best to delete
       preferentially those single-terminal branches, replacing
       the call with the arg. */
    del_brnum = RandomInt(child->current_number_of_adfs);

    /* Go thru the other branches and remove calls to the
       deleted ADF.  replace_call_to_adf() is probably the
       function in which the difference between the cadillac
       and pinto versions is expressed  */
    for (i=0; i<NUM_RPBS; i++) {
        brdel_replace_adf_call(del_brnum, &(child->rpbs[i]));
    }
    for (i=0; i<child->current_number_of_adfs; i++) {
        brdel_replace_adf_call(del_brnum, &(child->adfs[i]));
    }

    for (i=del_brnum+1; i<child->current_number_of_adfs;i++) {
        /* Move all physical contents of other branches
           to fill the "hole" left by the deleted branch. */
        /* code for MoveBranch is in newops.c */
        MoveBranch(&(child->adfs[i]), &(child->adfs[i-1]));
    }

#if (USE_MULTI_TYPED_ADFS)
    child->adf_type[child->current_number_of_adfs-1] = -1;
#endif

    /* Likewise fix function vector references to fill the
       hole, essentially shifting all adf references above
       the deleted branch down by one slot.  */
    for (i=0; i<NUM_RPBS; i++) {
        brdel_fix_function_vector(del_brnum, &(child->rpbs[i]));
    }
    for (i=0; i<child->current_number_of_adfs; i++) {
        brdel_fix_function_vector(del_brnum, &(child->adfs[i]));
    }

    /* Rename all calls to adf branches numbered higher than
       the deleted branch. */
    for (i=0; i<NUM_RPBS; i++) {
        for (j=del_brnum+1; j<child->current_number_of_adfs;j++) {
            brdel_rename_refs(&(child->rpbs[i]), j, j-1);
        }
    }
    for (i=0; i<child->current_number_of_adfs; i++) {
        for (j=del_brnum+1; j<child->current_number_of_adfs;j++) {
            brdel_rename_refs(&(child->adfs[i]), j, j-1);
        }
    }

    /* kind of a kludge; this may change: the adf_arity field of the Individual
       needs to be changed to reflect new arrangement.  Copy it from RPB 0
       function vector */
    for (i=0; i<child->current_number_of_adfs; i++)
        child->adf_arity[i] = -1;
    for (i=0; i<child->current_number_of_adfs; i++)
    {
        for (j=0;j<NUM_RPBS;j++)
            if (((int) child->rpbs[j].function_vector[i])>=0)
            {
                child->adf_arity[i] = ((int) child->rpbs[j].function_vector[i]);
                j = NUM_RPBS;
            }
    }

    (child->current_number_of_adfs)--;

    if (ErrorInDude(child))
    {
        gpi_SendError("Error in branch del, operation aborted, child set to parent\n");
        CopyIndividual(parent, child);
        return(1);
    }

    CompressIndividual(child,&tind);
    UnCompressIndividual(&tind,child);
/*
*/
    return 0;
}

/*===============================================================*/
/*=== the following routines support brdel_replace_adf_call() ===*/
/*===============================================================*/

#define BIG_BUFFER_SIZE 4096
static void brdel_replace_adf_call(int brnum, Branch *br)
{
    int             point, endpoint, new_subtree_size;
    int             old_subtree_size, expanded_subtree_size;
    static Fnode    new_subtree_seg[BIG_BUFFER_SIZE];

    /* start at end of tree and work bass-ackwards: this
       guarantees that deepest nested calls will be substituted
       first */
    for (point = TraverseSubtree(br,0); point >= 0; point--) {
        if (br->tree[point].opcode == (brnum)) {
            /* then this is a call to the deleted branch */

            /* compute start and end of segment to be replaced */
            endpoint = TraverseSubtree(br,point);
            old_subtree_size = (endpoint-point)+1;
            expanded_subtree_size = TraverseSubtree(br, 0)+1;