sgalib.cpp

这是一个遗传算法

// SGAlib.cpp : implementation file
//

#include "stdafx.h"
//#include "SGA for testing.h"
#include "SGAlib.h"
#include "iostream.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// SGAlib

SGAlib::SGAlib()
{
	

}

SGAlib::~SGAlib()
{
}


BEGIN_MESSAGE_MAP(SGAlib, CWnd)
	//{{AFX_MSG_MAP(SGAlib)
		// NOTE - the ClassWizard will add and remove mapping macros here.
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()


/////////////////////////////////////////////////////////////////////////////
// SGAlib message handlers

struct individual {
	unsigned* chrom;
	unsigned fitness;
	unsigned varible[3];
	int xsite;
	int parent[2];
	unsigned* PathValues;	
};
individual* oldpop;
individual* newpop;

struct bestever{
	unsigned* chrom;
	unsigned fitness;
	 unsigned varible[3];
	int generation;
};
bestever bestfit;

//静态变量必须初始化
int SGAlib::jrand=0;
double SGAlib::rndx2=0.0;
int SGAlib::rndcalcflag=0;
double  SGAlib::oldrand[55]={0.0};

FILE * outfp;

void SGAlib::initialize()
{
	initdata();
	chromsize=(lchrom/(8*sizeof(unsigned)));
	if (lchrom%(8*sizeof(unsigned))) chromsize++;
	initmalloc();
	randomize();
	nmutation=0;
	ncross=0;
	bestfit.fitness=0;
	bestfit.generation=0;
	initpop();
	//statistics(oldpop);
	for(int j=0;j<popsize;j++)
	{
		if (oldpop[j].fitness>bestfit.fitness)
		{
			for(int i=0;i<chromsize;i++)
			{
				bestfit.chrom[i]=oldpop[j].chrom[i];
			}
			bestfit.fitness=oldpop[j].fitness;
			bestfit.varible[0]=oldpop[j].varible[0];
			bestfit.varible[1]=oldpop[j].varible[1];
			bestfit.varible[2]=oldpop[j].varible[2];
		}	
	}

	initreport();	
}

void SGAlib::initmalloc()
{
	unsigned nbytes;
	int j;
	
	//分配给当前代和新一代种群内存空间
	nbytes=popsize*sizeof(individual);
	oldpop=(individual*)malloc(nbytes);
	if (oldpop ==NULL) nomemory("oldpop");
	newpop=(individual*)malloc(nbytes);	
	if(newpop ==NULL) nomemory("newpop");	
	//分配给染色体内存空间
	nbytes=chromsize*sizeof(unsigned);
	for(j=0;j<popsize;j++)
	{
		if((oldpop[j].chrom=(unsigned*)malloc(nbytes)) ==NULL)
			nomemory("oldpop chromosomes");
		if((newpop[j].chrom=(unsigned*)malloc(nbytes)) ==NULL)
			nomemory("newpop chromosomes");
		if ((oldpop[j].PathValues=(unsigned*)malloc(6*sizeof(unsigned))) ==NULL )
			nomemory("oldpop PathValues");
		if ((newpop[j].PathValues=(unsigned*)malloc(6*sizeof(unsigned))) ==NULL )
			nomemory("newpop PathValues");
	}
	if ((bestfit.chrom=(unsigned*)malloc(nbytes)) ==NULL )
		nomemory("bestfit chromosomes");
	

}

/*释放内存空间*/
void SGAlib::freeall()
{
	int i;
	for(i=0;i<popsize;i++)
	{
		free(oldpop[i].chrom);
		free(newpop[i].chrom);
		free(oldpop[i].PathValues);
		free(newpop[i].PathValues);
	}
	free(oldpop);
	free(newpop);
	free(bestfit.chrom);
}

/*内存不足，退出*/
void SGAlib::nomemory(char *string) 
{
	fprintf(outfp,"malloc: out of memory making %s!! \n",string);
	exit(-1);
}

void SGAlib::initdata()
{
	cout<<"\n输入种群大小（20-100）：";
	cin>>popsize;
	cout<<popsize;
	if ((popsize%2)!=0) 
	{
		fprintf(outfp,"种群大小已设置为偶数\n");
		popsize++;
	}
	cout<<"\n染色体长度（21-48中取3的倍数）：";
	cin>>lchrom;
	cout<<lchrom;
	cout<<"\n最大世代数（100-300）：";
	cin>>maxgen;
	cout<<maxgen;
	cout<<"\n交叉率（0.2-0.9）：";
	cin>>pcross;
	cout<<pcross;
	cout<<"\n变异率（0.01-0.1）：";
	cin>>pmutation;
	cout<<pmutation;
}

void SGAlib::initpop() //初始化种群
{
	int j,j1,k,stop;
	unsigned mask=1;
	for(j=0;j<popsize;j++)
	{	
		for(k=0;k<chromsize;k++)
		{
			oldpop[j].chrom[k]=0;
			if (k==(chromsize-1))
				stop=lchrom-(k*(8*sizeof(unsigned)));
			else
				stop=8*sizeof(unsigned);
			for(j1=1;j1<=stop;j1++)
			{
				oldpop[j].chrom[k]=oldpop[j].chrom[k]<<1;
				if(flip(0.5))
					oldpop[j].chrom[k]=oldpop[j].chrom[k]|mask;
			}
		}
		oldpop->parent[0]=0;
		oldpop->parent[1]=0;
		oldpop->xsite=0;
		
		calcfitfunc(&oldpop[j]) ; //计算初始适应值
	}
	
}

