cgp-functions.c

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

		winner = get_tournament_winner(chromosomes);
		
		for (j=0;j<num_genes;j++)
			new_chromosomes[i][j]=chromosomes[winner][j];
	}
}

// Generate new population with crossover and mutation
// using generational evolutionary algorithm
void generate_new_pop_ga(int** chromosomes,
						 int* best_chromosome,
						 int elitism)
{
	int		i,j;
    int		num_children,num_mutant;
	int		parent1,parent2,crossover_point;
	int**	new_chromosomes;
	
	new_chromosomes = create_2dchromosome_space();

    num_mutant= get_num_mutant(num_genes,per_cent_mutate);
	num_children=get_num_children(num_genes,per_cent_crossover);

	get_best_chromosome(chromosomes,best_chromosome);

	select_new_pop(chromosomes,new_chromosomes);

	// apply crossover to generate some children
    for (i=0;i<num_children;i++)
	{
		crossover_point = 1 + newrand(num_genes-2); // crossover point generated at random
		get_candidates(&parent1,&parent2);
	    recombine(new_chromosomes[parent1],new_chromosomes[parent2],chromosomes[i],crossover_point);
	}

	// copy over remaining parents
	for (i=num_children;i<population_size;i++)
		for (j=0;j<num_genes;j++)
			chromosomes[i][j]=new_chromosomes[i][j];

	// mutate each chromosome
	for (i=0;i<population_size-1-elitism;i++)
    {
		//mutate each chromosome
		mutate(chromosomes[i],num_mutant);
    }

	// do elitism if required
	if (elitism)
		for (i=0;i<num_genes;i++)
			chromosomes[population_size-1][i]=best_chromosome[i];

	free_chromosomes(new_chromosomes);
}

// (1+lambda evolutionary strategy where lamda = population size -1
// This defines the EA algorithm
// note that using mu=1 and lambda = population_size -1
// should give the same.
void generate_new_pop_es(int** chromosomes,
						 int*  best_chromosome)
{
	int j,k;
	int num_mutant;

	num_mutant=get_num_mutant(num_genes,per_cent_mutate);

     // copy best_chromosome into last member of chromosome array
    for (j=0;j<num_genes;j++)
       chromosomes[population_size-1][j]=best_chromosome[j];

     // generate new population by mutating all but last
    for (k=0;k<population_size-1;k++)
    {
       for (j=0;j<num_genes;j++) // copy best chromosome
          chromosomes[k][j]=best_chromosome[j];

       for (j=0;j<num_mutant;j++)
       {
		   //mutate the chromosome
		   mutate(chromosomes[k], num_mutant);
       }
    }
}

// from pseudo code available at wikipedia
// insertion sort is highly efficient for small
// list of things to sort, and
// we don't expact to use a arge population
void insertion_sort(int Fit[], int** chromosomes)
{
  int  i, j, value;
  int* chrom;

  for (i=1; i < population_size; i++)
  {
    value = Fit[i];
	chrom = chromosomes[i];
    j = i-1;
	// IMPORTANT NOTE: This is usually Fit[j] > value
	// The equality means that the sort swaps
	// ones that are equal which means that
	// low index chromosomes that are as good as
	// the best will be moved to a higher index
	// this makes sure that the newest chromosomes
	// are chosen provided they are as good as the best
    while ((j >= 0) && (Fit[j] >= value))
    {
		Fit[j+1] = Fit[j];
		chromosomes[j+1] = chromosomes[j];
		j = j - 1;
    }
    Fit[j+1] = value;
	chromosomes[j+1] = chrom;
  }
}


// calculate best population fitness and the best chromosome
void  sort_chromosomes_by_fitness(int** chromosomes)
{
	int		i;
	int     Fit[MAX_NUM_CHROMOSOMES];

    for (i=0;i<population_size;i++)
    {
		Fit[i] = fitness(chromosomes[i]);

		// this tries to small circuits if make_efficient is set to 1
		// it does this by adding the number of UNUSED nodes to the fitness
		// score but only if the fitness of the circuit is perfect
		// i.e. it implements the desired function
        if ((Fit[i]==num_bits) && (make_efficient)) 
			Fit[i]=Fit[i]+num_nodes-get_num_nodes_active(chromosomes[i]);
	}
	insertion_sort(Fit,chromosomes);
}


