cpp1.cpp

遗传算法C语言源代码

/**************************************************************************
*                  Simple Genetic Algorithm                               *
**************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/**************************************************************************
*                  The Definition of Constant                             *
**************************************************************************/
#define POPSIZE 5000      //population size
#define MAXIMIZATION 1   //maximization flag
#define MINIMIZATION 2   //minimization flag
/**************************************************************************
*                  The Definition of User Data                            *
*     (For different problem,there are some difference.)                  *
**************************************************************************/
#define Cmax 1000        //certain maximal value
#define Cmin 0           //certain minimum value
#define LENGTH1 10       //the chromosome length of 1st variable
#define LENGTH2 10     //the chromosome length of 2nd variable
#define LENGTH3 10
#define CHROMLENGTH LENGTH1+LENGTH2+LENGTH3    //total length of chromosome
int FunctionMode=MINIMIZATION;         //optimization type
int PopSize=500;                        //population size
int MaxGeneration=500;                 //max.number of generation
double Pc=0.6;                         //probability of crossover
double Pm=0.001;                       //probability of mutation
/**************************************************************************
*                  The Definition of Data Structure                       *
**************************************************************************/
struct individual                      //data structure of individual
{
char chrom[CHROMLENGTH+1];       //a string of code representing individual
double value;                    //object value of this individual
double fitness;                  //fitness value of this individual
};
/**************************************************************************
*                  The Definition of Global Variables                     *
**************************************************************************/
int generation;                  //number of generation
int best_index;                  //index of best individual
int worst_index;                 //index of worst individual
struct individual bestindividual; //best individual of current generation
struct individual worstindividual;//worst individual of current generation
struct individual currentbest;    //best individual by now
struct individual population[POPSIZE];  //population
double I[29]={261,389,462,505,525,543,556,567,577,583,587,595,597,597,589,556,538,516,486,505,477,429,379,320,263,220,182,167,152};
double QC[29]={228,300,382,444,490,513,528,543,553,564,573,581,588,594,592,584,566,550,520,504,483,461,420,368,318,271,234,193,178};
double QJ[29]={228,300};
double QJ1[29]={228,300};


