遗传算法.cpp

理解普通的遗传算法和佳点集遗传算法的基本思想和不同点,用遗传算法测试一标准函数。

// 遗传算法.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdio.h"



#include "stdlib.h"
#include "stdio.h"
#include "time.h"
#include "math.h"
//#include "iomanip.h"




const int num=15;//所求问题的规模
const int length=30;//编码的长度
int qunti[num][length],value[num];
float jieguo[num],canshu[num];

void create()//初始化数据
{
   int i,j; 
   srand( (unsigned)time( NULL ) ); 
	for(i=0;i<num;i++)
	{
		for(j=0;j<length;j++)
		{
			qunti[i][j]=(rand()%2);
	}
	}
}

void calvalue()//二进制转为十进制
{
	int i,j;
	for(i=0;i<num;i++)
	{
		value[i]=0;
		for(j=0;j<length;j++)
			value[i]=value[i]*2+qunti[i][j];
	}
}
void calcanshu()//求X值
{
	int i;
	int zdz=1;
	for(i=0;i<length;i++)
	{
		zdz=2*zdz;
	}
	zdz--;
	for(i=0;i<num;i++)
	{
		canshu[i]=-5.12+float(10.24*((float)value[i]/(zdz-1)));
	}
}
void caljieguo()//求函数f(x)值
{
	int i;
	for(i=0;i<num;i++)
	{
		jieguo[i]=(float)(canshu[i]*canshu[i]+canshu[i]*canshu[i]+canshu[i]*canshu[i]);
	}
}
void  select()   //赌轮法选择一个适应度高的个体
{
	int i,j;
	int temp[num][length];
	double anssum = 0;
	float p,jilei[num];
	int searchmax();
	srand( (unsigned)time( NULL ) );  //产生随机数
	//x=rand();
	for (i=0; i<num; i++)
		anssum=anssum+jieguo[i];  //计算总适应度
	for (i=0; i<num; i++)   //计算适应度比例
		jilei[i]=jieguo[i]/anssum;
	for (i=1; i<num; i++)	//计算积累概率
		jilei[i] = (jilei[i]+jilei[i-1]);
	for (i=0;i<num;i++)
	{		p=rand()%100; //随机产生概率
		    j=0;
		while(p>jilei[j])
		{			j++;		}
		temp[i][length]=qunti[j][length];   
 //选择出来大于随机概率的个体赋值于TEMP
	}

	for(i=0;i<num;i++)
	{
		qunti[i][length]=temp[i][length];
	}   //更新群体值
	for(i=0;i<num;i++)
	{	calvalue();
		calcanshu();
		caljieguo();
        searchmax();
	}  
}
int searchmax()//求最大值
{
	int i,t;
	float max=0;
	for(i=0;i<num;i++)
	{
		if(max<jieguo[i])
		{	max=jieguo[i];
			t=i;
		}
	}
	return t;
}     //选择计算结果的最大值


void genertic(float crossover,float mutation,int generation)  //交叉
{
	int i,j,k,t,n;
	int jc,by,gt1,gt2,pos,temp;
	float jg[num];
	jc=int(num*crossover);    //得到交叉的个体数目
	by=int(num*mutation);  //得到变异的个体数目
	for(i=0;i<generation;i++)
	{
	  printf("\n第");
	  printf("%d",i+1);
	  printf("代后,对应的值为:");
	   for(t=0;t<num;t++)
	   {
		   if(t%2==0)   printf("\n");
		   printf("染色体值为:" );
		   printf("%f",canshu[t]);
		   printf("适应值为:");
		  printf("%f",jieguo[t]);
	   }
	   n=searchmax();
	   printf("\n此时最优解为:\n");
	  printf("染色体值为:");
	   printf("%f",canshu[n]);
	   printf("适应值为:");       
	   printf("%f",jieguo[n]);
	  
	     calvalue();
	     calcanshu();
	     caljieguo();
	     select();

	     for(j=0;j<num;j++)
	   {
		   if(j==0)jg[j]=jieguo[j];
		   else if(jieguo[j]<jg[j-1])
		   {
			   for(k=j-1;k>=-1;k--)
			   {if(k!=-1&&jieguo[j]<jg[k])
					   jg[k+1]=jg[k];
				   else
				   {
					   jg[k+1]=jieguo[j];
					   k=-2;
			   }}
		   }
		   else 
			   jg[j]=jieguo[j];
	   }
       for(j=0;j<jc;j++) 
	   {
		   do
		   {
			   gt1=rand()%num;
		   }while(gt1==n||jieguo[gt1]>jg[num/4]);
		   do
		   {
			   gt2=rand()%num;
		   }while(gt2==n||gt2==gt1||jieguo[gt2]>jg[num/4]);
		   pos=rand()%length;   //交叉位置
		   for(k=0;k<pos;k++)
		   {
			   temp=qunti[gt1][k];
               qunti[gt1][k]=qunti[gt2][k];
			   qunti[gt2][k]=temp;
		   }
	   }      // 交叉JC次

	   for(j=0;j<by;j++)
	   {
		   do
		   {
			   gt1=rand()%num;
		   } while(gt1==n||jieguo[gt1]<jg[num/4]);
		   pos=rand()%length;
		   qunti[gt1][pos]=(qunti[gt1][pos]+1)%2;
	   }
	}
}     //  进行变异
int _tmain(int argc, _TCHAR* argv[])
//主函数
{
	float crossover,mutation;
	int generation;
	srand((unsigned)time(NULL));  
//产生伪随机数
	printf("本程序通过计算f(x)=x*x+x*x+x*x的最大值，\n其中x取[-5.12，5.12]中的某个数,其最大值约为78.64\n\n问题规模为: ");
	printf("%d",num);
	printf("\n染色体长度为:");
	printf("%d",length);
	printf("请输入交叉和变异选择的概率,他们的概率之和小于1.0\n交叉:");
	scanf("%f",&crossover);
	printf("\n变异:");
	scanf("%f",&mutation);
	printf("\n输入要运行的迭代次数:");
	scanf("%d",&generation);
	printf("\n");
	create();    //初始化数据
	calvalue();   //计算数据的值
	calcanshu();  //计算X值
	caljieguo();  //计算适应值
	genertic(crossover,mutation,generation);
	//进行交叉变异得到最后结果

	return 0;
}