// (mu+lambda) evolutionary strategy 
// new population formed from mu best parents and population_size - mu offspring
// So the mu parents are copied across unchanged
// I don't keep a record of the fitnesses of these which is inefficient
// as I calcuate their fitnesses all over again in the next population!!!!
void generate_new_pop_es_mu_plus_lambda(int** chromosomes, int *best_chromosome, int mu)
{
	int		i=0,j,k;
	int		num_mutant,parent;

	num_mutant=get_num_mutant(num_genes,per_cent_mutate);

	// find mu best parents. First sort the population by fitness
	// the best ones have the highest index: ascending order
	sort_chromosomes_by_fitness(chromosomes);
	
     // get best_chromosome
    for (j=0;j<num_genes;j++)
       best_chromosome[j]= chromosomes[population_size-1][j];

     // generate new population by mutating all but best mu
    for (k=0;k<population_size-mu;k++)
    {
		//get a parent chromosomes from the pool of mu parents
		parent = population_size - mu + newrand(mu);
		for (j=0;j<num_genes;j++) // copy best chromosome
			chromosomes[k][j]=chromosomes[parent][j];
		
		for (j=0;j<num_mutant;j++) //mutate the chromosome	
			mutate(chromosomes[k], num_mutant);
    }
}

// (mu,lambda) evolutionary strategy 
// new population formed by mutating
// the mu best parents and to form the new population_size
void generate_new_pop_es_mu_comma_lambda(int** chromosomes, int* best_chromosome, int mu)
{
	int		i=0,j,k;
	int		num_mutant,parent;

	num_mutant=get_num_mutant(num_genes,per_cent_mutate);

	// find mu best parents. First sort the population by fitness
	// the best ones have the highest index: ascending order
	sort_chromosomes_by_fitness(chromosomes);

	// get best_chromosome
    for (j=0;j<num_genes;j++)
		best_chromosome[j]= chromosomes[population_size-1][j];


     // generate new population by mutatiing copies of parents (chosen at random)
    for (k=0;k<population_size-mu;k++)
    {
		//get a parent chromosomes from the pool of mu parents
		parent = population_size - mu + newrand(mu);
		for (j=0;j<num_genes;j++) // copy best chromosome
			chromosomes[k][j]=chromosomes[parent][j];
		
		for (j=0;j<num_mutant;j++) //mutate the chromosome	
			mutate(chromosomes[k], num_mutant);
    }
	// now mutate the parents
    for (k=population_size-mu;k<population_size;k++)
    {		
		for (j=0;j<num_mutant;j++) 	
			mutate(chromosomes[k], num_mutant);
    }

}

// allocate space for population of chromosomes
int** create_2dchromosome_space(void)
{
	int i;
	int **chromosomes = NULL;

	chromosomes=(int** )calloc(population_size,sizeof(int*)); // create space for pointers to int pointers
	if (chromosomes==NULL)
	{
       printf("ERROR.Can not allocate space for this many chromosome pointers\n");
       exit(0);
	}
	
	for (i=0;i<population_size;i++) // create array of pointers to ints (genes)
	{
	  chromosomes[i] = create_chromosome_space();
      if (chromosomes[i]==NULL)
      {
         printf("ERROR.Not enough memory for chromosomes of this length\n");
         exit(0);
      }
   }

	return chromosomes;
}

// allocate space for a single chromosome
int* create_chromosome_space(void)
{
	int* chromosome = NULL;
	
	chromosome=(int*)calloc(num_genes,sizeof(int));
    if (chromosome==NULL)
    {
		printf("ERROR.Not enough memory for a chromosome of this length\n");
        exit(0);
    }
	return chromosome;
}


// release memory
void free_chromosomes(int** chromosomes)
{
	int i;

	for (i=0;i<population_size;i++)
		free(chromosomes[i]);		
	free(chromosomes);
}