/**************************************************************************
*                    Declaration of Prototype                             *
**************************************************************************/
void GenerateInitialPopulation(void);
void GenerateNextPopulation(void);
void EvaluatePopulation(void);
long DecodeChromsome(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);
/**************************************************************************
*                             main program                                *
**************************************************************************/
void main(void)
{
	generation=0;
    GenerateInitialPopulation();
    EvaluatePopulation();
	while(generation<MaxGeneration){
       generation++;
       GenerateNextPopulation();
       EvaluatePopulation();
       PerformEvolution();
       OutputTextReport();  }       
}
/**************************************************************************
*                 Function:Generate the first population.                 *
*                            Variable: None.                              *
**************************************************************************/
void GenerateInitialPopulation(void)
{
	int i,j;
	srand((unsigned int)time(NULL)); 
	//randomize();
	for(i=0;i<PopSize;i++){
		for(j=0;j<CHROMLENGTH;j++){
		//	population[i].chrom[j]=((rand() / (RAND_MAX / 11 + 1))<5)?'0':'1';
			population[i].chrom[j]=(((rand()%10+0))<5)?'0':'1';
		}
		population[i].chrom[CHROMLENGTH]='\0';
	}
}
/**************************************************************************
*               Function:Initialize the first population.                 *
*                            Variable: None.                              *
**************************************************************************/
void GenerateNextPopulation(void)
{
	SelectionOperator();
	CrossoverOperator();
	MutationOperator();
}
/**************************************************************************
*    Function:Evaluate populayion accordint to certain formula            *
*                            Variable: None.                              *
**************************************************************************/
void EvaluatePopulation(void)
{
	CalculateObjectValue();
	CalculateFitnessValue();
	FindBestAndWorstIndividual();
}
/**************************************************************************
*      Function:To decode abinary chromosome into a decimal integer       *
*                            Variable: None.                              *
*          Note:The returned value may be plus,or minus.                  *
* For different coding method,this value may be change into"unsigned int".*
**************************************************************************/
long DecodeChromsome(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);
}
/**************************************************************************
*                 Function:To calculate object value                      *
*                            Variable: None.                              *
*          Note:For different problem,user must change these code.        *
*            This example is dealing with Rosenbrock function.            *
*                   f(x1,x2)=100*(x1**2-x2)**2+(1-x1)**2                  *
*                   Its maximal value is:                                 *
*                   f(-2.048,-2.048)=3905.926227                          *
**************************************************************************/
void CalculateObjectValue(void)
{
	int i,j;
	long temp1,temp2,temp3;
	double x1,x2,x3;
	//Rosenbrock function
	for(i=0;i<PopSize;i++){
		population[i].value=0;
		temp1=DecodeChromsome(population[i].chrom,0,LENGTH1);
        temp2=DecodeChromsome(population[i].chrom,LENGTH1,LENGTH2);
		temp3=DecodeChromsome(population[i].chrom,LENGTH1+LENGTH2,LENGTH3);
		x1=temp1/1023.0;
		x2=temp2/1023.0;
		x3=temp3/1023.0;
		for(j=2;j<29;j++){
			QJ[j]=x1*I[j-2]+x2*I[j]+(1-x1-x2)*QJ[j-2]+x3*(I[j-1]-QJ[j-1]);

		population[i].value+=abs(QJ[j]-QC[j]);
		}

	
	if (1-x1-x2>1||1-x1-x2<0) population[i].value+=100000; 
	
	}
//	printf("%f\n",population[499].value);
}
/**************************************************************************
*                  Function:To calculate fitness value.                   *
*                            Variable: None.                              *
**************************************************************************/
void CalculateFitnessValue(void)
{
	int i;
	double temp;
	for (i=0;i<PopSize;i++){
		if(FunctionMode==MAXIMIZATION){//maximazation
			if((population[i].value+Cmin)>0.0){
				temp=Cmin+population[i].value;
			}else {
				temp=0.0;
			}
		}else if(FunctionMode==MINIMIZATION){//minimazation
			if(population[i].value<Cmax){
				temp=Cmax-population[i].value;
			}else {
				temp=0.0;
			}
		}
		population[i].fitness=temp;
	}
}
/**************************************************************************
*              Function:To Find out the best individual so                *
*                         far current generation.
*                            Variable: None.                              *
**************************************************************************/
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;
		}
		sum+=population[i].fitness;
	}
	//find out the best individual so far 
	if(generation==0){//initialize the best individual
		currentbest=bestindividual;
	}else{
		if(bestindividual.fitness>currentbest.fitness){
			currentbest=bestindividual;
		}
	}
}
/**************************************************************************
*      Function:To perform evolution operation based on elitise           *
*               model.Elitise model is to replase the worst               *
*               individual of this generation by the current              *
*               best one.                                                 *
*                            Variable: None.                              *
**************************************************************************/
void PerformEvolution(void)
{
	if(bestindividual.fitness>currentbest.fitness){
		currentbest=population[best_index];
	} else {
		population[worst_index]=currentbest;
	}
}
/**************************************************************************
*      Function:To reproduce a chromsome by proportional selection        *  
*                            Variable: None.                              *
**************************************************************************/
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];
	}
	srand((unsigned int)time(NULL)); 
	//selection operation
	for(i=0;i<PopSize;i++){
	 //   p=rand() / (RAND_MAX / 1001 + 1);/1000.0;
		p=(rand()%1000+0)/1000.0;
		index=0;
		while(p>cfitness[index]){
			index++;
		}
		newpopulation[i]=population[index];
	}
	for(i=0;i<PopSize;i++){
		population[i]=newpopulation[i];
	}
}
/**************************************************************************
*                   Function:Crossover two chromosome by means            *
*                            of one-point crossover.  
*                            Variable: None.                              *
**************************************************************************/
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;
	}
	 srand((unsigned int)time(NULL)); 
	for(i=0;i<PopSize;i++){
	//	srand((unsigned int)time((time_t *)NULL));
		point=rand()%(PopSize-i)+0;
		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+0)/1000.0;
		if(p<Pc){
			point=rand()%(CHROMLENGTH-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;
			}
		}
	}
}
/**************************************************************************
*                   Function:Mutation of a chromosome                     *
*                          Variable: None.                                *
**************************************************************************/
void MutationOperator(void)
{
	int i,j;
	double p;
	//bit mutation
	srand((unsigned int)time(NULL)); 
	for(i=0;i<PopSize;i++){
		for(j=0;j<CHROMLENGTH;j++){
			p=(rand()%1000+0)/1000.0;
			if(p<Pm){
				population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
			}
		}
	}
}
/**************************************************************************
*         Function:Output the results of current population               *
*                          Variable: None.                                *
**************************************************************************/
void OutputTextReport(void)
{  
	FILE *fp;
	fp=fopen("result.txt","w");
	long temp1,temp2,temp3;
	double x1,x2,x3;
	int i,j;
	double sum;            //temporary sum
	double average;        //average of population object value
	//calculate average object value
	sum=0.0;
	for(i=0;i<PopSize;i++){
		sum+=population[i].value;
//	fprintf(fp,"%f\n",population[i].value);
	}
	average=sum/PopSize;
	//print results of this population
fprintf(fp,"gen=%d,avg=%f,best=%f\n",generation,average,currentbest.value);
     fprintf(fp,"chromosome=");
	for(i=0;i<CHROMLENGTH;i++){
		fprintf(fp,"%c",currentbest.chrom[i]);
	}
		temp1=DecodeChromsome(currentbest.chrom,0,LENGTH1);
        temp2=DecodeChromsome(currentbest.chrom,LENGTH1,LENGTH2);
		temp3=DecodeChromsome(currentbest.chrom,LENGTH1+LENGTH2,LENGTH3);
		x1=temp1/1023.0;
		x2=temp2/1023.0;
		x3=temp3/1023.0;
         fprintf(fp,"\n%f,%f,%f,%lf\n",x1,x2,1-x1-x2,x3);
	fprintf(fp,"\n");
//	for(i=0;i<29;i++)
	//	fprintf(fp,"%f,%f,%f\n",I[i],QC[i],QJ[i]);
	//fprintf(fp,"\n\n");
//	for(j=2;j<29;j++) { QJ1[j]=x1*I[j-2]+x2*I[j]+(1-x1-x2)*QJ1[j-2]+x3*(I[j-1]-QJ1[j-1]);
//	fprintf(fp,"%f,%f,%f\n",I[j],QC[j],QJ1[j]);}
}