cgp-functions.c

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

			}
			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=num_inputs;i<num_inputs+num_nodes;i++)
      if (!node_used[i])
         num_unused_nodes++;

	num_nodes_active=num_nodes-num_unused_nodes;

	return num_nodes_active;

}

// generate a strating population
// from a chromosome read from a file (cgp.chr)
void read_from_chrom(int** chromosomes)
{
	int	  i,j;
	FILE* fp;

    fp=fopen("cgp.chr","r");
    if (!fp)
    {
		puts("Missing file cgp.chr (contains a chromosome)");
        exit(1);
    }
    else
	{
          // make starting population copies of loaded chromosome
		for (j=0;j<population_size;j++)
        {
			if (j==0)
            {
				i=0;
				do
				{
					fscanf(fp,"%d",&chromosomes[j][i]);
					i++;
				}
				while (!feof(fp));

				if ((i-1)!=num_genes)
				{
					puts("ERROR. Number of genes in cgp.chr does not match the expected number");
					puts("Check the number of genes in the .par file");
					exit(0);
				}
            }
            else
            {
				for (i=0;i<num_genes;i++)
					chromosomes[j][i]=chromosomes[0][i];
            }
        }
		fclose(fp);
	}
}

// This calculates the limits that are used in the claculation
// of allowed gene values (alleles)
void get_gene_limits(int column, int* limit_min, int* limit)//每一列的上下限
{
	int limit_max;

	limit_max=num_inputs+column*num_rows;
	if (column<levels_back)
		*limit_min=0;
	else
		*limit_min=num_inputs+(column-levels_back)*num_rows;

	*limit=limit_max-(*limit_min);
}

// returns a random valid connection gene that
// obeys the constraints imposed by
// levels_back. Also allows program inputs
// to disobey levels_back
int get_connection_gene(int limit_min, int limit)
{
	int limit_plus, rand_num;
	int gene;

	if (limit_min==0)
		gene = newrand(limit);
	else // allows inputs to disobey levels_back
	{
		limit_plus = limit+num_inputs;
		rand_num = newrand(limit_plus);
		if (rand_num<limit)
			gene = rand_num+limit_min;
		else
			gene = rand_num-limit;
	}

	return gene;
}

// returns a random valid function gene 
int get_function_gene(void)
{
	return allowed_functions[newrand(num_functions)];
}

// returns a random valid output gene
int get_output_gene(void)
{
	int limit_min,limit;
	int output_gene;
	
	limit_min=num_inputs+(num_cols-levels_back)*num_rows;
	limit=levels_back*num_rows;

    output_gene = newrand(limit)+limit_min;
	
	return output_gene;
}

// Calculates output of node in 32-bit format
unsigned  node_type(unsigned long in[MAX_NUM_GENES_PER_NODE],
                     unsigned code)
{
   unsigned result;

   if (code==0)      // constants
      result=0;
   else if (code==1)
      result=MAXNUM;
   else if (code==2) // wire and inverter
      result=in[0];
   else if (code==3)
      result=in[1];
   else if (code==4)
      result=~in[0];
   else if (code==5)
      result=~in[1];
   else if (code==6) // two input gate functions
      result=(in[0] & in[1]);
   else if (code==7)
      result=(in[0] & ~in[1]);
   else if (code==8)
      result=(~in[0] & in[1]);
   else if (code==9)
      result=(~in[0] & ~in[1]);
   else if (code==10)
      result=(in[0]^in[1]);
   else if (code==11)
      result=(~in[0]^in[1]);
   else if (code==12)
      result=(in[0] | in[1]);
   else if (code==13)
      result=(in[0] | ~in[1]);
   else if (code==14)
      result=(~in[0] | in[1]);
   else if (code==15)
      result=(~in[0] | ~in[1]);
   else if (code==16)  // mux functions
      result=((in[0] & ~in[2]) | (in[1] & in[2]));
   else if (code==17)
      result=((in[0] & ~in[2]) | (~in[1] & in[2]));
   else if (code==18)
      result=((~in[0] & ~in[2]) | (in[1] & in[2]));
   else if (code==19)
      result=((~in[0] & ~in[2]) | (~in[1] & in[2]));

   return result;
}


// this is the EA fitness function
// it decodes the cgp chromosome
int fitness(int* chromosome)
{
   register int i,k,test;
   unsigned int index,fit,function_type;
   int count;
   unsigned long in[MAX_NUM_GENES_PER_NODE];

   fit=0;

   for (test=0;test<num_tests;test++)
	{
      /* load plu_inputs into output */
      for (i=0;i<num_inputs;i++)
	      output[i]=plu_inputs[test][i];

      count=num_inputs;
      index=0;

	  //process nodes
      for (k=0;k<num_nodes;k++)
      {
         for (i=0;i<num_genes_per_node-1;i++) // get input data to node
            in[i]=output[chromosome[index+i]];

         function_type=chromosome[index+num_genes_per_node-1];
         
         output[count]=node_type(in,function_type);

         count++;

         index=index+num_genes_per_node;
      }
	  // process outputs
      for (i=0;i<num_outputs;i++)
      {
         output[count]=output[chromosome[index]];
         index++;
         count++;
      }
	  
	  /* check how many bits of plu_outputs and bits of calculated outputs agree */
	  count=0;
	  for (i=0;i<num_outputs;i++)
         count=count+invhamming(plu_outputs[test][i],end_count+i);

	  fit=fit+count;
   }

   return fit;
}