// Do a run of the EA
int  EA(int* best_gen, int* num_nodes_active, int run, 
		char prog[MAX_NUM_LETTERS], char stat[MAX_NUM_LETTERS])
{
	int		gen_index;
	int		best_fit=0, previous_best_fit=0;
	int**	chromosomes;
	int*	best_chromosome;
	FILE*	fp;

	chromosomes = create_2dchromosome_space();
	best_chromosome = create_chromosome_space();

	initialise(chromosomes);

	for (gen_index=1;gen_index<=num_generations;gen_index++)
	{
		if (gen_index % report_interval==0)
			printf("\nGENERATION is %d",gen_index);

		// find new best chromosome and its fitness
		best_fit = get_best_chromosome(chromosomes,best_chromosome);

		if (best_fit > previous_best_fit) // we have an improvement
		{
      		if (progress_report)
			{
         		fp=fopen(prog,"a");
         		printf("\nGENERATION is %u Best fitness is now %d",gen_index,best_fit);
         		fprintf(fp,"\nGENERATION is %u     Best fitness is now %d",gen_index,best_fit);
         		fprintf(fp,"\nThe chromosome is\n");
         		fclose(fp);
         		fprint_a_chromosome(best_chromosome,prog,1);
				fprint_active_genes(best_chromosome,prog);

				fp=fopen(stat,"a");
				fprintf(fp,"%d\t%d\n",gen_index,best_fit);
				fclose(fp);
			}
			*best_gen = gen_index;
			previous_best_fit = best_fit;
		}

		if (best_fit == num_bits) // jump out of run as maximum fitness acheived
		{
			break;
			gen_index++;
		}
		else
		{
			switch (ea_type)
			{
				case 0:
					generate_new_pop_ga(chromosomes,best_chromosome,elitism);
					break;
				case 1:
					generate_new_pop_es(chromosomes,best_chromosome);
					break;
				case 2:
					generate_new_pop_es_mu_plus_lambda(chromosomes,best_chromosome,mu);
					break;
				case 3:
					generate_new_pop_es_mu_comma_lambda(chromosomes,best_chromosome,mu);
					break;
			}

		}
	}

	*num_nodes_active = get_num_nodes_active(best_chromosome);

	fp=fopen("cgp.txt","a");
	fprintf(fp,"Run %d and gen %d acheived fitness %d\n",run,*best_gen,best_fit);
	fprintf(fp,"Here is the chromosome\n");
	fclose(fp);

	fprint_a_chromosome(best_chromosome,"cgp.txt",1);
	fprint_active_genes(best_chromosome,"cgp.txt");

	fprint_a_chromosome(best_chromosome,"cgp.chr",0);

	free_chromosomes(chromosomes);

	free(best_chromosome);

	return best_fit;
}


// do mutiple runs of EA and write out results
void run_EA(int num_runs_total)
{
	int		j;
	int		best_gen,run;
	int		worst_of_best_fit,best_of_best_fit=0;
	int		fitness_final=0,num_nodes_active;
	char	prog[20],stat[20],runstring[10];
	double	fitnesses[1000], temp;
	double	av_fitness=0.0,av_best_gen=0.0,st_dev=0.0;
	double  av_num_nodes_active=0.0;
	FILE*	best;
	FILE*	fp;


	worst_of_best_fit=num_bits+ num_nodes;

	for (run=0;run<num_runs_total;run++)
	{

		sprintf(runstring,"%d",run); //store run as characters
		printf("\n\nRUN %d\n",run);

		if (progress_report>0)
		{
			strcpy(prog,"cgp");
			strcat(prog,runstring);

			strcpy(stat,prog);
			strcat(prog,".prg"); // create .prg file name
			strcat(stat,".txt"); // create .txt file name 

			fp=fopen(prog,"w");  // create empty .prg file
			fclose(fp);

			fp=fopen(stat,"w");
			fprintf(fp,"\nRUN %d\n\n",run);
			fprintf(fp,"Generation\tfitness\n",run);
			fclose(fp);
		}

		fitness_final =  EA(&best_gen,&num_nodes_active,run,prog,stat);

        if (fitness_final < worst_of_best_fit)
			worst_of_best_fit=fitness_final;

		if (fitness_final > best_of_best_fit)
		{
			best_of_best_fit=fitness_final;
			
		}

		av_num_nodes_active=av_num_nodes_active+num_nodes_active;
		fitnesses[run]=(double)fitness_final;
		av_fitness=av_fitness+(double)fitness_final;
		if (fitness_final==num_bits)
			av_best_gen=av_best_gen+(double)best_gen;
   }

   av_fitness=av_fitness/((double)num_runs_total);
   av_best_gen=av_best_gen/((double)num_runs_total);
   av_num_nodes_active=av_num_nodes_active/((double)num_runs_total);

   st_dev=0.0;
   for (j=0;j<num_runs_total;j++)
   {
		temp=(fitnesses[j]-av_fitness);
		temp=temp*temp;
		st_dev=st_dev+temp;
   }

   st_dev=st_dev/(double)num_runs_total;
   st_dev=sqrt(st_dev);

   best=fopen("cgp.txt","a");
   fprintf(best,"\naverage fitness  %6.4lf\n",av_fitness);
   fprintf(best,"\nstd dev          %6.4lf\n\n",st_dev);
   fprintf(best,"\naverage number of active nodes is  %6.4lf\n",av_num_nodes_active);
   fprintf(best,"\nThe best solution of all runs  is  %d\n",best_of_best_fit);
   fprintf(best,"\nThe worst solution of all runs is  %d\n",worst_of_best_fit);
   fprintf(best,"\nOf perfect solutions, the average number of generations is  %6.4lf\n",av_best_gen);
   fclose(best);

}