ga.c

遗传算法 虽然比较简单 但功能可以实现 找一个测试函数的最值 效果可以

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
//#include "mpi.h"

#define PCROSSOVER 0.6               /* probability of crossover */ 
#define PMUTATION 0.1           /* probability of mutation */ 
#define N 40                    /*popusize*/
#define D 2
#define PI 3.1415926
#define E 2.71828183
#define MAX 30
#define MIN -30
#define LEN 40
#define CROSSTIME 10
#define MUTATETIME 10
#define TIME 500

     
struct genotype /* genotype (GT), a member of the population */ 
{ 
  
 double fitness;            /* GA's fitness */  
 double eva;
 double value1;
 double value2;
 int offspring;
 int b[LEN];

}; 

struct genotype population[N+1];    /* population */ 
struct genotype newpopulation[N+1]; /* new population; */ 
struct genotype best;
                                    

/* Declaration of procedures used by this genetic algorithm */ 

void initialize(void); 
void evaluate(void); 
void elitist(void); 
void select(void); 
void crossover(void);  
void mutate(void); 
void btod(void);

void initialize(void)
{
	int i=0,j=0;
	double t=0;
	
	for(i=1;i<=N;i++)
	{
		
		for(j=0;j<LEN;j++)
		{	
			
			t=(rand()%10)/10.0;

			if(t>0.5)
				population[i].b[j]=1;
			else
				population[i].b[j]=0;
	//		printf("%d",population[i].b[j]);

		}
	//	putchar('\n');
		

	}
}

void btod()
{
	int i=0,j=0;
	double x=0,y=0;
	for(i=1;i<=N;i++)
	{
		x=0;
		y=0;
		for(j=0;j<(LEN/2);j++)
		{
			x+=(population[i].b[j]*pow(2,(LEN/2)-1-j));			
		}
		population[i].value1=MIN+x*(MAX-MIN)*1.0/(pow(2,LEN/2)-1);

		for(j=LEN/2;j<LEN;j++)
		{
			y+=(population[i].b[j]*pow(2,LEN-1-j));			
		}
		population[i].value2=MIN+y*(MAX-MIN)*1.0/(pow(2,LEN/2)-1);
	}

}

void evaluate(void)
{
	int i=0;
	double temp1=0,temp2=0;
	for(i=1;i<=N;i++)
	{
		temp1=pow(population[i].value1,2)+pow(population[i].value2,2);
		temp2=cos(2*PI*population[i].value1)+cos(2*PI*population[i].value2);
	    population[i].fitness=(-20)*exp(-0.2*sqrt((1.0/D)*temp1))-exp((1.0/D)*temp2)+20+E;
		

	}
}

void select(void)
{
	
	int count; 
	int j=0,i=0,child=0,temp1=1,num=0;
	double sum=0,temp[N+1];
	struct genotype max,best1;
	max.fitness=-1000;
	best1.fitness=1000;
	for(i=1;i<=N;i++)
	{
		if(max.fitness<population[i].fitness)
		{
			max=population[i];
			
		}

	}

	for(i=1;i<=N;i++)
	{
		population[i].eva=exp(0.0025*(max.fitness-population[i].fitness));
		sum+=population[i].eva;
	}
	for(i=1;i<=N;i++)
	{
		temp[i]=population[i].eva*1.0/sum;
		population[i].offspring=(int)(temp[i]*N);
		temp[i]=temp[i]-population[i].offspring;
		child+=population[i].offspring;
		
   	}
		
	for(i=1;i<=N;i++)
	{
		if(temp[i]>=0.5)
		{
			child++;
			population[i].offspring++;
			
		}

	}
	if(child<N)
	{
		int temp=N-child;
		for(i=1;i<=N;i++)
		{
			if(best1.fitness>population[i].fitness)
			{
				best1=population[i];
				count=i;
			}

		}
		population[count].offspring+=temp;
			

	}
	
	for(i=1;i<=N;i++)
	{
		num=population[i].offspring;
		for(j=temp1;j<temp1+num;j++)
		{
			if(num==0)
				break;
			newpopulation[j]=population[i]; //新一带产生 仅binary

		}
		temp1+=num;
	}

	
}

void crossover(void)              //新一代进行交叉
{
	double cross=0;
	struct genotype temp;
	int i=0,j=0,crosspoint,can1,can2; 
	
	
	for(i=1;i<=CROSSTIME;i++)
	{
		
		cross=(rand()%10)*1.0/10;
		if(cross<PCROSSOVER)
		{
			can1=(int)(rand()%N)+1;  //待交叉者
			can2=(int)(rand()%N)+1;
			crosspoint=(int)(rand()%LEN);
			temp=newpopulation[can1];
            for(j=crosspoint;j<LEN;j++)
			{
				newpopulation[can1].b[j]=newpopulation[can2].b[j];
				newpopulation[can2].b[j]=temp.b[j];
			}

		}
	
	}

}

void mutate(void)                         //变异
{
	int mutatepoint,i,can;
	double pmutate=0;
	
	for(i=1;i<=MUTATETIME;i++)
	{   
		
		pmutate=(rand()%10)/10.0;
		if(pmutate<PMUTATION)
		{
	    	can=(rand()%N)+1;
		    mutatepoint=(rand()%LEN);
			if(newpopulation[can].b[mutatepoint]==0)
				newpopulation[can].b[mutatepoint]=1;
			else
				newpopulation[can].b[mutatepoint]=0;
		}
	
	}
}

void elitist(void)
{	
	
	int i=0;

	for(i=1;i<=N;i++)
	{
		if(best.fitness>population[i].fitness)
		{
			best=population[i];
			
		}
		
	}
	

	printf("x=%f  y=%f  f(x)=%f\n",best.value1,best.value2,best.fitness);

}

main()
{	
	
	int i=0,j=0,k=0;
	srand((unsigned)time(NULL));   //seed
	best.fitness=1000;
	initialize();
	for(k=0;k<TIME;k++)
	{
		btod();
		evaluate();               //将binary转换为十进制 x,y	 
		select();                 //用期望的方式生成后代
		crossover();              //交叉
		mutate();                 //单点变异
		elitist();               //选出本代中的最优个体
		for(i=1;i<=N;i++)
		{
			for(j=0;j<LEN;j++)
			population[i].b[j]=newpopulation[i].b[j];
		}
		
	}
/*	for(i=1;i<=N;i++)
	{
		printf("%f %f %f\n",newpopulation[i].value1,newpopulation[i].value2,newpopulation[i].fitness);
	}
	printf("%f %f %f\n",best.value1,best.value2,best.fitness);*/
		
	
}