sga.cpp

遗传算法的C++源码

#include "StdAfx.h"
#include <stdlib.h>
#include <malloc.h>
#include <stdio.h>
#include <winbase.h>

//#include <graphic.h>
#include <string.h>
#include <math.h>
//#include "graph.c"
/*Globle variable*/
struct individual //个体
{
	unsigned *chrom;//染色体
	double fitness;//个体适应度
	double varible;//个体对应的变量
	int xsite;	//交叉位置
	int parent[2];	//父个体
	int *utility;	//特定数据指针变量
}individual;

struct bestever
{
	unsigned *chrom;	//最佳个体染色体
	double fitness;		//最佳个体适应度
	double varible;		//最佳个体对应的变量
	int generation;		//最佳个体生成代
}bestever;

struct individual *oldpop;	//当前代种群
struct individual *newpop;	//新一带种群
struct bestever bestfit;	//最佳个体
double sumfitness;		//种群中个体适应度
double max;			//种群中个体最大适应度
double avg;			//种群中个体平均适应度
double min;			//种群众个体最小适应度
float pcross;			//交叉率
float pmutation;		//变异率
int popsize;			//种群大小
int lchrom;			//染色体大小
int chromsize;			//存储一个染色体所需要字节数
int gen;			//当前世代
int maxgen;			//最大世代数
int run;			//当前运行次数
int maxruns;		//总运行次数
int printstrings;	//输出染色体编码的判断
int nmutation;		//当前代变异放生次数
int ncross;			//当前代交叉发生次数
/***********;*******************************/
//随机数发生器使用的静态变量//
static double oldrand[55];
static int jrand;
static double mdx2;
static int rndcalcflag;
//文件指针
FILE *outfp;
/********************************************************/
#define INITRANDOM	0.123
#define MINVARIABLE -1
#define MAXVARIABLE 2
/*******************函数列表********************/
void advance_random();
int flip(float);
int rnd(int ,int);
void randomize();
double randomnormaldeviate();
float randomperc();
rndreal(float, float);
void warmup_random(float);
void initialize();
void initdata();
void initpop();
void initreport();
void generation();
void initmalloc();
void freeall();
void nomemory(char *);
void report();
void writepop();
void writechrom(unsigned*);
void preselect();
void statistics(struct individual*);
void title();
void repchar(FILE *,char*,int);
void skip(FILE*, int);
int select();
void objfunc(struct individual *);
int crossover(unsigned*,unsigned*,unsigned*,unsigned*);
void mutation(unsigned*);
/*******************函数列表********************/
/********************************************************/
/*************************************************/
//initialize()遗传算法初始化
/**************************************************/
void initialize()
{
	//键盘输入遗传算法参数
	initdata();
	//确定染色体的字体长度
	chromsize=(lchrom/(8*sizeof(unsigned)));
	if(lchrom%(8*sizeof(unsigned))) chromsize++;
	//分配给全局数据结构空间
	initmalloc();
	//初始化随机数发生器
	randomize();
	//初始化全局技术变量和一些数值
	nmutation=0;
	ncross=0;
	bestfit.fitness=0.0;
	bestfit.generation=0;
	//初始化种群，并统计计算结果
	initpop();
	statistics(oldpop);
	initreport();
}

