lang.c

遗传规划工具

/*	pgpc -- Parallel Genetic Programming in C
            written by David Andre
	 Copyright c 1995, Genetic Programming Institute?
                    Genetic Algorithms Technology Corporation
		All rights reserved.
		v1.1 May 9th, 1994
 	ep05.c  */

/********************************************************************/
/*  INCLUDE FILES -- SHOULD NOT CHANGE  */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

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


#include "gp.h"
#include "proto.h"

void gpi_SendError(char *str);          /*funcdef*/
/********************************************************************/
/* NECESSARY GLOBAL VARIABLES  -- SHOULD NOT CHANGE*/
Individual * CurrentDude;
FitCaseInfo fitness_cases[MAX_NUM_FIT_CASES];
GlobalFitCaseInfo global_fitness_case_info;
extern long int seed;
static char str[256];
int dind;
Population * ppop;

/********************************************************************/
/*this shouldn't change*/
/* INCLUDE THE FILE CONTAINING THE CreateFitnessCases function,
    if we are under borland */
/*#ifdef __BORLANDC__*/
#include _PRB_CFC
/*#endif*/

/********************************************************************/
/* USER SPECIFIED VARIABLES -- CAN BE CHANGED                       */
/********************************************************************/
int next_node_num;
TableType table[MAX_NUM_ADFS];
int active_node;
int active_arc;
int ready;
int stack[STACK_SIZE];
int stack_index;
int jump_index;
TableType *active_table;

#define get_transition(tbl, old_state, input) (((tbl).state[old_state]).trans[input])
void PrintAutomata();

void split(Branch *br, int action);
void CreateTable(Branch* br);
void EvalTable(int *string, int length);
void Test();

/********************************************************************/
/*NECESSARY PROBLEM SPECIFIC FUNCTIONS -- USER CAN CHANGE*/
/*Function that returns the maximum size of the branch passed to it,
in terms of the number of nodes*/

int GetBranchSize(int brn)/*;*/ /*funcdef - problem - GetBranchSize*/
{

switch (brn) {
    case 0: return(NODES_PER_RPB);
    case 1:
    case 2:
    case 3: return(NODES_PER_ADF);
    default:
        #ifdef _ICC
            __asm{seterr;};
        #else
            printf("Error in getbranchsize\n");
            exit(1);
        #endif
    }

}

/*Function returns the weight of the given branch for weighted branch crossover*/

int GetBranchWeight(int brn)/*;*/ /*funcdef*/
{
switch(brn) {
    case 0:
        return(1);
    case 1:
    case 2:
    case 3:
        return(1);
    default:
        return(1);
  }
}

/********************************************************************/
/* Can be used to print extra information about the best individual, by
    using the extra_ints and extra_floats structures    */
void PrintProblemSpecificInfo(FILE * fp, Population * pop) /*;*/ /*funcdef*/
{
#ifndef _ICC

    fprintf(fp,"\n");

#endif
}

/********************************************************************/
/* Called at the nodes if any pointer re-initialization needs to be done */
void InitFitnessCases(Population * pop)
{

}

/********************************************************************/
/* Used to create any random constants -- must match name in <prob>.h */
/*
float make_RandomFloat()
{
    return((float) ((float)0.001 + (float) RandomFloat((float) 2.0)));
}*/

int make_RandomInt()
{
    return((int) ((int) RandomInt(20)));
}



/********************************************************************/
/* DEFINITIONS OF GP FUNCTIONS*/

/*  Each must start with a _start_def_func, and end with a
    _end_def_func, and can use the _eval_subtree macro, the
    _skip_subtree macro, the _eval_args macro, etc */


/************************* Creation Functions ***************************/

void split(Branch *br, int action) {
    int child;
    int parent;
    int i, j;
    StateInfo *child_ptr, *parent_ptr, *sister_ptr;

    #if (STRACE)
        printf("SPLIT - new node = %d\n", next_node_num);
    #endif

    /* start cut here */
    if (!ready) {
        ready = 1;
        active_node = 0;
        for (j = 0; j < NUM_INPUTS; j++) {
            (*active_table).state[0].trans[j] = 0;
        }
        (*active_table).state[0].action = action;

        /*Eval Subtrees*/
        active_arc = ARC_A;
        _eval_subtree(br,ppop);
        active_arc = ARC_B;
        _eval_subtree(br,ppop);

        return;
     }
    /* end cut here */

    parent = active_node;
    child  = next_node_num;
    next_node_num++;
    active_node = child;

    parent_ptr = &((*active_table).state[parent]);
    child_ptr = &((*active_table).state[child]);
    sister_ptr = &((*active_table). state[((*parent_ptr).trans[active_arc])]);

    for (i = 0; i < NUM_INPUTS; i++) {
        (*child_ptr).trans[i] =
            (*sister_ptr).trans[i];
    }
    (*child_ptr).action = action;

    for (j = active_arc; j < NUM_INPUTS; j++) {
        (*parent_ptr).trans[j] = child;
    }
    /*Eval Subtrees*/
    active_arc = ARC_A;
    _eval_subtree(br,ppop);
    active_arc = ARC_B;
    _eval_subtree(br,ppop);

    active_node = parent;

}

