binarynew.cpp

利用遗传算法求最小值

#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#define POPSIZE 50          //群体规模
//#define MAXIMIZATION 1
//#define MINIMIZATION 2
//#define Cmax 100
//#define Cmin 0
#define NVARS 3                 //变量个数 
#define LENGTH1 8               
#define LENGTH2 8
#define LENGTH3 8               //各个变量的二进制位数
//#define LENGTH4 3
//#define LENGTH5 3
//#define LENGTH6 3
#define CHROMLENGTH LENGTH1+LENGTH2+LENGTH3//+LENGTH4+LENGTH5+LENGTH6
//int FunctionMode=MAXIMIZATION;
int PopSize=50;                //群体规模
int MaxGeneration=1000;         //运行的最大代数
double Pc=0.5;                  //杂交概率
double Pm=0.15;                  //变异概率
//double upper[NVARS];
//double lower[NVARS];
struct individual
{
	char chrom[CHROMLENGTH+1];
	double value;
	double fitness;
};
int generation;
int best_index;
int worst_index;
//FILE *galog; 
struct individual bestindividual;
struct individual worstindividual;
struct individual currentbest;
struct individual population[POPSIZE];
void GenerateInitialPopulation(void);
void GenerateNextPopulation(int generation);
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(int generation);     //交叉操作
void MutationOperator(int generation);    //变异操作
void OutputTextReport(void);
int random(int n);
void main()
{   
	FILE *infile;
//	int i;
	long temp1,temp2,temp3;
	double x1,x2,x3,s=0;
//		A[13]={0.176,0.4548,0.699,0.903,1,1.3,1.477,1.699,1.903,2,2.3,2.699,3},
//		B[13]={1.6,1.68,1.724,1.748,1.756,1.778,1.785,1.796,1.82,1.833,1.875,1.944,2};
/*		A[13]={0.3,0.477,0.699,0.9,1,1.3,1.6,1.699,1.9,2,2.3,2.477,3},
		B[13]={1.3,1.38,1.462,1.505,1.544,1.6,1.653,1.672,1.699,1.724,1.785,1.845,2};
*/
        if((infile=fopen("gadata.txt","w"))==NULL)
		{
          printf("\nCannot open input file!\n");
          exit(1);
		}

	generation=0;
    GenerateInitialPopulation();
    EvaluatePopulation();
	while(generation<MaxGeneration)
	{
		generation++;
        GenerateNextPopulation(generation);
        EvaluatePopulation();
        PerformEvolution();
//		printf("%4d %10.4f\n",generation,currentbest.fitness);
//        OutputTextReport();
//	}
	temp1=DecodeChromosome(currentbest.chrom,0,LENGTH1);
	temp2=DecodeChromosome(currentbest.chrom,LENGTH1,LENGTH2);
    temp3=DecodeChromosome(currentbest.chrom,LENGTH1+LENGTH2,LENGTH3);
   // temp4=DecodeChromosome(currentbest.chrom,LENGTH1+LENGTH2+LENGTH3,LENGTH4);
    //temp5=DecodeChromosome(currentbest.chrom,LENGTH1+LENGTH2+LENGTH3+LENGTH4,LENGTH5);
   // temp6=DecodeChromosome(currentbest.chrom,LENGTH1+LENGTH2+LENGTH3+LENGTH4+LENGTH5,LENGTH6);
	x1=-5.12+10.24*temp1/(pow(2,LENGTH1)-1);
    x2=-5.12+10.24*temp2/(pow(2,LENGTH2)-1);
	x3=-5.12+10.24*temp3/(pow(2,LENGTH3)-1);
    //x4=lower[3]+(upper[3]-lower[3])*temp4/(pow(2,LENGTH4)-1);
	//x5=lower[4]+(upper[4]-lower[4])*temp5/(pow(2,LENGTH5)-1);
    //x6=lower[5]+(upper[5]-lower[5])*temp6/(pow(2,LENGTH6)-1);
    //fprintf(galog,"\n\nSimulation completed\n");
    printf("%d %f %f %f %10.4f\n",generation,x1,x2,x3,currentbest.fitness);
	fprintf(infile,"%d %f %f %f %10.4f\n",generation,x1,x2,x3,currentbest.fitness);
	}
 //   printf("\n best fitness=%f\n",currentbest.fitness);
    fclose(infile);
//    getch();
}
void GenerateInitialPopulation(void)
{
	int i,j;
//	randomize();
	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(int generation)
{
     SelectionOperator();
     CrossoverOperator(generation);
     MutationOperator(generation);
}
void EvaluatePopulation(void)
{
     CalculateObjectValue();
//     CalculateFitnessValue();
     FindBestAndWorstIndividual();
}

long DecodeChromosome(char *string,int point, int length)
{
	int i;
	long decimal=0L,temp;
	char *pointer;
	temp=1;
	for(i=0,pointer=string+point+length-1;i<length;i++,pointer--)
	{
		decimal+=(*pointer-'0')*temp;
		temp*=2;
	}
	return(decimal);
}
void CalculateObjectValue(void)
{   
	FILE *infile;
	int i;
	long temp1,temp2,temp3;
	double x1,x2,x3,s=0;
//		A[13]={0.176,0.4548,0.699,0.903,1,1.3,1.477,1.699,1.903,2,2.3,2.699,3},
//		B[13]={1.6,1.68,1.724,1.748,1.756,1.778,1.785,1.796,1.82,1.833,1.875,1.944,2};
/*		A[13]={0.3,0.477,0.699,0.9,1,1.3,1.6,1.699,1.9,2,2.3,2.477,3},
		B[13]={1.3,1.38,1.462,1.505,1.544,1.6,1.653,1.672,1.699,1.724,1.785,1.845,2};
*/
        if((infile=fopen("data.txt","w"))==NULL)
		{
          printf("\nCannot open input file!\n");
          exit(1);
		}
		
for(i=0;i<PopSize;i++)
	{	
		temp1=DecodeChromosome(population[i].chrom,0,LENGTH1);
		temp2=DecodeChromosome(population[i].chrom,LENGTH1,LENGTH2);
		temp3=DecodeChromosome(population[i].chrom,LENGTH1+LENGTH2,LENGTH3);
		//temp4=DecodeChromosome(population[i].chrom,LENGTH1+LENGTH2+LENGTH3,LENGTH4);
		//temp5=DecodeChromosome(population[i].chrom,LENGTH1+LENGTH2+LENGTH3+LENGTH4,LENGTH5);
		//temp6=DecodeChromosome(population[i].chrom,LENGTH1+LENGTH2+LENGTH3+LENGTH4+LENGTH5,LENGTH6);
		x1=-5.12+10.24*temp1/(pow(2,LENGTH1)-1);
        x2=-5.12+10.24*temp2/(pow(2,LENGTH2)-1);
	    x3=-5.12+10.24*temp3/(pow(2,LENGTH3)-1);
        //x4=lower[3]+(upper[3]-lower[3])*temp4/(pow(2,LENGTH4)-1);
	    //x5=lower[4]+(upper[4]-lower[4])*temp5/(pow(2,LENGTH5)-1);
       // x6=lower[5]+(upper[5]-lower[5])*temp6/(pow(2,LENGTH6)-1);
       //s=x1*x1+x2+x3+x4+x5+x6;
	   s=x1*x1+x2*x2+x3*x3;
	   population[i].fitness=1/(s+1);
//	   printf("%f %f %f\n",x1,x2,x3);
	   fprintf(infile,"%f %f %f %10.4f\n",x1,x2,x3,population[i].fitness);
      }
	fclose(infile);
}
/*
void CalculateFitnessValue(void)
{
	int i;
	double temp;
	for(i=0;i<PopSize;i++)
	{
		if(FunctionMode==MAXIMIZATION)
		{
			if((population[i].value+Cmin>0.0))
			{
				temp=Cmin+population[i].value;
			}
			else
				temp=0;
		}
		else
			if(FunctionMode==MINIMIZATION)
			{
				if(population[i].value<Cmax)
					temp=Cmax-population[i].value;
				else
					temp=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;
			}
			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;
		}
	}
}
void PerformEvolution(void)
{
	if (bestindividual.fitness>currentbest.fitness)
	{
		currentbest=population[best_index];
	}
}
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(int generation)
{
	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=random(PopSize-i);
		temp=index[i];
		index[i]=index[point+i];
		index[point+i]=temp;
	}
//one-point crossover operation
	if(generation%2==1)
		for(i=0;i<PopSize-1;i+=2)
		{
			p=rand()%1000/1000.0;
			if(p<Pc)
			{
				point=random(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;
				}
			}
		}
	else
		for(i=0;i<PopSize;i++)
		{
			p=rand()%1000/1000.0;
			if(p<Pc)
			{
				point=random(CHROMLENGTH-1)+1;
				for (j=point;j<CHROMLENGTH;j++)
				{
					population[i].chrom[j]=currentbest.chrom[j];
				}
			}
		}

} 



void MutationOperator(int generation)
{
	int i,j;
	double p;
//bit mutation
	if(generation%2==1)//
		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';
				}
			}
		}
	else
		for(i=0;i<PopSize;i++)
		{
			j=0;
			while(population[i].chrom[j]==currentbest.chrom[j])
				j++;
			for(;j<CHROMLENGTH;j++)
			{
				p=rand()%1000/1000.0;
				if(p<Pm)
				{
					population[i].chrom[j]=currentbest.chrom[j];
				}
			}
		}
}

/*
void OutputTextReport(void)
{

	int i;
	double sum;   //temporary sum
    double average;   // average of population objest value

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

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