ga.cpp

遗传算法

/***************************************************************/ 
/*	 求 min(f(x1,x2) =100*(x[2]-x[1]*x[1])*(x[2]-x[1]*x[1])+(1-x[1])*(1-x[1]) 	   */
/*	 -2.048<= xi <= 2.048,  i = 1,2;   Delta = 0.001			   */
/***************************************************************/ 

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

#define POPSIZE 1200			// 群体个数 
#define MAXGENS 500				// 最大迭代代数 
#define NVARS 2					// 个体数
#define PXOVER 0.7				// 交叉概率
#define PMUTATION 0.005  		// 变异概率
#define UPBOUND 2.048			// 解取值范围上边界
#define LOWBOUND -2.048			// 解取值范围下边界
#define CODELEN 12				// 编码长度(12位二进制编码)
#define PRECS 4096				// 

typedef unsigned short U16;

typedef struct genotype			// 基因型
{ 
	double gene[NVARS];			// 解
	double fitness;				// 适应度
	double upper[NVARS];		// 解的上边界
	double lower[NVARS];		// 解的下边界
	double rfitness;			// 相对适应度
	double cfitness;			// 累加适应度
}GT; 

GT population[POPSIZE+1];		// 父代种群
GT newpopulation[POPSIZE+1];	// 子代种群


int generation;					// 当前代数
int cur_best;					// 最佳个体
FILE *galog;					// 输出文件	 


void initialize(void); 
U16 code(double);
double decode(U16);
double randval(double, double); 
void evaluate(void); 
void keep_the_best(void); 
void elitist(void); 
void select(void); 
void crossover(void); 
void Xover(int,int); 
void swap(double *,double *); 
void partswap(double *,double *, int point); 
void mutate(void); 

/***************************************************************/ 
// 初始化种群

void initialize(void) 
{ 
	int i, j; 

	// initialize variables within the bounds 
	for (i = 0; i < NVARS; i++) 
    { 
		for (j = 0; j < POPSIZE; j++) 
        { 
			population[j].fitness = 0; 
			population[j].rfitness = 0; 
			population[j].cfitness = 0; 
			population[j].lower[i] = LOWBOUND; 
			population[j].upper[i]= UPBOUND; 
			population[j].gene[i] = randval(population[j].lower[i], population[j].upper[i]); 
        } 
    } 
} 

/***************************************************************/ 
// 二进制编码函数

U16 code(double sour)
{
	int dc;
	dc = (U16)((sour - LOWBOUND)/(UPBOUND - LOWBOUND) * PRECS);
	if(dc == PRECS)
		dc = PRECS - 1;
	return dc;
}

/***************************************************************/ 
// 二进制译码函数

double decode(U16 sour)
{
	double ds;
	ds = (double)sour/PRECS * (UPBOUND - LOWBOUND) + LOWBOUND;
	return ds;
}

/***********************************************************/ 
// 产生给定范围的随机数

double randval(double low, double high) 
{ 
	double val; 
	val = ((double)(rand()%32768)/32768.0)*(high - low) + low; 
	return(val); 
} 

/*************************************************************/ 
// 评价函数：取函数值作为适应度

void evaluate(void) 
{ 
	int idx; 
	int i; 
	double x[NVARS+1]; 

	for (idx = 0; idx < POPSIZE; idx++) 
    { 
		for (i = 0; i < NVARS; i++) 
			x[i+1] = population[idx].gene[i]; 
      
		
		population[idx].fitness = 1/( 100*(x[2]-x[1]*x[1])*(x[2]-x[1]*x[1])+(1-x[1])*(1-x[1]) );
    } 
} 

/***************************************************************/ 
// 保留种群中的最佳个体

void keep_the_best() 
{ 
	int idx; 
	int i; 
	cur_best = 0;		/* stores the index of the best individual */ 

	for (idx = 0; idx < POPSIZE; idx++) 
    { 
		if (population[idx].fitness > population[POPSIZE].fitness) 
        { 
			cur_best = idx; 
			population[POPSIZE].fitness = population[idx].fitness; 
		} 
    } 
	/* once the best member in the population is found, copy the genes */ 
	for (i = 0; i < NVARS; i++) 
		population[POPSIZE].gene[i] = population[cur_best].gene[i]; 
} 

/****************************************************************/ 
// 最佳个体优先保留：如果本代最佳个体不如上代最佳个体，上代最佳
//     个体将替换本代最差个体(精英选择算法）

void elitist() 
{ 
	int i; 
	double best, worst;	 
	int best_mem, worst_mem; 

	best = population[0].fitness; 
	worst = population[0].fitness; 
	for (i = 0; i < POPSIZE - 1; ++i) 
    { 
		if(population[i].fitness > population[i+1].fitness) 
        {       
			if (population[i].fitness >= best) 
            { 
				best = population[i].fitness; 
                best_mem = i; 
            } 
			if (population[i+1].fitness <= worst) 
            { 
                worst = population[i+1].fitness; 
                worst_mem = i + 1; 
            } 
        } 
		else 
        { 
			if (population[i].fitness <= worst) 
            {
				worst = population[i].fitness; 
                worst_mem = i; 
            } 
			if (population[i+1].fitness >= best) 
            { 
                best = population[i+1].fitness; 
                best_mem = i + 1; 
            } 
        } 
    }

	if (best >= population[POPSIZE].fitness) 
	{ 
		for (i = 0; i < NVARS; i++) 
			population[POPSIZE].gene[i] = population[best_mem].gene[i]; 
		population[POPSIZE].fitness = population[best_mem].fitness; 
	} 
	else 
	{ 
		for (i = 0; i < NVARS; i++) 
			population[worst_mem].gene[i] = population[POPSIZE].gene[i]; 
		population[worst_mem].fitness = population[POPSIZE].fitness; 
	} 
}
 
