遗传窜法.c

利用遗传算法求函数最大值的一段源代码

#include  <stdlib.h> //求函数在(-4,4)的最大值
#include  <math.h>
#include  <time.h>
#include  <string.h> 
#define POPSIZE  10//population size
#define Pc  0.8 //crossover probability
#define Pm 0.005//mutation probability
#define G  0.8 //generation gap
#define LENGTH 22 //  一个变量的长度
#define Maxgeneration  20
#define N  2      //  函数变量个数

int generation;
double value[POPSIZE][N];  //变量值

struct indivaual
{char chrom[N*LENGTH];
 double value;              //函数值
 double fitness;
};
struct indivaual population[POPSIZE];
struct indivaual matingpool[POPSIZE]; 



void decode(struct indivaual *p)
{
	int i,j,k,l;
	double temp=0.0;
	for(j=0;j<POPSIZE;j++)
	{
		i=0;k=0;
		for(l=0;i<N*LENGTH+1;k++,i++)
		{
			if (k==LENGTH)
			{
				k=0; 
				value[j][l]=8*temp/(pow(2,LENGTH))-4.0;
				temp=0.0;
				l++;
			}
			if (i==N*LENGTH)
				break;
			temp+=((int)(p[j].chrom[i]))*(pow(2,(LENGTH-1-k)));
		}
	}
}

void Function(struct indivaual *p)         
{	
	int i;
	decode(p);
	for(i=0;i<POPSIZE;i++)
	{
		p[i].value=4*value[i][0]*exp(-(pow(value[i][0],2)+pow(value[i][1],2)))+sin(pow(value[i][0],2));
	}
	
}

void Fitness(struct indivaual *p)
{
	int i;
	for(i=0;i<POPSIZE;i++) 
	{
		p[i].fitness=p[i].value+1000;
	}
}

//产生出始种群
void GenerateInitialPopulation()            
{
	int i,j;

	/* Seed the random-number generator with current time so that
    * the numbers will be different every time we run.
    */
	srand((unsigned)time(NULL));

	for(i=0;i<POPSIZE;i++)
	{
		for(j=0;j<N*LENGTH;j++)
		{
			(population[i]).chrom[j]=(char)(rand()%2);
		}
			(population[i]).chrom[j]='\0';
	}
}

void Order(struct indivaual *q)   //排序
{
	int i,j,k; 
 
	struct indivaual temp;
	for(k=0;k<POPSIZE-2;k++)
	{
		for(i=0;i<POPSIZE-1-k;i++)
		{
			if ((q[i].fitness)<(q[i+1].fitness))
			{
				for(j=0;j<N*LENGTH;j++)
				{
					temp.chrom[j]=q[i].chrom[j];
				}
				temp.fitness=q[i].fitness;         
				temp.value=q[i].value;
				for(j=0;j<N*LENGTH;j++)
				{
					q[i].chrom[j]=q[i+1].chrom[j];
				}
				q[i].fitness=q[i+1].fitness;
				q[i].value=q[i+1].value;
				for(j=0;j<N*LENGTH;j++)
				{
					q[i+1].chrom[j]=temp.chrom[j];
				}
				q[i+1].fitness=temp.fitness;
				q[i+1].value=temp.value;
			}
			continue;
		}
	}
}

void Reproduction()           //复制 生成matingpool
{
	int i,j,k;
	double total=0.0;
	double m,n;
	srand((unsigned)time(NULL));
	for(i=0;i<POPSIZE;i++)
	{
		total+=(population[i].fitness);
	}
	for(i=0;i<POPSIZE;i++)
	{
		n=(double)(rand()%(int)(total)); 
		m=0.0;
		for(k=0;(m<n)&&(k<POPSIZE);k++)
		{
			m+=(population[k].fitness);
		}
		for(j=0;j<N*LENGTH;j++)
		{
			matingpool[i].chrom[j]=population[k-1].chrom[j];
		}
		matingpool[i].fitness=population[k-1].fitness;
		matingpool[i].value=population[k-1].value;
	}
}