/*************************************************/
//initdata() 遗传算法参数输入
/**************************************************/
void initdata()
{
/*	char answer[2];
//	setcolor(9);
//	setbkcolor(15);
	printf("种群大小（20-100）");
	scanf("%d",&popsize);
	if((popsize%2)!=0)
	{
		fprintf(outfp,"种群大小已经设置为偶数\n");
		popsize++;
	}
//	setcolor(9);
//	setbkcolor(15);
	printf("染色体长度(8-40);");
	scanf("%d",&lchrom);
//	setcolor(9);
//	setbkcolor(15);
	printf("是否输出染色体编码(y/n):");
	printstrings=1;
	scanf("%s",answer);
	if(strcmp(answer,"n")==0) printstrings=0;
//	setcolor(9);
//	setbkcolor(15);
	printf("最大世代数(100-300):");
	scanf("%d",&maxgen);
//	setcolor(9);
//	setbkcolor(15);
	printf("交叉率(0.2-0.9):");
	scanf("%d",&pcross);
//	setcolor(9);
//	setbkcolor(15);
	printf("变异率(0.01-0.1):");
	scanf("%d",&pmutation);
	*/
	printstrings=1;
	popsize=30;
	lchrom=32;
	maxgen=150;
	pcross=0.8;
	pmutation=0.05;
}
/*************************************************/
//initreport() 初始化参数输出
/**************************************************/
void initreport()
{
	skip(outfp,1);
	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");
	skip(outfp,1);
	fflush(outfp);

}
/*************************************************/
//initmalloc() 为全局变量分配数据空间
/**************************************************/
void initmalloc()
{
	unsigned nbytes;
	int j;
	//分配给当前代和新一代种群北内存空间
	nbytes=popsize*sizeof(struct individual);
	if((oldpop=(struct individual *)malloc(nbytes))==NULL) nomemory("oldpop");
	if((newpop=(struct individual *)malloc(nbytes))==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((bestfit.chrom=(unsigned *)malloc(nbytes))==NULL) nomemory("bestfit chromosomes");
}
/*************************************************/
//freeall() 释放全局变量数据空间
/**************************************************/
void freeall()
{
	int i;
	for(i=0;i<popsize;i++)
	{
		free(oldpop[i].chrom);
		free(newpop[i].chrom);
	}
	free(oldpop);
	free(newpop);
	free(bestfit.chrom);
}
/*************************************************/
//nomemory() 内存不足，推出
/**************************************************/
void nomemory(char *string)
{
	fprintf(outfp,"malloc:out of memory %s!\n",string);
	exit(-1);
}
/*************************************************/
//report() 输出种群统计结果
/**************************************************/
void report()
{
	repchar(outfp,"-",80);
	skip(outfp,1);
	if(printstrings==1)
	{
		repchar(outfp," ",((80-17)/2));
		fprintf(outfp,"模拟计算统计报告\n");
		fprintf(outfp,"世代数%3d",gen);

		repchar(outfp," ",((80-28)/1));
		fprintf(outfp,"\n");
		fprintf(outfp,"世代数%3d\n",(gen+1));

		fprintf(outfp,"个体染色体编码");
		repchar(outfp," ",lchrom-5);
		fprintf(outfp,"适应度");
		repchar(outfp," ",5);
   		fprintf(outfp,"父个体");
		repchar(outfp," ",3);
		fprintf(outfp,"交叉位置");
		repchar(outfp," ",2);
		fprintf(outfp,"染色体编码");
		repchar(outfp," ",lchrom-5);
		fprintf(outfp,"适应度\n");
		repchar(outfp," -",80);
		skip(outfp,1);
		writepop();
		repchar(outfp," -",80);
		skip(outfp,1);
	}
	fprintf(outfp,"第%d代统计：\n",gen);
	fprintf(outfp,"总交叉操作次数=%d,总变异操作数=%d\n",ncross,nmutation);
	fprintf(outfp,"最小适应度：%f,最大适应度:%f,平均适应度:%f\n",min,max,avg);
	fprintf(outfp,"迄今发现最佳个体所在代数：%d\n",bestfit.generation);
	fprintf(outfp,"适应度：%f染色体\n",bestfit.fitness);
	writechrom((&bestfit)->chrom);
	fprintf(outfp,"对应的变量值：%f\n",bestfit.varible);
	skip(outfp,1);
	repchar(outfp,"-",80);
	skip(outfp,1);
}

/*************************************************/
//writepop() 输出种群统计结果
/**************************************************/
void writepop()
{
	struct individual *pind;
	int j;
	for(j=0;j<popsize;j++)
	{
		fprintf(outfp,"%3d)",j+1);
		//当前代个体 
		pind=&(oldpop[j]);
		writechrom(pind->chrom);
		fprintf(outfp,"\t%8f\t",pind->fitness);
		//新一代个体
		pind=&(newpop[j]);
		fprintf(outfp,"(%2d,%2d),%2d\t",pind->parent[0],pind->parent[1],pind->xsite);
		writechrom(pind->chrom);
		fprintf(outfp,"\t%8f\n",pind->fitness);
	}
}

/*************************************************/
//writechrom() 输出染色体编码
/**************************************************/
void writechrom(unsigned *chrom)
{
	int j,k,stop;
	unsigned mask=1,tmp;
	for(k=0;k<chromsize;k++)
	{
		tmp=chrom[k];
		if(k==(chromsize-1))
			stop=lchrom-(k*(8*sizeof(unsigned)));
		else
			stop=8*sizeof(unsigned);
		for(j=0;j<stop;j++)
		{
			if(tmp&mask)
				fprintf(outfp,"1");
			else
				fprintf(outfp,"0");
			tmp=tmp>>1;
		}
	}
}
/*************************************************/
//statistics() 计算种群统计数据
/*************************************************/
void statistics(struct individual *pop)
{
	int i,j;
	sumfitness=0.0;
	min=pop[0].fitness;
	max=pop[0].fitness;
	//计算最大，最小和累积适应度
	for(j=0;j<popsize;j++)
	{
		sumfitness+=pop[j].fitness;
		if(pop[j].fitness>max) max=pop[j].fitness;
		if(pop[j].fitness<min) min=pop[j].fitness;
		//new global best - fit individual
		if(pop[j].fitness>bestfit.fitness)
		{
			for(i=0;i<chromsize;i++)
				bestfit.chrom[i]=pop[j].chrom[i];
			bestfit.fitness=pop[j].fitness;
			bestfit.varible=pop[j].varible;
			bestfit.generation=gen;

		}
	}
	//计算平均适应度
	avg=sumfitness/popsize;
}

/*************************************************/
//title() 
/*************************************************/
void title()
{
	//settextstyle(0,0,4);
	fprintf(outfp,"SGA Optimizer");
	//setcolor(9);
	//disp_hz24("基本遗传算法",220,60,25);
}

/*************************************************/
//repchar() 
/*************************************************/
void repchar(FILE *outfp,char *ch,int repcount)
{
	int j;
	for(j=0;j<=repcount;j++)
		fprintf(outfp,"%s",ch);
}
void skip(FILE *outfp,int skipcount)
{
	int j;
	for(j=1;j<=skipcount;j++)fprintf(outfp,"\n");
}