xiaoshen.c

基于小生竞的遗传算法 Genetic Algorithm Based 0n Niche

#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define POPSIZE 500     //种群的最大值
#define cmax 200
#define length1 10
#define length2 10
#define chromlength length1+length2  //染色体长度
int     popsize;                        //种群大小
int     N;
int     maxgeneration;  //最大世代数
double  pc;          //交叉率
double  pm;          //变异率
double  L;
double  penalty;
struct  individual
{
int  chrom[chromlength+1];
double value;         //函数值
double fitness;      //适应度
};
int generation;      //世代数
int best_index;
struct individual bestindividual;  //最佳个体
struct individual currentbest;
struct individual population[POPSIZE];
//函数声明                                       
void generateinitialpopulation();                 
void generatenextpopulation();
void evaluatepopulation();
long decodechromosome(int *,int,int);
void calculateobjectvalue();
void calculatefitnessvalue();
void findbestindividual();
void performevolution();
void selectoperator();
void crossoveroperator();
void mutationoperator();
void input();
void outputtextreport();
void caculateHMlength();
void orderpopulation();


void generateinitialpopulation( )  //初始化种群
{
	int i,j;


	
	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()  //生成下一代
{
	selectoperator();
	crossoveroperator();
	mutationoperator();
}
void evaluatepopulation()   //评价个体，求最佳个体
{
	calculateobjectvalue();
	calculatefitnessvalue();
	findbestindividual();
}
long decodechromosome(int *string ,int point,int length) //给染色体解码
{
	int i;
	long decimal=0;
	int *pointer;
for(i=0,pointer=string+point;i<length;i++,pointer++)
	if(*pointer-0)

	{decimal +=(long)pow(2,i);
	}
	return (decimal);

}
void calculateobjectvalue()  //计算函数值
{
	int i;
	long temp1,temp2;
    double x,y;

	for (i=0; i<popsize; i++)
	{
		 temp1=decodechromosome(population[i].chrom,0,length1);
         temp2=decodechromosome(population[i].chrom,length1,length2);
         x=6.000*temp1/1023.0-3.000;
         y=4.000*temp2/1023.0-2.000;
         population[i].value=(4-2.1*x*x+(x*x*x*x)/3)*x*x+x*y+(-4+4*y*y)*y*y;
}
}
void calculatefitnessvalue()//计算适应度
{
	int  i;
    double temp;
    for(i=0;i<popsize;i++)
	{
   if(population[i].value<cmax)
      {temp=cmax-population[i].value;}
    else{ temp=0.0;}
    population[i].fitness=temp;
	}
}
void findbestindividual( )       //求最佳个体
{
	int i;
	double sum=0.0;
	
	bestindividual=population[0];

	for (i=1;i<popsize; i++){
		if (population[i].fitness>bestindividual.fitness){
			bestindividual=population[i];
			best_index=i;
                                }
        sum+=population[i].fitness;
          }
     if (generation==0){
		currentbest=bestindividual;
	}
	else{
		if(bestindividual.fitness>=currentbest.fitness){
			currentbest=bestindividual;
		}
	}
}
void performevolution() //演示评价结果
{
	if (bestindividual.fitness>currentbest.fitness){
		currentbest=population[best_index];
	}
	
}
void selectoperator() //比例选择算法
{
	int i,index;
	double p,sum=0.0;
	double cfitness[POPSIZE];

	struct individual newpopulation[POPSIZE];
	for(i=0;i<popsize;i++)
	{sum+=population[i].fitness;}

    for(i=0;i<popsize; i++){
		cfitness[i]=population[i].fitness/sum;
	}

	for(i=1;i<popsize; i++){
		cfitness[i]=cfitness[i-1]+cfitness[i];
	}

	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 i,j;
	int index[POPSIZE];
	int point,temp;
	double p;
	int a;

	
	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;
	}

	
	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++){
				a=population[index[i]].chrom[j];
				population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
				population[index[i+1]].chrom[j]=a;
			}
		}
	}

}
void mutationoperator() //变异操作
{
	int i,j;
	double p;
	
	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 input()     //数据输入
{   printf("初始化全局变量:\n");
	printf("    种群大小(50-500)：");
   scanf("%d", &popsize);
    if((popsize%2) != 0)
      {
	printf( "   种群大小已设置为偶数\n");
	popsize++;};
    printf("     最大世代数(100-300)：");
    scanf("%d", &maxgeneration);
    printf("     交叉率(0.2-0.99)：");
    scanf("%f", &pc);
    printf("     变异率(0.001-0.1)：");
    scanf("%f", &pm);
    printf("     海明距离：");
    scanf("%f", &L);
    printf("     阈值函数值：");
    scanf("%f", &penalty);
}
void outputtextreport()//数据输出
{
	int i;
    double sum;
    double average;
    sum=0.0;
    for(i=0;i<popsize;i++)
	{sum+=population[i].value;}
    average=sum/popsize;
	
    printf("当前世代=%d\n当前世代平均函数值=%f\n当前世代最低函数值=%f\n",generation,average,population[best_index].value);

}
void orderpopulation()   //对个体按适应度进行降序，记忆前N个个体
{  int i,j,k;
   struct individual t;
   for(i=0;i<popsize-1;i++)
   {k=i;
     for(j=i+1;j<popsize;j++)
        if(population[j].fitness>population[k].fitness)
			k=j;
		if(k!=i)
		{t=population[i];population[i]=population[k];population[k]=t;}
   }
   N=popsize/4;            //N的大小取popsize的1/4
   for(i=popsize;i<popsize+N;i++)
    population[i]=population[i-popsize]; 
}
void caculateHMlength()  //计算海明距离
{   int i=0,j=0,k=0;
    struct individual t;
    double value;
	int hmlength[500][500];
	hmlength[0][1]=0;    //用来存贮两个个体之间的海明距离
	for(i=0;i<popsize+N;i++)
      for(j=i+1;j<popsize+N;j++)
	  {for(k=0;k<chromlength;k++)
	    hmlength[i][j]=hmlength[i][j]+(population[i].chrom[k]-population[j].chrom[k])*(population[i].chrom[k]-population[j].chrom[k]);
	    if(hmlength[i][j]<(L*L))
			value=population[i].fitness-population[j].fitness;
		if(value>0)
			population[j].fitness=penalty;
		else
			population[i].fitness=penalty;
	  }
     for(i=0;i<popsize+N-1;i++)
	 {k=i;
     for(j=i+1;j<popsize+N;j++)
        if(population[j].fitness>population[k].fitness)
			k=j;
		if(k!=i)
		{t=population[i];population[i]=population[k];population[k]=t;}
   }
}
void main()    //主函数
{   int i;
    double pe;
printf("本程序为求函数f(x,y)=(4-2.1*x*x+(x*x*x*x)/3)*x*x+x*y+(-4+4*y*y)*y*y的最小值 \n其中-3<=x<=3,-2<=y<=2\n");
    generation=0;
    input();
    generateinitialpopulation();
	evaluatepopulation();
	while(generation<maxgeneration)
	{
		generation++;
		orderpopulation();
		generatenextpopulation();
		caculateHMlength();
		evaluatepopulation();
		performevolution();
		outputtextreport();
	}
    printf("\n");
	printf("         统计结果:        ");
    printf("\n");
    printf("最小函数值等于：%f\n",currentbest.value);
	printf("其染色体编码为：");
	for (i=0;i<chromlength;i++)
	{
	printf("%d",currentbest.chrom[i]);
		
	}
    printf("\n"); 
	scanf("%f", &pe);
}