/**************************************************************/ 
// 选择函数：比例选择

void select(void) 
{ 
	int idx, i, j; 
	double sum = 0; 
	double p; 

	/* find total fitness of the population */ 
	for (idx = 0; idx < POPSIZE; idx++) 
	{ 
		sum += population[idx].fitness; 
    } 

	/* calculate relative fitness */ 
	for (idx = 0; idx < POPSIZE; idx++) 
    { 
		population[idx].rfitness =  population[idx].fitness/sum; 
    }

	population[0].cfitness = population[0].rfitness; 

	/* calculate cumulative fitness */ 
	for (idx = 1; idx < POPSIZE; idx++) 
    { 
		population[idx].cfitness =  population[idx-1].cfitness + population[idx].rfitness; 
    } 

	/* finally select survivors using cumulative fitness. */ 
	for (i = 0; i < POPSIZE; i++) 
    { 
		p = rand()%32768/32768.0; 
		if (p < population[0].cfitness) 
			newpopulation[i] = population[0];       
		else 
        { 
			for (j = 0; j < POPSIZE;j++)       
				if (p >= population[j].cfitness && p < population[j+1].cfitness) 
					newpopulation[i] = population[j+1]; 
        } 
    } 

	/* once a new population is created, copy it back */ 
	for (i = 0; i < POPSIZE; i++) 
		population[i] = newpopulation[i];       
} 

/***************************************************************/ 
// 交叉选择函数 

void crossover(void) 
{ 
	int idx, one; 
	int first  =  0; 
	double x; 

	for (idx = 0; idx < POPSIZE; ++idx) 
    { 
		x = rand()%32768/32768.0; 
		if (x < PXOVER) 
        { 
			++first; 
			if (first % 2 == 0) 
				Xover(one, idx); 
			else 
                one = idx; 
        } 
    } 
} 

/**************************************************************/ 
// 交叉函数

void Xover(int one, int two) 
{ 
	int i, r; 
	int point;		// crossover point 

	/* select crossover point */ 
	r = rand() % (NVARS * CODELEN);
	i = r/CODELEN;
	point = r % CODELEN;

	partswap(&population[one].gene[i], &population[two].gene[i], point);

	for(++i; i<NVARS; i++)
		swap(&population[one].gene[i], &population[two].gene[i]);

} 

/*************************************************************/ 
// 全交换函数：变量值互换

void swap(double *x, double *y) 
{ 
	double temp; 

	temp = *x; 
	*x = *y; 
	*y = temp; 
} 

/*************************************************************/ 
// 部分交换函数：交换选定交叉点之后的所有信息

void partswap(double *x, double *y, int point) 
{ 
	U16 one, other;
	U16 tm1, tm2;
	U16 k = 0xfff;

	point ++ ;

	if(point < CODELEN)
	{
		k <<= (CODELEN - point);
		k = k & 0xfff;

		one = code(*x);
		other = code(*y);
		tm1 = (one << point) & 0xfff;
		tm1 >>= point;
		tm2 = (other << point) & 0xfff;
		tm2 >>= point;

		one = (one & k) | tm2;
		other = (other & k) | tm1;

		*x = decode(one);
		*y = decode(other);
	}
} 

/**************************************************************/ 
// 变异函数

void mutate(void) 
{ 
	int i, j, k; 
	double x; 
	U16 cd, t;
	U16 M ;

	for (i = 0; i < POPSIZE; i++) 
	{
		for (j = 0; j < NVARS; j++) 
		{
			M = 0x800;
			for (k = 0; k < CODELEN; k++)
			{
				x = rand()%32768/32768.0;
				if (x < PMUTATION)
				{
					cd = code(population[i].gene[j]);
					t = cd & M;
					cd = cd & (~M & 0xfff);
					t = ~t & M;
					cd = cd | t;
					population[i].gene[j] = decode(cd);
				}
				M >>= 1;
			}
        } 
	}
} 

/**************************************************************/ 
// 主函数

void main(void) 
{ 
	int i; 

	srand((unsigned)time(NULL));	// generater the starting point of random number
	if ((galog = fopen("galog.txt","w"))==NULL) 
    { 
		exit(1); 
    } 
	generation = 0; 

	initialize(); 
	evaluate(); 
	keep_the_best(); 
	while(generation < MAXGENS) 
    { 
		select(); 
		crossover(); 
		mutate(); 
		
		evaluate(); 
		elitist();
		
 		generation++; 
   } 
	fprintf(galog,"\n\n Simulation completed\n"); 
	fprintf(galog,"\n Best member: \n"); 
	printf("\n\n Simulation completed\n"); 
	printf("\n Best member: \n"); 


	for (i = 0; i < NVARS; i++) 
	{ 
		fprintf (galog,"\n var(%d) = %3.4f",i,population[POPSIZE].gene[i]); 
		printf ("\n var(%d) = %3.4f",i,population[POPSIZE].gene[i]); 
	} 
	fprintf(galog,"\n\n Best fitness = %3.4f",population[POPSIZE].fitness); 
	fprintf(galog,"\n\n min f(x[1],x[2]) = %3.4f\n ",1/population[POPSIZE].fitness);
	fclose(galog); 
	printf("\n\n Best fitness = %3.4f",population[POPSIZE].fitness); 
	printf("\n\n min f(x[1],x[2]) = %3.4f\n ",1/population[POPSIZE].fitness); 
} 
/***************************************************************/