// creates initial population of chromosomes
// either having been generated from a single
// chromosome from a file or by generating
// an entire random population
void initialise(int** chromosomes)
{
    int  j,csome,row,col;
	int  count;
    int  limit=0,limit_min=0;

    if (run_from_chrom)
    {
		read_from_chrom(chromosomes);
    }
    else  // generate random population
    {
		for (csome=0;csome<population_size;csome++)
		{
			count=0;
			for (col=0;col<num_cols;col++)
			{
				get_gene_limits(col,&limit_min,&limit);

				for (row=0;row<num_rows;row++)
				{
					//connection genes
					for (j=0;j<num_genes_per_node-1;j++)
						chromosomes[csome][count+j]=get_connection_gene(limit_min,limit);

					// function gene
					chromosomes[csome][count+num_genes_per_node-1]=get_function_gene();
					count=count+num_genes_per_node;
                }
			} 
			for (j=0;j<num_outputs;j++)
				chromosomes[csome][count+j]=get_output_gene();
       } 
    } 
}



// calculate best population fitness and the best chromosome
int  get_best_chromosome(int** chromosomes,
                         int*  best_chromosome)
{
	int	i;
    int	fitness_max;	
    int	best_member,fit;

	fitness_max=-1;
    best_member=0;

    for (i=0;i<population_size;i++)
    {

		fit = fitness(chromosomes[i]);

		// this looks for small circuits if make_efficient is set to 1
        if ((fit==num_bits) && (make_efficient)) 
			fit=fit+num_nodes-get_num_nodes_active(chromosomes[i]);

		if (fit > fitness_max)
		{
			fitness_max = fit;
			best_member = i;
		}

		if (fit==num_bits) // we solved the problem, so stop？？？？
			break;
	}

	// here is the best chromosome
	for (i=0;i<num_genes;i++)
		best_chromosome[i]=chromosomes[best_member][i];

	return fitness_max;
}

// checks to see if the gene is not an output gene
int is_not_output_gene(int gene)
{
	return (gene < num_genes_per_node*num_nodes);
}

// checks to see if the gene is a function gene
int is_function_gene(int gene, int locus)
{
	return (is_not_output_gene(gene) && (locus==(num_genes_per_node-1)));

}

// calculates how many mutations to do per chromosome
int get_num_mutant(int num_genes, double per_cent_mutate)
{
	return (int)(num_genes*per_cent_mutate/100.0);
}

// calculates total number of children that should be produced
int get_num_children(int num_genes, double per_cent_crossover)
{
	return (int)(population_size*per_cent_crossover/100.0);
}

// mutate chromosome
void mutate(int*  chromosome, int num_mutations)
{
	int which_gene,which_locus;
	int limit,limit_min;
	int col;

	which_gene=newrand(num_genes);
	which_locus=which_gene % num_genes_per_node;

	if (is_not_output_gene(which_gene))
	{
		if (is_function_gene(which_gene,which_locus))
		{
			if (num_functions == 1) // redirect the mutation to a connection
			{
				which_locus=newrand(num_genes_per_node-1);
				which_gene=which_gene-num_genes_per_node-1+which_locus;
			}
			chromosome[which_gene]=get_function_gene();
		}
		else // it is a connection gene
		{
			col = which_gene/(num_genes_per_node*num_rows);
			
			get_gene_limits(col,&limit_min,&limit);
				   
			chromosome[which_gene]=get_connection_gene(limit_min,limit);
		}
	}
	else // it is an output gene
	{
		chromosome[which_gene]=get_output_gene();
	}
}



// single point crossover to generate one child
void recombine(int* parent_chromosome1,
			   int* parent_chromosome2,
			   int* child_chromosome,
			   int  crossover_point)
{
	int i,j=0;

	for (i=0;i<crossover_point;i++)
	{
		child_chromosome[j]=parent_chromosome1[i];
		j++;
	}
	for (i=crossover_point;i<num_genes;i++)
	{
		child_chromosome[j]=parent_chromosome2[i];
		j++;
	}

}


// get two randomly chosen but different candidates
void get_candidates(int* candidate1, int* candidate2)
{
	
	*candidate1= newrand(population_size);

	do
	{
		*candidate2=newrand(population_size);
	}
	while (*candidate2 == *candidate1);

}

// hold a tournament and get the winner
int get_tournament_winner(int** chromosomes)
{
	int		i,winner;
	int		candidate1,candidate2;
	int		population_fitness[MAX_NUM_CHROMOSOMES];

	// calculate fitnesses
	for (i=0;i<population_size;i++)
		population_fitness[i] = fitness(chromosomes[i]);

	get_candidates(&candidate1, &candidate2);

	if (population_fitness[candidate1] > population_fitness[candidate2]) 
		winner = candidate1;
	else  
		winner = candidate2;

	return winner;
}

// create a new population by tournamnet selection
void select_new_pop(int** chromosomes,
					int** new_chromosomes)
{
	int		i,j,winner;
	int		candidate1,candidate2;

    for (i=0;i<population_size;i++)
	{
		get_candidates(&candidate1, &candidate2);