佳点集算法.cpp

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

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

#include "stdafx.h"

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

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

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[20][30];
	double anssum = 0;
	float p,jilei[20];
	int searchmax();
	srand( (unsigned)time( NULL ) );
	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];
	}
	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,gt3,pos;
	float jg[20];
	jc=int(num*crossover);
	by=int(num*mutation);
	for(i=0;i<generation;i++)
	{
	  printf("\n第");
	  printf("%d",i+1);
	  printf("代以后,对应的值:\n");
	   for(t=0;t<num;t++)
	   {
		   if(t%2==0);
		   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]);	
		   int i1,r,count;
		   int index[30];
		   float temp[30];
		   for(i1=0;i1<length;i1++)
		   {
			   if(qunti[gt1][i1]==qunti[gt2][i1])
				   qunti[gt3][i1]=qunti[gt1][i1];
			   else
			   {
				   count++;
				   for(r=0;r<i1;r++)
					  index[r]=i1;
			   }
			   temp[0]=e;   //取佳点rk={e的k次方}
			   for(r=1;r<count;r++)
			   {
				   temp[r]=e*temp[r-1];
			   }
			   for(r=0;r<count;r++)
			   {
				   temp[r]=temp[r]-(int)temp[r];
				   if(temp[r]<0.5)
					   temp[r]=0;
				   else
					   temp[r]=1;
			   }
			   for(r=0;r<count;r++)
			   {
				   i1=index[r];
				   qunti[gt3][i1]=temp[r];
			   }
		   }
	   }
	   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;//crossover 是交叉概率,mutation是变异的概率,其值均小于 1
	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.\n");
	printf("\n交叉:");
	scanf("%f",&crossover);
	printf("\n变异:");
	scanf("%f",&mutation);
	printf("\n输入要运行的迭代次数:");
	scanf("%d",&generation);
	printf("\n");
	create();
	calvalue();
	calcanshu();
	caljieguo();
	genertic(crossover,mutation,generation);
	return 0;
}