void Crossover()
{
	int i,j,k;
	int index[POPSIZE];
	int pointp,temp,point[N];
	char ch;
	srand((unsigned)time(NULL));
	for(i=0;i<POPSIZE;i++)
	{
		index[i]=i;
	}
	for(i=0;i<POPSIZE;i++)              //打乱顺序
	{
		pointp=rand()%(POPSIZE-i);
		temp=index[i];
		index[i]=index[pointp+i];
		index[pointp+i]=temp;
	}
	for(i=0;i<(int)(Pc*POPSIZE)-1;i+=2) 
	{
		for(k=0;k<N;k++)
		{
			point[k]=k*LENGTH+rand()%LENGTH;
		}
		for(k=0;k<N;k++)
		{ 
			for(j=point[k];j<(k+1)*LENGTH;j++)
			{
				ch=matingpool[index[i]].chrom[j];
				matingpool[index[i]].chrom[j]=matingpool[index[i+1]].chrom[j]; 
				matingpool[index[i+1]].chrom[j]=ch;
			}
		}
	}
}

void Mutation()                 //基因突变 
{int i,j;
 int index[POPSIZE];
 int pointp,temp;
 srand((unsigned)time(NULL));
 for(i=0;i<POPSIZE;i++)
 {index[i]=i;}
 for(i=0;i<POPSIZE;i++)
 {pointp=rand()%(POPSIZE-i);
  temp=index[i];
  index[i]=index[pointp+i];
  index[pointp+i]=temp;
 }
  for(i=0;i<(int)(Pm*POPSIZE)-1;i++) 
  {j=rand()%(N*LENGTH-1);
  matingpool[index[i]].chrom[j]=((matingpool[index[i]].chrom[j]=='0')?'1':'0'); 
  }
}

void GenerateNextpopulation()
{int i,j;
 Reproduction();
 Crossover();
 Mutation();
 Function(matingpool);
 Fitness(matingpool);
 Order(matingpool);
 Order(population);
 for(i=0;i<(int)(G*POPSIZE);i++)
 {for(j=0;j<N*LENGTH;j++) 
 {population[(int)((1-G)*POPSIZE)+i].chrom[j]=matingpool[i].chrom[j];
 }
  population[(int)((1-G)*POPSIZE)+i].fitness=matingpool[i].fitness;
  population[(int)((1-G)*POPSIZE)+i].value=matingpool[i].value;
 }
 
}

void OutputTextReport()
{int i,k,l;
 double sum,average,temp;
 sum=0.0;
 for(i=0;i<POPSIZE;i++)
 {sum+=population[i].value;}
  average=sum/POPSIZE;
  printf("\nGENERATION:%d\nAVERAGE:%f\nGOODVALUE:%f",generation,average,population[0].value);
  printf("\nbestchrom:");
  for(i=0;i<N*LENGTH;i++)
  {printf("%d",population[0].chrom[i]);}
  printf("\n");

  for(l=0,i=0,k=0,temp=0.0;i<N*LENGTH+1;k++,i++)                               //对最优染色体解码
   {if (k==LENGTH)                                                   //对最优染色体解码
	{k=0;                                                           //对最优染色体解码
	 value[0][l]=temp/(pow(2,LENGTH));                             //对最优染色体解码
	 temp=0.0;l++;                                                //对最优染色体解
  }                                                              //对最优染色体解码
    if (i==N*LENGTH)                                            //对最优染色体解码
		break;                                                 //对最优染色体解码
    temp+=((int)(population[0].chrom[i]))*(pow(2,(LENGTH-1-k)));       //对最优染色体解码
   }
  for(i=0;i<N;i++)
  printf("x%d=%f\n",i+1,8*value[0][i]-4.0);
}

main()
{
	generation=0;

	GenerateInitialPopulation();

	Function(population);
	Fitness(population);
	for(;generation<Maxgeneration;generation++)
	{
		GenerateNextpopulation();
	}
	Order(population);
	OutputTextReport();
	printf("%f",population[0].value);
}