void SGAlib::initreport()
{
	fprintf(outfp,"             基本遗传算法参数\n");
	fprintf(outfp,"-----------------------------------------------\n");
	fprintf(outfp,"      种群大小（popsize）   =%d\n",popsize);
	fprintf(outfp,"      染色体长度（lchrom）  =%d\n",lchrom);
	fprintf(outfp,"      最大进化代数（maxgen）=%d\n",maxgen);
	fprintf(outfp,"      交叉概率（pcross）    =%f\n",pcross);
	fprintf(outfp,"      变异概率（pmutation） =%f\n",pmutation);
	fprintf(outfp,"-----------------------------------------------\n");

}

void SGAlib::generation()
{
	int mate1,mate2,jcross,j=0;
	preselect();  //每代运算前进行预选
	do {
		//挑选交叉配对
		mate1=select();
		mate2=select();
		//交叉和变异
		jcross=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom);
		mutation(newpop[j].chrom);
		mutation(newpop[j+1].chrom);
		//解码，计算适应值
		calcfitfunc(&newpop[j]);
		//记录亲子关系和交叉位置
		newpop[j].parent[0]=mate1+1;
		newpop[j].xsite=jcross;
		newpop[j].parent[1]=mate2+1;
		calcfitfunc(&newpop[j+1]);
		newpop[j+1].parent[0]=mate1+1;
		newpop[j+1].xsite=jcross;
		newpop[j+1].parent[1]=mate2+1;
		j=j+2;
		
	} while(j<(popsize-1));

}

/*输出种群统计结果*/
void SGAlib::report()
{
	repchar(outfp,"-",100);
	fprintf(outfp,"\n");
	repchar(outfp," ",((80-17)/2));
	fprintf(outfp,"模拟计算统计报告\n");
	fprintf(outfp,"       世代数%3d",gen);
	repchar(outfp," ",(80-40));
	fprintf(outfp,"  世代数%3d\n",(gen+1));
	fprintf(outfp,"   个体染色体编码");
	repchar(outfp," ",lchrom-10);
	fprintf(outfp,"适应度   父个体  交叉位置  ");
	fprintf(outfp,"染色体编码");
	repchar(outfp," ",lchrom-8);
	fprintf(outfp,"适应度\n");
	repchar(outfp,"-",100);
	fprintf(outfp,"\n");
	writepop();
	repchar(outfp,"-",100);
	fprintf(outfp,"\n第%d代统计：\n",gen+1);
	fprintf(outfp,"总交叉操作次数=%d，总变异操作次数=%d\n",ncross,nmutation);
	fprintf(outfp,"  最小适应度：%d，最大适应度：%d，平均适应度：%f\n",min,max,avg);
	fprintf(outfp,"迄今发现最佳个体=〉所在代数：%d",bestfit.generation);
	fprintf(outfp,"  适应度：%d  染色体",bestfit.fitness);
	writechrom(bestfit.chrom);
	fprintf(outfp,"  对应的变量值：%d,%d,%d",bestfit.varible[0],bestfit.varible[1],bestfit.varible[2]);
	fprintf(outfp,"\n");
	repchar(outfp,"-",100);
	fprintf(outfp,"\n");
}

void SGAlib::writepop()
{
	individual *pind;
	int j;
	for(j=0;j<popsize;j++)
	{
		fprintf(outfp," %3d)  ",j+1);
		//当前代个体
		pind=&(oldpop[j]);
		writechrom(pind->chrom);
		fprintf(outfp,"    %d  ",pind->fitness);
		//新一代个体
		pind=&(newpop[j]);
		fprintf(outfp,"(%2d,%2d)   %2d  ",pind->parent[0],pind->parent[1],pind->xsite);
		repchar(outfp," ",6);
		writechrom(pind->chrom);
		fprintf(outfp,"    %d\n",pind->fitness);	
	}
}

void SGAlib::writechrom(unsigned *chrom) //输出染色体编码
{
	int j,k,stop,L=0;
	unsigned mask=1,tmp;
	char a[48];
	memset( a, ' ', sizeof(char)*48);
	
	for(k=0;k<chromsize;k++)
	{
		tmp=chrom[k];
		//fprintf(outfp,"%d:",tmp);
		
		if (k==(chromsize-1)) 
			stop=lchrom-(k*(8*sizeof(unsigned)));
		else
			stop=8*sizeof(unsigned);
		for(j=0;j<stop;j++)
		{	
			if (tmp&mask)
				a[L++]='1'; 
			else
				a[L++]='0'; 
			tmp=tmp>>1;	
		}
	}

	for(int i=L-1;i>=0&&a[i]!='\0';i--)
	{
		fprintf(outfp,"%c",a[i]);
	}
}


void SGAlib::preselect()
{
	int j;
	sumfitness=0;
	for(j=0;j<popsize;j++)
	{
		sumfitness+=oldpop[j].fitness;
		
	}
}

int SGAlib::select()//轮盘赌选择
{
	float sum,pick;