遗传算法的基本程序.txt

遗传算法的基本程序,可应用于所有用遗传算法解决的问题.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define POPSIZE          500

#define MAXIMIZATION     1
#define MINIMIZATION     2

#define Cmax             100
#define Cmin             0
                         
#define LENGTH1          10
                         
#define LENGTH2          10        

#define CHROMLENGTH   LENGTH1+LENGTH2
int FunctionMode        =MAXIMIZATION;
int PopSize             =80;
int MaxGeneration       =200;
double Pc               =0.6;
double Pm               =0.001;

struct individual
{
char chrom[CHROMLENGTH+1];						 						    
double value;
double fitness;
};

int generation;
int best_index;
int worst_index;
struct individual bestindividual;
struct individual worstindividual;
struct individual currentbest;
struct individual population [POPSIZE];

void GenerateInitialPopulation (void);
void GenerateNextPopulation (void);
void EvaluatePopulation (void);
long DecodeChromosome (char *,int,int);
void CalculateObjectValue (void);
void CalculateFitnessValue (void);
void FindBestAndWorstIndividual (void);
void PerformEvolution (void);
void SelectionOperator (void);
void CrossoverOperator (void);
void MutationOperator (void);
void OutputTextReport (void);

void main (void)
{
generation=0;
GenerateInitialPopulation ();
EvaluatePopulation ();

while (generation<MaxGeneration){
    generation++;
	GenerateNextPopulation();
	EvaluatePopulation ();
	PerformEvolution ();
	OutputTextReport ();
 } 
}

void GenerateInitialPopulation (void)
{
 int i,j;

srand((unsigned)time(NULL));
 for (i=0;i<PopSize;i++){
     for(j=0;j<CHROMLENGTH;j++){
	     population [i] .chrom [j] = (rand()%10 < 5)?'0':'1';
		 }
		 population [i] .chrom [CHROMLENGTH] ='\0';
 }
}
void GenerateNextPopulation (void)
{
 SelectionOperator ();
 CrossoverOperator ();
 MutationOperator ();
}
void EvaluatePopulation  (void)
{
 CalculateObjectValue ();
 CalculateFitnessValue  ();
 FindBestAndWorstIndividual ();
}

long DecodeChromosome (char *string,int point,int length)
{
 int i;
 long decimal=0l;
 char *pointer;

  for(i=0,pointer=string+point;i<length;i++,pointer++){
      decimal+=(*pointer-'0')<<(length-1-i);
  }
  return (decimal);
} 

void CalculateObjectValue (void)
{
 int i;
 long temp1,temp2;
 double x1,x2;
  
//Rosenbrock function
for (i=0;i<PopSize;i++) {
     temp1=DecodeChromosome (population [i].chrom,0,LENGTH1);
	 temp2=DecodeChromosome (population [i].chrom,LENGTH1,LENGTH2);
	 x1=4.096*temp1/1023.0-2.048;
	 x2=4.096*temp2/1023.0-2.048;
	 population[i].value=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
 }
}

void CalculateFitnessValue (void)
{
 int i;
 double temp;

 for (i=0;i<PopSize;i++) {
     if(FunctionMode==MAXIMIZATION) {//maximization
	    if((population[i].value+Cmin) >0.0){
		    temp=Cmin+population [i].value;
		} else {
		  temp=0.0;
		}
     } else if (FunctionMode==MINIMIZATION){ // minimization
	   if (population [i].value<Cmax) {
	       temp=Cmax-population[i].value;
	   }  else  {
	         temp=0.0;
          }
     }
	   population[i].fitness=temp;
 }
} 	

void FindBestAndWorstIndividual (void)
{
 int i;
 double sum=0.0;
 //find out the best and worst individual of this generation
 bestindividual=population [0];
 worstindividual=population [0];
 for (i=1;i<PopSize;i++) {
     if (population [i].fitness>bestindividual.fitness){
	     bestindividual=population [i];
		 best_index=i;
	 }  else if (population [i].fitness<worstindividual.fitness) {
	    worstindividual=population [i];
		worst_index=i;
	 }
}
//find out the best individual so far
if (generation==0){  //initialize the best individual
    currentbest=bestindividual;
}  else {
    if (bestindividual.fitness>currentbest.fitness) {
	    currentbest=bestindividual;
    }
 }
}

void PerformEvolution (void)
{
 if (bestindividual.fitness>currentbest.fitness) {
     currentbest=population [best_index];
 } else {
    population [worst_index] =currentbest;
 }
}

void SelectionOperator (void)
{
 int i,index;
 double p,sum=0.0;
 double cfitness [POPSIZE];//cumulative fitness value 
 struct individual newpopulation [POPSIZE];
 
 //calculate relative fitness
 for (i=0;i<PopSize;i++) {
      sum+=population [i].fitness;
 }
 for (i=0;i<PopSize;i++){
      cfitness[i]=population[i].fitness/sum;
 }
 
 //calculate cumulative fitness
 for (i=1;i<PopSize;i++){
      cfitness[i]=cfitness[i-1]+cfitness[i];
 }

 //selection operation
 for (i=0;i<PopSize	;i++){
      p=rand()%1000/1000.0;
	  index=0;
	  while(p>cfitness[index]){
	    index++;
	  }
	  newpopulation[i]=population[index];
 }
 for (i=0;i<PopSize;i++){
     population[i] =newpopulation[i];
 }
} 

void CrossoverOperator (void)
{
int i,j;
int index [POPSIZE];
int point,temp;
double p;
char ch;

//make a pair of individual randomly
for (i=0;i<PopSize;i++) {
   index [i] =i;
}
for (i=0;i<PopSize;i++){
   point=rand() % (PopSize-i);
   temp=index [i];
   index [i]=index [point+i];
   index [point+i] =temp;
}

//one-point crossover operation
for (i=0;i<PopSize-1;i+=2) {
    p=rand ()%1000/1000.0;
	if (p<Pc) {
	    point=rand() % (CHROMLENGTH-1) +1; 
		for (j=point;j<CHROMLENGTH;j++) {
		     ch=population [index [i]] .chrom [j];
			 population [index [i]] .chrom [j]=population [index[i+1]] .chrom [j];
			 population [index [i+1]] .chrom [j] =ch;
		 }
	 }
 }
}   

void MutationOperator (void)
{
 int i,j;
 double p;
 
 // bit mutation
 for (i=0;i<PopSize;i++) {
     for(j=0;j<CHROMLENGTH;j++){
	     p = rand ()%1000/1000.0;
		 if ( p<Pm) {
		   population [i] .chrom [j] =(population [i] .chrom [j] == '0')?'1':'0';
	  }
	 }
 }
} 

void OutputTextReport (void)
{
 int i;
 double sum;
 double average;
 
 // calculate average object value
 sum=0.0;
 for (i=0;i<PopSize;i++) {
 	 sum+=population [i] .value;
}
average=sum/PopSize;

// printer results of this population
printf (" gen=%d,avg=%f,best=%f,", generation,average, currentbest.value);
printf (" chromsome=");
for (i=0;i<CHROMLENGTH;i++) {
    printf ("%c",currentbest.chrom [i]);
}
 printf (" \n");
}