cgp-functions.c

进化计算方面：基于图阵列的GP算法。值得进化计算方面的学生学习

// cgp-functions.c  
// Julian F. Miller (c) 2007

// IMPORTANT: program outputs are arranged most significant on the left
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "cgp.h"

// validate cgp program command line and create file strings for .par and .plu files
void validate_command_line(int argc, char* argv[], char parfile[], char plufile[])
{
	puts("");
	puts("*********    WELCOME TO CARTESIAN GENETIC PROGRAMMING      *********"); 
	puts("********* Validating command line arguments to cgp program *********");

	if (argc!=3)
	{
		puts("INCORRECT NUMBER OF ARGUMENTS");
		puts("Type cgp <file.par> <file.plu> then return");
		exit(1);
	}


	if (strlen(argv[1])>(MAX_NUM_LETTERS-1))
	{
   		puts("filename for parameter file is too long");
		printf("It should be less than %d characters\n",MAX_NUM_LETTERS);
		exit(2);
	}
	//strcpy(parfile,argv[1]);
	//strcpy(plufile,argv[2]); 

	if (strlen(argv[2])>(MAX_NUM_LETTERS-1))
	{
   		puts("filename for plu file is too long");
		printf("It should be less than %d characters\n",MAX_NUM_LETTERS);
		exit(3);
	}
	strcpy(parfile,argv[1]);
	strcpy(plufile,argv[2]); 

}

// read from the parameter file all the global parameters
void get_parameters(char parfile[],char plufile[])
{
	int		i;
	char	dummy[50];
	FILE*	fp;

	printf("\n********* Reading parameters defined in %s *********\n",parfile);
	fp=fopen(parfile,"r");
	if (!fp)
	{
		printf("Missing file: %s\n",parfile);
		exit(1);
	}
	fscanf(fp,"%d %s",&population_size,dummy);
	fscanf(fp,"%lf %s",&per_cent_mutate,dummy);
	fscanf(fp,"%lf %s",&per_cent_crossover,dummy);
	fscanf(fp,"%d %s",&num_generations,dummy);
	fscanf(fp,"%d %s",&num_runs_total,dummy);
	fscanf(fp,"%d %s",&num_rows,dummy);
	fscanf(fp,"%d %s",&num_cols,dummy);
	fscanf(fp,"%d %s",&levels_back,dummy);
	fscanf(fp,"%d %s",&progress_report,dummy);
	fscanf(fp,"%d %s",&report_interval,dummy);
	fscanf(fp,"%u %s",&global_seed,dummy);
	fscanf(fp,"%d %s",&ea_type,dummy);
	fscanf(fp,"%d %s",&mu,dummy);
	fscanf(fp,"%d %s",&elitism,dummy);
	fscanf(fp,"%d %s",&save_best_chrom,dummy);
	fscanf(fp,"%d %s",&run_from_chrom,dummy);
	fscanf(fp,"%d %s",&make_efficient,dummy);
	// assigned global constants
	num_functions=0;
	num_genes_per_node=3;//规定每个节点的表示维数

	for (i=0;i<MAX_NUM_FUNCTIONS;i++)//共有20个可选函数
	{
		fscanf(fp,"%d %s",&number[i],&node_types[i]);
		if (number[i])
		{
			allowed_functions[num_functions]=i;
			num_functions++;//可以用的函数 数目1表示可用
			if (i>15)
				num_genes_per_node=4;//后面四个函数为MUX类型
		}
	}
	fclose(fp);

	read_plu(plufile);//返回ni，no,num_nodes....output[];


	if (population_size > MAX_NUM_CHROMOSOMES)
	{
		printf("Too large a population size (<= %d)\n",MAX_NUM_CHROMOSOMES);
		exit(0);
	}

	if (num_genes > MAX_NUM_GENES)
	{
		printf("Too many genes selected (<= %d)\n",MAX_NUM_GENES);
		exit(0);
	}

	if (num_runs_total < 1)
	{
		puts("Number of runs of EA must be at least 1");
		exit(0);
	}
	else if (num_runs_total > MAX_NUM_RUNS)
	{
		printf("Number of runs of EA must be less than %d\n", MAX_NUM_RUNS);
		exit(0);
	}

	if (num_genes < 10)
	{
		puts("Number of genes/bits must be at least 10");
		exit(0);
	}

	if ((progress_report< 0) || (progress_report > 1))
	{
		puts("Progress report parameter must be 0 or 1");
		exit(0);
	}

	if ((ea_type< 0) || (ea_type > 3))
	{
		puts("ea type parameter must be 0 or 1");
		exit(0);
	}

	if ((mu < 1) || (mu > population_size))
	{
		puts("mu (number of parents) must be greater than 1 and not greater than the populations size");
		exit(0);

	}

	srand(global_seed);

	puts("********* Beginning execution *********");
}