_start_def_func(splitA)
    split(br, ACTION_ACCEPT);
    return((GTYPE) 1);
_end_def_func(splitA)

_start_def_func(splitR)
    split(br, ACTION_REJECT);
    return((GTYPE) 1);
_end_def_func(splitR)


_start_def_func(retract)
    if (ready)
        (*active_table).state[active_node].trans[active_arc] = active_node;
    _eval_subtree(br,ppop);
    return((GTYPE) 1);
_end_def_func(retract)

_start_def_func(done)
    return((GTYPE) 1);
_end_def_func(done)


_start_def_func(write_node)
    if ((stack_index < STACK_SIZE - 1) && ready) {
        stack[stack_index++] = active_node;
    }
    _eval_subtree(br,ppop);
    return((GTYPE) 1);
_end_def_func(write_node)

_start_def_func(to_node)
    if ((stack_index > 0) && ready) {
        (*active_table).state[active_node].trans[active_arc] = stack[stack_index];
        stack_index--;
    }
    _eval_subtree(br,ppop);
    return((GTYPE) 1);
_end_def_func(to_node)



_start_def_func(pops)
    if ((stack_index > 0) && ready) {
        stack_index--;
    }
    _eval_subtree(br,ppop);
    return((GTYPE) 1);
_end_def_func(pops)


_start_def_func(dec)
    if ((jump_index > 0) && ready) {
        jump_index--;
    }
    _eval_subtree(br,ppop);
    return((GTYPE) 1);
_end_def_func(dec)

_start_def_func(reset)
    jump_index = stack_index;
    _eval_subtree(br,ppop);
    return((GTYPE) 1);
_end_def_func(reset)


_start_def_func(jump)
    if ((jump_index > 0) && ready) {
        if (jump_index > stack_index)
            (*active_table).state[active_node].trans[active_arc]
                = stack[stack_index];
        else
            (*active_table).state[active_node].trans[active_arc]
                = stack[jump_index];
    }
    _eval_subtree(br,ppop);
    return((GTYPE) 1);
_end_def_func(jump)



/*********************** BOOLEAN FUNCTIONS **************************/

_start_def_func(jand)
    if (_eval_subtree(br,ppop))
    {
        return(_eval_subtree(br,ppop));
    }
    else
    {
        _skip_subtree(br);
        return((GTYPE) 0);
    }
_end_def_func(jand)

_start_def_func(jor)
    if (_eval_subtree(br,ppop))
    {
        _skip_subtree(br);
        return((GTYPE) 1);
    }
    else
    {
        return(_eval_subtree(br,ppop));
    }
_end_def_func(jor)

_start_def_func(jnot)
    return(!(_eval_subtree(br,ppop)));
_end_def_func(jnot)



/********************************************************************/
/* MORE STABLE FUNCTIONS __ OFTEN WILL NOT BE CHANGED BY USER */

/*This function is called when a random constant is evaluated*/
GTYPE random_func(Branch * br)
{
    br->ind->index_ptr++;
    return((GTYPE) (*ppop).constants[(int) br->tree[br->ind->index_ptr].opcode]);
}

GTYPE adf(Branch * br)
{
    int opcode;

    opcode = br->tree[br->ind->index_ptr].opcode;
    (br->ind->index_ptr)++;

    return(table[opcode].result);
}

GTYPE adf_arg(Branch * br)
{
    return( ((*ppop).pop_globals.g_arg)[( (br->tree[(br->ind->index_ptr++)].opcode) -
                                                MAX_NUM_ADFS) ]);
}

/********************************************************************/
/*This function sets up the function sets and declares the
functions.  The first 4 lines should always be there.*/