// write out parameter values in results file
void write_cgp_info(char command[],char plufile[])
{
	int		i;
	FILE*	fp;

	fp=fopen("cgp.txt","w");
	fprintf(fp,"The program is        %s\n",command);
	fprintf(fp,"The plu file is       %s\n",plufile);
	fprintf(fp,"population_size is    %d\n",population_size);
	fprintf(fp,"mutation rate is      %6.2lf\n",per_cent_mutate);
	fprintf(fp,"crossover rate is     %6.2lf\n",per_cent_crossover);
	fprintf(fp,"num_generations is    %d\n",num_generations);
	fprintf(fp,"num_runs is           %d\n",num_runs_total);
	fprintf(fp,"num_rows is           %d\n",num_rows);
	fprintf(fp,"num_cols is           %d\n",num_cols);
	fprintf(fp,"levels_back is        %d\n",levels_back);
	fprintf(fp,"progress report is    %d\n",progress_report);
	fprintf(fp,"report interval is    %d\n",report_interval);
	fprintf(fp,"global_seed is        %u\n",global_seed);
	fprintf(fp,"ea type is            %d\n",ea_type);
	fprintf(fp,"mu is                 %d\n",mu);
	fprintf(fp,"elitism is            %d\n",elitism);
	fprintf(fp,"save_best_chrom is    %d\n",save_best_chrom);
	fprintf(fp,"run_from_chrom is     %d\n",run_from_chrom);
	fprintf(fp,"make_efficient is     %d\n",make_efficient);
	for (i=0;i<MAX_NUM_FUNCTIONS;i++)
	{
		fprintf(fp,"%d %s\n",number[i],node_types[i]);
	}
	fprintf(fp,"\nHere are the Results\n");
	fclose(fp);
}


// counts number of bits that a and output[addr] have in common
// a is passed in as the truth table outputs and output[addr]
// holds the evolved circuit outputs
unsigned int invhamming(unsigned long a,int addr)//?不解
{
   register int		i;
   unsigned			result=0;
   unsigned long	temp;

   temp=~a^output[addr];
   output[addr]=0; //reset the output to zero
   for (i=0;i<bit_width;i++)
      result=result+getbit(temp,i);
   return result;
}

//  returns a random integer between 0 and range-1
int newrand(int range)
{
    int temp;

    temp=rand() % range;
    return(temp);
}

// reads the truth table as a .plu file (compressed truth table)
// also calculates some program globals
void read_plu(char plufile[])
{
    int		i,j;
    char	dummy[MAX_NUM_LETTERS];
    FILE*	fp;

    fp=fopen(plufile,"r");
    if (!fp)
    {
        puts("ERROR. Missing .plu file");
        exit(1);
    }
    else
    {
       fscanf(fp,"%s %d",dummy,&num_inputs);//输入个数ni
       fscanf(fp,"%s %d",dummy,&num_outputs);//输出连接数no
       fscanf(fp,"%s %d",dummy,&num_products);//？？？
       for (i=0;i<num_products;i++)
       {
          for(j=0;j<num_inputs;j++)
              fscanf(fp,"%u", &plu_inputs[i][j]);
          for(j=0;j<num_outputs;j++)
				  fscanf(fp,"%u", &plu_outputs[i][j]);
		 }
       fclose(fp);

    }

	num_tests=num_products;

	// assigned global constants
	num_nodes=num_rows*num_cols;
    num_genes=num_genes_per_node*num_nodes+num_outputs;
    end_count=num_inputs+num_nodes;

    for (i=0;i<end_count+num_outputs;i++)
       output[i]=0;

    num_bits=pow2(num_inputs)*num_outputs;

    if (num_inputs==2)
       bit_width=4;
    else if (num_inputs==3)
       bit_width=8;
    else if (num_inputs==4)
       bit_width=16;
    else
       bit_width=32;

}

// prints a chromosome to a file
void fprint_a_chromosome(int* chromosome, char name[], int append)
{
   int		i;
   FILE*	fp;

   if (append)
	   fp=fopen(name,"a");
   else
	   fp=fopen(name,"w");
   for (i=0;i<num_nodes*num_genes_per_node;i++)
   {
      if ((i+1)%num_genes_per_node == 0)
         fprintf(fp," %d\t",chromosome[i]);
      else
         fprintf(fp," %d",chromosome[i]);
   }
   fprintf(fp,"\t");
   for (i=0;i<num_outputs;i++)
      fprintf(fp," %d",chromosome[num_nodes*num_genes_per_node+i]);
   fprintf(fp,"\n\n");
   fclose(fp);
}

// prints a chromosome to the screen
void print_a_chromosome(int* chromosome)
{
   int i;

   for (i=0;i<num_nodes*num_genes_per_node;i++)
   {
      if ((i+1)%num_genes_per_node == 0)
         printf(" %d\t",chromosome[i]);
      else
         printf(" %d",chromosome[i]);
   }
   printf("\t");
   for (i=0;i<num_outputs;i++)
      printf(" %d",chromosome[num_nodes*num_genes_per_node+i]);
   printf("\n");
}