void 	MakeFunctionTable(Population * pop) /*;*//*funcdef*/
{
               _init_make_function_table_vars;
	       _init_make_function_table;

/*DECLARATIONS OF ADFS -- (MUST COME FIRST, IF ANY) */
                            /*name*/   /*code*/ /*weight*/
                           /*------------------------------*/
                _declare_adf(adf0,    adf,        1     );
                _declare_adf(adf1,    adf,        1     );
                _declare_adf(adf2,    adf,        1     );


/*DECLARATIONS OF DUMMY ARGS -- (MUST COME SECOND, IF ANY) */
                            /*name*/    /*code*/    /*weight*/
                           /*-----------------------------------*/


/*DECLARATIONS OF REGULAR FUNCTIONS -- COMES AFTER ADFS AND DUMMY_ARGS*/

                             /*code   arity     macro?    weight  printname*/
                           /*----------------------------------------------*/
                _declare_func(jand,     2,       1,        1,     and);
                _declare_func(jor,      2,       1,        1,     or);
                _declare_func(jnot,     1,       1,        1,     not);

                _declare_func(splitA,   2,       1,        1,     splitA);
                _declare_func(splitR,   2,       1,        1,     splitR);

                _declare_func(retract,  1,       1,         1,     retract);
                _declare_func(write_node, 1,     1,         1,     write_node);
                _declare_func(to_node,  1,       1,         1,     to_node);
		/*      _declare_func(pops,  1,       1,         1,     pops);
                _declare_func(dec,  1,       1,         1,     dec);
                _declare_func(reset,  1,       1,         1,     reset);
                _declare_func(jump,  1,       1,         1,     jump);
		*/
                _declare_func(done,     0,       0,         1,     done);
                                                		
/*DECLARATION OF THE RANDOM FUNCTION,  MUST ALWAYS be included! _declare_random(weight)*/

                _declare_random(1);

/*DEFINITION OF FUNCTION SETS FOR EACH BRANCH. */
		/*The following now specifies the INITIAL function_vectors*/
                /*THE RPBs come first, then the ADFs*/

                branchnum =0;
                _start_def_func_set_for_branch(branchnum);
                _use_adf(branchnum, "adf0",0);
                _use_adf(branchnum,"adf1",0);
                _use_adf(branchnum,"adf2",0);
                _use_func(branchnum,"and");
                _use_func(branchnum,"or");
                _use_func(branchnum,"not");

                for (branchnum = 1; branchnum <= MAX_NUM_ADFS; branchnum++) {
                    _start_def_func_set_for_branch(branchnum);
                    _use_func(branchnum,"splitA");
                    _use_func(branchnum,"splitR");
                    _use_func(branchnum,"retract");
                    _use_func(branchnum,"write_node");
                    _use_func(branchnum,"to_node");
		    /*     _use_func(branchnum,"pops");
                    _use_func(branchnum,"dec");
                    _use_func(branchnum,"reset");
                    _use_func(branchnum,"jump"); */
                    _use_func(branchnum,"done");
                }
}

/********************************************************************/

/* Evaluation of Individual*/


void PrintAutomata() {
    int i, j;

    printf("TRANSITION TABLE\n");
    printf("----------------\n");
    printf("\ta\tb\n");
    printf("\t-\t-\n");
    for (i = 0; i < next_node_num; i++) {
        printf("%d\t", i);
        for ( j = 0; j < NUM_INPUTS; j++) {
            printf("%d\t", (*active_table).state[i].trans[j]);
        }
        printf("\n");
    }

    printf("\n\nACCEPTING STATES:   ");
    for (i = 0; i < next_node_num; i++) {
        if ((*active_table).state[i].action == ACTION_ACCEPT) {
            printf("%d  ", i);
        }
    }
    printf("\n\n");
}



/* Faster EVAL */

int EvalFitnessOfDude(Individual * ind,Population *pop)
{
    int sum;
    Branch * brs;
    FitCaseInfo *current_case;
    FitCaseInfo *last_case = &(fitness_cases[MAX_NUM_FIT_CASES - 1]);
    int result;
    TableType *last_table = &table[MAX_NUM_ADFS - 1];
    int table_num;

    CurrentDude = ind;
    sum = 0;
    ppop = pop; 	

    PrintIndividual(ind, stdout);
/*    Test();*/

    /* Create Transition Tables */
    for (table_num = 0; table_num < MAX_NUM_ADFS; table_num++) {
        active_table = &table[table_num];
        CreateTable(&ind->adfs[table_num]);
        PrintAutomata();
    }


    for (current_case = &(fitness_cases[0]); current_case <= last_case;
                            current_case++) {
        for (active_table = &table[0]; active_table <= last_table; active_table++) {
            EvalTable((*current_case).string, (*current_case).length);
        }

        result = EvalBranch(ind->rpbs,pop);	
        if ((*current_case).valid) {
            if (result) sum++;
        }
        else {
            if (!result) sum++;
        }
    }

    ind->hits = sum;
    ind->s_fitness = (float) (MAX_NUM_FIT_CASES - sum);
}



void CreateTable(Branch* br) {
    stack_index = 0;
    jump_index = 0;
    ready = 0;
    next_node_num = 1;

    (br->ind->index_ptr) = 0;
    _eval_subtree(br ,ppop);
}


void EvalTable(int *string, int length) {
    int *last_input;
    int *input;
    int current_state = 0;

    last_input = &(string[length - 1]);
    for (input = &(string[0]); input <= last_input; input++) {
            current_state = get_transition(*active_table, current_state, *input);
            /*printf("current state = %d\n", current_state);*/
        }

    (*active_table).result = (*active_table).state[current_state].action;
}



void Test() {
    int i, j;

    for (i = 0; i < MAX_NUM_ADFS; i++) {
        for (j = 0; j < MAX_NUM_STATES; j++) {
            table[i].state[j].action = 1;
        }
    }
}