// prints out a chromosome showing inactive genes as -1
void fprint_active_genes(int* chromosome,char name[30])
{
	int		i,j,index;
	int		num_unused_nodes=0;
	int		num_nodes_active;
	int		node_used[MAX_OUTPUT_SIZE];
	int*	active_chromosome = NULL;
	int		address[MAX_NUM_GENES_PER_NODE];
	FILE*	fp;


	active_chromosome = create_chromosome_space();

	fp=fopen(name,"a");
	for (i=0;i<num_genes;i++)
		active_chromosome[i]=-1;
	for (i=num_genes-num_outputs;i<num_genes;i++)
		active_chromosome[i]=chromosome[i];

	/* first look at chromosome and identify gates not used */
	/* these are all the outputs of gates which do not appear in the chromosome */
	for (i=0;i<num_nodes+num_inputs;i++)
		node_used[i]=0;
	// all the nodes whose output is given by the output genes are active
	for (i=num_genes-num_outputs;i<num_genes;i++)
		node_used[chromosome[i]]=1;

	for (i=num_nodes+num_inputs-1;i>=num_inputs;i--)
	{
		if (node_used[i])
		{
			/* get input addresses and type of this gate */
			index=num_genes_per_node*(i-num_inputs);
			for (j=0;j<num_genes_per_node;j++)
			{
				address[j]=chromosome[index+j];
				active_chromosome[index+j]=address[j];
			}
			if ((address[num_genes_per_node-1]==2) || (address[num_genes_per_node-1]==4))
			{
				node_used[address[0]]=1;
			}
			else if ((address[num_genes_per_node-1]==3) || (address[num_genes_per_node-1]==5))
			{
				node_used[address[1]]=1;
			}
			else if ((address[num_genes_per_node-1]>=6) && (address[num_genes_per_node-1]<=15))
			{
				node_used[address[0]]=1;
				node_used[address[1]]=1;
			}
			else if (address[num_genes_per_node-1]>15)
			{
				node_used[address[0]]=1;
				node_used[address[1]]=1;
				node_used[address[2]]=1;
			}
		}
	}

   for (i=0;i<num_nodes*num_genes_per_node;i++)
   {
	   if ((i+1)%num_genes_per_node == 0)
	   {
		   if (active_chromosome[i]<0)
			   fprintf(fp,"%d\t",active_chromosome[i]);
		   else
			   fprintf(fp," %d\t",active_chromosome[i]);
	   }
	   else
	   {
	     if (active_chromosome[i]<0)
			fprintf(fp,"%d",active_chromosome[i]);
		 else
			fprintf(fp," %d",active_chromosome[i]);
	   }
   }
   fprintf(fp,"\t");
   for (i=0;i<num_outputs;i++)
      fprintf(fp," %d",active_chromosome[num_nodes*num_genes_per_node+i]);
   
   for (i=num_inputs;i<num_inputs+num_nodes;i++)
	   if (!node_used[i])
		   num_unused_nodes++;
   num_nodes_active=num_nodes-num_unused_nodes;

   fprintf(fp,"\nnumber of active gates is %d\n\n",num_nodes_active);
   fclose(fp);

   free(active_chromosome);
}

// this routine works out how many nodes are active
int get_num_nodes_active(int* chromosome)
{
	int   i,j,index;
    int   address[MAX_NUM_GENES_PER_NODE];
	int   num_unused_nodes=0,num_nodes_active;
	int   node_used[MAX_OUTPUT_SIZE];

	/* first look at chromosome and identify gates not used
	   these are all the outputs of gates which 
	   do not appear in the chromosome */

	for (i=0;i<num_nodes+num_inputs;i++)
		node_used[i]=0;
	// all the nodes whose output is given by the output genes are active
	for (i=num_genes-num_outputs;i<num_genes;i++)
		node_used[chromosome[i]]=1;

	for (i=num_nodes+num_inputs-1;i>=num_inputs;i--)
	{

		if (node_used[i])
		{
			// get input addresses and type of this gate 
			index=num_genes_per_node*(i-num_inputs);
			for (j=0;j<num_genes_per_node;j++)
				address[j]=chromosome[index+j];

			if ((address[num_genes_per_node-1]==2) || (address[num_genes_per_node-1]==4))
			{
				node_used[address[0]]=1;
			}
			else if ((address[num_genes_per_node-1]==3) || (address[num_genes_per_node-1]==5))
			{
				node_used[address[1]]=1;
			}
			else if ((address[num_genes_per_node-1]>=6) && (address[num_genes_per_node-1]<=15))
			{
				node_used[address[0]]=1;
				node_used[address[1]]=1;